Joint congestion control and media access control design for ad hoc wireless networks
Published 24 August 2005
Lijun Chen, Steven H. Low, John C. Doyle
Citations249
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
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.
Abstract
We present a model for the joint design of congestion control and media access control (MAC) for ad hoc wireless networks. Using contention graph and contention matrix, we formulate resource allocation in the network as a utility maximization problem with constraints that arise from contention for channel access. We present 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. The first is a primal algorithm where the MAC layer at the links generates congestion (contention) prices based on local aggregate source rates, and TCP sources adjust their rates based on the aggregate prices in their paths. The second is a dual subgradient algorithm where the MAC sub-algorithm is implemented through scheduling link-layer flows according to the congestion prices of the links. Global convergence properties of these algorithms are proved. This is a preliminary step towards a systematic approach to jointly design TCP congestion control algorithms and MAC algorithms, not only to improve performance, but more importantly, to make their interaction more transparent.
Keywords
Computer ScienceEngineering
Cambridge University Press eBooksConvex Optimization
31,266 Citations2004Stephen Boyd, Lieven Vandenberghe
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/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 Communications MagazineDoes the IEEE 802.11 MAC protocol work well in multihop wireless ad hoc networks?
909 Citations2001S. Xu, Tarek Saadawi
It is concluded that the current version of this wireless LAN protocol does not function well in multihop ad hoc networks, and it is doubt whether the WaveLAN-based system is workable as a mobile ad hoc testbed.
IEEE Communications MagazineCross-layer design for wireless networks
849 Citations2003Sanjay Shakkottai, Theodore S. Rappaport +1 more
This article addresses the issue of cross-layer networking, where the physical and MAC layer knowledge of the wireless medium is shared with higher layers, in order to provide efficient methods of allocating network resources and applications over the Internet.
Analysis of TCP performance over mobile ad hoc networks
707 Citations1999Gavin Holland, Nitin H. Vaidya
A new metric, expected throughput, is introduced for the comparison of throughput in multi-hop networks, and this metric is used to show how the use of explicit link failure notification (ELFN) techniques can significantly improve TCP performance.
Achieving MAC layer fairness in wireless packet networks
667 Citations2000Thyaga Nandagopal, Tae‐Eun Kim +2 more
A general analytical framework is proposed that captures the unique characteristics of shared wireless channels and allows the modeling of a large class of system-wide fairness models via the specification of per-flow utility functions and generates local contention resolution mechanisms in response to a given utility function.
IEEE/ACM Transactions on NetworkingA duality model of TCP and queue management algorithms
658 Citations2003Steven H. Low
A duality model of end-to-end congestion control is proposed and applied to understand the equilibrium properties of TCP and active queue management schemes to maximize aggregate utility subject to capacity constraints.
IEEE Transactions on Wireless CommunicationsJoint scheduling and power control for wireless ad hoc networks
576 Citations2004Tamer ElBatt, Anthony Ephremides
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.
Distributed fair scheduling in a wireless LAN
547 Citations2000Nitin H. Vaidya, Paramvir Bahl +1 more
Simulation results show that the proposed algorithm is able to schedule transmissions such that the bandwidth allocated to different flows is proportional to their weights.
The impact of multihop wireless channel on TCP throughput and loss
524 Citations2004Zhixiao Fu, Petros Zerfos +4 more
This paper studies TCP performance over multihop wireless networks that use the IEEE 802.11 protocol as the access method and proposes two techniques, link RED and adaptive pacing, through which it is able to improve TCP throughput by 5% to 30% in various simulated topologies.
IEEE/ACM Transactions on NetworkingEnd-to-end congestion control schemes: utility functions, random losses and ecn marks
449 Citations2003S.S. Kunniyur, R. Srikant
Wireless NetworksAnalysis of TCP Performance over Mobile Ad Hoc Networks
407 Citations2002Gavin Holland, Nitin H. Vaidya
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 Personal CommunicationsA feedback-based scheme for improving TCP performance in ad hoc wireless networks
310 Citations2001Keerthi Chandran, Srinivasan Raghunathan +2 more
Joint scheduling and power control for wireless ad-hoc networks
302 Citations2003Tamer ElBatt, Anthony Ephremides
This paper introduces power control as a solution to the multiple access problem in contention-based wireless ad-hoc networks, limiting multi-user interference to increase single-hop throughput, and reducing power consumption to increase battery life.
Maxmin fair scheduling in wireless networks
290 Citations2003Leandros Tassiulas, Sunetra Sarkar
A fair scheduling which assigns dynamic weights to the flows such that the weights depend on the congestion in the neighborhood and schedule the flows which constitute a maximum weighted matching is proposed.
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.
On max-min fairness and scheduling in wireless ad-hoc networks
282 Citations2001Xiao Long Huang, Brahim Bensaou
The theoretical framework by which one can calculate the fair shares that would achieve max-min fairness in an ad-hoc network is laid down, which design distributed algorithms that allow each node to determine itsmax-min per-link fair share in a global ad-Hoc network without knowledge of the global topology of the network.
A comparison of TCP performance over three routing protocols for mobile ad hoc networks
247 Citations2001Thomas D. Dyer, Rajendra V. Boppana
The results indicate that the proactive ADV algorithm performs well under a variety of conditions and that the fixed RTO technique improves the performances of the two on-demand algorithms significantly.
A feedback based scheme for improving TCP performance in ad-hoc wireless networks
235 Citations2002Keerthi Chandran, S. Ragbunathan +2 more
It is observed that in the event of route failures, as the route re-establishment time increases, the use of feedback provides significant gains in throughput as well as savings in unnecessary packet transmissions.
Improving TCP performance over mobile ad-hoc networks with out-of-order detection and response
230 Citations2002Feng Wang, Yongguang Zhang
This research explores a new approach to improve TCP performance by detecting and responding to out-of-order packet delivery events, which are the results of frequent route changes in a Mobile Ad Hoc Network.
IEEE Transactions on Automatic ControlA Unifying Passivity Framework for Network Flow Control
228 Citations2004John T. Wen, Murat Arcak
This paper presents a unifying framework which encompasses global stability results as special cases for flow control schemes by using a passivity approach, and significantly expands the current classes of stable flow controllers by augmenting the source and link update laws with passive dynamic systems.
Enhancing TCP fairness in ad hoc wireless networks using neighborhood RED
219 Citations2003Kaixin Xu, Mário Gerla +2 more
A Neighborhood RED (NRED) scheme is proposed, which extends the RED concept to the distributed neighborhood queue, and can improve TCP unfairness substantially in ad hoc networks.
Fair bandwidth sharing algorithms based on game theory frameworks for wireless ad-hoc networks
208 Citations2005Zuyuan Fang, Brahim Bensaou
Some applications are presented to show how such a framework can be invoked to design efficient media access control protocols in a noncooperative, self-organized, topology-blind environment as well as in environments where the competing nodes share some basic information to guide their choice of channel access policies.
To layer or not to layer: balancing transport and physical layers in wireless multihop networks
173 Citations2004Mung Chiang
Under the rigorous framework of nonlinearly constrained optimization, this work proves the convergence of this coupled system to the global optimum of joint power control and congestion control, for both synchronized and asynchronous implementations.
A comparison of TCP performance over three routing protocols for mobile ad hoc networks
154 Citations2001Thomas D. Dyer, Rajendra V. Boppana
TCP over wireless multi-hop protocols: simulation and experiments
96 Citations2003Mário Gerla, Rajive Bagrodia +3 more
This paper provides new insight into two critical problems of TCP over wireless multi-hop, the conflict between data packets and ACKs, which causes TCP performance to degrade for window sizes greater than 1 packet and the interaction between MAC and TCP layer backoff timers which causes severe unfairness and capture conditions.
TCP behavior across multihop wireless networks and the wired internet
84 Citations2002Kaixin Xu, Sang Bae +2 more
The fairness issues of multiple TCP flows as well as the coexistence of TCP flows and video streams in the wired/wireless scenario are investigated and will prove very valuable to future commercial and military ad hoc networks.
Fair Sharing of MAC under TCP in Wireless Ad Hoc Networks
78 Citations1999Ken Tang, Mário Gerla
Using simulation, this study provides new insights into the interactions between TCP and various MAC layer protocols, including CSMA, FAMA and 802.11, and addresses the issue of fair sharing of MAC with multiple TCP flows.
A topology-independent fair queueing model in ad hoc wireless networks
72 Citations2002Haiyun Luo, Songwu Lu
This paper proposes a new topology-independent fair queueing model for a shared-medium ad hoc network that ensures coordinated fair channel access among spatially contending flows while seeking to maximize spatial channel reuse.
A unifying passivity framework for network flow control
63 Citations2003John T. Wen, Murat Arcak
This paper presents a unifying framework which encompasses global stability results as special cases for several flow control schemes by using a passivity approach, and significantly expands the current classes of stable flow controllers by augmenting the source and link update laws with passive dynamic systems.
Can shortest-path routing and TCP maximize utility
39 Citations2004J. Wang, Liming Li +2 more
This paper proves rigorously that shortest-path routing based purely on congestion prices is unstable, and that routing instability can reduce utility to less than that achievable by the necessarily stable static routing.
SIAM Journal on ComputingGuaranteeing Fair Service to Persistent Dependent Tasks
36 Citations1998Amotz Bar-Noy, Alain Mayer +2 more
This work introduces a new scheduling problem that is motivated by applications in the area of access and ∞ow control in high-speed and wireless networks and presents fair and ecient scheduling algorithms for the case where the con∞ict graph is an interval graph.
IEEE Journal on Selected Areas in CommunicationsA topology-independent wireless fair queueing model in ad hoc networks
26 Citations2005Haiyun Luo, Songwu Lu
This paper proposes a new topology-independent fair queueing model for a shared-medium ad hoc network that ensures coordinated fair channel access among spatially contending flows, while seeking to maximize spatial reuse of bandwidth.