One document matched: draft-ooms-cl-multicast-02.txt
Differences from draft-ooms-cl-multicast-01.txt
INTERNET DRAFT D. Ooms
<draft-ooms-cl-multicast-02.txt> Alcatel
W. Livens
Colt Telecom
O. Paridaens
ULB
April, 2000
Expires October, 2000
Connectionless Multicast
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Abstract
This draft proposes a new mechanism for multipoint-to-multipoint
(mp2mp) communication in IP networks, namely Connectionless Multicast
(CLM). Instead of a group address, a list of member addresses is
encoded in the data packets.
The traditional Host Group Model [DEER] for IP multicast requires a
globally unique address for each session. To support this model,
multicast routing protocols create state per group in the routers.
Like any connection oriented protocol, it suffers from scalability
problems in backbone networks where the number of groups to be
maintained can be huge. CLM does not have this problem, and
additionally has some other advantages. Its limitation lies in the
Ooms, et al. Expires October 2000 [Page 1]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
number of members per multicast session, not in the number of
sessions. CLM will not replace the traditional multicast model. CLM
offers an alternative for mp2mp communication in the cases that
traditional multicast becomes expensive.
The pros and cons of CLM are described and suggestions are made to
alleviate the disadvantages. Furthermore different modes of
operation are described: an end-to-end mode in close conjunction with
SIP (Session Initiation Protocol [HAND]), as well as an interworking
mode with PIM-SM and Simple Multicast. Both IPv4 and IPv6 are
considered.
Table of Contents
1. Introduction
2. The cost of the traditional multicast model
3. Description
4. Working modes
4.1 CLM as an end-to-end multicast routing solution
4.2. CLM as an interdomain multicast routing protocol
4.2.1. Simple Multicast
4.2.2. PIM-SM
4.3. Summary
5. Premature Cloning
6. Caching
6.1. Principle
6.2. Caching and Unicast Reroutes
6.2.1. Intra-node
6.2.2. Inter-node
7. Address list encoding
8. IP Protocol extensions
8.1. IPv4
8.2. IPv4 Alternative
8.3. IPv6
9. Gradual Deployment
10. Security Considerations
11. Acknowledgements
A Hierarchical Address List Encoding
A.1. Compound addresses
A.2. Processing of a compound address
A.3. Compound address encoding example
Table of Abbreviations
CLM ConnectionLess Multicast
HALE Hierarchical Address List Encoding
Ooms, et al. Expires October 2000 [Page 2]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
IRC Internet Relay Chat
mp2mp multipoint-to-multipoint
PIM-SM Protocol Independent Multicast Sparse Mode
RUN Receiver Update Notification
SM Simple Multicast
Changes
- added picture of 'cost of multicast' (2)
- small changes to advantages section (3)
- small changes to disadvantages section (3)
- RUN moved from option to destination address field (6.1)
- added section on caching and unicast reroutes (6.2)
- new option format: introduction of bitmap, P-bit, A-bit and U-bit (8.1)
- added seperate section on gradual deployment (9)
- added paragraph on IPsec compatibility (10)
1. Introduction
The main goal of multicast is to avoid duplicate information flowing
over the same link. By using traditional multicast instead of
unicast, bandwidth consumption decreases while the state and
signalling per session increases. Apart from these two dimensions,
we identify a third one: the header processing per packet. This
three dimensional space is depicted in Figure 1.
Ooms, et al. Expires October 2000 [Page 3]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
state&signaling
per session
in router
^
|
|
....
B | ....
. | ....
. | ....
. | ....
. +------------------..---> processing
. / .... C per packet
. / ..... in router
. / .....
. / .....
./ .....
/A....
/
/
link bandwidth
Figure 1
A first method to deliver identical information from a source to n
destinations is to unicast the information n times (A in Figure 1).
A second method, the traditional multicast model (B in Figure 1)
sends the information only once to a multicast address. In the third
alternative (CLM), which is the subject of this draft, the
information is sent only once, but the packet contains a list of
destinations (point C). For a detailed description of CLM we refer
to section 3.
The three points A, B and C define a plane (indicated with dots in
Figure 1): a plane of conservation of misery. All three approaches
have disadvantages. The link bandwidth is a scarce resource,
especially in access networks. State&signaling/session encounters
limitations when the number of sessions becomes large and an
increased processing/packet is cumbersome for high link speeds.
Traditional multicast can move a little bit along the line A-B by
switching between source and shared trees. However, this flexibility
is very limited. Thus state&signaling/session is, amongst others
(see section 2) a cost for the traditional multicast model.
Also pure CLM encounters limitations (processing/packet), but the
nice and differentiating feature of CLM is that it gives the router
the choice to make its own tradeoffs. CLM has three mechanisms built
Ooms, et al. Expires October 2000 [Page 4]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
in (caching, premature cloning and optimized address list encoding)
that allows the router to move in this plane of conservation of
misery, according to its own needs, which could be e.g. its location
in the network. Caching allows a router to move from C to B, while
premature cloning allows a shift from C to A.
It is often argumented that it is not worthwhile to use multicast for
mp2mp communication with a limited number of members, and use unicast
instead. This is definitely untrue as following example illustrates:
assume n residential users set up a video conference. For e.g. xDSL,
GPRS or cable modem access technologies a host has no problem
receiving n-1 basic 100kb/s video flows, but the host is not able to
send its own video data n-1 times at this rate. Because of the
limited and often asymmetric access capacity, some type of multicast
is mandatory.
In CLM, a host sends a packet with the addresses of the other n-1
members. The first router beyond the access link can probably
process the packets in pure CLM mode since the link speed is
relatively small here. Further in the network, where link speeds
increase, routers can decide to maintain a cache entry for this
session. Once arrived in a backbone network, where bandwidth is
plentiful, the CLM packets could be prematurely cloned into multiple
unicast packets to avoid the heavy header processing in the core
routers.
A simple but important application of CLM lies in bridging the access
link for mp2mp communication. The host sends the CLM packet with the
list of unicast addresses and the first router prematurely clones the
CLM packet to multiple normal unicast packets.
We believe that the flexibility of CLM to adapt to specific network
conditions makes CLM an excellent multicast forwarding mechanism in
the heterogeneous internetworks, as we currently know them.
2. The cost of the traditional multicast model
The characteristics of the traditional IP multicast model are
determined by its two components: the Host Group model [DEER] and a
Multicast Routing Protocol. Both components add to the difference in
nature between unicast and multicast.
In the Host Group model, a group of hosts is identified by a
multicast group address, which is used both for subscriptions and
forwarding. This model has two main costs:
- Multicast address allocation: The creator of a multicast group must
Ooms, et al. Expires October 2000 [Page 5]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
allocate a multicast address which is unique in its scope (scope will
often be global). This issue is being addressed by the Malloc
working group, which is proposing a set of Multicast Address
Allocation Servers (MAAS) and three protocols (MASC, AAP, MADCAP).
- Destination unawareness: When a multicast packet arrives in a
router, the router can determine the next hops for the packet, but
knows nothing about the ultimate destinations of the packet, nor
about how many times the packet will be duplicated later on in the
network. This complicates the security, accounting and policy
functions.
In addition to the Host Group model, a routing algorithm is required
to maintain the member state and the delivery tree. This can be done
using a (truncated) broadcast algorithm or a multicast algorithm
[DEER]. Since the former consumes too much bandwidth by
unnecessarily forwarding packets to some routers, only the multicast
algorithms are considered. These multicast routing protocols have
the following costs:
- Connection state: The multicast routing protocols exchange messages
that create state for each multicast group or (source, group) in all
the routers that are part of the point-to-multipoint tree. This can
be viewed as a kind of signaling that creates multicast connection
state, possibly yielding huge multicast forwarding tables. The name
Connectionless Multicast refers to the elimination of this connection
state.
- Source advertisement mechanism: Multicast routing protocols
provide a mechanism by which members get 'connected' to the sources
for a certain group without knowing the sources themselves. In
sparse-mode protocols (CBT, PIM-SM), this is achieved by having a
core node, which needs to be advertised in the complete domain. On
the other hand, in dense-mode protocols (PIM-DM, DVMRP) this is
achieved by a "flood and prune" mechanism. Both approaches raise
additional scalability issues.
The cost of multicast address allocation, destination unawareness and
the above scalability issues lead to a search for other multicast
schemes. Recently, several changes to the Host Group Model were
proposed to address these drawbacks:
- Simple Multicast [PERL] uses the couple of core and multicast
addresses as the group identifier. In this way core advertisement
and multicast address allocation can be avoided.
- In Express [HOLB], a multicast channel is identified by source and
multicast addresses. Thus address allocation is not required and
Ooms, et al. Expires October 2000 [Page 6]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
since there is no core, there is no core advertisement either.
Creating a multicast session with multiple changing sources is
implemented by using a session manager and a set of multicast
channels.
- In Source-Specific Multicast [HOLB2] a host joins a specific
source. This approach avoids multicast address allocation as well as
the need for an interdomain routing protocol.
Note that all three approaches still create state&signaling per
multicast session in each on-tree node. Figure 2 depicts the above
costs as a function of the number of members in the group. All the
costs have a hyperbolic behavior.
cost of the current
multicast model
per member
^
| costly| OK
| <-----|----->
| . |
| .. |
| ..|..
| | .........
| | ........
+--------------------------->
| number of members
v
alternative=clm
Figure 2
The current multicast model becomes expensive for its members if the
groups are small. Small groups are typical for conferencing, gaming
and collaborative applications. This is a class of applications for
which CLM wants to offer an alternative.
3. Description
In the Host Group Model the packet carries a multicast address as a
logical identifier of all group members. In Connectionless Multicast
(CLM) the packet carries all the IP addresses of the multicast
session members (in the context of CLM the term 'multicast session'
will be used instead of 'multicast group' to avoid the strong
association of multicast group with multicast group address in
traditional IP multicast).
In each router the next hop for each destination is determined based
Ooms, et al. Expires October 2000 [Page 7]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
on the unicast routing table. In this way for every distinct next
hop the new list of destinations is determined. When there is only
one destination left the CLM packet could turn into a normal unicast
packet, which can be unicasted along the remainder of the route.
Although not restricted to this type of multicast session, the most
beneficial application of CLM is for sessions with a limited number
of members (super-sparse sessions).
For sessions with a large number of members (broadcast applications),
CLM can be used as an interdomain multicast routing mechanism between
a limited number of domains which run either PIM-SM or Simple
Multicast.
So, CLM will not replace the traditional multicast model, but offers
an alternative for mp2mp communication where traditional multicast
becomes expensive.
In practice, traditional multicast routing protocols impose
limitations on the number of groups and the size of the network in
which they are deployed. For CLM these limitations do not exist.
CLM has the following advantages:
1) No multicast address allocation required.
2) Routers do not have to maintain state per session (or per source-
session).
3) No need for multicast routing protocols (nor intra- nor
interdomain). CLM completely relies on the unicast routing table.
4) No core node, so no single point of failure.
5) No symmetrical paths required. Traditional multicast routing
protocols create non-shortest-path trees if the paths are not
symmetrical (symmetrical = the shortest path from A to B is the same
as the shortest path from B to A). It is expected that more and more
paths in the Internet will be asymmetrical due to traffic engineering
and more policy routing, thus deviating more and more from optimal
network usage.
4) Automatic reaction to unicast reroutes. CLM will react
immediately to unicast route changes. In traditional multicast
routing protocols a communication between the unicast and the
multicast routing protocol needs to be established. In many
implementations this is on a polling basis, yielding a slower
reaction to e.g. link failures.
Ooms, et al. Expires October 2000 [Page 8]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
5) Easy security and accounting. In contrast with the Host Group
Model, in CLM all the sources know the members of the multicast
session, which gives the sources the means to e.g. reject certain
members or count the traffic going to certain members quite easily.
Not only a source, but also a border router is able to determine how
many times a packet will be duplicated in its domain. It becomes
also more easy to restrict the number of senders or the bandwidth per
sender.
6) Heterogeneous receivers. Besides the list of destinations, the
packet can also contain a list of DiffServ bytes. While traditional
multicast protocols have to create separate groups for each service
class, CLM incorporates the possibility of having receivers with
different service requirements within one multicast session.
7) CLM packets can make use of traffic engineered unicast paths.
8) More simple implementation of reliable protocols on top of CLM,
because CLM can easily address a subset of the original list of
destinations to do a retransmission.
9) Easy transition phase (section 9).
However, CLM has a number of disadvantages as well:
1) Overhead. Each packet contains all remaining destinations, but
the total amount of data is still much less than for unicast (payload
is only sent once). A method to compress the list of destination
addresses might be useful (section 7).
2) More complex header processing. Each destination in the packet
needs a routing table lookup. So a CLM packet with n destinations
requires the same number of routing table lookups as n unicast
headers. Additionally, a different header has to be constructed per
next hop. Remark however that:
a) Since CLM will typically be used for super-sparse sessions, there
will be a limited number of branching points, compared to non-
branching points. Only in a branching point new headers need to be
constructed.
b) The header construction is a very simple operation: overwriting a
1-byte bitmap.
c) Among the non-branching points, a lot of them will contain only
one destination. In these cases normal unicast forwarding can be
applied.
Ooms, et al. Expires October 2000 [Page 9]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
d) By using a hierarchical encoding of the list of destinations in
combination with the aggregation in the forwarding tables the
forwarding can be accelerated (section 7).
e) When the packet enters a region of the network where link
bandwidth is not an issue anymore, the packet can be prematurely
cloned. This avoids more complex processing downstream (section 5).
f) The forwarding can also be enhanced by a caching mechanism
(section 6). This caching allows the same forwarding behavior as
current multicast.
3) Multi-access networks. Currently Ethernet does not support CLM.
This means that one has to send a packet for each next-hop in a
multi-access network.
4) CLM only works with a limited number of receivers.
4. Working modes
The preceding sections mainly focused on the data plane, this section
will focus on the control plane of CLM. CLM is mainly applicable to
super-sparse multicast sessions. Besides this, we also describe how
CLM can be used as an interdomain multicast routing protocol,
connecting e.g. Simple Multicast or PIM-SM domains.
4.1 CLM as an end-to-end multicast routing solution
If CLM is used end-to-end, it is especially useful for super-sparse
sessions, e.g. conferencing, multi-party gaming, etc...
In the current Internet three approaches to establish multipoint-to-
multipoint sessions can be identified:
- Internet Relay Chat (IRC) [OIKA]. In this approach a set of
servers keeps track of the created channels and the members of these
channels. The servers are also responsible for emulating the mp2mp
data delivery, which relies on unicast forwarding.
- Current IP Multicast Group Establishment (IGMP, Multicast Protocol,
Multicast Address Allocation). In this approach the creation of the
group, mainly the multicast address allocation, is the responsibility
of a set of servers, while the member state is distributed over the
network. The data delivery is distributed over the network and
relies on multicast forwarding.
- Session Initiation Protocol (SIP) [HAND]. A host takes the
Ooms, et al. Expires October 2000 [Page 10]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
initiative to set up a session. With the assistance of a SIP server
a session is created. The session state is kept in the hosts. Data
delivery can be achieved by several mechanisms: meshed unicast,
bridged or multicast. Note that for the establishment of multicast
delivery, a multicast protocol and communication with Multicast
Address Allocation Servers (MAAS) are still required.
Both CLM and SIP address super-sparse mp2mp sessions. It turns out
that CLM (a very flexible data plane mechanism) can be easily
integrated with SIP (a very flexible control plane protocol). When
an application decides to use CLM forwarding it does not affect its
interface to the SIP agent: it can use the same SIP messages as it
would use when it opted for meshed unicast forwarding.
4.2. CLM as an interdomain multicast routing protocol
4.2.1. Simple Multicast
Simple Multicast provides a tunnel mechanism. This tunnel is used
either to cross non Simple Multicast domains or to limit the
multicast forwarding state in parts of the network. When the tunnel
is used for the latter purpose, the bandwidth saving of multicast is
lost in these parts of the network, i.e. parallel tunnels for the
same group can exist on a specific link (Figure 3). Assume ERi are
Simple Multicast Exit Routers and BRi are Backbone Routers in which
one wants to avoid multicast forwarding state. S is a sender to the
group and Ri are receivers. For this topology Simple Multicast will
construct a first tunnel from ER1 to ER2 and a second tunnel from ER1
to ER3, yielding duplicate traffic on the link ER1-BR1.
+--------BR2--------ER2------R1
|
|
S------ER1------BR1-------BR3--------ER3------R2
Figure 3
If the backbone routers are CLM routers the duplicate traffic can be
avoided without building multicast state. The interworking is easy
since ER1 knows the endpoints of both tunnels: it can send the
multicast packet in CLM mode by putting ER2 and ER3 as destinations
in the packet, thereby creating a point-to-multipoint tunnel.
4.2.2. PIM-SM
Ooms, et al. Expires October 2000 [Page 11]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
With MSDP [FARI] the Rendezvous Points (RPs) of different PIM-SM
domains discover which RPs have sources for a certain group in their
domain. Similarly, a Multicast Receiver Distribution Protocol (MRDP)
can be created. MRDP allows RPs to discover which RPs have receivers
for a certain group in their domain. If MRDP is running and an RP
has a source for a group, it can send the data in a CLM mode to the
RPs which have receivers for this group.
4.3. Summary
The working modes of CLM and other mp2mp communication mechanisms are
summarized in Table 1.
| control plane | data plane
+ -----------+-------------+---------------
| session | member | forwarding
| creation | state |
----------+------------+-------------+---------------
IRC | servers | servers | servers (UC)
multicast | servers | network | network (MC)
SIP/CLM |host/server | hosts | network (CLM/UC)
SM/CLM | / |exit router | network (CLM/UC)
MRDP/CLM | / | RP | network (CLM/UC)
Table 1
5. Premature Cloning
A router can decide to prematurely clone a CLM packet, i.e. duplicate
a CLM packet before its actual branching point and reduce it to a
normal unicast packet. This early cloning facilitates a less complex
forwarding in all downstream routers.
An operator's border router can e.g. prematurely clone the CLM
packets that would normally branch in the operator's domain. Or an
edge router can prematurely clone CLM packets to multiple unicast
packets (when CLM was only used to bridge the access link).
The transformation of a CLM packet to a normal unicast packet
(Premature Cloning or a CLM packet with only one destination left)
requires a recalculation of the transport layer checksum (UDP and TCP
checksums are calculated over the pseudo header which includes the
destination address field). Note that this does not require a
complete recalculation of the checksum, only a delta calculation:
Ooms, et al. Expires October 2000 [Page 12]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
Checksum' = ~ (~Checksum + ~daH + ~daL + daH'+ daL')
In which "'" indicates the new values, "da" the destaination address
and "H" and "L" respectively the higher and lower 16 bit.
6. Caching
The increased forwarding complexity is the main challenge for CLM:
packet headers have to be processed at wirespeed. It was already
mentioned that in major parts of the tree the normal unicast
forwarding can be applied (from the moment there is only one
destination address left in the packet).
A method for further enhancing the forwarding is building a cache for
the highest bandwidth sources.
6.1. Principle
If the source supports caching it will put a number in the
destination address field of the IP header: the Receiver Update
Notification (RUN). Each time the set of destinations changes the
source will indicate this to the downstream routers by changing the
RUN. The cache will contain entries for (S, RUN). If the router
receives a high bandwidth flow with a new (S, RUN) it can create a
new cache entry. Unused cache entries will time out.
A possible optimization is that the source increments the RUN value
by 1 if the list of receivers changes. In that way the router can
immediately remove the entry (S, RUN) and replace it by an (S, RUN+1)
entry. When the RUN value reaches its maximum value the clearing of
the cache entry still relies on the expiration of a timer.
Note that a source can send to multiple sessions. In this case the
source has to partition its RUN space amongst these sessions. It
could be beneficial to split the 32-bit RUN number in two parts: one
session identifier and one real Receiver Update Notification).
Maintaining a cache may seem contradictory to the main characteristic
of CLM (avoid state in the router), but it is important to note that
each router can independently decide to create a cache or not. The
router itself can make the tradeoff between memory and processing
time.
There are two ways of keeping a cache:
1) Each (S, RUN) entry has a list of next hops with the associated
list of destinations. Note that this list of destinations can be a
simple bitmap. When a bitmap is used it is required that the sender
Ooms, et al. Expires October 2000 [Page 13]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
always lists the addresses in the same order. It could be useful to
have a standardized order for this (e.g. always in increasing order).
2) Only (S, RUN) which have one next-hop (still multiple
destinations) are cached. These packets do not have to change their
list of destinations, so the latter information should not be kept in
the cache.
Both ways of applying a cache can be used in parallel.
In a previous version of CLM, RUN was located in the IP option. It
was moved to the destination address field to avoid UDP checksum
recalculation and to allow to apply IPsec to CLM packets. For RUN a
subrange of the multicast address space could be reserved.
If the sender does not support the caching mechanism, it has to set
RUN to a reserved value NO_SENDER_CACHE_SUPPORT (e.g.
233.0.0.0=0xe9000000).
6.2. Caching and Unicast Reroutes
When a unicast route changes the CLM caches need to be updated
because they still forward according to the old unicast topology.
This adaptation requires two components:
1) Intra-node: Communication between the unicast routing and the CLM
cache in the node where the unicast route changes.
2) Inter-node: A downstream signaling to notify the downstream caches
of a unicast route change.
6.2.1. Intra-node
The cache can adapt to the route change by one of following
mechanisms:
- Flush the complete CLM cache when a unicast reroute occurs.
- Loop through the complete CLM cache to check which CLM cache
entries are affected by the unicast reroute. This mechanism is
computational intensive.
- Each unicast route entry keeps a list of pointers to associated CLM
cache entries. This mechanism consumes extra memory.
- For every CLM packet one could do a route look-up for one
destination. In this way the cache is updated every N packets
(assume N destinations). The advantage is that the load is
Ooms, et al. Expires October 2000 [Page 14]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
distributed in time, the cost being that some receivers will loose
some packets.
6.2.2. Inter-node
Three mechanisms can be thought of:
- One could increment the RUN value on the outgoing interfaces for
which the list of destinations has changed. This has the
disadvantage that one needs to store a RUN per outgoing interface and
do a transport layer checksum recalculation in nodes where the RUN
changes.
- One could send a number of packets with a special RUN value
(UPDATE_DOWNSTREAM_CACHE) on the outgoing interfaces for which the
list of destinations has changed. Downstream routers receiving a
packet with this RUN value have to update their CLM cache. The
disadvantage is that one does know how many packets to send to be
sure the downstream caches are updated. When the RUN is split in two
parts (see above) the updating can be limited to the affected
session.
- A more elegant way is to quickly compare the bitmap in the packet
with the bitmaps in the CLM cache. If the bitmap in the packet
equals the ORed bitmaps of the outgoing interfaces of the CLM cache
nothing must be done. If a bit has changed following actions have to
be performed:
1->0 (destination less): clear the bit in the bitmap of the outgoing
interface
0->1 (additional destination): do a unicast route look-up
7. Address list encoding
In this section the Hierarchical Address List Encoding method (HALE)
is described which possibly allows to reduce the packet overhead or
to increase the forwarding capacity. Given a list of IP addresses,
the method iteratively separates the common prefixes of the list of
IP addresses.
To illustrate HALE, consider the multicast tree in Figure 4. The
source S1 wants to deliver the same information to destinations D1
(ABCD), D2 (ABCE) and D3 (AFGH). For simplicity we will assume in
this example that the separation of common bits is only executed on
byte boundaries. The addresses of D1 and D2 have ABC in common, so
it can be written as the compound address ABC{D,E}. The address of
D3 and the compound address ABC{D,E} have A in common, yielding a new
Ooms, et al. Expires October 2000 [Page 15]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
compound address A{BC{D,E},FGH}.
D1
/
/ABCD
A{BC{D,E},FGH} ABC{D,E} / ABCE
S1-------------------R1------------R2----------D2
\
\AFGH
\ AFGH
R3---------------D3
ABCD |
> ABC{D,E} |
ABCE | |
> A{BC{D,E},FGH}
AFGH |
Figure 4
HALE, combined with the aggregation in the routing tables, allows to
save on lookup cycles.
More details on HALE and how the forwarding benefits from this
encoding can be found in Appendix A.
8. IP Protocol extensions
8.1. IPv4
In IPv4 two approaches can be followed to include the list of
destination addresses. Either one adds a new IPv4 option or one adds
an extra header between the network and the transport layer.
Since the IPv4 option field is limited to 40 bytes (of which 4 bytes
are used for the option type field) only 9 destination addresses can
be included. Since this is the real maximum (in the abscence of
other options or other information per destination) we will limit the
number of destinations to 8 to allow the bitmap to fit in 1 byte. If
the number of receivers is larger than 8 multiple packets can be
sent. Although for a different purpose, [AGUI] and [GRAF] already
proposed an IPv4 option to carry multiple destinations. We propose
the new IP option depicted in Figure 5.
Ooms, et al. Expires October 2000 [Page 16]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1 0 0| TYPE | LENGTH |A|U|RES|P|D|ENC| BITMAP |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (Encoded) List of Ports, DS Bytes and Addresses |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
0 1 2 3
Figure 5
TYPE = number for this IPv4 option
LENGTH = total length of the option in bytes
A = anonymity bit: if this bit is set the destination addresses for
which the bit in the bitmap is zero have to be overwritten by zero
(receiver shouldn't know all other receivers).
U = unicast transformation bit: if this bit is set a router is
allowed to reduce the CLM packet to a unicast packet when there is
only one destination left.
RES = Reserved.
P = port bit: if this bit is set the packet will contain a (encoded)
port for each destination.
D = DSCP bit: if this bit is set the packet will contain a (encoded)
DS-byte for each destination.
ENC (2 bits) = encoding method used on the list of ports, DS bytes
and destination addresses. Following encoding methods are defined:
(P,D,ENC)
(0,0,00) = no encoding: flat list of destination addresses
(0,0,01) = hierarchical address list encoding (Appendix A.3)
(0,1,00) = no encoding and DSCP per destination (Figure 6)
BITMAP = every destination has a corresponding bit in the bitmap to
indicate whether the destination is still valid on this branch. The
least significant bit corresponds to the first destination.
Figure 6. shows the 'List of Ports, DS Bytes and Addresses' in case
(P,D,ENC) = (0,1,00).
Ooms, et al. Expires October 2000 [Page 17]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| destination address 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| . . . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| destination address N |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| DS byte 1 | DS byte 2 | ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | DS byte N | padding |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 6
8.2. IPv4 Alternative
Instead of using the IP option field one could add an extra header
between the network and the transport layer. This header is depicted
in Figure 7. The IP header will carry the protocol number PROTO_CLM.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|VERSION|UNUSED | PROT ID | LENGTH |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| CHECKSUM |A|U|RES|P|D|ENC| RESERVED |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| BITMAP |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (Encoded) List of Ports, DS Bytes and Addresses |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 7
VERSION = CLM version number
PROT ID = specifies the protocol on the transport layer
LENGTH = length in bytes of the CLM header.
CHECKSUM = it is not clear yet whether a checksum is needed (ffs).
If only one bit is wrong it can still be useful to forward the packet
to N-1 correct destinations and 1 incorrect destination. On the
other hand when the header info is used to install a cache (see
section 6) one can not allow that packets are permanently forwarded
Ooms, et al. Expires October 2000 [Page 18]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
wrongly. One approach could be to provide a checksum per
destination.
The other fields were described earlier.
8.3. IPv6
Since IPv6 allows more flexibility in adding options (e.g. no
limitation on the size), there is no limitation in terms of encoding
on the number of destinations that can be put in a packet. However,
since a packet can only be sent after all the destinations have been
processed, packets with a lot of addresses will experience a larger
delay.
For IPv6 the overhead will be larger since the addresses are longer.
Note however that IPv6 probably allows an encoding with better
compression because of the geographical/provider distribution of
addresses. Moreover if CLM is used as an interdomain multicast
mechanism only the locator part of the address needs to be
considered.
9. Gradual Deployment
At least two schemes for gradual introduction of CLM can be thougth
of:
1) CLM-capable routers can be interconnected by tunnels (MBone
approach).
2) a router could discover which neighbours are not CLM-capable and
will prematurely clone CLM packets directed to these neighbours. A
mechanism (protocol/protocol extension) to discover CLM capability of
a neighbour is ffs.
Note: Following rules apply to routers that do not understand CLM
packets:
- A router that does not know the CLM option: packets with
unrecognized options must be passed through unchanged ([BAKE]).
- A router will not send ICMP errors for packets with a multicast
address in the destination address field ([BAKE]).
10. Security Considerations
Since a packet contains every destination, it is much more easy to
restrict multicast sessions to certain receivers. It also allows
ISPs to check, when a packet enters their network, how much resources
Ooms, et al. Expires October 2000 [Page 19]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
this packet packet will consume in their network.
In the end-to-end mode it is also easy to restrict the number of
senders or to restrict/monitor the bandwidth of a sender.
IPsec can be applied to CLM packets in order to provide various
security services. We hereby suggest a (non exhaustive) list of
possible scenarios for applying IPsec (ie. AH or ESP) to CLM packets.
If the list of destinations resides in the IPv4 option, one can
provide source authentication and end-to-end packet integrity by
applying AH in transport mode and defining the IPv4 option as a
mutable field ([KENT]). Obviously, the drawback is that an attacker
could maliciously modify the values in the IPv4 option (eg.
destination addresses, bit fields, bit map, ...).
Considering that only the bitmap field is subject to modifications in
the IPv4 option, one could extend the integrity protection onto the
other fields by splitting the IPv4 option into two separate options :
one for the bitmap and one for the other fields. The bitmap option
is then defined as a mutable field while the second option is defined
as non-mutable. The other fields can then be protected with IPsec.
Data confidentiality could also be provided with the use of IPsec
ESP, which can be combined with AH to protect the packet header as
discussed above.
Note that CLM packets on which IPsec has been applied cannot be
transformed into unicast packets (hence their 'U' bit must be cleared
by the sender). If the list of destinations is protected by IPsec,
anonymity cannot be provided either (hence the 'A' bit must be
cleared by the sender).
In order to make use of IPsec, an SA must be agreed upon between the
participants using some automatic method such as IKE or manual
configuration. In its current state, IKE cannot be used to set up
such a single SA between multiple parties, hence manual configuration
would be required.
11. Acknowledgements
The authors would like to thank Olivier Paridaens, Emmanuel Desmet,
Hans De Neve and Miroslav Vrana for the fruitful discussions and/or
their thorough revision of this document. Some of the changes in this
version of the draft were inspired by fruitful discussions with Yuji
Imai and Rick Boivie.
Ooms, et al. Expires October 2000 [Page 20]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
A Hierarchical Address List Encoding (HALE)
A.1. Compound addresses
A list of addresses can be compressed into a compound address by
writing common prefixes only once, followed by a list of their
suffixes.
We used following syntax to represent compound addresses:
<compound_address> ::= prefix "{" <suffix_list> "}"
<prefix> ::= [<address_fragment>]
<suffix_list> ::= [<suffix_list> ","] <suffix>
<suffix> ::= <compound_address> | <address_fragment>
<address_fragment> ::= [<address_fragment>] <symbol>
<symbol> ::= [A-Z] in our example, one bit in practice
(can also be a nibble or octet)
Let's take the following list of addresses as an example:
ABCD, ABCE, AFGH
The addresses all have a common prefix A, so we can write A once
followed by the list of suffixes BCD, BCE and FGH. i.e.
A { BCD, BCE, FGH }
Two of these suffixes share a common prefix BC, so we obtain:
A { BC { D, E }, FGH }
A.2. Processing of a compound address
Following pseudo code parses a compound address and issues a minimum
amount of lookup() calls to a routing table engine. We assume the
lookup takes a symbol (e.g. one bit) as argument and returns a pointer
to it's internal (e.g. tree) structure which can be passed to a next
lookup. The parser maintains a stack of such indices. We assume that a
meta symbol also denotes the number of non-meta symbols that follow (see
encoding in A.3.).
index=routing_table_root; /* routing table entry point */
skip=0; /* flag used to skip over irrelevant
* parts of the compound address */
getch(meta); /* get first meta symbol. Only the
* length is used */
while(1) {
Ooms, et al. Expires October 2000 [Page 21]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
len=LEN(meta); /* number of non-meta symbols that
* follow */
for (i=0; i<len; i++) { /* parse len symbols as
* address_fragment */
getch(symbol); /* read next symbol from the compound
* address */
if (!skip) {
lookup(symbol, &index); /* search in the routing table, using
* symbol, starting from index, storing
* the resulting location back in index
*/
if (IS_LEAF(index)) { /* the next-hop is determined */
forward(index); /* forward packet to this nexthop */
skip=stack_pointer; /* skip to end of this suffix */
}
}
}
getch(meta); /* get next meta symbol */
if (IS_OPEN_BRACKET(meta))
push(index); /* push index on the stack */
if (skip==stack_pointer)
skip=0; /* we've skipped the list_element */
if (IS_CLOSE_BRACKET(meta))
pop(index); /* pop index from the stack */
if (IS_COMMA(meta) && skip)
index=stack_pointer; /* take the index on top of the stack */
}
A.3. Compound address encoding example
Below is a possible encoding scheme for a compound address which
limits the amount of overhead.
CLM option:
Ooms, et al. Expires October 2000 [Page 22]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1 0 0| TYPE | LENGTH |A|U|RES|P|D|ENC| BITMAP |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NUM META | meta symbols ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| meta symbols + padding |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| address_fragments, not byte aligned |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
NUM META = number of meta symbols
Meta symbol:
0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+
|X|sym| length |
+-+-+-+-+-+-+-+-+
X = unused
sym = meta symbol
00 = open bracket
01 = close bracket
10 = comma
11 = close bracket followed by comma
length = number of bits of the address_fragment (symbol) following this
meta symbol.
References
[AGUI] L. Aguilar, "Datagram Routing for Internet Multicasting",
Sigcomm84, March 1984.
[BAKE] F. Baker, "Requirements for IP Version 4 Routers", RFC1812, June
1995.
[DEER] S. Deering, "Multicast Routing in a datagram internetwork", PhD
thesis, December 1991.
[FARI] D. Farinacci, "Multicast Source Discovery Protocol", draft-
farinacci-msdp-00.txt, June 1998.
Ooms, et al. Expires October 2000 [Page 23]
Internet Draft draft-ooms-cl-multicast-02.txt April 2000
[GRAF] C. Graff, "IPv4 Option for Sender Directed Multi-Destination
Delivery", RFC1770, March 1995.
[HAND] M. Handley, H. Schulzrinne, E. Schooler, J, Rosenberg, "SIP:
Session Initiation Protocol", RFC2543, March 1999.
[HOLB] H. Holbrook, "Express Multicast: Making Multicast Economically
Viable".
[HOL2] H. Holbrook, B. Cain, "Source-Specific Multicast for IP",
draft-holbrook-ssm-00.txt, March 2000.
[KENT] S. Kent, R. Atkinson, "Security Architecture for the Internet
Protocol", RFC2401, November 1998.
[OIKA] J. Oikarinen, D. Reed, "Internet Relay Chat Protocol", RFC1459,
May 1993.
[PERL] R. Perlman, "Simple Multicast: A design for Simple, Low-overhead
Multicast", draft-perlman-simple-multicast-02.txt, February
1999.
Authors Addresses
Dirk Ooms
Alcatel Corporate Research Center
Fr. Wellesplein 1, 2018 Antwerpen, Belgium.
Phone : 32 3 2404732
Fax : 32 3 2409879
E-mail: Dirk.Ooms@alcatel.be
Wim Livens
Colt Telecom
Zweefvliegtuigstraat 10, 1130 Brussel, Belgium.
Phone : 32 2 7901705
Fax : 32 2 7901711
E-mail: WLivens@colt-telecom.be
Olivier Paridaens
Universite Libre de Bruxelles, Service Telematique et Communication
Bd du Triomphe, CP 230, 1050 Brussels, Belgium.
Phone : 32 2 6505703
Fax : 32 2 6293816
E-mail: paridaens@helios.iihe.ac.be
Ooms, et al. Expires October 2000 [Page 24]
| PAFTECH AB 2003-2026 | 2026-04-23 23:36:17 |