MPH 算法是一種啟發式的求解近似最小成本組播樹的算法。
基本介紹
- 中文名：MPH算法
- 外文名：Minimum Path Cost Heuristic
組播,問題模型,算法過程,複雜度,其他算法,
組播
在傳送者和每一接收者之間實現點對多點網路連線。如果一台傳送者同時給多個的接收者傳輸相同的數據，也只需複製一份的相同數據包。一個節點傳送一個信息包到一個組地址，路由器動態的保持這一組主機的信息並建立組播樹，給出一個傳送者到所有接受者的路徑。組播生成樹為數據組播時在網路里經過的路徑。
MPH 算法是一種啟發式的求解近似最小成本組播樹的算法。
問題模型
為簡化問題，首先將一個通信網路表示為一個帶權無向圖G=(V,E,C)。（V表示網路中的節點集合，E是邊（代表節點間的通信鏈路）的集合，C是各邊對應的費用的集合）。設G中共有n個節點，記為vi（i=1,2,……,n），圖中的邊標記為<vi,vj>(1≤i≤j≤n)，每條邊的成本標記為cost(<vi,vj>)，則G的成本為∑<vi,vj>∈E cost(<vi,vj>)。
在多播網路中數據由源節點s∈V生成，並傳送給多播組中的所有成員，不妨假設多播組成員的節點集合（即端節點集合）為M，M⊆V，其中共有m個元素。規定算法為以源節點為根的生成樹。
節點vi，vj之間的最短路徑：節點vi，vj之間的路徑中各邊成本和最小的一條路徑。
節點到樹的最短路徑：該節點到樹中各節點的最短路徑中成本最小的路徑。
Steiner節點：多播樹中源節點s和M中任一端節點以外的結點（其作用為使得多播組中的節點相連後成本最小）。
最小成本組播樹：無向圖G的源節點為s，端節點集合為M（共有m個元素）。G的一個子圖（樹）T=<Vt,Et,Ct>，VtV，EtE，CtC，若滿足源節點s到其他任何一個端節點存在一條路徑，且除s點入度為0，其餘節點入度為1；端節點的出度大於或等於0，Steiner節點的出度大於或等於1，則T是關於s和M的組播樹。組播樹的成本是從源節點s到所有端節點的各邊費用之和。這些組播樹中成本最小的樹為最小成本組播樹。
算法過程
① 假設T=<Vt,Et,Ct>為部分組播樹，初始化為只包含源節點s，此時Vt={s}, Et=Φ,Ct=Φ。
② 在餘下的端節點M-Vt中搜尋出到最小生成樹T的路徑最短的端節點u（若有多個符合條件則任取一個即可），將從u到T的最短路徑併入生成樹T（端節點u及路徑上的所有節點併入Vt,該路徑上的邊併入Et，對應邊的費用併入Ct）。
③ 重複②至M中的所有節點都包含到Vt中，產生的T為近似最小成本組播樹。
複雜度
① 對每一個即將加入到部分組播生成樹T的端節點，最壞情況下需m*n次比較才能選出當前的最短路徑，則T中的m個端節點逐個加入需要進行m2n此比較。
② 將選定的端節點到樹T的最短路徑上的節點加入到生成樹中的次數最多是n。
③ 將該最短路徑上的邊加入到生成樹中的次數最多是圖的邊數總數e。
所以MPH算法的時間複雜度為O(m2n + e)。
其他算法
1. 集中算法（顯示路由算法、源路由算法）：源節點計算出從源端到目標節點的整個組播樹。如 MOSPF 協定中使用 Dijkstra 算法計算以該數據報源端為根的最短路徑樹。
2. 分散式算法：組播樹的計算由位於不同網路中的多個路由器協作完成。如PIM-SM 協定。
3. 近似算法：以多項式時間解決最佳化問題並保證能夠得到接近最佳化解的近似解的算法。如：KMB 算法。
4. 啟發式算法：採用某個啟發式函式或啟發式規則對計算步驟進行限制，不保證一定能夠找到可用解，但設計性好的啟發式算法常能得到接近最優的解，且具有相對低的時間複雜度。
