The Experts below are selected from a list of 9342 Experts worldwide ranked by ideXlab platform
Eytan Modiano - One of the best experts on this subject based on the ideXlab platform.
-
Loop-Free Backpressure Routing Using Link-Reversal Algorithms
IEEE ACM Transactions on Networking, 2017Co-Authors: Anurag Rai, Li Chih-ping, Georgios S. Paschos, Eytan ModianoAbstract:The Backpressure routing policy is known to be a throughput optimal policy that supports any feasible traffic demand, but may have poor delay performance when packets traverse loops in the network. In this paper, we study loop-free Backpressure routing policies that forward packets along directed acyclic graphs (DAGs) to avoid the looping problem. These policies use link reversal algorithms to improve the DAGs in order to support any achievable traffic demand. For a network with a single commodity, we show that a DAG that supports a given traffic demand can be found after a finite number of iterations of the link-reversal process. We use this to develop a joint link-reversal and Backpressure routing policy, called the loop free Backpressure (LFBP) algorithm. This algorithm forwards packets on the DAG, while the DAG is dynamically updated based on the growth of the queue backlogs. We show by simulations that such a DAG-based policy improves the delay over the classical Backpressure routing policy. We also propose a multicommodity version of the LFBP algorithm and via simulation show that its delay performance is better than that of Backpressure.
-
TCP-Aware Backpressure Routing and Scheduling
IEEE Transactions on Mobile Computing, 2016Co-Authors: Hulya Seferoglu, Eytan ModianoAbstract:In this work, we explore the performance of Backpressure routing and scheduling for TCP flows over wireless networks. TCP and Backpressure are not compatible due to a mismatch between the congestion control mechanism of TCP and the queue size based routing and scheduling of the Backpressure framework. We propose a TCP-aware Backpressure routing and scheduling mechanism that takes into account the behavior of TCP flows. TCP-aware Backpressure provides throughput optimality guarantees in the Lyapunov optimization framework, and gracefully combines TCP and Backpressure without making any changes to the TCP protocol. The simulation results show that TCP-aware Backpressure (i) improves the throughput of TCP flows significantly, (ii) provides fairness across competing TCP flows, and (iii) accommodates both TCP and non-TCP flows in a wireless network, and improves throughput of these flows without hurting fairness.
-
MobiHoc - Loop-Free Backpressure Routing Using Link-Reversal Algorithms
Proceedings of the 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2015Co-Authors: Anurag Rai, Li Chih-ping, Georgios S. Paschos, Eytan ModianoAbstract:The Backpressure routing policy is known to be a throughput optimal policy that supports any feasible traffic demand in data networks, but may have poor delay performance when packets traverse loops in the network. In this paper, we study loop-free Backpressure routing policies that forward packets along directed acyclic graphs (DAGs) to avoid the looping problem. These policies use link reversal algorithms to improve the DAGs in order to support any achievable traffic demand. For a network with a single commodity, we show that a DAG that supports a given traffic demand can be found after a finite number of iterations of the link-reversal process. We use this to develop a joint link-reversal and Backpressure routing policy, called the loop free Backpressure (LFBP) algorithm. This algorithm forwards packets on the DAG, while the DAG is dynamically updated based on the growth of the queue backlogs. We show by simulations that such a DAG-based policy improves the delay over the classical Backpressure routing policy. We also propose a multicommodity version of the LFBP algorithm, and via simulation we show that its delay performance is better than that of Backpressure.
-
Loop-Free Backpressure Routing Using Link-Reversal Algorithms
arXiv: Networking and Internet Architecture, 2015Co-Authors: Anurag Rai, Li Chih-ping, Georgios S. Paschos, Eytan ModianoAbstract:The Backpressure routing policy is known to be a throughput optimal policy that supports any feasible traffic demand in data networks, but may have poor delay performance when packets traverse loops in the network. In this paper, we study loop-free Backpressure routing policies that forward packets along directed acyclic graphs (DAGs) to avoid the looping problem. These policies use link reversal algorithms to improve the DAGs in order to support any achievable traffic demand. For a network with a single commodity, we show that a DAG that supports a given traffic demand can be found after a finite number of iterations of the link-reversal process. We use this to develop a joint link-reversal and Backpressure routing policy, called the loop free Backpressure (LFBP) algorithm. This algorithm forwards packets on the DAG, while the DAG is dynamically updated based on the growth of the queue backlogs. We show by simulations that such a DAG-based policy improves the delay over the classical Backpressure routing policy. We also propose a multicommodity version of the LFBP algorithm, and via simulation we show that its delay performance is better than that of Backpressure.
-
ITA - TCP-aware Backpressure routing and scheduling
2014 Information Theory and Applications Workshop (ITA), 2014Co-Authors: Hulya Seferoglu, Eytan ModianoAbstract:In this work, we explore the performance of back-pressure routing and scheduling for TCP flows over wireless networks. TCP and Backpressure are not compatible due to a mismatch between the congestion control mechanism of TCP and the queue size based routing and scheduling of the back-pressure framework. We propose a TCP-aware Backpressure routing and scheduling that takes into account the behavior of TCP flows. TCP-aware Backpressure (i) provides throughput optimality guarantees in the Lyapunov optimization framework, (ii) gracefully combines TCP and Backpressure without making any changes to the TCP protocol, (iii) improves the throughput of TCP flows significantly, and (iv) provides fairness across competing TCP flows.
Michael J. Neely - One of the best experts on this subject based on the ideXlab platform.
-
a new Backpressure algorithm for joint rate control and routing with vanishing utility optimality gaps and finite queue lengths
IEEE ACM Transactions on Networking, 2018Co-Authors: Michael J. NeelyAbstract:The Backpressure algorithm has been widely used as a distributed solution to the problem of joint rate control and routing in multi-hop data networks. By controlling an algorithm parameter, the Backpressure algorithm can achieve an arbitrarily small utility optimality gap. However, this in turn brings in a large queue length at each node and hence causes large network delay. This phenomenon is known as the fundamental utility-delay tradeoff. The best known utility-delay tradeoff for general networks is $[O(\epsilon ), O(1/\epsilon )]$ and is attained by a Backpressure algorithm based on a drift-plus-penalty technique. This may suggest that to achieve an arbitrarily small utility optimality gap, Backpressure-based algorithms must incur arbitrarily large queue lengths. However, this paper proposes a new Backpressure algorithm that has a vanishing utility optimality gap, so utility converges to exact optimality as the algorithm keeps running, while queue lengths are bounded throughout by a finite constant. The technique uses Backpressure and drift concepts with a new method for convex programming.
-
A New Backpressure Algorithm for Joint Rate Control and Routing with Vanishing Utility Optimality Gaps and Finite Queue Lengths
arXiv: Networking and Internet Architecture, 2017Co-Authors: Michael J. NeelyAbstract:The Backpressure algorithm has been widely used as a distributed solution to the problem of joint rate control and routing in multi-hop data networks. By controlling a parameter $V$ in the algorithm, the Backpressure algorithm can achieve an arbitrarily small utility optimality gap. However, this in turn brings in a large queue length at each node and hence causes large network delay. This phenomenon is known as the fundamental utility-delay tradeoff. The best known utility-delay tradeoff for general networks is $[O(1/V), O(V)]$ and is attained by a Backpressure algorithm based on a drift-plus-penalty technique. This may suggest that to achieve an arbitrarily small utility optimality gap, the existing Backpressure algorithms necessarily yield an arbitrarily large queue length. However, this paper proposes a new Backpressure algorithm that has a vanishing utility optimality gap, so utility converges to exact optimality as the algorithm keeps running, while queue lengths are bounded throughout by a finite constant. The technique uses Backpressure and drift concepts with a new method for convex programming.
-
LIFO-Backpressure achieves near-optimal utility-delay tradeoff
IEEE ACM Transactions on Networking, 2013Co-Authors: Longbo Huang, Scott Moeller, Michael J. Neely, Bhaskar KrishnamachariAbstract:There has been considerable work developing a stochastic network utility maximization framework using Backpressure algorithms, also known as MaxWeight. A key open problem has been the development of utility-optimal algorithms that are also delay-efficient. In this paper, we show that the Backpressure algorithm, when combined with the last-in-first-out (LIFO) queueing discipline (called LIFO-Backpressure), is able to achieve a utility that is within O(1/V) of the optimal value, for any scalar V ≥ 1, while maintaining an average delay of O([log(V)]2) for all but a tiny fraction of the network traffic. This result holds for a general class of problems with Markovian dynamics. Remarkably, the performance of LIFO-Backpressure can be achieved by simply changing the queueing discipline; it requires no other modifications of the original Backpressure algorithm. We validate the results through empirical measurements from a sensor network testbed, which show a good match between theory and practice. Because some packets may stay in the queues for a very long time under LIFO-Backpressure, we further develop the LIFOp-Backpressure algorithm, which generalizes LIFOp-Backpressure by allowing interleaving between first-in-first-out (FIFO) and LIFO. We show that LIFOp Backpressure also achieves the same O(1/V) close-to-optimal utility performance and guarantees an average delay of O([log(V)]2) for the packets that are served during the LIFO period.
-
Backpressure with adaptive redundancy bwar
International Conference on Computer Communications, 2012Co-Authors: Majed Alresaini, Bhaskar Krishnamachari, Maheswaran Sathiamoorthy, Michael J. NeelyAbstract:Backpressure scheduling and routing, in which packets are preferentially transmitted over links with high queue differentials, offers the promise of throughput-optimal operation for a wide range of communication networks. However, when the traffic load is low, due to the corresponding low queue occupancy, Backpressure scheduling/routing experiences long delays. This is particularly of concern in intermittent encounter-based mobile networks which are already delay-limited due to the sparse and highly dynamic network connectivity. While state of the art mechanisms for such networks have proposed the use of redundant transmissions to improve delay, they do not work well when the traffic load is high. We propose in this paper a novel hybrid approach that we refer to as Backpressure with adaptive redundancy (BWAR), which provides the best of both worlds. This approach is highly robust and distributed and does not require any prior knowledge of network load conditions. We evaluate BWAR through both mathematical analysis and simulations based on a cell-partitioned model. We prove theoretically that BWAR does not perform worse than traditional Backpressure in terms of the maximum throughput, while yielding a better delay bound. The simulations confirm that BWAR outperforms traditional Backpressure at low load, while outperforming a state of the art encounter-routing scheme (Spray and Wait) at high load.
-
INFOCOM - Backpressure with Adaptive Redundancy (BWAR)
2012 Proceedings IEEE INFOCOM, 2012Co-Authors: Majed Alresaini, Bhaskar Krishnamachari, Maheswaran Sathiamoorthy, Michael J. NeelyAbstract:Backpressure scheduling and routing, in which packets are preferentially transmitted over links with high queue differentials, offers the promise of throughput-optimal operation for a wide range of communication networks. However, when the traffic load is low, due to the corresponding low queue occupancy, Backpressure scheduling/routing experiences long delays. This is particularly of concern in intermittent encounter-based mobile networks which are already delay-limited due to the sparse and highly dynamic network connectivity. While state of the art mechanisms for such networks have proposed the use of redundant transmissions to improve delay, they do not work well when the traffic load is high. We propose in this paper a novel hybrid approach that we refer to as Backpressure with adaptive redundancy (BWAR), which provides the best of both worlds. This approach is highly robust and distributed and does not require any prior knowledge of network load conditions. We evaluate BWAR through both mathematical analysis and simulations based on a cell-partitioned model. We prove theoretically that BWAR does not perform worse than traditional Backpressure in terms of the maximum throughput, while yielding a better delay bound. The simulations confirm that BWAR outperforms traditional Backpressure at low load, while outperforming a state of the art encounter-routing scheme (Spray and Wait) at high load.
Hulya Seferoglu - One of the best experts on this subject based on the ideXlab platform.
-
TCP-Aware Backpressure Routing and Scheduling
IEEE Transactions on Mobile Computing, 2016Co-Authors: Hulya Seferoglu, Eytan ModianoAbstract:In this work, we explore the performance of Backpressure routing and scheduling for TCP flows over wireless networks. TCP and Backpressure are not compatible due to a mismatch between the congestion control mechanism of TCP and the queue size based routing and scheduling of the Backpressure framework. We propose a TCP-aware Backpressure routing and scheduling mechanism that takes into account the behavior of TCP flows. TCP-aware Backpressure provides throughput optimality guarantees in the Lyapunov optimization framework, and gracefully combines TCP and Backpressure without making any changes to the TCP protocol. The simulation results show that TCP-aware Backpressure (i) improves the throughput of TCP flows significantly, (ii) provides fairness across competing TCP flows, and (iii) accommodates both TCP and non-TCP flows in a wireless network, and improves throughput of these flows without hurting fairness.
-
ITA - TCP-aware Backpressure routing and scheduling
2014 Information Theory and Applications Workshop (ITA), 2014Co-Authors: Hulya Seferoglu, Eytan ModianoAbstract:In this work, we explore the performance of back-pressure routing and scheduling for TCP flows over wireless networks. TCP and Backpressure are not compatible due to a mismatch between the congestion control mechanism of TCP and the queue size based routing and scheduling of the back-pressure framework. We propose a TCP-aware Backpressure routing and scheduling that takes into account the behavior of TCP flows. TCP-aware Backpressure (i) provides throughput optimality guarantees in the Lyapunov optimization framework, (ii) gracefully combines TCP and Backpressure without making any changes to the TCP protocol, (iii) improves the throughput of TCP flows significantly, and (iv) provides fairness across competing TCP flows.
-
TCP-Aware Backpressure Routing and Scheduling
arXiv: Networking and Internet Architecture, 2013Co-Authors: Hulya Seferoglu, Eytan ModianoAbstract:In this work, we explore the performance of Backpressure routing and scheduling for TCP flows over wireless networks. TCP and Backpressure are not compatible due to a mismatch between the congestion control mechanism of TCP and the queue size based routing and scheduling of the Backpressure framework. We propose a TCP-aware Backpressure routing and scheduling that takes into account the behavior of TCP flows. TCP-aware Backpressure (i) provides throughput optimality guarantees in the Lyapunov optimization framework, (ii) gracefully combines TCP and Backpressure without making any changes to the TCP protocol, (iii) improves the throughput of TCP flows significantly, and (iv) provides fairness across competing TCP flows.
E.l. Hahne - One of the best experts on this subject based on the ideXlab platform.
-
Sharing memory in banyan-based ATM switches
IEEE Journal on Selected Areas in Communications, 1997Co-Authors: D. Basak, A.k. Choudhury, E.l. HahneAbstract:We study a multistage ATM switch in which shared-memory switching elements are arranged in a banyan topology. By "shared-memory," we mean that each switching element uses output queueing and shares its local cell buffer memory among all its output ports. We apply a buffer management technique called delayed pushout that was originally designed for multistage ATM switches with hierarchical topologies. Delayed pushout combines a pushout mechanism, for sharing memory efficiently among queues within the same switching element, and a Backpressure mechanism, for sharing memory across switch stages. The Backpressure component has a threshold to restrict the amount of sharing between stages. A synergy emerges when pushout, Backpressure, and this threshold are all employed together. Using a computer simulation of the switch under bursty traffic, we study delayed pushout as well as several simpler pushout and Backpressure schemes under a variety of traffic conditions. Of the five schemes we simulate, delayed pushout is the only one that performs well under all load conditions.
Bhaskar Krishnamachari - One of the best experts on this subject based on the ideXlab platform.
-
LIFO-Backpressure achieves near-optimal utility-delay tradeoff
IEEE ACM Transactions on Networking, 2013Co-Authors: Longbo Huang, Scott Moeller, Michael J. Neely, Bhaskar KrishnamachariAbstract:There has been considerable work developing a stochastic network utility maximization framework using Backpressure algorithms, also known as MaxWeight. A key open problem has been the development of utility-optimal algorithms that are also delay-efficient. In this paper, we show that the Backpressure algorithm, when combined with the last-in-first-out (LIFO) queueing discipline (called LIFO-Backpressure), is able to achieve a utility that is within O(1/V) of the optimal value, for any scalar V ≥ 1, while maintaining an average delay of O([log(V)]2) for all but a tiny fraction of the network traffic. This result holds for a general class of problems with Markovian dynamics. Remarkably, the performance of LIFO-Backpressure can be achieved by simply changing the queueing discipline; it requires no other modifications of the original Backpressure algorithm. We validate the results through empirical measurements from a sensor network testbed, which show a good match between theory and practice. Because some packets may stay in the queues for a very long time under LIFO-Backpressure, we further develop the LIFOp-Backpressure algorithm, which generalizes LIFOp-Backpressure by allowing interleaving between first-in-first-out (FIFO) and LIFO. We show that LIFOp Backpressure also achieves the same O(1/V) close-to-optimal utility performance and guarantees an average delay of O([log(V)]2) for the packets that are served during the LIFO period.
-
Backpressure with adaptive redundancy bwar
International Conference on Computer Communications, 2012Co-Authors: Majed Alresaini, Bhaskar Krishnamachari, Maheswaran Sathiamoorthy, Michael J. NeelyAbstract:Backpressure scheduling and routing, in which packets are preferentially transmitted over links with high queue differentials, offers the promise of throughput-optimal operation for a wide range of communication networks. However, when the traffic load is low, due to the corresponding low queue occupancy, Backpressure scheduling/routing experiences long delays. This is particularly of concern in intermittent encounter-based mobile networks which are already delay-limited due to the sparse and highly dynamic network connectivity. While state of the art mechanisms for such networks have proposed the use of redundant transmissions to improve delay, they do not work well when the traffic load is high. We propose in this paper a novel hybrid approach that we refer to as Backpressure with adaptive redundancy (BWAR), which provides the best of both worlds. This approach is highly robust and distributed and does not require any prior knowledge of network load conditions. We evaluate BWAR through both mathematical analysis and simulations based on a cell-partitioned model. We prove theoretically that BWAR does not perform worse than traditional Backpressure in terms of the maximum throughput, while yielding a better delay bound. The simulations confirm that BWAR outperforms traditional Backpressure at low load, while outperforming a state of the art encounter-routing scheme (Spray and Wait) at high load.
-
INFOCOM - Backpressure with Adaptive Redundancy (BWAR)
2012 Proceedings IEEE INFOCOM, 2012Co-Authors: Majed Alresaini, Bhaskar Krishnamachari, Maheswaran Sathiamoorthy, Michael J. NeelyAbstract:Backpressure scheduling and routing, in which packets are preferentially transmitted over links with high queue differentials, offers the promise of throughput-optimal operation for a wide range of communication networks. However, when the traffic load is low, due to the corresponding low queue occupancy, Backpressure scheduling/routing experiences long delays. This is particularly of concern in intermittent encounter-based mobile networks which are already delay-limited due to the sparse and highly dynamic network connectivity. While state of the art mechanisms for such networks have proposed the use of redundant transmissions to improve delay, they do not work well when the traffic load is high. We propose in this paper a novel hybrid approach that we refer to as Backpressure with adaptive redundancy (BWAR), which provides the best of both worlds. This approach is highly robust and distributed and does not require any prior knowledge of network load conditions. We evaluate BWAR through both mathematical analysis and simulations based on a cell-partitioned model. We prove theoretically that BWAR does not perform worse than traditional Backpressure in terms of the maximum throughput, while yielding a better delay bound. The simulations confirm that BWAR outperforms traditional Backpressure at low load, while outperforming a state of the art encounter-routing scheme (Spray and Wait) at high load.
-
WiOpt - LIFO-Backpressure achieves near optimal utility-delay tradeoff
2011 International Symposium of Modeling and Optimization of Mobile Ad Hoc and Wireless Networks, 2011Co-Authors: Longbo Huang, Scott Moeller, Michael J. Neely, Bhaskar KrishnamachariAbstract:There has been considerable recent work developing a new stochastic network utility maximization framework using Backpressure algorithms, also known as MaxWeight. A key open problem has been the development of utility-optimal algorithms that are also delay efficient. In this paper, we show that the Backpressure algorithm, when combined with the LIFO queueing discipline (called LIFO-Backpressure), is able to achieve a utility that is within O(1/V) of the optimal value for any scalar V ≥ 1, while maintaining an average delay of O([log(V)]2) for all but a tiny fraction of the network traffic. This result holds for general stochastic network optimization problems and general Markovian dynamics. Remarkably, the performance of LIFO-Backpressure can be achieved by simply changing the queueing discipline; it requires no other modifications of the original Backpressure algorithm. We validate the results through empirical measurements from a sensor network testbed, which show good match between theory and practice.
-
LIFO-Backpressure Achieves Near Optimal Utility-Delay Tradeoff
arXiv: Optimization and Control, 2010Co-Authors: Longbo Huang, Scott Moeller, Michael J. Neely, Bhaskar KrishnamachariAbstract:There has been considerable recent work developing a new stochastic network utility maximization framework using Backpressure algorithms, also known as MaxWeight. A key open problem has been the development of utility-optimal algorithms that are also delay efficient. In this paper, we show that the Backpressure algorithm, when combined with the LIFO queueing discipline (called LIFO-Backpressure), is able to achieve a utility that is within $O(1/V)$ of the optimal value, while maintaining an average delay of $O([\log(V)]^2)$ for all but a tiny fraction of the network traffic. This result holds for general stochastic network optimization problems and general Markovian dynamics. Remarkably, the performance of LIFO-Backpressure can be achieved by simply changing the queueing discipline; it requires no other modifications of the original Backpressure algorithm. We validate the results through empirical measurements from a sensor network testbed, which show good match between theory and practice.
