Probabilistic Packet Scheduling: Achieving Proportional Share Bandwidth Allocation

Abstract:

This paper describes and evaluates a probabilistic packet scheduling
algorithm for achieving proportional bandwidth allocation among TCP
connections. With our approach, either end hosts or edge routers tag
each packet with a ticket that represents the share of network
bandwidth this flow should receive. Routers then probabilistically
decide when to forward/drop a packet based on the value of this ticket
and the current congestion level. Our approach accommodates network
topologies that span multiple domains by allowing a packet to trade in
the tickets it was granted in the source domain for an equitable
number of tickets in the target domain. The bandwidth allocation can
be controlled by either a sender-based or a receiver-based version of
the algorithm.