Journal of High Speed Networks 15（2006）123-130 Destination-driven shortest path tree algorithms Baoxian Zhang and Hussein T. Mouftah Journal of High Speed Networks 15（2006）123-130 Hussein Mouftah is a Tier 1 Canada Research Chair and Professor in the School of Information Technology & Engineering at the University of Ottawa. He is also an Adjunct Professor in the Electrical & Computer Engineering Department at Queen's University. Baoxian Zhang任職於北京的graduate university of the chinese academy of sciences(中國科學院研究生院)的college of software engineering。 而Hussein Mouftah是任職於渥太華的university of ottawa的school of information technology and engineering。 他們也都曾經任職於加拿大的queen’s university(英國女王大學)，因此我猜這篇paper應該是出自於當時。 Presented by Tzu-Cheng Hsieh, OPLab, IM, NTU 2007/3/26

Agenda Introduction Destination-driven shortest-path algorithm（DDSP） Algorithm for building cost-effective destination-driven trees Simulation results Conclusion 2018/12/2 OPLAB, IM, NTU

Introduction Shortest Path Tree（SPT）is the most widely used type of tree for multicast provisioning. However, SPTs have not considered efficient resource utilization in their constructions. The work aims at constructing cost-effective SPTs to enhance link sharing. 一般來說multicast通常都是利用shortest path tree來達成。 不過，shortest path tree並沒有在路徑的選擇上考慮有效的資源利用。 因此，這篇paper希望能提出一套具有成本效益的shortest path tree algorithm來提高link sharing 2018/12/2 OPLAB, IM, NTU

Agenda Introduction Destination-driven shortest-path algorithm（DDSP） Algorithm for building cost-effective destination-driven trees Simulation results Conclusion 2018/12/2 OPLAB, IM, NTU

DDSP（1/7） Note that all link costs are equal to one. s：source di：destination s d1 d2 s d1 d2 假設這個網路拓撲的每條link皆為1單位cost。 s為source node，d sub i為destination node。 因此shortest path有這兩種走法。 我們會發現同樣皆為shortest path tree，左邊的multicast的cost為4單位，而右邊的multicast的cost為3單位。 是因為右邊的d sub 2利用了這條link，因此只需要額外2單位的cost就可以連結到d sub 2，作者就是希望能夠提高link sharing來降低multicast的cost。 cost = 3 cost = 4 2018/12/2 OPLAB, IM, NTU

DDSP（2/7） When Equal Cost Multiple（shortest）Paths（ECMP）are available, priority is given to the route among these paths, on which a destination of the group sits. When multiple such routes are available, on each of which one or more destinations sit, priority is given to the one incurring the minimal extra cost. 因此DDSP的目的是希望當相同cost的路徑可以選擇時，去挑選具有destination node的path。 而當多條路徑上皆有destination node時，是去挑選destination node之間相離最近的那條path，因為這條path會享有較大的link sharing帶來最小的cost。 2018/12/2 OPLAB, IM, NTU

DDSP（3/7） Note that all link costs are equal to one. s：source di：destination 2 s d1 d3 d2 s d1 d3 d2 1 例如這個網路拓撲，d sub three有上下二條path可以選擇，並且二條path皆含有destination node。 左邊的shortest path的cost為5單位，而右邊的shortest path為4單位。 是因為d sub 1到d sub 3需要花2單位的cost，而d sub 2到d sub 3只需要花1單位的cost。 也就是說，左邊的shortest path只省下了1單位link sharing的cost，而右邊的shortest path可以省下2位link sharing的cost。 cost = 4 cost = 5 2018/12/2 OPLAB, IM, NTU

DDSP（4/7） DDSP works in a manner very similar to Dijkstra’s SPT algorithm. Notations G The directed graph of a communication network V(G) The set of all nodes in G E(G) The set of all links in G C(i,j) The cost of the link (i,j) s The source node DDSP algorithm與dijkstra algorithm很類似，只是多了幾條指令。 這裡先介紹一些notation的定義。 G是代表網路拓撲的圖。 V of G是代表G中的nodes集合。 E of G是代表G中的lins集合。 C of i j是代表link i j 的cost，也就是node i 到node j 的cost。 小寫s是代表souce node。 2018/12/2 OPLAB, IM, NTU

DDSP（5/7） Notations（Cont.） S The set of all destinations CST[i] The accumulated cost of the computed path from s to i, i∈V(G) rCST[i] The accumulated cost from the nearest destination to node i along the computed path Adj[i] The set of adjacent nodes of node i, i∈V(G) π[i] Predecessor of node i Q A min-priority queue sorted in the increasing order of CST[．] 大寫S是代表destinations node的集合。 CST of i 是代表從source node到node i 的累積cost。 rCST of i 是代表從最近的destination node到node i 的累積cost。 Adj of i 是代表node i 的鄰居node。 pi of i 是代表node i 的父節點。 Q是針對每個node的CST遞增的queue，也就是CST較小的node排越前面。 2018/12/2 OPLAB, IM, NTU

d1 s y d2 x (∞,∞) (1,0) (0,0) (∞,∞) (2,1) (∞,∞) (3,0) (2,2) (∞,∞) (1,1) 這就是DDSP的algorithm，大部分與dijkstra algorithm是類似的，唯一多加的地方也是DDSP精神所在的地方是這三行。 CST相同時，也就是當shortest path有多種選擇時，會去比較rCST，也就是會去比較這些path上的destination node何者最近，並選擇這條path來傳送資料。 從圖來說明，首先先從source node來處理，左邊的數字代表CST，右邊的數字代表rCST，從dijkstra algorithm可以先算出d sub 1及x這二個node的資料。 接下來由d sub 1算出node y的資料。然後再由node x算出node y的資料為2 2，可以發現走上面的path只需要額外1單位的cost，而走下面的path需要2單位的cost，因此algorithm會選擇上面那條path。 最後再由node y算出d sub 2的資料並完成routing的動作。 2018/12/2 OPLAB, IM, NTU

DDSP（7/7） The computational complexity of DDAP is if Fibonacci heaps are used to implement the priority queue operations, where and represent the number of links and nodes in the network, respectively. 由於這個algorithm類似於dijkstra algorithm，因此時間複雜度為link個數加上node個數，而若使用費不納級數來排序的話，所花的時間為v lg v，因此總共的複雜度為e + v lg v。 2018/12/2 OPLAB, IM, NTU

Agenda Introduction Destination-driven shortest-path algorithm（DDSP） Algorithm for building cost-effective destination-driven trees Simulation results Conclusion 2018/12/2 OPLAB, IM, NTU

Algorithm for building cost-effective destination-driven trees（1/6） For a tree built by using DDSP, each node is restricted to be connected with the source node via a shortest path. Relaxing this restriction can lead to a significantly reduced tree cost. 剛剛所介紹的DDSP仍然是屬於shortest path tree的一種，也就是每一個node與source node之間皆為shortest path。 作者希望透過relax這個shortest path的限制，提出一個cost-effective的algorithm來降低cost。 2018/12/2 OPLAB, IM, NTU

Algorithm for building cost-effective destination-driven trees（2/6） Note that all link costs are equal to one. s：source di：destination s d1 d2 s d1 d2 從這個網路拓撲來看，左邊的path為DDSP所run出來的shortest path tree。 而右邊的path並不是shortest path tree的multicast path。也就是從source node到d sub 2的shortest path為3單位，而右邊的path卻花了4單位才到d sub 2。 可以發現左邊的shortest path tree所花的multicast cost為5單位，而右邊不是shortest path tree但所花的multicast cost為4單位。 作者希望能relax shortest path的限制來提高link sharing進一步降低cost。 3 4 cost = 4 cost = 5 2018/12/2 OPLAB, IM, NTU

Algorithm for building cost-effective destination-driven trees（3/6） According to the algorithm, each group member can connect to the source via a path with a length at most H longer than the length of the shortest path connecting the source and that group member. Here, H is a small positive constant and is refered to as path length constraint. 根據這個作法，每一個node與source node之間的path會大於shortest path最多H單位的cost。 由這個graph來說，也就是每一個node與source node之間的path會大於shortest path最多1單位的cost。 這個1單位的cost，也就是H，在這篇paper裡稱作path length constraint。 2018/12/2 OPLAB, IM, NTU

Algorithm for building cost-effective destination-driven trees（4/6） The algorithm for building cost-effective destination-driven trees employs the strategy of farthest-first. That is, the node with a longest distance away from the source has priority over others to be chosen. The algorithm requires DDSP to run first. 一般來說，shortest path algorithm都是從source node開始作處理，但是這個algorithm是利用farthest first的處理方式。 也就是先處理離source node最遠的那個node。 而這個algorithm需要DDSP先run過。 2018/12/2 OPLAB, IM, NTU

Algorithm for building cost-effective destination-driven trees（5/6） Q： d2、d1 z、d1 d1 w (1,1) (2,0) (3,1) s d1 x z y d2 w (0,0) 1 2 (1,1) (2,2) (3,0) 這就是作者所提出的cost-effective algorithm，其中最重要的地方是這幾行。在這裡直接利用圖來說明。 這張圖是先經由DDSP所run出來的結果，此時先將destination node放入queue中，這裡的queue是依CST遞減來排序，並且此後routing會經過並且未處理的node皆會放入queue中。 首先先從離source node最遠的d sub 2開始處理，先檢查鄰居node是否存在於queue中，也就是檢查鄰居node是否會被routing到，此時並沒有，因此保留原來的path。並將queue改為z d sub 1。 接下來處理node z，發現d sub 1存在於queue中，也就是routing會經過的node，此時則比較d sub 1到node z的cost是否小於原本node z所必須要花的cost，也就是比較cost of y x和rCST of x，在這裡從d sub 1到node 1的cost只須要花1單位的cost，而不須要花到DDSP所計算出來的2單位的cost，因此選擇d sub 1到node z的這條path。 此時對d sub 1作處理得到這條path，再對node w作處理得到這條path，就完成了routing的動作。 這裡很明顯的source node到d sub 2的path並不是shortest path，但卻省下了1單位的cost。 2018/12/2 OPLAB, IM, NTU

Algorithm for building cost-effective destination-driven trees（6/6） Thus the overall computational complexity of the algorithm is , which is the same to that of DDSP. 而這個algorithm的時間複雜度也是e+v lg v。 2018/12/2 OPLAB, IM, NTU

Agenda Introduction Destination-driven shortest-path algorithm（DDSP） Algorithm for building cost-effective destination-driven trees Simulation results Conclusion 2018/12/2 OPLAB, IM, NTU

Simulation results（1/5） In all the simulation, the cost of each link was set as one. The paper called the algorithm for building cost-effective destination-driven trees as DDSP-H, where H is the maximum number of extra hops. In this simulation, the paper investigate the quality of a multicast tree generated by using DDSP-0(DDSP), DDSP-1, and Dijkstra’s SPT algorithm, respectively. 在這個simulation中，作者將每條link的cost皆設為1單位。 為了方便起見，這篇paper將剛剛所介紹的第二個algorithm稱作DDSP-H，其中h是path length constraint。也就是source node和node間所選擇的path最多只能比shortest path多付出h單位的cost。 而在這個simulation中，作者分為針對DDSP-0，也就是DDSP，DDSP-1和Dijkstra’s algorithm所產生的multicast cost來作比較。 2018/12/2 OPLAB, IM, NTU

Simulation results（2/5） The paper define the inefficiency of an algorithm x as the difference between the cost of the tree built by algorithm x and the cost of the tree built by DDSP-1, normalized to the cost of the tree built by DDSP-1. The paper obtained results for different group sizes, network sizes, and average node degree. 而simulation的內容是以DDSP-1為基底，分別比較DDSP-0和dijkstra algorithm對DDSP-1的cost ineffciency，成本無效性。 且分別針對不同的group size、network size和average node degree來作比較。 2018/12/2 OPLAB, IM, NTU

Simulation results（3/5） 第一個是在不同的group size下作比較，縱軸是多花的cost百分比。其中network size設為100，average node degree設為4。 在這個環境下，由於group member越少，相同cost的path當中存在destination node的probability比較小，也就是能獲得link sharing的機會較小，因此差異較沒那麼大，而隨著group member的增加，差異性才會越來越大。 2018/12/2 OPLAB, IM, NTU

Simulation results（4/5） 接下來是在不同的network size下作比較。其中將group size設為15，average node degree設為4。 在這個環境下，當network size存在50個node時DDSP-1的效益最好。 因為當network size有25個node時，destination node的分怖是非常密集的，因此若不使用DDSP-1，還是可以很容易選到有destination node的path來提升link sharing，因此差異性較不明顯。 而當network大於50個node時，destination node的分怖又過於稀疏，因此相同cost的path當中存在destination node的probability比較小，link sharing的機會相對較小，因此差異性也較不明顯。 2018/12/2 OPLAB, IM, NTU

Simulation results（5/5） 接下來是在不同的average node degree下作比較。其中group size設為15，network size設為100。 由於average node degree越大，相同路徑的選擇也越多，相對來說能夠link sharing的機會也越大，因此差異性會越來越大。 2018/12/2 OPLAB, IM, NTU

Agenda Introduction Destination-driven shortest-path algorithm（DDSP） Algorithm for building cost-effective destination-driven trees Simulation results Conclusion 2018/12/2 OPLAB, IM, NTU

Conclusion In summary, the DDSP-family algorithms outperform Dijkstra’s algorithm in terms of cost performance. Further, DDSP-1 outperforms DDSP-0 due to its relaxation in the end-to-end path length for enhanced link sharing capability. Further increasing the value of H brings insignificant improvement in cost performance. 總結來說，DDSP的cost performance較dijkstra algorithm來得好。 而其中DDSP-1的效能又較DDSP-0來得好，因為relax掉shortest path的限制。 也就是說，隨著path length constraint H的增加，帶來的效益也越高。 2018/12/2 OPLAB, IM, NTU

The End. Thanks for your listening! 2018/12/2 OPLAB, IM, NTU