SideBar

Applications of distributed control in telecommunications systems design

Distributed control theory is a system in which multiple automata, execute the same or similar algorithm, using their local view of the system, to jointly achieve an equilibrium, which maximizes some target system parameter over the entire system. Typical distributed control systems will have zero direct communication between the automata. There may be a network controller, which serves the role of giving feedback to the automata using a fixed algorithm. By appropriate choice of the control and feedback algorithms, it is possible to ensure that, from any given starting point, the automata achieve a an equilibrium, which is within some given margin of the globally optimal solution.

In this article, we shall review distributed control in the context of communication networks. We shall review the basic theory of distributed control, and three specific applications of the same. The last application will introduce the reader to strategic aspects of distributed control, which is a field of increasing importance.

Basic theory

A very good introduction to the problem of distributed control is given in [Kleinrock93], where we see entirely independent automata converge to a global equilibrium for a statistical system, using a very simple algorithm with very limited memory. At its very least, this paper shows unequivocally that distributed control works. Of course, it only provides one example of how to choose an optimizing algorithm, and not a general technique.

A more general result comes from the following:

What this implies is that, given appropriate feedback design, any algorithm which maximizes the local reward will also lead to a global equilibrium arbitrarily close to the global optimum. The trick is to design the feedback mechanism and reward function g() to achieve the conditions required. One of the key conditions is that there must exist a finite local maximum. For a more in-depth treatment of the other conditions, see [Foschini93] and others.

The case of Ethernet

Ethernet is a good example of distributed control, with a large number of very interesting problems hidden in its deceptively simple design. Consider the case when a large number of Ethernet hosts try to gain access to the network. The initial randomizing interval is very small, so effectively, they will all try to transmit at the same time, which causes collision. When the hosts detect collision, they backoff i.e. they double the randomizing interval, select a random time-period from within this interval and sleep. After waking up, they try accessing the network again.

It is clear that the optimal value of the randomizing interval is n, the number of hosts trying to access the network. In that case, assuming that the hosts are selecting their sleep periods in a random and uncorrelated pattern, exactly one host will wake up at any given time and access the network. The mechanism described above is nothing but an algorithm to determine the value of n. The idea of period-doubling is to do a binary search for the value of n. Unfortunately, as shown in [Molle94], the Ethernet algorithm has actually very poor convergence and actually degenerates into a linear search. It also violates the principle of conservation of work, especially at times when conservation of work is most important. More details are available in [Molle94]

Distributed power control in a cellular network

Uplink Power control in cellular networks is another example of power control. Here the system parameter is the total interference and the local parameter for optimization is the signal to interference ratio at the receiver. The optimum value for the individual endpoint is the target SIR, which is a minimum threshold required for quality. For a hybrid network, the target SIR for different hosts may be different dependent on the kind of traffic they are carrying. There are many algorithms for uplink power control, see [Foschini93], [Zander98], etc. Most of them show strong convergence properties. An interesting set of algorithms are described in [Foschini93] known as the genie algorithms; the algorithms work if and only if an equivalent solution exists in a centralized model i.e. if there could exist a genie which provided a centralized algorithm for uplink control, then the genie could very well be replaced by distributed algorithms.

The case of TCP - distributed control as a game-theory problem

The third and last example here is TCP. The scenario is a single network, with multiple TCP connections running over it. There is one single buffer with limited buffer space, through which all connections are routed. The TCPs have to transmit at a rate, so that the aggregate rate is lower than the clearing rate of the router. i.e. . Thus, the local function of each TCP is to choose a transmission function, so as to achieve the global condition mentioned here. Since the TCP's transmit in a bursty manner, it is possible that even if the above condition met in the average, there could be instantaneous cases where there is buffer overflow. A more realistic global optimum would be try to reduce the probability of this happening to less than a certain threshold i.e. . There are various methods to achieve this equilibrium, which we shall not go into further. See [Duffield98]. We say an equilibrium is reached when each TCP chooses its transmission function so that the probability of the event described above reaches some stable value. Associate with that, each TCP also gets a certain drop rate for its traffic. The tuple of (transmission rate, drop rate) for each TCP is its allocation and a resultant QoS is derived from this tuple.

Unfortunately, achieving a global equilibrium does not automatically achieve a good local optimum for a TCP. It is quite possible that one TCP gets a very large bandwidth and others get very small bandwidths, and even then the two conditions above are maintained. Even more importantly, the TCPs which have small bandwidth would immediately try to increase their transmission rate and thus disturbe the equilibrium. Even more importantly, there is no finite local optimum as far as TCP is concerned. TCP is a bandwidth hunting algorithm and will keep hunting for bandwidth indefinitely; the marginal utility of bandwidth is always positive. This can easily lead to an equilibrium which is extremely unfair; one TCP takes up the entire buffer available, whereas all other TCPs are reduced to very low transmission rates. This problem is unique to TCP among the scenarios we have discussed here and occurs when we have "greedy" endpoints in a distributed control environment.

Fortunately, distributed control also works, and works extremely well, in the case where the endpoints are greedy. It also works when the endpoints are strategic i.e. they do not advertise their true desires to the network. [Scott Shenker] provides a very interesting analysis of these cases and points out the following requirements.

When an equilibrium is achieved, there should be an incentive to all TCP connections to remain at that equilibrium. In other words, if a single TCP connection chooses to change its behaviour, the resulting global change should immediately cause the changing TCP to be worse off than it was before.
When we have multiple TCP connections with different round trip times, the TCP with the largest round-trip time can manipulate the equilibrium to its favour simply due to "follow the leader" paradox. By not responding to feedback, it forces other TCPs to converge around the equilibrium it chooses.
The equilibrium should be envy-free. If we take any pair of TCPs and exchange their allocations, the TCPs should be worse off in the new equilibrium than before.

Scott shenker himself points out that, in fact, GPS schedulers actually often fail multiple of these criteria and suggest an alternative, called the fair sharing algorithm. Interested readers are invited to see [Shenker93] for a technical discussion of the same.

References

[Molle94] M.Molle, "A New Binary Logarithmic Arbitration Method for Ethernet", Technical Report-CSRI, University of Toronto, April 94

[Kleinrock93] Kleinrock, Tung, "Distributed Control Methods", Proceedings of the 2nd International Symposium on high performance distributed systems, 1993

[Shenker94] Scott Shenker. Making greed work in networks: a game theoretic analysis of switch service disciplines. In ACM SIGCOMM94

[Shenker93] Scott Shenker. "Some Technical Results on Continuity, Strategy-proofness, and Related Strategic Concepts", 1993

[Foschini93] Foschini, Miljanic, "A simple distributed autonomous power control algorithm and its convergence," IEEE Transactions on Vehicular Technology, November 1993

[Zander98] Andersin, Rosberg, Zander, "Distributed Discrete Power Control in Cellular PCS", Wireless Personal Communications, 1998

[Duffield98] Duffield, Lakshman, Stilliadis, "On Adaptive Bandwidth Sharing with Rate Guarantees", Proc. IEEE Infocom 1998

readers have visited this page