系統識別號 | U0002-2707201016224800 |
---|---|
DOI | 10.6846/TKU.2010.01010 |
論文名稱(中文) | 叢聚係數與網路壅塞關係 |
論文名稱(英文) | The Relationship between Clustering Coefficient and Network Congestion |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 資訊工程學系資訊網路與通訊碩士班 |
系所名稱(英文) | Master's Program in Networking and Communications, Department of Computer Science and Information En |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 98 |
學期 | 2 |
出版年 | 99 |
研究生(中文) | 周金侯 |
研究生(英文) | Chin-Hou Chou |
學號 | 697420601 |
學位類別 | 碩士 |
語言別 | 繁體中文 |
第二語言別 | 英文 |
口試日期 | 2010-06-28 |
論文頁數 | 44頁 |
口試委員 |
指導教授
-
蔡憶佳
委員 - 蔡憶佳 委員 - 陳伯榮 委員 - 林慶昌 |
關鍵字(中) |
網路壅塞 封包傳遞 小世界網路 無尺度網路 隨機網路 |
關鍵字(英) |
Network congestion Packet transmission Random network Small world network Scale free network |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
近年來網際網路蓬勃發展,網路的使用者、傳遞的資料量每年都不斷的攀升,但由於網路技術、資源不足以應付如此龐大的資料量,網路壅塞現象於焉而生。減緩網路壅塞的現象成為一個重要的議題,同時也是迫切需要解決的問題。本研究在網路大小不變的情形下,藉由連線交換技術改變網路結構,提升網路叢聚係數的方式,探究叢聚係數對於網路發生壅塞現象的影響。在本研究中,我們觀察到小世界網路與無尺度網路若擁有較高的叢聚係數,則網路可以在同一時間內進行更多的封包傳輸任務。另外,不同的網路模型也會對網路壅塞現象有不同的影響。藉由提升網路叢聚係數以提升網路傳輸效能的方式,低連線密度的隨機網路、無尺度網路以及小世界網路會降低其傳輸效能,而高連線密度的隨機網路與無尺度網路則可以有效提升傳輸效。 |
英文摘要 |
The Internet has been grows vigorously in recent years. The users and the data that will transmission by the network are increasing every year, but the network transmission technology and resource are not enough to deal with so much data. It triggers the network congestion phenomenon. Now, to reduce the network congestion phenomenon becomes an important topic. In this paper, we used the local link switching technology which will improve the network clustering coefficient and maintain the size of the network to adjust the network structure. Then we study the influence of the network congestion phenomenon by clustering coefficient. We observed that the network with higher clustering coefficient can execute the more transmission tasks at the same time. In the result, scale free network and small world network can increase the packet density by increasing the clustering coefficient, but random network doesn’t have this property. Additionally, the network model will influence the network congestion phenomenon, too. By our method that increases the network clustering coefficient, the random network and scale free network has the best result in the efficiency of transmission. The small world network decreased its own efficiency of transmission when we increased its clustering coefficient. |
第三語言摘要 | |
論文目次 |
第一章 緒論 1 1-1 研究背景 1 1-2 研究動機與目的 2 1-3 研究方法 3 第二章 背景知識 4 2-1 網路 4 2-2 最短路徑 5 2-3 叢聚係數 6 2-4 連線交換技術 8 2-5 隨機網路 10 2-6 小世界網路 11 2-7 無尺度網路 12 第三章 傳輸模擬 15 3-1 封包傳輸模擬 15 3-2 傳輸效能評估 17 3-3 壅塞模擬實驗結果 18 第四章 網路叢聚係數影響分析 25 4-1 隨機網路 26 4-2 小世界網路 29 4-3 無尺度網路 31 第五章 結論與未來工作 35 參考文獻 37 附錄--英文論文 39 圖 目 錄 圖 一 網路範例圖 4 圖 二 網路最短路徑範例圖 6 圖 三 計算叢聚係數範例圖 7 圖 四 節點的鄰點連線圖 7 圖 五 連線交換範例圖 9 圖 六 連線交換後的網路圖形之一 9 圖 七 連線交換後的網路圖形之二 9 圖 八 不同機率值隨機重接網路連線的圖形變化 12 圖 九 無尺度網路的節點分支度機率分配 13 圖 十 條連線的隨機網路壅塞模擬實驗結果 18 圖 十一 條連線的隨機網路壅塞模擬實驗結果 19 圖 十二 條連線的隨機網路壅塞模擬實驗結果 20 圖 十三 條連線的隨機網路壅塞模擬實驗結果 20 圖 十四 條連線的小世界網路壅塞模擬實驗結果 21 圖 十五 條連線的小世界網路壅塞模擬實驗結果 21 圖 十六 條連線的小世界網路壅塞模擬實驗結果 21 圖 十七 條連線的小世界網路壅塞模擬實驗結果 22 圖 十八 條連線的無尺度網路壅塞模擬實驗結果 22 圖 十九 條連線的無尺度網路壅塞模擬實驗結果 23 圖 二十 條連線的無尺度網路壅塞模擬實驗結果 23 圖 二十一 條連線的無尺度網路壅塞模擬實驗結果 23 圖 二十二 條連線隨機網路調整叢聚度進行網路壅塞模擬實驗結果 26 圖 二十三 條連線隨機網路調整叢聚度進行網路壅塞模擬實驗結果 27 圖 二十四 條連線隨機網路調整叢聚度進行網路壅塞模擬實驗結果 28 圖 二十五 條連線隨機網路調整叢聚度進行網路壅塞模擬實驗結果 28 圖 二十六 條連線小世界網路調整叢聚度進行網路壅塞模擬實驗結果 29 圖 二十七 條連線小世界網路調整叢聚度進行網路壅塞模擬實驗結果 30 圖 二十八 條連線小世界網路調整叢聚度進行網路壅塞模擬實驗結果 30 圖 二十九 條連線小世界網路調整叢聚度進行網路壅塞模擬實驗結果 31 圖 三十 條連線無尺度網路調整叢聚度進行網路壅塞模擬實驗結果 32 圖 三十一 條連線無尺度網路調整叢聚度進行網路壅塞模擬實驗結果 33 圖 三十二 條連線無尺度網路調整叢聚度進行網路壅塞模擬實驗結果 33 圖 三十三 條連線無尺度網路調整叢聚度進行網路壅塞模擬實驗結果 34 |
參考文獻 |
[1]D. De Martino, L. Dall'Asta, G. Bianconi, and M. Marsili, "Congestion phenomena on complex networks," Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), vol. 79, pp. 015101-4, 2009. [2]P. N. Hsiao, "A Small World with Scale Free Model for Network Communication," in Department of Computer Science and Information Engineering: Tamkang University, 2003, p. 41. [3]L. Hardesty, "Internet Gridlock," TECHNOLOGY REVIEW, 2008. [4]J. Z. Liang, "Congestion Avoidance with Explicit Rate Indication in IP Network," in Electrical Engineering. vol. Master Tainan: National Chang Kung University, 2003, p. 78. [5]E. J. Lee, K. I. Goh, B. Kahng, and D. Kim, "Robustness of the avalanche dynamics in data-packet transport on scale-free networks," Physical Review E, vol. 71, p. 056108, 2005. [6]L. Zhao, Y. C. Lai, K. Park, and N. Ye, "Onset of traffic congestion in complex networks," Physical Review E, vol. 71, p. 026125, 2005. [7]S. Valverde and R. V. Solé, "Internet's critical path horizon." vol. 38, 2004, pp. 245-252. [8]H. Lin and C. X. Wu, "Dynamics of congestion transition triggered by multiple walkers on complex networks." vol. 51, 2006, pp. 543-547. [9]J. J. Wu, Z. Y. Gao, H. J. Sun, and H. J. Huang, "Congestion in different topologies of traffic networks." vol. 74, 2006, pp. 560-566. [10]J. J. Wu, Z. Y. Gao, and H. J. Sun, "Optimal traffic networks topology: A complex networks perspective," Physica A: Statistical Mechanics and its Applications, vol. 387, pp. 1025-1032, 2008. [11]L. Zhao, T. H. Cupertino, K. Park, Y. C. Lai, and X. Jin, "Optimal structure of complex networks for minimizing traffic congestion," Chaos: An Interdisciplinary Journal of Nonlinear Science, vol. 17, pp. 043103-5, 2007. [12]T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2 ed.: MIT Press and McGraw-Hill, 2001. [13]Yihjia Tsai, "Clustering Coefficient Increasing Local Link Switching Algorithm," in ICS Damsui, Taipei County, Taiwan, R.O.C., 2008. [14]P. Erdős and A. Rényi, "On the evolution of random graphs," mta 5, pp. 17-61, 1960. [15]H. He and O. Sýkora, "New Circular Drawing Algorithms," ITAT, 2004. [16]S. Milgram, "The small world problem," Psychology Today 2, pp. 60-67, 1967. [17]D. J. Watts and S. H. Strogatz, "Collective dynamics of /`small-world/' networks," Nature, vol. 393, pp. 440-442, 1998. [18]M. E. Crovella, M. S. Taqqu, and A. Bestavros, "Heavy Tailed Probability Distributions in the World Wide Web," in In A Practical Guide To Heavy Tails New York: Chapman & Hall, 1998, pp. 3-25. [19]H. Ebel, L. I. Mielsch, and S. Bornholdt, "Scale-free topology of e-mail networks," Physical Review E, vol. 66, p. 035103, 2002. [20]R. Albert and A. L. Barabási, "Statistical mechanics of complex networks," Reviews of Modern Physics, vol. 74, p. 47, 2002. |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信