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.