Question? Leave a message!




Why IP multicast

Why IP multicast 29
Multicast Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 1Overview  Why multicast Multicast apps ...  Concepts: groups, scopes, trees  Multicast addresses, LAN multicast  Group management: IGMP  Multicast routing and forwarding: MBONE, PIM  Reliable Multicast Transport Protocols  Multicast Congestion Control  Deployment issues, SourceSpecific Multicast (SSM), Applicationlevel Multicast Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 2Multicast = Efficient Data Distribution Src Src Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 3Why Multicast  Need for efficient onetomany delivery of same data  Applications:  News/sports/stock/weather updates  Distance learning  Configuration, routing updates, service location  Pointcasttype “push” apps  Teleconferencing (audio, video, shared whiteboard, text editor)  Distributed interactive gaming or simulations  Email distribution lists  Content distribution; Software distribution  Webcache updates  Database replication Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 4Why Not Broadcast or Unicast  Broadcast:  Send a copy to every machine on the net  Simple, but inefficient  All nodes must process packet even if they don’t care  Wastes more CPU cycles of slower machines (“broadcast radiation”)  Network loops lead to “broadcast storms”  Replicated Unicast:  Sender sends a copy to each receiver in turn  Receivers need to register or sender must be pre configured  Sender is focal point of all control traffic  Reliability = perreceiver state, separate sessions/processes at sender Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 5Why IP multicast  Applicationlayer relays:  A ―relay‖ node or set of nodes does the replicated unicast function instead of the source  Multiple relays can handle ―groups‖ of receivers and reduce number of packets per multicast = efficiency  Manager has to manually configure names of receivers in relays etc  Applevel topology may be suboptimal But bandwidth is becoming cheaper Becoming more popular in content distribution  IP Multicast: replication/multicast engine at the network layer Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 6Multicast Apps Characteristics  Number of (simultaneous) senders to the group  The size of the groups  Number of members (receivers)  Geographic extent or scope  Diameter of the group measured in router hops  The longevity of the group  Number of aggregate packets/second  The peak/average used by source  Level of human interactivity  Lecture mode vs interactive  Dataonly (eg database replication) vs multimedia Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 7IP Multicast Architecture Service model Hosts Hosttorouter protocol (IGMP) Routers Multicast routing protocols (various) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 8IP Multicast model: RFC 1112  Message sent to multicast “group” (of receivers) Senders need not be group members A group identified by a single “group address” Use “group address” instead of destination address in IP packet sent to group Groups can have any size; Group members can be located anywhere on the Internet Group membership is not explicitly known Receivers can join/leave at will Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 9IP Multicast Concepts (Continued)  Packets are not duplicated or delivered to destinations outside the group Distribution tree constructed for delivery of packets Packets forwarded “away” from the source No more than one copy of packet appears on any subnet Packets delivered only to “interested” receivers = multicast delivery tree changes dynamically Network has to actively discover paths between senders and receivers Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 10IP Multicast Addresses  Class D IP addresses  224.0.0.0 – 239.255.255.255 1 1 1 0 Group ID  Address allocation:  Wellknown (reserved) multicast addresses, assigned by IANA: 224.0.0.x and 224.0.1.x Transient multicast addresses, assigned and reclaimed dynamically, e.g., by ―sdr‖ program  Each multicast address represents a group of arbitrary size, called a “host group”  There is no structure within class D address space like subnetting = flat address space Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 11IP Multicast Service — Sending  Uses normal IPSend operation, with an IP multicast address specified as the destination  Must provide sending application a way to: Specify outgoing network interface, if 1 available Specify IP timetolive (TTL) on outgoing packet Enable/disable loopback if the sending host is/isnt a member of the destination group on the outgoing interface Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 12IP Multicast Service — Receiving  Two new operations JoinIPMulticastGroup(groupaddress, interface) LeaveIPMulticastGroup(groupaddress, interface)  Receive multicast packets for joined groups via normal IPReceive operation Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 13LinkLayer Transmission/Reception  Transmission • IP multicast packet is transmitted as a linklayer multicast, on those links that support multicast • Linklayer destination address is determined by an algorithm specific to the type of link • Reception • Necessary steps are taken to receive desired multicasts on a particular link, such as modifying address reception filters on LAN interfaces • Multicast routers must be able to receive all IP multicasts on a link, without knowing in advance which groups will be used Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 14Using LinkLayer Multicast Addresses  Ethernet and other LANs using 802 addresses:  Direct mapping Simpler than unicast No ARP etc.  32 class D addrs may map to one MAC addr IP multicast address 1 1 1 0 28 bits Group bit 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 LAN multicast address  Special OUI for IETF: 0x01005E.  No mapping needed for pointtopoint links Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 15Multicast over LANs Scoping  Multicasts are flooded across MAClayer bridges along a spanning tree But flooding may steal sending opportunity for nonmember stations which want to transmit Almost like broadcast  Scope: How far do transmissions propagate  Implicit scoping: Reserved Mcast addresses = don’t leave subnet. Also called “linklocal” addresses Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 16Scope of Multicast Forwarding  TTLbased scoping:  Multicast routers have a configured TTL threshold  Mcast datagram dropped if TTL = TTL threshold  Useful as a blanket parameter.  Administrative scoping:  Use a portion of class D address space (239.0.0.0 thru 239.255.255.255)  Truly local to admin domain; address reuse possible.  In IPv6, scoping is an internal attribute of an IPv6 multicast address Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 17Multicast Scope Control – Small TTLs  TTL expandingring search to reach or find a nearby subset of a group  Rings can be nested, but not overlapping s 1 2 3 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 18Multicast Scope Control  AdministrativelyScoped Addresses (RFC 1112 )  Uses address range 239.0.0.0 — 239.255.255.255  Supports overlapping (not just nested) domains The rest of the Internet address boundary set on interfaces to these links An administrative domain Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 19IP Multicast Architecture Service model Hosts Hosttorouter protocol (IGMP) Routers Multicast routing protocols (various) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 20Internet Group Management Protocol  IGMP: “signaling” protocol to establish, maintain, remove groups on a subnet.  Objective: keep router uptodate with group membership of entire LAN Routers need not know who all the members are, only that members exist  Each host keeps track of which mcast groups are subscribed to Socket API informs IGMP process of all joins Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 21How IGMP Works Routers: Q Hosts:  On each link, one router is elected the ―querier‖  Querier periodically sends a Membership Query message to the allsystems group (224.0.0.1), with TTL = 1  On receipt, hosts start random timers (between 0 and 10 seconds) for each multicast group to which they belong Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 22How IGMP Works (cont.) Routers: Q Hosts: G G G G  When a host’s timer for group G expires, it sends a Membership Report to group G, with TTL = 1  Other members of G hear the report and stop (suppress) their timers  Routers hear all reports, and time out non responding groups Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 23How IGMP Works (cont.) Normal case: only one report message per group present is sent in response to a query  Query interval is typically 6090 seconds When a host first joins a group, it sends immediate reports, instead of waiting for a query IGMPv2: Hosts may send a “Leave group” message to “all routers” (224.0.0.2) address  Querier responds with a Groupspecific Query message: see if any group members are present  Lower leave latency Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 24IGMPv2 1.1.1.10 1.1.1.11 1.1.1.12 H1 H2 H3 H3 Report for 232.1.2.3 1.1.1.1 rtra 2nd S,G join(s) 1st ,G join Host sends IGMPv2 report for group DR adds membership DR sends ,G join to RP (it has to, it doesn’t know the sources) DR sends S,G join to source (data provides the sources) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 25IGMPv3 1.1.1.10 1.1.1.11 1.1.1.12 H1 H2 H3 H3 Report for 232.1.2.3 sourcelist 1.1.1.1 rtra S,G join(s) Host sends IGMPv3 report for group which can specify a list of sources to explicitly include. DR adds membership. DR sends S,G join directly to sources in the sourcelist, and is not required to send ,G join to RP (see SSM discussion later) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 26IP Multicast Architecture Service model Hosts Hosttorouter protocol (IGMP) Routers Multicast routing protocols Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 27Multicast Routing  Basic objective – build distribution tree for multicast packets The “leaves” of the distribution tree are the subnets containing at least one group member (detected by IGMP)  Multicast service model makes it hard Anonymity Dynamic join/leave Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 28Simple Mcast Routing Techniques  Flood and prune  Begin by flooding traffic to entire network  Prune branches with no receivers  Examples: DVMRP, PIMDM  Unwanted state where there are no receivers  Linkstate multicast protocols  Routers advertise groups for which they have receivers to entire network  Compute trees on demand  Example: MOSPF  Unwanted state where there are no senders Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 29How to Flood Efficiently  A router forwards a packet from source (S) iff it arrives via the shortest path from the router back to S  Reverse path check  Packet is replicated out all but the incoming interface  Reverse shortest paths easy to compute  just use info in DV routing tables S  DV gives shortest reverse paths y x  Efficient if costs are symmetric z Forward packets that arrive t on shortest path from “t” to “S” (assume symmetric routes) a Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 30Problem  Flooding can cause a given packet to be sent multiple times over the same link: can filter better than this S x y a duplicate packet z b  Solution: Reverse Path Broadcasting Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 31Reverse Path Broadcasting (RPB)  Basic idea: forward a packet from S only on child links for S  Child link of router x for source S: link that has x as parent on the shortest path from the link to S S 5 6 x y forward only to child link a child link of x for S z b Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 32How to Find Child Links  Routing updates  If z tells x that it can reach S through y,  and if the cost of this path is = the cost of the path from z to S through x,  then x knows that the link to z is a child link  In case of tie, lower address wins S 5 6 x y forward only to child link a child link of x for S z b Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 33Problem  This is still a broadcast algorithm – the traffic goes everywhere – lousy filtering  First order solution: Truncated RPB Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 34Truncated RPB  Don't forward traffic onto networks with no receivers 1. Identify leaves (see below) 2. Detect group membership in leaf (IGMP)  Identify leaves  Leaf links are the child links that no other router uses to reach source S  Use periodic updates of form:  “this is my nextlink to source S”  If child is not the “nextlink” for anyone, it is a leaf Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 35Reverse Path Multicast (RPM)  Prune back transmission so that only absolutely necessary links carry traffic  Use ondemand pruning so that router group state scales with number of active groups S data message prune message a b x y v t a b Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 36Basic RPM Idea  Prune (Source,Group) at leaf if no members  Send NonMembership Report (NMR) up the tree  If all children of router R prune (S,G)  Propagate prune for (S,G) to parent R  On timeout:  Prune dropped  Flow is reinstated  Down stream routers reprune  Note: this is a softstate approach  Grafting: Explicitly reinstate subtree when  IGMP detects new members at leaf, or when a child asks for a graft. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 37Putting it together: Topology G G S G Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 38Flood with Truncated Broadcast G G S G Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 39Pruning G G Prune (s,g) S Prune (s,g) G Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 40Grafting G G G Report (g) Graft (s,g) S Graft (s,g) G Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 41After Grafting Complete G G G S G Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 42DistanceVector Multicast Routing  DVMRP consists of two major components:  A conventional distancevector routing protocol (like RIP)  A protocol for determining how to forward multicast packets, based on the unicast routing table  DVMRP router forwards a packet if  The packet arrived from the link used to reach the source of the packet Reverse path forwarding check – RPF  Packet forwarded ONLY to child links  If downstream links have not pruned the tree Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 43DVMRP limitations  Like distancevector protocols, affected by count toinfinity and transient looping Multicast trees more vulnerable than unicast  Shares the scaling limitations of RIP. New scaling limitations: (S,G) state in routers: even in pruned parts Broadcastandprune has an initial broadcast. Limited to few senders. Many small groups also undesired. Why  No hierarchy: flat routing domain Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 44Multicast Backbone (MBone)  An overlay network of IP multicastcapable routers using DVMRP  Tools: sdr (session directory), vic, vat, wb R R H R R Host/router H MBone router R H R Physical link Tunnel Part of MBone Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 45MBone Tunnels  A method for sending multicast packets through multicastignorant routers  IP multicast packet is encapsulated in a unicast IP packet (IPinIP) addressed to far end of tunnel: IP header, IP header, Transport header dest = unicast dest = multicast and data…  Tunnel acts like a virtual pointtopoint link Intermediate routers see only outer header Tunnel endpoint recognizes IPinIP (protocol type = 4) and decapsulates datagram for processing  Each end of tunnel is manually configured with unicast address of the other end Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 46Simple Routing Techniques (recall)  Flood and prune  Begin by flooding traffic to entire network  Prune branches with no receivers  Examples: DVMRP, PIMDM  Unwanted state where there are no receivers  Linkstate multicast protocols  Routers advertise groups for which they have receivers to entire network  Compute trees on demand  Example: MOSPF  Unwanted state where there are no senders Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 47Multicast OSPF (MOSPF) Extend OSPF to support multicast Multicastcapable routers flag link state routing advertisements Linkstate packets include multicast group addresses to which local members have joined Routing algorithm augmented to compute shortestpath distribution tree from a source to any set of destinations Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 48MOSPF: Example Source 1 Z W Q T Receiver 1 Receiver 2 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 49Link Failure/Topology Change Source 1 Z X W Q T Receiver 1 Receiver 2 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 50Group Membership Change Source 1 Z Receiver 3 W Q T Receiver 1 Receiver 2 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 51MOSPF: Impact on Route Computation Can’t precompute all source multicast trees Compute tree ondemand when first packet from a source S to a group G arrives New linkstate advertisement May lead to addition or deletion of outgoing interfaces if it contains different group addresses May lead to recomputation of entire tree if links are changed Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 52Routing Techniques (taxonomy)  Tree building methods:  Datadriven: calculate the tree only when the first packet is seen. Eg: DVMRP, MOSPF  Controldriven: Build tree in background before any data is transmitted. Eg: CBT  Joinstyles:  Explicitjoin: The leaves explicitly join the tree. Eg: CBT, PIMSM  Implicitjoin: All subnets are assumed to be receivers unless they say otherwise (eg via tree pruning). Eg: DVMRP, MOSPF Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 53Shared vs. Sourcebased Trees  Sourcebased trees Separate shortest path tree for each sender (S,G) state at intermediate routers Eg: DVMRP, MOSPF, PIMDM, PIMSM  Shared trees Single tree shared by all members Data flows on same tree regardless of sender (,G) state at intermediate routers Eg: CBT, PIMSM Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 54Sourcebased Trees Router S Source R Receiver R R R S S R Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 55A Shared Tree Router S Source R Receiver R R RP R S S R Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 56Shared vs. SourceBased Trees  Sourcebased trees  Shortest path trees – low delay, better load distribution  More state at routers (persource state)  Efficient in densearea multicast  Shared trees  Higher delay (bounded by factor of 2), traffic concentration  Choice of core affects efficiency  Pergroup state at routers  Efficient for sparsearea multicast Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 57Corebased Routing Protocols  Specify “meeting place” aka “core” or “rendezvous point (RP)”  Sources send initial packets to core  Receivers join group at core  Requires mapping between multicast group address and “meeting place”  Examples: CBT, PIMSM Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 58Protocol Independent Multicast (PIM)  Support for both shared and persource trees  Dense mode (persource tree) Similar to DVMRP  Sparse mode (shared tree) Core = rendezvous point (RP)  Independent of unicast routing protocol Just uses unicast forwarding table Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 59PIM Protocol Overview Basic protocol steps Routers with local members Join toward Rendezvous Point (RP) to join shared tree Routers with local sources encapsulate data in Register messages to RP Routers with local members may initiate data driven switch to sourcespecific shortest path trees PIM v.2 Specification (RFC2362) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 60PIM Example: Build Shared Tree Shared tree after R1,R2 join Source 1 Join message toward RP (,G) (,G) RP (,G) (,G) (,G) (,G) Receiver 1 Receiver 2 Receiver 3 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 61Data Encapsulated in Register Unicast encapsulated data packet to RP in Register Source 1 (,G) (,G) RP (,G) (,G) (,G) (,G) Receiver 1 Receiver 2 Receiver 3 RP decapsulates, forwards down shared tree Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 62RP Send Join to High Rate Source Shared tree Source 1 Join message toward S1 (S1,G) RP Receiver 1 Receiver 2 Receiver 3 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 63Build SourceSpecific Distribution Tree Shared Tree Source 1 Join messages (S1, G) (S1,G),(,G) RP (S1,G),(,G) (S1,G),(,G) Receiver 1 Receiver 2 Receiver 3 Build sourcespecific tree for high data rate source Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 64Forward On ―Longestmatch‖ Entry Shared Tree Source 1 Source 1 Distribution Tree (S1, G) (, G) (S1,G),(,G) RP (S1,G),(,G) (S1,G),(,G) Receiver 1 Receiver 2 Receiver 3 Sourcespecific entry is “longer match” for source S1 than is Shared tree entry that can be used by any source Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 65Prune S1 off Shared Tree Shared Tree Source 1 Source 1 Distribution Tree Prune S1 RP Receiver 1 Receiver 2 Receiver 3 Prune S1 off shared tree where if S1 and RP entries differ Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 66Multicast Address Allocation  Unicast IP addresses Allocated statically to hosts Allocated hierarchically by hosts’ org  Multicast IP addresses Allocated per session Groups cross admin boundaries Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 67Address Allocation Solutions  Central server Blocks of addresses for internal groups Leases for global addresses  Random allocation Send to group to ask if address is in use Need conflict resolution protocol Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 68Multicast AddressSet Claim (MASC)  Address allocation goals Efficient utilization of address space Aggregation of routing entries Robust and scalable  Distributed, collaborative allocation Dynamic claim and listen protocol Claim “prefixes” from parent Communicate prefixes to local addresss allocation Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 69MASC Domain A 224.0.0.0/16 A1 A1 B1 C1 Domain B Domain C 224.0.128.0/24 224.0.1.0/24 B2 C2 F1 G1 Domain F Domain G Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 70Prefix Selection  Collect available prefixes  Remove those that have been claimed  Randomly select one of remaining prefixes with shortest mask (largest range)  Claim first subprefix of desired size Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 71Reliable Multicast: The Goal  Implement reliability on top of IP multicast  Don’t necessarily care about ordering or bytestream abstraction  Why is this hard  Sender cannot keep state for unknown number of dynamic receivers Remember open dynamic group semantic  Algorithms like TCP that estimate path properties such as RTT and congestion window don’t generalize to trees. Remember: TCP is only for a unicast session  Has to address (N)ACK implosions Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 72Implosion Packet 1 is lost All 4 receivers request a resend Resend request S S 1 2 R1 R1 R2 R2 R3 R4 R3 R4 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 73Retransmission  Retransmitter Options: sender, other receivers  How to retransmit Unicast, multicast, scoped multicast, retransmission group, …  Problem: retransmissions (aka repairs) may reach destinations that don’t require a retransmission A.k.a “exposure” problem Solution: subcast the retransmission only to receivers that need it. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 74Why Subcast Exposure problem… Packet 1 does not reach R1; Packet 1 resent to all 4 receivers Receiver 1 requests a resend Resend request Resent packet S S 1 2 1 1 R1 R1 R2 R2 R3 R4 R3 R4 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 75Ideal Recovery Model Packet 1 reaches R1 but is lost Only one receiver sends NACK to before reaching other Receivers the nearest S or R with packet Resend request Repair sent S S only to Resent packet those that 1 2 1 need packet R1 R1 1 R2 R2 R3 R4 R3 R4 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 76Using the Routers • Routers do transport level Router S processing: • Buffer packets • Combine ACKs • Send retransmissions R1 RTX • Model solves implosion NACK R2 and exposure, but not scalable • Violates endtoend argument R3 R4 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 77Reliable Multicast Transport: Issues  Retransmission can make reliable multicast as inefficient as replicated unicast (N)ACKimplosion if all destinations ack at once “Crying baby”: a bad link affects entire group  Heterogeneity: receivers, links, group sizes  Anonymous/Open/Dynamic Group Model: Source does not know of destinations, and destinations may vanish  Multicast applications do not need strong reliability of the type provided by TCP. Can tolerate some reordering, delay, etc Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 78RMT building blocks: RFC 3048  NACK only: Eg: SRM uses only endtoend mechanisms.  Treebased ACK: aggregators reduce reverse traffic. Eg: RMTPII  Asynchronous Layered Coding (ALC): use of forwarderror correction (FEC), and no feedback, aka “proactive” FEC  Router assist: use of NAKs but router support for aggregation. Eg: PGM FEC retransmissions (aka reactive FEC) instead of data retransmissions Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 79Classes of RMT Protocols TRACK Ring NACKOnly RMTPII RMP SRM •Tree with Hard State •Ring Algorithm •No Hierarchy •ACK NACK FEC •ACK NACK •Multicast NACK FEC •Confirmed Delivery •Many to Many •Simple to Implement •Requires Configuration •Lowest Scalability •Moderate Scalability Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 80Classes of RMT Protocols ALC (FEC) File Transfer RouterAssist Digital MFTP PGM Fountain    •No Return Channel •Onelevel TRACK •Tree with Soft State •FEC Only •ACK NACK •NACK FEC •Highest Scalability •Simple to Implement •Scaleable Auto Config Supports Hetergeneity •Non Real Time •Req. New Router Code •Best for non real time or Shivkumar Kalyanaraman Rensselaer Polytechnic Institute semireliable video 81SRM  Originally designed for wb  Receiverreliable NACKbased  Every member may multicast NACK or retransmission Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 82SRM Request Suppression Packet 1 is lost; R1 requests Packet 1 is resent; R2 and R3 no resend to Source and Receivers longer have to request a resend Resend request Resent packet S S 1 2 1 X R1 R1 R2 R2 X Delay varies R3 R3 X by distance Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 83SRM: Stochastic Suppression 0 Time d data 1 d repair session msg d 2 NACK d 3 2d = Sender Delay = U0,D d 2 S,R = Repairer = Requestor Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 84SRM: Summary  All members get all the data that has been sent to the the multicast group (packet reliability )  Repair requests/responses are multicast.  Scope of repair requests/responses can be TTL limited or a separate “local recovery group” can be formed  Techniques to avoid implosion of repair requests, and reduce control traffic: NAK backoff timers  NACK/Retransmission suppression  Delay before sending  Delay based on RTT estimation  Deterministic + Stochastic components  Periodic session messages  Full reliability  Estimation of distance matrix among members Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 85RMTP: Fixed Hierarchy  Rcvr unicasts periodic ACK to its Designated Receiver (DR) S  DR unicasts its own ACK to its parent  Rcvr chooses closest statically configured (DR) D R2 D R1  Mcast or unicast retransmission  Based on percentage of R3 D R4 R5 requests  Scoped mcast for local recovery R R R R R R DR D R Receiver R Router Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 86RMTP: Comments : Heterogeneity Lossy link or slow receiver will only affect a local region : Position of DR critical Static hierarchy cannot adapt local recovery zone to loss points Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 87Pragmatic General Multicast Packet 1 resent to R2, R3, R4; Packet 1 reaches only R1; Not resent to R1 R2, R3, R4 request resends Routers Resend request Resent packet S S remember resend 1 2 1 X requests R1 R1 1 1 1 R2 R2 1 1 1 1 R3 R4 R3 R4 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 88ALC Protocol: Digital Fountain  Instead of using a single multicast group, split data over multiple groups  Example: Groups at 8, 16, 32, 64, 128, 256 Kbps  Receivers can receive from 8 504 Kbps  Requires a way of splitting data up  Hierarchical video codecs  File transfer with Tornado FEC codes  Supports very large and heterogeneous groups, simple to implement  Requires sparse mode routing protocols Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 89Multicast Congestion Control  What if receivers have very different bandwidths 100Mb/s 100Mb/s  Send at max R S  Send at min R 1Mb/s  Send at avg Mb/s 1Mb/s R R 56Kb/s Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 90Single Rate: Drop To Zero Problem 100 90 80 Assumptions 70 All receivers have same 0.01 60 0.10 loss rate (worst case) 50 1.00 40 10.00 All other assumptions 30 are optimistic, providing 20 an upper bound 10 0 10 20 30 40 50 100 Number of Receivers 90 1 80 Above: Droptowardszero 2 70 3 on a TCP Time Scale, 60 4 50 for different loss rates 6 40 8 30 12 20 16 Right: Droptowardszero 10 For different averaging periods 0 0 10 20 30 40 50 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute Number of Receivers 91 Percentage of Nominal Throughput Percentage of Nominal ThroughputSingle Rate: TCP Friendliness T C P T h r o u g h p u t E q u a t i o n s 1 0 0 , 0 0 0 1 0 , 0 0 0 S im p le T 0 = 3 R T 0 = 6 R 1 , 0 0 0 T 0 = 1 2 R Fairness T 0 = 1 8 R 100 Safety 10 0 . 0 1 0 . 1 1 10 100 P e r c e n t L o s s Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 92 K b p s PGM Congestion Control (PGMCC)  Receivers measure their loss and RTT  The slowest receiver sends back an ACK on each data packet (I.e. ack clock)  The sender runs TCP congestion control algorithms using these ACKs  Results in faster responsiveness but somewhat high variation in send rate  Works well for small groups, or if only a single receiver at a time is congested Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 93MultiRate: Receiver Adaptation  Receiverdriven Layered Multicast (RLM)  Layered video encoding  Each layer uses its own mcast group  Receiver subscribes to max group that will get through with minimal drops  Dynamically adapt to available capacity  Use packet losses as congestion signal  On congestion, receivers drop a layer  On spare capacity, receivers add a layer  Join experiments used for shared learning  Assume no special router support  Packets dropped independently of layer Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 94Layered Media Streams R1 joins layer 1, joins layer 2 R2 R1 joins layer 3 10Mbps 10Mbps R2 join layer 1, 512Kbps S R join layer 2 R 10Mbps fails at layer 3 128Kbps R3 R3 joins layer 1, fails at layer 2 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 95RLM Join Experiment  Receivers periodically try subscribing to higher layer  If enough capacity, no congestion, no drops  Keep layer ( try next layer)  If not enough capacity, congestion, drops  Drop layer ( increase time to next retry)  What about impact on other receivers Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 96Join Experiments Layer 4 3 2 1 Time Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 97RLM Receiver Coordination  Receiver advertises intent to add layer  Other receivers Avoid conflicting experiments If experiment fails, will see increased drops = don’t try adding layer (shared learning) OK to try adding lower layer during higher layer experiment Won’t cause drops at higher layer Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 98IP Multicast: Concerns  Deployment is difficult and slow ISP’s reluctant to turn on IP Multicast  Open Group Model: Anyone can join a Group  Interdomain routing: MSDP doesn’t scale  Address allocation is also complex  PIMSM requires a Rendezvous Point (RP): subject to attack  Multicast tried to solve too many problems… Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 99SingleSource Multicast (SSM)  Sourcespecific channel (S,G)  only S can send to G (S’,G) (S,G)  another source S’ must use a separate channel (S’,G)  hosts join channels, so a member joining only (S,G) will NOT receive traffic from S’  Current infrastructure uses Any Source Multicast (ASM)  any source can send to any group at any time Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 100Why SSM  Network Operator  trivial address allocation (16 million addresses per host)  no networklayer source discovery (PIM RP and/or MSDP moved to the application layer)  overcomes two significant obstacles to deployment  Content Provider  exclusive access to multicast groups (no interruptions)  permanent multicast groups (easy to advertise)  provides better service Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 101Problem: How to find the Source source source Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 102How to Find the Sources  broadcast everywhere receivers decide when they do not want the traffic  any source multicast (ASM) PIM SM/MBGP/MSDP/IGMPv2 use a rendezvous point (RP) receivers send joins along reverse path to RP sources send traffic to RP  source specific multicast (SSM) PIM/MBGP/IGMPv3 require receivers to already know source(s) use some outofband mechanism Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 103How MSDP works with PIMSM A SA RP Source C D SA Join RP Join RP Join B Receiver Join Join RP SA MSDP peer PIM message Physical link MSDP message Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 104How SSM Works A Source C D Join Join Join Join B Receiver Join Join PIM message Physical link Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 105SSM Advantages (cont’d)  No RP, No need for MSDP  All joins are (S,G), so no need for Class D address allocation  Receivers find out about sources through outofband means (such as a web site)  SSMonly implementations are much simpler than the full PIMSM  No RP, No Bootstrap RP Election  No Register state machine  No need to keep (,G), (S,G,rpt) and (,,RP) state  No (,G) Assert State Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 106Applicationlevel Multicast  Do we really need network level multicast Efficiency Logical rendezvous  Can we get efficiency by creatively using the actual members or a few infrastructure nodes Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 107Applicationlevel Multicast S S R2 R2 R3 R4 R3 R4 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 108Narada: End System Multicast Gatech Stanford Stan1 Stan2 CMU Berk1 Berk2 Berkeley Overlay Tree Stan1 Gatech Stan2 CMU Berk1 Berk2 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 109Performance Concerns Delay from CMU to Stan1 Gatech Berk1 increases Stan2 CMU Berk2 Berk1 Duplicate Packets: Gatech Stanford Stan1 Bandwidth Wastage Stan2 CMU Berk1 Berk2 Berkeley Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 110Overlay Tree  The delay between the source and receivers is small  Ideally, the number of redundant packets on any physical link is low  Heuristic:  Every member in the tree has a small degree  Degree chosen to reflect bandwidth of connection to Internet CMU CMU CMU Stan2 Stan2 Stan2 Stan1 Stan1 Stan1 Gatech Gatech Berk1 Berk1 Berk1 Gatech Berk2 Berk2 Berk2 High latency High degree (unicast) ―Efficient” overlay Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 111Mesh  Advantages:  Offers a richer topology  robustness; don’t need to worry to much about failures  Don’t need to worry about cycles  Desired properties  Members have low degrees  Shortest path delay between any pair of members along mesh is small CMU Stan2 Stan1 Berk2 Berk1 Gatech Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 112Overlay Trees  Source routed minimum spanning tree on mesh  Desired properties Members have low degree Small delays from source to receivers CMU Stan1 Stan2 Stan2 Stan1 Berk1 Gatech Berk2 Berk2 Berk1 Gatech Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 113Summary  IP multicast issues and applications  Multicast over LANs and scoping  IGMP  Multicast Routing and MBONE  Reliable multicast transports  Multicast Congestion Control  SSM, Overlay Multicast Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 114
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.ShivJindal
User Type:
Teacher
Country:
India
Uploaded Date:
19-07-2017