The impact of imperfect scheduling on cross-layer congestion control in wireless networks

ABSTRACT

In this paper, we study cross-layer design for congestion control in multihop wireless networks. In previous work, we have developed an optimal cross-layer congestion control scheme that jointly computes both the rate allocation and the stabilizing schedule that controls the resources at the underlying layers. However, the scheduling component in this optimal cross-layer congestion control scheme has to solve a complex global optimization problem at each time, and is hence too computationally expensive for online implementation. In this paper, we study how the performance of cross-layer congestion control will be impacted if the network can only use an imperfect (and potentially distributed) scheduling component that is easier to implement. We study both the case when the number of users in the system is fixed and the case with dynamic arrivals and departures of the users, and we establish performance bounds of cross-layer congestion control with imperfect scheduling. Compared with a layered approach that does not design congestion control and scheduling together, our cross-layer approach has provably better performance bounds, and substantially outperforms the layered approach. The insights drawn from our analyzes also enable us to design a fully distributed cross-layer congestion control and scheduling algorithm for a restrictive interference model.

REFERENCES

• 1: [1] X. Lin and N. B. Shroff, "The impact of imperfect scheduling on cross-layer rate control in wireless networks," in Proc. IEEE INFOCOM, Miami, FL, Mar. 2005, pp. 1804-1814.
• 2: [2] L. Xiao, M. Johansson, and S. Boyd, "Simultaneous routing and resource allocation via dual decomposition," in Proc. 4th Asian Control Conf., Singapore, Sep. 2002, pp. 29-34.
• 3: [3] M. Johansson, L. Xiao, and S. Boyd, "Simultaneous routing and power allocation in CDMA wireless data networks," in Proc. IEEE Int. Conf. Communications, Anchorage, AK, May 2003, pp. 51-55.
• 4: [4] M. J. Neely, E. Modiano, and C. E. Rohrs, "Dynamic power allocation and routing for time varying wireless networks," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003, pp. 745-755.
• 5: [5] S. Toumpis and A. J. Goldsmith, "Capacity regions for wireless ad hoc networks," IEEE Trans. Wireless Commun., vol. 2, no. 4, pp. 736-748, Jul. 2003.
• 6: Atilla Eryilmaz , R. Srikant , James R. Perkins, Stable scheduling policies for fading wireless channels, IEEE/ACM Transactions on Networking (TON), v.13 n.2, p.411-424, April 2005 [doi>10.1109/TNET.2004.842226]
• 7: [7] R. L. Cruz and A. V. Santhanam, "Optimal routing, link scheduling and power control in multi-hop wireless networks," in Proc. IEEE INFOCOM , San Francisco, CA, Apr. 2003, pp. 702-711.
• 8: [8] L. Tassiulas and A. Ephremides, "Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks," IEEE Trans. Autom. Control, vol. 37, no. 12, pp. 1936-1948, Dec. 1992.
• 9: [9] X. Lin and N. B. Shroff, "Joint rate control and scheduling in multihop wireless networks," in Proc. IEEE Conf. Decision and Control, Paradise Island, Bahamas, Dec. 2004, pp. 1484-1489.
• 10: [10] M. Johansson and L. Xiao, "Scheduling, routing and power allocation for fairness in wireless networks," in IEEE Vehicular Technology Conf. (VTC)-Spring, Milan, Italy, May 2004, pp. 1355-1360.
• 11: [11] M. Chiang, "To layer or not to layer: balancing transport and physical layers in wireless multihop networks," in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004, pp. 2525-2536.
• 12: [12] M. J. Neely, E. Modiano, and C. Li, "Fairness and optimal stochastic control for heterogeneous networks," in Proc. IEEE INFOCOM, Miami, FL, Mar. 2005, pp. 1723-1734.
• 13: [13] L. Chen, S. H. Low, and J. C. Doyle, "Joint congestion control and media access control design for wireless ad hoc networks," in Proc. IEEE INFOCOM, Miami, FL, Mar. 2005, pp. 2212-2222.
• 14: [14] I. Paschalidis, W. Lai, and D. Starobinski, "Asymptotically optimal transmission policies for low-power wireless sensor networks," in Proc. IEEE INFOCOM, Miami, FL, Mar. 2005, pp. 2458-2469.
• 15: [15] S. H. Low and R. Srikant, "A mathematical framework for designing a low-loss low-delay Internet," Network and Spatial Economics, vol. 4, no. 1, pp. 75-102, Mar. 2004.
• 16: Rayadurgam Srikant, The Mathematics of Internet Congestion Control (Systems and Control: Foundations and Applications), SpringerVerlag, 2004
• 17: [17] S. Sarkar and L. Tassiulas, "End-to-end bandwidth guarantees through fair local spectrum share in wireless ad hoc networks," in Proc. IEEE Conf. Decision and Control, Maui, HI, Dec. 2003, pp. 564-569.
• 18: [18] Y. Yi and S. Shakkottai, "Hop-by-hop congestion control over a wireless multi-hop network," in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004, pp. 2548-2558.
• 19: [19] Y. Xue, B. Li, and K. Nahrstedt, "Price-based resource allocation in wireless ad hoc networks," in Proc. 11th Int. Workshop on Quality of Service (IWQoS 2003), Monterey, CA, Jun. 2003, vol. LNCS 2707, pp. 79-96.
• 20: [20] X. Lin and N. B. Shroff, The impact of imperfect scheduling on cross-layer rate control in multihop wireless networks. Technical Report, Purdue Univ., W. Lafayette, IN, 2004 [Online]. Available: http://min. ecn.purdue.edu/~linx/papers.html
• 21: Thomas Bonald , Laurent Massoulié, Impact of fairness on Internet performance, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.82-91, June 2001, Cambridge, Massachusetts, United States
• 22: Jeonghoon Mo , Jean Walrand, Fair end-to-end window-based congestion control, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.556-567, Oct. 2000 [doi>10.1109/90.879343]
• 23: [23] J. M. Borwein and A. S. Lewis, Convex Analysis and Nonlinear Optimization: Theory and Examples. New York: Springer, 2000.
• 24: N. Z. Shor , Krzysztof C. Kiwiel , Andrzej Ruszcayǹski, Minimization methods for non-differentiable functions, Springer-Verlag New York, Inc., New York, NY, 1985
• 25: Emilio Leonardi , Marco Mellia , Fabio Neri , Marco Ajmone Marsan, On the stability of input-queued switches with speed-up, IEEE/ACM Transactions on Networking (TON), v.9 n.1, p.104-118, Feb., 2001 [doi>10.1109/90.909028]
• 26: Gustavo de Veciana , Takis Konstantopoulos , Tae-Jin Lee, Stability and performance analysis of networks supporting elastic services, IEEE/ACM Transactions on Networking (TON), v.9 n.1, p.2-14, Feb., 2001 [doi>10.1109/90.909020]
• 27: [27] G. Fayolle, A. L. Fortelle, J. M. Lasgouttes, L. Massoulie, and J. Roberts, "Best effort networks: modeling and performance analysis via large network asymptotics," in Proc. IEEE INFOCOM, Anchorage, AK, Apr. 2001, pp. 709-716.
• 28: [28] H. Q. Ye, "Stability of data networks under an optimization-based bandwidth allocation," IEEE Trans. Autom. Control, vol. 48, no. 7, pp. 1238-1242, Jul. 2003.
• 29: Michael J. Neely , Eytan Modiano , Charles E. Rohrs, Power allocation and routing in multibeam satellites with time-varying channels, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.138-152, February 2003 [doi>10.1109/TNET.2002.808401]
• 30: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 31: [31] J. G. Dai and B. Prabhakar, "The throughput of data switches with and without speedup," in Proc. IEEE INFOCOM, Tel Aviv, Israel, Mar. 2000, pp. 556-564.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
      C.2.3 Network Operations
          Subjects: Network management
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Design, Management, Performance

Keywords:
congestion control, cross-layer design, imperfect scheduling, mathematical programming/optimization, multihop wireless networks, stability, stochastic processes/queueing theory