D.M. Chiu, R Jain/ Congestion Avoidance in Camputer Network This papel contenlaLes un a detailed analys At the other end of the spectrum, we have de of the increase/decrease algorithms. This analysis centralized decision-making. In this case the deci- resulted in the selection of the increase/decrease sions are made by the users while the resources algorithms used in the binary feedback scheme feed formation regi garding current resource usage. proposed in [1ll and [10]. However, the analysis Algorithms studied by Jaffe [5] and later exten presented here is general and applies to many sions by Gaini [2] and Mosely [91 are all good other applications besides congestion avoidance examples of this approach. Briefly, the binary feedback scheme for conges- In this paper we analyze a class of decentral- tion avoidance operates as follows. The resources ized decision-making algorithms that are based on in the network monitor their usage and determine a special form of feedback, namely the feedback if they are loaded below or above an optimal from the resource is a binary signal. This binary level Depending upon the load level, the resource signal indicates whether the resource is currentI sends a binary feedback (1-overloaded, 0 erloaded or underutilized. A very good reason nderloaded) to the users who then adjust their for considering a binary form of feedback is the using an increase/ decrease algorithm. Thi motivation of making the controller/ manager of binary feedback is sent by setting a bit in the the resource as simple and efficient as possible packet header. The use of a bit in the packet The requirement of a binary feedback often min header as a feedback mechanism has been incor- mizes the work at the resource in generating the porated into the OSI connectionless networking feedback protocol standards [4]. The bit is called a"conges- n experienced bit " and is a part of a field called 1.3. Notations and Definition The abstract model assumes that all the users Figure 2 shows the assumed model of the net sharing the same bottleneck will receive the same work with n users sharing it. The congestion state feedback, Based on this feedback, the users try to of the system is determined by the number of adJust their load so that the bottleneck is effi- packets in the system. We assume a discrete time iently used as well as equally shared by all users. operation with time divided into small slots.'These In this abstracted context. we assume that the slots basically represent intervals at the beginning feedback and control loop for all users is synchro- of which the users set their load level based on the nous, that is, all users receive the same feedback network feedback received during the previous and react to it: the next feedback is then gener ted after all users have reacted to the feedback x(1), then the total load at the bottleneck re and so on. Also, we concentrate on one bottleneck source would be Ex, (t),and the state of the resource and the users that share it. Because of system is denoted by the n-dimensional vector these abstractions, we are able to demonstrate x(0) some of the subtle behavior of this type of al erating at or near the knee, all resources de- gorith. The results piescuted licle wele verified Mandel by the users are granted (this is not true by detailed simulations of real networks [7, 10. 111. at the cliff). Thus, x, (()denotes the ith user s 1.2 Past Work User J he algorithms studied here belong to a class of distributed algorithms for managing distributed pectrum of such distributed al- User 2 Xxi> goni gorithms have been studied in the literature. At onc cnd of thc spcctrum, we havc centralized decision-making. In this paradigm, information (about user demands) flows to the resource managers, and the decision of how to allocate the User n resource is made at the resource. The analysis by Sanders [12] is a good example of this approach Fig 2. A control system model of a users sharing a network