基于無標度網(wǎng)絡(luò)的緊湊路由策略研究.pdf

1、路由是Internet網(wǎng)絡(luò)的基本功能。隨著Internet網(wǎng)絡(luò)規(guī)模的增長，節(jié)點路由表規(guī)模急劇膨脹，致使傳統(tǒng)最短路徑路由系統(tǒng)的擴展性面臨著嚴峻的挑戰(zhàn)。緊湊路由通過適當增加路徑長度，從而大幅降低路由表的規(guī)模，很好地保證了Internet路由系統(tǒng)的擴展性。
　　緊湊路由分為通用的緊湊路由和專用的緊湊路由。通用的緊湊路由適合于任意網(wǎng)絡(luò)，專用的緊湊路由利用了特定網(wǎng)絡(luò)的拓撲特性，在該拓撲類型的網(wǎng)絡(luò)上取得了比通用緊湊路由更好的路由性能。而Int

2、ernet網(wǎng)絡(luò)是無標度網(wǎng)絡(luò)，具有明顯的冪率分布、小世界等特性。因此，本文主要對無標度網(wǎng)絡(luò)下專用的緊湊路由進行了一系列的研究工作，具體的研究工作如下:
　　1.研究無標度網(wǎng)絡(luò)下地標節(jié)點的覆蓋面對Thorup-Zwick(TZ)緊湊路由策略的影響。在無標度網(wǎng)絡(luò)下，系統(tǒng)分析了地標節(jié)點的覆蓋面與平均伸長系數(shù)、平均路由表的關(guān)系，并通過設(shè)置閾值來約束地標節(jié)點的最小覆蓋面，提出了基于地標節(jié)點覆蓋面的緊湊路由算法，同時在Intemet AS圖上進

3、行仿真實驗。研究結(jié)果表明，隨著地標節(jié)點最小覆蓋面的增大，平均伸長系數(shù)先減小而后逐漸增加，平均路由表先減小而后保持不變;閾值的選取與實際網(wǎng)絡(luò)模型有關(guān)，當選取一個合適的閾值時，基于地標節(jié)點覆蓋面的緊湊路由算法比原始的TZ算法有更小的平均伸長系數(shù)和平均路由表。
　　2.研究基于無標度網(wǎng)絡(luò)的名字無關(guān)的緊湊路由策略。在連續(xù)10年的Internet AS圖上，深入分析了基于TZ策略和基于Carmi-Cohen(CC)策略的名字無關(guān)的NIHDL

4、R(Name-Independent Highes-Degree Landmark Routing)緊湊路由算法的性能，并通過仿真實驗對兩算法做了系統(tǒng)地分析與比較。具體表現(xiàn)如下:基于CC策略的NIHDLR算法與基于TZ策略的NIHDLR算法取得了近乎一致的路由性能，其中，基于CC策略的NIHDLR算法有略微偏小的平均伸長系數(shù)，但其平均路由表略微偏大。對于引入握手機制可以優(yōu)化路由性能，實驗結(jié)果表明，當未引入握手機制時，兩算法的平均伸長系數(shù)