Transcript multicast!

An analysis of a router-based loss
detection service for active
reliable multicast protocols
M. Maimour, C. Pham
RESAM UCB Lyon - INRIA RESO
ENS Lyon
ICON’02, Singapor
Thursday, August 29th, 2002
A (very) quick overview of multicast
Sender
Sender
data
data
data
without
multicast
data
data
with
multicast
Receiver
Receiver
IP multicast
RFC 1122
data
data
data
data
Receiver
data
Receiver
Receiver
Receiver
2
multicast!
multicast!
multicast!
multicast!
multicast!
multicast!
multicast!
Everybody's talking
about multicast! Really
annoying ! Why would I
need multicast for by
the way?
multicast!
multicast!
multicast!
multicast!
multicast!
Challenges for the Internet
Think about…









high-speed www
video-conferencing
video-on-demand
interactive TV programs
remote archival systems
tele-medecine, white board
high-performance computing, grids
virtual reality, immersion systems
distributed interactive simulations/gaming…
4
The Wild Wild Web
important data
heterogeneity,
link failures,
congested routers
packet loss,
packet drop,
bit errors…
?
5
Multicast difficulties

At the routing level





management of the group address (IGMP)
dynamic nature of the group membership
construction of the multicast tree (DVMRP,
PIM, CBT…)
multicast packet forwarding
At the transport level



reliability, loss recovery strategies
flow control
congestion avoidance
6
Reliable multicast

What is the problem of loss recovery?




feedback (ACK or NACK) implosion
replies/repairs duplications
difficult adaptability to dynamic
membership changes
Design goals



reduces recovery latencies
reduces the feedback traffic
improves recovery isolation
7
•
•
•
•
•
•
YOID•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
10 human years (means much more in computer year)
•
•
•
Application-based
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
HBM
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
ALMI
•
•
•
•
•
•
FLID
•
•
•
•
•
•
•
•
MTP
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
RLC
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
AFDP
•
•
•
•
•
•
•
•
•
•
•
•
••
•
RLM
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
• •
•
•
•
•
•
•
••
•
•
••
•
•
PGM
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
AER•
•
•
•
•
•
RMANP
•
•
•
•
•
•
••
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
ARM
•
•
•
•
•
•
•
•
•
•
•
••
•
•
••
•
CIFL•
•
•
•
•
•
•
•
•
DyRAM
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Layered/FEC
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
XTP
•
•
•
•
•
•
••
•
•
• •
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
••
•
•
•
Router supported,
active networking
•
•
•
•
•
•
•
•
•
•
•
•
•
RMF
•
•
•
•
•
•
•
•
•
•
•
•
LBRM
•
•
•
•
•
•
•
•
•
•
•
••• •
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
SRM
•
•
•
•
•
•
•
•
•
•
•
•
LMS
•
•
•
•
•
•
•
•
End to End
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
RMTP
•
•
•
•
••
••
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
TRAM
••
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
The reliable
multicast
universe
•
•
•
•
•
•
•
•
•
•
•
•
Logging server/replier
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
• •
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•

•
••
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
••
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
• •
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•

•
•
•
•
•
••• •
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
PGM
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
RMANP
•
•
•
•
•
AER
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
ARM
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Routers have specific
functionalities/services
for supporting multicast
flows.
Active networking goes a
step further by opening
routers to dynamic code
provided by end-users.
Open new perspectives
for efficient in-network
services and rapid
deployment.
••
••
•
•
DyRAM
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•

••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Router supported,
active networking
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Ex: Global NACKs suppression
data4
only one NACK is
forwarded to the
source
10
The case of loss detection

Traditionally the loss detection is
performed by :



the sender (use of ACKs) in senderinitiated protocols
the receivers (use of NACKs) in receiverinitiated protocols
We want to investigate a routersupported loss detection service
11
Motivations and design choices




Enable early packet loss detection
(EPLD) to reduce the latency
Routers keep track of the packet
sequence: 2 variables per multicast
session
Implemented as an active service,
executed by an active router
EPLD services are enabled at specific
locations in the network
12
"Satellite picture" of the Internet
from UREC, http://www.urec.fr
13
Users' accesses
residentials
offices
PSTN
ADSL
Cable
…
Internet
Data
Center
metro ring
Network Provider
campus
Network Provider
Internet
14
1st step: Analysis and network model


Each node is modeled by a M/G/1 queue.
The delay analysis is based on the mean
waiting time of the system.
15
The methodology



The different mean flow rates λ1, λ2,... λn
of the node with their respective
service requirement X1, X2, ..., Xn.
The load ρ at this node can be computed
using : ρ = Σλi E[Xi].
The mean waiting time (P-K formula) :
E[W]= Σλi E[Xi2] / 2(1- ρ)
16
Performance comparaison

Protocol A :



Nacks suppression
Subcast
Protocol D :



Nacks suppression
Subcast
Early Packet Loss Detection service
17
Numerical results






The router position influence
Loss detection service as a function of the
loss rate
Maximum loss rate supported by the
system
Required processing power at the routers
so they are never the bottleneck
Load at the different nodes
The gain as a function of B (# recv)
18
Router position
19
Router position (cont.)
20
Loss detection service gain
21
Max loss rate supported as a function of
the processing power of the routers
22
Required processing power at the routers
so they are never the bottleneck
23
Load at the different nodes
low
overhead!
24
The gain as a function of B
25
2nd step: Adding EPLD in DyRAM

DyRAM is an active reliable multicast
protocol with local recoveries from
elected repliers
more accurate model
26
Simulation results
4 receivers/group
#grp: 6…24
simulation results
very close to those
of the analytical
study
EPLD is very
beneficial
to DyRAM
p=0.25
27
Conclusions




Early packet loss detection by routers is
found to enhance the performances of
reliable multicast
Reduction of the recovery latency is
targeted to enable distributed
applications on computational grids
Simulations and experimental test-beds
are encouraging
Incorporated into egde-routers?
28