Transcript Active networks, (and reliable multicast) - univ

ACTIVE RELIABLE
MULTICAST
HOW IT WORKS, HOW IT CAN BE
USED ON COMPUTATIONAL GRIDS
Congduc PHAM
SUN's "Gourmandise Cérébrale"
SUN Labs Europe,
Thursday, February 14th, 2002
http://www.ens-lyon.fr/LIP/RESAM
Outline



Introduction
How it works
How it can be used on computational
grids
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
From unicast…

Problem


Sender
Sending same data
to many receivers
via unicast is
inefficient
Example

data
data
data
data
data
data
Popular WWW sites
become serious
bottlenecks
Receiver
Receiver
Receiver
5
…to multicast on the Internet.



Not n-unicast from
the sender
perspective
Efficient one to
many data
data
distribution
Towards low
latence, high
Receiver
bandwidth
Sender
data
data
data
Receiver
Receiver
6
User perspective of the Internet
from UREC, http://www.urec.fr
7
What it is in reality…
from UREC, http://www.urec.fr
8
Links: the basic element in networks

Backbone links



optical fibers
10 to 160 GBits/s with DWDM techniques
End-user access






V.90 56Kbits/s modem on twisted pair
512Kbits/s to 2Mbits/s with xDSL modem
1Mbits/s to 10Mbits/s Cable-modem
64Kbits/s to 1930Kbits/s ISDN access
9.6Kbits/s (GSM) to 2Mbits/s (UMTS)
155Mbits/s to 1Gbits/s SDH
9
Routers: key elements of internetworking

Routers




run routing protocols and build routing
table,
receive data packets and perform relaying,
may have to consider Quality of Service
constraints for scheduling packets,
are highly optimized for packet forwarding
functions.
10
The Wild Wild Web
important data
heterogeneity,
link failures,
congested routers
packet loss,
packet drop,
bit errors…
?
11
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
12
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
13
Active Reliable Multicast
How does
it work?
What is active networking?





Programmable nodes/routers
Customized computations on packets
Standardized execution environment
and programming interface
No killer applications, only a different
way to offer high-value services, in an
elegant manner
However, adds extra processing cost
15
Motivations behind active networking

user applications can implement, and
deploy customized services and
protocols



specific data filtering criteria (DIS, HLA)
fast collective and gather operations…
globally better performances by
reducing the amount of traffic


high throughput
low end-to-end latency
16
Active networks implementations

Discrete approach (operator's approach)



Adds dynamic deployment features in
nodes/routers
New services can be downloaded into
router's kernel
Integrated approach



Adds executable code to data packets
Capsule = data + code
Granularity set to the packets
17
The discrete approach

Separates the injection of programs
from the processing of packets
A1
A
2
active code A1
active code A2
Data
Data
18
The integrated approach

User packets carry code to be applied
on the data part of the packet
data
code
data
data
data
data

code
High flexibility to define new services
19
An active router
AL packet
IP input processing
some layer for executing code.
Let's call it Active Layer
IP output processing
IP packet
IP packet
Filter Action
Routing
agent
Forwarding
table
Packet scheduler
IP output processing
IP packet
IP packet
Packet scheduler
20
Solutions for Reliable Multicast

Traditional




end-to-end retransmission schemes
scoped retransmission with the TTL fields
receiver-based local NACK suppression
Active contributions




cache of data to allow local recoveries
feedback aggregation
subcast
…
21
A step toward active services: LBRM
22
Active local recovery


routers perform cache of data packets
repair packets are sent by routers,
when available
data
data
data5
data1
data2
data3
data4
data5
data1
data2
data3
data4
data5
data1
data2
data3
data5
23
Global NACKs suppression
data4
only one NACK is
forwarded to the
source
24
Local NACKs suppression
data
NACK
25
Active subcast features

Send repair packet only to the relevant
set of receivers
26
Active Reliable Multicast
How can it
be used?
Computational grids
The DyRAM framework
Some simulation results
Conclusions and perspectives
What is a computational grid?
application user
from Dorian Arnold: Netsolve Happenings
28
Some grid applications
Astrophysics:
Black holes,
neutron stars,
supernovae
Mechanics:
Fluid dynamic,
CAD, simulation.
Distributed &
interactive
simulations:
DIS, HLA,Training.
Chemistry&biology:
Molecular simulations,
Genomic simulations.
29
Reliable multicast: a big win for grids
Data replications
Code & data transfers,
interactive job submissions
SDSC IBM SP
1024 procs
5x12x17 =1020
224.2.0.1
Data communications for
distributed applications
(collective & gather
operations, sync. barrier)
NCSA Origin Array
256+128+128
5x12x(4+2+2) =480
Databases, directories
services
CPlant cluster
256 nodes
Multicast address group 224.2.0.1
30
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
31
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Resource Broker:
•
7 sites OK, but
need
•
to send data fast…
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
• •
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Nobel
Prize is on the way :-)
•
•
•
•
•
•
•
•
The phenomenon
was short• but we manage
•
•
to react quickly.
This would have not
been possible
without
efficient
•
•
•
•
•
•
multicast facilities to enable quick
•
•
•
reaction
and fast distribution
of • data.
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
• •
•
Congratulations, you
have done
a great
•
•
job, it's •the discovery of the
•
century!!
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
••• •
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
From [email protected]
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
We see
something,
•
OK! • Resource
Estimator
but too weak. •
Says need 5TB, 2TF.
•
Please simulate
•
Where can I do this?•
to enhance signal!
•
•
•
•
•
•
•
•
•
•
•
•
•
••
•
•
•
•
•
•
••
•
•
•
•
•
•
•
•
•
•
•
•
Resource Broker:
• match…
LANL is best
•
•but down for the
moment •
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
From reliable multicast to Nobel prize!
•
•
•
•
•
•
•
•
•
•
•
•
Multicast communications on grids




Dynamic groups are very difficult to
handle with the reliability constraint
Mixture of high-throughput (data
replication) and low latencies
(distributed applications) needs
The application under consideration can
have a great impact on the protocol
design (i.e. local recoveries)
A one protocol-fits-all solution is
difficult!
32
The DyRAM framework (M. Maimour)







Receiver-based: use of NACKs.
No cache in routers, receivers perform
local recoveries…
…which are based on a tree structure
constructed on a per-packet basis.
Routers play an active role.
Low-overhead active services
Focus on low latency
Load balancing features
33
where to put active
components?
1000 Base FX
active router
active router
core network
Gbits rate
Server
active router
active router
100 Base TX
active router
Related works on local recovery

SRM


RMTP, TMTP, LMS, PGM, TRAM


any receiver in the neighborhood
a designated receiver
LBRM

a logging server
35
Active services in DyRAM

Designed to provide low latencies





Session initialization
Early packet loss detection
NACK aggregation
Subcast of repair packets
Dynamic replier election
36
DyRAM and IP multicast


Relies on IP multicast but has few
interactions
Runs its own simple session protocol to
gather additional topological information
at the DyRAM level to enhance the
group anonymity imposed by IP multicast
37
DyRAM: session initialization
@R1,vif 1
@R2,vif 2
@R3,vif 2
@R4,vif 2
@D1,vif 0
Total Replies=5
D0
DyRAM
IP multicast
2
INIT
0
1
INIT
Total Replies=3
Reply @
D1
INIT
DyRAM
Reply @D1
R1
IP multicast
IP multicast
1
INIT
0
@R5,vif 1
@R6,vif 1
@R7,vif 0
INIT
Reply @
Reply @
IP multicast
IP multicast
Reply @
Reply @
R4
R3
R2
R5
R6
R7
How and where losses can occur




Packet losses occur mainly in edge
routers
In this case, all downstream links would
most likely be affected by a packet loss
On medium speed LAN, when a packet
has been sent on the wire all computers
will usually be able to receive it
On very high-speed LAN, computers can
be the bottleneck
39
DyRAM: early packet loss detection



The repair latency can be reduced if the
lost packet could be requested as soon
as possible
DyRAM realizes this functionality by
enabling some routers to detect losses
and therefore to generate NACKs
towards the source
This loss detection service should be
located near the source, but not too
near!
40
DyRAM: replier election




A receiver is elected to be a replier for
each lost packet
Several recovery trees at a given time
Load balancing can be taken into
account, several optimizations possible
Uses the topological information
gathered during the session
initialization
41
DyRAM: replier election
@R1,vif 1
@R2,vif 2
@R3,vif 2
@R4,vif 2
@D1,vif 0
NAK 2 from R1
NAK 2 from R2
NAK 2 from R3
NAK 2 from R4
D0
DyRAM
IP multicast
2
NAK 2
0
1
Repair 2
NAK 2,@
D1
Repair 2
DyRAM
Repair 2
@R5,vif 1
@R6,vif 1
@R7,vif 0
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
R6
R7
DyRAM: subcasting




Tries to solve the exposure problem
Using the NACK pattern to select
relevant links can not avoid exposure
Use of IP addresses is more costly but
allows for an exact matching
Several optimizations possible, including
a dynamic selection of the appropriate
mechanism
43
Routers’ soft state
The NACK State (NS) structure which
maintains for each lost packet,
 seq : the sequence number of the
requested packet.
 rank : the number of NACK received.
 subList : List of the links from which
similar NACKs arrived (or IP addresses).
44
Routers’ soft state (cont.)
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 : a bit vector that keeps track
of received packet
Reduces the replier election delay.
45
DyRAM overview
One
benefit
of
active
networking is to unload the
source
from
heavy
retransmission overheads.
The backbone is fast,
very fast (DWDM,
10Gbits/s
not
uncommun),
so
nothing else than fast
forwarding functions.
Any receiver can be
designated as a replier
for a loss packet.The
election is performed
by the associated
upstream active router
on a per-packet basis.
Therefore several loss
recovery trees can coexist in parallel at a
given time.
source
100 Base TX
active router
active router
core network
Gbits rate
active router
1000 Base FX
active router
active router
DyRAM can increases
performances by
associating a dedicated
active router to a pool of
computing resources.
The active router
associated to the source
can perform early
processing on packets.
For instance our DyRAM
protocol uses subcast
and loss detection
facilities in order to
reduce the end-to-end
latency.
A hierarchy of active
routers can be used
for processing specific
functions at different
layers of the hierarchy.
For instance, having
an active router at the
nearest location from
the source/destination
could performs very
efficient NACK packets
suppression
Some simulation results




Network model and used metrics
Local recovery from the receivers
DyRAM vs. ARM
DyRAM combined with cache at routers
47
Network model
10 MBytes file transfer
48
Metrics



Load at the source : the number of the
retransmissions from the source.
Load at the network : the consumed
bandwidth.
Completion time per packet (latency).
49
Local recovery from the receivers (1)
4 receivers/group

#grp: 6…24
Local recoveries
reduces the load at
the source
(especially for high
loss rates and a
large number of the
receivers).
p=0.25
50
Local recovery from the receivers (2)

As the groups size
increases, doing
the recoveries
from the receivers
greatly reduces the
bandwidth
consumption
48 receivers distributed in g groups  #grp: 2…24
51
Local recovery from the receivers (3)
4 receivers/group

#grp: 6…24
Local recoveries
reduces the endto-end delay (per
packet)
p=0.25
52
DyRAM vs ARM

ARM performs
better than
DyRAM only for
very low loss
rates and with
considerable
caching
requirements
53
DyRAM with cache at the routers (1)

ARM without cache
When DyRAM
benefits from the
cache at the
routers in addition
to the recovery
from the receivers,
it always performs
better than ARM.
p=0.25
54
DyRAM with cache at the routers (2)

ARM without cache
When DyRAM
benefits from the
cache at the
routers in addition
to the recovery
from the receivers,
it always performs
better than ARM.
p=0.25
55
DyRAM: early loss detection
4 receivers/group #grp: 6…24
p=0.25
p=0.5
56
Conclusions


Reliability on large-scale multicast
session in difficult. Active services can
provide efficient solutions for avoiding
implosion and exposure.
The main design goals for DyRAM is to
reduce the end-to-end delays (recovery
for instance) to enable large distributed
applications on computational grids.
57
References



D. L. Tennehouse, J. M. Smith, W. D. Sincoskie,
D. J. Wetherall, and G. J. Winden. A survey of
active network research. IEEE Communications
Magazine, pages 80--86, January 1997.
L. Wei, H. Lehman, S. J. Garland, and D. L.
Tennenhouse. Active reliable multicast. IEEE
INFOCOM'98, March 1998.
M. Maimour, C. Pham. A Throughput Analysis of
Reliable Multicast Protocols in an Active
Networking Environment. IEEE ISCC'2001,
Hammanet, Tunisia.
58