Enhancing Multicast Routing for Software-Defined Networks

Reliable Multicast Routing for Software-Defined Networks

Introduction (1/7) Unicast Video services via unicast suffer from high server and network loadKeep one connection for each client high server load Each stream occupy bandwidth high network load

Introduction (2/7) Multicast Multicast reduces the load of both servers and networks Support more clients with the same resources The load of the server is reduced More clients can be served The load of the network is reduced

Introduction (3/7) Reliable Multicast Reliable transmission is desired by some applications Video services such as MPEG DASH Sender handles recovery high recovery cost Middle nodes handle recovery where to place the recovery nodes Recovery Packets Acks Acks Place a recovery node Acks Save BW and latency

Introduction (4/7) Multicast with SDN Multicast traffic engineering for SDN? Shortest-Path Tree (SPT) in Internet Employ OSPF unicast routing, no traffic engineering Minimize an end-to-end cost Difficult to efficiently reduce the total bandwidth consumption Steiner Tree (ST) in Graph Theory Minimum resource consumption (# of edges in T) Does not consider the selection of the recovery node Difficult to facilitate local loss recovery 5

Introduction (5/7) Recover-Aware Steiner Tree Reliable multicast Each destination is assigned a recovery node to recover loss packets Recovery nodes cache packets and monitor transmission for destinations The total costs include tree and recovery cost Proposed Recover-Aware Steiner tree (RST) Reduce both tree and recovery costs Objective: minimize (tree cost + recovery cost) : weighting factor for recovery cost

Introduction (6/7) Tree and Recovery Costs D = {1, 2, 3, 4, 5, 6, 7}, C = V, r = 2, R = {7, v} , w(T) = 39 Then c(T) = 36 s s s 3 3 9 9 par(v) = s w(Pv) = 3 + 8 = 11 w(P1) = 2 w(P2) = 3 7 7 u u w(P3) = 1 w(Pv) = 11 8 8 5 5 2 2 w(P4) = 5 w(P5) = 3 w(P6) = 5 w(P7) = 9 v v 2 2 1 1 w w 6 6 3 3 1 1 1 1 3 3 2 2 4 4 5 5 par(2) = v w(P2) = 1 + 2 = 3 2 2

Introduction (7/7) Comparison (b) Shortest-path tree Tree cost = 40 Recovery = 58 (a) Original Network (c) Steiner tree Tree cost = 22 Recovery = 66 (d) Recover- aware Steiner tree Tree cost = 25 Recovery = 32

Related Works Few current works in SDN community address multicast traffic engineering Current reliable multicast approaches (RMTP-II, PGM, NORM) focus on minimizing the number of ACK and NAK messages None of them consider the selection of recovery nodes Can not minimize recovery costs

Main Contributions Observe that both SPT and ST are not suitable for reliable multicast Traffic engineering Can not reduce both tree and recovery costs Propose Recover-Aware Steiner Tree (RST) Integer Programming (IP) formulation Prove that RST is NP-hard and not approximable within k k: terminal node number Propose k-approximation algorithm RAERA for RST RAERA: Recover-Aware Edge Reduction Algorithm Achieve the best approximation ratio 10

Hardness Result RST is NP-Hard Steiner tree (ST) approximable within ratio 1.55 RST not approximable within |D|1- for every 0 Gap-introducing reduction from the Set Cover (SC) problem Transform an instance in SC to G in RST, such that If SC returns TRUE, OPT(G) ( + 1)(k + 1)|D| If SC returns FALSE, OPT(G) ( + 1)(k + 1)|D|2- k: D: the destination set L: the cost of each edge from s to X in G

Gap-Introducing Reduction An instance in SC Transform to G in RST y1 1 y2 x1 y1 y1 y3 x1 y2 L x2 ym x2 y3 x3 x3 s y1 x4 x4 y2 L y3 x5 x5 ym ym 1 X |Y|p copies of Y X Y

If (X, Y, E) has a k-node subset A of X covering all nodes in Y, then there exists a tree T rooted at s which contains A and D. And recovery set R is set as A. R = {x1, x2, x5} c(T) = k * L + |D| , w(T) = k * L + |D| y1 y2 y3 x1 x1 y1 y1 ym x2 y2 x2 y3 x3 x3 s T y1 x4 x4 y2 y3 x5 x5 ym ym k-node subset A X |Y|p copies of Y X Y

If (X, Y, E) does not have a k-node subset A of X covering all nodes in Y,| then w(T) > L * |Y|p y1 y2 y3 x1 ym x2 x3 s y1 x4 y2 For each copy of Y, at least one node connects to a non- recovery node, leading to a much higher recovery cost . y3 x5 ym X |Y|p copies of Y

Recover Aware Edge Reduction Algorithm (1/8) Tree Routing Phase The first phase starts from the shortest-path tree with root s and iteratively improves the tree to reduce the tree cost. RAERA iteratively re-routes a destination node on the solution tree T(VT, ET) to reduce the tree cost. More importantly, the re-routing path needs to include at least one candidate recovery node in C and the cost of the depth in the new tree cannot exceed the depth of the original shortest-path tree. Recovery Selection Phase Recovery Selection Phase is a dynamic programming algorithm to select the recovery nodes to minimize the recovery cost.

Recover Aware Edge Reduction Algorithm (2/8) Calculate a shortest-path tree for each destination An example of Tree Routing Phase: s 3 9 s 1 5 3 12 1 5 12 c 8 1 b 6 c 1 8 11 6 b 1 6 1 11 d 6 e d 8 e 5 5 1 5 3 3 10 1 5 u 1 10 8 6 u 1 v v 2 6 1 2 2 2 2 7 2 7 1 2 2 w 3 2 w 2 4 5 2 2 5 2 4 2 1 2 9 1 9 x 3 2 1 3 2 3 8 9 9 8 1 3 Shortest-path tree with root s Original network

Recover Aware Edge Reduction Algorithm (3/8) An example of Tree Routing Phase: Re-route destinations s s 3 3 1 1 5 5 12 12 c c 8 8 b b 1 1 6 6 1 1 11 11 6 6 d d e e 3 5 5 1 5 1 5 10 10 8 8 3 u u 1 1 v v 6 6 2 2 2 2 7 7 1 1 2 2 2 2 2 1 w w 5 5 2 2 4 4 2 2 2 9 9 3 3 2 3 8 2 3 8 Shortest-path tree with root s Tree Routing Phase

Recover Aware Edge Reduction Algorithm (4/8) Recovery Selection Phase: For each node v in VT, let Tv be the subtree of T rooted at v. Let Rv be a recovery set on Tv. The dynamic programming algorithm finds the optimal recovery sets for two cases. A recovery set Rv on Tv is type I if v not in Rv. Rv belongs to type II if v in Rv. x,k(Tv): the minimum recovery cost on Tv over all type I recovery set Rv with |Rv| x, such that v exactly dominates k nodes in Rv D. x(Tv): the minimum recovery cost on Tv over all type II recovery set Rv with |Rv| x . Bottom up

Recover Aware Edge Reduction Algorithm (5/8) Lemma 1: For each node ? ? and its child nodes ?1, ,???in ?, the following equations hold for 0 ? ?, 1 ? |?|, and 1 ? ??. 1) If ?? ?, then ??,????= ???? ?????+ ???? ??,? 1???+ ? ???? If ?? ?, then ??,????= if ? = 1 and ?? ?, if ? = 1,?? ?,and ?? ?, if ? > 1, 2) min{??,1???+ ????,?????+ ????} ??,????+ ? ???? if ? = 1, if ? > 1, v v v Since ?? ?, ?? dominates ? 1 nodes in ??? Similar discussions to 2) recovery node u1 u2 u v When ? > 1, ?? When ?? is NOT a When ?? is a recovery node can not be a recovery node

Recover Aware Edge Reduction Algorithm (6/8) Lemma 2: Suppose ?1, ???are the child nodes of ? ??. For 2 ? ??, the following equality holds. ? ??? = min ? [0,?] ? [1,?] Use DP, for ? = 2 to ??, to calculate ??,?( ?=1 ???) for every ?,? ? 1 ?)}. ??? ??,? {?? ? ,? ? + ?? ,? (?? ?=1 ?=1 # R & #D Cost (0,0) c1 (0,1) c2 ? (1,0) c3 v u1 u2 # R & #D Cost # R & #D Cost (0,0) c1 (0,0) c1 (0,1) c2 (0,1) c2 (1,0) c3 (1,0) c3

Recover Aware Edge Reduction Algorithm (7/8 x,k(Tv1) k = 1 17 12 k = 2 k = 3 21 18 13 x 0 1 2 0,3(Tv1) = 0,2(Tu) + 3 * 2 = 15 + 6 1,1(Tv1) = 1(Tu) + 2 = 15 + 2 1,3(Tv1) = 1,2(Tu) + 3 * 2 = 12 + 6 2,1(Tv1) = 2(Tu) + 2 = 10 + 2 2,3(Tv1) = 2,2(Tu) + 3 * 2 = 7 + 6 v 2 3 k = 1 10 9 k = 2 15 12 7 k = 1 8 1(Tw) = 20 2(Tw) = 16 k = 2 20 16 11 x 0 1 2 1(Tu) = 15 2(Tu) = 10 x 0 1 2 u w

Recover Aware Edge Reduction Algorithm (8/8 x,k(Tv1) k = 2 x,k(Tv2) k = 1 10 k = 1 17 12 k = 3 21 18 13 k = 2 26 22 17 x 0 1 2 x 0 1 2 v 1,3(Tv) = min{ 0,1(Tv1) + 1,2(Tv2), 0,2(Tv1) + 1,1(Tv2), 1,1(Tv1) + 0,2(Tv2), 1,2(Tv1) + 0,1(Tv2)} 2 3 = min{ , , 17+26 , } = 43 u w

Simulation Setup Estinet network simulator A real topology Biznet with 29 nodes and 33 links #destinations = 6 ~ 12 #recovery nodes = 2 Synthetic topologies Generated by Inet #nodes = 4000 ~ 10000 #destinations = 100 ~ 500 #recovery nodes = 15 ~ 55

Simulation Setup Algorithms The shortest-path tree algorithm (SPT) The Steiner tree (ST) algorithm The optimal solution by CPLEX RAERA Performance metrics Total cost (tree + recovery costs) Total retransmitted bytes Average latency

The Real Topology ST does not consider recovery cost and results in the highest recovery cost higher recovery cost to-end hops, and it results in the highest tree cost SPT minimizes end- SPT also provides 52 28 CPLEX CPLEX RAERA RAERA 42 The tree cost provided by RAERA is similar to optimized solution 24 Recovery Cost ST ST Tree Cost SPT SPT 32 20 22 ST minimizes tree cost, and provides the lowest tree cost 16 REARA also consider recovery cost, so the cost is the lowest 12 12 6 8 10 12 6 8 10 12 k k Tree Cost Recovery Cost

The Real Topology Longer end-to-end hops make longer latency when k is larger Because of the highest recovery cost, ST generates 6 250 the most CPLEX CPLEX retransmission bytes Retransmission (MBytes) 5 RAERA 200 RAERA ST 4 ST Latency (s) SPT is in between 150 SPT SPT 3 100 2 SPT reduces the end-to-end hops, so 50 1 REARA similar to optimized solution generates the fewest retransmission bytes 0 0 8 its latency does not grow with k critically 6 8 10 12 6 10 12 k k REARA shows the lowest latency with lower total costs Retransmission Latency

Synthetic Topology ST and SPT work similar with higher cost. The cost increase with k, because of larger tree for more destinations. The cost slightly decreases with more recovery nodes 2000 RAERA 1250 RAERA Cost (Tree+Recovery) Cost (Tree+Recovery) ST 1600 ST 1150 SPT SPT 1200 1050 800 950 400 850 0 750 100 200 300 k 400 500 15 25 35 r 45 55 Cost with Different k Cost with Different r REARA successfully reduces the cost

Synthetic Topology The cost does not increase with |V|, because the size of tree is similar. More destinations generate more retransmission Bytes. ST and SPT work similar. 1200 80 RAERA RAERA 70 ST 1100 ST Retransmission (MBytes) 60 Cost (Tree+Recovery) SPT SPT 50 1000 40 900 30 20 800 10 700 0 4000 6000 8000 10000 100 200 300 k 400 500 RAERA provides lower cost and generate less transmission bytes |V| Cost with Different |V| Retransmission bytes with different k

Synthetic Topology Latency does not change obviously with k and r because of longer end-to-end hops latency than REARA, because of higher recovery latency Latency is the highest in ST cast, SPT shows higher 160 160 RAERA RAERA ST ST 120 120 SPT SPT Latency (s) Latency (s) 80 80 40 40 0 0 100 200 300 k 400 500 15 25 35 r 45 55 Latency with different k Latency with different r RAERA provides the lowest latency

Running Time of RAERA Intel Xeon E7-4870 2.4 GHz CPUs and 128GB RAM Running time increases with k When scale is small, the running time is less than 1 second v 4000 6000 8000 10000 k = 100 0.7 1.5 2.61 4.08 k = 200 1.37 2.23 3.39 4.9 k = 300 2.87 3.9 5.09 6.6 k = 400 5.29 6.93 7.91 10.14 k = 500 9.56 11.48 12 13.99 Even in a large scale, the running is still acceptable. Also increases with |V|

Implementation We evaluate RAERA in our experimental SDN network Use Floodlight as our controller Implement recovery nodes in Click software router Topology includes 14 nodes and 20 links with 8 destinations and 2 recovery nodes Test video is 136 seconds in length

Evaluation in Our Testbed RAERA provides better video quality Algorithm Bandwidth Consumption 13.18 Mbytes 16.39 Mbytes 17.83 Mbytes Re-buffering RAERA ST SPT 0.4 s 33.5 s 7.8 s ST and SPT generate similar retransmission bytes ST provides longer average end-to-end hops that causes longer video re- buffering

Conclusion Traffic engineering and recovery node selection in SDN have not been carefully addressed for reliablemulticast Propose Recover-aware Steiner Tree (RST) Prove that RST NP-Hard and not able be approximated within k. Design algorithm RAERA k approximation algorithm tightest bound Acquire a solution in seconds in massive networks 33

Backup Slides

Reliable Multicast Sender handles recovery high recovery cost Middle nodes handle recovery where to place the recovery nodes High recovery costs Acks Recovery Packets Recovery Packets Acks

Reliable Multicast Sender handles recovery high recovery cost Middle nodes handle recovery where to place the recovery nodes Place a recovery node Recovery Packets Acks Acks Acks Save BW and latency

Recover Aware Edge Reduction Algorithm (7/8) An example for recovery node selection Use lemma 2 to calculate x,k(Tu) k = 1 k = 2 k = 3 9 9 9 k = 4 x 0 1 2 x,k(Tu) 1(Tu) = 2(Tu) = 9 u can help only tree special nodes for recovery, so there is no solution when k = 1, 2, 4

Recover Aware Edge Reduction Algorithm (8/8) Use Lemma1.(ii) to calculate x,k(T11) k = 1 14 14 k = 2 k = 3 24 24 24 k = 4 x 0 1 2 x,k(T11) 1,1(T111) = min { 1,1(Tu) + 5, 1(Tu) + 5} = min { , 9 + 5} 2,3(T111) = 2,3(Tu) + 3 * 5 = 9 + 15