跳到主要內容

臺灣博碩士論文加值系統

(44.211.31.134) 您好!臺灣時間:2024/07/25 18:02
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:陳雍穆
研究生(外文):Yung-Mu Chen
論文名稱:階層式路由架構與服務品質路由應用之研究
論文名稱(外文):A Layered Routing Architecture and Its Applications in QoS Routing
指導教授:鍾添曜
指導教授(外文):Tein-Yaw Chung
學位類別:碩士
校院名稱:元智大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:英文
論文頁數:31
中文關鍵詞:有限泛洪階層式架構可程式化網路路由架構服務品質保證路由主動式網路
外文關鍵詞:Bounded FloodingLayered ArchitectureProgrammable NetworkRouting ArchitectureQoS RoutingActive Network
相關次數:
  • 被引用被引用:0
  • 點閱點閱:172
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:3
  在電腦網路中尋找一條最佳化並且具有多重條件限制的服務品質(QoS)路由路徑是屬於NP-Hard的問題。在過去,有許多研究學者提出許多解決方案來尋找合適的服務品質路由路徑,並且減少選徑時所產生的網路負荷。例如:啟發式搜尋,限制性泛洪搜索,選擇性偵測與平行性偵測等技術。然而這些解決方案所使用的是完整定型(monolithic)且不可更動的路由協定;換言之,它們獨立並重新發展於現有的路由協定之外,這樣的做法既不實用也沒有必要性。
  在本論文中,我們提出兩種新的服務品質路由協定─最短路徑導向路由協定(SAR)以及次節點路徑導向路由演算法(NAR)。這兩種路由協定以可程式化的路由節點模型,例如P1520,做為基礎架構。在這個路由架構當中,新的路由服務可以建立在現有的選徑服務之上,例如OSPF,不必重新從零開始發展。
  在這兩個演算法中,我們以N-hop flooding協定做為網路資訊交換的基礎服務,並依此建立一個OSPF路由協定,做為預設的路由服務。N-hop flooding、OSPF與其他一些路由協定可以將自己的服務,提供給新發展的路由服務使用。在我們的泛洪演算法當中,採用了下列三個方式來限制泛洪的網路負擔:使用一個有限範圍的額度N,有限的回應時間,以及只接收一次訊息的策略。並且為了減少不必要的資源保留,我們採用兩段式資源保留策略。
  我們藉由模擬程式來比較本論文所提出的演算法與傳統泛洪演算法以及最短路徑路由演算法之間的效能。由模擬結果可以發現本文所提出的演算法─NAR與SAR─效能較傳統的泛洪演算法與最短路徑路由演算法為佳。模擬結果也證實了簡單的服務品質路由服務是可以在分層路由架構,輕易地實作並獲得良好的加值服務。

Finding an optimal multi-constraint QoS path in a computer network is a NP hard problem. In the past, many researchers have proposed solutions, such as heuristic searching, limited hop flooding, selective probing and parallel probing, to find a feasible multi-constraint QoS routing path with reduced routing overhead. These solutions use basic monolithic routing protocol, i.e., they are built from scratch and are independent of existing routing protocols. However, this is neither practical nor necessary. In this thesis, we propose two new QoS routing protocols, shortest path aware routing algorithm (SAR) and next-hop path aware routing algorithm (NAR), based on a programmable router model, such as P1520. In this routing architecture, a new routing service can be built on existing routing services, such as OSPF, and using routing table as an interface. We use an N-hop flooding protocol as our basic routing information exchange protocol. Based on which, an OSPF routing protocol is built and provides default routing service. New routing services can be built upon the services of N-hop flooding, OSPF, and some other routing protocols. In our flooding algorithm, we limit flooding overhead by hop count N, finite response time (timeout), and receive-once policy. In order to reduce excessive resources reservation, we employ Two-Pass resource reservation scheme in our routing protocol. We compare the performance of our algorithms with traditional flooding algorithm and shortest path routing by simulation. The simulation results show that the proposed algorithms SAR and NAR have good performance than traditional flooding algorithm and the shortest path routing. The results also confirm that simple QoS routing services can be easily implemented to obtain good value-added services on layered routing architecture.

1 INTRODUCTION 1
1.1 BACKGROUND AND MOTIVATION 1
1.2 ORGANIZATION OF THESIS 2
2 RELATED WORK 3
2.1 QOS ROUTING PROTOCOL 3
2.2 P1520 REFERENCE MODEL 5
2.3 ACTIVE NETWORK 7
3 LAYERED ROUTING ARCHITECTURE AND QOS AWARE ROUTING ALGORITHMS 10
3.1 LAYERED ROUTING ARCHITECTURE 10
3.2 N-HOP FLOODING ALGORITHM 12
3.3 SHORTEST PATH AWARE ROUTING (SAR) ALGORITHM 13
3.4 NEXT-HOP PATH AWARE ROUTING (NAR) ALGORITHM 16
4 SIMULATION 20
4.1 SIMULATION MODEL 20
4.2 SIMULATION RESULT 21
4.2.1 Effect of Call Characteristics 21
4.2.2 Effect of Call QoS Requirement 25
4.2.3 Effect of Hop Count Number 27
5 CONCLUSION AND FUTURE WORK 29
5.1 CONCLUSION 29
5.2 FUTURE WORK 29
REFERENCES 30

[1].D.L. Tennenhouse, J.M. Smith, W.D. Sincoskie, D.J. Wetherall, G.J Minden, “ A survey of active network research,” IEEE Communications Magazine, Vol. 35, pp. 80 —86, Jan. 1997.
[2].Patel, “Active network technology,” IEEE Potentials, Vol. 20, pp. 5 —10, Feb.—Mar. 2001.
[3].J. Biswas, A.A. Lazar, J.-F. Huard, K. Lim; S. Mahjoub, L.-F. Pau, M. Suzuki, S. Torstensson, W. Wang; S. Weinstein, “The IEEE P1520 standards initiative for programmable network interfaces,” IEEE Communications Magazine, Vol. 36, pp. 64 —70, Oct. 1998.
[4].Multiservice Switching Forum (MSF). http://www.msforum.org
[5].International Softswitch Consortium (ISC). http://www.softswitch.org
[6].N. Bjorkman, Y. Jiang, T. Lundberg, A. Latour-Henner, A. Doria, “The movement from monoliths to component-based network elements,” IEEE Communications Magazine, Vol. 39, pp.86 —93, Jan. 2001.
[7].IEEE P1520 Working Group. http://www.ieee-pin.org/
[8].Anand Tripathi, “Challenges designing next-generation middleware systems,” Communications of the ACM Vol. 45, pp. 39—42, Jun. 2002.
[9].W.C Lee, M.G. Hluchyi, P.A. Humblet, “Routing subject to quality of service constraints in integrated communication networks,” IEEE Network Magazine., Vol. 9, pp. 46 —55, July-Aug. 1995.
[10].S. Chen, K. Nahrstedt, “An overview of quality of service routing for next-generation high-speed networks: Problems and solutions”, IEEE Network Magazine, Vol. 12, pp. 64—79, Nov. 1998.
[11].Zheng Wang, J. Crowcroft, “Quality-of-service routing for supporting multimedia applications,” IEEE J. Select. Areas Commun. , Vol. 14, pp. 1228—1234, Sep 1996
[12].K. G. Shin and C. Chou, “A distributed route-selection scheme for establishing real-time channels,” in Proc. High Performance Networking, pp. 319—330, 1995.
[13].S. Chen and K. Nahrstedt, “Distributed quality-of-service routing in high-speed networks based on selective probing,” in Proc. IEEE Local Computer Networks (LCN) 1998, pp. 80—89, 1998.
[14].S-K Kweon and K. G. Shin, “Distributed qos routing using bounded flooding”, Technical Report, CSE-TR-388-99, University of Michigan, 1999
[15].G. Manimaran, H.S. Rahul, C.S.R. Murthy, “A new distributed route selection approach for channel establishment in real-time networks,” IEEE/ACM Trans. Networking, Vol. 7, pp. 698 —709, Oct. 1999.
[16].H.K. Pung, J. Song, L. Jacob, “Fast and efficient flooding based QoS routing algorithm,” in Proc. Computer Communications and Networks, pp. 298—303, 1999.
[17].C.-C. Chou, S.-K. Kweon, K.G. Shin, “Distributed route selection for establishing real-time channels,” IEEE Trans. Parallel and Distributed Systems, Vol. 11, pp. 318 —335, Mar. 2000.
[18].Fei, M. Gerla, “Smart forwarding technique for routing with multiple QoS constraints,” in Proc. IEEE GLOBECOM '00, Vol. 1, pp. 599—604, 2000.
[19].K. S. Teng, M. Maheswaran, “Limited scope probing: a distributed approach for QoS-based routing,” Network Computing and Applications (NCA) 2001. IEEE International Symposium on, pp. 350—353, 2001.
[20].Johnny Chen, Peter Druschel, Devika Subramanian, “A Simple, Practical Distributed Multi-Path Routing Algorithm,” Rice University, CS Technical Reports, TR98 —320, July 16, 1998.
[21].S.Chen, K. Nahrstedt, Y.Shavitt , “A QoS-Aware Multicast Routing Protocol,” IEEE J. Select. Areas Commun. , Vol. 18, pp. 2580—2592, Dec 2000.
[22].S. Yan, M. Faloutsos, A. Banerjea, “QoS-aware multicast routing for the Internet: the design and evaluation of QoSMIC,” IEEE/ACM Trans. Networking, Vol. 10, pp. 54 —66, Feb. 2002.
[23].Zhi Li, P. Mohapatra, “QoS-aware multicast protocol using bounded flooding (QMBF) technique”, IEEE ICC2002, pp. 1259 —1263, 2002
[24].P. Francis, S. Jamin, Cheng Jin, Yixin Jin, D. Raz, Y. Shavitt, L. Zhang, “IDMaps: a global Internet host distance estimation service,” IEEE/ACM Trans. Networking, Vol. 9, pp. 525 —540, Feb. 2001.
[25].Shaikh, M. Goyal, A. Greenberg, R. Rajan, Ramakrishnan, K. K, “An OSPF topology server: design and evaluation,” IEEE J. Select. Areas Commun. , Vol. 20, pp. 746—755, May 2002.
[26].H. Lorenz, A. Orda, “QoS routing in networks with uncertain parameters,” IEEE/ACM Trans. Networking, Vol. 6, pp. 768—778, Dec 1998
[27].T. Cormen, C. Heiserson and R. Rivest, Introduction to Algorithms, MIT Press, 1990.
[28].William Stallings, Data & Computer Communications, Prentice Hall, 2000.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top