第3章 基于超節(jié)點(diǎn)的覆蓋網(wǎng)絡(luò)拓?fù)錁?gòu)建算法

3.1 研究背景

為改善現(xiàn)有IP網(wǎng)絡(luò)的可靠性和效率，路由覆蓋網(wǎng)作為一種有效的方法得到了深入研究和廣泛應(yīng)用。一方面，路由覆蓋網(wǎng)可以通過(guò)彈性路由解決IP網(wǎng)絡(luò)鏈路斷裂或擁塞引起的丟包問(wèn)題，提高IP網(wǎng)絡(luò)的可靠性；另一方面，通過(guò)優(yōu)選覆蓋路徑，可以降低通信時(shí)延，提高IP網(wǎng)絡(luò)的效率。覆蓋網(wǎng)絡(luò)拓?fù)涫潜Ｕ掀湫阅艿那疤岷突A(chǔ)。通過(guò)分析已有覆蓋網(wǎng)絡(luò)拓?fù)浯嬖诘膯?wèn)題，本章提出了基于超節(jié)點(diǎn)的覆蓋網(wǎng)絡(luò)拓?fù)錁?gòu)建算法SR-KMST。該算法研究了超節(jié)點(diǎn)的選取以及K最小生成樹(shù)拓?fù)渖傻膯?wèn)題，并針對(duì)物理鏈路故障引發(fā)的覆蓋網(wǎng)備份路徑與物理路徑同時(shí)失效的問(wèn)題，提出了快速恢復(fù)機(jī)制。

已有的路由覆蓋網(wǎng)拓?fù)淇蓺w納為網(wǎng)狀、樹(shù)狀和混合狀態(tài)3種類(lèi)型。最具代表性的是全網(wǎng)狀（Full Mesh overlay Topology, FM）[23]、多樹(shù)狀（K-Minimum Spanning Tree overlay topology, KMST）[63]、混合狀（Mesh-Tree overlay topology, MT[136], Adjacent-Connection overlay topology, AC[25]）。下面介紹已有覆蓋網(wǎng)拓?fù)浼捌浯嬖诘膯?wèn)題。

1．Full Mesh overlay topology

全網(wǎng)狀覆蓋網(wǎng)拓?fù)渲校梢詢(xún)?yōu)選中繼節(jié)點(diǎn)進(jìn)行覆蓋路由，所以其性能較好。假定共有M個(gè)覆蓋節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)需與其他M-1節(jié)點(diǎn)建立覆蓋鏈路，如圖3-1所示，所以FM的復(fù)雜度是O（M2），可擴(kuò)展性差，研究表明全網(wǎng)狀覆蓋拓?fù)涞囊?guī)模最大為50個(gè)節(jié)點(diǎn)[23]。

2．K-Minimum Spanning Tree overlay topology

KMST是在相同的覆蓋網(wǎng)節(jié)點(diǎn)間形成K個(gè)最小生成樹(shù)，使得任意兩點(diǎn)間存在K條不同的覆蓋路徑，其中覆蓋網(wǎng)鏈路的權(quán)重為兩點(diǎn)間時(shí)延或該鏈路對(duì)應(yīng)的物理路徑所包含的物理鏈路的數(shù)量（即跳數(shù)）。由于鏈路的時(shí)延與鏈路當(dāng)前的負(fù)載有關(guān)，很難實(shí)時(shí)檢測(cè)，在一定程度上，鏈路的跳數(shù)可以近似地反映鏈路的時(shí)延的大小關(guān)系。其中，K的值由節(jié)點(diǎn)度的約束條件決定，如圖3-2表示2-MST覆蓋網(wǎng)拓?fù)浣Y(jié)構(gòu)。最小生成樹(shù)是連接所有節(jié)點(diǎn)的最低代價(jià)的結(jié)構(gòu)，可以降低覆蓋網(wǎng)的維護(hù)代價(jià)；另一方面，KMST確保源和目的節(jié)點(diǎn)間存在K條不同的傳輸路徑，這樣，當(dāng)一條路徑出現(xiàn)故障時(shí)，可以快速切換到另一條路徑，提高傳輸?shù)目煽啃?。與FM相比較，KMST中每個(gè)節(jié)點(diǎn)最多需維護(hù)2K個(gè)鄰居節(jié)點(diǎn)的關(guān)系，可擴(kuò)展性好。但KMST僅考慮了覆蓋節(jié)點(diǎn)間的連接關(guān)系，沒(méi)有考慮覆蓋網(wǎng)節(jié)點(diǎn)的選擇問(wèn)題。

3．Mesh-Tree overlay topology

MT是在已建立的覆蓋網(wǎng)最小生成樹(shù)的基礎(chǔ)上，在祖孫或叔侄關(guān)系的節(jié)點(diǎn)間增加鏈路，如圖3-3所示。與KMST類(lèi)似，雖然MT提高了網(wǎng)絡(luò)的可靠性，但沒(méi)有考慮覆蓋節(jié)點(diǎn)的選擇問(wèn)題。

4．Adjacent-Connection overlay topology

AC拓?fù)涞臉?gòu)建方法如下：對(duì)于任何覆蓋網(wǎng)節(jié)點(diǎn)對(duì)（m, n），如果沒(méi)有其他覆蓋網(wǎng)節(jié)點(diǎn)連接到節(jié)點(diǎn)m和n形成的物理路徑上的任何覆蓋網(wǎng)節(jié)點(diǎn)，則建立一條m和n之間的覆蓋鏈路，如圖3-4所示。雖然在構(gòu)建AC拓?fù)鋾r(shí)，用到了節(jié)點(diǎn)間的物理路徑，但沒(méi)有考慮節(jié)點(diǎn)間的最短路徑，即沒(méi)有考慮時(shí)延等參數(shù)。

以上的覆蓋網(wǎng)拓?fù)湓跇?gòu)建過(guò)程中著重考慮了節(jié)點(diǎn)間的連接關(guān)系，而忽略選擇合理的覆蓋網(wǎng)節(jié)點(diǎn)，這必然影響路由覆蓋網(wǎng)的性能，因?yàn)橐恍┕?jié)點(diǎn)在數(shù)據(jù)通信中起著關(guān)鍵的作用，如果在建立覆蓋網(wǎng)拓?fù)鋾r(shí)加入這些節(jié)點(diǎn)，能夠提高覆蓋路由的性能，例如降低時(shí)延。