第3章 基于超節點的覆蓋網絡拓撲構建算法

3.1 研究背景

為改善現有IP網絡的可靠性和效率，路由覆蓋網作為一種有效的方法得到了深入研究和廣泛應用。一方面，路由覆蓋網可以通過彈性路由解決IP網絡鏈路斷裂或擁塞引起的丟包問題，提高IP網絡的可靠性；另一方面，通過優選覆蓋路徑，可以降低通信時延，提高IP網絡的效率。覆蓋網絡拓撲是保障其性能的前提和基礎。通過分析已有覆蓋網絡拓撲存在的問題，本章提出了基于超節點的覆蓋網絡拓撲構建算法SR-KMST。該算法研究了超節點的選取以及K最小生成樹拓撲生成的問題，并針對物理鏈路故障引發的覆蓋網備份路徑與物理路徑同時失效的問題，提出了快速恢復機制。

已有的路由覆蓋網拓撲可歸納為網狀、樹狀和混合狀態3種類型。最具代表性的是全網狀（Full Mesh overlay Topology, FM）[23]、多樹狀（K-Minimum Spanning Tree overlay topology, KMST）[63]、混合狀（Mesh-Tree overlay topology, MT[136], Adjacent-Connection overlay topology, AC[25]）。下面介紹已有覆蓋網拓撲及其存在的問題。

1．Full Mesh overlay topology

全網狀覆蓋網拓撲中，可以優選中繼節點進行覆蓋路由，所以其性能較好。假定共有M個覆蓋節點，每個節點需與其他M-1節點建立覆蓋鏈路，如圖3-1所示，所以FM的復雜度是O（M2），可擴展性差，研究表明全網狀覆蓋拓撲的規模最大為50個節點[23]。

2．K-Minimum Spanning Tree overlay topology

KMST是在相同的覆蓋網節點間形成K個最小生成樹，使得任意兩點間存在K條不同的覆蓋路徑，其中覆蓋網鏈路的權重為兩點間時延或該鏈路對應的物理路徑所包含的物理鏈路的數量（即跳數）。由于鏈路的時延與鏈路當前的負載有關，很難實時檢測，在一定程度上，鏈路的跳數可以近似地反映鏈路的時延的大小關系。其中，K的值由節點度的約束條件決定，如圖3-2表示2-MST覆蓋網拓撲結構。最小生成樹是連接所有節點的最低代價的結構，可以降低覆蓋網的維護代價；另一方面，KMST確保源和目的節點間存在K條不同的傳輸路徑，這樣，當一條路徑出現故障時，可以快速切換到另一條路徑，提高傳輸的可靠性。與FM相比較，KMST中每個節點最多需維護2K個鄰居節點的關系，可擴展性好。但KMST僅考慮了覆蓋節點間的連接關系，沒有考慮覆蓋網節點的選擇問題。

3．Mesh-Tree overlay topology

MT是在已建立的覆蓋網最小生成樹的基礎上，在祖孫或叔侄關系的節點間增加鏈路，如圖3-3所示。與KMST類似，雖然MT提高了網絡的可靠性，但沒有考慮覆蓋節點的選擇問題。

4．Adjacent-Connection overlay topology

AC拓撲的構建方法如下：對于任何覆蓋網節點對（m, n），如果沒有其他覆蓋網節點連接到節點m和n形成的物理路徑上的任何覆蓋網節點，則建立一條m和n之間的覆蓋鏈路，如圖3-4所示。雖然在構建AC拓撲時，用到了節點間的物理路徑，但沒有考慮節點間的最短路徑，即沒有考慮時延等參數。

以上的覆蓋網拓撲在構建過程中著重考慮了節點間的連接關系，而忽略選擇合理的覆蓋網節點，這必然影響路由覆蓋網的性能，因為一些節點在數據通信中起著關鍵的作用，如果在建立覆蓋網拓撲時加入這些節點，能夠提高覆蓋路由的性能，例如降低時延。