Incentive-compatible differentiated scheduling

In this paper, we take a novel approach at service dieren-tiation in packet-switched networks. Existing mechanisms for delay control and dierentiation typically require some form of explicit resource allocation and consequently, admis-sion control. We propose incentive-compatible dierentiated scheduling as a basic building block for Internet service pro-visioning. This scheduling scheme enables policy-free ap-proximate service dierentiation without admission control, for example at Internet peering exchanges. In addition, the same building block can also facilitate precise service dif-ferentiation in combination with several forms of admission control. We present the basic design of a scheduling al-gorithm and discuss its implementation details and design alternatives. We prove that the algorithm has strong game-theoretic properties and present some initial simulations il-lustrating the eect of this scheduler on Internet trac. 1