名空間路由研究和源管理路由算法的分析與建模.pdf

1、網(wǎng)絡(luò)路由一直是網(wǎng)絡(luò)的關(guān)鍵問題。今天的計(jì)算機(jī)網(wǎng)絡(luò)非常龐大、高速,傳載著各種多媒體信息,因此,網(wǎng)絡(luò)路由面臨新的挑戰(zhàn)。路由算法層出不窮,目的都是為了尋找滿足要求的路徑來傳遞信息。而目前因特網(wǎng)使用的路由算法,主要是基于1959年提出的Dijkstra算法和1962年提出的基于Bellman-Ford算法等理論研究成果。這些經(jīng)典路由算法都是假設(shè)在網(wǎng)絡(luò)拓?fù)涞幕A(chǔ)上定義一個(gè)度量,在這個(gè)度量的基礎(chǔ)上計(jì)算每個(gè)節(jié)點(diǎn)到達(dá)其他節(jié)點(diǎn)的最短路由,并且為每個(gè)子網(wǎng)保持

2、一個(gè)路由表項(xiàng)。它們的特點(diǎn)是全局維護(hù),精確路由指向,最短路徑路由。隨著網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大,子網(wǎng)數(shù)量急劇增多,目前全局最優(yōu)的傳統(tǒng)路由算法將面臨嚴(yán)重挑戰(zhàn)。網(wǎng)絡(luò)發(fā)展趨勢引發(fā)在理論上重新審視現(xiàn)有路由算法和開拓新路由方案的迫切需求。
　　 本文在研究了VRR(Virtual Ring Routing)和ROFL(Routing on Flat Labels)路由算法的基礎(chǔ)上,總結(jié)出的名空間路由思想:它是基于拓?fù)洫?dú)立的路由法則；具有非精確路由指

3、向,每個(gè)節(jié)點(diǎn)只指向有限個(gè)其他可達(dá)節(jié)點(diǎn),按照路由法則將信息轉(zhuǎn)發(fā)到記錄中“最近”指向節(jié)點(diǎn)去；非全局路由維護(hù),每個(gè)節(jié)點(diǎn)只需獨(dú)立維護(hù)各自指定節(jié)點(diǎn)的可達(dá)性。
　　 本文研究了把VRR(Virtual Ring Routing)和ROFL(Routing on Flat Labels)應(yīng)用到BGP路由協(xié)議的可行性,并把這種方法稱為源管理路由方案。有如下發(fā)現(xiàn):節(jié)點(diǎn)命名對路由性能有明顯的影響,而在VRR(Virtual Ring Routing

4、)和ROFL(Routingon Flat Labels)中命名是隨機(jī)的；拓?fù)湎嚓P(guān)的命名策略并不能提高路由性能；核心AS在源管理路由算法中起到重要作用。
　　 探討了源管理路由方案在基于AS商業(yè)關(guān)系的實(shí)際網(wǎng)絡(luò)拓?fù)渲械目尚行?發(fā)現(xiàn):直接把源管理路由方案應(yīng)用實(shí)際AS商業(yè)關(guān)系的網(wǎng)絡(luò)拓?fù)渲?源管理路由方案得到的路徑并不是都符合BGP路由策略；提出基于分層源管理路由方案建立和維護(hù)多條虛擬鄰居路徑的方法以提供基于AS商業(yè)關(guān)系的完備路由信息,

5、確保完整路徑的有效性。
　　 提出了源管理路由算法的理論模型,該路由算法思想雖然簡單,卻沒有理論模型來描述它的路由選擇問題以及計(jì)算任意節(jié)點(diǎn)間的路徑長度,尤其是從理論上來評估源管理路由算法的性能。模型中通過利用虛擬環(huán)路徑這一獨(dú)特想法來描述路徑選擇問題,根據(jù)源節(jié)點(diǎn)和目的節(jié)點(diǎn)名字在標(biāo)識符數(shù)值上的距離,分析在虛擬環(huán)上出現(xiàn)的所有可能路徑的概率,計(jì)算在虛擬環(huán)上路徑的平均跳數(shù),最終估算出實(shí)際物理路徑的長度。分析影響路由性能的因素,網(wǎng)絡(luò)中的節(jié)點(diǎn)

6、數(shù)量,虛擬鄰居路徑的長度,源節(jié)點(diǎn)目的節(jié)點(diǎn)名字在標(biāo)識符數(shù)值上的距離以及網(wǎng)絡(luò)拓?fù)涠加绊懼垂芾砺酚伤惴窂介L度的分布。通過全面深入的分析源管理路由算法,對其路由效率及可擴(kuò)展性有了完整的認(rèn)識,為適應(yīng)于未來核心網(wǎng)絡(luò)路由打下堅(jiān)實(shí)的理論基礎(chǔ)。
　　 針對源管理路由方案中核心節(jié)點(diǎn)路由表可能會過于龐大的問題,研究了通過命名來壓縮路由表的可能性。提出了一種基于概率的啟發(fā)性命名算法,通過節(jié)點(diǎn)到達(dá)連續(xù)地址節(jié)點(diǎn)的下一跳盡可能相同(并將這些地址是連續(xù)的節(jié)