Ars-msr 1 Mcast 2013

  • Published on

  • View

  • Download

Embed Size (px)




<ul><li><p>Multicast Communications </p><p>Arhitecturi pentru retele </p><p>si servicii (ARS) </p><p>Managementul serviciilor si retelelor (MSR) </p></li><li><p> Octavian Catrina 2 </p><p>Multicast communications </p><p> Multicast communications </p><p> Data delivered to a group of receivers. Typical examples: </p><p>One-to-many (1:N) </p><p>one-way </p><p>MS </p><p>MR </p><p>Many-to-many </p><p>(N : M) </p><p>MS/R </p><p>MS/R </p><p>One-to-many (1:N) </p><p>two-way </p><p>MS </p><p>MR/US </p><p> Chapter outline </p><p> What applications use multicast? What are the requirements </p><p>and design challenges of multicast communications? </p><p> What multicast support does IP provide (network layer)? </p><p> After an overview of multicast applications, we'll focus on IP </p><p>multicast: service model, addressing, group management, and </p><p>routing protocols. </p><p>M=Multicast; U=Unicast </p><p>S= Sender; R=Receiver </p></li><li><p> Octavian Catrina 3 </p><p>Multicast applications (examples) </p><p> One-to-many Real-time audio-video distribution: </p><p>lectures, presentations, meetings, </p><p>movies, etc. Internet TV. Time </p><p>sensitive. High bandwidth. </p><p> Push media: news headlines, </p><p>stock quotes, weather updates, </p><p>sports scores. Low bandwidth. </p><p>Limited delay. </p><p> File distribution: Web content </p><p>replication (mirror sites, content </p><p>network), software distribution. </p><p>Bulk transfer. Reliable delivery. </p><p> Announcements: alarms, service </p><p>advertisements, network time, etc. </p><p>Low bandwidth. Short delay. </p><p> Many-to-many Multimedia conferencing: multiple </p><p>synchronized video/audio streams, </p><p>whiteboard, etc. Time sensitive. </p><p>High bandwidth, but typically only </p><p>one sender active at a time. </p><p> Distance learning: presentation </p><p>from lecturer to students, questions </p><p>from students to everybody. </p><p> Synchronized replicated resources, </p><p>e.g., distributed databases. Time </p><p>sensitive. </p><p> Multi-player games: Possibly high </p><p>bandwidth, all senders active in </p><p>parallel. Time sensitive. </p><p> Collaboration, distributed </p><p>simulations, etc. </p></li><li><p> Octavian Catrina 4 </p><p>Sender </p><p>Rcvrs </p><p>- </p><p>6 5 </p><p>2 1 </p><p>4 3 </p><p>7 </p><p>Multi-unicast </p><p>delivery </p><p>Multicast requirements (1) </p><p> Efficient and scalable delivery </p><p> Multi-unicast repeats each data item. </p><p> Wastes sender and network resources. </p><p> Cannot scale up for many receivers </p><p>and/or large amounts of data. </p><p> Timely and synchronized delivery </p><p> Multi-unicast uses sequential transmission. </p><p> Results in long, variable delay for large </p><p>groups and/or for large amounts of data. </p><p> In particular, critical issue for real-time </p><p>communications (e.g., videoconferencing). </p><p> We need a different delivery paradigm. </p></li><li><p> Octavian Catrina 5 </p><p> Multi-unicast vs. Multicast tree </p><p> Multi-unicast delivery 1:N transmission handled as N </p><p>unicast transmissions. </p><p> Inefficient, slow, for N1: multiple </p><p>packet copies per link (up to N). </p><p> Multicast tree delivery Transmission follows the edges of </p><p>a tree, rooted at the sender, and </p><p>reaching all the receivers. </p><p> A single packet copy per link. </p><p>Sender </p><p>Rcvr </p><p>Rcvrs </p><p>5 </p><p>3 </p><p>4 </p><p>2 </p><p>1 </p><p>- </p><p>4 3 2 </p><p>1 </p><p>Multicast tree delivery </p><p>Sender </p><p>Rcvr </p><p>Rcvrs </p><p>5 </p><p>3 </p><p>4 </p><p>2 </p><p>1 </p><p>- </p><p>4 3 2 </p><p>1 </p><p>Multi-unicast delivery </p></li><li><p> Octavian Catrina 6 </p><p>Multicast requirements (2) </p><p> Group management </p><p> Group membership changes dynamically. </p><p> We need join and leave mechanisms (latency may be critical). </p><p> For many applications, a sender must be able to send without </p><p>knowing the group members or having to join (e.g., scalability). </p><p> A receiver might need to select the senders it receives from. </p><p> Multicast group identification </p><p> Applications need special identifiers for multicast groups. </p><p>(Could they use lists of host IP addresses or DNS names?) </p><p> Groups have limited lifetime. </p><p> We need mechanisms for dynamic allocation of unique </p><p>multicast group identifiers (addresses). </p></li><li><p> Octavian Catrina 7 </p><p>Multicast requirements (3) </p><p> Session management </p><p> Receivers must learn when a multicast session starts and </p><p>which is the group id (such that they can "tune in"). </p><p> We need session description &amp; announcement mechanisms. </p><p> Reliable delivery </p><p> Applications need a certain level of reliable data delivery. </p><p>Some tolerate limited data loss. Others do not tolerate any loss </p><p>(e.g., all data to all group members - hard problem). </p><p> We need mechanisms that can provide the desired reliability. </p><p> Heterogeneous receivers </p><p> Receivers within a group may have very different capabilities </p><p>and network connectivity: processing and memory resources, </p><p>network bandwidth and delay, etc. </p><p> We need special delivery mechanisms. </p></li><li><p> Octavian Catrina 8 </p><p>Requirements: Some conclusions </p><p> Multi-unicast delivery is not suitable </p><p> Multi-unicast does not scale up for large groups and/or large </p><p>amounts of data: it becomes either very inefficient, or does not </p><p>fulfill the application requirements. </p><p> We need new mechanisms and protocols, </p><p>specially designed for multicast. </p><p> Specific functional requirements </p><p> Specific multicast functions, which are not needed for unicast: </p><p>group management, heterogeneous receivers. </p><p> General functions, which are also needed for unicast, but </p><p>become much more complex for multicast: addressing, routing, </p><p>reliable delivery, flow &amp; congestion control. </p></li><li><p> Octavian Catrina 9 </p><p>Which layers should handle multicast? </p><p> Data link layer </p><p> Efficient delivery within a multi-access network. </p><p> Multicast extensions for LAN and WAN protocols. </p><p> Network layer </p><p> Multicast routing for efficient &amp; timely delivery. </p><p> IP multicast extensions. Multicast routing protocols. </p><p> Transport layer </p><p> End-to-end error control, flow control, and congestion control </p><p>over unreliable IP multicast. </p><p> Multicast transport protocols. </p><p> Application layer multicast </p><p> Overlay network created at application layer using existing </p><p>unicast transport protocols. Easier deployment, less efficient. </p><p>Still an open research topic. </p></li><li><p> Octavian Catrina 10 </p><p>IP multicast model (1) </p><p> "Transmission of an IP datagram to a group of hosts" </p><p> Extension of the IP unicast datagram service. </p><p> IP multicast model specification: RFC 1112, 1989. </p><p> Multicast address </p><p> Unique (destination) address for a group of hosts. </p><p> Different datagram delivery semantics A distinct range of </p><p>addresses is reserved in the IP address space. </p><p> Who receives? Explicit receiver join </p><p> IP delivers datagrams with a destination address G only to </p><p>applications that have explicitly notified IP that they are </p><p>members of group G (i.e., requested to join group G). </p><p> Who sends? Any host can send to any group </p><p> Multicast senders need not be members of the groups they </p><p>send to. </p></li><li><p> Octavian Catrina 11 </p><p>IP multicast model (2) </p><p> No restrictions for group size and member location </p><p> Groups can be of any size. </p><p> Group members can be located anywhere in an internetwork. </p><p> Dynamic group membership </p><p> Receivers can join and leave a group at will. </p><p> The IP network must adapt the multicast tree accordingly. </p><p> Anonymous groups </p><p> Senders need not know the identity of the receivers. </p><p> Receivers need not know each-other. </p><p> Analogy: A multicast address is like a radio frequency, on which </p><p>anyone can transmit, and anyone can tune in. </p><p> Best-effort datagram delivery </p><p> No guarantees that: (1) all datagrams are delivered (2) to all </p><p>group members (3) in the order they have been transmitted. </p></li><li><p> Octavian Catrina 12 </p><p>IP multicast model: brief analysis </p><p> Applications viewpoint </p><p> Simple, convenient service interface. Same send/receive ops </p><p>as for unicast, plus join/leave ops. </p><p> Anybody can send/listen to a group. Security, billing? </p><p> Extension to reliable multicast service? Difficult problem. </p><p> IP network viewpoint </p><p> Scales up well with the group size. </p><p> Single destination address, no need to monitor membership. </p><p> Does not scale up with the number of groups. Conflicts with </p><p>the original IP model (per session state in routers). </p><p> Routers must discover the existence/location of receivers and </p><p>senders. They must maintain dynamic multicast tree state per-</p><p>group and even per-source&amp;group. </p><p> Dynamic multicast address allocation. How to avoid allocation </p><p>conflicts (globally)? Very difficult problem. </p></li><li><p> Octavian Catrina 13 </p><p>IPv4 multicast addresses </p><p> IPv4 multicast addresses </p><p> IP multicast in LANs </p><p> Relies on the MAC layer's native multicast. </p><p> Mapping of IP multicast addresses to MAC </p><p>multicast addresses: </p><p>31 28 27 0 </p><p>1110 multicast address </p><p>228 addresses </p><p>Class Address range </p><p>D to </p><p> </p><p>1 1 1 0 28 bits (228 addresses) </p><p>IPv4 multicast address </p><p>Ethernet multicast address </p><p>0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 0 23 bits </p><p>group bit </p><p>Ethernet LAN </p></li><li><p> Octavian Catrina 14 </p><p>Multicast scope </p><p> Multicast scope </p><p> Limited network region where multicast packets are forwarded. </p><p> Application-specific reasons or/and better efficiency. </p><p> TTL-based or administrative scopes (RFC 2365). </p><p> IPv4 administrative scopes: </p><p> Organization-local ( </p><p> Local scope ( </p><p> Link-local scope ( </p><p> Global scope: No boundary, all </p><p>remaining multicast addresses. </p><p>3 2 </p><p>4 </p><p>1 </p><p>5 </p><p>Local A </p><p>6 Internet </p><p>Organization-local </p><p>Local B </p><p> Administrative scopes </p><p> Delimited by configuring boundary routers: do not forward </p><p>some ranges of multicast addresses, on some interfaces. </p><p> Connected, convex regions. </p><p> Nested and/or overlapping. </p></li><li><p> Octavian Catrina 15 </p><p>Group management: local </p><p> Multicast service requirements </p><p> Multicast routers have to discover </p><p>the location of the members of </p><p>any multicast group &amp; maintain a </p><p>multicast tree reaching them all. </p><p> Dynamic group membership. </p><p>Sender </p><p>Rcvr </p><p>Rcvrs </p><p>5 </p><p>3 </p><p>4 </p><p>2 </p><p>1 </p><p>- </p><p>4 3 2 </p><p>1 </p><p>IGMP </p><p>IGMP IGMP </p><p>Multicast tree </p><p> Local (link) level </p><p> Multicast applications must notify </p><p>IP when they join or leave a </p><p>multicast group (API available). </p><p> Internet Group Management Protocol (IGMP) allows multicast </p><p>routers to learn which groups have members, at each interface. </p><p> Dialog between hosts and a (link) local multicast router. </p></li><li><p> Octavian Catrina 16 </p><p>Group management: internetwork </p><p> Implicit vs. explicit join </p><p> Implicit: Multicast tree obtained by </p><p>pruning a default broadcast tree. </p><p>Nodes must ask to be removed. </p><p> Explicit: Nodes must ask to join. </p><p> Global (internetwork) level </p><p> Multicast routing protocols </p><p>propagate information about </p><p>group membership and allow </p><p>routers to build the tree. </p><p>Sender </p><p>Rcvr </p><p>Rcvrs </p><p>5 </p><p>3 </p><p>4 </p><p>2 </p><p>1 </p><p>- </p><p>4 3 2 </p><p>1 </p><p>IGMP </p><p>IGMP IGMP </p><p>Multicast tree </p><p>Multicast Routing Protocol </p><p> Data-driven vs. control-driven multicast tree setup </p><p> Data-driven: tree built/maintained when/while data is sent. </p><p> Control-driven: tree set up &amp; maintained by control messages </p><p>(join/leave), independently of the sender(s) activity. </p></li><li><p> Octavian Catrina 17 </p><p>Local groups </p><p>at IF i1: </p><p>Groups: </p><p> </p><p>i1 </p><p>Groups: </p><p> </p><p>Groups: </p><p>none </p><p> </p><p>Group Management: IGMP (1) </p><p> Internet Group Management Protocol </p><p> Enables a multicast router to learn, for each of its directly </p><p>attached networks, which multicast addresses are of interest to </p><p>the systems attached to these networks. </p><p> IGMPv1: join + refresh + implicit leave (timeout). IGMPv2: adds </p><p>explicit leave (fast). IGMPv3 (2002): adds source selection. </p><p> IGMPv3 presented in the following, IGMPv1/v2 in the annex. </p><p> Periodic General Queries: Refresh/update group list </p><p> Reports are randomly delayed to avoid bursts. (Duplicate reports are completely suppressed in IGMPv1 &amp; v2.) </p><p>(2) IP packet to </p><p>IGMPv3 Current State Report: </p><p>member of group </p><p>(1) IP packet to (all systems on this subnet) </p><p>IGMPv3 General Query: Anybody interested in any group? </p></li><li><p> Octavian Catrina 18 </p><p>IGMP (2) </p><p> Host joins a group </p><p>Local groups </p><p>at IF i1: i1 </p><p>Groups: </p><p>+ </p><p> Host leaves a group Router must check if there are other members of that group. </p><p>Local groups </p><p>at IF i1: </p><p>Groups: </p><p>none/left </p><p>i1 </p><p>Groups: </p><p> </p><p>Groups: </p><p>none </p><p>(1) IP packet to </p><p>IGMPv3 State Change Report: </p><p>not member of </p><p>(2) IP packet to (all systems on this subnet) </p><p>IGMPv3 Group-Specific Query: Anybody interested in </p><p>IP packet to (all IGMPv3 routers) </p><p>IGMPv3 State Change Report: joined group add </p><p>(3) IP packet to </p><p>IGMPv3 Current State Report: </p><p>member of </p><p> maintained </p></li><li><p> Octavian Catrina 19 </p><p>Rcvr </p><p>5 </p><p>4 3 </p><p>Sender </p><p>Rcvr </p><p>3 2 </p><p>1 </p><p>- </p><p>1 </p><p>4 </p><p>6 </p><p>5 </p><p>7 </p><p>Rcvr </p><p>2 </p><p>Rcvrs </p><p>Multicast trees </p><p> What kind of multicast tree? </p><p> Minimize tree diameter (path </p><p>length, delivery delay) or tree </p><p>cost (network resources)? </p><p> Special, difficult case of minimum </p><p>cost spanning tree (Steiner tree). </p><p>No good distributed algorithm! </p><p>Shortest paths tree (e.g., unicast routing). </p><p> Practical solution </p><p> Take advantage of existing </p><p>unicast routing: Shortest path </p><p>tree based on routing info from </p><p>unicast routing protocol. </p><p> Multicast extension of a unicast </p><p>routing protocol, or separate </p><p>multicast routing protocol. </p><p>Min cost tree. </p></li><li><p> Octavian Catrina 20 </p><p>Source-based vs. shared trees </p><p> Source-based trees </p><p> One tree per sender. </p><p> Tree rooted at the </p><p>sender. Typically </p><p>shortest-path tree. </p><p> Shared trees </p><p> One tree for all senders. </p><p> Examples: Minimum diameter tree or minimum cost tree, etc. </p></li><li><p> Octavian Catrina 21 </p><p>Rcvrs 5 3 </p><p>Sender </p><p>Rcvr </p><p>3 2 </p><p>1 </p><p>- </p><p>1 </p><p>4 </p><p>6 </p><p>5 </p><p>Rcvr </p><p>2 </p><p>Sender + </p><p>7 4 </p><p> </p><p> </p><p>Interface notation: </p><p>N = North (up); S = South (down) </p><p>W = West (left); E = East (right) </p><p>NW = North-West (up-left). Etc. </p><p>Source-based trees (1) </p><p> In general: M1 senders/group M sources transmit to a group. </p><p> Session participants may be </p><p>senders, receivers, or both. </p><p> A separate source-based tree has </p><p>to be set up for each sender. </p><p> Source-based tree Tree rooted at a sender which </p><p>spans all receivers. </p><p> Typically, shortest-path tree. </p><p>Router 2: Multicast forwarding table </p><p>Source prefix Multicast group In IF Out IF </p><p> N S, E, SE </p><p> E N </p><p>... </p></li><li><p> Octavian Catrina 22 </p><p>Source-based trees (2) </p><p> Pros </p><p> Per-source tree optimization. </p><p> Shortest network path &amp; transfer delay. </p><p> Tree created/maintained only when/while a source is active. </p><p> Cons </p><p> Does not scale for multicast sessions with M&gt;&gt;1 sources. </p><p> The network must create and maintain M separate trees: </p><p> per-source &amp; group state in routers, higher control traffic and </p><p>processing overhead. </p><p> Examples </p><p>PIM-DM, DVMRP, MOSPF. Mixed solution: PIM-SM. </p><p> PIM-DM, DVMRP, MOSPF: Data-driven tree setup. </p><p> PIM-SM: Explicit join, control-driven tree setup. </p></li><li><p> Octavian Catrina 23 </p><p>Rcvrs 5 3 </p><p>Sender </p><p>Rcvr </p><p>3 2 </p><p>1 </p><p>- </p><p>1 </p><p>4 </p><p>6 </p><p>5 </p><p>Rcvr </p><p>2 </p><p>Sender + </p><p>7 4 </p><p>Core </p><p>Interface notation: </p><p>N = North (up); S = South (down) </p><p>W = West (left); E = East (right) </p><p>NW = North-West (up-left). Etc. </p><p>Shared trees (1) </p><p> Core-based shared tree The multicast session uses a </p><p>single distribution tree, with </p><p>the root at a "core" node, and </p><p>spanning all the receivers </p><p>("core-based" tree). </p><p> Each sender transmits its </p><p>packets to the core node, </p><p>which delivers them to the </p><p>group of receivers. </p><p> Typically, shortest-path tree, </p><p>with the central root node. </p><p>Router 5: Multicast forwarding table </p><p>Multicast group </p><p>(any sender) </p><p>In IF Out IF </p><p> W N, E </p><p>... </p></li><li><p> Octavian Cat...</p></li></ul>