Joint Asynchronous Congestion Control and Distributed Scheduling for Multi-Hop Wireless Networks
Published 1 January 2006
Loc Bui, Atilla Eryılmaz, R. Srikant, Xianren Wu
Citations97
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An architecture for fair resource allocation that consists of a distributed scheduling algorithm operating in conjunction with an asynchronous congestion control algorithm that supports at least one-third of the throughput supportable by any other algorithm, including centralized algorithms is proposed.
Abstract
We consider a multi-hop wireless network shared by many users. For an interference model that only constrains a node to either transmit or receive at a time, but not both, we propose an architecture for fair resource allocation that consists of a distributed scheduling algorithm operating in conjunction with an asynchronous congestion control algorithm. We show that the proposed joint congestion control and scheduling algorithm supports at least one-third of the throughput supportable by any other algorithm, including centralized algorithms.
Keywords
Computer ScienceEngineering
Journal of the Operational Research SocietyRate control for communication networks: shadow prices, proportional fairness and stability
5,023 Citations1998F. P. Kelly, A.K. Maulloo +1 more
This paper analyses the stability and fairness of two classes of rate control algorithm for communication networks, which provide natural generalisations to large-scale networks of simple additive increase/multiplicative decrease schemes, and are shown to be stable about a system optimum characterised by a proportional fairness criterion.
IEEE Transactions on Automatic ControlStability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
2,880 Citations1992Leandros Tassiulas, Anthony Ephremides
IEEE/ACM Transactions on NetworkingFair end-to-end window-based congestion control
2,103 Citations2000Jeonghoon Mo, Jean Walrand
IEEE/ACM Transactions on NetworkingOptimization flow control. I. Basic algorithm and convergence
1,975 Citations1999Steven H. Low, D.E. Lapsely
An optimization approach to flow control where the objective is to maximize the aggregate source utility over their transmission rates to solve the dual problem using a gradient projection algorithm.
IEEE Transactions on Automatic ControlThe Mathematics of Internet Congestion Control
834 Citations2005
This book is about the application of some well-known results in control theory to the study of Internet congestion control and results that are familiar to control researchers including convex optimization, Lyapunov stability theory, and the Nyquist criterion are the main tools used.
CMS books in mathematicsConvex Analysis and Nonlinear Optimization
795 Citations2006Jonathan M. Borwein, Adrian S. Lewis
Systems & controlThe Mathematics of Internet Congestion Control
789 Citations2004R. Srikant
A Decentralized Solution Relationship to Current Internet Protocols and Global Stability for a Single Link and Single Flow Stochastic Models and Their Deterministic Limits Connection-level Models Real-Time Sources and Distributed Admission Control.
IEEE Transactions on Information TheoryLink scheduling in polynomial time
565 Citations1988Bruce Hajek, Galen H. Sasaki
Two polynomial-time algorithms are given for scheduling conversations in a spread spectrum radio network that jointly meet a prespecified end-to-end demand and has the smallest possible length.
Queueing SystemsMaximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual Algorithm
530 Citations2005Alexander Stolyar
A dynamic control algorithm, which is introduced, which the authors call Greedy Primal-Dual (GPD) algorithm, and prove its asymptotic optimality, and shows that it can accommodate a wide range of applications.
The impact of imperfect scheduling on cross-layer rate control in wireless networks
420 Citations2005Xiaojun Lin, Ness B. Shroff
This paper studies how the performance of cross-layer rate control can be impacted if the network can only use an imperfect scheduling component that is easier to implement, and designs a fully distributed cross-layered rate control and scheduling algorithm for a restrictive interference model.
2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No.04CH37601)Joint rate control and scheduling in multihop wireless networks
396 Citations2004Xiaojun Lin, Ness B. Shroff
This work proposes a dual optimization based approach through which the rate control problem and the scheduling problem can be decomposed and demonstrates via both analytical and numerical results that the proposed mechanism can fully utilize the capacity of the network, maintain fairness, and improve the quality of service to the users.
Convex Analysis and Nonlinear Optimization
386 Citations2000Jonathan M. Borwein, Adrian S. Lewis
IEEE/ACM Transactions on NetworkingStable scheduling policies for fading wireless channels
366 Citations2005Atilla Eryılmaz, R. Srikant +1 more
It is proved that, for any mean arrival rate that lies in the capacity region, the queues will be stable under the policy and it is shown that it is easy to incorporate imperfect queue length information and other approximations that can simplify the implementation of the policy.
Fairness and optimal stochastic control for heterogeneous networks
343 Citations2005Michael J. Neely, Eytan Modiano +1 more
Fair resource allocation in wireless networks using queue-length-based scheduling and congestion control
329 Citations2005Atilla Eryılmaz, R. Srikant
Characterizing achievable rates in multi-hop wireless networks
322 Citations2003Murali Kodialam, Thyaga Nandagopal
The approach that is used is quite flexible and is a promising method to handle more sophisticated interference conditions, multiple channels, multiple antennas, and routing with diversity requirements.
IEEE/ACM Transactions on NetworkingHop-by-Hop Congestion Control Over a Wireless Multi-Hop Network
287 Citations2007Yung Yi, Sanjay Shakkottai
This paper develops a fair hop-by-hop congestion control algorithm with the MAC constraint being imposed in the form of a channel access time constraint, using an optimization based framework, and shows that this algorithm is globally stable using a Lyapunov function based approach.
Dynamic power allocation and routing for time varying wireless networks
250 Citations2004Michael J. Neely, Eytan Modiano +1 more
A joint routing and power allocation policy is developed which stabilizes the system and provides bounded average delay guarantees whenever the input rates are within this capacity region.
Joint congestion control and media access control design for ad hoc wireless networks
249 Citations2005Lijun Chen, Steven H. Low +1 more
This work presents two algorithms that are not only distributed spatially, but more interestingly, they decompose vertically into two protocol layers where TCP and MAC jointly solve the system problem.
IEEE Transactions on Information TheoryScheduling and performance limits of networks with constantly changing topology
171 Citations1997Leandros Tassiulas
A transmission scheduling policy is proposed that utilizes current topology state information and achieves all throughput vectors achievable by any anticipative policy.
Bluetooth Revealed: The Insider's Guide to an Open Specification for Global Wireless Communications
164 Citations2001Brent A. Miller, Chatschik Bisdikian
Bluetooth Revealed previews Bluetooth's future, including next-generation vertical and horizontal applications, and introduces today's resources for Bluetooth development, including silicon and developer's kits as well as legacy product enablers.
Regulated Maximal Matching: A Distributed Scheduling Algorithm for Multi-Hop Wireless Networks With Node-Exclusive Spectrum Sharing
124 Citations2006Xinzhou Wu, R. Srikant
A scheduling algorithm called regulated maximal matching is introduced which is fully distributed and guarantees a throughput that is at least half of the throughput achievable by a centralized algorithm.
Advances in Applied ProbabilityPathwise optimality of the exponential scheduling rule for wireless channels
112 Citations2004Sanjay Shakkottai, R. Srikant +1 more
Given a system with N users, and any set of positive numbers n, it is shown that in a heavy-traffic limit, under a nonrestrictive ‘complete resource pooling’ condition, this algorithm has the property that, for each time t, it minimizes max n a n q́ n (t), where q̃ n is the queue length of user n in the heavy-Traffic regime.
Joint Asynchronous Congestion Control and Distributed Scheduling for Multi-Hop Wireless Networks
97 Citations2006Loc Bui, Atilla Eryılmaz +2 more
An architecture for fair resource allocation that consists of a distributed scheduling algorithm operating in conjunction with an asynchronous congestion control algorithm that supports at least one-third of the throughput supportable by any other algorithm, including centralized algorithms is proposed.
IEEE Transactions on Automatic ControlA regulator stabilization technique: Kumar-Seidman revisited
80 Citations1994Carlos Humes
This note exploits the hereditary properties of the sufficient conditions for stability, relax this condition and presents a regulator based stabilization technique, easily implementable in distributed fashion, and gives an upper bound for the number of regulatory mechanisms to be used in a given system.
End-to-end bandwidth guarantees through fair local spectrum share in wireless ad-hoc networks
51 Citations2004Sunetra Sarkar, Leandros Tassiulas
The algorithm is based on a combination of a link scheduling method to avoid local conflicts, a fair session service discipline per link and a hop-by-hop window flow control scheme and it can be shown that the long term rates allocated to the different sessions are maxmin fair.
Stable scheduling policies for fading wireless channels
33 Citations2003Atilla Eryılmaz, R. Srikant +1 more
The stable scheduling policies for fading wireless channels are described and their various modifications: at any time k, given the current channel state s[k] is studied.
Distributed Fair Resource Allocation in Cellular Networks in the Presence of Heterogeneous Delays
9 Citations2005L. Ying, R. Srikant +2 more
It is shown that the joint congestion control-scheduling algorithm continues to be stable and continues to provide a fair allocation of the network resources.
Routing multimedia packets in a frequency-hop packet radio network
7 Citations2002M.B. Pursley, H.B. Russell +1 more
A new method is described for routing multimedia traffic in a frequency-hop (FH) store-and-forward packet radio network based on least-resistance routing with different link and path resistance metrics for different message types.