Optimal delay scheduling in networks with arbitrary constraints

ABSTRACT

We consider the problem of designing an online scheduling scheme for a multi-hop wireless packet network with arbitrary topology and operating under arbitrary scheduling constraints. The objective is to design a scheme that achieves high throughput and low delay simultaneously. We propose a scheduling scheme that - for networks operating under primary interference constraints - guarantees a per-flow end-to-end packet delay bound of ^5dj/(1-ρ_j), at a factor 5 loss of throughput, where d_j is the path length (number of hops) of flow j and ρ_j is the effective loading along the route of flow j. Clearly, d_j is a universal lower bound on end-to-end packet delay for flow j. Thus, our result is essentially optimal. To the best of our knowledge, our result is the first one to show that it is possible to achieve a per-flow end-to-end delay bound of O(# of hops) in a constrained network.

Designing such a scheme comprises two related subproblems: Global Scheduling and Local Scheduling. Global Scheduling involves determining the set of links that will be simultaneously active, without violating the scheduling constraints. While local scheduling involves determining the packets that will be transferred across active edges. We design a local scheduling scheme by adapting the Preemptive Last-In-First-Out (PL) scheme, applied for quasi-reversible continuous time networks, to an unconstrained discrete-time network. A global scheduling scheme will be obtained by using stable marriage algorithms to emulate the unconstrained network with the constrained wireless network.

Our scheme can be easily extended to a network operating under general scheduling constraints, such as secondary interference constraints, with the same delay bound and a loss of throughput that depends on scheduling constraints through an intriguing "sub-graph covering" property.

REFERENCES

• 1: Matthew Andrews , Antonio Fernández , Mor Harchol-Balter , Tom Leighton , Lisa Zhang, General Dynamic Routing with Per-Packet Delay Guarantees of O(Distance + 1/Session Rate), SIAM Journal on Computing, v.30 n.5, p.1594-1623, 2000 [doi>10.1137/S009753979935061X]
• 2: S. Chuang, A. Goel, N. McKeown, and B. Prabhakar. Matching output queueing with a combined input/output-queued switch. Selected Areas in Communications, IEEE Journal on, 17(6):1030--1039, 1999.
• 3: F. P. Kelly. Reversibility and Stochastic Networks. John Wiley and Sons Ltd., New York, 1979.
• 4: D. Gale and L. Shapley. College Admissions and the Stability of Marriage. The American Mathematical Monthly, 69(1):9--15, 1962.
• 5: A. E. Gamal, J. Mammen, B. Prabhakar, and D. Shah. Optimal Throughput-Delay Scaling in Wireless Networks - Part II: Constant-Size Packets. IEEE Transactions on Informaition theory, 52(11):5111--5116, 2006.
• 6: Leonidas Georgiadis , Michael J. Neely , Leandros Tassiulas, Resource allocation and cross-layer control in wireless networks, Foundations and Trends® in Networking, v.1 n.1, p.1-144, April 2006 [doi>10.1561/1300000001]
• 7: P. Gupta and P. Javidi. Towards delay-optimal routing in ad-hoc networks. In Proc. Asilomar Conference on Signals Systems and Computers, Pacific Grove CA USA, Nov.4--7 2007.
• 8: F. Leighton, B. Maggs, and S. Rao. Packet routing and job-shop scheduling in O(congestion + dilation) steps. Combinatorica, 14(2):167--186, 1994.
• 9: B. Prabhakar and N. McKeown. On the speedup required for combined input and output-queued switching. Automatica, 35(12):1909--1920, 1999.
• 10: R. W. Wolff. Stochastic Modeling and the Theory of Queues. Prentice-Hall, 1988.
• 11: L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control, 37(12):1936--1949, 1992.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
delay, scheduling algorithm, throughput