Copyright © (2002) by Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distrubuted for profit or commericial advantage. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.
Most of the end-to-end congestion control schemes are "voluntary'' in nature and critically depend on end-user cooperation. We show that in the presence of selfish users, all such schemes will inevitably lead to a congestion collapse. Router and switch mechanisms such as service disciplines and buffer management policies determine the sharing of resources during congestion. We show, using a Game Theoretic approach, that all the currently proposed mechanisms, either encourage the behaviour that leads to congestion ("Evil behaviour'') or are oblivious to it.
We propose a sample service discipline called Rate Inverse Scheduling (RIS) that punishes Evil behaviour and rewards Good (congestion avoiding) behaviour in such a way that the resulting "Selfish User's Equilibrium'' (Nash Equilibrium) leads to (max-min) fair allocation of resources. We show that RIS solves the problems of excessive congestion due to unresponsive flows, aggressive versions of TCP, multiple parallel connections and is fair to TCP as well.
By: Rahul Garg, Abhinav Kamra, Varun Khurana
Published in: ACM Computer Communications Review, volume 32, (no 3), pages 47-61 in 2002
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .