Probabilistic Packet Scheduling: Achieving Proportional Share Bandwidth Allocation
Report ID: TR-632-01Author: Peterson, Larry / Zhang, Ming / Krishnamurthy, Arvind / Wang, Randolph Y.
Date: 2001-02-00
Pages: 14
Download Formats: |PDF| |Postscript|
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.