| dc.contributor.advisor | 連耀南 | zh_TW |
| dc.contributor.advisor | Lien,Yao-Nan | en_US |
| dc.contributor.author (Authors) | 溫永全 | zh_TW |
| dc.contributor.author (Authors) | Wen,Yung-Chuan | en_US |
| dc.creator (作者) | 溫永全 | zh_TW |
| dc.creator (作者) | Wen,Yung-Chuan | en_US |
| dc.date (日期) | 2007 | en_US |
| dc.date.accessioned | 11-Sep-2009 16:03:43 (UTC+8) | - |
| dc.date.available | 11-Sep-2009 16:03:43 (UTC+8) | - |
| dc.date.issued (上傳時間) | 11-Sep-2009 16:03:43 (UTC+8) | - |
| dc.identifier (Other Identifiers) | G0094753041 | en_US |
| dc.identifier.uri (URI) | https://nccur.lib.nccu.edu.tw/handle/140.119/29686 | - |
| dc.description (描述) | 碩士 | zh_TW |
| dc.description (描述) | 國立政治大學 | zh_TW |
| dc.description (描述) | 資訊科學學系 | zh_TW |
| dc.description (描述) | 94753041 | zh_TW |
| dc.description (描述) | 96 | zh_TW |
| dc.description.abstract (摘要) | 受到封包網路原本忽略時效性特性之影響，對時效性要求極高的多媒體網路服務，如Voice over IP (VoIP)以及Video on Demand (VoD)在All-IP整合的核心網路上提供時，其服務品質低於傳統之電路交換網路。 封包在網路的傳遞過程中受到各種因素之影響，於到達目的地時，可能會造成long delay time，high jitter或packet loss，而在目的地端幾乎已經沒有補救機會，故而如果能在傳遞的過程中，依封包的時效性及重要性做適度的次序調動(rescheduling)而不要依序傳遞(FIFO)，讓過遲的封包提前送出，而將有時間餘裕的封包稍緩送出，如此截長補短，可提高網路效能及整體QoS滿意度。 我們在BBQ (Budget-Base QoS)的架構下發展一套簡單而有效的方法，在單佇列(Single Preemptive Queue)及多佇列(Multiple FIFO Queue)的router架構下，根據封包時效性及重要性賦予合適的profit function，並參考封包在後續路程上各router的負載狀態以便能更精確預估封包是否能及時到達目的地並調整profit function參數以調整封包的送出順序，如此能提高排程的效能。 我們先對單一服務等級的封包排程進行研究，獲得參數調整之技巧，再根據其結果設計多服務等級的封包排程方法，其重點在於如何調配profit function給不同的服務等級。 我們藉由NS-2模擬模擬器進行實驗，評估本方法的效能，實驗結果顯示我們的方法可以較每個router僅根據自身所知的資訊進行排程更可以有效提高網路效能，且能對不同的服務等級做差異化處理以提高整體QoS滿意度。最後在多等級服務的實驗環境及評估指標下，網路高負載的情況，本方法與Simulated Priority Queue排程演算法比較可以提升34%的整體滿意度。 | zh_TW |
| dc.description.abstract (摘要) | Running time sensitive multimedia services such as Voice-over-IP (VoIP) and Video-on-Demand (VoD) on All-IP networks may have lower quality than that on the traditional circuit-switched networks. Influenced by many factors, packets transported on a packet-switched network, may suffer from long delay time, large jitter and high packet loss rate. When a packet arrives its destination late, there is no way to correct the problem. Thus, it will be beneficial if routers could forward packets base on their timeliness and importance, instead of using First-In-First-Out (FIFO) service plan, giving important late packets proper precedence. The overall QoS satisfaction will be improved significantly. In this thesis, we develop a simple and effective scheduling policy based on this concept for the environments where packets have predefined hop-by-hop time schedule. Routers are assumed in two different queue architectures: ideal Single Preemptive Queue router and practical Multiple FIFO Queue router. To forward a packet, a router first assigns a suitable profit function to the packet based on its timeliness and importance as well as the loading status in its succeeding routers along its predefined traveling path, then inserts the packet into an appropriate position in the output queues. Taking the loading status of succeeding routers into account could predict more accurately whether the packet could reach its destination on time or not. We conduct the research for the single service class environments first to learn the characteristics of this new scheduling policy, and then for the multiple service class environments based on the knowledge acquired. The challenge is to find the best way to assign proper profit functions to different classes of packets in order to utilize resources more wisely, e.g. urgent and important packets get precedence. We evaluate the performance of this approach by simulation using NS-2 network simulator. Simulation results show that our approach outperforms our previous version which doesn`t take the loading status of succeeding routers into account. Furthermore, our approach can outperform the Simulated Priority Queue by at least 34% under heavy load and our evaluation metrics. | en_US |
| dc.description.tableofcontents | 第一章 簡介 1 1.1封包網路上乘載具時效性應用之問題 1 1.2 UMTS資料流類別 2 1.3網路服務品質管理辦法 4 1.4以預算為基礎之服務品質保證 (Budget Based QoS Management) 5 1.4.1以Class區別的服務策略 (Class Based Service Policies) 5 1.4.2以預算為基礎之管理 (Budget Based Management) 5 1.4.3端對端服務品質保證 (End-to-End QoS Management) 6 1.5 Router架構 6 1.6排程演算法 7 1.7研究動機與目的 8 1.8論文架構 8 第二章 相關研究 9 2.1 A New Jitter Control Mechanism by Per-Hop Packet Scheduling Approach 9 2.1.1兩種router架構 9 2.1.2獨立排程演算法 11 2.1.2.1 Single Preemptive Queue獨立排程演算法 (IRS-SPQ) 11 2.1.2.2 Multiple FIFO Queue獨立排程演算法 (IRS-MQ) 12 2.2 A Priority Based Packet Scheduler with Deadline Considerations 12 2.3 Implementation of Expedited Forwarding Using Dynamic Hop Counts Based Absolute Priority Scheduling 12 2.4 Scalable Hardware Priority Queue Architectures for High-Speed Packet Switches 13 2.5評論 13 第三章 前瞻式排程 15 3.1 Objective Function 16 3.2排程整體架構 19 3.3 Profit Function 20 3.4 Scheduling Policy 23 3.5 Priority Multiple Queue router (PMQ) 24 3.5.1 PMQ架構 24 3.6前瞻式排程 (Looking Ahead Scheduling) 25 3.6.1設計理念及目標 26 3.6.2估計後續router負載 26 3.6.3動態調整profit function參數 27 3.7 LAS排程演算法 31 3.7.1演算法流程 32 3.7.2演算法虛擬碼 (Pseudo code) 34 第四章 效能評估 35 4.1實驗環境 35 4.2實驗設計 36 4.2.1實驗步驟 37 4.2.2實驗參數 37 4.3評估指標 38 4.4實驗一：在單一服務等級環境中比較IRS-PMQ與IRS-MQ 38 4.4.1實驗1A：探討負載對效能的影響 39 4.4.1.1實驗目標 39 4.4.1.2實驗流程 39 4.4.1.3實驗結果與分析 39 4.4.2實驗1B：探討路徑長度對效能的影響 41 4.4.2.1實驗目標 41 4.4.2.2實驗流程 41 4.4.2.3實驗結果與分析 42 4.4.3實驗1C：探討queue size對效能的影響 44 4.4.3.1實驗目標 44 4.4.3.2實驗流程 44 4.4.3.3實驗結果與分析 44 4.5實驗二：在單一服務等級環境中比較LAS-PMQ與IRS-PMQ 46 4.5.1實驗2A：探討負載對效能的影響 47 4.5.1.1實驗目標 47 4.5.1.2實驗流程 47 4.5.1.3實驗結果與分析 47 4.5.2實驗2B：探討路徑長度對效能的影響 49 4.5.2.1實驗目標 49 4.5.2.2實驗流程 49 4.5.2.3實驗結果與分析 50 4.5.3實驗2C：探討queue size對效能的影響 52 4.5.3.1實驗目標 52 4.5.3.2實驗流程 52 4.5.3.3實驗結果與分析 52 4.5.4實驗2D：探討他人負載對前瞻式排程效能的影響 54 4.5.4.1實驗目標 54 4.5.4.2實驗流程 55 4.5.4.3實驗結果與分析 56 4.6實驗三：多服務等級效能評估實驗 57 4.6.1實驗3A：探討四種profit function共存的效能表現 58 4.6.1.1實驗目標 58 4.6.1.2實驗流程 58 4.6.1.3實驗結果與分析 58 4.6.2實驗3B：探討雙real-time服務等級共存的效能表現 60 4.6.2.1實驗目標 60 4.6.2.2實驗流程 60 4.6.2.3實驗結果與分析 62 4.7實驗總結 66 第五章 結論與未來研究方向 67 參考文獻 69 | zh_TW |
| dc.language.iso | en_US | - |
| dc.source.uri (資料來源) | http://thesis.lib.nccu.edu.tw/record/#G0094753041 | en_US |
| dc.subject (關鍵詞) | 前瞻式 | zh_TW |
| dc.subject (關鍵詞) | 封包排程 | zh_TW |
| dc.subject (關鍵詞) | 服務品質 | zh_TW |
| dc.subject (關鍵詞) | Looking Ahead | en_US |
| dc.subject (關鍵詞) | packet scheduling | en_US |
| dc.subject (關鍵詞) | QoS | en_US |
| dc.title (題名) | 有助於提高服務品質的前瞻式封包排程機制 | zh_TW |
| dc.title (題名) | QoS-Aware Packet Scheduling by Looking Ahead Approach | en_US |
| dc.type (資料類型) | thesis | en |
| dc.relation.reference (參考文獻) | [1] M. Alam, R. Prasad, and J.R. Farserotu, “Quality of service among IP-based heterogeneous networks,” IEEE Personal Communications, vol. 8, no. 6, pp. 18-24, Dec. 2001. | zh_TW |
| dc.relation.reference (參考文獻) | [2] J.C.R. Bennett, K. Benson, A. Charny, and J.-Y. Le Boudec, “Delay Jitter Bounds and Packet Scale Rate Guarantee for Expedited Forwarding,” IEEE/ACM Transactions on Networking, vol. 10, no. 4, pp. 529-540, Aug. 2002. | zh_TW |
| dc.relation.reference (參考文獻) | [3] J.C.R. Bennett and H. Zhang, “WF2Q : Worst-case Fair Weighted Fair Queueing,” Proc. of INFOCOM, vol. 1, pp.120-128, Mar. 1996. | zh_TW |
| dc.relation.reference (參考文獻) | [4] D. Black, M. Carlson, E. Davies, and Z. Wang, “An Architecture for Differentiated Services,” IETF RFC 2475, Dec. 1998. | zh_TW |
| dc.relation.reference (參考文獻) | [5] M. Claypool and J. Tanner, “The Effects of Jitter on the Perceptual Quality of Video,” Proc. of ACM international conference on Multimedia, pp. 115-118, Nov. 1999. | zh_TW |
| dc.relation.reference (參考文獻) | [6] E. Crawley, Editor, L. Berger, and S. Berson, “A Framework for Integrated Services and RSVP over ATM,” IETF RFC 2382, Aug. 1998. | zh_TW |
| dc.relation.reference (參考文獻) | [7] T. Dag and O. Gokgol, “A Priority Based Packet Scheduler with Deadline Considerations,” Proc. of CNSR, May 2006. | zh_TW |
| dc.relation.reference (參考文獻) | [8] X. Fei, A. Marshall, and J. Luo, “DO-WF2Q: delay-optimized WF2Q packet scheduling,” IEEE Proc. on Communications, vol. 152, no. 5, pp. 655-660, Oct. 2005. | zh_TW |
| dc.relation.reference (參考文獻) | [9] V.K. Garg and O.T.W. Yu, “Integrated QoS support in 3G UMTS networks,” IEEE Wireless Communications and Networking Conference, vol. 3, pp. 1187-1192, Sep. 2000. | zh_TW |
| dc.relation.reference (參考文獻) | [10] Jing-Guo Ge, Ming-Chuan Yang, and Hua-Lin Qian, “Implementation of Expedited Forwarding Using Dynamic Hop Counts Based Absolute Priority Scheduling,” Proc. of ICCT, vol. 1, pp. 324-333, Apr. 2003. | zh_TW |
| dc.relation.reference (參考文獻) | [11] Yong Lee, Jian-Yu Lou, Jun-Zhou Luo, and Xiao-Jun Shen, “An Efficient Packet Scheduling Algorithm With Deadline Guarantees for Input-Queued Switches,” IEEE/ACM Transactions on Networking, vol. 15, no. 1 pp. 212-225, Feb. 2007. | zh_TW |
| dc.relation.reference (參考文獻) | [12] Yao-Nan Lien, Hung-Ching Jang, Tsu-Chieh Tsai, and Hsing Luh, “Budget Based QoS Management Infrastructure for All-IP Networks,” Proc. of ICACT, vol. 1, pp. 185-190, Feb. 2005. | zh_TW |
| dc.relation.reference (參考文獻) | [13] Tsung-Ming Lin, “A New Jitter Control Mechanism by Per-Hop Packet Scheduling Approach,” Master thesis, National Chengchi University, Dec. 2006. | zh_TW |
| dc.relation.reference (參考文獻) | [14] P. Lorenz, “Quality of service and new architectures for future telecommunications networks,” Proc. of MILCOM, vol. 2, pp. 695-698, Oct. 2000. | zh_TW |
| dc.relation.reference (參考文獻) | [15] S.-W. Moon, K.G. Shin, and J. Rexford, “Scalable Hardware Priority Queue Architectures for High-Speed Packet Switches,” Proc. of RTAS, pp. 203-212, Jun. 1997. | zh_TW |
| dc.relation.reference (參考文獻) | [16] R. Pellizzoni and G. Lipari, “Improved schedulability analysis of real-time transactions with earliest deadline scheduling,” Proc. of RTAS, pp. 66-75, Mar. 2005. | zh_TW |
| dc.relation.reference (參考文獻) | [17] I. Stoica and Hui Zhang, “Providing Guaranteed Services Without Per Flow Management,” Proc. of ACM SIGCOMM, vol. 29, no. 4, pp. 81-94, Oct. 1999. | zh_TW |
| dc.relation.reference (參考文獻) | [18] Fu-Ming Tsou, Hong-Bin Chiou, and Zsehong Tsai, “Design and Simulation of an Efficient Real-Time Traffic Scheduler with Jitter and Delay Guarantees,” IEEE Transaction on Multimedia, vol. 2, no. 4, pp. 255-266, Dec. 2000. | zh_TW |
| dc.relation.reference (參考文獻) | [19] Jing-Gang Wang and B. Ravindran, “BPA: A Fast Packet Scheduling Algorithm for Real-Time Switched Ethernet Networks,” Proc. of ICPP, pp. 159-166, 2002. | zh_TW |
| dc.relation.reference (參考文獻) | [20] Chin-Chi Wu, Hsien-Ming Wu, and Woei Lin, “Efficient and Fair Multi-Level Packet Scheduling for Differentiated Services,” Proc. of ISM, Dec. 2005. | zh_TW |
| dc.relation.reference (參考文獻) | [21] Chin-Chi Wu, Hsien-Ming Wu, Chiou Moh, and Woei Lin, “A Hierarchical Packet Scheduler for Differentiated Services in High-Speed Networks,” Proc. of ACIS, pp. 63-68, Jul. 2006. | zh_TW |
| dc.relation.reference (參考文獻) | [22] Yan Xu, Yi-Lin Chang, and Zeng-Ji Liu, “Calculation and Analysis of Compensation Buffer Size in Multimedia Systems,” IEEE Communications Letters, vol. 5, no. 8, pp. 355-357, Aug. 2001. | zh_TW |
| dc.relation.reference (參考文獻) | [23] Lin-Hua Zhong, Jin Xu, and Xian-Lei Wang, “VWQGRR: a Novel Packet Scheduler,” Proc. of ICN, pp. 36-36, Apr. 2007. | zh_TW |
| dc.relation.reference (參考文獻) | [24] 3GPP, “Technical Specification Group Services and Systems Aspects: Architecture for an All IP network,” 3GPP TR 23.922 version 1.0.0., Oct. 1999. | zh_TW |
| dc.relation.reference (參考文獻) | [25] “The Network Simulator - ns-2,” http://www.isi.edu/nsnam/ns/. | zh_TW |
