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 34Slide 35Slide 36Slide 37Slide 38MulticastOutlineMulticast Introduction and MotivationRIP-based and Protocol Independent Multicast RoutingCS 640 2One to many communication•Application level one to many communication•multiple unicasts•IP multicastS SRRRRRRCS 640 3Why Multicast•When sending same data to multiple receivers–better bandwidth utilization–less host/router processing–quicker participation•Application–Video/Audio broadcast (One sender)–Video conferencing (Many senders)–Real time news distribution–Interactive gamingCS 640 4IP multicast service model•Invented by Steve Deering (PhD. 1991)–It’s a different way of routing datagrams •Senders transmit IP datagrams to a "host group" •“Host group” identified by a class D IP address•Members of host group could be present anywhere in the Internet•Members join and leave the group and indicate this to the routers•Senders and receivers are distinct: i.e., a sender need not be a member•Routers listen to all multicast addresses and use multicast routing protocols to manage groupsCS 640 5IP multicast group address•Things are a little tricky in multicast since receivers can be anywhere•Class D address space•Allocation is essentially random – any class D can be used–Nothing prevents an app from sending to any multicast address•Some well-known address have been designated •Standard are evolvingCS 640 6Getting Packets to End Hosts•Packets from remote sources will only be forwarded by IP routers onto a local network only if they know there is at least one recipient for that group on that network•Internet Group Management Protocol (IGMP, RFC2236)–Used by end hosts to signal that they want to join a specific multicast group–Used by routers to discover what groups have have interested member hosts on each network to which they are attached.–Implemented directly over IPCS 640 7IGMP – Joining a groupExample : R joins to Group 224.2.0.1•R sends IGMP Membership-Reportto 224.2.0.1•DR receives it. DR will start forwarding packets for 224.2.0.1 to Network A•DR periodically sends IGMP Membership-Query to 224.0.0.1 (ALL-SYSTEMS.MCAST.NET)•R answers IGMP Membership-Report to 224.2.0.1RR: ReceiverDR: Designated Router Data to 224.2.0.1IGMP Membership-ReportNetwork ANetwork BDRCS 640 8IGMP – Leaving a groupExample : R leaves from a Group 224.2.0.1•R sends IGMP Leave-Group to 224.0.0.2 (ALL-ROUTERS.MCAST.NET)•DR receives it. •DR stops forwarding packets for 224.2.0.1 to Network A if no more 224.2.0.1 group members on Network A.Data to 224.2.0.1RDRR: ReceiverDR: Designated Router IGMP Leave-GroupNetwork ANetwork BCS 640 9Challenges in the multicast model•How can a sender restrict who can receive?–need authentication, authorization–encryption of data–key distribution–still an active area of researchCS 640 10IP multicast routing•Purpose: share Group information among routers, to implement better routing for data distribution•Distribution tree structure–Source tree vs shared tree•Data distribution policy–Opt in (ACK) type vs opt out (NACK) type•Routing protocols are used in conjunction with IGMPCS 640 11Source distribution treeReceiver 1EBA D FSourceNotation: (S, G) S = Source G = GroupCReceiver 2SR RCS 640 12Shared distribution treeReceiver 1EBA D FSourceNotation: (*, G) * = all sources G = GroupCReceiver 2S1R RShared RootS2CS 640 13Source tree characteristics•Source tree–More memory O (G x S ) in routers –optimal path from source to receiver, minimizes delay•good for–small number of senders, many receivers such as Radio broadcasting applicationCS 640 14Shared tree characteristics•Shared tree–Less memory O (G) in routers–Sub-optimal path from source to receiver, may introduce extra delay (source to root)•good for–Environments where most of the shared tree is the same as the source tree–Many senders with low bandwidth (e.g. shared whiteboard)CS 640 15Data distribution policy•Opt out (NACK) type–Start with “broadcasting” then prune brunches with no receivers, to create a distribution tree–Lots of wasted traffic when there are only a few receivers and they are spread over wide area•Opt in (ACK) type–Forward only to the hosts which explicitly joined to the group–Latency of join propagationCS 640 16Protocol types•Dense mode protocols–Assumes dense group membership–Source distribution tree and NACK type–DVMRP (Distance Vector Multicast Routing Protocol)–PIM-DM (Protocol Independent Multicast, Dense Mode)–Example: Company-wide announcement•Sparse mode protocol–Assumes sparse group membership–Shared distribution tree and ACK type–PIM-SM (Protocol Independent Multicast, Sparse Mode)–Examples: Orientation for new employees.CS 640 17DVMRPexchange distance vectors•Each router maintains a ‘multicast routing table’ by exchanging distance vector information among routers –First multicast routing protocol ever deployed in the Internet•Similar to RIP–Constructs a source tree for each group using reverse path forwarding•Tree provides a shortest path between source and each receiver•There is a “designated forwarder” in each subnet–Multiple routers on the same LAN select designated forwarder by lower metric or lower IP address (discover when exchanging metric info.)•Once tree is created, it is used to forward messages from source to receiversCS 640 18DVMRPbroadcast & prune•Flood multicast packets based on RPF (Reverse path forwarding) rule to all routers.•Leaf routers check and sends prune message to upstream router when no group member is on their network •Upstream router prune the interface with no dependent downstream router.•Graft message to create a new branch for late participants•Restart forwarding after prune lifetime (standard : 720 minutes) •draft-ietf-idmr-dvmrp-v3-09.txt (September 1999)CS 640 19RPF(reverse path forwarding)•Simple algorithm developed to avoid unnecessary packets to flow around.•RPF algorithm takes advantage of the IP routing table to compute a multicast tree for each source.•RPF check1. When a multicast packet is received, note its source (S) and interface (I)2. If
View Full Document
Unlocking...