Article

Free access

Downlink scheduling in CDMA data networks

Authors:

Niranjan Joshi,

Srinivas R. Kadaba,

Ganapathy S. SundaramAuthors Info & Claims

MobiCom '00: Proceedings of the 6th annual international conference on Mobile computing and networking

Pages 179 - 190

https://doi.org/10.1145/345910.345941

Published: 01 August 2000 Publication History

Abstract

Packet data is expected to dominate third generation wireless networks, unlike current generation voice networks. This opens up new and interesting problems. Physical and link layer issues have been studied extensively, while resource allocation and scheduling issues have not been addressed satisfactorily.

In this work, we address resource management on the downlink of CDMA packet data networks. Network performance (for example, capacity) has been addressed, but user centric performance has not received much attention. Recently, various non-traditional scheduling schemes based on new metrics have been proposed, and target user performance (mostly without reference to wireless). We adapt these metrics to the CDMA context, and establish some new results for the offline scheduling problem. In addition, we modify a large class of online algorithms to work in our setup and conduct a wide range of experiments. Based on detailed simulations, we infer that:

Algorithms which exploit “request sizes” seem to outperform those that do not. Among these, algorithms that also exploit channel conditions provide significantly higher network throughput.

Depending on continuous or discretized bandwidth conditions, either pure time multiplexing or a combination of time and code multiplexing strikes an excellent balance between user satisfaction and network performance.

Discrete bandwidth conditions can lead to degraded user level performance without much impact on network performance. We argue that the discretization needs to be fine tuned to address this shortcoming.

References

[1]

3GPP. http://~.3~p.org.

[2]

A. Bakre and B. R. Badrinath. I-TCP: Indirect TCP for Mobile Hosts. Technical Report TR-314, Dept. Comp. $ci., Rutgers Univ., '94.

[3]

A. J. Viterbi. CDMA: Principles o/Spread Spectrum Communication. Addison-Wesley, '95.

Digital Library

[4]

A. V. Goldberg and R. E. Tarjan. A New Approach to the Maximum Flow Problem. J. A CM, pages 921-940, '88.

Digital Library

[5]

B. Mah. An Empirical Model of HTTP Network Traffic. In Proc. IEEE INFOCOM, japan, Apr. '97.

Digital Library

[6]

B. Zenel and D. Duchamp. A General Purpose Proxy Filtering Mechanism Applied to the Mobile Environment. in Proc. MobiCom, Hungary, Sept. '97.

Digital Library

[7]

D. Karger, C. Stein, and J. Wein. Handbook of Algorithms and Theory of Computation, chapter Scheduling Algorithms. CRC Press, '99.

[8]

G. Montenegro, S. Dawkins, M. Kojo, V. Magret and N. Vaidya. Long Thin Networks. IETF Draft at http://~.ww, ietf. org/, May '99.

Digital Library

[9]

Hari Balakrishnan, Srinivasan Seshan, and Randy H. Katz. Improving Reliable Transport and Handoff Performance in Cellular Wireless Networks. A CM Wireless Networks, Dec. '95.

Digital Library

[10]

j. E. Gehrke, S. Muthukrishnan, R. Rajaraman, and A. Shaheen. Scheduling to Minimize Average Stretch. Technical Report 99-2, DIMACS, Rutgers Univ., '99.

[11]

K. Kumaran and P. Whiting. Rate Processor Sharing: A Robust Technique for Scheduling Downlink Data Transmissions in CDMA Wireless. Technical Report BL0112120-990809-17TM, Bell Labs, '99.

[12]

K. Ratnam and I. Matta. WTCP: An Efficient Transmission Control Protocol for Networks with Wireless Links. Technical Report NU-CCS-97-11, Northeastern Univ., July '97.

[13]

K. Thompson, G. Miller, and R. Wilder. Wide-Area Internet Traffic Patterns and Characteristics. IEEE Network, Nov./Dec. '97.

Digital Library

[14]

M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, and P. Whiting. Data Rate Scheduling Algorithms and Capacity Estimates for CDMA Forward Link. Technical Report BL0112120-990922-32TM, Bell Labs, '99.

[15]

M. Bender, S. Chakraborti, and S. Muthukrishnan. Flow and Stretch Metrics for Scheduling Continuous Job Streams. In Proc. IX Ann. A CM-SIAM Syrup. Discrete Algorithms, pages 270-279, San Francisco, CA, Jan. '98.

Digital Library

[16]

M. E. Crovella. R. Frangioso and M. Harchol-Balter. Connection Scheduling in Web Servers. In Proc. {ISENIX Syrup. Internet Technologies and Systems, Boulder, CO, Oct. '99.

Digital Library

[17]

M. Harchol-Balter, M. Crovella, and C. Murta. The Case for SRPT Scheduling in Web Servers. Technical Report MIT-LCS-TR-767, LCS, MIT, Oct. '98.

[18]

M. Liljberg, H. Helin, M. Kojo, and K. Raatikainen. Enhanced Services for World-Wide Web in Mobile WAN Environment. Technical Report C-1996-28, Dept. Comp. Sci., Univ. Helsinki, Finland, '96.

[19]

M. R. Garey and D. S. Johnson. Computers and Intractability: A guide to the Theory of NP-Completeness. W. H. Freeman and Co., '79.

Digital Library

[20]

NLANR. h~tp://~, ircache, nlanr, net.

[21]

P. Barford and M. Crovella. Generating Representative Web Workloads for Network and Server Performance Evaluation. In Proc. ACM $IGMETRiCS, pages 151-160, July '98.

Digital Library

[22]

P. Sarath Kumar and Sanjiv Nanda. High Data Rate Packet Communications for Cellular Networks using CDMA: Algorithms and Performance. IEEE JSA C, pages 472-492, Mar. '99.

Digital Library

[23]

S. Acharya, S. Muthukrishnan, and G. Sundaram. Scheduling Data Delivery Over Multiple Channels. Technical Report., Bell Labs, '99.

[24]

S. Lu, V. Bharghavan, and R. Srikant. Fair Scheduling in Wireless Packet Networks. IEEE/A CM Trans. Networking, pages 473-489, Aug. '99.

Digital Library

[25]

S. Lundby. Forward Multi-Carrier Link Level Results: IMT-2000 A and B Models, Supplemental Channel. In TIA, TR45.5.4 Standards, Mar. '98.

[26]

S. Ramakrishna. Optimal Scheduling of CDMA Systems. PhD thesis, WlNLAB, Rutgers Univ., '98.

[27]

TIA/IS-2000.2. TR45.5. Physical Layer Standard for cdma~O00 Spread Spectrum Systems, Sept. '99.

[28]

W. Willinger and V. Paxson. Where Mathematics Meets the Internet. Notices of the AMS, pages 961-970, Sept. '98.

[29]

Y. Lu and R. W.Brodersen. Integrating Power Control, Error Correction Coding, and Scheduling for a CDMA Downlink System. IEEE JSA C, pages 978-989, June '99.

Digital Library

Cited By

Sevindik VBayat OWeitzen JBiaz SWu S(2011)Performance analysis and simulation of packet scheduling algorithms in a femtocell environmentProceedings of the 44th Annual Simulation Symposium10.5555/2048370.2048383(95-99)Online publication date: 3-Apr-2011
https://dl.acm.org/doi/10.5555/2048370.2048383
SEVINDIK VBAYAT O(2011)Packet Scheduling and Traffic Differentiation in Femtocell EnvironmentIEICE Transactions on Communications10.1587/transcom.E94.B.3018E94-B:11(3018-3025)Online publication date: 2011
https://doi.org/10.1587/transcom.E94.B.3018
Sevindik VBayat OWeitzen J(2011)Radio resource management and packet scheduling in femtocell networks2011 International Symposium of Modeling and Optimization of Mobile, Ad Hoc, and Wireless Networks10.1109/WIOPT.2011.5930058(428-433)Online publication date: May-2011
https://doi.org/10.1109/WIOPT.2011.5930058
Show More Cited By

Index Terms

Recommendations

Interference Cancellation with Space Diversity for Downlink MC-CDMA Systems

Modern wireless communications require an efficient spectrum usage and high channel capacity and throughput. Multiple-input and multiple-output (MIMO), Linear equalizers, multi-user detection and multicarrier code-division multiple access (MC-CDMA) are ...
Multicarrier block-spread CDMA for broadband cellular downlink

Effective suppression of multiuser interference (MUI) and mitigation of frequency-selective fading effects within the complexity constraints of the mobile constitute major challenges for broadband cellular downlink transceiver design. Existing wideband ...
Downlink Specific Linear Equalization for Frequency Selective CDMA Cellular Systems

We derive and compare several linear equalizers for the CDMA downlink under frequency selective multipath conditions: minimum mean-square error (MMSE), zero-forcing (ZF), and RAKE. MMSE and ZF equalizers are designed based on perfect knowledge of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiCom '00: Proceedings of the 6th annual international conference on Mobile computing and networking

August 2000

300 pages

ISBN:1581131976

DOI:10.1145/345910

Chairmen:
Raymond Pickholtz
George Washington Univ., Washington, DC
,
Sajal K. Das
Univ. of Texas at Arlington, Arlington
,
Ramon Caceres
AT&T Labs
,
J. J. Garcia-Luna-Aceves
Univ. of California, Santa Cruz, Santa Cruz

Copyright © 2000 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation
SIGCOMM: ACM Special Interest Group on Data Communication
SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing
IEICE: Inst of Electronics, Info & Communication Engineers
IFIP WG 6.3: IFIP WG 6.3

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

MobiCom00

Sponsor:

SIGMETRICS
SIGCOMM
SIGMOBILE
IEICE
IFIP WG 6.3

MobiCom00: The 6th Annual International Conference on Mobile Computing and Networking

August 6 - 11, 2000

Massachusetts, Boston, USA

Acceptance Rates

MobiCom '00 Paper Acceptance Rate 28 of 226 submissions, 12%;

Overall Acceptance Rate 440 of 2,972 submissions, 15%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

66
Total Citations
View Citations
1,408
Total Downloads

Downloads (Last 12 months)103
Downloads (Last 6 weeks)25

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sevindik VBayat OWeitzen JBiaz SWu S(2011)Performance analysis and simulation of packet scheduling algorithms in a femtocell environmentProceedings of the 44th Annual Simulation Symposium10.5555/2048370.2048383(95-99)Online publication date: 3-Apr-2011
https://dl.acm.org/doi/10.5555/2048370.2048383
SEVINDIK VBAYAT O(2011)Packet Scheduling and Traffic Differentiation in Femtocell EnvironmentIEICE Transactions on Communications10.1587/transcom.E94.B.3018E94-B:11(3018-3025)Online publication date: 2011
https://doi.org/10.1587/transcom.E94.B.3018
Sevindik VBayat OWeitzen J(2011)Radio resource management and packet scheduling in femtocell networks2011 International Symposium of Modeling and Optimization of Mobile, Ad Hoc, and Wireless Networks10.1109/WIOPT.2011.5930058(428-433)Online publication date: May-2011
https://doi.org/10.1109/WIOPT.2011.5930058
Li K(2011)Downlink data transmission scheduling algorithms in wireless networksSimulation Modelling Practice and Theory10.1016/j.simpat.2010.11.01019:6(1427-1444)Online publication date: Jun-2011
https://doi.org/10.1016/j.simpat.2010.11.010
Luton GMakké RMueckenheim JTreillard P(2011)Support of mobile TV over an HSPA networkBell Labs Technical Journal10.1002/bltj.2050816:2(153-168)Online publication date: 1-Sep-2011
https://dl.acm.org/doi/10.1002/bltj.20508
Choi BKim JBeard C(2010)QoS and Channel-Aware Packet Bundling for Capacity Improvement in Cellular NetworksIEEE Transactions on Vehicular Technology10.1109/TVT.2010.206220259:8(3886-3901)Online publication date: Oct-2010
https://doi.org/10.1109/TVT.2010.2062202
Li K(2010)Power assignment and transmission scheduling in wireless networks2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW)10.1109/IPDPSW.2010.5470777(1-8)Online publication date: Apr-2010
https://doi.org/10.1109/IPDPSW.2010.5470777
Wu GAnpalagan A(2010)A Coordinated Location-dependent Downlink Scheduling Scheme in Cellular TD-CDMA Networks with Partitioned CellsWireless Personal Communications: An International Journal10.1007/s11277-009-9680-953:4(481-502)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.1007/s11277-009-9680-9
Tzeng SLu H(2010)QoS provisioning for multiple non-real-time services in cellular wireless networksWireless Communications and Mobile Computing10.1002/wcm.93611:10(1392-1405)Online publication date: 10-Feb-2010
https://doi.org/10.1002/wcm.936
Chan MRamjee R(2008)Improving TCP/IP Performance over Third-Generation Wireless NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2007.707377:4(430-443)Online publication date: 1-Apr-2008
https://dl.acm.org/doi/10.1109/TMC.2007.70737
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten