Parallel scheduling problems in next generation wireless networks

ABSTRACT

Next generation 3G/4G wireless data networks allow multiple codes (or channels) to be allocated to a single user, where each code can support multiple data rates. Providing fine-grained QoS to users in such networks poses the two dimensional challenge of assigning both power (rate) and codes for every user. This gives rise to a new class of parallel scheduling problems. We abstract general downlink scheduling problems suitable for proposed next generation wireless data systems. This includes a communication-theoretic model for multirate wireless channels. In addition, while conventional focus has been on throughput maximization, we attempt to optimize the maximum response time of jobs, which is more suitable for stream of user requests. We present provable results on the algorithmic complexity of these scheduling problems. In particular, we are able to provide very simple, online algorithms for approximating the optimal maximum response time. This relies on resource augmented competitive analysis. We also perform an experimental study with realistic data of channel conditions and user requests to show that our algorithms are more accurate than our worst case analysis shows, and they provide fine-grained QoS to users effectively.

REFERENCES

• 1: L. Becchetti, S. Diggavi, S. Leonardi, A. Marchetti-Spaccamela, S. Muthukrishnan, T. Nandagopal, and A. Vitaletti, "Parallel scheduling problems in next generation wireless networks," DIMACS Technical Report \# 2002-29, available from http://dimacs.rutgers.edu/TechnicalReports/, 2002.
• 2: Hari Balakrishnan , Venkata N. Padmanabhan , Srinivasan Seshan , Randy H. Katz, A comparison of mechanisms for improving TCP performance over wireless links, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.756-769, Dec. 1997 [doi>10.1109/90.650137]
• 3: Y. Lu and R W. Brodersen, "Integrating power control, error correction coding, and scheduling for a CDMA downlink system," IEEE Selected Areas in Communications, vol. 17, no. 5, pp. 978--989, May 1999.
• 4: Thyagarajan Nandagopal , Songwu Lu , Vaduvur Bharghavan, A unified architecture for the design and evaluation of wireless fair queueing algorithms, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.132-142, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313520]
• 5: S. Ramakrishna and J M. Holtzman, "A scheme for throughput maximization in a dual-class CDMA system," IEEE Selected Areas in Communications, vol. 16, no. 6, pp. 830--844, August 1998.
• 6: N. Bambos, "Toward power-sensitive network architectures in wireless communications: concepts, issues, and design aspects," IEEE Personal Communications, vol. 5, no. 3, pp. 50--59, June 1998.
• 7: D. Karger, C. Stein, and J. Wein, "Scheduling algorithms," in Algorithms and Theory of Computation Handbook, CRC Press, 1999.
• 8: John Turek , Joel L. Wolf , Philip S. Yu, Approximate algorithms scheduling parallelizable tasks, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.323-332, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141909]
• 9: Walter Ludwig , Prasoon Tiwari, Scheduling malleable and nonmalleable parallel tasks, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.167-176, January 23-25, 1994, Arlington, Virginia, United States
• 10: Klaus Jansen , Lorant Porkolab, Linear-time approximation schemes for scheduling malleable parallel tasks, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.490-498, January 17-19, 1999, Baltimore, Maryland, United States
• 11: John Turek , Walter Ludwig , Joel L. Wolf , Lisa Fleischer , Prasoon Tiwari , Jason Glasgow , Uwe Schwiegelshohn , Philip S. Yu, Scheduling parallelizable tasks to minimize average response time, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.200-209, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181331]
• 12: Renaud Lepère , Denis Trystram , Gerhard J. Woeginger, Approximation Algorithms for Scheduling Malleable Tasks under Precedence Constraints, Proceedings of the 9th Annual European Symposium on Algorithms, p.146-157, August 28-31, 2001
• 13: Swarup Acharya , S. Muthukrishnan, Scheduling on-demand broadcasts: new metrics and algorithms, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.43-54, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288248]
• 14: Niranjan Joshi , Srinivas R. Kadaba , Sarvar Patel , Ganapathy S. Sundaram, Downlink scheduling in CDMA data networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.179-190, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345941]
• 15: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 16: J M. Cioffi, G P. Dudevoir, M V. Eyuboglu, and G D. Forney, "MMSE decision-feedback equalizers and coding: Parts I & II," IEEE Transactions on Communications, vol. 43, no. 10, pp. 2582--2604, Oct. 1995.
• 17: P. Bender, P. Black, M. Grob, R. Padovani, N. Sindhushayana, and A. Viterbi, "CDMA/HDR; A bandwith-efficient high-speed wireless data service for nomadic users," IEEE Communications Magazine, vol. 38, no. 7, pp. 70--77, July 2000.
• 18: S. Nanda, K. Balachandran, and S. Kumar, "Adaptation techniques in wireless packet data services," IEEE Communications Magazine, vol. 38, no. 1, pp. 54--65, January 2000.
• 19: Michael A. Bender , Soumen Chakrabarti , S. Muthukrishnan, Flow and stretch metrics for scheduling continuous job streams, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.270-279, January 25-27, 1998, San Francisco, California, United States
• 20: Soumen Chakrabarti , S. Muthukrishnan, Resource scheduling for parallel database and scientific applications, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.329-335, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237577]
• 21: Hadas Shachnai , John J. Turek, Multiresource malleable task scheduling to minimize response time, Information Processing Letters, v.70 n.1, p.47-52, April 01, 1999 [doi>10.1016/S0020-0190(99)00030-7]
• 22: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 23: B. Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance [scheduling problems], Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.214, October 23-25, 1995
• 24: K.R. Baker, Introduction to Sequencing and Scheduling, Wiley, 1974.
• 25: "LOQO Optimization Toolkit," http://www.orfe.princeton.edu/ loqo, 2000.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.3 Communications Applications

General Terms:
Algorithms