|
 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
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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
|
|
 |
4
|
|
| |
5
|
|
| |
6
|
|
| |
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.
|
| |
9
|
|
| |
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.
|
| |
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
|
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
|
| |
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.
|
| |
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
|
|
| |
20
|
NLANR. h~tp://~, ircache, nlanr, net.
|
| |
21
|
|
| |
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.
|
| |
23
|
S. Acharya, S. Muthukrishnan, and G. Sundaram. Scheduling Data Delivery Over Multiple Channels. Technical Report., Bell Labs, '99.
|
| |
24
|
|
| |
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.
|
CITED BY 14
|
|
|
|
|
|
|
|
L. Becchetti , S. Diggavi , S. Leonardi , A. Marchetti-Spaccamela , S. Muthukrishnan , T. Nandagopal , A. Vitaletti, Parallel scheduling problems in next generation wireless networks, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
|
|
|
|
|
|
|
|
|
Zhengrong Ji , Yi Yang , Junlan Zhou , Mineo Takai , Rajive Bagrodia, Exploiting medium access diversity in rate adaptive wireless LANs, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
C.2