跳到主要內容

臺灣博碩士論文加值系統

(54.225.48.56) 您好!臺灣時間:2022/01/19 21:26
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:黃仁景
研究生(外文):Ren-Jing HUANG
論文名稱:封包交換網路之壓縮影像傳輸品質保證研究
論文名稱(外文):The Study on Quality of Service Guarantees of Compressed Video Sources in Packet Switch Networks
指導教授:朱延平朱延平引用關係
指導教授(外文):Yen-Ping CHU
學位類別:博士
校院名稱:國立中興大學
系所名稱:應用數學系
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:140
中文關鍵詞:服務品質保證漏斗式規範器多媒體延遲保證
外文關鍵詞:QoSleaky bucket regulatormultimediadelay bound
相關次數:
  • 被引用被引用:0
  • 點閱點閱:1252
  • 評分評分:
  • 下載下載:313
  • 收藏至我的研究室書目清單書目收藏:1
研究一般化之多類別傳輸限時保證(服務保證之標的),考量目前普遍使用之先進先出(FCFS)排程交換節點。由於先進先出排程策略對每一經過之連線皆視為平等,無優先順序。因此,每一條連線經過此交換節點的時間延遲(Time Delay)皆相同,所以若兩條連線經過相同的節點,則其整體的傳輸時間是相同的;但若經過不同的節點,則其整體的傳輸時間可以不同。論文首先討論所謂的確定性服務,可以明確的計算出目前在網路上所有連線的傳輸時間,並且知道目前剩餘之頻寬,如此,方可計算出將來允許新連線進入的數目及增加之傳輸時間。若增加之傳輸時間會影響原有連線之品質保證,將會拒絕新連線進入。由於允許新連線進入之計算策略不同,其連線數目亦不同。因此,首先探討兩種計算策略,一為EQ策略(Equal Allocation),即要求各節點必須平均分攤整體的傳輸時間,亦即,該連線所經過之節點,每個節點的時間延遲皆相同;另一種為OPT策略(Optimal Allocation),允許各節點分配不同時間延遲,依據各節點之剩餘頻寬愈大則提供比其他節點更短之時間延遲。如此,可避免某個節點因為用盡頻寬,而造成新連線無法再進入。為有效評估上述兩種計算策略之效能,我們分別定義兩種指標,一是可接受負載區域(Admissible Load Region),即是允許新加入類型之連線個數,區域愈大,表示其服務範圍愈大;另一是相對效益(Relative Gain),定義為新連線數增加率除以傳輸時間增加率,此數值愈大,表示效率愈高。另外,為了更進一步了解上述網路封包傳遞之特性,我們撰寫一套模擬程式,用以模擬多媒體影像封包經過漏斗式規範器(Leaky Bucket)及延遲調整器(Delay Jitter)封包流量變化的情形,並得知封包經過先進先出排程交換節點所累積之資料量,進而直接獲得該連線之整體傳輸時間,引導我們進入論文第二部分的研究。
論文第二部分,我們應用多類別傳輸限時保證於動態壓縮影像(MPEG)之網路傳輸,我們以一部星際戰爭影片(Star War)之十分鐘片段之資料傳輸量作為輸入值,探討在上述網路架構下,由於此壓縮影像之傳輸封包大小差異相當大的特性下,其傳輸時間的變化。進而探討動態壓縮影像的交通規範值(Traffic Specification),對網路的影響。例如,我們使用漏斗式規範器來規範動態壓縮影像資料的流量時,使用兩個參數,分別為資料速率(ρ)及資料緩衝量(σ)。對於一個動態壓縮影像,一則我們可以要求較高的速率(例如瞬時顛峰速率)。將各種資料速率及資料緩衝量組合的情況,畫在二維座標圖上,即可獲得一條曲線,我們稱其為緩衝曲線(Burstiness curve)。因此,其在漏斗式規範器的資料緩衝區所累積的資料量將會降低,如此可以降低傳輸時間延遲,但其缺點是佔用太多的網路頻寬;一則是要求較低的速率(例如平均速率),則在漏斗式規範器的資料緩衝區所累積的資料量會大大提高,造成傳輸延遲升高,導致無法滿足該連線之傳輸限時需求,但其優點是佔用較低的網路頻寬。因此,論文提出一個公式可以依據連線之限時需求,找到一個最佳之傳輸速率,使得網路所能提供之新連線個數最多,提高網路使用效率。我們比較發現本文之單漏斗式規範器網路的使用效率可以與多漏斗式規範器效能相同,且單漏斗式規範器相較於多漏斗式規範器在實用化較為簡單。
雖然,先進先出節點普遍應用於目前的網際網路,但畢竟無法提供不同的優先服務順序,因此,無法提供差別服務。論文的第三部份,我們將先進先出節點改為最近限時優先節點(Early Deadline First),探討在此網路節點下傳輸壓縮影像之最佳之傳輸速率。首先我們用分析的方式找出其最佳傳輸速率,進而以實際的壓縮影片資料為例,比較最佳速率與瞬時顛峰速率及平均速率所能允許之連線個數,以證實最佳傳輸速率所提昇之效能。
最後,我們將最佳交通規範值方法應用於不同的節點排程策略,包括最小起始標籤公平排班法(Minimum Starting-tag Fair Queuing)、自我對時公平排班法(Self Clocked Fair Queuing)與起始時間公平排班法(Starting-time Fair Queuing),比較不同的節點排程策略所允許之新連線個數,得到其效能提昇之比較值。另外,我們更進一步探討不同的多媒體影像,例如,高傳輸速率高瞬間資料量、高傳輸速率低瞬間資料量、低傳輸速率高瞬間資料量及低傳輸速率低瞬間資料量等四種類型,對網路所能提供之新連線個數做一定量分析比較,提供未來網路管理策略訂定之參考。

In this dissertation, we want to provide the packet switch network with an end-to-end delay quality of service (QoS) guarantee and utilize the bandwidth of the network more efficiently. Consider the network’s use of the FCFS switch nodes that provide the same delay for all the connections, it means the end-to-end delay of all the connections will be same if they go through the same switch nodes. The admission control functions in a network require an adequate per-switch delay allocation policy to allocate end-to-end delay requirements to a set of local switches. In this dissertation, we consider a deterministic service that provides a deterministic number of connections for each service class. We compare two kinds of allocation policies. One is EQ policy (Equal Allocation) where each switch node shares the time delay equally. The other is an OPT policy (Optimal Allocation) where each node can share a different time delay per its residential bandwidth. Therefore, it can avoid any switch node that uses all its allocated bandwidth such that no new connection can be enabled. In order to evaluate the performance of difference allocation policies, we define two performance indices; the admissible region (AR) and the relative gain (RG). In order to realize the packet flow in the above network, we wrote a program to simulate each packet flow in the regulators, delay jitters and FCFS switch nodes. With this simulation program, we evaluate the accumulated bits in the buffer of FCFS node and also the end-to-end delay of each packet. This information motivates the study of the second part of the dissertation.
In the second part, we apply the above N service class networks to the MPEG video sources. We use a set of 10 minute long star wars MPEG-compressed video traces to evaluate our proposed networks. The networks use the leaky bucket to define the input traffic. Since the traffic of the MPEG packet burst rate varied with each of the 10 different transmissions, this presented us with the following problem. If we use the peak rate to determine bandwidth allocation, it will occupy too large network bandwidth and preclude new connections. If we use the mean rate to determine bandwidth allocation, it will introduce longer time delays and not meet the delay requirement. Therefore, we derived a closed form formula to determine the best rate to transfer the MPEG video and allow new connections equal to the network’s use of multiple leaky buckets.

1 Introduction
1.1 Motivation
1.2 Related Works
1.3 Contributions of this Dissertation
1.4 Structure of the Dissertation
2 Compressed Video Source and QoS Network: An Overview
2.1 MPEG
2.2 QoS Metric in Guaranteed Service
2.3 Traffic Shaping
2.3.1 Burstiness and Bandwidth Allocation
2.3.2 Traffic Shapers
2.3.3 Leaky Bucket Scheme
2.3.4 Desirable Properties of a Traffic Shaper
2.3.5 Composite Shaper
2.3.6 Composite Leaky Bucket
2.4 Packet Scheduling Discipline
2.4.1 Earliest Deadline First
2.4.2 Weighted Fair Queuing
2.4.3 Self-Clocked Fairing Queuing
2.4.4 Start-time Fairing Queuing
2.4.5 Minimum Start-time Fairing Queuing
3 The QoS of N Class Sources in a FCFS Network
3.1 Introduction
3.2 The QoS Criteria
3.2.1 Single Node
3.2.2 End-to-end Case
3.2.3 Upper Bound of the Performance
3.3 The Analysis Model
3.3.1 EQ Policy
3.3.2 OPT Policy
3.3.3 Comparison of OPT and EQ Policy
3.4 Numerical Results
3.5 Simulations
4 Resource Allocation in FCFS Network for Multimedia Traffic Flows using a Burstiness Curve Envelope
4.1 Introduction
4.2 Optimal Traffic Class Selection
4.2.1 Network Architecture and Traffic Model
4.2.2 Joint Selection
4.2.3 Call Admission Formula
4.2.4 Optimal Traffic Class Selection Formula
4.3 Numerical Results
5 Resource Allocation in EDF Network for Multimedia Traffic Flows using a Burstiness Curve Envelope
5.1 Introduction
5.2 Proposed Traffic Selection Discipline
5.2.1 Traffic class Selection Problem
5.2.2 Optimal Traffic class Selection Formula
5.3 Numerical Results
6 Resource Allocation in Fair Queuing Network for Multimedia Traffic Flows using a Burstiness Curve Envelope
6.1 Introduction
6.2 Delay Bound
6.3 Traffic Class Selection
6.4 Numerical Results
7 Summary and Future Work
7.1 Summary
7.2 Suggestion of Future Work
Appendix
Bibliography

[1] D. Ferrari and D. Verma, A scheme for real-time channel establishment in wild-area networks, IEEE JSAC, vol. 8 pp.368-379, Apr., 1990.
[2] Yen-Ping Chu, E-Hong Hwang, Kuan-Cheng Lin and Chin-Hsing Chen, Local allocation of end-to-end delay requirement, IEICE Trans. Communication, Vol.E82-B, No.9, pp.1380-1387, Sep., 1999.
[3] J. Turner, New directions in communication (or which way to the information age?), IEEE Comm. Mag., vol.24, no.10, Oct., 1986.
[4] R. Nagarajan, J. Kurose and D. Towsley, Local allocation of end-to-end quality-of-service in high-speed networks, IFIP TC6 Task Group / WG 6.4 International Workshop on Performance of Comm. Systems, pp.99-118, Martinique, Jan., 1993.
[5] H. Zhang and D. Ferrari, Improving utilization for deterministic service in multimedia communication, International Conference on Multimedia Computing and Systems, pp.295-304, Boston, MA, May, 1994.
[6] J. Hyman, A. Lazar, and G. Pacifici, Joint scheduling and admission control for ATS-based switching nodes, in Proc. SIGCOMM’92, pp.223-234, Aug., 1992.
[7] J. Liebeherr, D. Wrege, and D. Ferrari, Exact admission control in network with bounded delay services, IEEE/ACM Transactions on Networking, Dec., 1996.
[8] Chi-Yuan Hsu, Antonio Ortega, and Amy R. Reibman, Joint selection of source and channel rate for VBR video transmission under ATM policing constraints, IEEE J. Selective Areas in Communication, vol. 15, no. 6, pp.1016-1028, Aug., 1997.
[9] Yen-Ping Chu, Ren-Jing Huang, and Kuan-Cheng Lin, Optimal schedulable region analysis of FCFS network model supports end-to-end delay requirement, Proceeding of 1999 National Computer Symposium, Tamkang University, Taipei, Taiwan, pp. B-133-138, Dec., 1999.
[10] Edward W. Knightly and Hui Zhang, Traffic characterization and switch utilization using a deterministic bounding interval dependent traffic model, IEEE INFOCOM’95.
[11] S. Keshav, An engineering approach to computer networking, Addison-Wesley, pp.402-406, 1997.
[12] H. Zhang and D. Ferrari, Rate-controlled service disciplines, Journal of High Speed Networks, Vol.3, No.4, pp.389-412, 1994.
[13] Rahul Garg, Characterization of video traffic, Technical report of international computer science institute, 1995.
[14] Oliver Rose. Statistical properties of MPEG video traffic and their impact on traffic modeling in ATM systems, Proceedings of the 20th Annual Conference on Local Computer Networks, Minneapolis, MN, pp.397-406, 1995.
[15] Yen-Ping Chu and Kuan-Cheng Lin, Optimal admission control based on per-switch delay allocation for networks with bounded delay service, IEICE Transaction on Communication, Jul., 2000.
[16] L. Georgiadis, R. Guerin, V. Peris and K. N. Sivarajan, Efficient network QoS provisioning base on per node traffic shaping, IEEE/ACM Transaction on Networking, Vol.4, No.4, pp.482-501, Aug., 1996.
[17] E. P. Rathgeb, Modeling and performance comparison of policing mechanisms for ATM networks, IEEE Journal on Selected Areas in Communications, 9(4): pp.325-334, Apr., 1991.
[18] E. W. Knightly, D.E. Wrege, J. Liebeherr, and H. Zhang, Fundamental limits and tradeoffs of providing deterministic guarantees to VBR traffic, Proceeding ACM Sigmetrics ’95, pp.98-107, May, 1995.
[19] E. W. Knightly, Traffic models and admission control for integrated services networks, PhD thesis, University of California at Berkeley, May, 1996.
[20] S. V. Raghavan and Sarish K. Tripathi, Networked multimedia system: concept, architecture, and design, Prentice Hall, pp.107-120, 1998.
[21] D. Pan. An overview of the MPEG audio compression algorithm in SPIE. Digital Video Compression on Personal Computers: Algorithms and Technologies, Vol.2187, pp.260-273, 1994.
[22] Didier Le Gall, MPEG: A video compression standard for multimedia applications, Communications of the ACM, Vol.34, No.4, pp.46-58, Apr., 1991.
[23] Joan L.Mitchell, William B. Pennebaker, Chad E. Pogg, and Didier Legall (Eds.), MPEG Video Compression Standard, Chapman & Hall, 1997.
[24] H. Zhang, Service disciplines for guaranteed performance service in packet switching networks, Proceeding of IEEE, 83(10): pp.1374-1399, Oct., 1995.
[25] D. Ferrari, Clint requirement for real-time communication services, IEEE comm. Mag., 28(11), pp. 65-72, Nov. 1990.
[26] D. Verma, H. Zhang, and D. Ferrari, Guaranteeing delay jitter bounds in packet switching networks, Proc. Og TRICOMM, pp.35-46, Apr., 1991.
[27] R. Nagarajan and J. Kurose, On defining, computing and guaranteeing quality-of-service in high-speed networks, In IEEE Infodon’92, pp.8C.2.1-8C.2.10, May, 1992.
[28] O. Yaron and M. Sidi, Calculating performance bounds in communication networks, Proc. of INFOCOM, pp.539-546, Apr., 1993.
[29] S. Radhakrishnan and S. V. Raghavan. Network support for distributed multimedia - issues and trends, Proceedings of SEACOMM'94, International Conference on Communications and Computer Networks, KuaJa Lumpur, Malaysia, Oct., 1994.
[30] Erwin P. Ratligeb, Modeling and performance comparison of policing mechanisms for ATM networks, IEEE Journal on Selected Areas in Communications, Vol. 9, No. 3, pp. 325-334, Apr., 1991.
[31] Krishna Blala, Israel Cidon, and K. Sohraby, Congestion control for high-speed packet switched networks, IEEE INFOCOM, pp.520-526, 1990.
[32] A.E- Eckberg, D. T. Luan, and D. M. Lucantoni, Bandwidth management: a congestion control strategy for broadband packet networks characterizing the throughput burstiness filter, Computer Networks and ISDN Systems Vol. 20, pp.415-423, 1990.
[33] M. Sidi, W. Liu, and I. Cidon and I. Gopal, Congestion control through input rate regulation, Proceedings of GLOBECOM'89, Dallas, Texas, pp.1764-1768, Nov., 1989.
[34] Masayuki MuraJta, Yoshihiro Ohtba and Hideo Miyahara, Analysis of flow enforcement algorithm for bursty traffic in ATM networks, Proceedings of IEEE INFOCOM'92, Firenze, ltaly, pp.2453-2462, May l992.
[35] San-qi Li and Song Chong, Fundamental limits of input rate control in high-speed network, Proceedings of IEEE lNFOCOM'93, San Francisco, California, pp.662-671, Mar., l993.
[36] S. Radhakrishnan, S. V. Raghavan, and Ashok K. Agrawala, A flexible traffic shaper with variable burstiness for high-speed networks, Proceedings of the JENC6 International Conference to be held in Tel Aviv, Israel, May, 1995.
[37] S. Radhakrishnan, S. V. Raghavan, Ashok K. Agrawala, A flexible traffic shaper for high-speed networks: design and comparative study with leaky bucket, Computer Networks and ISDN Systems, Vol. 28, pp.453-469, 1996.
[38] D. Saha, S. Mnkherjee, and S. K. Tripathi, Multi-rate traffic shaping and end-to-end performance guarantees in ATM networks, Proceedings of International Conference on Network Protocols, 1994.
[39] A. L. Elwalid and D. Mitra, Effective Bandwidth of general Markovian traffic sources and admission control of high-speed networks, Proceedings of IEEE INFOCOM'93, San Francisco, California, pp.256-2.65, Mar., 1993.
[40] R. Guerin, H. Ahmadia and M. Naghshineh, Equivalent capacity and its application to bandwidth allocation in high-speed networks, IEEE Journal on Selected Areas in Communications, Vol. 9, No. 7, pp.968-981, Sep., 1991.
[41] R. L. Cruz. A Calculus for Network Delay, Part 1: Network elements in isolation, IEEE transactions on information theory, Vol. 37, No.1, pp. 114-131, Jan., 1991.
[42] S. Keshav, Congestion control for computer networks, PhD thesis, univ. of California at Berkeley, 1991.
[43] L. Kleinrock, Queuing systems, John Wiley and sons, 1975.
[44] L. Kleinrock, Queuing systems, and Vol. 2: computer applications, Wiley, 1976.
[45] L. Zhang, Virtual Clock: a new traffic control algorithm for packet switching networks, ACM Trans. On Comp. System, Vol. 9, No. 1, pp.3-26, 1990.
[46] A. Demers, S. Keshav, and S. Shenker, Analysis and simulation of fair queuing algorithm, Journal of Internetworking Research and Experience, pp.3-26, Oct., 1990.
[47] A. Parekh and R. G. Gallager, A generalize processor sharing approach to flow control in integrated services network: the single-node case, IEEE/ACM Trans. On Networking, Vol. 2, No. 2, pp.344-357, Jun., 1993.
[48] A. Parekh and R. G. Gallager, A generalize processor sharing approach to flow control in integrated services network: the multiple-node case, IEEE/ACM Trans. On Networking, Vol. 2, No. 2, pp.137-150, Apr., 1994.
[49] S. Golestani, A self-clocked fair queuing scheme for broadband application, Proceedings of IEEE INFOCOM’94, Toronto, ACA Z, pp.636-646, Jun., 1994.
[50] P. Goyal, S. Lam and H. Vin, Start-time Fair Queuing: a scheduling algorithm for integrated services packet switching networks, Proceedings of SIGCOMM, 1996.
[51] D. Kandlur, K. Ahin, and D. Ferrari, Realtime communication in multi-hop networks, Proc. Of 11th International Conference on Distributed Computer System, May 1991.
[52] Q. Zheng and K. Shin, On the ability establishing real-time channel in point-to-point packet-switching networks, IEEE Trans. On Comm., pp.1096-1105, Mar., 1994.
[53] S. Golestani, A Stop-and-Go queuing framework for congestion management, Proc. of ACM SIGCOMM, pp.8-18, Sep., 1990.
[54] S. Golestani, Congestion-free transmission of real-time traffic in packet networks, Proc. Of INFOCOM, pp.527-542, Jun., 1990.
[55] C. Kalmanek, H. Kanakia, and S. Keshav, Rate controlled servers for very high speed networks, Proc. Of IEEE GLOBECOM, pp.300.3.1-300.3.9, Dec., 1990.
[56] H. Zhang and D. Ferrari, Rate-controlled static priority queuing, Proc. of IEEE INFOCOM, pp.227-236, Apr., 1993.
[57] L. Georgiadis, R. Guerin, and A. Parekh, Optimal multiplexing on a single link: delay and buffer requirements, Proc. of IEEE INFOCOM, pp.524-532, Jun., 1994.
[58] S. V. Raghavan and Sarish K. Tripathi, Networked multimedia system: concept, architecture, and design, Prentice Hall, pp.281-294, 1998.
[59] Y. P. Chu and E. H. Hwang, A new packet scheduling algorithm: Minimum starting-tag fair queuing, IEICE Transaction on Communications, Vol. E80-B, No. 10, Oct., 1997.
[60] D. Ferrari, Real time communication in an internetwork, Journal of High Speed Networks, Vol. 1, N0. 1, pp.79-103, 1992.
[61] P. Goyal, S. Lam and H. Vin, Start-time Fairing Queuing: a scheduling algorithm for integrated service packet switching networks, Proceding of SIGCOMM, 1996.
[62] P. Goyal, S. Lam and H. Vin, Start-time Fairing Queuing: a scheduling algorithm for integrated service packet switching networks, Technical report TR-96-02, Departmrnt of Computer Sciences, University of Texas at Austin.
[63] R. Jain, Congestion control and traffic management in ATM networks: recent advances and survey, Comp. Networks and ISDN Sys., Oct., 1996.
[64] S. Golestani, Network delay analysis of a traffic class of fair queuing algorithms, IEEE Journal on Selected Areas in Comm., Vol. 13, pp.105-1070, Aug., 1995.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 李柏佳(民88)。臺北市國民小學組織再造的方向與展望。學校行政,3期,頁39-50。
2. 林信義(民87)。從企業再造觀點談政府再造與創新。公務人員月刊,25期,頁5。
3. 吳清山(民88)。跨世紀學校組織再造之重要課題及其策略。教師天地,98期,頁4-9。
4. 吳清山(民87)。教育革新中學校組織再造之探究。北縣教育,24期,頁10-15。
5. 吳明清(民87):學校教育改革的趨向與課題。教育資料與研究,22期,頁1-7。
6. 李安民,賴燊雲(民87)。從教育改革的觀點看學校組織再造。北縣教育,24期,頁24-30。
7. 何玉美(民88)。四兩撥千斤的未來企業─核心專長留下其餘外包。管理雜誌,298期,頁60-64。民90年7月16日,取自http://www.harment.com/mm/9904/cov.htm
8. 邱毅(民87)。透視企業變革的核心一認識企業變革。人力發展月刊,55期,頁6-10。民90年7月19日,取自http://www.tpg.gov.tw/a26/55/HG03.html
9. 張芳全(民88)。教育改革行動方案評析。教育研究月刊,第77期,頁33。民90年4月15日,取自http://www.edujournal.com.tw/77/33.htm。
10. 張明輝(民88)。企業組織的革新對學校組織再造的啟示。教師天地,98期。民90年12月5日,取自http://192.192.169.230/edu_paper/e_doc/g0000225/A100_10.htm。
11. 張德銳(民89)。新世紀我國中小學學校經營的方向。學校行政,5期,頁12-22。