臺灣博碩士論文加值系統

在網際網路越盛行發展之際，使用者卻越來越不能忍受現今網路品質的不可預期性，許多新的多媒體應用系統，如視訊會議或網路電話，都需要基本服務品質保證方可使用，因此傳統齊頭式平等的盡力傳輸模式(Best-Effort)已不適合未來整合性網路，我們知道許多未來的應用(applications)必須仰賴網路提供傳輸服務品質保證(QoS guarantees)的能力及多種服務類別，以滿足各個不同使用者、應用程式的傳輸需求，這些服務品質的保證通常以下列的型態出現：有上界的端點間傳輸延遲(bounded end-to-end delay)、頻寬(bandwidth)、傳輸延遲的基差(delay jitter)、封包遺失率(packet loss)等，或是上述幾項的組合。因此，如何支援網路傳輸線頻寬共享的理想就日益重要，也就是需要網路能提供機制允許資源的共享可藉由行政考量，通訊協定及其資料型態或其他重要因素分類，且個別給與不同的網路資源或服務品質的保證。
對於資源共享，我們提出一套有彈性的整合性階層性資源共享架構，除了階層性資源共享架構外，還包括優良頻寬管理所應提供的功能，如控制最大傳送速度、預約與週期性保留頻寬，及實作一套易於使用的管理者介面。
對於下層的封包排程器方面，為了達到控制最大傳送速度，我們提出一個新演算法WF2Q-M(WF2Q with Maximum rate control)。WF2Q-M的最大特色是改變WF2Q計算virtual clock，virtual starting time及virtual starting time的方法，將封包的eligible time與WF2Q的virtual starting time結合，因此一個服務類別只需要排程佇列，而不需速度控制器，以降低系統達到最大傳送速度所需成本。故我們只需利用WF2Q會檢查virtual clock是否已大於封包的virtual starting time的特色，就可精確的達到控制最大傳送速度，且同時保有WF2Q逼近GPS的特性。除此之外，我們利用更改系統virtual clock增加的速度來反應出系統內佇列分享到因控制最大傳送速度而產生的剩餘頻寬，並將這個理念推廣到variable rate server系統裡，而不必使用H. Zhang "measured by bits"的方法。

The advent of high-speed networking has introduced new applications such as video conference and voice over IP. These applications have stringent performance requirements in terms of throughputs, delay, delay jitter and loss rate. For corporations, they hope the bandwidth allocation can follows by some polices, e.g. business critical traffic can receive better quality of service then other traffic. Current the best-effort service model is not enough, because the performance of each session can degrade significantly when the network is overloaded, and it handle all traffic equally. When Internet gets more and more popular and powerful, users are less patient with the unpredictable quality of server of Internet. There is an urgent need to provide network services with performance guarantees and to support link sharing, which allows resource sharing among traffic that are grouped according to business-oriented polices, protocol, traffic type, administrative affiliation, and other criteria.
In this work, we propose a hierarchical link sharing architecture and a new scheduling algorithm WF2Q-M. The link sharing architecture include a hierarchical links sharing service model and some good properties of resouce management, e.g. advance and periodic reservation, maximum rate control and a hierarchical Web interface for users. The packet scheduler WF2Q-M can simultaneously support maximum rate control and have good properties of WF2Q. By merging packet's eligible time into its virtual staring time and use WF2Q based algorithms, we can skip the packet regulator in the literatures' service model to support rate control. By changing the ratio of system real clock to virtual clock, WF2Q-M can be properly defined as variable-rate servers.

第一章 緒論............................................1
第一節 研究動機......................................1
第二節　研究目的......................................2
第三節 論文架構......................................3
第二章 文獻探討.........................................4
第一節 Work-Conserving Service Disciplines............4
2.1.1　GPS..........................................4
2.1.2　WFQ及WF2Q....................................6
2.1.3　SCFQ (Self-Clocked Fair Queueing)............9
2.1.4　小結........................................10
第二節 Non-Work-Conserving Service Disciplines.......10
2.2.1　Jitter-Earliest-Due-Date....................11
2.2.2　Stop-and-Go.................................12
2.2.3　Rate-Controlled Static Priority.............13
2.2.4　小結........................................13
第三節 Link Sharing and Resource Management..........14
2.3.1　Link Sharing................................14
2.3.2　Resource Allocation.........................14
2.3.3　Hierarchical link sharing...................16
2.3.4　小結........................................17
第三章 階層式資源共享架構..............................18
第一節　簡介.........................................18
第二節　Organization.................................20
第三節　Router and Interface.........................20
第四節　Agency.......................................21
第五節　Class........................................22
第六節　Bpipe........................................23
第七節　Maximum Rate Control.........................23
第八節　Priority.....................................25
第九節　Advance Reservation..........................26
3.9.1　簡介........................................26
3.9.2　提供的功能..................................27
3.9.3　系統架構及限制..............................30
3.9.4　准許進入控制................................31
第十節　Policy Manager...............................33
3.10.1　動機.......................................33
3.10.2　系統架構...................................34
3.10.3　介面與操作方法.............................35
第四章 WF2Q with maximum rate control..................36
第一節　簡介.........................................36
第二節　系統架構.....................................39
第三節　演算法.......................................41
4.3.1　eligible time...............................41
4.3.2　Resource Allocation.........................42
4.3.3　WF2Q-M use Real Clock.......................44
4.3.4　WF2Q-M use Real Clock and Virtual Clock.....48
第四節　系統特性.....................................59
第五節 Hierarchical WF2Q-M...........................62
4.5.1　virtual clock...............................62
4.5.2　演算法......................................63
第五章 System simulation and evaluation...............68
第一節系統模擬......................................68
5.1.1　模擬及測試環境..............................68
5.1.2　實驗及模擬結果..............................69
5.1.3　小結........................................74
第二節演算法衡量....................................75
5.2.1　優點........................................75
5.2.2　缺點........................................76
5.2.3　Usage.......................................76
第六章 結論...........................................78
參考文獻...............................................80

[1]J. C. R. Bennett and H. Zhang, “WF2Q: worst-case fair weighted fair queueing,” in Proc. IEEE INFOCOM’96, San Francisco, CA, Mar. 1996
[2]J. C. R. Bennett and H. Zhang, “Hierarchical packet fair queueing algorithms,” IEEE/ACM Trans. Networking, vol. 5, pp. 675-689, Oct. 1997.
[3]S. Blake, et. al., “An Architecture for Differentiated Services,” IETF RFC2475, December 1998.
[4]Kenjiro Cho. “A Framework for Alternate Queueing: Towards Traffic Management by PC-UNIX Based Routers” 1998
[5]D. Ferrari and D. Verma. “A scheme for real-time channel establishment in wide-area networks.” IEEE Journal on Selected Areas in Communications, 8(3):368-379, April 1990
[6]S. Floyd and V. Jacobson, “Link-sharing and resource management models for packet networks,” IEEE/ACM Trans. Networking, vol. 3 pp. 365-386, Aug. 1995.
[7]R. Garg, and H.saran, “Fair Bandwidth Sharing Among Virtual Networks: A Capacity Resizing Approach.” INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE , Volume: 1 , 2000 Page(s): 255 -264 vol.1
[8]S. Golestani. “Congestion-free transmission of real time traffic in packet networks.” In Proceedings of IEEE INFOCOM’90, pages 527-542, San Francisco, California, June 1990. IEEE Computer and Communication Societies.
[9]S. Golestani. “A self-clocked fair queeuing scheme for broadband applications.” In Preceedings of IEEE INFOCOM’94, page 636-646, Toronto, CA, Jane 1994
[10]http://www.isi.edu/nsnam/ns/
[11]http://www.pao.lombardiacom.it/wfq.html
[12]J. Heinanen, et. al., “Assured Forwarding PHB Group,” IETF RFC2597, June 1999.
[13]V. Jacobson, et. al., ”An Expedited Forwarding PHB,” IETF RFC2598, June 1999.
[14]K. Nichols et. al., “Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers”, IETF RFC2474, December 1998.
[15]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. 1, No. 3, pp.344-357, June 1993.
[16]O. Schelen,; A. Nilsson; J. Norrgard; S. Pink, “Performance of Qos Agents for Provisioning Network Resources”, Quality of Service, 1999. IWQoS '99. 1999 Seventh International Workshop on , 1999 , Page(s): 17 —26
[17]S. Shenker, C. Partridge and R. Guerin, “Specification of Guaranteed Quality of Service”, IETF RFC 2212, September 1997.
[18]D. Verma, H. Zhang, and D. Ferrari.”Guaranteeing delay jitter bounds in packet switching networks.” In Proceedings of Tricomm’91, pages 35-46, Chapel Hill, North Carolina, April 1991
[19]J. Wroclawski, “The Use of RSVP with IETF Integrated Services”, IETF RFC 2210, September 1997.
[20]J. Wroclawski, “Specification of the Controlled-Load Network Element Service”, IETF RFC 2211, September 1997.
[21]H. Zhang and D. Ferrari. “Rate-controlled static priority queueing.” In Proceedings of IEEE INFOCOM’93, pages 227-236, San Francisco, California, April 1993.
[22]H. Zhang, “Service Disciplines for Guaranteed Performance Service in Packet-Switching Network”, Proc. IEEE, Vol. 83, October 1995, pp. 1374-1396.