基于流言協議的覆蓋網拓撲管理

卞強 劉永成 苗信凱 吳海強

（中國電子科技集團公司第十五研究所 北京市 100083）

1 引言

近年來隨著網絡應用的不斷發展，越來越多的分布式應用系統得到了大規模的應用。每個節點既是客戶端也是服務端，在整個網絡范圍內形成一個無中心的分布式應用系統。這種系統帶來的最大的好處是，單個節點的失效不會對整個應用造成致命的影響。然而，隨著系統規模的逐漸擴大，各個節點組成的網絡拓撲逐漸復雜起來。從某個節點的視角來看，很難在某個時刻實時掌握整個分布式系統的網絡拓撲，從而對該節點向其他節點的數據同步和其他通信造成困難。流言協議在分布式系統的各個方面的應用都得到了研究，Tao Yu 等人[1]進行了基于流言協議的分布式共識評估和控制的研究，提出了疊加共識策略的本地類龍伯格觀測器，驗證了通過流言協議進行分布式共識評估的可行性。Pengfei Ren 等人[2]研究了基于流言的分布式學習問題，在隨機加入網絡拓撲的節點間進行數據隨機路由，最終在所有節點間形成構建相同的理論學習模型，通過這項研究驗證了基于流言協議的數據分發的穩定性。Istvan Hegedus等人[3]對基于流言的機器學習和聯邦機器學習進行了比較，經過實際試驗結果發現，在實際的網絡環境中，在機器學習中通過流言進行數據和策略的分發以及進行學習結果的匯聚要比聯邦機器學習更有效，驗證了流言協議在分布式環境下進行數據分發和匯聚的有效性。Mauro Franceschelli 等人[4]在異構隨機網絡中進行了有質量保證的任務分發研究，探討了在任務分發中的收斂特性，以及對各個節點組成的無向圖的邊選擇方法，以及最終的流言通信的終止。通過數值模擬驗證了相關理論的正確性，整個通信過程都是在保證任務分發性能的前提下進行的。

2 流言協議介紹

流言協議又稱流行病協議，是一種去中心化的分布式協議，用于實現分布式節點間的信息交換，一般用于大型的無中心化網絡環境中，并且假設網絡環境不太穩定。流言協議是分布式系統中被廣泛使用的一種最終一致性協議，可以使用流言協議來實現分布式網絡中所有節點數據的一致性同步。流言協議最初是由施樂公司帕洛阿爾托研究中心的研究員Alan Demers 于1988年提出的[5]。最初用于分布式數據庫中各節點間進行數據同步，后被廣泛用于數據庫復制、消息分發、大型集群的成員節點身份確認、大型集群的節點故障探測等[6～8]。

對于具有N 個節點的網絡，流言協議發送消息的收斂時間為O(logN)。每個節點僅發送固定數量的消息，并且與網絡中節點數目無關，因此整個網絡的收斂時間不會隨著網絡節點的增多而增大。在消息傳送過程中，發送節點不會等待被發送消息的應答消息到達后才進行其他工作，允許存在一定節點發送的失敗，但需要保證不小于扇出系數的發送成功量。在整個發送過程中，逐漸形成按照指數遞增的節點同時向外發送消息，因此系統可以輕松擴展到數百萬個節點。流言協議是去中心化的應用層網絡協議，所有節點都是地位對等的，沒有特殊的節點，網絡中任何節點的重啟或者宕機都不會影響流言協議的運行，整個系統具有很要的健壯性。系統中任何一個節點都可以隨時加入或離開，從整個系統的角度來看這些節點的加入和離開不會影響系統的整體服務質量。在大規模分布式系統中，流言協議通過消息的指數級快速傳播，將新消息快速地發送到全局的每一個節點，在有限的時間內能夠做到所有節點都擁有最新的數據。為了避免整個系統的廣播風暴，使消息傳播能夠最終停止，流言協議采用了SIR 模型[10]，通過“已刪除”狀態來標記已經處理過的消息，當節點收到的消息處于“已刪除”時，該節點將不再傳播該消息。根據 Ganesh 等人的研究[6]發現，在一個擁有N 個節點的分布式網絡系統中進行消息發送，若每個節點平均與logN+c個節點發送消息，那么原始消息發送至系統所有節點的概率將收斂至exp(-e-c)。這說明如果每個節點對外散播流言消息的扇出系數大于logN，則系統中所有節點都能夠收到原始消息的概率趨近于1，反之則趨近于0。Ganesh 等人的研究成果從理論上找到了基于流言機制進行消息隨機散播的可靠性條件。

3 覆蓋網拓撲同步機制

覆蓋網是一個構建在物理網絡之上的應用層虛擬網絡，Ranieri Baraglia 等人[11]通過覆蓋網構建了內容推薦系統。在覆蓋網中，各個節點是對等的，無中心的，隨時可以加入網絡和退出網絡，其形態具有動態性。為了掌握變化中的覆蓋網的形態，需要一種分布式的穩健的拓撲管理方法。傳統的泛洪協議具有簡單和可靠的特點，但隨著網絡規模的增長其收斂時間將會增大?；诹餮詤f議的拓撲管理方法利用流言的特點在覆蓋網中分發信息，其分發機制采用概率模型。每次進行消息分發時，按照扇出系數選擇部分節點進行分發，接收節點收到消息后，將其已知的部分網絡拓撲發送給發送節點，同時又作為消息發送者繼續進行消息分發。這樣，最終在每個節點形成一個動態的全局網絡拓撲。通過調整扇出系數和發送消息的時間間隔，實現對整個分布式系統穩定性的提升。每個節點可以自由加入和退出覆蓋網，在新節點加入覆蓋網時，需要至少配置一個已知節點，向已知節點發送上線消息。節點退出覆蓋網有兩種情形，一種是節點正常退出，在退出時向其他節點發送下線消息，這種情形的處理方式與節點上線類似；另外一種是異常退出，例如，機器宕機、服務奔潰或底層物理網絡產生故障，以下對整個通信過程進行描述。

（1）新節點加入。新節點m 加入分布式網絡系統時，節點m向系統中至少f（f 稱為扇出系數）個節點（假設節點n）提交注冊請求消息msg_r(m)。節點n 收到節點m 的注冊請求消息msg_r(m)時，首先將節點m 信息添加到自己的局部網絡視圖V(n)中，生成V(n+m)，同時發送一個自己已知的局部視圖V(n)發送給節點m。然后將注冊申請的節點信息N(m)轉發給其本地視圖中的每一個成員，同時生成c（稱為扇出系數）個注冊請求信息，并將其隨機轉發至本地網絡拓撲視圖中的c 個成員(n1,n2,…,nc)。c 是一個控制參數，主要用來增強系統的容錯性能，使新節點的信息能在系統中多個節點的局部視圖中存在。當網絡系統中某個節點(n1,n2,…,nc)收到轉發來的注冊請求消息時，它會以一定的概率p 接受這個注冊請求，概率p 的大小依賴于節點本地視圖的大小，然后將注冊消息隨機從本地視圖V(nc)中的選擇c 個成員進行轉發。

（2）節點正常退出。當網絡系統中某個節點m 需退出系統時，則在退出前向系統中至少一個節點（假設節點n）發布一個節點注銷流言消息msg_o(m)，消息msg_o(m)首先廣播至節點n 的局部視圖V(n)中的c 個節點(n1,n2,…,nc)。當網絡系統中的節點(n1,n2,…,nc)收到注銷流言信息msg_o(m)時，若節點的局部視圖V(nc)中包含有發送注銷消息的節點信息N(m)，則首先在局部視圖V(nc)中將其刪除，生成V(nc-m)。隨后將此注銷消息msg_o(m)隨機散播給其局部視圖中的其他節點；若節點的局部視圖V(nc) 中不包含節點信息N(m)，那么僅進行消息的散播。在沒有網絡節點失效及網絡鏈路故障的情況下經過一定輪次后，系統中每個節點都收到該注銷消息，保證了分布式系統中節點視圖的一致性。相關研究[12]表明，當70%以上的節點退出后依然可以保證系統的連接性。

（3）節點異常退出。因網絡故障或服務宕機等其他原因導致節點m 退出分布式網絡系統時，其他節點無法收到其注銷消息。這就需要每個節點對其已知的網絡拓撲進行心跳探測，設定探測周期為T，T 的大小取決于對網絡拓撲實時性的要求。當某個節點n通過心跳探測發現其局部視圖V(n)中的節點m 異常時，則向其他節點發布一個異常退出流言消息msg_q(nm)，經其他至少x 個節點確認后，則刪除其本地視圖V(n)中的節點m，更新為V(n-m)。x的值需根據網絡質量q 以及使用覆蓋網拓撲的其他應用對于覆蓋網拓撲可靠性要求r 來設定，即x=f(q,r)。

當節點出現異常退出時，可能服務本身出現了問題，也有可能是網絡出現了問題，此時需要防止整個網絡發生腦裂。在覆蓋網拓撲的管理中，由于每個節點只存儲局部拓撲視圖，且后續的數據同步需要依賴覆蓋網拓撲進行，既便發生暫時性的腦裂，后續的持續探測和隨機的流言分發機制會重新探測到發生腦裂的局部節點。

（4）廣播風暴的避免。在流言消息的分發過程中，為了保證消息發送的可靠性和傳播的時效性，一般會選擇扇出系數f>1，此時發送消息的節點數量呈指數級增長。為避免形成覆蓋網廣播風暴，通過對接收到的流言消息進行標記來阻斷消息的重復發送。以節點a、b、c、d、e 為例，如圖3 所示，節點a 向節點b 發送了消息msg。

節點b、d 的本地視圖為V(b)={a,c,d,e},V(d)={a,b,c,e},

假定扇出系數f=3。節點b 收到消息msg 后，將消息分發給其本地視圖V(b)中的節點a、c、d，節點a 已將msg 標記為重復消息，將不再繼續分發流言。節點d 繼續分發流言，將消息分發給其本地視圖V(d)的節點b、c、e，節點b、c 已將msg 標記為重復消息，將不再分發流言。

（5）防止惡意節點的攻擊。在分布式網絡系統中，各個節點之間的連接是松散的，并且不存在中心節點，這種結構容易被惡意節點攻擊，造成覆蓋網拓撲的損壞。Anubhava 等人采用基于概率的流言模型，通過在每個節點引入控制表以及能力分發指數來實現對惡意節點的探測和分析，通過仿真驗證分析取得了較好的結果。在一些分布式異構網絡中，組建覆蓋網的各個節點所處的底層鏈路的不同物理介質的穩定性存在差異，同時骨干網絡和支線網絡其穩定性也存在差異。在這種情況下，可以采用Anubhava 等人的基于概率的流言模型，對每一個節點i 被新加入節點的連接概率Pi進行有傾向性的控制，即：

其中ηi 為節點的能力分發指數，ki 為節點所擁有可連通的鄰居節點的數量L(t)為其所有的鄰居節點?？梢愿鶕煌濣c的網絡類型對α 和β 進行調整，實現對惡意節點攻擊的防止。

4 結論

綜上所述，通過流言協議進行分布式網絡覆蓋網的拓撲管理，可以管理新節點的加入、退出。通過引入SIR 模型，解決了流言分發的網絡風暴，在流言模型中引入能力分發指數概率模型，解決惡意節點的探測和分析，保證不會因惡意節點的擾動對整個覆蓋網拓撲造成影響。本文中每個節點只存儲覆蓋網的部分拓撲視圖，符合實際應用場景中對覆蓋網的要求，同時也減小了拓撲維護過程中所帶來的網絡開銷。從流言協議的理論模型分析了流言傳播的收斂時間和分布式網絡規模之間的關系，從理論上驗證了對多達上千個節點的分布式網絡中運用流言協議的可行性，后續還需通過數值模擬定量分析在實際網絡中流言協議對拓撲管理的可靠性，尤其是當某些節點頻繁上下線時。