Fairness and optimal stochastic control for heterogeneous networks

ABSTRACT

We consider optimal control for general networks with both wireless and wireline components and time varying channels. A dynamic strategy is developed to support all traffic whenever possible, and to make optimally fair decisions about which data to serve when inputs exceed network capacity. The strategy is decoupled into separate algorithms for flow control, routing, and resource allocation, and allows each user to make decisions independent of the actions of others. The combined strategy is shown to yield data rates that are arbitrarily close to the optimal operating point achieved when all network controllers are coordinated and have perfect knowledge of future events. The cost of approaching this fair operating point is an end-to-end delay increase for data that is served by the network.

REFERENCES

• 1: Michael J. Neely , Eytan Modiano, Dynamic power allocation and routing for satellite and wireless networks with time varying channels, Massachusetts Institute of Technology, 2003
• 2: [2] M. J. Neely, E. Modiano, and C. Li, "Fairness and optimal stochastic control for heterogeneous networks," in IEEE INFOCOM, Mar. 2005.
• 3: [3] M. J. Neely, "Energy optimal control for time varying wireless networks," in Proc. IEEE INFOCOM, Mar. 2005.
• 4: Leonidas Georgiadis , Michael J. Neely , Leandros Tassiulas, Resource allocation and cross-layer control in wireless networks, Foundations and Trends® in Networking, v.1 n.1, p.1-144, April 2006 [doi>10.1561/1300000001]
• 5: [5] J. W. Lee, R. R. Mazumdar, and N. B. Shroff, "Downlink power allocation for multi-class CDMA wireless networks," in Proc. IEEE INFOCOM , 2002.
• 6: [6] R. Berry, P. Liu, and M. Honig, "Design and analysis of downlink utility-based schedulers," in Proc. 40th Allerton Conf. Communication, Control, and Computing, Oct. 2002.
• 7: [7] P. Marbach and R. Berry, "Downlink resource allocation and pricing for wireless networks," in Proc. IEEE INFOCOM, 2002.
• 8: [8] M. Chiang, "Balancing transport and physical layer in wireless multihop networks: Jointly optimal congestion control and power control," IEEE J. Sel. Area Commun., vol. 1, no. 23, pp. 104-116, Jan. 2005.
• 9: [9] L. Xiao, M. Johansson, and S. Boyd, "Simultaneous routing and resource allocation for wireless networks," in Proc. 39th Allerton Conf. Communication, Control, and Computing, Oct. 2001.
• 10: [10] B. Krishnamachari and F. Ordonez, "Analysis of energy-efficient, fair routing in wireless sensor networks through non-linear optimization," in IEEE Vehicular Technology Conf., Oct. 2003.
• 11: [11] P. Marbach, "Priority service and max-min fairness," in Proc. IEEE INFOCOM, 2002.
• 12: [12] F. Kelly, "Charging and rate control for elastic traffic," Eur. Trans. Telecommun., vol. 8, pp. 33-37, 1997.
• 13: [13] F. P. Kelly, A. Maulloo, and D. Tan, "Rate control for communication networks: Shadow prices, proportional fairness, and stability," J. Oper. Res. Soc., vol. 49, pp. 237-252, 1998.
• 14: Steven H. Low , David E. Lapsley, Optimization flow control—I: basic algorithm and convergence, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.861-874, Dec. 1999 [doi>10.1109/90.811451]
• 15: [15] X. Lin and N. B. Shroff, "The impact of imperfect scheduling on cross-layer rate control in wireless networks," in Proc. IEEE INFOCOM, 2005.
• 16: [16] B. A. Movsichoff, C. M. Lagoa, and H. Che, "Decentralized optimal traffic engineering in connectionless networks," IEEE J. Sel. Areas Commun., vol. 23, no. 2, pp. 293-303, Feb. 2005.
• 17: Steven H. Low, A duality model of TCP and queue management algorithms, IEEE/ACM Transactions on Networking (TON), v.11 n.4, p.525-536, August 2003 [doi>10.1109/TNET.2003.815297]
• 18: Xin Liu , Edwin K. P. Chong , Ness B. Shroff, A framework for opportunistic scheduling in wireless networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.41 n.4, p.451-474, 15 March 2003 [doi>10.1016/S1389-1286(02)00401-2]
• 19: [19] R. Cruz and A. Santhanam, "Optimal routing, link scheduling, and power control in multi-hop wireless networks," in Proc. IEEE INFOCOM , Apr. 2003.
• 20: [20] L. Tassiulas and A. Ephremides, "Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks," IEEE Trans. Autom. Contr., vol. 37, no. 12, pp. 1936-1949, Dec. 1992.
• 21: [21] L. Tassiulas and A. Ephremides, "Dynamic server allocation to parallel queues with randomly varying connectivity," IEEE Trans. Inf. Theory, vol. 39, pp. 466-478, Mar. 1993.
• 22: [22] P. R. Kumar and S. P. Meyn, "Stability of queueing networks and scheduling policies," IEEE Trans. Autom. Contr., vol. 40, no. 2, pp. 251-260, Feb. 1995.
• 23: [23] N. McKeown, V. Anantharam, and J. Walrand, "Achieving 100% throughput in an input-queued switch," in IEEE INFOCOM, 1996.
• 24: Nabil Kahale , Paul E. Wright, Dynamic Global Packet Routing in Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1414, April 09-11, 1997
• 25: [25] M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, and P. Whiting, "Providing quality of service over a shared wireless link," IEEE Commun. Mag., vol. 39, no. 2, pp. 150-154, Feb. 2001.
• 26: [26] E. Leonardi, M. Mellia, F. Neri, and M. A. Marsan, "Bounds on average delays and queue size averages and variances in input-queued cell-based switches," in Proc. IEEE INFOCOM, 2001.
• 27: 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]
• 28: [28] M. J. Neely, E. Modiano, and C. E. Rohrs, "Dynamic power allocation and routing for time varying wireless networks," IEEE J. Sel. Areas Commun., vol. 23, no. 1, pp. 89-103, Jan. 2005.
• 29: [29] A. Eryilmaz and R. Srikant, "Fair resource allocation in wireless networks using queue-length-based scheduling and congestion control," in Proc. IEEE INFOCOM, Mar. 2005.
• 30: [30] S. Borst, "User-level performance of channel-aware scheduling algorithms in wireless data networks," in Proc. IEEE INFOCOM, 2003.
• 31: [31] D. N. Tse, "Optimal power allocation over parallel broadcast channels," in Proc. Int. Symp. Information Theory (ISIT), Jun. 1997.
• 32: [32] H. Kushner and P. Whiting, "Asymptotic properties of proportional-fair sharing algorithms," in Proc. 40th Allerton Conf. Communication, Control, and Computing, 2002.
• 33: [33] V. Tsibonis, L. Georgiadis, and L. Tassiulas, "Exploiting wireless channel state information for throughput maximization," in Proc. IEEE INFOCOM, Apr. 2003.
• 34: [34] L. Li and A. Goldsmith, "Capacity and optimal resource allocation for fading broadcast channels: Part i: Ergodic capacity," IEEE Trans. Inf. Theory, pp. 1083-1102, Mar. 2001.
• 35: Alexander L. Stolyar, Maximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual Algorithm, Queueing Systems: Theory and Applications, v.50 n.4, p.401-457, August 2005 [doi>10.1007/s11134-005-1450-0]
• 36: [36] J. W. Lee, R. R. Mazumdar, and N. B. Shroff, "Opportunistic power scheduling for dynamic multiserver wireless systems," IEEE Trans. Wireless Commun., vol. 5, no. 6, pp. 1506-1515, Jun. 2006.
• 37: [37] P. Kall and S. W. Wallace, Stochastic Programming. New York: Wiley, 1994.
• 38: [38] M. J. Neely, "Super-fast delay tradeoffs for utility optimal fair scheduling in wireless networks," IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 1489-1501, Aug. 2006.
• 39: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 40: [40] D. Shah and M. Kopikare, "Delay bounds for approximate maximum weight matching algorithms for input queued switches," in Proc. IEEE INFOCOM, Jun. 2002.
• 41: [41] M. J. Neely, E. Modiano, and C. E. Rohrs, "Tradeoffs in delay guarantees and computation complexity for n × n packet switches," in Proc. Conf. Inf. Sci. Syst. (CISS), Princeton, NJ, Mar. 2002.
• 42: [42] X. Wu and R. Srikant, "Regulated maximal matching: A distributed scheduling algorithm for multi-hop wireless networks with node-exclusive spectrum sharing," in Proc. IEEE Conf. Decision Contr., 2005.
• 43: [43] P. Chaporkar, K. Kar, and S. Sarkar, "Throughput guarantees through maximal scheduling in wireless networks," in Proc. 43rd Allerton Conf. Communication, Control and Computing, Sep. 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Stochastic programming
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

General Terms:
Algorithms, Design, Management

Keywords:
distributed computing, flow control, queueing analysis, satellite networks, stochastic optimization, wireless networks