A Synthesis on the Paper Entitled “Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks” by D. Chiu and R. Jain

D. Chiu and R. Jain in their paper entitled “Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks” analyzed several increase/decrease algorithms for increasing or decreasing the load a user is contributing to a network. This is in response to the fact that network congestion persists as an issue across heterogenous networks built on old and new technologies. These algorithms were analyzed with the variable indicators efficiency, fairness, convergence time and size of oscillations as metrics. The authors differentiated congestion control against congestion avoidance with the previous being a reactive mechanism and the latter a proactive mechanism. Both mechanisms are important for a inter/network and are worth devoting time for more in-depth study. The paper though focuses on congestion avoidance. The analysis in this paper came about due to the authors’ selection of algorithms to be used for the variant called binary feedback scheme proposed in another paper. The analysis is also scoped to a class of distributed algorithms designed for distributed decision-making. Specifically, these algorithms belong to the category of decentralized decision making algorithms in which the decision of how to respond to the current status of the network as indicated by the resource managers is distributedly assigned to the hosts.

In the paper the authors defined the state of congestion of a network to be the number of packets in it. Each host’s load contributes to the overall load of the network. Initially each host has an initial value for its resource demand. This demands are served by the resource managers as best as the situation allows. Upon service to hosts the resource managers also describes the status of the network. Upon receipt of the status indicator, cooperative response is expected  from the hosts. On heavy load situations, the hosts are expected to lighten their demands so the network could cope up gradually. On light load situations, the hosts are encouraged to use up resources as much as the system could support. As noted in the paper, the succeeding demand of a host is a function of the network status as defined by the resource managers and the host’s previous resource demand. The network status as indicated by the resource managers is what the authors call as binary feedback given that the values signifying the status are define as 0 for underload and 1 for overload. This choice of design gives the benefit of simplicity of implementation of the algorithm for the resource manager.

The change (increase or decrease) in a host’s resource demand is what the authors define as the host’s control. Along with this several linear controls were also presented, namely, (1) multiplicative increase/multiplicative decrease, (2) additive increase/additive decrease, (3) additive increase/multiplicative decrease, and (4) multiplicative increase/additive decrease. These controls were evaluated by the authors based on the previously mentioned set of criteria, namely, (1) efficiency, (2) fairness, (3) distributednes and (4) convergence. The metric of efficiency describes how close the utilization of the overall resources (load) in the system to the maximum load the network could allow. This metric does not take into consideration the allocation of resources to each host. The metric of fairness is defines the allocation of resources to each host in the network. The hosts are divided into classes defined by the type of resource with which they are having bottleneck. Each host in each class should have an equal allocation of  bottleneck with the other hosts in that class. This scheme of allocation is defined in other papers as maximum fairness criterion. The information on the total load capacity of the network and the total number of hosts sharing the total resources are known to resource managers and the dissemination of these information to all hosts should bear a very minimum effort. Control schemes with shorter convergence time (time it takes the system to get into the state of equilibrium) and smaller oscillation amplitude (defines the variance from the equilibrium state) are also required.

In the paper, the mentioned control schemes are first evaluated to determine which among these schemes converge. From the resulting set of feasible schemes a subset satisfying the distributedness criterion is also identified. From this subset of feasible control schemes a subset which optimizes the trade-off between fairness and efficiency is further identified. For identifying the ratio of fairness to efficiency of a specific control scheme, a two dimensional space is utilized in which the horizontal axis corresponds the resource allocation for a specific user and the horizontal axis for another user. A point in the space, defined by (a, b) represents the allocation of resources for the two hosts a and b. The target level of efficiency is defined in the space to be the line defined by the set of all points such that a + b = total load capacity. On the the other hand, the target level of fairness is defined to be the line defined by the set of all points such that a = b. The goal of a control scheme is to bring the allocation of resources for the two users into the intersection of  these two lines, as it is in that point that the trade-off between fairness and efficiency is optimized. The convergence to fairness and efficiency were separately discussed by the authors in the paper. After considering the convergence of the control schemes, the authors looked into the integration of the distributedness criterion. The distrbutedness criterion limits further the set of feasible controls into those which do not require knowledge of information about the state of the system but only the binary feedback from the resource manager to the hosts. The total set of restrictions therefore limits the set of feasible controls into those which can converge distributively into fairness and efficiency.

In conclusion, the authors note that the total restriction on the set of feasible controls is represented in the two dimensional plane as the intersection of the regions representing the individual restrictions on convergence in fairness and efficiency. In the plane it is represented as a line connecting the origin and point of intersection of convergence to efficiency and fairness.

In addition to what was presented in the paper, the authors also briefly looked into non-linear controls and presented some practical considerations for implementation of the control algorithms.

It is important to note that the success of congestion avoidance based on the control schemes presented in the paper depends greatly on the cooperative response of the hosts. Uncooperative behavior of the hosts can be handled by the network through enforcing controls in the gateways as resource managers. As a host in the network it is still advantageous in general to cooperate with the rest of the network to have a better network usage experience. Implicitly, the idea of collective sacrificial response from the hosts assures the whole network of better performance and therefore positively reflects back to the hosts as better network usage experience.

Advertisements

About Jeffrey A. Aborot

> Background: BS Computer Science, University of the Philippines Baguio. > Work: Advanced Science and Technology Institute - Department of Science and Technology of the Philippines. > Academics: MS Computer Science (on-going), Algorithms and Complexity Laboratory, Computer Science Department, UP Diliman > Languages: Filipino, Tagalog, Cuyunon, English, Java, Python, C. > Operating Systems: Linux, OSX. > Weird Stuff: Bunch of Pentax film cams.
This entry was posted in Computer Networks and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s