The delay performance of adaptive routing and scheduling in communication networks

Ji, Tianxiong

Permalink

https://hdl.handle.net/2142/30890 Copy

Description

Title

The delay performance of adaptive routing and scheduling in communication networks

Author(s)

Ji, Tianxiong

Issue Date

2012-05-22T00:13:31Z

Director of Research (if dissertation) or Advisor (if thesis)

Srikant, Rayadurgam

Doctoral Committee Chair(s)

Srikant, Rayadurgam

Committee Member(s)

• Basar, Tamer
• Coleman, Todd P.
• Sreenivas, Ramavarapu S.
• Vaidya, Nitin H.

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Routing
• Scheduling
• Communication Networks
• Delay performance
• Connection-level
• Adaptive
• Throughput optimal

Abstract

Throughput and latency are two important QoS metrics in communication networks. Ideally, we would like to deliver a large amount of data from a source to its destination within a short time period. During the past decades, researchers have designed a number of network-layer routing algorithms and MAC-layer scheduling algorithms to deliver good QoS performance under various network conditions. In this dissertation, we study the delay performance of routing and scheduling algorithms in communication networks. A collection of algorithms called MaxWeight Scheduling (MWS) algorithms is known to be throughput optimal. A particular algorithm in this class was conjectured to be delay-optimal as well. We disprove this conjectured by constructing a delay-optimal algorithm for a specific network and show that it outperforms the particular MWS algorithm. Next, we propose a packet-by-packet adaptive routing and scheduling algorithm for multi-hop traffic which dramatically reduces delays in the network, while maintaining near throughput optimality. This algorithm uses a particular routing table, called a probabilistic routing table, to adaptively find a route for every packet. The probabilistic routing table is generated by running an emulated network, called the shadow network, which is essentially a model of the real network with a slightly higher traffic load. The scheduling decisions are also determined by the shadow system. Our joint routing and scheduling algorithm reduces the capacity region slightly, but provides low delay performance everywhere in this reduced region. In addition, the queueing and routing architecture is more consistent with the architecture of current routers and switches. We also extend our results to the case where network coding is used to improved the throughput in the network. Our algorithm provides a low-complexity solution to optimally exploit the routing-coding tradeoff. Lastly, we consider wireless ad hoc networks in which each connection (file) traverses only one hop. We assume files arrive for service at each link and a file departs when all its packets have been transmitted. We consider two cases: one in which the file size distribution is arbitrary but has bounded support; another in which the file size distribution is a mixture of geometric distributions. The only assumption we make about the window flow control protocol is that the window size is always greater than zero. We show the following result: for an appropriately chosen MAC-layer scheduling algorithm, the network is stable for all file arrival rates within the capacity region. In other words, the MAC-layer scheduling algorithm, by only knowing the MAC-layer information, can achieve throughput optimality independently of the window flow control protocol used.

Graduation Semester

2012-05

Permalink

http://hdl.handle.net/2142/30890

Copyright and License Information

Copyright 2012 Tianxiong Ji

Owning Collections