臺灣博碩士論文加值系統

在一次探討網際網路路由協定與資源預留訊號協定分開發展時它們之間的相互關係時，我們發現當要將整個網路上資源的整體效益和使用率提昇時，則資源預留訊號協定必須結合底層的路由協定來考慮。在此篇論文之中，一個品質保證的群播的路由和資源預留協定 ( MQRP ) 被提出。MQRP 協定整合了資源預留訊號協定和一個連結狀態的路由協定 ( link-state routing protocol ) ，此協定可以對優先權有差別的群播服務保證其點對點的時間延遲限制。而且 MQRP 協定可以允許每一個接收者對他有興趣的資料流來設定優先權值及可容許的點對點時間延遲限制，並保證接收者可在時間延遲限制內收到資料。為了要能夠保證服務的品質，則需要保證每一條連線 ( 資料流 ) 所提出的要求，這些要求包含最大的時間延遲、時間延遲的差異量和對頻寬的需求等…，而要滿足這些需求，則必須在每一個網路節點上安置一個資料封包遞送排程器。所以，為了使我們所提出的架構能夠達到上述的要求，我們設計了一個排程演算法。我們所提出的排程演算法，希望在公平性及時間延遲的要求限制下，能更有效率將資料流排程，所以我們將 MQRP 和排程的機制整合在一起，如此一來由 MQRP 協定中所得到的排隊等候時間延遲可以被用在排程中以達到最好的情形。在效能的模擬實驗之中，一些已被提出的資源預留協定被我們修改為 "有優先權差別的，時間延遲限制的群播" ( priority-differentiated, delay-bound multicast ) 服務問題，以方便在 "隨機網路" ( random network ) 的架構上與我們所提出的 MQRP 協定來比較。而且，我們也利用了舉例說明及展示實驗的結果，來顯示當所有的效能與 WFQ 相同時，我們所提出的 "保證時間延遲排程演算法" ( Guaranteed-Delay, GD ) 在處理時會先將時間延遲要求較嚴格的資料先處理。

Recapitulating the separated developments of Internet routing and resource reservation signaling protocols, we argue that when it comes to the overall efficiency and utilization of the network resources, the reservation signaling must corporate with the underlying routing protocol. In this thesis, a multicast QoS-based routing and reservation protocol (MQRP) that integrates a resource reservation signaling with a link-state routing protocol to guarantee end-to-end delay bounds for priority-differentiated multicast is presented. The protocol allows each receiver to prioritize its selection on multiple hierarchical layer-encoded media streams and guarantees the user-specified end-to-end delay bounds on the selected streams. For guaranteed quality of service (QoS), it is required some constraints such as maximum delay, delay variation and bandwidth requirement be guaranteed for each connection. The key component to meet these requirement is the packet forwarding scheduler within each network node. In order to provide efficient flow scheduling subject to the fairness and delay constraints, we consider a mechanism in which the MQRP and scheduling are integrated into a framework so that the queueing delay can be taken into the consideration. For performance evaluation, several resource reservation protocols modified for the priority-differentiated, delay-bounded multicast problems are compared to MQRP based on the simulation results on random networks. Examples and simulation result show that while the total performance is equivalent to WFQ, the Guaranteed-Delay algorithm serves the packets with small delay requirement first.

一、 緒論…………………………………………………………………1
二、 優先權差別的時間延遲限制群播服務………………………4
2.1 問題規劃…………………………………………………………4
2.2 協定的概觀………………………………………………………6
2.2.1 協定的狀態變化圖……………………………………………7
2.2.2 RSVP 物件類別…………………………………8
2.3資料封包排程法則的概觀.………………………9
三、 品質群播服務的路由和資源預留協定…………………14
3.1群播資料流特徵和時間延遲模組…………………………… 14
3.1.1群播資料流特徵…………………………………14
3.1.2 時間延遲模型……………………………………16
3.1.3 頻寬分享…………………………………………7
3.2群播樹建立和資源預留演算法…………………………………18
3.3 允入控制和資源分配演算法………………………….21
3.4 資料流的連續性…………………………………………23
3.5 例子：美國西部網路……………………………………26
四、 保證時間延遲的排程……………………………31
4.1 保證時間延遲演算法………………………………………31
4.2 時間延遲和公平性的分析……………………………36
五、 模擬………………………………………………………………………40
5.1 MQRP 效率的分析.……………………………………………………40
5.1.1 RSVP 和群播路由協定的比較…………………………………40
5.1.2 模擬 MQRP 的平台……………………………………………42
5.1.3 資源使用率和擴展性……………………………………………42
5.1.4 增益和頻寬的效率………………………………………………45
5.2 保證時間延遲排程演算法的模擬………………………………………47
5.2.1 交通產生器.…………………………………………………47
5.2.2 模擬實驗的結果……………………………………………49
六、 結論……………………………………………………………………………….54
參考文獻…………………………………………………………………………55
自傳……………………………………………………………………………59

參考資料
[1] Q. Zhu, M. Parsa, and J.J. Garcia-Luna-Aceves, "A Source-Based
Algorithm Delay-Constrained Minimum-Cost Multicasting", in
proceedings of IEEE INFOCOM'95,April 1995. pp.377-385.
[2] G.N. Rouskas, and I.Baldine, "Multicast Routing with End-To-End Delay
and Delay Variation Constrains", IEEE Journal on selected areas in
communications, Vol. 15 , No. 3, April 1997, pp.346-356.
[3] H.F. Salama, D.s. Reeves and Y. Viniotis, "Evaluation of Multicast
Routing Algorithms for Real-Time Communication on High-Speed
Networks", IEEE Journal on selected areas in communications, Vol. 15 ,
No. 3, April 1997, pp.332-345.
[4] N. Shacham and James S. Meditch, "An Algorithm For Optimal Multicast
of Multimedia Stream", in Proceedings of IEEE INFOCOM'94, Vol. 2,
pp.564-586.
[5] V.P. Kompella, J.C. Pasqale, and G.C. Polyzos, "Multicast Routing for
Multimedia Communication", IEEE/ACM Transactions on Networking, 1993.
[6] L. Zhang, S. Deering, D. Estrin, S. Shenker and D. Zappala, "RSVP:A
New Resource ReSer Vation Protocol", IEEE Network, Sept. 1993.
[7] S. Schenker, C. Partridge, and R. Guerin, "Specification of Guaranteed
Quality of Service", IEEE Communications Magazine, May 1997.
[8] D.J. Mitzel, D. Estrin, S Shenker and L. Zhang. , "An Architectural
Comparison of ST-II and RSVP", IEEE 1994.
[9] A. Parekh and R. Gallagher, "A Generalized processor Sharing Approach
to Flow Control - The Single Node Case," IEEE/ACM Trans. Networking,
vol. 1, no. 3, 1993, pp. 366-57.
[10] A. Parekh and R. Gallagher, "A Generalized processor Sharing Approach
to Flow Control - The Multiple Node Case," IEEE/ACM Trans. Networking,
vol. 2, no. 2, 1996, pp. 137-50.
[11] A. Birman, V. Firoiu, R. Guerin and D. Kandlur, "Support for RSVP-based
Services over ATM networks," IEEE Globecom'96, pp. 10-15, 1996.
[12] E. Crawley, R. Nair, B. Rajagopalan, and H. Sandick," A Framework for
QoS-based Routing in the Internet," RFC 2386, August 1998.
[13] A. Demers, S. Keshav, and S. Shenker, "Analysis and Simulation of a
Fair Queueing Algorithm", Internetworking: Research and Experience,
vol.1, no. 1, pp.3-26, October 1990.
[14] N. Ferrari and D. Verma, "A scheme for real time channel establishment
in wide-area networks," IEEE Journal on selected areas in
communications, Vol. 8 , No. 3, pp. 368-379, April 1990.
[15] S. J. Golestani, "A Self-Clocked Fair Queueing Scheme for Broadband
Applications," Proceedings of IEEE INFOCOM'94, pp. 636-646, Toronto,
1994.
[16] J.C.R. Bennett and H. Zhang, " WF2Q : Worst-case fair weighted fair
queueing," Proceedings of IEEE INFOCOM'96, pp. 120-128, San
Francisco, CA, March 1996.
[17] P. Goyal, H.M. Vin, and H. Cheng, " Start-Time Fair Queueing: A
Scheduling Algorithm for Integrated Services Packet Switching
Networks," IEEE/ACM Transaction on Networking, vol. 5, no. 5, pp.
690-704, October 1997.
[18] D. Stiliadis and A. Varma, " Efficient Fair Queueing Algorithms for
Packet-Switched Networks," IEEE/ACM Transactions on Networking, vol.
6, no. 2, pp. 175-185, April 1998.
[19] P. Goyal and H.M. Vin, " Generalized Guaranteed Rate Scheduling
Algorithms: A Framework," IEEE/ACM Transaction on Networking, vol.
5, no. 4, pp. 561-571, August 1997.
[20] D. Stiliadis and A. Varma, " Latency-rate servers: A general model
for analysis of traffic scheduling algorithms," Proceedings of IEEE
INFOCOM'96, pp. 111-119, San Francisco, April 1996.
[21] D. Stiliadis and A. Varma, " Rate-Proportional Servers: A Design
Methodology for Fair Queueing Algorithms," IEEE/ACM Transactions on
Networking, vol. 6, no. 2, pp. 164-174, April 1998.
[22] L. Zhang, " Virtual Clock: A new traffic control algorithm for packet
switching networks," Proceedings of ACM SIGCOMM'90, pp. 19-29,
Philadelphia, PA. September 1990.
[23] Zhang, Z., Sanchez, C., Salkewicz, B., and E. Crawley, "QoS Extensions
to OSPF", Work in Progress.
[24] Zappala, D., Estrin, D., and S. Shenker, "Alternate Path Routing and
Pinning for Interdomain Multicast Routing", USC Computer Science
Technical Report # 97-655 , USC, 1997.
[25] Y. Goto, M. Ohta and K. Araki, "Path QoS Collection for Stable
Hop-by-Hop QoS Routing", Proc. INET '97, June, 1997.
[26] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, W. Weiss, " An
Architecture for Differentiated Services," Internet Draft,
Diffserv, Feb., 1999.
[27] S. Shenker, C. Partridge, and R. Guerin, " Specification of Guaranteed
Quality of Service," RFC 2212, September 1997.
[28] P.P. White, "RSVP and Integrated Services in the Internet: A Tutorial",
IEEE Communications Magazine, May 1997.
[29] S. J. Golestani, " Network Delay Analysis of a Class of Fair Queueing
Algorithms," IEEE Journal on Selected Areas in Communications, vol.
13, No. 6, pp. 1057-1070, August 1995.
[30] J.C.R. Bennett and H. Zhang, " Hierarchical Packet Fair Queueing
Algorithms," IEEE/ACM Transaction on Networking, vol. 5, no. 5, pp.
675-689, October 1997.
[31] N. Shacham and H. Yokota, "Admission Control Algorithms for Multicast
Sessions with Multiple Streams," IEEE Journal on selected areas in
communications, Vol. 15 , No. 3, April 1997, pp.557-566.
[32] B. M. Waxman, "Routing of Multiple Connections," IEEE Journal on
selected areas in communications, Vol. 6, No. 9, December 1988,
pp.1617-1622.
[33] A. Adas, "Traffic models in broadband networks," IEEE Communication
Magazine, pp. 82-89, July, 1997.
[34] S. Jamin, P. B. Danzig, S. J. Shenker and L. Zhang, "A Measurement-Based
Admission Control Algorithm for Integrated Service Packet Networks,"
IEEE/ACM Transactions on Networking, Vol. 5, No. 1, February 1997,
pp.56-70.