More Web Proxy on the site http://driver.im/

research-article

Throughput and QoS optimization in nonuniform multichannel wireless mesh networks

Author:

T. H. SzymanskiAuthors Info & Claims

Q2SWinet '08: Proceedings of the 4th ACM symposium on QoS and security for wireless and mobile networks

Pages 9 - 19

https://doi.org/10.1145/1454586.1454589

Published: 27 October 2008 Publication History

Abstract

A technology to increase throughput and QoS in infrastructure-based Wireless Mesh Networks (WMNs) is proposed. In a uniform WMN, let each Base Station (BS) have R1 transceivers for communications with neighboring BSs, and R2 transceivers for communications with the Stationary and Mobile Subscribers within the wireless cell. One Gateway BS provides access to the global Internet, and the throughput capacity of the entire WMN is constrained by the IO bandwidth of the Gateway. A small number of extra wireless links can be added to the Gateway BS and selected other BSs, resulting in a nonuniform system. The addition of an asymptotically small number of transceivers can increase WMN capacity several fold. Efficient scheduling requires the partitioning of an asymmetric bipartite graph representing a general traffic rate matrix, into multiple graphs representing doubly-stochastic matrices. Routing and scheduling algorithms presented. The algorithms can provision long-term multimedia flows including VOIP or IPTV with guaranteed service. For multichannel WMNs where the traffic is routed and partitioned, the number of queued cells per BS is near-minimal and bounded, the end-to-end delay and jitter are near-minimal and bounded, and cell loss rates due to scheduling conflicts are zero. The algorithm also achieves 100% of capacity.

References

[1]

Akyildiz, I.F, Wang, X. 2005. A Survey on Wireless Mesh Networks, IEEE Radio Communications, (Sept. 2005), S23-S30.

[2]

Cao, M., Wang, X., Kim, S.K., Madihian, M. 2007. Multi-Hop Wireless Backhaul Networks: A Cross-Layer Design Paradigm, IEEE JSAC, 25, 4, (May 2007), 738--748.

Digital Library

[3]

Xergias, S., Passas, N., Salkintzis, A.K. 2008. Centralized Resource Allocation for Multimedia Traffic in IEEE 802.16 Mesh Networks, Proc. IEEE, 96, 1, (Jan. 2008), 54-63.

[4]

Sharma, G., Mazumda, R.R., Shroff, N.B. 2006. On the Complexity of Scheduling in Wireless Networks, IEEE Mobicom'06, (Sept. 2006).

Digital Library

[5]

Tassiulas L. and Ephremides A. 1992. Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks, IEEE Trans. Automatic Control, 37, 12, (Dec. 1992), 1936--1948.

[6]

Tassiulas L. 1998. Linear Complexity algorithms for maximum throughput in radio networks and input queued switches, IEEE Infocom, (April 1998), 533--539.

[7]

Tassiulas, L., Ephremides, A. 1992. Joint optimal routing and scheduling in packet radio networks, IEEE Trans Inform. Theory, 38, 1, (Jan. 1992), 165--169.

Digital Library

[8]

Jain, K., Padhye, J.,Padmanabhan, V., Qiu, L. 2003. Impact on Interference on multi-hop wireless networks performance, ACM Mobicom'03 (2003).

Digital Library

[9]

Jain, K., Padhye, J.,Padmanabhan, V., Qiu, L. 2005. Impact of Interference on Multi-Hop Wireless Network Performance, Wireless Networks, 11, (2005), 471--487.

Digital Library

[10]

Chou C.T., Qadir, J., Lim, J.G. (2007). Advances and Challenges with Data Broadcasting in Wireless Mesh Networks, IEEE Comm. Magazine, (Nov. 2007), 78--122.

Digital Library

[11]

Sharma, G., Shroff, N.B., Mazumdar, R.R. 2006. Maximum Weighted Matching with Interference Constraints, IEEE Int. Conf. Pervasive Computing and Comm. Workshop, (2006).

Digital Library

[12]

Madan, R., Cui, S., Lall, S., Goldsmith, A.J. 2005. Cross-layer design for lifetime maximization in interference-limited wireless sensor networks, IEEE Infocom, 2005.

[13]

Kodlialam, M., Nandagopal, T. 2003. Characterizing Achievable rates in multi-hop wireless mesh networks: the joint routing and scheduling problem, ACM Mobicom'03, San Diego, California, (2003).

Digital Library

[14]

Cruz, R.L., Santhaman, A.V. 2005. Optimal routing, link scheduling and power control in multi-hop wireless networks, Proc. IEEE Infocom, 1, (Mar. 2005), 702--711.

[15]

Xiao, L., Johansoon, M., Boyd, S.P. 2004. Simultaneous routing and resource allocation via dual decomposition, IEEE Trans. Comm., 52, 7, (Jan. 2004), 1136--1144.

[16]

Elliot, T., Ephremides, A. 2004. Joint scheduling and power control for wireless ad hoc networks, IEEE Trans, Wireless Comm., 1, (2004), 74--85.

Digital Library

[17]

Sharma, G., Shroff, N.B., Mazumdar, R.R. 2007. Joint Congestion Control and Distributed Scheduling for Throughput Guarantees in Wireless Networks, IEEE Infocom, (2007), 2072--2080.

Digital Library

[18]

Szymanski, T.H. 2008. A Conflict-Free Low-Jitter Guaranteed-rate MAC Protocol for Base-Station Communications in Wireless Mesh Networks, To Appear, Int. Conf. Access Networks, Las Vegas, (Oct 2008).

[19]

Parekh, A.K., Gallager, R.G. 1993. A Generalized Processor Sharing Approach to Flow Control in Integrated Service Networks: the Single Node Case, IEEE/ACM Trans. Networking, 1, (1993), 344--357.

Digital Library

[20]

Parekh, A.K., Gallager, R.G. 1994. A Generalized Processor Sharing Approach to Flow Control in Integrated Service Networks: the Multiple Node Case, IEEE/ACM Trans. Networking, 2, 2, (1994), 137--150.

Digital Library

[21]

Jajszczyk, A. 2003. Nonblocking, Repackable and Rearrangeable Clos Networks: Fifty Years of the Theory Evolution, IEEE Comm. Magazine, (2003), 28--33.

Digital Library

[22]

McKeown, N., Mekkittikul, A., Anantharam, V., Walrand, J. 1999. Achieving 100% Throughput in an Input Queued Switch, Trans. Comm.,47, 8, (1999), 1260--1267.

[23]

Lotfinezhad, M., Liang, B., Sousa, E.S. 2008. Dynamic Control of Tunable Sub-optimal Algorithms for Scheduling of Time-varying Wireless Networks, IEEE iWQoS Conf., Enschede, Netherlands, (June 2008), 153--163.

[24]

Gourgy, A., Szymanski, T.H., Down, D. On Tracking the Behaviour of an Output Queued Switch using an Input Queued Switch, Submitted, IEEE Trans. Networking.

Digital Library

[25]

Koksal, C.E., Gallager, R.G., Rohrs, C.E. 2004. Rate Quantization and Service Quality over Single Crossbar Switches, IEEE Infocom, (2004).

[26]

Gopya, P., Vin, H.M. 1997. Generalized Guaranteed Rate Scheduling Algorithms: A Framework, IEE/ACM Trans. Networking, 5, 4, (1997), 561--571.

Digital Library

[27]

Keslassy, I., Kodialam, M., Lakshamn, T.V., Stiliadis, D. 2005. On Guaranteed Smooth Scheduling for Input-Queued Switches, IEEE/ACM Trans. Networking, 13, 6, (2005).

Digital Library

[28]

Kodialam, M.S., Lakshman, T.V., Stilladis, D.: Scheduling of Guaranteed-bandwidth low-jitter traffic in input-buffered switches, US Patent Application #20030227901.

[29]

Chen, W.J., Chang, C-S., Huang, H-Y. 2001.Birkhoff-von Neumann Input Buffered Crossbar Switches, IEEE Trans. Comm., 49, 7, (2001), 1145--1147.

[30]

Chang, C-S., Chen, W.J., Huang, H-Y. 1999. On Service Guarantees for Input Buffered Crossbar Switches: A Capacity Decomposition Approach by Birkhoff and von Neuman, IEEE iWQoS, (1999), 79--86.

[31]

Mohanty, S.R., Bhuyan, L.N. 2005. Guaranteed Smooth Switch Scheduling with Low Complexity, IEEE Globecom, (2005), 626--630.

[32]

Sun, W., Shin, K.G. 2005. End-to-End Delay Bounds for Traffic Aggregates Under Guaranteed-Rate Scheduling Algorithms, IEEE/ACM Trans. Networking, 11, 3, (2005), 1188--1201.

Digital Library

[33]

Giaccone, P., Leonardi, E., Shat, D. 2007. Throughput Region of Finite-Buffered Networks, IEEE Trans. PDS, 11, 12, (2007), 251--263.

Digital Library

[34]

Szymanski, T.H. 2006. QoS Switch Scheduling using Recursive Fair Stochastic Matrix Decomposition, IEEE Int. Conf. HPSR, (2006), 417--424.

[35]

Szymanski, T.H. A Low-Jitter Guaranteed-Rate Scheduling Algorithm for Packet-Switched IP Routers, Accepted (with revision), IEEE Trans. on Comm, (2008).

Digital Library

[36]

Szymanski, T.H. Method and Apparatus to Schedule Packets through a Crossbar Switch with Delay Guarantees, US Patent Application, (2007).

[37]

Szymanski, T.H. Method and Apparatus to Schedule Packets through a Wireless Mesh Network with Near Minimal Delay and Jitter, US Provisional Patent App., (2008).

[38]

Szymanski, T.H., Gilbert, D. 2007. Delivery of Guaranteed Rate Internet Traffic with Very Low Delay Jitter, IEEE Pacific Rim Conf. on Comm., Comp. and Signal Processing, (2007), 450--455.

[39]

Szymanski, T.H., Gilbert, D. Low-Jitter Guaranteed-Rate Communications for Cluster Computing Systems, To Appear, Pacific Rim Special Issue, Int. Journal of Computer Networks and Distributed Systems, (2008).

Digital Library

[40]

Szymanski, T.H. Bounds on End-to-End Delay and Jitter in Input-Queued IP/MPLS Networks, Submitted, (2008).

Cited By

Szymanski T(2010)Provisioning backhaul traffic flows in TDMA/OFDMA infrastructure wireless mesh networks with near-perfect QoSProceedings of the 33rd IEEE conference on Sarnoff10.5555/1843486.1843506(100-106)Online publication date: 12-Apr-2010
https://dl.acm.org/doi/10.5555/1843486.1843506
Zhang JAnsari NJin YHu W(2010)Dichotomy Slot Allocation: A QoS Guaranteed Scheduling Algorithm for Input-Queued SwitchesIEEE Systems Journal10.1109/JSYST.2010.20402264:1(74-83)Online publication date: Mar-2010
https://doi.org/10.1109/JSYST.2010.2040226
Szymanski T(2009)Bounds on end-to-end delay and jitter in input-buffered and internally-buffered IP networksProceedings of the 32nd international conference on Sarnoff symposium10.5555/1719650.1719693(229-235)Online publication date: 30-Mar-2009
https://dl.acm.org/doi/10.5555/1719650.1719693
Show More Cited By

Index Terms

Throughput and QoS optimization in nonuniform multichannel wireless mesh networks
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
2. Networks
  1. Network architectures
  2. Network types

Recommendations

Throughput-range tradeoff of wireless mesh backhaul networks

Wireless backhaul communication is expected to play a significant role in providing the necessary backhaul resources for future high-rate wireless networks. Mesh networking, in which information is routed from source to destination over multiple ...
An adaptive contention-based scheduling scheme for proportional service differentiation in multichannel wireless networks
QShine '06: Proceedings of the 3rd international conference on Quality of service in heterogeneous wired/wireless networks

In this paper, we propose an adaptive contention-based MAC scheduling scheme called Multi-channel Contention-based TDMA (MC/TDMA) for Multichannel wireless networks which provides proportional service differentiation while achieving high resource ...
Distributed multichannel MAC protocol for IEEE 802.11 ad hoc wireless LANs

The IEEE 802.11 standard supports several independent and equal-capacity communication channels, which can be shared simultaneously and accessed by mobile stations in existing wireless local area networks (WLANs). However, under the restriction of one ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Q2SWinet '08: Proceedings of the 4th ACM symposium on QoS and security for wireless and mobile networks

October 2008

124 pages

ISBN:9781605582375

DOI:10.1145/1454586

General Chair:
Albert Zomaya
University of Sydney, Australia
,
Program Chair:
Matteo Cesana
Politecnico di Milano, Italy

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 October 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MSWiM '08

Sponsor:

MSWiM '08: The 11th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems

October 27 - 28, 2008

British Columbia, Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 46 of 131 submissions, 35%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
415
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Szymanski T(2010)Provisioning backhaul traffic flows in TDMA/OFDMA infrastructure wireless mesh networks with near-perfect QoSProceedings of the 33rd IEEE conference on Sarnoff10.5555/1843486.1843506(100-106)Online publication date: 12-Apr-2010
https://dl.acm.org/doi/10.5555/1843486.1843506
Zhang JAnsari NJin YHu W(2010)Dichotomy Slot Allocation: A QoS Guaranteed Scheduling Algorithm for Input-Queued SwitchesIEEE Systems Journal10.1109/JSYST.2010.20402264:1(74-83)Online publication date: Mar-2010
https://doi.org/10.1109/JSYST.2010.2040226
Szymanski T(2009)Bounds on end-to-end delay and jitter in input-buffered and internally-buffered IP networksProceedings of the 32nd international conference on Sarnoff symposium10.5555/1719650.1719693(229-235)Online publication date: 30-Mar-2009
https://dl.acm.org/doi/10.5555/1719650.1719693
Szymanski T(2009)A low-jitter guaranteed-rate scheduling algorithm for packet-switched IP routersIEEE Transactions on Communications10.1109/TCOMM.2009.11.07066657:11(3446-3459)Online publication date: 1-Nov-2009
https://dl.acm.org/doi/10.1109/TCOMM.2009.11.070666
Fazio MPaone MBruneo DPuliafito A(2009)Dependable QoS support in Mesh NetworksProceedings of the 2009 IEEE International Symposium on Parallel&Distributed Processing10.1109/IPDPS.2009.5160905(1-7)Online publication date: 23-May-2009
https://dl.acm.org/doi/10.1109/IPDPS.2009.5160905

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten