Network Control: From Theory to Practice

The performance and control of communication networks can be analyzed using a beautiful theory based on queue stability. This theory gave us the backpressure algorithm firstly proposed by Tassiulas & Ephremides in 1992 [1], whereby packets flow in the data network according to queue backlog differences (a packet always flows from a highly-backlogged node to a neighboring node with smaller backlog). In the context of the ONR project, Prof. Modiano and his group work towards bridging the gap between this control theory and how real networks work.

An important constraint of wireless devices is computational power, which makes the implementation of the scheduling component of Backpressure practically prohibitive. A first achievement of this work was to separate scheduling and routing operations of Backpressure so that efficient routing can be combined with any arbitrary scheduling [2]. Examples of constrained scheduling schemes are distributed protocols like 802.11 (WiFi). Therefore this approach allows to use Backpressure on networks built using WiFi devices.

In the domain of congestion control, the group studied and proposed solutions to the problem of combining TCP with Backpressure, observed before to be a mis-match [3]. Since TCP is used in more than 50% of data communications today, applying the network control theory required addressing this problem. After doing so [4], the group went beyond TCP and proposed innovative congestion control methods where instead of deciding rates at the source (like TCP does), a different methodology was used: all packets are freely injected in the network and then the network decides in a distributed fashion which packets to drop at congested nodes [5,6]. This relieves the sources from the burden of allocating rates, and enables communication schemes where parts of a network may not be trustworthy, while at the same time preventing the network from malicious attacks (DoS).

Currently the group is focusing in several directions of great interest. One challenge is that Backpressure assumes that every node applies control in a homogeneous fashion, practical networks are made of diverse technologies and are inherently inhomogeneous. Motivated by this, the group studies the problem of controlling a network using only a fraction of nodes. Our experiments show that not only full throughput can be achieved if the choice of the control nodes is appropriate, but moreover delay performance is improved [7]. Another direction is the study of optimal broadcasting in wireless networks. We are developing an optimal control methodology of polynomial complexity. Previous approaches required the enumeration of all embedded trees in the network graph, which has prohibitive complexity.