臺灣博碩士論文加值系統

本論文提出一個無線網路中的封包排程方法，讓網路服務經營商(network operator)能夠更有彈性地分配網路資源，並且提供服務品質保證。該方法稱為可變式服務曲線(Adaptive Service Curve, ASC)。除了改進效能外，我們特別專注於提出一個嶄新且完整的架構，希望能為這個領域開創新方向。
在此論文中，我們首先定義出一個好的排程者(scheduler)需要提供三種彈性，然後說明ASC如何達到這個要求。第一種彈性，在容易發生傳輸錯誤的無線環境中，ASC能提供傳輸錯誤時反應方式(error resilience)的差別化(differentiation)。更詳細地說，當傳輸錯誤發生時，ASC能讓系統選擇是否繼續傳輸，花多少的資源去傳輸。例如，對傳輸品質不佳的使用者加倍傳輸，將導致整體系統效能降低，另一方面，若只傳輸狀況良好的使用者，系統效能達到最好，但這兩種選擇應該由訊務種類和使用者需求來決定；第二種彈性是以上的反應方式能針對個別使用者量身定做；第三種彈性是在資源分配上，我們提出一個有效的方法讓傳統的服務曲線(service curve)可以在無線環境中正常運作，由於繼承了服務曲線的優點，ASC能在分配資源上很有彈性，例如，傳輸延遲和頻寬可獨立考量，避免過度配置資源(over-allocation)的情形發生。
在技術面，ASC所提出的架構融合了傳輸調變(link adaptation)、彈性化(flexibility)、有效的服務定義模式(traffic characterization model)。此論文的結果顯示ASC能提供無線通訊資源管理完整的解決方案。

This thesis presents a novel wireless scheduling mechanism, called Adaptive Service Curve (ASC). The proposed mechanism increases the flexibility with which network operators can adjust the allocation of resources. We first point out that a good scheduler should exhibit three kinds of flexibility, and then we show the ASC can achieve this goal. First, ASC should be able to differentiate the error resilience requirements due to the impact of location-dependent channel errors in wireless networks. Specifically, ASC can employ link adaptation, enabling a choice to be made between maximizing system throughput and making/wasting more link effort on error-prone channels. Second, the above flexibility is not system-wide. Rather, users can subscribe to different error resilience requirements. ASC utilizes the service curve model that can best meet QoS requirements to provide the third kind of flexibility, and prevents an unacceptable over-allocation of scarce radio resources. Accordingly, a framework is proposed to make the existing service curve model operate effectively in wireless environments. The ASC scheduler combines in a single-framework the three aspects of scheduling, namely, link adaptation, flexibility and a mature traffic characterization model. This design represents a complete solution for wireless resource management.

1. Introduction
1.1. Motivation and Contributions
1.2. Related Work
1.3. Organization
2. Background Information
2.1. System Environments
2.2. Problem Statement
2.2.1. Location-Dependent Channel Errors
2.2.2. Link Adaptation
2.2.3. An Effective and Efficient Model
2.3. Review of the Service Curve
2.3.1 Definition of Service Curv
2.3.2 The Advantages of the Service Curve Approach
3. Adaptive Service Curve Scheduler
3.1. Fair Service Curve Model
3.2. Curve Adaptation for Error Resilience
3.3. Resilience Curve
3.4. Discussion and Applicability
4. Simulation
4.1. Simulation Model
4.2. Simulation Results
5. Conclusions
5.1. Summary of Contributions
5.2. Future Research
References

[1] 3G TS 23.107, “Universal Mobile Telecommunications System (UMTS): QoS Concept and Architecture”, Jan. 2000.
[2] A. Autenrieth and A. Kirstädter, “Provisioning of Differentiated IP Resilience and QoS: An Integrated Approach,” ITG Wksp. “IP in Telekommunikationsnetzen,” Bremen, Germany, Apr. 2001.
[3] A. Autenrieth and A. Kirstädter, “Engineering End-to-End IP Resilience Using Resilience-Differentiated QoS,” IEEE Communications Magazine, Vol. 40, Issue 1, Jan. 2002.
[4] P. Bhagwat, P. Bhttacharya, A. Krishna, and S. Tripathi, “Enhancing Throughput over Wireless LANs Using Channel State Dependent Scheduling,” in Proc. IEEE INFOCOM, Mar. 1996.
[5] S. Bucheli, J. R. Moorman, J. W. Lockwood and S. M. Kang, “Compensation Modeling for QoS Support on a Wireless Network,” in Proc. IEEE GLOBECOM, Dec. 2000.
[6] Y. Cao and O. K. Li, “Scheduling Algorithm in Broad-Band Wireless Networks,” in Proc. The IEEE, 89(1): 76-86, Jan 2001.
[7] D. A. Cekhardt and P. Steenkiste, “Effort-Limited Fair (ELF) Scheduling for Wireless Networks,” in Proc. IEEE INFOCOM, 2000.
[8] Cheng S. Chang, “Performance Guarantees in Communication Networks,” Springer-Verlag, 2000.
[9] Chia S. Chang and K. C. Chen, “Service Curve Proportional Sharing Algorithm for Service-Guaranteed Multiaccess in Integrated-Service Wireless Networks,” in Proc. IEEE VTC, 1999.
[10] R. L. Cruz, “Quality of Service Guarantees in Virtual Circuit Switched Networks,” IEEE J. Select. Areas in Commun., 13: 1048-1056, 1995.
[11] T. S. Eugene Ng, I. Stoica and H. Zhang, “Packet fair Queueing Algorithms for Wireless Networks with Location-Dependent Errors,” in Proc. IEEE INFOCOM, Mar. 1998.
[12] T. S. Eugene Ng, D. C. Stephens, I. Stoica and H. Zhang, “Supporting Best-Effort Traffic with Fair Service Curve,” in Proc. IEEE GLOBECOM, 1999.
[13] T. S. Eugene Ng, D. C. Stephens, I. Stoica and H. Zhang, "Supporting Best-Effort Traffic with Fair Service Curve," Technical Report, CMU-CS-99169, Feb. 2000.
[14] C. Fragouli, V. Sivaraman, and M. Srivastava, “Controlled Multimedia Wireless Link Sharing via Enhanced Class-Based Queuing with Channel-State-Dependent Packet Scheduling,” in Proc. IEEE INFOCOM, 1998.
[15] IEEE Local and Metropolitan Area Network Standards Committee, “Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications,” IEEE Std 802.11-1997, The Institute of Electrical and Electronics Engineers, 1997.
[16] Z. Jiang, L. F. Chang, and N. K. Shankaranarayanan, “Providing Multiple Service Classes for Bursty Data Traffic in Cellular Networks,” in Proc. IEEE INFOCOM, Mar. 2000.
[17] Z. Jiang and N. K. Shankaranarayanan, “Channel Quality Dependent Scheduling for Flexible Wireless Resource Management,” in Proc. IEEE ICC, June 2001.
[18] S. Lu, V. Bharghavan and R. Srikant, “Fair Scheduling in Wireless Packet Networks,” IEEE/ACM Trans. Networking, 7: 473-488, 1999.
[19] S. Lu, T. Nandagopal, and V. Bharghavan, “A Wireless Fair Service Algorithm for Packet Cellular Networks,“ in Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM 98), Oct. 1998.
[20] G. T. Nguyen, R. H. Katz, B. D. Noble, and M. Satyanarayanan, “A Trace-Based Approach for Modeling Wireless Channel Behavior,” in Proc. Winter Simulation Conf., Dec 1996.
[21] A. K. Parekh and R. G. Gallager, “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case,“ IEEE/ACM Trans. Networking, 1: 344-357, June 1993.
[22] A. K. Parekh and R. G. Gallager, “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Multiple-Node Case,“ IEEE/ACM Trans. Networking, 2: 137-150, April 1994.
[23] S. D. Patek, “Service Curves in Data Networks Analysis,” Area Exam Report for the Department of EECS, MIT, Cambridge, MA. 1997.
[24] X. Qiu and J. Chuang, “Link Adaptation in Wireless Data Networks for Throughput Maximization under Retransmissions,” in Proc. IEEE ICC, 1999.
[25] P. Ramanathan and P. Agrawal, “Adapting Packet Fair Queueing Algorithms to Wireless Networks,” in Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM 98), Oct. 1998.
[26] H. Sariowan, R. L. Cruz, and G. C. Polyzos, “SCED: A Generalized Scheduling Policy for Guaranteeing Quality-of-Service,” IEEE/ACM Trans. Networking, 7(5): 669-684, Oct. 1999.
[27] I. Stoica, H. Zhang, and T. S. Eugene Ng, "A Hierarchical Fair Service Curve Algorithm for Link-Sharing, Real-Time and Priority Services," in Proc. ACM SIGCOMM, 1997.
[28] I. Stoica, H. Zhang, and T. S. Eugene Ng, “A Hierarchical Fair Service Curve Algorithm for Link-Sharing, Real-Time and Priority Services,” IEEE/ACM Trans. Networking, 8(2): 185-199, Apr. 2000.