We present a solution of a class of network utility maximization (NUM) problems using minimal communication. The constraints of the problem are inspired less by TCP-like congestion control but by problems in the area of internet of things and related areas in which the need arises to bring the behavior of a large group of agents to a social optimum. The approach uses only intermittent feedback, no inter-agent communication, and no common clock. The proposed algorithm is a combination of the classical AIMD algorithm in conjunction with a simple probabilistic rule for the agents to respond to a capacity signal. This leads to a nonhomogeneous Markov chain and we show almost sure convergence of this chain to the social optimum.
The AIMD literature is huge and it is not straightforward to discuss the available results in any sort of compact manner here. We refer interested readers to some recent works on this topic in the context of TCP and internet congestion control @cite_22 @cite_15 @cite_11 @cite_26 @cite_19 @cite_26 @cite_6 @cite_49 @cite_48 . Much of this work is based on fluid approximations of AIMD dynamics; the notable exceptions are @cite_42 @cite_1 @cite_2 . The latter of these papers make use of tools from iterated function systems to deduce the existence of such a unique probability distribution for standard linear AIMD networks (of which TCP is an example) under an assumption on the underlying probability model (albeit under very restrictive assumptions). To the best of our knowledge, this paper, along with the companion paper @cite_42 , established for the first time, the stochastic convergence of AIMD networks. However, the window of infinite length considered in this paper goes well beyond the set-up in these papers. In particular, the result presented in this paper may be considered as the limiting case of the results presented in these papers.
@cite_26 @cite_22 @cite_48 @cite_42 @cite_1 @cite_6 @cite_19 @cite_49 @cite_2 @cite_15 @cite_11
1867902620 2132210216 2062284068 2100166367 1591231997
The proposals in this document are experimental. While they may be deployed in the current Internet, they do not represent a consensus that this is the best method for high-speed congestion control. In particular, we note that alternative experimental proposals are likely to be forthcoming, and it is not well understood how the proposals in this document will interact with such alternative proposals. We study communication networks that employ drop-tail queueing and Additive-Increase Multiplicative-Decrease (AIMD) congestion control algorithms. It is shown that the theory of nonnegative matrices may be employed to model such networks. In particular, important network properties, such as: 1) fairness; 2) rate of convergence; and 3) throughput, can be characterized by certain nonnegative matrices. We demonstrate that these results can be used to develop tools for analyzing the behavior of AIMD communication networks. The accuracy of the models is demonstrated by several NS studies. This papers analyzes a class of nonlinear additive-increase multiplicative-decrease (AIMD) protocols that are widely deployed in communication networks. It is demonstrated that the use of these protocols guarantees that the system has a unique stable outcome to which it converges geometrically under all starting points. The development is based on a contraction argument and the derivation of explicit bounds on the contraction coefficient of corresponding operators in terms of the network parameters. In particular, bounds on the corresponding rate of convergence are obtained, improving upon known bounds for standard (linear) AIMD networks. High-speed networks with large delays present a unique environment where TCP may have a problem utilizing the full bandwidth. Several congestion control proposals have been suggested to remedy this problem. The existing protocols consider mainly two properties: TCP friendliness and bandwidth scalability. That is, a protocol should not take away too much bandwidth from standard TCP flows while utilizing the full bandwidth of high-speed networks. This work presents another important constraint, namely, RTT (round trip time) unfairness where competing flows with different RTTs may consume vastly unfair bandwidth shares. Existing schemes have a severe RTT unfairness problem because the congestion window increase rate gets larger as the window grows ironically the very reason that makes them more scalable. RTT unfairness for high-speed networks occurs distinctly with drop tail routers for flows with large congestion windows where packet loss can be highly synchronized. After identifying the RTT unfairness problem of existing protocols, This work presents a new congestion control scheme that alleviates RTT unfairness while supporting TCP friendliness and bandwidth scalability. The proposed congestion control algorithm uses two window size control policies called additive increase and binary search increase. When the congestion window is large, additive increase with a large increment ensures square RTT unfairness as well as good scalability. Under small congestion windows, binary search increase supports TCP friendliness. The simulation results confirm these properties of the protocol. The traditional TCP-Reno is not capable of achieving a high throughput in high-speed networks due to its highly conservative and loss-dependent congestion control mechanism. Although TCP-Vegas achieves a good link utilization due to its proactive type of congestion control mechanism that uses RTT as an indication of network congestion, it lacks friendliness to TCP-Reno. Protocols such as HighSpeed-TCP and Scalable-TCP have been proposed to address this problem, but they behave non-friendly to TCP-Reno especially when sharing high bandwidth links. In order to improve the friendliness with TCP-Reno and throughput performance in high-speed networks, we propose a new congestion control mechanism, TCP-xHS (High-speed) that harmonizes the fast ramping and proactive congestion controlling approaches of HighSpeed-TCP and TCP-Vegas. Through simulation results we justify the effectiveness of TCP-xHS for a wider range of link bandwidths.