跳到主要內容

臺灣博碩士論文加值系統

(3.239.4.127) 您好!臺灣時間:2022/08/20 06:42
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張可均
論文名稱:多點傳送網路之備援虛擬路徑規劃
論文名稱(外文):A Study on Backup VP planning
指導教授:溫于平溫于平引用關係
學位類別:碩士
校院名稱:國立清華大學
系所名稱:工業工程與工程管理學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:58
中文關鍵詞:多點傳送虛擬路徑復原網路
外文關鍵詞:multicastvirtual pathrestorationnetwork
相關次數:
  • 被引用被引用:0
  • 點閱點閱:230
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在現今資訊導向的社會中,舉凡是商業、政治或是社會活動都是蓬勃地在進行著。特別是這些活動的資訊,更是需要快速地經由各種不同的方式傳遞。而在多種資訊傳遞方式下,應用網路傳輸的使用者也越來越多。為了能在資訊爆炸的時代有效的使用有限的頻寬資源,應用多點傳送的技術就因應而生了。多點傳送通訊可以簡單的定義為一種可以在單一的作業中從一個節點發送訊息到一個以上的接收端的能力
但是當人們對網路的依賴越來越高時,如果網路設備故障,將會導致更嚴重的影響。因此,提供容忍故障發生的頻寬是很重要且不可忽視的。不同於單點傳送網路,多點傳送網路的應用大多屬於多媒體的應用,像是視訊會議、遠距教學等多點傳送服務,都必須要有嚴格的QoS要求。所以,本研究的課題是建立一個模式能夠在可允許的設置備援頻寬成本下,尋找較小的備援路徑延遲。並針對此問題發展目標規劃模式,接著提出一啟發式方法,以解決問題擴張時目標規劃求解時間的指數成長。此啟發式方法雖不能保證可以找到目標規劃的正確解,但是從實驗結果中顯示,其績效值的差距都在可容許的範圍內(15%),而且可以穩定且快速的求得近似解,增加了模式應用的可行性。

Current and future distributed real-time applications, such as teleconferencing, remote collaboration, and distance learning, require the underlying communication network to provide multicast service. Furthermore, these applications often involve the exchange of multimedia information with stringent QoS requirement (e.g., bounded end-to-end delay). If a failure occurs in the today’s high capacity and high speed networks, then it can result in a huge loss of bandwidth, loss of service to users, and loss of bandwidth to the operating companies. Therefore the automatic and rapid network service restoration against various unexpected failures becomes a very important issue for network operation and management. In view of this, the asynchronous transfer mode (ATM) network has played a major role in both local area networks (LANs) and wide area networks (WANs).
In this thesis, we consider the problem of constructing a backup virtual path in multicast ATM networks if failures happen. Multicasting is the ability of a communication network to accept a single message from an application and to deliver copies of the message to multiple recipients at different locations. A major contribution of this work is to apply a heuristic algorithm to the backup path search process instead of the goal-programming model. Experimental results indicate that using this heuristic algorithm has a number of advantages over using goal programming.The proposed heuristic algorithm gives an approximation that does not exceed in average the cost and delay time of the exact solution by more than 15%. So it is a practical multicast backup virtual path searching algorithm for large-scale networks.

目錄 Ⅰ
表目錄 Ⅲ
圖目錄 Ⅳ
第一章 續論 1
1.1研究背景與動機 1
1.2 研究目的 4
1.3 研究範圍及限制 4
1.4 研究架構 6
第二章 文獻回顧 8
2.1網路復原模式 8
2.2 點對點復原模式 12
2.3 多點傳送網路的性質 13
2.3.1 多點傳送的應用 13
2.3.2 多點傳送樹的性質 14
2.4 多點傳送網路備用路徑規劃方法回顧 17
第三章 多點傳送備援路徑規劃模式 19
3.1 問題定義 19
3.2 規劃求解模式建立 19
3.2.1 平衡負載成本函數 19
3.2.2 多目標規劃求解模式建立 20
3.3啟發式規劃方法的介紹 24
3.3.1 起始解的設計 24
3.3.2 起始解的改善 27
第四章 實驗設計與效能分析 31
4.1 實驗設計 31
4.1.1假設與限制 31
4.1.2 問題產生 31
4.1.3 實驗方法 32
4.2 效能分析 33
4.2.1啟發式演算法參數的設定 33
4.2.2規劃模式效能分析 34
4.2.3 啟發式演算法的其它績效值分析 37
第五章 結論與建議 40
5.1 結論 40
5.2 建議 41
參考文獻 42
附錄A Yen’s Algorithm的介紹與修改 44
附錄B 啟發式演算法程式碼 49

[1] Ambs, K., Cwilich, S., Deng, M., Houck, D. J., Lynch, D. F. and Yan, D., “Optimizing Restoration Capacity in the AT&T Network,” Interfaces, Vol. 30, pp. 26-44, 2000.
[2] Bang, Y. C., Radhakrishnan, S., Rao, N. S. V. and Batsell, S. G., ”On multicasting with minimum end-to-end delay,” Eight International Conference on Computer Communications and Networks, 1999, pp. 604 —609
[3] Bazaraa S. B., Jarvis, J. J. and Sherali, H. D., Linear Programming and Network Flow, second edition, Wiley, Canada, 1990.
[4] Greca, A.and Nakagawa, K., “A coordination based self-healing algorithm for survivable ATM VP networks,” Proceedings of the IEEE Conference on High Performance Switching and routing, pp. 425-430, 2000.
[5] Hou, C. J., “Design of a fast restoration mechanism for virtual path-based ATM networks,” INFOCOM 1997.Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Vol. 1, pp. 361 —369,1997.
[6] Kwong, S., Lam, D. W. F., Tang, K. S. and Man, K. F., “Optimization of Spare Capacity in Self-Healing Multicast ATM Network Using Genetic Algorithm,” IEEE Transaction on industrial electronics, Vol. 47, No. 6, pp. 1334 —1343, 2000.
[7] Miller C. K., Multicast Networking and Application, 1st edition, Addison-Wesley Longman, U.S.A., 1999.
[8] Martins, E. Q. V.,Pascoal, M. M. B. and Santos, J, L. E., “The K shortest paths problem,” Research Report, CISUC,1998.
[9] Murakami, K. and Kim, H. S., “Optimal Capacity and Flow Assignment for Self-Healing ATM Networks Based on Line and End-to-End Restoration,” IEEE/ACM Transactions on Networking, Vol. 6, Issue 2, pp. 207 —221, 1988.
[10] Sahasrabuddhe, L.H. and Mukherjee, B., “Multicast routing algorithms and protocols: a tutorial,” IEEE Network, Vol. 14, Issue 1, 2000, pp. 90 —102.
[11] Shi, J.J. and Fonseka, “Analysis and design of survivable telecommunications networks,” IEE Proceedings- Communications, Vol. 144 Issue 5, Pp. 322 —330,1997.
[12] Sriram, R., Manimaran, G. and Murthy, C. S. R., “Algorithms for delay-constrained low-cost multicast tree construction,” Computer Communication, Vol. 21, Issue 18, pp. 1693-1706, 1998.
[13] Tawfig A. and Taieb Z., “Low-Cost, Bounded-Delay Multicast Routing for QoS-Based Networks,” Seventh International Conference on computer Communications and Networks, 1998
[14] Wang, Z. and Crowcroft, J., “Quality-of-service routing for supporting multimedia applications,” IEEE Journal on Selected Areas in Communications, Vol. 14, Issue 7, pp. 1228 —1234.
[15] Wen, U. P., Wu, T. L. and Shyur, C. C., “Bi-directional self-healing ring network planning,” Computer & Operation Research, 2001.
[16] Wu, C. S. and Lee, S. W., “Backup VP planning for multicast connections in ATM networks,” Computer Communication, Vol. 22, Issue 10,1999, pp. 898-906
[17] Wu, C. S.; Lee, S. W. and Hou, Y. T., ”Backup VP Preplanning Strategies for Survivable Multicast ATM Networks,” Proceeding IEEE ICC, 1997, pp. 267-271.
[18] Xiong Y. and Mason, L. G., “Restoration strategies and spare capacity requirements in self-healing ATM networks,” IEEE/ACM Transactions on Networking, pp. 98 —110, 1999.
[19] Yen, J. Y., “Finding the K shortest loopless paths in a network,”, Management Science,Vol. 17, pp. 712-716,1971.
[20] Zhu, Q., Parsa, M., Aceves, G., L. J. J., “A source-based algorithm for delay-constrained minimum-cost multicasting,” INFOCOM '95. Fourteenth Annual Joint Conference of the IEEE Computer and Communications Societies, pp. 377 —385, 1995.
[21] 何瑞光,交換技術發展現況及趨勢,通訊雜誌,2000, 81∼88頁。
[22] 李詩偉,高存活性通訊網路之路徑規劃與路由選擇,國立中正大學電機工程研究所博士論文,1998。
[23] 周廣志譯, 頻寬的競爭,(Lu, C., The Race For Bandwidth: Understanding Data Transmission),微軟出版社, 7頁,2000。
[24] 侯雍聰,ATM網路中可存活性點對多點通訊之備份路徑規劃,國立中正大學電機工程研究所碩士論文,1997。
[25] 袁文宗,網路概論,台北:儒林, 17-10頁,1996。
[26] 梁隆星、林正勝等,寬頻網路服務相關技術與應用,電信研究雙月刊,第25卷第5期, 833∼845頁,1995。

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