IntroductionFairnessDefinitions of fairnessMax-min fairnessProportional fairnessShadow prices and utilityRate adaptionEfficiencyModeling TCPECN, AQM and REDExplicit congestion notificationActive queue managementRandom early detectionPricing and REDConclusionsU C BDepartment of Electrical Engineering and Computer ScienceEE228A Communication NetworksReport for the Final ProjectFlow Control for Best-Effort Networks:Fairness and EfficiencyXiaotian [email protected] 28, 2001AbstractThe Internet is established on the best-effort service model. The Transmission Control Pro-tocol employed in the current Internet has both fairness and efficiency issues. Pricing schemehas been proposed to address the fairness issue and prevent aggressive users occupying exces-sive network resource. Random early detection (RED) for the incipient congestion in routers,together with explicit congestion notification, is able to maintaining a relative small queuesize, thus improves efficiency of the network. It also solves the flow synchronization prob-lem related to the tail-drop and other queue management mechanisms. Combination of thepricing scheme and RED is proposed in the effort to address the fairness and efficiency issuessimultaneously.1 IntroductionThe Internet is a best-effort network: It treats all packets the same and exerts its best effort todeliver the packets without discrimination or quality of service (QoS) guarantees. The packetscould be delayed or dropped when congestion occurs. The Transmission Control Protocol (TCP)was introduced to deal with congestion. TCP is a receiver-driven end-to-end window-based flowcontrol mechanism. It adjusts the transmission rate and/or resends the lost packets according to thereceiver’s acknowledgements.The success of the TCP congestion control has been based on the cooperation between theusers. The congestion control algorithms of TCP were deployed universally and users had beenadhering to these rules. However, the incentives for misbehaving have always existed, and with theincrease of user populations, it would happen more frequently that TCP algorithms are modified to1strive more aggressively for a larger share of available bandwidth. Misbehaving users are rewardedby receiving a larger fraction of bandwidth than its “fair share”, at the cost of responsible users. Andusers of the Internet are not aware of their competitors’ behavior. It is well known, from the gametheory, that this kind of cooperation is unstable, since the non-cooperative users will potentiallybe rewarded if the other users remain cooperative, and there is no risk of being panelized formisbehaving. However, it is also well known in the game theory that non-cooperative actions oftenlead to suboptimal outcomes. Therefore, in order to keep the users operating cooperatively for anoptimal utilization of resources, fairness has to be defined and incentives for cooperation have tobe created.The current TCP employs an implicit feedback mechanism—packet-dropping. This mecha-nism creates both efficiency and effectiveness problems. If congestion occurs near the destinationof packets and the router has to drop these packets, then the bandwidth used by these packets toreach the congested router is wasted. Also, the conceived network status by the end-users basedon this implicit feedback information could be misleading and not representing the actual networkcondition. Therefore, it will be beneficial to let the routers to play a more active role and provideexplicit and accurate information to the end-users, since the routers know exactly their own sta-tus. On the other hand, the tail-drop method employed by current routers also has some problems.The tail-drop method takes effect too late. It signals congestion to the users only when the queuehas overflowed and often causes the full queue length sustained. It is also possible to introduceglobal synchronization in the network with tail-drop routers. When a queue overflows, it is likelythat packets from many different sources are dropped. Those users reduce their transmission ratesimultaneously and their control actions become synchronized. This could lead to link underuti-lization or lockout for some users. This phenomenon is described in [1]. Therefore, more activequeue management mechanism in routers is desired.In the following sections, the fairness and efficiency issues are discussed in more details andmechanisms (pricing and random early detection) are presented to address these issues. A possiblesolution of combining the two mechanisms is also proposed to achieve fairness and efficiency atthe same time.2 FairnessAs pointed out in the introduction, effectiveness of the current TCP flow control algorithm relieson the assumption that all the Internet users are cooperative. However, there is no mechanismemployed to prevent users from misbehaving. With the evolution of the Internet, it is becomingmore important to establish effective mechanisms to maintain cooperation. But first the definitionof fairness has to be established.22.1 Definitions of fairness2.1.1 Max-min fairnessThe most common notion of fairness is the so-called max-min fairness, which is a result of optimi-zation-under-uncertainty. It is based on the observation that rational users with limited knowledgetend to make a decision so that they will have the greatest benefit under the least advantage situ-ation, which is often formed as a max-min problem. Max-min fairness is defined as follows [2]:A vector of resource allocations x is max-min fair if for any other feasible (i.e., the sum of theallocations does not exceed the capacity of the resource) allocation vector y there exists a user jsuch that yj> xj, then there exists a user i such that yi< xi< xj.Max-min fairness is widely used in cases where some users’ demand is smaller than others’.It operates as follows:1. Resources are allocated in increasing order of demand.2. A user is never allocated a share higher than its demand.3. All users with unsatisfied demands are allocated equal shares.Initially, all users get at least as much as the small users’ demand. Then the remaining resourcesare distributed evenly among all unsatisfied users. This fairness criterion favors users with smalldemand absolutely, in the sense that no matter how large increase in the allocation for a user withlarger demand cannot compensate for the
View Full Document
Unlocking...