Notes

Outline

Satellite Multicast for Web Applications Hilmar Linder hlinder@cosy.sbg.ac.at University of Salzburg/Austria

Overview Introduction IP multicast Reliable Multicast: Building Blocks The RRMP Protocol Summary Questions

Why IP multicast ? Need for efficient delivery to multiple destinations across inter/intranets Broadcast: Send a copy to every machine on the net Simple, but inefficient All nodes “must” process the packet even if they don’t care Wastes more CPU cycles of slower machines (“broadcast radiation”) Network loops lead to “broadcast storms”

Why IP multicast ? (contd) 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 Latency = time between the first and last receiver getting a copy {can be large if transmission times are large}

Why IP multicast ? (contd) Application-layer 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 => too much administrative burden Alternative: build replication/multicast engine at the network layer

Multicast Protocol Architecture

IP multicast concepts Message sent to multicast “group” (of receivers) Senders need not be group members Each group has a “group address” – Class D Address Use “group address” instead of destination address in IP packet sent to group Groups can have any size End-stations (receivers) can  join/leave groups at will

IP multicast concepts (contd) Packets are not unnecessarily duplicated or delivered to destinations outside the group Distribution tree for delivery/distribution of packets Packets forwarded “away”  from the source Only one copy of a 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 Non-member nodes even on a single subnet do not receive packets (unlike subnet-specific broadcast)

IP multicast concepts (contd) Group membership on a single subnet is achieved through IGMP (and ICMPv6 in IPv6) Tree is built by multicast routing protocols. Algorithms based on: Flooding Spanning trees Reverse-path broadcasting Core based trees

Multicast Applications News/sports/stock/weather updates Distance learning Routing updates (OSPF, RIP etc) Pointcast-type “push” apps Videoconferencing, shared whiteboards Distributed interactive gaming or simulations Email distribution lists Voice-over-IP Database replication

Multicast Application Characteristics Number of (simultaneous) senders to the group 1XN versus NxM The size of the groups Number of members (receivers) Geographic extent The lifetime of the group Level of human interactivity Lecture mode versus interactive Data-only (e.g. database replication) versus multimedia Number of aggregate packets/second The peak/average bandwidth used by source

What applications need Reliable Multicast?

Multicast Protocol Architecture

Goal Fully reliable multicast: All packets delivered to all receivers Can’t we just extend TCP?

Data Reliability

Data Reliability

Data Reliability

Challenges for Reliable Multicast Scalability to the number of receivers: Heterogeneity of receivers Feedback implosion Congestion control How to achieve reliability: Automatic Repeat Request (ARQ) Forward Error Correction (FEC)

Building Blocks Elements from unicast: Loss detection Loss recovery: ARQ versus FEC Additional elements for multicast Mechanisms for control message Implosion Avoidance Mechanisms to deal with heterogeneous receivers

Where to place the loss detection Receiver-based (NAK) distributed over receivers 1 NAK per packet (for all receivers) Sender-based (ACK) centralized 1 ACK per receiver and packet needs a table of per-receiver ACK

Feedback Processing Assume R receivers, independent packet loss probability Feedback per packet: average number of ACKs: R - p*R average number of NAKs: p*R -> more ACKs than NAKs Processing: higher throughput for receiver-based loss detection Reliability needs ACK: No NAK does not mean successful reception!

Feedback suppression At Receivers: choose a random timer in [0,T] due to a exponential distribution and listen for other’s feedback On reception of feedback: cancel timer On timer expiration: multicast feedback, so that other receivers can see it

Loss Recovery FEC versus ARQ: ARQ is the only way to guarantee 100% reliability Who retransmits: Sender, other receiver, network node How to retransmit: Unicast or Multicast What is retransmitted Originals or Parities

Forward Error Correction based on (n,k) Encoding

Hybrid ARQ Example

Hybrid ARQ Example (contd)

Hybrid ARQ Example (contd)

Hybrid ARQ Example (contd)

Hybrid ARQ Example (contd)

Hybrid ARQ Example (contd)

Hybrid ARQ Example (contd)

Hybrid ARQ Example (contd)

Hybrid ARQ Example (contd)

Hybrid ARQ Algorithm Hybrid ARQ Algorithm: Sender send k original packets Receiver detects that k-l packets have been received and sends a NAK(l) Sender receives NAK(L1), NAK(L2), .., NAK(Ln) from the receivers and sends Lmax = max {L1, L2, .., Ln} parity packets. A single parity packet can repair the loss of different data packets at different receivers

Performance Measure The mean number of transmission E[M] per packet affects: The bandwidth needed The total transfer latency The processing rate at the sender and receiver With FEC, E[M] can be reduced dramatically Processing costs for FEC need to be considered How fast is encoding/decoding Throughput of a protocol based on FEC

Scenario specific selection of Mechanisms FEC is of particular benefit in the following scenarios: Large groups No feedback Heterogeneous RTTs Limited buffer ARQ is of particular benefit in the following scenarios: Heterogeneous loss Loss in shared links of the multicast tree dominates Small groups Non-interactive applications

Restricted Reliable Multicast Protocol (RRMP) Error Detection and Correction Module FEC only Hybrid ARQ Proactive ARQ Transport Module: Bandwidth Management Flow Control RTT estimation Group Management Statistics Module

Proactive Error Control Parities are sent pro-actively along with data avoid retransmission reduce latency

Mercure Network Simulation

Summary There is no “one-fits-all” reliable multicast protocol Application requirements influence the decision for the “best” multicast protocol Standardization of RM “building blocks” is currently ongoing Further research for “Internet compatibility” of RM protocols is necessary

Questions ??