Mechanisms are provided for tracing a route taken by a packet in a Software Defined Network (SDN). Each switch in the SDN is assigned a first color label, from a set of color labels, such that such that adjacent switches have different color labels. Rules are installed in each switch to forward a received data packet to the SDN controller in response to a second color label of the received data packet not matching the first color label assigned to the switch. A second color label, from the set of color labels, is assigned to a trace data packet. A route of the trace data packet is traced through the SDN based on the second color label and application of the one or more rules to the trace data packet at each of the switches in the SDN as the trace data packet is received by each of the switches in the SDN.