臺灣博碩士論文加值系統

網際網路的資料流量隨著電子商務、多媒體資訊傳輸及大量檔案下載等應用呈現大幅的成長，瞬間大量的資料傳輸影響了企業網路的使用效能。為滿足不同的服務品質(Quality of Service，QoS)，網際網路工程工作小組(Internet Engineering Task Force，IETF)發展出兩種網路架構，也就是整合性服務(integrated services，IntServ)及差異性服務(differentiated services，DiffServ)。由於在多媒體的通訊網路中訊務間的服務品質需求不同，我們必須運用一些服務品質控制及排程法則的機制。藉由這些機制，使得網路能依據訊務的連結或類別不同，而提供不同等級的服務。靜態的排程法則容易實作，卻不善於處理猝發的訊務。而動態的排程法則，雖然可隨網路狀態變動而調整，但計算的複雜度卻較高。因此，我們得綜合靜、動態兩者優點，來有效的管理網路訊務的傳送。本論文中，我們提出二種排程法則運用於變動封包長度的網路中，一為靜態排程，而另一為類動態(quasi-dynamic)排程。首先，為資料塊基礎的結轉儲存循環法則(DCORR)，其服務週期具有主要週期及次要週期兩部分，而服務權重亦具有結轉儲存功能。第二種是，截止期限調變之權重式循環法則(DMWRR)，為達到較低的計算複雜度及良好的延遲表現，因此以權重式循環方式為基礎，配合延遲保證(delay guarantee)及虛擬時鐘之虛擬延遲時間(virtual Delay Time，VDT)來調整權重。由於數學分析複雜，以上所提的二種方法，均以模擬方式來驗證可以達到預期的表現。

Owing to the electronic commerce, multimedia information, and lots of file-download, the traffic in the Internet make much progress. The instant huge data transmission impacts the efficiency of enterprise networks. For satisfying different quality of service (QoS) requirements, IETF has developed two different network architectures, namely integrated services (IntServ) and differentiated services (DiffServ). Due to difference of requirements of QoS in multimedia communication networks, it needs to apply some mechanisms of QoS control and schedulers to the networks. With these mechanisms, the networks can offer different levels of services according to different connections or different types of traffic. However, a static scheduler is easily implemented but poor in tackling burstiness, and a dynamic scheduler is adaptive to network status but complex in computation. Thus, we will adopt the good performance of dynamic scheduling schemes and the simplicity of static scheduling schemes to the traffic transmission in the networks efficiently manage. In this thesis, there are two scheduling schemes proposed for packets of non-fixed sizes. One is static scheduler and the other is quasi-dynamic scheduler. First of all, the Datagram-Based Carry-Over Round Robin (DCORR) was proposed. Its service cycle can be divided into two subcycles: a major cycle and a minor cycle, and the service weight remained due to lack of arrival packets can be carried over into the next cycle. Secondly, the Deadline Modulating Weight Round Robin (DMWRR) was proposed. The DMWRR combines WRR and the concept of deadline and VC-VFT for low computation complication and better delay performance. Owing to the complication of these scheduling schemes, DCORR and DMWRR are examined by simulations, which show that the performance can meet the requirement as expected.

中文摘要……………………………………………………………………… i
英文摘要…………………………………………………………………… iii
誌謝…………………………………………………………………………… v
目錄……………………………………………………………………………vi
圖目錄………………………………………………………………………viii
表目錄…………………………………………………………………………xi
第一章 序論………………………………………………………………… 1
1.1 研究背景…………………………………………………………………1
1.2 研究動機與方向…………………………………………………………2
1.3 論文架構…………………………………………………………………3
第二章 相關研究討論……………………………………………………… 4
2.1 網際網路通訊協定(IP)服務架構之簡介………………………………4
2.1.1 整合性服務……………………………………………………………4
2.1.2 差別性服務……………………………………………………………5
2.2 排程法則簡介……………………………………………………………7
2.2.1 靜態排程法則概觀……………………………………………………7
2.2.2 動態排程法則概觀……………………………………………………9
第三章 結轉儲存循環法則(CORR)…………………………………………11
3.1 簡介…………………………………………………………………… 11
3.2 結轉儲存循環法則…………………………………………………… 12
3.2.1 服務權重值的分配………………………………………………… 12
3.2.2 訊胞基礎的結轉儲存循環法則…………………………………… 13
3.2.3 資料塊基礎的結轉儲存循環法則………………………………… 15
3.3 結轉儲存循環法則結合訊務整形…………………………………… 22
3.4 數值模擬結果………………………………………………………… 25
3.4.1 ON-OFF訊務模型…………………………………………………… 25
3.4.2 模擬系統之參數值………………………………………………… 28
3.4.3 模擬結果與探討…………………………………………………… 29
3.5 結論…………………………………………………………………… 51
第四章 截止期限調變之權重式循環法則(DMWRR)……………………… 53
4.1 簡介…………………………………………………………………… 53
4.2 相關背景……………………………………………………………… 55
4.2.1 最早截止者優先…………………………………………………… 55
4.2.2 虛擬時鐘之虛擬完成時間………………………………………… 55
4.3 截止期限調變之權重式循環法則…………………………………… 57
4.3.1 截止期限和虛擬時鐘之虛擬完成時間…………………………… 58
4.3.2 服務權重值的重新分配…………………………………………… 59
4.4 數值模擬結果………………………………………………………… 68
4.4.1 模擬結果與探討…………………………………………………… 68
4.5 結論…………………………………………………………………… 84
第五章 總結：相關討論與未來方向………………………………………85
參考文獻………………………………………………………………………87

[1] Hui Zhang, “Service disciplines for guaranteed performance service in packet-switching networks,” Proceedings of the IEEE Volume: 83 10 , Oct. 1995 , Page(s): 1374-1396.
[2] R. Braden, D. Clark, and S. Shenker, “Integrated services in the Internet architecture: an overview,” Internet RFC 1633, June 1994.
[3] S. Blake, D. Blake, M. Carlson, E. Davies, Z. Wang, and W. Weiss, “An architecture for differentiated services,” Internet RFC 2475, Dec. 1998.
[4] H. Shimonishi and H. Sluzuki, “Performance analysis of weighted round robin cell scheduling and its improvement in ATM networks,” IEICE Trans. Comm., vol. E81-B, no. 5, pp. 910-918, May 1998.
[5] Wang, J.; Levy, Y., “Managing performance using weighted round-robin,” Computers and Communications, 2000. Proceedings. ISCC 2000. Fifth IEEE Symposium on , 2000, Page(s): 785-792.
[6] H. Yokota, M. Forsberg, and T. Asami, “Extension to Weighted Round Robin Packet Scheduling for Variable-length Packet Networks,” IEICE Trans. Inf. & Syst., vol. E82-D, no. 3, pp. 668-676, March, 1999.
[7] Shreedhar, M.; Varghese, G., “Efficient fair queuing using deficit round-robin,” Networking, IEEE/ACM Transactions on, Volume: 4 Issue: 3, June 1996, Page(s): 375-385.
[8] Kanhere, S.S.; Sethu, H., “Fair, efficient and low-latency packet scheduling using nested deficit round robin,” High Performance Switching and Routing, 2001 IEEE Workshop on , 2001, Page(s): 6-10.
[9] Saha, D.; Mukherjee, S.; Tripathi, S.K., “Carry-over round robin: a simple cell scheduling mechanism for ATM networks,” INFOCOM ''96. Fifteenth Annual Joint Conference of the IEEE Computer Societies. Networking the Next Generation., Proceedings IEEE , Volume: 2 , 1996, Page(s): 630 -637 vol.2.
[10] Saha, D.; Mukherjee, S.; Tripathi, S.K., “Carry-over round robin: a simple cell scheduling mechanism for ATM networks,” Networking, IEEE/ACM Transactions on, Volume: 6 Issue: 6, Dec. 1998, Page(s): 779-796.
[11] R. Garg and X. Chen, “RRR: recursive round robin scheduler,” Computer Networks, vol. 31, issue 18, pp. 1951-1966, Aug. 1999.
[12] M. Katevenis, S. Sidiropoulos, and C. Courcoubetis, “Weighted round-robin cell multiplexing in a general-purpose ATM switch chip,” IEEE Journal on Selected Areas in Communications, vol. 9 8, pp.1265-1279, Oct. 1991.
[13] L. Zhang, “VirtualClock: A new traffic control algorithm for packet-switched networks,” ACM Trans. Comp. Sys., vol. 9, no. 2, pp. 101-124, May 1991.
[14] C. L. Liu, James W. Layland, “Scheduling algorithms for multiprogramming in a hard-real-time environment,” Journal of the ACM, vol.20, no.1, pp.46-61, Jan. 1973.
[15] 蔡英典, “網際網路具服務品質之排程法則,” 義守大學資訊工程研究所碩士論文, 中華民國九十年六月.
[16] Timothy Kwok著, 郭文山譯, “ATM網路概論,” 儒林圖書有限公司, 1999.
[17] David E. McDysan, Darren L. Sphohn著, 呂維毅譯, “ATM網路新世紀,” 和碩科技文化有限公司, 1996.
[18] Larry L. Peterson, Bruce S. Davie著, 潘育群 等譯, “電腦網路,” 東華書局, 民90.
[19] A. Hung, and G. Kesidis, “Bandwidth scheduling for wide-area ATM networks using virtual finishing times,” IEEE/ACM Transactions on Networking, vol. 4, no. 1, pp. 49-54, Feb. 1996.
[20] O. Altintas, Y. Atsumi, and T. Yoshida, “Urgency-based round robin: a new scheduling discipline for packet switching networks,” Proc. IEEE ICC 98, vol. 2, pp. 1179-1184, 1998.
[21] M. H. MacGregor and W. Shi, “Deficits for bursty latency-critical flows: DRR++,” Pro. IEEE ICON 2000, pp. 287 -293, 2000.
[22] H. Zhang and D. Ferrari, “Rate-controlled service discipline,” J. High Speed Networks, vol. 3, no. 4, pp. 389-412, 1994.
[23] 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 Transactions on Networking, vol. 2, no. 2, pp. 137--150, Apr. 1994.
[24] J. C. R. Bennett and H. Zhang, "WF2Q: Worst-case fair weighted fair queueing," Proc. IEEE Infocom''96, pp. 120--128, 1996.