A network element includes circuitry and multiple ports. The multiple ports are configured to connect to a communication network. The circuitry is configured to receive via one of the ports a packet that originated from a source node and is destined to a destination node, the packet including a mark that is indicative of a cumulative state derived from at least bandwidth utilization conditions of output ports that were traversed by the packet along a path, from the source node up to the network element, to select a port for forwarding the packet toward the destination node, to update the mark of the packet based at least on a value of the mark in the received packet and on a local bandwidth utilization condition of the selected port, and to transmit the packet having the updated mark to the destination node via the selected port.