Transcript From EGP to BGP - Politecnico di Torino

Multicast Communications
Gruppo Reti TLC
[email protected]
http://www.tlc.polito.it/
Index
•
•
•
•
•
Multicast advantages
Addressing in multicast
Multicast Routing Protocols
Multicast in the Internet
IGMP
1. Multicasting
• Unicast
– A single flow, from a source to a destination
– IP packets have unicast or broadcast address
• Broadcast
– A single flow, from a source to all nodes
• Multicast address hostid=all ones, e.g., 130.192.255.255
• Multicast
– A single flow, from a source to a group of
destinations
– IP packets have multicast address, in class D
Multicast vs. Multiple Unicast
Multiple Unicast:
Multicast:
Group address
1, 2 and 3
Packet
duplicated
1
1
Packet
duplicated
2
3
2
3
Multicast advantages
• Plus:
– Minor load on the source
• The source sends a single copy of each packet
– Better capacity utilization for the network
• A single copy of a packet can travel on a link
• Requirements:
– Group management
– Packet replication at network nodes
• From a single input port to a set of output ports
Multicast applications
• Push data
– Video, audio streams
• Resource discovery
– Multicast queries can be used to find
information if the destination is unknown, or
includes multiple nodes (e.g., RIP/OSPF)
• Multimedia collaboration
– Video conference, e-learning
Multicast in Internet
IP Multicast: RFC 1112
• Destination of messages are groups of hosts
– The sender can be part or not of the destinations
– A multicast address indentifies the destination group
• Special subset of addresses
–
–
–
–
No limit on the number of hosts in a group
Group members can be anywhere in the network
Members are unknown to the sender
Members can join or leave at any moment
IP Multicast
• Packets are not sent outside the group
– Multicast trees are used to route packets
– On a LAN, a single copy of each packet is sent
(LAN Multicast)
– Packet must reach only interested members =>
group management is mandatory
– The network should find the best multicast tree
Reliable Multicast
• What if you want reliable multicast:
– Retransmission management are complex, and often
it is easier to send n unicast flows….
– Ack-implosion: members can overflow the sender with
ACKs!
– The source does not know the members!
– “Crying baby”: the slowest receiver can limit the
performance of all members
• Heterogeneous Group size, link speed, members’
performance
– Applications may have different requirements (not all
need a la TCP reliability)
• How to solve this problem?
Addressing (RFC 1466)
1 2 3 4
Class A
0
16
netid=7 bit
Class B 1 0
Class C
8
1 1 0
24
hostid=24 bit
netid=14 bit
hostid=16 bit
netid= 21 bit
Classe D 1 1 1 0
Multicast addresses
Classe E 1 1 1 1
28 bit riservati
hostid=8 bit
3
Multicast: layer 2 and layer 3
Multicast bit
Destination
(6 bytes)
Source
(6 bytes)
Length
(2 bytes)
Data
(46-1500 bytes)
Pad
Frame Check Seq.
(4 bytes)
Ethernet adresses
• Source and destination addresses:
– 6 bytes ciascuno
• Two types
– Physical address: identifies a single linecard
– Multicast address: identifies a group of
linecards
– The first bit makes it clear
0 = physical address
1 = multicast address
Multicast addressing in IP
• Class D address
28 bits
1 1 1 0
Multicast group
From 224.0.0.0 up to 239.255.255.255
host group: is the set of group members
multicast source: the sender in a host group
Only UDP at layer 4 is supported
Mapping: Ethernet to IP
• Ethernet: 48-bit long addresses
• A subset of addresses are multicast addresses
– from 01.00.5e.00.00.00 to 01.00.5e.7f.ff.ff
– 23 bit to identify 2^23 multicast groups
• IP has 28 bit to identify a multicast group
• Only the least-significant 23 bits of the IP
address can be mapped to the 23 bits of the
ethernet address
• Conflicts?
Multicast routing protocols
•
•
•
•
•
•
Flooding
Shared Spanning Tree
Source-Based Spanning Trees
Reverse Path Forwarding (RPF)
Truncated Reverse Path Broadcast (TRPB)
Reverse Path Multicasting (RPM)
Flooding
• Same algorithm that can be used for unicast
• A router forwards a packet to all ports, but the
one the it arrived from
• Router have to track packet sequence
numbers to identify duplicated
– Packets with an old sequence number are
discarded
Flooding
A sends to group G: {B,C,D}
B
A
E
C
D
Flooding
B
A
E
C
D
Plus and minus
• Advantages:
– Simple to implement
– No need to manage groups
• Everybody gets everything
• Drawbacks:
– Routers have to store packet sequence number.
Can be humongous
– Several copies of the same packets are received
– Packets go to everyone, even if not interested
Shared Spanning Tree
• Build a spanning tree
– A tree that spans through all the network
– May be inside into a single Autonomous
System
• Forwarding:
– A router forwards a multicast packet to all
ports in the spanning tree, but the one it was
received from
– No loops: no duplicate packets
Shared Spanning Tree
A sends to group G: {B,C,D}
B
A
E
C
D
Shared Spanning Tree
B
A
E
C
D
Spanning Tree Path
Shared Spanning Tree
B
A
E
C
D
Spanning Tree Path
Plus and minus
• Advantages:
– Traffic goes on a subset of links
– No packet duplicate
• Drawbacks:
– The network has to manage the spanning tree
– Shared spanning tree: everybody receives
everything even if not interested
– Link of the spanning tree may be congested
Source Based Trees
• Setup a single spanning tree rooted at
each source
• Each source-based spanning tree is
explicitily built using the shortest paths
from the source to each destination
Source Based Trees
All edges has
the same costs
B
A
E
C
D
Source Based Trees
B
A
E
C
D
Spanning Tree Path for (A, G)
Spanning Tree Path for (C, G)
etc...
Source Based Trees
A sends to group G: {B,C,D}
B
A
E
C
D
Spanning Tree Path for (A, G)
Spanning Tree Path for (C, G)
etc...
Plus and minus
• Advantages:
– Packets are routed using minimum cost paths
– No duplicate packet
• Drawbacks:
– A single Source Based Tree is build for each sender
– Multicast routing tables grow large (one entry for
each source)
– Everybody receive everything
Reverse Path Forwarding
• Also known as Reverse Path Broadcast
• RPF is a simple algorithm to setup sourcebased spanning tree
– It uses the same unicast routing tables!
• Forwarding:
– When a packet is received,
• If the packet is received from a port that would be used to
forward packets to the source, forwad the packet to all the
ports (but the one you received it from)
• If the packets arrives from any other port, drop it
Reverse Path Forwarding
All links have
the same cost
B
A
E
C
D
Reverse Path Forwarding
A sends to group G: {B,C,D}
Will be discarded
B
Will be discarded
A
E
C
D
Plus and minus
• Advantages:
– Efficient and simple to be implemented
– No need to store packet sequence numbers
– Use the same information of the unicast routing
tables
• Disadvantages:
– Some duplicates packets are generated
– Everybody keeps receiving everything, even if not
interested
TRPB (Truncated RPB)
• Extension of RPF
• Signaling is used to identify interested nodes
– Internet Group Management Protocol (IGMP)
• If the router does not get any messages from
interested nodes, it drops forwarding packet on
that port
TRPB (Truncated RPB)
B
A
E
C
D
TRPB (Truncated RPB)
A sends to group G: {B,C,D}
All links have
the same costs
Will be discarder
B
Will be discarded
A
E
C
D
The router knows that E is not interested
and stops forwarding packets
Plus and minus
• Advantages:
– Same as RPB, but only interested nodes get
the packets
• Disadvantages:
– Packets get to all routers in the network
Reverse Path Multicast (RPM)
• Generalization of the idea of dropping links
going to uninterested hosts
• If a multicast packet arrives to a router that has
no interested member, it sends a “prune”
message to the sending router (explicit leave)
– Prune messages allow the parent router to know if
there is no one interested in the multicast packets
Reverse Path Multicast
All links have
the same costs
B
A
E
C
D
Reverse Path Multicast
A sends to group G: {B,C,D}
Will be discarded
B
Will be discarded
A
E
C
D
The router knows that E is not interested
and stops forwarding packets
Reverse Path Multicast
Will be discarded
B
Will be discarded
A
Prune messages
E
C
D
The router knows that E is not interested
and stops forwarding packets
Reverse Path Multicast
Will be discarded
B
These branches are
chopped
A
E
C
D
Reverse Path Multicast
• Pruned branches will automatically “grow”
again after a timeout
– This allows new members to be reached again by
the information
• Router may use explicit signaling messages
(graft messages) to request parents to start
forwarding packets to it again (explicit join)
– Graft messages speed-up the multicast group join
procedure
Plus and Minus
• Advantages:
– Same as TRPB
– Plus only interested routers gets the packets
• Drawbacks:
– Complexity grows: prune (and graft)
messages
Multicast in Internet
• Multicast protocols
– Distance Vector Multicast Routing Protocol
(DVMRP – RFC 1075)
– Multicast OSPF (MOSPF – RFC 1584)
– Core Based Trees (CBT – RFC 2201)
– Protocol Independent Multicast (PIM – RFC
2362, RFC 3873)