Transcript Multicast Routing Algorithms

Multicast Routing
Algorithms
Multicast routing
 Flooding and Spanning Tree
 Forward Shortest Path algorithm
 Reversed Path Forwarding (RPF) algorithms
 Steiner Tree (ST) algorithm
 Shared tree algorithms

Multicast Routing
 
  

IPMC 1
Internet
IPMC 2
IPMC 3
IPMC 4
Multicast routing protocol
IGMP protocol
Subnetwork attached
to a router
  
Construction of Distribution Tree in
Case of Many Sources





For forwarding multicast packets across internet, we should use multicast
protocols
 Several algorithms may be used by the protocols
In case of many sources the multicast routing algorithms can handle the
distribution of the packets in three ways:
Primitive methods
– Flooding
– Spanning Tree
Source Based Tree
– Forward Shortest Path
– (Reverse Path Forwarding (RPF) algorithms – not detailed)
– Steiner Trees (ST)
Shared Tree
– Center Based Trees (CBT)
Primitive Methods

These do not take into account:
– the multicast traffic refers to different multicast groups
– which group member is sender and which is receiver


Such are the Flooding and the Spanning Tree algorithms
These are regarded as basic procedures
– They are used as building blocks of the more sophisticated algorithms
regarding construction of distribution tree
Flooding





When the router receives a multicast packet first it checks
whether it has already met with this
If this is the first occasion, the router forwards it to its all
interfaces, except that from which the packet arrived
If it has already met with that packet, the router will drop it out
In such a way all router will get the packet once at least
Its disadvantages:
– It generates high number multiplied packets
– It wastes network bandwidth
– Every router must maintain table of the lately arrived packets,
which requires a huge memory
Flooding



When a router receives a
packet, the router will
determine whether it’s the first
time it receives the packet. If
so, the packet will be
delivered to all interfaces
except the one on which it
arrived, otherwise the packet
will be discarded.
No routing tables needed
Inefficient use of bandwidth
The Operation of the Flooding
Source
Legend
router
IP connection
A
branch of
distribution tree
C
D
group-member
host
B
F
E
non group-member
host
multicast data
subnetwork
Spanning Tree



Only one active path connects
any two of routers
The multicast packets will not
loop and reach all routers
May not provide the most
efficient path between the source
subnetwork and group members
Spanning Tree
B
Legend
C
S=A
branch
E
F
D
H
router with an
attached subnet
G
I
connection
J
K
M
N
group member
host
L
P
O
non group-member
host
The Operation of the Spanning Tree
Algorithm
Source
Legend
router
IP connection
A
branch of the
distribution tree
C
D
group member host
B
non group memeber
F
E
multicast data
subnet
Multicast Routing
Algorithms—Characteristics
 Distribution
trees
– Source tree
Uses
more memory O(NS x NG) but you get optimal paths
from source to all receivers, minimizes delay
– Shared tree
Uses
less memory O(NG) but you may get suboptimal paths
from source to all receivers,
may introduce extra delay
Source Based Tree


Each source creates its own distribution tree
The advantages of such a kind of algorithms are
– the higher end-to-end power
» E.g., smaller delay
– sharing the traffic load coming from each source on
the network

Disadvantage is that each router must generate
large routing table, since one routing item is
needed for each source and each group
Forward Shortest Path

In case of link-state unicast routing
algorithms every router know the whole
network topology
– Thus they can calculate the shortest path
form the source to the receivers

This tree is different from the reverse
shortest path (later) if the links are nonsymmetrical
Reverse Path Forwarding

What is RPF?
–A router forwards a multicast datagram if received on the interface used to send
unicast datagrams to the source
Unicast
C
B
Receiver
A
Source
F
D
E
Multicast
Reverse Path Forwarding
 If
the RPF check succeeds, the datagram
is forwarded
 If
the RPF check fails, the datagram
is typically silently discarded
 When
a datagram is forwarded, it is sent out each interface in the outgoing
interface list
 Packet
is never forwarded back out the
RPF interface!
Shortest Path or Source
Distribution Tree
Source
Notation: (S, G)
S = Source
G = Group
A
B
C
Receiver 1
D
F
E
Receiver 2
The Reverse Path Forwarding (RPF)
Algorithm-Family


These forward packet on their output interfaces if and only if the
packet arrived on the interface, which is on the shortest path to
the source
The “reverse path” naming is originated from the fact that after
the multicast tree was built, the routers have to listen to the
reverse path to the multicast source
– If a packet arrive in an other interface, which is not in the shortest
path to the source, the packet will be dropped out by the router
Finding the Shortest Path




If a packet comes and another packet has already arrived on a
shorter way from the sender, then the new packet will be
dropped out
But if the new packet arrived in the shorter path, from this
point its path is the current shortest path
It is important, since the packet must carry the IP addresses of
the routers along the path, and in case of longer path the size of
the packet increases
This algorithm does not need any additional method to prevent
against the packet multiplication, e.g., automatic hop count
limiting mechanism, since the algorithm automatically limits
the path of the packets to the shortest path
The RPF Tree Rooted in the Router A
Source
Legend
router
A
IP connection
shortest path
C
D
group member host
B
non group member
host
F
E
subnet
The RPF Tree Rooted in the Router C
Legend
router
A
IP connection
C
D
B
shortest path
Source
F
E
group member host
non group member
host
subnet
The Different Reverse Path
Forwarding (RPF) Algorithms




Reverse Path Forwarding/Flooding/Broadcast (RPF)
(Sophisticated/Extended) Reverse Path Broadcast
(RPB)
Truncated Reverse Path Broadcast (TRPB)
Reverse Path Multicast (RPM)
Reverse Path
Forwarding/Flooding/Broadcast (RPF)
Source
Legend
router
IP connection
A
brach of tree
parent link
C
D
B
group member host
F
E
non group member
host
multicast data
subnet
RPF
A local router only accepts
packets from the ‘nearest’
source (parent), otherwise the
packets are discarded.
Accepted packets will be
forwarded to all interfaces
except the source
It does not take into account
multicast group membership
when building the distribution
tree, so packets may be
forwarded to non-membership
subnetwork
(Sophisticated/Extended) Reversed
Path Broadcast (RPB)
(S1, G1)
S1 Source
R2
R3
parent
link
child
link
G1
I1
I4
child
link
R5
Legend
G2
router
multicast data
G4
I2
G2
G1
I3
IP connection
R4
distribution tree
I5
G1
child
link
G2
G5
G1 group member
host
non group member
host
subnet
R6
G1
R8
R7
G2
G1
G3
G5
The RPB Tree
Source
Legend
router
IP connection
A
branch of the tree
(shortest path)
C
D
group member host
B
non group member
host
F
E
multicast data
subnet
Truncated Reverse Path Broadcast (TRPB)
(S1, G1)
S1 Source
R2
R3
parent
link
child
link
G1
I1
I4
child
link
R5
Legend
G2
router
multicast data
G4
I2
G2
G1
I3
IP connection
R4
distribution tree
I5
truncation
child
link
G1
G2
G5
member
of group G1
non group
member
subnet
R6
R8
R7
truncation
G1
G2
G1
G3
G5
Truncated Reverse Path Broadcasting
(TRPB)
It’s an enhancement of RPB
With the help of IGMP, multicast
routers determine the group
membership on each leaf
subnetwork, thus avoiding
forwarding packets to nonmembers
Eliminates unnecessary traffic on
leaf subnetworks , but does not
consider group memberships when
building the branches of the
distribution tree
Source,
G1
G3
G1
G2
Truncated
TRPB Based Multicast Delivery
Source
Legend
router
IP connection
A
branch of the tree
group member host
C
D
B
non group member
host
F
E
multicast data
subnet
Reverse Path Multicasting (RPM)

RPM creates a delivery tree that spans only
• Subnetworks with group members, and
• Routers along the shortest path to subnetworks with group members



First packet will be sent to all interfaces except the source. If none of the subnetworks
connected to the leaf router have group members, the leaf router may transmit a "prune"
message on its parent link informing the upstream router not to forward packets in this
group to the leaf
In RPM, ‘first packet’ still needs to be forwarded throughout the network.
Each router has to maintain state information for all groups. It will be impossible as the
number of groups and sources increases.
Reversed Path Multicast (RPM)
Legend
Source
router
IP connection
A
branch of the tree
truncated branch
C
D
group member host
B
non group member
host
F
E
multicast data
prune message
subnet
Building The Distribution Tree using RPM
Steiner Trees (ST)
Source
Legend
router
IP connection
A
branch of the tree
group member host
C
D
B
non group member
host
F
E
multicast data
subnet
Shared Tree




The all sources sends the packet to the same tree
The same tree distributes the all packets
This algorithm concentrates the traffic to the small set of the
network connections
This algorithm is not optimal if all sources are active in the same
time
– E.g., distributed interactive simulation application

This algorithm works well, when the source operates alternatively
– E.g., audio-conference


Its advantage is that it needs one item per group, only
Such algorithm is e.g., Center Based Trees
Center Based Trees (CBT)




If a host wants to join one group, it has to send a unicast “join request” message to the
core.
Compared to previous algorithms, CBT can use bandwidth and router resources more
efficiently
CBT may result in traffic concentration and bottlenecks near core routers since traffic
from all sources traverses the same set of links as it approaches the core
A single shared tree may create trees not as optimal as source-trees
Operation of the Center Based
Trees (CBT) Algorithm
Source
Legend
router
core router
A
IP connection
branch of the tree
C
D
group member host
B
non group member
F
E
multicast data
unicast data
subnet
Shared Distribution Tree
Source 1
Notation: (*, G)
* = All Sources
G = Group
Source 2
A
B
C
Receiver 1
D (Shared Root) F
E
Receiver 2
Center Based Multicast Distribution
Tree
Incoming multicast
packet to the group
Legend
router
core router
connection
CBT backbone
path of the
multicast packets
Comparison of the properties
related to the construction of the
distribution tree
Property
Taking into account the existence of
various multicast groups (different
distribution path for each group)
Different distribution paths for each
source
Building distribution tree (instead of
forwarding on the whole network
topology, in such a way avoiding the
duplicated packets)
Avoiding the flooding in the first step
Taking into account the group
membership of the host
Usage of multicast routing tables
Flooding
Span.
RPF RPB TRPB RPM
Trees
ST
CBT
No
No
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
No
No
No
Yes
No
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
No
Yes
No
No
No
No
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Comparison of the properties
related to the traffic on the tree
Property
Omitting the routers that are not
necessary for multicast delivery
Forwarding that packets, only, which
arrived in the shortest path
Forwarding the packet on the shortest
path, only
Using that paths, only, which have the
smallest hop-count or cost
Avoiding the whole concentration of
the traffic
Avoiding the concentration of the
traffic of each group
Flooding
Span.
trees
No
No
No
No
No
No
No
Yes
Yes
No
No
No
No
No
Yes
Yes
RPF RPB TRPB RPM
ST
CBT
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
No
No
No
No
No
No
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
No