Article

Dynamic Global Packet Routing in Wireless Networks

Authors:

Paul E. WrightAuthors Info & Claims

INFOCOM '97: Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution

Page 1414

Published: 09 April 1997 Publication History

Abstract

We consider schemes for reuse-efficient packet access in wireless data networks. We show that computing the maximum ergodic packet arrival rate is NP-hard. We give an upper bound on the maximum ergodic throughput in terms of the eigenvalues of matrices related to the path-gain matrix. We present simple, practical heuristic algorithms which exhibit good throughput and packet delay and report on results of preliminary simulations. More sophisticated algorithms that yield optimal throughput are also presented. A recent result of McKeown, Anantharam and Walrand on scheduling of input-queued switches is obtained as a byproduct.

References

[1]

D. Bertsekas and R. Gallager. Data Networks. Prentice-Hall, 1987.

Digital Library

[2]

N. Biggs. Algebraic Graph Theory. Cambridge University Press, 1974.

[3]

Y. Okumura et. al. Field Strength and its Variablity in VHF and UHF Radio Service. Rev. Elec. Comm. Lab., NTT., 16:9-10, 1968.

[4]

U. Feige. Randomized graph products, chromatic numbers, and the lovász ¿function. In 27th Annual ACM Symposium on Theory of Computing, pages 635-640. ACM Press, 1995.

Digital Library

[5]

M. Hata. Empirical Formula for Propagation Loss in Land Mobile Radio Service. IEEE Trans. on Vehicular Tech., VT-29(3):317-325, 1980.

[6]

A. Kamath, O. Palmon, and S. Plotkin. Routing and admission control in general topology networks with Poisson arrivals. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 269-278. SIAM Press, January 1996.

Digital Library

[7]

F. P. Kelley. Blocking probabilities in large circuit-switched networks. Adv. Appl. Prob., 18:473-505, 1986.

[8]

L. Kleinrock. Queueing systems, volume I. Wiley, New York, 1975.

Digital Library

[9]

D. E. Knuth. The sandwich theorem. The Electronic Journal of Combinatorics, 1(A1):48pp., 1994.

[10]

J-P. Linnartz. Narrowband Land-Mobile Radio Networks. Artech House, 1993.

Digital Library

[11]

J-P. Linnartz. Wireless Data Networking. Artech House, 1995.

[12]

L. Lovász. On the Shannon capacity of a graph. IEEE Transactions on Information Theory IT- 25, pages 1-7, 1979.

Digital Library

[13]

C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. J. ACM, 41:960-981, 1994.

Digital Library

[14]

N. McKeown, V. Anantharam, and J. Walrand. Achieving 100% throughput in an input-queued switch. In Proceedings INFOCOM'96, pages 296- 302. IEEE, 1996.

Digital Library

[15]

D. Mitra. Asymptotic Analysis and Computational Methods for a Class of Simple Circuit-Switched networks with Blocking. Adv. Appl. Prob., 19:219-239, 1987.

[16]

D. Mitra. An asynchronous distributed algorithm for power control in cellular radio systems. In Fourth WINLAB Workshop on Third Generation Wireless Information Networks, Rutgers University, 1993.

[17]

E. Seneta. Non-negative matrices and Markov Chains. Springer-Verlag, 1981.

[18]

A. S. Tannenbaum. Computer Networks. Prentice-Hall, 1988.

Digital Library

[19]

J. Whitehead. Global Packet Resource Allocation (GPDRA) for Wireless Networks. Technical report, AT&T, 1996.

[20]

J. Zander. Performance of optimum transmitter power control in cellular radio systems. IEEE transactions on vehicular technology, 41:57-62, 1992.

Cited By

Seferoglu HModiano E(2016)Separation of routing and scheduling in backpressureIEEE/ACM Transactions on Networking10.1109/TNET.2015.243621724:3(1787-1800)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1109/TNET.2015.2436217
Rengarajan BDe Veciana G(2011)Architecture and abstractions for environment and traffic-aware system-level coordination of wireless networksIEEE/ACM Transactions on Networking10.1109/TNET.2010.209804319:3(721-734)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1109/TNET.2010.2098043
Neely M(2010)Delay-based network utility maximizationProceedings of the 29th conference on Information communications10.5555/1833515.1833859(2669-2677)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.5555/1833515.1833859
Show More Cited By

Dynamic Global Packet Routing in Wireless Networks
1. Networks
  1. Network types

Recommendations

The Packet Loss Effect on MPEG Video Transmission in Wireless Networks
AINA '06: Proceedings of the 20th International Conference on Advanced Information Networking and Applications - Volume 01

The purpose of this paper is to study the packet loss effect on MPEG video transmission quality in wireless networks. First, we consider the distribution of packet losses in wireless network, including distributed and burst packet losses. Besides, we ...
Keeping the packet sequence in optical packet-switched networks

This paper deals with optical packet switches with limited buffer capabilities, subject to asynchronous, variable-length packets and connection-oriented operation. The focus is put on buffer scheduling policies and queuing performance evaluation. In ...
Packet-Level FEC Research Over Wireless Networks

Over wireless networks, interference caused by external sources, multipath fading due to terrestrial obstruction, and the mobility of transmitters or receivers will result in bursty errors of transmitted packets. To deal with the problem, a packet-level ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

INFOCOM '97: Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution

April 1997

ISBN:0818677805

Copyright © Copyright (c) 1997 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 09 April 1997

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Seferoglu HModiano E(2016)Separation of routing and scheduling in backpressureIEEE/ACM Transactions on Networking10.1109/TNET.2015.243621724:3(1787-1800)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1109/TNET.2015.2436217
Rengarajan BDe Veciana G(2011)Architecture and abstractions for environment and traffic-aware system-level coordination of wireless networksIEEE/ACM Transactions on Networking10.1109/TNET.2010.209804319:3(721-734)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1109/TNET.2010.2098043
Neely M(2010)Delay-based network utility maximizationProceedings of the 29th conference on Information communications10.5555/1833515.1833859(2669-2677)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.5555/1833515.1833859
Neely M(2008)Order optimal delay for opportunistic scheduling in multi-user wireless uplinks and downlinksIEEE/ACM Transactions on Networking10.1109/TNET.2007.90968216:5(1188-1199)Online publication date: 1-Oct-2008
https://dl.acm.org/doi/10.1109/TNET.2007.909682
Andrews MZhang L(2004)Scheduling Protocols for Switches with Large EnvelopesJournal of Scheduling10.1023/B:JOSH.0000019679.68869.e87:3(171-186)Online publication date: 1-May-2004
https://dl.acm.org/doi/10.1023/B%3AJOSH.0000019679.68869.e8
Armony MBambos N(2003)Queueing Dynamics and Maximal Throughput Scheduling in Switched Processing SystemsQueueing Systems: Theory and Applications10.1023/A:102471402424844:3(209-252)Online publication date: 1-Jul-2003
https://dl.acm.org/doi/10.1023/A%3A1024714024248
Andrews MZhang LEppstein D(2002)Scheduling protocols for switches with large envelopesProceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/545381.545440(443-452)Online publication date: 6-Jan-2002
https://dl.acm.org/doi/10.5555/545381.545440

View Options

View options

Media

Figures

Other

Tables

View Table of Contents