D.-M. Chiu, R. Jain/Congestion Aeoidance in Computer Networks class ought to have the equal sliaie uf tlie but- Responsiveness tleneck. Thus, a system in which x, (t)=x()vi,J sharing the same bottleneck is operating fairly. If all users do not get exactly equal allocations, the system is less fair and we need an index or a Goal Smoothness function that quantifies the fairness. One such Total load on Fairness: F(r) n(∑x2) the network This index has the following properties (a) The fairness is bounded between 0 and 1(or 0% and 100%). A totally fair allocation( with Fig 3. Responsiveness and smoothness all x, 's equal) has a fairness of I and a totally unfair allocation(with all resources (4)Convergence: Finally we require the contro given to only one user)has a fairness of 1/n scheme to converge. Convergence is generally which is 0 in the limit as n tends to oo measured by the speed with which(or time taken (b)The fairness is independent of scale, i.e., till) the system approaches the goal state from any (c)The fairness is a continuous function, Any of the feedback, the system does not generally slight change in allocation shows up in the converge to a single steady state. Rather, the sys- fairness tem reaches an"equilibrium"in which it oscillates (d )If only k of n users share the resource around the optimal state. The time taken to reach equally with the remaining n-k users not this"equilibrium" and the size of the oscillations receiving any resource, then the faimess jointly deteRmine tie convergene. Te Lille dv termines the responsiveness, and the size of the For other properties of this fairness function, see oscillations determine the smoothness of the con- [6] trol. Ideally we would like the time as well as ( Distributedness: The next requirement that oscillations to be small. Thus, the controls with we put on the control scheme is that it be distrib- smaller time and smaller amplitude of oscillations uted. A centralized scheme requires complete are called more responsive and more smooth, re- knowledge of the state of the system. For example, pectively, as shown in Fig. 3. we may want to know each individual users de- Imand or their sulll. Tlis inforMation nlay be 1,5 Outline uf this Puper available at the resourcc. However, conveying this information to each and every user causes consid In this paper, we develop a simple and intuitive erable overhea d, especially since a user may be methodology to explain when and why a control g several resources at the same time. We are converges. We address the following questions thus primarily interested in control schemes that What are all the possible solutions that converge to an be implemented in real networks and, there efficient and fair states? How do we compare those fore, we assume that the system does the mini- controls that converge? mum amount of feedback. It only tells whether it The paper is organized as follows In Section is underloaded or overloaded via the binary feed e will characterize the set of all linear controls back bits. Other information such as X and thc and, thus, identify the set of feasibl number of users sharing the resource are assumed ntrols. Then we narrow down the feasible set to to be unknown by the users. This restricts the set a subset that satisfies our distributedness criterion of feasible schemes. We therefore, describe the set These subset still includes controls that have un- of feasible schemes with and without this restric- acceptable magnitudes of oscillation or those that tion converge too slowly. Then in Section 3, we discuss