Transcript Chapter 16
Internet Multicasting Chapter 16 Hardware Broadcast Many HW technologies support sending packets to multi destinations concurrently Broadcasting: most common form Copy of packet delivered to each destination Easy on bus technologies (Ethernet) Done with single packet transmission Others: SW must forward copies of the packet Broadcast Address Reserved destination address Specifies broadcast delivery Ex. – Ethernet: address of all 1’s HW at each machine accepts packet for: The machine’s address The broadcast address Chief disadvantage of broadcasting Demand on resources Network bandwidth Computational resources on all machines Hardware Origins of Multicast Multicasting Less common form of multi-point delivery Also supported by hardware technologies Allows each system to choose if it wants to participate in a given multicast Large set of addresses reserved for multicast One address used for each group of machines that want to communicate Multicast is a generalization of all addressing Unicast: multicast with one computer in the group Broadcast: multicast with all computers in the group Multicast: arbitrary computers in the group Multicast cannot replace conventional addressing Difference in underlying mechanisms Forwarding and delivery done differently Unicast and broadcast Forwarding depends on network topology Multicast Forwarding must send packet to all segments Conclusion: Multicast may be a generalization of addressing schemes However, underlying forwarding and delivery mechanisms make it less efficient Ethernet Multicast ½ of Ethernet addresses reserved for multicast Low-order bit of high-order byte distinguishes 0 for unicast; 1 for multicast Multicast in dotted hexadecimal notation: 01.00.00.00.00.0016 If interface configured for Ethernet multicast: 01.00.5E.00.00.0116 Will accept any packet sent to computer’s unicast address, broadcast address, or above multicast address IP Multicast IP Multicasting Internet abstraction of hardware multicasting Allows transmission to subset of hosts Generalizes subset Can spread across arbitrary physical networks Anywhere throughout the internet Given subset is called a multicast group IP multicasting has following characteristics: Group address Each multicast group has unique class D address Some groups permanent; some temporary Number of groups Up to 228 simultaneous multicast groups Number limited by constraints on routing table size Dynamic group membership Host can join or leave anytime Host can be member of arbitrary number of groups Use of hardware If underlying network HW supports multicast; IP uses it If not; IP uses broadcast or unicast to deliver IP multicast Inter-network forwarding Members of IP multicast group can attach to multiple nets Multicast routers are required to forward IP multicast Capability usually added to conventional routers Delivery semantics Uses same best-effort delivery as other IP datagram delivery Multicast datagrams can be lost, delayed, duplicated, etc. Membership and transmission Arbitrary host can send datagrams to any multicast group Membership only used to determine who receives Conceptual Pieces Three conceptual pieces required Multicast addressing scheme Effective notification & delivery mechanism Efficient internetwork forwarding facility Many goals, details, and constraints present challenges for an overall design Addressing scheme has conflicting goals Allow local autonomy in assigning addresses Define addresses that have global meaning Notification and delivery has same problem Make effective use of hardware when available Allow IP multicast over networks w/o HW support Forwarding facility presents biggest challenge Want both efficient and dynamic scheme Route packets along shortest path Not send copy on path not leading to member of the group Allow hosts to join and leave a group at any time IP multicast includes all three aspects Rest of chapter considers each in more detail IP Multicast Addresses Permanently assigned addresses Called well-known Used for major services on global Internet Other groups created when needed Transient multicast groups Discarded when group member count = 0 Class D addresses reserved for multicast Figure 16.1 No identification information in the group bits Not identify the origin or owner of a group No info about whether all members on one physical network Range: 224.0.0.0 through 239.255.255.255 Lowest address reserved Others up through 224.0.0.255: routing & group maintenance Figure 16.2 shows examples of permanently assigned addresses Figure 16.2 Multicast Address Semantics Multicast treated differently than unicast Multicast address can only be destination No ICMP messages for multicast datagrams Ping sent to multicast address never answered Time-to-live field is honored Reaches zero; datagram discarded No ICMP message sent Mapping IP Multicast to Ethernet Multicast IP multicast standard does not cover all types of network hardware Does specify mapping to Ethernet multicast Efficient and easy Place low-order 23 bits of IP multicast address into the low-order 23 bits of the special Ethernet multicast address 01.00.5E.00.00.0016 Example: 224.0.0.2 becomes 01.00.5E.00.00.0216 11101010 00000000 00000000 00000010 Mapping is not unique IP multicast uses 28 significant bits More than one IP multicast group may map to same Ethernet multicast address 11100000 0xxxxxxx xxxxxxxx xxxxxxxx . . . . . . 11101111 1xxxxxxx xxxxxxxx xxxxxxxx Scheme chosen as a compromise Uses 23 of the 28 bits Chances are small that two groups will be the same Using fixed part of Ethernet address helps Makes debugging easier Eliminates interference between IP and other protocols Consequences: host may get msg in error IP software must check incoming datagrams Hosts and Multicast Delivery IP multicast on single physical network Host uses HW multicast address Receiver always listening to it Multicast throughout the internet Special multicast routers forward the datagrams Host must send datagram to multicast router Does via the hardware, like in local multicast Diff between local & non-local in the routers Multicast Scope Scope of multicast group Refers to dispersion of group members Perhaps restricted to a network or organization Scope of multicast datagram Set of networks over which datagram will be sent Informally, datagram’s scope is called its range IP uses two techniques to control scope Time-to-live field Administrative scoping TTL field control Set to small value, host can limit distance it’s routed Control messages have TTL of 1 (host-router comm) Applications on single host can use IP multicast Set TTL value to 0; never leave host Can configure site routers such that a certain TTL is needed or else the datagram will never leave the site TTL field gives course-grain control over scope Administrative scoping Reserve parts of address space Do for local groups or groups part of a single org Routers forbidden from forwarding datagrams with addresses from this space Extending Host SW to Handle Multicasting Host participates in IP multicast in 1 of 3 levels (1) Host can neither send nor receive IP multicast (2) Host can send but not receive IP multicast (3) Host can both send and receive IP multicast Modifications for host sending are not difficult IP SW allows application to specify multicast as destination Network interface SW must be able to map IP multicast address into HW multicast address Extending host to receive is more complex Host IP SW must have API allowing programs to join & leave multicast groups If multiple applications join, must pass all a copy If all leave, host must know it no longer participates Host must inform multicast routers of membership Hosts join specific IP groups on specific networks Host may have multiple network connections May join group on one network and not on another Keep group membership associated with networks Allows multicast use with local machines on one net SW must keep separate lists of multicast addresses for each network Application must specify a particular network when joining or leaving a multicast group Internet Group Management Protocol To participate in IP multicast, host must: Local network multicast: Have SW allowing send/receive multicast datagrams Multicast that spans physical networks Must inform local multicast routers Multicast routers must know memberships Use IGMP to communicate group membership Current version is 3; knows as IGMPv3 IGMP is like ICMP Uses IP datagrams to carry messages IGMP provides a service used by IP Think of as integral part of IP, not separate protocol IGMP is a standard for TCP/IP Required on all machines receiving IP multicast Conceptually, IGMP has two phases Host joins group; sends message Routers get and establish routing Routers poll hosts to see if still members If none report, router stops advertising membership IGMP Implementation IGMP designed to avoid adding overhead May have multiple multicast routers on a net May have hosts participating, too Must avoid having all participants generate control traffic Several way IGMP minimizes effect on network All host/router communication uses IP multicast IP destination address is a multicast address Datagrams with IGMP messages transmitted via HW multicast Hosts not using IP multicast never receive IGMP messages When polling, single query sent about all groups Not send a separate query for each group Default polling rate is 125 seconds Single polling router used Even if multiple multicast routers attach to same network Hosts respond to queries at different times Query contains value N Hosts pick random number between 0 and N to wait Have multiple groups; pick different number for each Reports for multiple group memberships can be sent in a single packet Group Membership State Transitions IGMP must remember status of each multicast group to which host belongs Keeps a table to record group membership When host joins, allocates entry Keeps group reference counter; initializes to 1 Another application joins; increment counter Application terminates execution or drops out; decrement Counter reaches zero; informs multicast router Figure 16.4 The three possible states of an entry in a host’s multicast group table and transitions among them, where each transition is labeled with an event and an action. The state transitions do not show messages sent when joining and leaving a group. IGMP Message Format Skip: 16.16: IGMP Membership Query Message Format 16.17: IGMP Membership Report Message Format Multicast Forwarding & Routing Information Unanswered questions How do routers exchange membership info? How do routers ensure datagrams get to all group members? No single standard for propagation No real agreement on an overall plan Protocols differ in goals and basic approach Why is multicast routing so difficult? Multicast routing differs from conventional routing because multicast forwarding differs Figure 16.9 Need dynamic routing No “dots” on net 2; not send packets there But, host can join at any time Unicast routing: changes when topology changes Multicast: change when application leaves/joins group Insufficiency of destination routing F & E can send to cross group Same destination; different actions A send to cross group: still another action Multicast forwarding requires a router to look at more than destination address Arbitrary senders Any host can send to the group; not just members G can send to dotted group Not a member of the group No members on G’s network Datagram may pass through other networks with no members of the group So: Multicast datagram may originate on a computer that is not part of the group May be forwarded across networks that do not have any group members attached Basic Multicast Forwarding Paradigms Routers must use more than destination What exactly do they use? Multicast destination represents a set of computers Want to reach all members of the set Do not want to route over same network twice Partial solution: do not send back on arriving interface Will not prevent problem if set of routers form loop Rely on datagram’s source address to avoid loops One idea: Reverse Path Forwarding Uses source address to prevent loop Multicast router must have conventional table Have shortest path to all destinations Datagram arrives Looks up in table; finds interface I which leads to source If it arrived on I; forward copy to all other interfaces Otherwise, discard the copy Each multicast datagram goes to every network Every host in multicast group will receive it RPF alone not used – wastes bandwidth Transmits to nets with no members & lead to no members Truncated Reverse Path Forwarding Modified version of RPF Avoids sending datagrams where not needed Multicast router needs to have: Conventional routing table List of multicast groups reachable thru each NI When a multicast datagram arrives: Router first applies RPF rule If should discard, does so If not, checks to see if one or more members in the destination are reachable over each interface Truncates sending when no more members lie along path Uses both source and destination addresses in decision Consequences of TRPF Guarantees each member gets datagram Has two surprising consequences Delivers an extra copy to some networks Delivery depends on the datagram’s source If A is source, Net 4 & B will get duplicate copies Figure 16.10 Behavior of delivery depends on the source Figure 16.11 Multicast Trees Use graph theory to describe a tree Set of paths from a given source to all members Graph is tree if no cycles appear That is, router is on no more than one path Called forwarding tree or delivery tree Each multicast router is a node in the tree Network that connects two routers is an edge Last router along each path from source is a leaf Network hanging off leaf router is a leaf network Tree with root X Leaves R3, R4, R5, and R6 Technically not a tree R3 lies along two paths Informally, referred to as a tree anyway Important principle Forwarding tree is defined as set of paths through multicast routers from source to all members of a multicast group For a given multicast group, each possible source can determine a different forwarding tree An immediate consequence concerns the size of tables used for forwarding Each entry in multicast table is a pair: (multicast group, source) Conceptually, source identifies a single host that can send datagram In practice, do not keep separate entry for each host All forwarding trees defined by all hosts on a single network are identical To save space, use a network prefix as source Router defines on forwarding entry for all hosts on same net Aggregating entries by net prefix reduces table size Multicast tables can still be much larger than conventional Conventional: size proportional to number of networks Multicast: proportional to product of number of networks and number of multicast groups Essence of Multicast Routing Inconsistency between IP multicast & TRPF TRPF not forward datagram to a network unless that network leads to a member Multicast router must know about group membership IP allows host to leave/join at any time Leads to rapid changes Group membership must be propagated Since membership does not follow local scope Membership issue central to routing All multicast routing schemes propagate info In addition to using info for forwarding Rapid changes may make router info imperfect Routing updates may lag changes Multicast design represents a tradeoff Routing traffic vs. inefficient data transmission Must propagate group membership info or routers will not forward datagrams efficiently If scheme communicates with every member, resulting traffic will overwhelm an internet Every design is a compromise Reverse Path Multicasting Derived from TRPF Extensions make it more dynamic Three underlying assumptions: Receipt by every member more important than eliminating unnecessary transmissions Multicast routers have conventional tables with correct information Multicast routing should improve efficiency when possible RPM uses two step process At start, uses RPF broadcast scheme Ensures all networks get copy of datagram At same time, RPM has routers inform one another about paths not leading to members Routers stop forwarding along such paths How do routers learn location of members? RPM propagates information bottom-up Starts with hosts that join or leave groups Sends info via IGMP to local router Thus, routers know about local members, but not distant Leaf routers can decide if forward to leaf networks Does not forward if no members of the group Leaf router informs next router along path back to source Whenever router learns no members lie beyond it Stops forwarding; informs next router back toward root Called pruning a path from the forwarding tree RPM called broadcast and prune Router broadcasts using RPF Until get information that allows a path to be pruned RPM system also called data-driven Router does not send membership info to any other routers until datagrams arrive for the group Data-driven model must also handle case of host joining after path has been pruned RPM handles joins bottom-up Host informs local router it has joined Router consults its record of the group Obtains address of router previously sent prune msg to Send new message that undoes prune Known as graft requests DV Multicast Routing Protocol Like RIP protocol; extended for multicast Allows multicast routers to pass info Group membership & datagram transfer cost Routers make up forwarding tree for each possible (group, source) pair Sends datagrams out over networks that correspond to branches in the forwarding tree Routers talk with extended form of IGMP New msg types to enter group, leave group, query other routers, & carry routing info (including cost) Mrouted Program Implements DVMRP for UNIX systems Like routed Cooperates closely with OS to install routing info Unlike routed Does not use standard routing table Can only be used with a multicast kernel Has special multicast routing table Code needed to forward multicast datagrams Uses multicast tunneling Mrouted handles two tasks: Route propagation Uses DVMRP to propagate routing information Constructs multicast routing table Usually has mrouted in addition to standard routing Multicast tunneling Not all routers can forward multicast datagrams Can tunnel a datagram from one router to another Go through routers that do not participate in multicast Both tasks may not be needed at a computer Configuration file used to specify how operate Tunneling Used when routers on the path between participating hosts do not run multicast routing software Tunnel consists of agreement between mrouted programs running on two routers Both listen on local net for datagram sent to specified multicast destination When one arrives, it is encapsulated by mrouted Put in conventional unicast datagram Sent to other router Other mrouted program receives datagram through its tunnel Extracts the multicast datagram Forwards according to its multicast routing table Outer, unicast datagram has own TTL counter Inner, multicast datagram has separate TTL counter Tunnel treated like single physical network Alternative Protocols DVMRP has some limitations Uses small value for infinity (like RIP) Keeps lots of information Does broadcast and prune Lots of traffic to propagate membership information Since use DV, propagation is slow Does not scale well Other multicast protocols Core Based Trees (CBT) Protocol Independent Multicast (PIM) Multicast extensions to OSPF (MOSPF) None are a required standard Core Based Trees (CBT) Avoids broadcasting Uses demand-driven paradigm Does not forward along path until host(s) join Instead of forward until negative info received, does not forward until positive info received Which routers should be informed when a host informs local router (via IGMP) that it has joined a group? Divides the internet into regions Designates a core router for each region Protocol Independent Multicast (PIM) Really two protocols PIM-DM (dense mode) LAN environment Most all networks are listening to each group PIM-SM (sparse mode) WAN environment Members are small subset of possible networks PIM-DM Assumes low-delay networks with plenty of bandwidth Optimized for guaranteed delivery Uses broadcast and prune Not worry about overhead PIM-SM Demand-driven like CBT Designates router to be rendezvous point (RP) Like CBT core RP is equivalent of CBT core router Multicast Extensions to OSPF (MOSPF) Let multicast routing benefit from info gathered by conventional protocols Uses OSPF’s topology database to build forwarding tree for each source Has advantage of being demand-driven Disadv: Amount of routing information to propagate Information must be synchronized Works well within area; cannot scale to internet Reliable Multicast Refers to system that: Uses multicast delivery Guarantees all group members receive data: In order No loss, duplication, or corruption Theory More efficient forwarding scheme than broadcasting All data still arrives intact In practice Not as easy as sounds “In sequence” delivery may be meaningless If group has multiple senders Multicast schemes easily produce duplication Need to bound the delay for some applications Reliability requires acknowledgements Arbitrary number of group members Thus, send must handle arbitrary number of ACKs This is the ACK implosion problem Use hierarchical approach Multicasting limited to single source ACK points identified Router in tree that agrees to cache copies of data Processes ACK from hosts or routers down the tree ACK point accomplishes necessary retransmissions NACK usually used Host detects lost datagram; requests retransmission Choice of branching topology and ACK points is crucial to success of reliable multicast Other approaches to reliability Send multiple datagram copies Works well if RED is used by routers Probability of more than one copy being discarded is small Forward error-correcting codes Sender incorporates error-correction info into each datagram If one is lost, error correcting code contains sufficient redundant information to allow sender to reconstruct the missing datagram Summary IP multicast is an abstraction of hardware multicasting Allows delivery to multiple destinations Uses class D addresses to specify delivery Actual transmission uses hardware, if available Multicast groups are dynamic Hosts can join/leave at any time For local multicast: Host only need ability to send/receive multicast Over multiple networks: Multicast routers propagate group information Arrange routing so all members get copy of datagram Hosts communicate membership via IGMP Efficient Only periodic message from a multicast router and a single reply for each multicast group per network Variety of protocols for routing information propagation Either data-driven or demand-driven Multicast forwarding table is much larger than unicast routing table Needs entries for each (group, source) pair Not all routers propagate multicast routes or forward multicast datagrams IP tunnel used to transfer datagrams Multicast datagram encapsulated in unicast datagram Reliable multicast Uses multicast forwarding But offers reliable delivery semantics Must avoid ACK implosion Use hierarchy of acknowledgement points Other approaches send redundant information