Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Multicast Routing Multipoint Communication: A Survey of Protocols, Functions, and Mechanisms by: Christophe Diot, Walid Dabbous and Jon Crowcroft Introduction to IP Multicast Routing by: Chuck Semeria and Tom MauferMulticast RoutingIntroduction (uses, definitions, etc.)Group ManagementRouting AlgorithmsRouting ProtocolsOther Considerations (ATM, scalability, security)TerminologyUnicast: Traditional point-to-point network communicationMulticast: Node(s) can send to members of a group (one-to-many or many-to-many)Broadcast: Blast the packet to everybody on the networkThe Basic IdeaIP Multicast traffic for a (source, destination group) pair is transmitted from the source to the receivers via a spanning tree that connects all hosts in the group. Different routing protocols use different techniques to build the trees. Once constructed all multicast traffic is distributed through the treeCommunication TiersLocally: host informs local multicast router of desire to join the group (using IGMP)Globally: local routers interact with other routers to receive multicast packets (using DVMRP, MOSPF, PIM)Introduction: UsesBulk data transfer (software updates, mailing list distribution, stock updates)Streamed Continuous Media (audio/visual conferences)Shared Application Data (shared whiteboard)Interactive Gaming or Simulations (very intensive)The MboneCollection of multicast subnetworks(islands) interconnected (tunneled) through the Internet for faster multicast deploymentStarted in 1992 with 40 subnets; up to 2800 subnets in 1996Based primarily on UDP for end-to-end transmission, IGMP for group management, and DVMRP for routingUse sd (session directory) to get a listing of active multicast sessionsMulticast PropertiessMust service a variety of applications (some have specific timing needs)The overall group should not be effected by individual join/leave operationsConnectionlessCurrent Best-effort serviceTwo ScenariosDense ModeGroup members are densely distributed throughout network (i.e. Many subnets contain at least one group member)Bandwidth is plentifulUses flooding to propogate informationProtocols include: DVMRP, MOSPF, PIM-DMSparse ModeGroup members are sparsely distributed throughout networkBandwidth is restricted (such as ISDN, home users)Uses selective techniques to set up and maintain multicast treesProtocols include: CBT, PIM-SMWhat defines a group?Network Group: logical grouping to control membership in local group (group address, group identifier, group properties, and group management) Social Group: participants in the communicationGroup management procedures advertise groups to potential members, broadcast routing information to multicast nodes, and control various group propertiesIGMPThe host sends IGMP report when an application joins the multicast groupIP_ADD_MEMBERSHIP socket optionhost not required to explicitly "unjoin" group when leavingThe router sends IGMP query at regular intervals which hosts belonging to the multicast group are obligated to replyIGMP EvolutionIGMPv1:Router sends Host Membership Query msg broadcast on LANHost replies to indicate group membershipRandomized delay before respondingImplicit leave via no reply to Query(timeout)RFC 1112IGMPv2:Added Group-Specific Query Elected router queries to see if any hosts left in groupLeave Group MessageLast host replying to query can send explicit Leave Group msgRFC 2236IGMP Evolution (cont.)IGMPv3:Lets source know if nobody is listeningReceivers can selectively choose sources to listen to (source pruning)Still being designedVirtual Circuit Group MgmtGroup of endpoints named at cirtuit setup timeMaster may be able to later add new receivers or senders to multicast circuitChallenges in reducing state information required when adding new receiversRouting Algorithms: The RequirementsMinimize network load. Need to optimize network resources while avoiding loops and concentrated trafficReliable transmission: data delivery shouldn't be affected by routing changes, link failures, etc.Use optimal routes as determined by resource availability, bandwidth, node connectivity, price paidMinimize router state (especially for larger groups)The Building BlocksMost routing protocols use these basic tree algorithms Reverse Path Forwarding (one tree per source)Flood and pruneSteiner Trees (a minimal spanning tree, which is shared for entire group)Core-based Trees (one tree per group)Desirable CharacteristicsFlooding can be danagerous in heterogeneous networks. Have to periodically flood if new receiver appearsRecall the challenges for routing algorithms:Evolve with group membership. Algorithm should uniquely identify group membersMinimize state information in the nodesOptimize routing given cost considerationsAvoid traffic concentrationReverse Path ForwardingRely on router's existing knowledge of unicast routing table (shortest path from self to sender)Best for densely distributed receiversResult of algorithm is are directed graphs: source-rooted delivery trees emanating from the subnet directly connected to sourceEfficient and easy to implement but doesn't use group membership information to build the tree so packets may hit subnets without membersRPF with PruningUse RPF technique plus record group membership.Timer controlled; have to periodically flood and re-prune to capture new membersRequires state information per source and per group to be kept at each node (leads to scalability problems)Steiner TreesMinimum cost tree connecting all routers with attached group members; network resources are globally optimizedNP-complete problem; but good heuristics existForms an undirected tree ==> symmetric linksGenerally not used in practice:computational complexityrequires knowledge of entire network topologymust be rerun when a router needs to leave/joinCore-Based TreesSingle tree shared by everybody (multiple sender / multiple receiver)One router is labeled as center of tree (but
View Full Document
Unlocking...