Transcript Pragmatic General Multicast

TCP/IP: Upper Layer Protocols
Fall 2002
Pragmatic General
Multicast
RFC 3208
By: Sachin Kamboj
Outline
 Introduction to multicasting


Multicast vs. multiple unicast
Pros of multicasting
 Pragmatic general multicast







Services offered
Example applications
Requirements for achieving reliability
Components of a PGM network
Operation
PGM–PDU types
PGM–PDU formats
Introduction to Multicasting
 Communication can be of three types: unicast,
broadcast and multicast.

Unicast:
 One to one communication between hosts.
 The destination address is the address of the unique
host which is the intended recipient of the message.
Introduction to Multicasting

Broadcast:
 One to all communication between hosts on a given
network.
 The destination address is the address of the network.
Network

11111111
Broadcast to all hosts on the Internet is not possible.
Internet
Introduction to Multicasting

Multicast:
 One to many (but not all) communication between hosts.
 A single packet is transmitted to a group of recipients.
 The destination address is the address of the group.
Hosts which are part of the group
Multicast vs. Multiple Unicast
Multicast
Multiple Unicast
Slide copied from pg. 407, Forouzan: TCP/IP Protocol Suite, 2nd edition
Multicast vs. Multiple Unicast
Multicasting:
Multiple Unicasting:
 The source transmits a
 The source transmits
single packet which is
duplicated by the routers.
 Destination address is the
same for all the duplicates.
 Only one copy of a packet
travels between any two
routers.
multiple packets.
 Each packet is intended for
a particular destination.
 Each packet has a different
unicast destination address.
 Multiple copies may travel
between any two routers.
Pros of Multicasting
•
Bandwidth:
0.8
Graph from Pg. 8, Williamson:
Developing IP Multicast
Networks, Vol.1
0.7
0.6
0.5
Bandwidth 0.4
Mbps
Multiple Unicast
Multicast
0.3
0.2
0.1
0
1
20
40
60
80
100
No. of Clients
•
Server Load:
• Server (source) only sends one copy of the packet
•
Network Loading:
• Network has fewer packets to transfer
Pragmatic General Multicast
 Services offered:

Multicast data packet (A-PDU) delivery from multiple
sources to multiple receivers.

Reliability:


Data integrity (uses checksums)


No-loss OR detectable loss
 Guarantees that a receiver in a group either receives
all data packets (A-PDUs) or is able to detect
unrecoverable data packet loss.
No-duplicate

Ordered or unordered
PGM has no notion of group membership.
 Uses the services provided by IP Multicast:
 Unreliable (best effort) packet delivery.
Services Provided by IP Multicast
 Offers a best-effort datagram (T-PDU) delivery service from a
source to a group of receivers.
 Handles the routing of IP-PDUs so that all the members of a
group receive a copy of the IP-PDU.
 Uses IGMP to provide group membership.
Hosts which are part of the group
Example Applications
 Financial services
 Transmitting news, stock quotes, financial indices and
other documents to multiple receivers.
 E-Learning
 Streaming audio and video to many students at once.
 Interactive communication between classmates
 Interactive TV
 Wireless Entertainment
 Delivery of data and content to hundreds of millions of
cell phones.
 Bulk Data transfer
Requirements for Achieving Reliability
 To achieve reliability ACKs are required.
 The source solicits confirmation from the receivers.

Acknowledgements can be of two types:


Positive acknowledgements:
In the Case of Loss
Negative acknowledgements:

T
I
M
E
O
U
T



Used by receivers
to indicate
In the Case
of Loss the non-receipt of data.
How do the receivers
know that some data that was
ACK
sent was lost?
Loss can be detected since subsequent packets after
the loss arrive out of order.
What type of acknowledgement should be used?


Sender
No fixed answer: Depends on the application.
Certain criteria can be used for deciding on the type of
acknowledgement.
Receiver
Positive vs. Negative Acknowledgements
Positive ACKs:
Negative ACKs:
 Frequency is a function of
 Frequency is a function of
the number of packets
transmitted.
 Primarily determine transmit
buffer management.
the reliability of the N/W.
 Primarily determine repairs
and reliability.
 For Multicast Protocols:
 The “burden” of positive acknowledgements can
overwhelm the source.
 Positive ACK based reliable multicast protocols do not
scale well!!
 PGM uses negative acknowledgements (NAKs).
Problems with NAKs in Multicasting
 Source
sends a single
copy
of the
first a
packet.
All the receivers
in the
group
send
NAK to






the source
Packet
Gets lost/corrupted
at thethe
firstnumber
link.
The Number
of NAKs equals
of receivers in the group
Source
the of
next
packet
in thenetwork
sequence.
A largesends
number
NAKs
cause
congestion
Packet reaches all the receivers in the group.
This condition is known as NAK Implosion
 The receivers detect a lost packet since a different seq. no was expected
Components of a PGM Network
 Source:
 Transport Layer originator of Data Packets (A-PDU).
 Receiver:

Transport Layer consumers of Data Packets (A-PDU).
 Network Elements:
 PGM entities present in the intervening network

Unlike other transport layer protocols which only deal
with end-to-end (machine-to-machine) communication,
PGM requires PGM compatible routers.
PGM in Network Elements
 Traditional transport-layer protocols deal with end to end
communication.

The transport layer is NOT present in intermediate routers.
Transport
Network
Data-Link
Physical
Network
Data-Link
Physical
Source
Network
Data-Link
Physical
Routers
Transport
Network
Data-Link
Physical
Receiver
 In PGM, the routers (known as network elements) have to
have PGM code in the transport layer.
Transport
Network
Data-Link
Physical
Source
Transport
Network
Data-Link
Physical
Transport
Network
Data-Link
Physical
Network Elements
Transport
Network
Data-Link
Physical
Receiver
Operation
 Normal Data Transfer (i.e. without loss)
PGM Network
Element


Non-PGM
Router
Packets are multicast to the group.
No reverse traffic to the source if the transmission was
successful
Operation
 Source Path Messages (SPMs)







If theprocess
The
router
data path
establishes
duplicates
is repeated
changes,
the
a by
path
subsequent
SPM.
each
for the
router.
particular
SPMs update
source
thebypath
They
SPMs
establish
are
source
by
path
the source
state
inatPGM
frequent
network
intervals
elements.
in
noting
as
the multicast
Path
NLA
(Network
Layer
Address)
in
the
SPM.
Theshown.
router
receivers
then
simply
replaces
notethe
thepath
address
NLA
of
in each
the first
SPM
upstream
with
the
exactly
the
same
way
that
data
packets
are
multicast.
They
provoke
prompt
detection
ofthe
missing
packets
 The
Path
always
contains
address
of the (A-PDUs)
nearest
address
network
Hence
the
element.
of network
itsNLA
own
outgoing
elements
interface.
and
receivers
always
know
the
in
A
SPM
the
absence
arrives
at
of the
data
first
to transmit.
router.
upstream
network
element
or
source.element/source.
address
of SPM
the
next
upstream
network
Finally
the
is transmitted
downstream.
Operation
 Case 1: A single packet loss









Receiver
NE
forwards
unicasts
the
retransmitted
a NAK
the
last-hop
(RDATA)
PGM
Network
only
those
Element
NEs
Upstream
NE
unicasts
the
NAK
to the
source
and
multicasts
a
Packet
with
Sequence
no to
(i)
is data
multicast
to
theto
group.
(NE)group
and
along
the exact that
reverse
did not
path
receive
from the
thesource.
original data.
NCF
to
themembers
downstream
Network
Elements
Packet with Sequence no. (i + 1) is now multicast.
NE (+ve)
This
is achieved
acknowledges
by multicasting
the NAK
RDATA
by multicasting
packets
aNCF
NCF
ontopacket.
the
Source,
on
receiving
a NAK,
immediately
sends aonly
the NE
Receiver detects loss of packet with Sequence No. (i).
interfaces
on
NAK
was
NE alsothe
forwards
thea NAK
to
thereceived.
upstream
PGM NE.
Finally
lostwhich
packet
is retransmitted
(multicast)
to the group.
Operation
 Case 2: Multiple packet loss









Receivers
NE
forwards
unicast
the
retransmitted
NAKs
the
last-hop
(RDATA)
PGM
Network
only
those
Elements
NEs
Upstream
NE
unicasts
the
NAK
to the
source
and
multicasts
a
Packet
with
Sequence
noto(i)
is data
multicast
to theto
group.
(NE)group
and
along
the exact that
reverse
did not
path
receive
from the
thesource.
original data.
NCF
to
themembers
downstream
Network
Elements
Packet with Sequence no. (i + 1) is now multicast.
NE (+ve)
This
is achieved
acknowledges
by multicasting
the NAKs
RDATA
by multicasting
packets
NCF
onto
packets.
the
Source,
on
receiving
a NAK,
immediately
sends aonly
NCF
the NE
Receivers detect loss of packet with Sequence No. (i).
interfaces
on
a NAK
was to
received.
NE alsothe
forwards
a single
NAK
the upstream
NE.
Finally
lostwhich
packet
is retransmitted
(multicast)PGM
to the
group.
PGM Packet Types
 PGM defines four basic packet types:
 Packets that travel downstream (from the source to the
receivers)




SPM
DATA
NCF
Packets that travel upstream (from the receivers to the host)

NAK
 SPMs have two functions:
 They establish source path state PGM network elements
 They provoke prompt detection of missing packets in the
absence of data to transmit
 Data packets carry ODATA (original data) and RDATA
(repair data)
 NAKs are transmitted by receivers to request repairs.
 NCFs are used to acknowledge the receipt of NAKs
PGM Packet Formats
 Source Path Messages (SPMs)


Sent by a source to establish source path state in network
elements and to provide transmit window state to receivers.
network header source
address
of anofSPM
is the
The network-header
destination
address
an SPM
is a
unicast NLA
of the
entity that originates the SPM.
multicast
group
address.
Source Port
Type
Destination Port
Options
Checksum
Global Source ID
Global Source ID
TSDU Length
SPM Sequence Number
Trailing Edge Sequence Number
Leading Edge Sequence Number
NLA AFI
Reserved
Path NLA
Option Extension when present …
PGM Packet Formats
 Data packets
 Carry application data from a source to receivers.
 Network header source and destination addresses are
the same as that for SPMs
Source Port
Type
Destination Port
Options
Checksum
Global Source ID
Global Source ID
TSDU Length
Data Packet Sequence Number
Trailing Edge Sequence Number
Option Extension when present …
Data……
PGM Packet Formats
 Negative acknowledgements and confirmations
Source Port
Type
Destination Port
Options
Checksum
Global Source ID
Global Source ID
TSDU Length
Requested Sequence Number
NLA AFI
Reserved
Source NLA
NLA AFI
Reserved
Multicast Group NLA
Option Extension when present …
References
 T. Speakman, J. Crowcroft, J. Gemmell, D. Farinacci,
S. Lin, D. Leshchiner, M. Luby, T. Montgomery, L.
Rizzo, A. Tweedly, N. Bhaskar, R. Edmonstone, R.
Sumanasekera, L. Vicisano:
RFC 3208: PGM: Reliable Transport Protocol
Specification,
(ftp://ftp.isi.edu/in-notes/rfc3208.txt)
 Derek Chen-Becker and Manoj Singla: “Implementation
and Evaluation of a Pragmatic General Multicast
(Implementation)”,
(http://students.cec.wustl.edu/~dwb2/work/pgm/)
Questions?