1、在互聯網中計算一個最小生成樹的簡單快速分布式算法摘要廣域網中一個核心問題是有效的多播一條消息到目標組的所有成員。一種最有效的多播一條消息的方法是沿著連接組的所有成員的生成樹的邊發送消息。本文中，我們提出一種新的全分布式算法來在一般的通訊網絡中構造一棵最小生成樹（MST）。在執行過程中，算法維系著一個跨所有組成員的不相交的樹集。每棵樹最初只由一個節點構成，每棵樹獨立的通過連接最近的樹進行擴充，直到所有節點都被連接到單棵樹中。所得到的通訊拓撲是健壯的（不會有單點遭受失敗）和可伸縮的（每個結點存儲有限數量的本地信息，這些信息與網絡的大小無關）1、引言處理在通訊網絡中構造一棵生成樹的問題通常和在廣域網

2、中設計一種有效的多播算法相關。多播操作所要求的全部帶寬是其效率的一個主要度量指標。使用一棵樹來路由多播消息的目的是減少消息傳播過程中所需要的消息數量。通常，有一些廣域網的應用（比如，計算機支持的會議，互聯網音頻和視頻多播等等）利用居于整個網絡中的代理來進行信息共享，并且這些應用屬于不相交的邏輯組。這些應用必須考慮如何有效的將信息傳播給相同組的所有成員的問題。不同的應用展示了不同的流量模式和通信量需求。這包括首要的目標是優化帶寬消耗（通過減少多播遞送方案所產生的消息數），但同時必須考慮最小化傳輸時延和或通訊鏈路上所招致的傳輸成本。在以時延作為邊的權值時，一棵最優的多播遞送樹是指樹中所有邊的權值之

3、和最小的樹。在一個給定的組中，應該使用一棵最優的多播遞送樹來路由消息。相對于流量的帶寬要求來說鏈路的容量有限時，還可以把容量約束加入到要考慮的問題中來。本文描述了在把一個一般的通訊網絡建模為一個連通圖，考慮把相鄰節點之間的傳輸時延作為度量（metric）時計算最小生成樹（MST）的一種分布式算法。構造MST是基于這樣的假設：節點可以測定發送到一個鄰節點的消息的往返時間。算法利用Bollobos的思想：在執行的整個過程中，維持著一個跨初始圖中所有節點的不相交的樹集（森林），森林中的樹通過最小權值的邊合并來擴充，直到所有的節點都被連接到單棵樹中，該樹就是最終的MST。盡管沒有考慮到流量特征和容量約

4、束，但使用其他度量來作為邊的權值也是直接的：我們假定預期流量的帶寬要求小于鏈路帶寬。然而，流量要求可以被認為是一個特定組的特征，在一個組管理算法的執行過程中，MST將可以重新配置以考慮在有多個具有高帶寬要求的組播出現時鏈路容量有限的情況。本文的剩余部分組織如下，第2節描述了MST的一般算法，第3節給出了算法的細節：初始化階段，構造階段，一個實例和算法消息的復雜度分析。第4節簡要的討論并給出了我們算法實現的測量結果。第5節是一個相關工作的最近調查。最后，第6節我們陳述了我們的結論并列出了對我們工作的一些延伸。圖1一般的MST算法2、一般的MST算法假定G（V，E）表示一個無向連通圖，這里V代表頂

5、點集，E代表邊集。然后，假定E中的每條邊關聯了一個權值并且沒有兩個權值是相等的。構造一個MST的一般算法見圖1。算法從創建V個不同的子圖開始，每個子圖包含一個頂點，接著，每個子圖獨立的選擇具有最小權值的邊（該邊把他和另外一個子圖連接起來），然后與該邊現關聯的兩個子圖沿著這條邊連接起來。步驟46重復直到所有的頂點都被連接起來。為了證明這個算法的正確性，我們需要證明在構造的過程中沒有環出現并且所得到的圖正是MST。引理1 圖1所描述的算法不會產生環。證明 開始時，每個子圖只包含一個頂點因而沒有環。對于步驟34假定不存在子圖Ti包含環，其次，假定一個由子圖Ti1,Ti2,Tik構成的子集同時選擇連接

6、邊（也就是，Ti1選擇ei1，Ti2選擇ei2,Tik選擇eik）使得產生了一個包含Ti1,Ti2,Tik中節點的環。因為每個子圖Tij（1jk）只選擇一條邊，并且要在包含Ti1,Ti2,Tik中的節點中創建一個環必須至少要有k條邊，很明顯所有的eij必須是不同的，也就是說，沒有兩個子圖選擇了相同的邊。為簡單起見，不妨設ei1連接著Ti1到Ti2，ei2連接著Ti2到Ti3,eik連接著Tik到Ti1（否則，我們可以輕易的為子圖和邊重新編號）。因為沒有兩條邊具有相同的權值，這隱含著ei1eik（否則，在步驟5，Ti1將會選擇eik而不是ei1）,ei2ei1,eikeik-1。但是從后面的k-

7、1個不等式中，我們得到eikei1,它和第一個不等式相矛盾，因而我們對可能產生環的假設是錯誤的。這樣，最后連接圖G中所有頂點的子圖是生成樹。進而由Bollobas5，我們有以下結論：定理1 由圖1中所描述的算法構造的生成樹是圖G的一棵MST，并且所得到的MST是唯一的。3、通訊網絡中的MST算法 我們把通訊網絡建模為一個無向連接圖G=（V，E）。這里節點集V代表工作站（或處理器）集，邊集E代表虛連接子集。如果兩臺工作站（節點）之間存在一條可以交換消息的通訊路徑，那么我們說這兩臺工作站是虛連接的。對每條路徑，我們關聯一個由兩個端節點之間的往返時間（RTT）所構成的權值。 MST算法分為兩個階段：

8、初始化階段和構造階段。初始化階段為圖中的每一條邊計算往返時間RTT并確保所有的權值都是唯一的。構造階段實現圖1中所給出的一般算法。以下兩節給出這兩個階段的細節。 3.1初始化階段為簡化起見，我們假定MST是作為一個外部請求的結果而被構造起來的，并且圖中的任何節點一次不能接收一個以上的請求，也就是說，MST的構造起始于一單個節點，該節點被稱為MST啟動者。在這個階段，每個節點管理以下的數據結構： adj_list-包含所有鄰節點的標識； rtt_list-包含由到每個鄰節點的RTT和計算該RTT的節點標識所組成的值對； MST算法的初始化階段見圖2。首先，啟動者節點發送一條START_MST消息

9、到其自身，接著包括啟動者在內的所有節點執行相同的代碼。當節點在第一次收到START_MST消息時，則該節點將消息轉發給除發送者節點之外的所有鄰節點（在其adj_list列表中的所有節點），并開始計算到每一個具有更小標識的鄰節點的RTT。使用這種方式，每條邊的權值只被計算一次，也就是由其具有更大標識的端節點來計算。一旦某條邊的RTT被計算出來之后，它就會和計算它的節點一起被利用一條RTT_MST消息插入到兩個端節點的rtt_list中。所有相關聯的邊的權值都被計算出來之后，節點啟動算法的第二階段。 為確保在邊的權值之間保持全序關系，我們定義在rtt_list中任意兩元素之間有以下關系： (RTT

10、i,ni)(RTTj,nj)(RTTiRTTj)or(RTTi=RTTj)and(ninj)圖2：MST算法的初始化階段3.2MST構造階段這個階段實現MST一般算法（見圖1）。首先，算法創建一個不連接的樹集，每棵樹包含一個節點（圖1，步驟1-2）。每棵樹用其節點的標識來標記（這里，我們假定每個節點都有唯一的標識）。接著，每個節點獨立的搜索具有最小權值的邊（被稱為最小橋），該邊將其和另外一棵樹連接起來（圖1，步驟4-5）。如果存在這樣的邊，則這兩棵樹被連接起來，并利用這兩棵樹中更小的標記來標記新樹（圖1，步驟6）。連接之后，具有較小標記的樹的樹根成為新樹的根。因為最開始時，每棵單節點的樹是用其

11、節點的標識來標記的，很容易看到任何新樹的標記是這棵樹的所有節點中最小標識，同時樹根是具有最小標識的節點（因此，樹的標記是其樹根的標識）。該過程重復，直到所有的節點都連接起來。 為了計算樹的最小橋，我們使用稱為COMPUTE的消息。這個消息包含兩個域：l label-樹的標記（該消息是在哪棵樹中進行傳遞的？）；l min_bridge_wt-用于計算最小橋的權值； 除此之外，每個節點還要管理以下數據結構：l label-節點所屬樹的標記；l cand_mst_heap-包含圖G中當前節點的所有屬于其它樹中的鄰節點的標識。這些鄰節點按照其權值升序存儲。l loc_min_bridge_wt-把當前

12、節點和另外一棵樹中的節點連接起來的最小權值（也就是候選MST堆中的第一個結點）。若無這樣的邊，就把loc_min_bridge_wt設為。注意最小橋的權值是該樹中所有本節點權值的最小值。l mst_adj_list-包含屬于同一棵樹中的所有鄰接點的標識。這樣，所有在候選MST堆中的節點機并上所有MST鄰節點列表中的節點集就是圖G中當前節點的所有鄰節點的集合。最小橋的計算是基于Dijkstra和Scholten10提出的擴散計算模型。根發送一條COMPUTE消息，消息中的min_bridge_wt被初始化為其自己的loc_min_bridge_wt（也就是把根和另外一棵樹中的某個節點連接起來的具

13、有最小權值的邊的權值）。每個節點在收到這條消息時就檢查COMPUTE.min_bridge_wt是否比其自身的loc_min_bridge_wt大。如果是這種情況，它就把COMPUTE.min_bridge_wt更新為loc_min_bridge_wt，并把這條消息轉發給其孩子結點。每個節點一旦收到所有孩子的應答消息之后，它就計算在所收到的消息中所有min_bridge_wt域的最小值，并把結果送回給父節點。最后，當根收到所有的應答之后，它就計算這棵樹的最小橋權值。為了闡明我們的想法，一個簡單的例子示于圖3。圖3：最小橋權值的計算。伴隨在每個節點旁邊的括號里的數字是與該節點相關聯的邊當中把該節

14、點和另外一棵樹中的某節點連接起來的具有最小權值的邊的權值（loc_min_bridge_wt），伴隨在每條消息旁邊的數字是包含在消息中min_bridge_wt的值。圖4：MST算法在計算最小橋的過程中，每個節點所執行的完整操作如下（詳細的算法描述在圖4和圖5中）：1、 根把COMPUTE.min_bridge_wt域初始化為自己的loc_min_bridge_wt，把COMPUTE.label域初始化為自己的標識。接著，根把消息送給其孩子結點并等待應答；2、 每當從父節點收到一條標記和自身標記相同的COMPUTE消息時，當前節點檢查COMPUTE.min_bridge_wt是否比自身loc_

15、min_bridge_wt大。如果是這種情況，那么COMPUTE.min_bridge_wt被更新為loc_min_bridge_wt。之后，該節點把消息轉發給其孩子結點并等待應答。如果該節點沒有任何孩子（也就是葉子節點），則把COMPUTE消息送回給父節點。3、 如果從某個鄰節點收到一條標記比自己標記小的COMPUTE消息時，當前節點就假定發送節點是其新的父節點。因而它把自己的標記更新為COMPUTE.label并繼續操作2；4、 每條標記比自己的標記大的COMPUTE消息被當前節點所忽略。5、 每當從孩子結點收到所有的COMPUTE消息之后，每個節點就計算在所收到的所有應答之中最小的min

16、_bridge_wt，并把結果送回給其父節點。如果當前節點是樹根，它就檢查所收到的min_bridge_wt是否和loc_min_bridge_wt相等。如果是這種情況（也就是最小橋在與根相關聯的某條邊中），樹根就沿著最小橋把當前的樹和其他的樹連接起來。否則，它發出一條包含所計算出來的min_bridge_wt值的DIFFUSE消息到其所有的孩子結點。圖5：COMPUTE消息處理（計算子階段）注意以上操作還執行節點的重新標記的任務。作為一個例子，考慮兩棵樹Ti和Tj剛剛被邊(vik,vjl)連接起來，這里vikTi,vjlTj,接著，假定label(Ti)label(Tj)。如果vjl轉發Tj

17、的COMPUTE消息到vik,則vik忽略該消息，因為在這種情況下，COMPUTE.label（label(Tj)）要比vik自己的標記（=(label(Ti)大。相反，如果vik轉發Ti的COMPUTE消息，那么vjl要把自己的標記更新為所收到的消息中的label域中的值，并把消息轉發給其孩子結點（步驟3），這樣，它的孩子節點依次遞歸執行相同的操作。這就確保了Tj中的每個節點都會把自己的標記更新為Ti的標記，這樣就成為了Ti的節點。同時，注意到當Tj的根第一次收到Ti的COMPUTE消息時，它就成為了發送節點的一個孩子結點并將不再為Tj產生任何其它的COMPUTE消息。這樣，Tj成為了Ti的

18、一棵子樹，這就完成了連接操作。一旦根計算出最小橋的權值，并且這個值和loc_min_bridge_wt不相等（操作5），它就啟動發送一條DIFFUSE消息到所有的孩子結點（圖4），這條消息包含和COMPUTE消息相同的域：label和min_bridge_wt。Label域包含該樹的標記，而min_bridge_wt域包含在前面所計算的該樹的最小橋權值。每當結點收到這條消息，它就檢查看是否DIFFUSE.min_bridge_wt是否和自己的loc_min_bridge_wt相等。如果相等，這就意味著最小橋在與當前節點相關聯的邊中。因此，當前的樹就沿著該最小橋和另外一棵樹進行連接。樹根送出DI

19、FFUSE消息之后，它就為新樹啟動最小橋權值的計算。注意，正如我們在前面所指出的，兩棵樹連接之后，僅僅具有最小標記的樹根完成新的最小橋權值的計算；另外一個樹根在收到一條具有更小標記的COMPUTE消息時終止，并因而成為新樹的一個簡單節點。最后一個必須處理的問題是如何檢測MST構造階段的結束。很明顯，一旦構造出了一棵MST之后，每個節點的cand_mst_heap列表變為空（因為所有的節點都屬于相同的生成樹）。因此，在MST構造好之后，最小橋的權值成為 因為沒有這樣的橋存在了。所以很自然的，當所計算的最小橋權值成為時，MST的樹根就檢測到了算法的結束。當向MST加入一條新的邊時，由最小橋的兩個端

20、節點之一調用add_MST_edge(mst_adj_list,cand_mst_search)函數。這個函數的目的是沿著最小橋連接兩棵子樹。這個任務有兩步來完成：首先，調用者從其cand_mst_search列表中刪除與該最小橋相關聯的鄰節點并將其插入到mst_adj_list列表中，接著它沿著最小橋向鄰節點發送一條特殊的消息。鄰節點在收到這條消息后就把發送節點的標識插入到其mst_adj_list列表中，同時將其從cand_mst_search列表中刪除。使用這種方式，最小橋的每個端節點都把對方的標識插入到自己的mst_adj_list列表中。注意，因為兩個端節點有可能在同時試圖相互連接，

21、所以必須小心以預防在mst_adj_list列表中的重復插入。3.3一個例子我們使用圖6中的圖為例來說明我們算法的構造階段在算法的構造階段的開始，每個節點假定自己就是一棵樹（僅由該節點所構成）的樹根并且這棵樹用該節點自己的標識來標記。接著，每個節點搜索與其相關聯的具有最小權值的邊。在我們的例子中，節點1找到邊（1，3），節點2找到邊（2，3），節點3找到邊（3，4）等等。此外，因為構造階段是異步的，從例子的角度出發，我們必須選擇一個字樹連接的順序。這個順序是任意的，也就是說，讀者可以選擇任何順序而不影響最終結果。現在假定節點4是第一個執行連接（也就是邊（3，4）被加入到MST中）的節點。由此，

22、節點4在完成連接之后，就啟動一個計算子階段，首先產生一條標記label4（根的標識）和min_bridge_wt3（也就是把節點4和另外一棵樹中的某個節點在這個例子中是節點5連接起來的一條相關聯的具有最小權值的邊的權值）的COMPUTE消息。因為節點3的標記要比所收到的COMPUTE消息中的標記小，故而該消息被節點3所忽略。反過來，節點3獨立的選擇相同的邊（3，4）來和節點4進行連接。連接之后，節點3也發出一條COMPUTE消息，不過這條消息的label=3且min_bridge_wt=2.節點4收到這條消息后，就把自己的標記該為所收到的COMPUTE消息中的標記，并成為由節點3和節點4所構成

23、的新樹中的葉子節點（圖6.b）。同樣，很容易看到因為節點4的loc_min_bridge_wt是3，COMPUTE消息中的min_bridge_wt域不被修改仍然保持為2。接著，因為節點4是剛剛形成的樹的一個葉子節點，所以它把COMPUTE消息送回給其父節點。節點3（它也是樹的根）一旦收到這條消息，就發現min_bridge_wt的值是2因而和其loc_min_bridge_wt相等。節點3因而判定邊（2,3）就是把由節點3和節點4所構成的樹和另外一棵樹連接起來的具有最小權值的邊，并且將該邊加入到MST中。注意：在這種情況下，沒有必要為了發現最小橋而發送DIFFUSE消息。接著，考慮節點2選擇

24、邊（2，3），把該邊加入到MST中，并啟動一個計算子階段：向其最近的鄰節點（節點3）發送一條label=2,min_bridge_weight=11的COMPUTE消息。因為節點3的標記label為3，比收到的COMPUTE消息中的label域的值小，故而把自己的標記改為2，成為新樹（把節點2作為樹根）的一個節點，并且把這條COMPUTE消息轉發給它的所有處于MST中的鄰節點，當然發送節點（也就是節點2）除外。同時，在轉發該消息之前，它要把消息中的min_bridge_weight更新為它的圖6：一棵MST構造的例子。節點的標識和邊的權值都是唯一的。在MST構造的不同階段，樹根由灰色的圓來表示

25、。每個節點的標記寫在括號里。loc_min_bridge_weight(5)。類似的，節點4在收到由節點3轉發過來的消息之后，就把自己的標記改為2，把消息中的min_bridge_weight改為3，接著，由于此時節點4成為了新樹的葉子節點，它就把COPUTE消息送回給節點3，再由節點3轉發給樹根（也就是節點2）。當樹根收到這條返回來的消息時，它發現消息中的min_bridge_weight值和loc_min_bridge_weight的值不等，因此發回一條DIFFUSE消息到其孩子結點。當節點3收到這條消息時，它檢測消息中的min_bridge_weight的值是否和本節點的loc_min_

26、bridge_weight相等。因為不等，所以該消息被轉發給節點4。最后節點4發現自己的本節點最小橋權值和所收到的消息中的本樹最小橋權值相等，這樣，它就選擇邊（4，5）把節點4所屬的樹和由節點5構成的樹連接起來。在例子中，我們假定節點6和節點7的連接發生在節點5和節點4的連接之前。（圖6.c.）。在以上所述的過程中，節點5和節點4連接之后，圖和部分構造的MST描述在圖6.d中。最后兩條邊（1，3）和（1，6）（圖6.3和圖6.f）加入到MST中時算法結束。3.4時間復雜度分析本節分析我們算法的時間復雜度。算法模型中假定： 1、傳播時延最多為一個時間單位； 2、所有消息，無論其類型，包含O（lo

27、gn）比特的信息，這里n為圖中的節點數。首先，我們導出初始化階段的時間復雜度結果。 引理2 給定一個具有n個節點的圖G，初始化階段要花O（n）時間。證明 首先，START-MST消息最多需要n個時間單元就會被圖G中所有節點接收（圖G中任何一條消息最長的傳播路徑為n）；其次， 每個節點必須計算到其所有鄰居的往返時間；因為每個節點最多有n-1個鄰居，計算到一個節點的往返時延需要2條消息，這個任務最多需要2（n-1）個時間單元。因此初始化任務最多需要3n-2個時間單元。 下面的三個引理決定了構建階段的時間復雜度。引理3 給定一個具有n個節點的圖G的子樹T，在T和其它另外一棵樹連接起來之前，在T的節點

28、之間最多交換O（n）條COMPUTE/DIFFUSE消息。證明 假定沒有具有不同于T的標記的COMPUTE消息被樹中的任何節點所接受。在最小橋權值的計算中，樹中的每一條邊被COMPUTE消息遍歷兩次：第一次是父節點把消息傳給它的孩子節點，第二次是孩子節點發送的應答。因為發現最小橋最多需要n-1條DIFFUSE消息（每邊一次），這樣，最多需要3（n-1）條消息就可以決定最小橋了。一旦決定了最小橋，T就可以沿著它的最小橋和其他樹合并。 其次，假定ViT收到一條標記比T的標記小的COMPUTE消息，因此，Vi成為發送節點的兒子并轉發該條新消息。此后Vi將不再發應答消息給其在樹T中的舊的父節點。因而，

29、從樹T中的至少一個節點收到收到一條標記比T的標記小的COMPUTE消息開始，任何由樹T的根發起的計算子階段都不能完成，從而樹T的根將不再發出其他消息。因此，在這種情況下，我們再一次的有樹T在最多3（n-1）條COMPUTE/DIFFUSE消息之后，就會和另外一棵樹連接起來。 最后，如果樹T中某節點收到一條標記比T的標記更大的消息時，該節點忽略掉該消息。這樣，在所有情況下最多需要3（n-1）條COMPUTE/DIFFUSE消息，樹T就能和圖G中的另外一棵樹連接起來。這證明了我們的引理3。 引理4 給定一棵具有n個節點的圖G的子樹T，在O（n）個時間單位之后，T完成和另外一棵樹的連接。證明 因為我

30、們假定傳播時間最多為一個時間單位，在T和另外一棵樹連接之前，所交換的COMPUTE/DIFFUSE相當于最多3（n-1）個時間單位。 在計算子階段，除了COMPUTE/DIFFUSE消息之外，還有其他兩種情況有消息交換。 第一：每個節點在收到一條COMPUTE消息之后，就計算與其關聯邊的最小權值本節點最小橋權值loc-min-bridge-weight）。注意，在上一次計算本節點最小橋權值loc-min-bridge-weight時，和該節點不在同一棵樹上的鄰節點在該節點的侯選mst列表cand-mst-list中，因為有可能在此過程中，該節點的侯選mst列表cand-mst-list中的最近

31、鄰節點現在和該節點處于同一棵樹中，該節點通過向鄰節點發送一條查詢其標記的消息來核實。如果該鄰節點的標記和本節點標記不同，那么本節點最小橋權值loc-min-bridge-weight保持不變，計算過程繼續。在這種情況下，對于每條COMPUTE消息，最多交換兩條消息：一條是請求鄰節點標記消息，另外一條是其應答消息。如果侯選mst列表cand-mst-list為空（也就是所有的鄰節點都和該接點在同一棵樹中），那么沒有消息交換并且本節點最小橋權值loc-min-bridge-weight為。另一方面，如果本節點標記和該節點的侯選mst列表cand-mst-list中最近的鄰節點的標記相等，這意味著這

32、兩個節點處于同一棵樹中因此該鄰節點從侯選mst列表cand-mst-list中刪除，該過程重復下去，直到發現了具有不同標記的鄰節點或侯選mst列表cand-mst-list成為空。現在，注意到可以從侯選mst列表cand-mst-list中刪除的最大鄰節點數恰好是n-1，也就是樹T中的節點數。因為這些刪除過程可以在樹T的每個節點并發執行，這相當于最多2（n-）個時間單位。 在MST計算子階段隱含信息交換的第二種情況是當所選擇的邊被確實插入到MST中時。更加確切的說，當一個節點選擇了一條將要加入到MST中的邊時，他會發送一條消息到相應的鄰節點。由此，每個節點都把其相應的臨節點插入到自己的mst臨

33、節點列表mst-adj-list中（比如當加入邊（Ni，Nj）時，節點Ni把節點Nj插入到自己的mst-adj-list，而Nj則把Ni插入到自己的mst-adj-list中）。這個任務增加了兩個時間單位，因此在從樹T構造完之時到它和另外一棵樹完成連接之時的時間間隔最多為3（n-1）+2（n-1）+2=5n-3個時間單位，這證明了我們的引理4。 給定圖G，我們定義圖G的構造樹（簡稱為CT（G）如下： 1、圖G的構造樹CT（G）的節點代表了在MST的構造過程中所產生的子樹。 2、如果T1和T2是是在子樹T的MST算法中所連接的兩棵子樹，那么T是T1和T2的在圖G的構造樹CT（G）中的父親。為簡化

34、起見，我們用CT（G）所代表的子樹的標記來標記CT（G）的節點。圖7展示了圖6中例子的CT（G）。注意：CT（G）的根是G的MST。 圖7：圖6中例子的構造樹（CT）。節點用其代表的子樹的標記來標記。引理5 給定具有n個節點的圖G，構造階段所花時間為O（n）。證明 假定T為CT（G）的根，且T1和T2為其兒子。其次再假定N1=N2，這里N1，N2各自代表了T1和T2中的節點個數。從引理1，T1在最多5N1-3個時間單位（從其被創建時開始）后，和T2完成連接。不妨給邊（T1，T）關聯一個值為5N1-3的權值。因為N=N1+N2，很容易看到（T1，T）的權值=5（N/2）-3。注意：和（T1，T）

35、相關聯的權值代表了從T1創建時刻起到T創建時刻止這段時間的一個上界。 接著，我們使用相同的方法，沿著樹向下遞歸；從當前的節點T1，我們選擇代表著具有最小節點個數的子樹T11的兒子，并且給邊（T1，T11）關聯的權值為5（N1/2）-3，這里N11是由T1所代表的子樹中的節點的個數。下一步，當前節點變成T11，過程繼續。結果，我們得到一條從T到葉子Tl的路徑，其長度代表了從Tl進入構造階段開始到最后一條邊加入到MST（也就是T被創建之時）止這段期間的一個上界。這樣，整個時間間隔的上界為： （5n/2-3）+（5n/22-3）+（5n/24-3）+25n另外，我們必須加上用于通知樹中所有節點有關算

36、法終止所需時間。因為這個任務要求最多3（n-1）條消息（每條MST的邊需要兩條COMPUTE消息和一條DIFFUSE消息），構造階段需要最多8n-3個時間單位來完成。 到目前為止，我們一直假設所有節點同時進入構造階段。如果情況不是這樣。那么在初始化階段之后，我們必須使用一條特殊的消息（類似于START-MSG）。因為圖G中最長的傳播路徑是n，在這種情況下，構造階段最多花9n-3個時間單位。 最后，從引理2到引理5我們直接得到以下結論： 定理2 給定一個具有n個接點的圖G，構造MST算法所花時間為O（n）。4 試驗結果我們已經在XTV系統2中實現并測試了我們的算法。作為這個系統的一部分，我們使用

37、生成樹拓撲把一組信息服務器連接起來，這個互連拓撲結構為發布和廣播與會議相關的信息提供了主干。當前實現的的測試和時間值是在一組二十臺DEC5000和DEC3000工作站下做的。所有的工作站都連接在相同的局域網上，所有的工作站都運行Ultrix4.2操作系統。我們通過變化組中服務器的臺數運行算法來驗證我們實現的正確性，服務器的臺數從3臺開始到20為止，對每一組實驗十次，并將結果和順行實現的Prim算法相比較。為了確保所構造的MST是真正隨機的，我們產生了偽隨機RTT的值，而不是讓網絡中反復無常的行為控制了MST的構造。在180次試驗的每次運行中，由我們的算法所構造的樹和由Prim算法生成的樹是一樣

38、的。為了測試算法的性能，我們在節點的個數從1個變化到20個的情況下分別執行該算法，對每種情況測試10次。在每種情況下，我們都考慮一個全連接的圖，也就是說每臺服務器的鄰節點列表（adj_list）由所有其他的服務器構成。稍后，我們將推導出我們算法在最壞情況下的時間復雜度，并且我們將指出如何將其與真實的測量值作比較。正如我們在第3節時間復雜度分析中所指出的，初始化階段最多需要3n-2個時間單位（見引理2的證明），構造階段最多需要9n-3個時間單位（見引理5的證明），這導致了整個算法在最壞情況下的總的時間復雜度為12n-5。現在回想以下，在我們的分析中，都假定任何消息的傳播試驗最多為一個時間單位。因

39、此在這種情況下我們選擇試驗中所測量的最大傳播時延（表示為tmax）來作為時間單位。這樣，我們的算法在最壞情況下，構造一個具有n個節點的圖的MST最多需要(12n-5)tmax的時間。圖8展示了實際上測量的時間（多每次實驗）對最壞情況的估計時間。可以看到，在所有情況下所測量到的時間都在預期的最壞情況時間之下。盡管我們的結果是在局域網中獲得的，但是我們可以期望在廣域網中結果至少是差不多的。因為在我們的簡化模型中所忽略的象消息處理時間和計算時間這樣參數，在出現廣域網中所經歷的相當大的傳播時延這種情況下，這些時間的意義要小得多。圖8：我們的MST算法的測量值對所期望的最差情況時間值。算法在服務器的臺數

40、從2臺到20臺的每種情況各執行10次試驗。5 相關工作以前在通訊網絡中分布式計算一棵MST的理論方案是基于Gallager,Humblet和Spira所提出的算法。這個算法利用相同的思想；它以所有節點都為子樹開始，重復的沿著他們最小權值的邊進行連接，直到一棵MST被構造出來。這個算法具有的消息復雜度為O（nlogn）(這是最優的)時間復雜度為O（nlogn）。為了獲取消息最優，在兩棵樹連接時實施了一些規則，每棵子樹具有一個相關聯的層次數L，以使得子樹中的節點個數2L（只有單個節點的子樹的層次數為0）。假定一棵具有L層的子樹T找到一條最小權值的外出邊，該邊將它和另外一棵具有L層的子樹T連接起來。

41、那么，僅當LL時T和T連接，否則T等待直到T足夠大為止。這個算法后來的改進減少了時間復雜度到了O（nlog*n）進一步又到達O（n）（它是最優的），但不幸的是，這是以增加算法的復雜性為代價的。盡管這個算法的理論價值是毋庸置疑的，但它的復雜性使得其在實現起來相當困難。作為一種可供選擇的辦法，我們設計并實現了一個盡管在消息的個數上不是最優的但卻是簡單的和時間最優的算法。我們這種以消息復雜度換取時間復雜度的決定被互聯網中的應用類型證明是有道理的，在這些應用中，對終端用戶來說，響應時間往往是要比消息交換的數目更為重要。多播問題的實際解決方案是基于以前曾經用在分布式路由算法中的方法18。當前存在的IP多

42、播構架的解決方案主要是距離矢量路由（DVMRP：距離矢量的多播路由協議）和鏈路狀態算法（LSMRP：鏈路狀態的多播路由協議）的擴展。在14中提出了一種對開放最短路徑鏈路狀態協議（OSP）的擴展。這些算法的主要缺點是伸縮性問題：路由遞送樹的計算是基于原點的，它要求潛在的涉及到要為所有現存的組路由消息的每臺路由器為所有潛在的多播源存儲路由信息。這導致了一個和（源點，組）對的個數成比例的伸縮因子。在廣域網的環境中，動態的計算以源為基礎樹成為路由節點一個繁重的計算任務。為每個組使用單個把屬于相同多播組的所有節點都連接起來的多播遞送樹而不是使用基于源的樹有可能被看作是IP網絡中多播路由的一個可能的解決方案。在17中提出了一種在廣域網中構造生成樹的分布式算法。因為該算