計算機網路中的匯聚樹

定義

計算機網路中給定節點的匯聚樹是由該節點與網路中所有其他節點透過最優路徑（更準確地說是最短路徑）連線而成的樹。或者，換句話說，匯聚樹是以給定節點作為目標節點，所有其他節點作為源節點形成的最小成本樹。路徑或成本的常用度量是跳數。

解釋

匯聚樹遵循最優性原理。根據該原理，在用於資料傳輸的路由器網路中，如果路由器“J”位於從路由器“I”到路由器“K”的最優路徑上，則從路由器“J”到路由器“K”的最優路徑也位於同一條路徑上。

作為最優性原理的直接結果，可以看出，從所有源節點到目標節點的一組最優路由形成了以目標節點為根節點的樹。

匯聚樹可能不是唯一的。可以存在多個具有相同路徑長度的匯聚樹。路由演算法的目標是找到網路中所有節點的匯聚樹。由於在資料傳輸過程中，鏈路和節點可能會發生故障和恢復，因此備用匯聚樹和路徑也提供給節點。

作為一棵樹，匯聚樹不包含任何環路或迴圈。因此，每個資料包都可以在有限的跳數內傳遞。此外，資料包不會在子網上無限迴圈。

示例

下圖左側顯示了一個網路，右側顯示了以節點 A 作為根節點的匯聚樹。

更新於: 2021年2月3日

5K+ 瀏覽量

啟動你的 職業生涯

透過完成課程獲得認證

開始學習
廣告