Multicast routing Who? From? When? Andrej Pancfk Faculty of Informatics at Masaryk University Spring 2010 A. Pancfk Multicast routing Spring 2010 1 / 25 Contents What is multicast routing? General techniques for routes creation Steiner tree problem application on multicast routing A. Pancfk Multicast routing Spring 2010 2 / 25 What is multicast routing? Multicast definition Multicast is a network technology for the delivery of information to a group of destinations simultaneously using the most efficient strategy to deliver the messages over each link of the network only once, creating copies only when the links to the multiple destinations split. A. Pancfk Multicast routing Spring 2010 3 / 25 What is multicast routing? Basic description Unicast vs. broadcast vs. multicast One-to-one vs. one-to-all vs. one-to-many Effectivity is important Multicast group Static / dynamic multicast groups Sparse / pervasive multicast groups Multicast applications - content delivery A. Pancfk Multicast routing Spring 2010 4 / 25 What is multicast routing? The multi-objective multicast routing problem formulation Directed graph G = (V, E) (i, j) e E - link Cjj - cost of the link dj - delay r\ e R - destinations s - source T(s, R) - multicast tree Pt(s, r i) C T(s, R) - path between source and destination r, d(pt(s, r,)) - delay of path E dj A. Pancfk Multicast routing Spring 2010 5 / 25 What is multicast routing? Objectives Path delay (QoS) - maximal / average Total cost of the tree Maximum congestion (capacity - usage) Overhead etc. A. Pancfk Multicast routing Spring 2010 6 / 25 What is multicast routing? End of part: What is multicast routing? A. Pancfk Multicast routing Spring 2010 7 / 25 General techniques for routes creation Description Algorithms can be On line Distributed algorithms Unicast tunneling - connecting two multicast enabled segments A. Panak Multicast routing Spring 2010 8 / 25 General techniques for routes creation Part 1 Flooding Spanning Trees Reverse Path Broadcasting (RPB) Truncated Reverse Path Broadcasting (TRPB) Reverse Path Multicasting (RPM) Core-Based Trees A. Pancfk Multicast routing Spring 2010 9 / 25 General techniques for routes creation Part 1 - Flooding Forwarding datagrams from source to other nodes Dropping datagram if it was already received Easy to implement Disadvantage is huge overhead A. Pancfk Multicast routing Spring 2010 10 / 25 General techniques for routes creation Part 1 - Spanning Trees Less overhead than flooding Easy to implement Great deal of experience with minimal spanning trees Disadvantage is suboptimality of routes A. Panak Multicast routing Spring 2010 11 / 25 General techniques for routes creation Part 1 - RPB & TRPB (Truncated) Reverse Path Broadcasting - (T)RPB Builds group specific source rooted spanning tree The node forwards the packet arriving on the link that is considered shortest to source Truncated variant considers group member positions A. Pancfk Multicast routing Spring 2010 12 / 25 General techniques for routes creation Part 1 - RPM Reverse Path Multicasting (RPM) Same as TRPB, but delivery tree that spans only subnetworks with group members routers and subnetworks along the shortest path to subnetworks with group members Leaf routers send prune message if there is no group member A. Panak Multicast routing Spring 2010 13 / 25 General techniques for routes creation Part 1 - Core-Based Trees Shared single static delivery tree Destinations join/prune the multicast group Disadvantages are bottlenecks near core routers suboptimality of routes A. Pancfk Multicast routing Spring 2010 14 / 25 General techniques for routes creation Part 2 Distance Vector Multicast Routing Protocol (DVMRP) Multicast OSPF (MOSPF) Protocol-Independent Multicast (PIM) A. Pancfk Multicast routing Spring 2010 15 / 25 General techniques for routes creation Part 2 - PIM Protocol-Independent Multicast (PIM) Uses CBT Explicit join mechanism Different versions sparse/dense/bidirectional IP routing protocol-independent It does reverse path forwarding A. Pancfk Multicast routing Spring 2010 16 / 25 General techniques for routes creation End of part: General techniques for routes creation A. Pancfk Multicast routing Spring 2010 17 / 25 Steiner tree problem Description Interconnect given a set V of nodes by a network of shortest length Expands spanning tree problem with "non-included" edges and vertices Most versions are NP-complete, but heuristics available Mapping on multicast routing problem One of the most studied A. Pancfk Multicast routing Spring 2010 18 / 25 Steiner tree problem Discussion Euclidean Steiner tree (polynomial near-optimal solution) Metric Steiner tree vs. General Steiner tree problem Best in situations where virtual connection must be established Varying levels of complexity upon the cost and/or criterion Is it optimal? A. Pancfk Multicast routing Spring 2010 19 / 25 Steiner tree problem Heuristics KMB Heuristic Takahashi and Matsuyama Wu Wang None of the algorithms just mentioned is superior in quality to any other A. Pancfk Multicast routing Spring 2010 20 / 25 Steiner tree problem Heuristics - KMB Has performance guarantee Very good results (5% of optima in real networks) Algorithm: Construct a complete graph K(R, E) where d(i, j) is the shortest path from i to j in G Find minimum spanning tree T of K Replace each edge (i, j) in T by complete path from G Compute minimum spanning tree from the result Remove all nodes that are not in R Multicast routing Spring 2010 21 / 25 A. Panök Steiner tree problem Heuristics - Takahashi and Matsuyama Combination of the processes of finding shortest paths and finding a minimum spanning tree It is path-distance heuristic Procedure is analogous to the one presented by Prim Algorithm: Initially the tree is composed only from source tree Then, at each step heuristic searches for still unconnected destination that is closes to the current T A. Pancfk Multicast routing Spring 2010 22 / 25 Steiner tree problem Steiner Tree Problems with Delay Constraints Adding additional requrements to previous definition Minimalizing delay - assurance of QoS NP-Complete Well studied problem - many algorithms available A. Pancfk Multicast routing Spring 2010 23 / 25 Steiner tree problem Steiner Tree Problems with Delay Constraints - Algorithms Variations on line distributed A. Pancfk Multicast routing Spring 2010 24 / 25 Steiner tree problem End of part: General techniques for routes creation Thank you for your attention A. Pancfk Multicast routing Spring 2010 25 / 25