Towards practical policies for network control

In the past three decades, several network control policies geared towards achieving throughput optimality have been developed. However, rarely any of these policies have been used in practice. We study three different issues that impede this transition and propose solutions that can facilitate the move. Throughput optimal routing policies are known to have poor delay performance because of packets traversing loops in the network. In the first part of the thesis, we develop a new distributed policy that forwards packets along directed acyclic graphs (DAGs) to avoid the looping problem. This policy uses a link reversal algorithm to improve the DAGs in order to support any achievable traffic demand. In the second part, we address the problem of optimal routing in overlay networks. Since most devices attached to the existing network do not support throughput optimal routing, a gradual move by forming an overlay network has been proposed in the literature. We develop a new algorithm that the overlay devices can use to achieve the maximum throughput. This algorithm requires the knowledge of the queue lengths of the legacy network, which might not be available. Hence, we also propose a method based on linear regression to estimate these quantities. To build a high throughput and robust overlay network, it is important to know the topology of the underlying network. However, the network owners usually keep the topology information private. Hence, in the third part of the thesis, we consider the problem of inferring the topology of a network using the measurements available at the end nodes. We use the interference information about the paths to formulate the topology inference problem as an integer program. We develop polynomial time algorithms to solve it optimally for networks with tree and ring topologies. Finally, we use the insights from these algorithms to develop a heuristic for identifying general topologies.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2018

Author dc:creator

• Rai, Anurag,1985-

Advisor dc:contributor.advisor

• Eytan H. Modiano.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/120417

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/120417