Transcript IP History and Overview

Satellite Multicast for Web
Applications
Hilmar Linder
[email protected]
University of Salzburg/Austria
Overview
• Introduction
• IP multicast
• Reliable Multicast:
– Building Blocks
– The RRMP Protocol
• Summary
• Questions
SatCAST
H. Linder - unisal
2
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”
SatCAST
H. Linder - unisal
3
Why IP multicast ? (contd)
• Replicated Unicast:
– Sender sends a copy to each receiver in turn
– Receivers need to register or sender must be preconfigured
– 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}
SatCAST
H. Linder - unisal
4
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
SatCAST
H. Linder - unisal
5
Multicast Protocol Architecture
Applications
Middleware
Reliable
Unreliable
TCP
Reliable Multicast
Internet Protocol
IP Multicast
Networking Infrastructure
SatCAST
H. Linder - unisal
6
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
SatCAST
H. Linder - unisal
7
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)
SatCAST
H. Linder - unisal
8
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:
•
•
•
•
SatCAST
Flooding
Spanning trees
Reverse-path broadcasting
Core based trees
H. Linder - unisal
9
Multicast Applications
•
•
•
•
•
•
•
•
•
SatCAST
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
H. Linder - unisal
10
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
SatCAST
H. Linder - unisal
11
What applications need Reliable
Multicast?
Real-time
Non-real-time
Multimedia
• Video server
• Video conferencing
• Internet audio
• Multimedia Events
• Replication:
• Video & web servers
• Kiosks
• Content delivery
• Intranet & Internet
Data-only
• Stock quotes
• News feeds
• White boarding
• Interactive gaming
• Data delivery
• Server-server
• Server-desktop
• DB replication
• SW distribution
• Requires reliability
SatCAST
H. Linder - unisal
12
Multicast Protocol Architecture
Applications
Middleware
Reliable
Unreliable
TCP
Reliable Multicast
Internet Protocol
Multicast
Networking Infrastructure
SatCAST
H. Linder - unisal
13
Goal
• Fully reliable multicast:
– All packets delivered to all receivers
• Can’t we just extend TCP?
S
Data
ACKs
SatCAST
H. Linder - unisal
R
14
Data Reliability
S
Data
A
SatCAST
B
C
H. Linder - unisal
D
15
Data Reliability
S
ACKs
A
SatCAST
B
Data
C
H. Linder - unisal
D
16
Data Reliability
S
A
SatCAST
B
“ACK Implosion”
C
H. Linder - unisal
D
17
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)
SatCAST
H. Linder - unisal
18
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
SatCAST
H. Linder - unisal
19
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
SatCAST
H. Linder - unisal
20
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!
SatCAST
H. Linder - unisal
21
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
S
A
B
NAK
(suppressed)
SatCAST
H. Linder - unisal
22
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
SatCAST
H. Linder - unisal
23
Forward Error Correction based
on (n,k) Encoding
1
2
k
Original packets
Encode
(copy 1st k)
1
2
k
k+1 k+2
n
Take any k
Decode
1
SatCAST
2
k
H. Linder - unisal
Original packets
24
Hybrid ARQ Example
S
2
1
A
SatCAST
B
H. Linder - unisal
25
Hybrid ARQ Example (contd)
S
2
2
1
1
A
SatCAST
B
H. Linder - unisal
26
Hybrid ARQ Example (contd)
S
1
SatCAST
A
B
H. Linder - unisal
2
27
Hybrid ARQ Example (contd)
S
NAK(1 packet lost)
1
A
B
2
(suppressed)
SatCAST
H. Linder - unisal
28
Hybrid ARQ Example (contd)
S
=
+
2
1
SatCAST
A
B
H. Linder - unisal
Retransmission
of Parity
1
2
29
Hybrid ARQ Example (contd)
S
P
1
SatCAST
P
A
B
H. Linder - unisal
2
30
Hybrid ARQ Example (contd)
S
A
B
P 1
SatCAST
2 P
H. Linder - unisal
31
Hybrid ARQ Example (contd)
S
=
2
SatCAST
A
+
P
B
1
+
2
H. Linder - unisal
=
P
1
32
Hybrid ARQ Example (contd)
S
A
B
1 2
1 2
Two losses recovered with a single retransmission...
SatCAST
H. Linder - unisal
33
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
SatCAST
H. Linder - unisal
34
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
SatCAST
H. Linder - unisal
35
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:
–
–
–
–
SatCAST
Heterogeneous loss
Loss in shared links of the multicast tree dominates
Small groups
Non-interactive applications
H. Linder - unisal
36
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
SatCAST
H. Linder - unisal
37
Proactive Error Control
• Parities are sent pro-actively along with data
– avoid retransmission
– reduce latency
S
S
2
2
1
1
A
B
=
2
SatCAST
A
+
P
H. Linder - unisal
1
B
+
2
=
P
1
38
Mercure Network Simulation
PEK
Sender in PEK, Receiver in NBO
Packet Loss Rate: 5
ARE
NBO
OCO
QLK
BKK
Connections btw. A Sites
SatCAST
H. Linder - unisal
39
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
SatCAST
H. Linder - unisal
40
Questions ??
SatCAST
H. Linder - unisal
41