Transcript Document

A loss detection Service for Active
Reliable Multicast Protocols
Moufida MAIMOUR & C. D. PHAM
INRIA-RESO
RESAM UCB-Lyon – ENS Lyon
INC’02, Plymouth
Tuesday, July 16th, 2002
Outline
•
•
•
•
•
•
Introduction
The DyRAM protocol
The active loss detection service
An active-based reliable multicast architecture
Some results (analysis, simulation, implementation)
Conclusion
From unicast…
Sender
• Problem
Sending same data to
many receivers via
unicast is inefficient.
data
data
data
data
data
data
Receiver
Receiver
Receiver
…to multicast on the Internet.

Sender
Problem
Sending same data to
many receivers via
unicast is inefficient.

Solution
data
data
data
data
Using multicast is
more efficient
Receiver
Receiver
Receiver
Reliable multicast
• At the routing level : IP Multicast provides
efficient delivery without any reliability
guarantees.
• Many multicast applications require
reliability.
• Reliability has to be addressed at a higher
level.
Reliable multicast protocols
• End-to-end solutions :
Only the end hosts (the source and/or the
receivers) are involved.
• In-network solutions :
Routers are involved in the recovery
process.
Active routers-based solutions
What are active routers ?
Active routers are able to perform
customized computations on the
messages flowing through them.
DyRAM main characteristics
• DyRAM is based on active services (routerassisted).
• the recovery is performed from the receivers (no
data cache at the routers)
• A recovery tree is constructed on a per-packet
basis via a replier election mechanism.
• Use of NACKs combined with periodic ACKs.
Main Active Services in DyRAM
• NACK suppression
• Subcast of repair packets
• Dynamic replier election
NACKs suppression
data4
only one NACK is
forwarded to the
source
Replier election and subcast
NAK 2 from link2
NAK 2 from link1
D0
DyRAM
IP multicast
2
NAK 2
0
1
Repair 2
NAK 2,@
D1
Repair 2
DyRAM
Repair 2
IP multicast
R1
NAK 2
1
0
IP multicast
NAK 2,@
NAK 2,@
IP multicast
NAK 2
R4
R3
IP multicast
Repair 2
R2
R5
R7
The active loss detection service
data4
A NACK is sent by the
router
The active loss detection
implementation
The Track List (TL) structure which maintains
for each multicast session,
• lastOrdered : the sequence number of the
last received packet in order
• lastReceived : the sequence number of the
last received data packet
• lostList : list of not received data packets in
between.
The active loss detection
implementation (cont.)
• On reception of a data packet with a
sequence number seq > TL.lastOrdered+1
• for each lost data packet (TL.lastOrdered <
lostseq < seq & lostseq Є TL.lostList),
• send a NACK for lostseq toward the source.
• ignore similar NACKs from downstream links
for a given period.
Where to place the active routers ?
PSTN
ISDN
xDSL
GSM, UMTS
10Mbits/s
core network
Gbits/s
Server
100Mbits/s
wireless LAN
1Mbits/s, 10MBits/s
visio-conferencing
Location of the loss detectioncapable routers
The
loss
detection service
should be located
not too far from
the source so the
corresponding
overhead is
justified !
Specialized active routers architecture
source
The active router associated
to the source can perform
early processing on packets.
core network
Gbits rate
A hierarchy of active routers
can be used for processing
specific functions at different
layers of the hierarchy : NACK
suppression, subcast, replier
election.
Simulation model
Simulation results
4 receivers/group
p=0.25
#grp: 6…24
DyRAM implementation
• Tamanoir execution environment
• Java 1.3.1 and a linux kernel 2.4
• A set of receivers and 2 PC-based routers
(Pentium II 400 MHz 512 KB cache 128MB
RAM)
• Active processing cost of a
• data packet : 20 micro sec
• NACK packet : 135 micro sec
• repair packet : 123 micro sec
Conclusion & future work
• Reliability on large-scale multicast session is
difficult. Active services at the edges can provide
efficient solutions for reducing implosion,
recovery delays and exposure problems and so
achieving scalability.
• Optimizing the replier election based on an
estimation of the receivers power (by means of
BW, delay …)
• A congestion control is currently under evaluation
and will be integrated into DyRAM in the near
future.