CS 6390 – Advanced Computer NetworksMulticast Routing: Problem StatementDVMRPHow to do efficient multicast in Extended LANs?Slide 5How to do efficient multicast in Extended LANs? ExampleSlide 7How to support multicast routing in a distance-vector environment?Reverse Path Forwarding (RPF)PowerPoint PresentationSlide 11Slide 12Slide 13An Architecture for Wide-Area Multicast RoutingPIM-SMSlide 16Slide 17Slide 18Slide 19Slide 20How to provide Inter-domain multicast routing?Inter-domain multicastIssues with ASMSlide 24IP Multicast Channels: EXPRESS Support for Large-Scale Single-Source ApplicationsSource Specific Multicast (SSM)SSMSingle-source IP Multicast AddressesAdvantagesCS 6390 – Advanced Computer NetworksMulticast RoutingMulticast Routing: Problem StatementGoal: find a tree (or trees) connecting routers having local mcast group members source-based: different tree from each sender to rcvrsUsed in DVMRP, PIM-SMshared-tree: same tree used by all group membersUsed in PIM-SM, CBTShared treeSource-based treesDVMRPDefined by Deering and Cheriton in “Multicast Routing in Datagram Internetworks and Extended LANs” in ACM Transactions on Computer Systems in 1990Shows how to do multicastExtended LANs -- will not discussIntra-domain distance-vector routing environmentsHow to do efficient multicast in Extended LANs?Single Spanning-Tree Multicast RoutingExtended LANs are formed by connecting LANs with link layer bridgesBridges propagate broadcast (and multicast) packets across every segment of the extended LANWay too inefficient, especially for multicast applications with sparsely located receivers Find an efficient way of doing multicast and convert applications to use multicast – solve host exposure problemHow to do multicast better in Extended LANs?How to do efficient multicast in Extended LANs?If bridges knew which interface lead to members of a given group, they would forward the packets on those interfaces onlyBut, how do bridges learn which interface lead to individual hosts?When a unicast packet arrives from a host, bridge records the (host addr, interface, age) into a tableCan we do something similar for multicast packets?A group member of a group G sends a membership-report to ALL-BRIDGES mcast addr with SourceAddr = G.Bridge records this interface as leading to a member of G and forwards this report to other bridges in the Ext. LANBridges use (addr, (outgoing int, age), (outgoing int, age), … ) table entries for multicastHow to do efficient multicast in Extended LANs?ExampleStep 1: A joins multicast group GA sends a msg to (G,ALL-BRG); msg forwarded to entire Extended LAN@B1: G: (3,age)@B2: G: (1,age)@B3: G: (1,age)Step 2: E joins multicast group GE sends a msg to (G,ALL-BRG); msg forwarded to entire Extended LAN@B1: G: (3,age),(1,age)@B2: G: (1,age)@B3: G: (1,age),(2,age)Step 3: B sends data to the multicast group (B,G)B1: forwards (B,G) data on interfaces 1 and 3B2: do not do anything, i.e., do not forward (B,G) on interface 2B3: forward (B,G) data on interface 2 but NOT on interface 3B1 B2 B3BA F C DE12312312How to do efficient multicast in Extended LANs?AlgorithmIf SourceADDR = G, record arriving interface as outgoing-interface with an age of zero into a table entry for this mcast addressPeriodically increment age, when age=expiry threshold, delete this interface info from entry and if no outgoing-branches remain, delete the entire entryIf a pkt arrives with multicast dest addr, forward a copy on every outgoing-branch recorded in the table entry excluding the arriving branchAn efficiency improvement to suppress unnecessary membership reports Hosts send membership-reports as (G,G)Bridge, on receiving a pkt with address (G,G) changes it to (G, all-bridges) and forwards to other bridgesThis suppresses #membership reports to 1 per report intervalHow to support multicast routing in a distance-vector environment?Distance Vector Multicast Routing (DVMRP)Flood and prune based tree construction algorithmCreate source-based shortest path trees Tree is rooted at the source siteIt corresponds to shortest path between the source and each receiverMain assumption is path symmetry (links have the same costs in both directions)Routers use Reverse Path Forwarding (RPF) ruleObservation:Every shortest-path multicast tree rooted at the sender is a subtree of a single shortest-path broadcast tree rooted at this senderFirst build a shortest-path broadcast tree by floodingThen prune that tree to get the multicast treeReverse Path Forwarding (RPF)if (pkt is received on incoming link on shortest path back to source) then accept datagram for forwardingelse ignore datagramrely on router’s knowledge of shortest path from it to sendereach router has simple forwarding behavior:Internet Multicasting Routing: DVMRPDVMRP: distance vector multicast routing protocol, RFC1075flood and prune: reverse path forwarding, source-based treeRPF tree based on DVMRP’s own routing tables constructed by communicating DVMRP routes no assumptions about underlying unicastinitial datagram to mcast group flooded everywhere via RPFrouters not wanting group data: send upstream prune msgsReverse Path Forwarding: Flooding•result is a source-specific reverse SPT–may be a bad choice with asymmetric linksR1R2R3R4R5R6R7router with attachedgroup memberrouter with no attachedgroup memberdatagram will be forwardedLEGENDS: sourcedatagram will not be forwardedReverse Path Forwarding: Pruningforwarding tree contains subtrees with no mcast group membersno need to forward datagrams down subtree“prune” msgs sent upstream by router with no downstream group membersR1R2R3R4R5R6R7router with attachedgroup memberrouter with no attachedgroup memberprune messageLEGENDS: sourcelinks with multicastforwardingPPPDVMRP: continued…soft state: DVMRP router periodically (1 min.) “forgets” branches are pruned: mcast data again flows down unpruned branchdownstream router: reprune or else continue to receive datarouters can quickly regraft to tree following IGMP join at leafThe first multicast routing protocol implemented and deployed on the InternetProblems?Not scalableAn Architecture for Wide-Area Multicast RoutingDeering, Estrin, Farinacci, Jacobson, Liu, WeiSIGCOMM 94PIM-SMMotivating observationsCompared to the
View Full Document
Unlocking...