Table
of Contents
1.
Introduction
IP Multicast
has been proposed to support group communications such as video conferencing
and data distribution. Many multicast protocols have been developed
for over a decade. However, no single multicast protocol can completely
supports all types of group communications.
As pointed
out by IETF reliable multicast transport Working Group (rmt wg) [1],
"one size fits all" protocol will be unable to meet the requirements
of all applications. The existing multicast protocols are mostly proposed
for a large group of many-to-many communication. However, for small
group communications, for example a video conferencing among ten people,
the cost in creating the multicast trees is too expensive, and they
do not scale well with a large number of groups.
To support
such small group communications, we propose a new multicast protocol
called Sender Initiated Multicast (SIM). SIM will not replace the
existing multicast protocols. It is designed to support a large number
of small groups. Its objective is to decrease the complexity and the
cost of deploying the protocol.
In this
section, we will discuss about the advantages and disadvantages of
the existing multicast protocols. Then, we will describe overview
of SIM.
1.1
Today's Multicast Technologies
IP Multicast
or the traditional multicast model is proposed by Deering in 1988 [2].
In this model, a multicast group is identified by a multicast address,
which is Class D in IP address space [3]. This idea
requires an administration mechanism of a global multicast address space
to avoid any conflicts in use of multicast addresses.
The
advantages of this traditional model are:
1)
Dynamic membership
Any
nodes that know the multicast group address can join or leave the
group at any time.
2)
On-demand data distribution
Any
group members can send data to other members at any time. At the
same time, any nodes can start receiving data anytime without disturbing
the sender.
However,
the disadvantages of this traditional model are:
1)
Address allocation
Because
the multicast group address has to be unique for each group, they
need a global multicast address allocation mechanism.
2)
Multicast routing
It
requires both inter-domain and intra-domain routing protocols.
3)
State maintenance on routers
Routers
on multicast trees have to maintain forwarding states for each multicast
group.
3)
Control message
Control
messages have to be exchanged among routers on multicast trees to
establish, keep or tear down multicast paths.
Even though
on-demand data distribution is one of the advantages of this traditional
model, it may be a security hole for the group communication. Anyone
who knows the group multicast address can join in the group and can
send traffic to the group, because there is no mechanism to restrict
hosts to join a specific multicast group. With this lack of this vital
mechanism, an unauthorized sender can easily disrupt the multicast traffic.
Therefore, the member management mechanism is also required to deploy
IP multicast service in the actual commercial Internet environment.
To simply
the traditional multicast, Simple Multicast [4]
and Source Specific Multicast (SSM) [5] are proposed.
Instead of using only multicast group address to identify a group,
they use the combination of source address and destination multicast
address. Therefore, there is no need to allocate a global multicast
address.
Currently,
a new scheme of multicast called "Explicit Multicast" or "xcast" has
been proposed [6] [7]. Xcast
is not one-fits-all multicast model, but it aims to support small
group communication. While the traditional multicast schemes can support
a limited number of very large multicast sessions, xcast can support
a very large number of small multicast sessions. Instead of using
multicast group address, xcast protocols explicitly encode list of
destinations in the data packets. The membership of a multicast group
is controlled by the data sender. Routers on multicast trees just
forward packets to all downstream routers for all receivers in destination
lists. Examples of xcast protocols are MDO6 [8],
CLM [9], DCM [10], ERM [11],
and SGM [12].
The
advantages of Xcast are:
1)
No states on routers
Routers
on multicast trees basically do not need to maintain states for
each multicast group.
2)
No control message
Basically,
no control message is exchanged among routers.
However,
the disadvantages of Xcast are:
1)
High cost in forwarding packets
Xcast
protocols basically need the additional packet header, and have
to process this header when the packets pass each router. Therefore,
it is relatively high cost to forward the packets comparing to the
traditional multicast protocols.
2)
Less data space
Since
a receiver list has to be attached to the packets, data area in
each packet becomes slightly smaller.
1.2
Overview of SIM
Considering
problems of the existing multicast protocols, Sender Initiated Multicast
(SIM) is designed to aim the following.
- Less
cost in maintaining state information
- Simple
and less-costly packet forwarding mechanism
- Simple
to deploy and support existing applications on receiver side
SIM is not
intended to replace with the existing multicast protocols, but it is
more like a subset of other protocols. Contrary to the traditional multicast
model, which supports many-to-many group communications, SIM is designed
to support mostly a one-to-many small group communications.
Similar
to Simply Multicast and SSM, each multicast group is identified by
the combination of sender IP address and a group multicast address.
With this mechanism, the collision of group multicast address can
be avoided. Moreover, there is no need to manage global multicast
address space, and can support a very large number of small groups.
As same as xcast protocols, the members of a receiver group are explicitly
specified by the data sender. Therefore, the sender can restrict number
of receivers and can provide access control. The data sender may announce
a multicast session to the end nodes by sending a Join-Invitation
message to the end nodes, or through mailing list.
In order
to specify members of a group, the list of receivers is attached to
the IP datagram. The list is defined in SIM header and the header
is attached as newly defined IP option. Depending on how often it
attaches the receiver list, SIM has two delivery modes; list mode
and preset mode. In SIM list mode, the sender always attaches a receiver
list to the packets. Contrary, in SIM preset mode, the sender periodically
attaches a receiver list to the packets.
Each
packet is forwarded to the next hop SIM router. At the branching SIM
routers, which perform as the branching point of multicast delivery
tree, the packet will be duplicated and forwarded to the next hop
SIM router. Only at the last branching SIM router, the packet will
be duplicated for all receivers in the receiver list, and forwarded
to them by unicast routing.
SIM
routers on the paths maintain forwarding states called SIM Forwarding
Information Base (FIB). SIM routers will look up for the next hop
nodes from SIM FIB. The nice advantage is that SIM routers use a two
tuple of sender address and multicast group address to look up for
SIM FIB. Therefore, the number of look-ups on forwarding table is
usually more than once. Furthermore, in order to save routers' resources,
such as buffer space and processing power, a SIM FIB entry is deleted
in two cases; (1) when it comes to an age, in other words, the timer
at the router is expired, and (2) when the last packet of a flow is
already transmitted. This mechanism can help and improve the packet
forwarding performance at SIM routers.
Another
significant feature of SIM is SIM Tunnel. SIM has a capability to
create a tunnel between SIM branching routers, in order that SIM non-branching
routers on the multicast tree have no need to maintain the forwarding
states. This method helps SIM to decrease cost on maintaining forwarding
states on routers, and can also deploy a high-speed forwarding process.
1.3
Advantages of SIM
SIM has
the following advantages.
1)
Scalable in number of multicast group
Even
though SIM is designed for small group communications, it scales
well with the number of small multicast group. By using a two tuple
of sender address and multicast group address, each data sender
can has as many as multicast group they want. Moreover, it eliminates
costs in deploying global multicast address allocation protocol.
2)
Simple and cost-efficient packet forwarding mechanism
A SIM
router forwards the packets to other SIM routers and also to receivers
by unicast routing. Therefore, there is no need to deploy any additional
multicast inter- and intra- domain routing protocol. In addition,
because a packet is duplicated only at branching routers, SIM does
not excessively consume the network resources.
3)
Easy to deploy on the global Internet
In order
to use SIM, at least the sender and one router on the path have
to implement this SIM protocol. In the SIM mechanism, at the last
branching router, the SIM header will be detached from the packets.
Some fields of the headers, such as the destination address field,
will be replaced with receiver's unicast address. Therefore, receivers
can receive SIM packets through the ordinary unicast packets processing
mechanism. In other words, the receivers have no need to modify
their protocol stacks. The existing applications residing on the
receivers can also be used without any modifications.
2. Design
In this
section, we describe the design of SIM and its basic operations in detail.
2.1
Creating a multicast session
SIM uses
the two tuple of (sender unicast address, multicast group address)
to identify a multicast session. Therefore, the multicast group address
does not need to be unique. That means every senders can assign the
full 28 bits worth of multicast addresses. Each sender may assign the
multicast group address randomly. A multicast session will contain of
one sender and multiple receivers. For many-to-many communication such
as video conferencing can be achieved by creating multiple multicast
sessions.
2.2
Membership
Because
each senders control the access separately, they need to notify the
receivers about the multicast session. That is, they have to notify
the sender unicast address and the multicast address. These can be deployed
through several possible membership management system depending on the
communication models.
For
one-to-many group communication such as file distributing, the sender
itself can hold the membership management system. It may send a Join-Invitation
message to each receiver. And after receiving Join-Acceptance
message from them, it can begin sending multicast data.
On the
other hand, for many-to-many group communication such as video conferencing,
it is not convenient to maintain a same receiver list on all the nodes.
It would be better to have only one node acts as a group membership
management server that will centrally maintain the receiver list.
This node may be one of a group member or the third part node. Each
member has to register to this membership management server, and share
the list before beginning the communication.
2.3
Forwarding Procedure
Basically,
many xcast protocols also attach the receiver list to each packet, and
forward the packets along the unicast paths. However, because these
protocols maintain forwarding state on per-receiver basis at routers
that can handle these protocols, the number of look-ups on forwarding
table is usually more than once. It is relatively heavy to forward the
packets compared to the ordinary IP multicast mechanism.
In contrast,
this problem is alleviated with SIM. Each group is identified by a
two-tuple, the sender's unicast address and a group multicast address.
When the router received a SIM packet, it will use this two-tuple
as a key to look up the SIM forwarding table. This technique will
reduce the number of look-ups to once, and gracefully cut off the
overhead on forwarding packets. The detail of SIM forwarding table
will be described in the next section.
Figure
1: SIM Forwarding Procedure
SIM forwarding procedure is defined as following (See Figure 1).
- The
sender sends the packets to the nearest SIM router.
- The
SIM router will find the receiver list from packet header, and look
up unicast routing table to find out the next hop nodes for each
receiver
- If
the packet for all receiver in the list have to be forwarded to
the same next hope node, and that node is also a SIM-aware router,
the packet will be forwarded to the next SIM router without any
modification.
- Else
if the packet has to be forwarded to multiple next hop nodes, the
packet will be duplicated. The receiver list of each packet will
be rewritten according to the receivers.
- If
there is only one receiver on the list, the packet header will be
rewrite as if they are unicast packets.
- If the next hope router is not SIM-aware router, and it is assumed
that there is no SIM-aware router on the network path to the receivers,
the packet will be send separately to each receiver. The packet
header will be rewrite as if they are unicast packets.
- The
packets will be forwarded by using rules 2-4 as described above
until they reach all the receivers.
2.4
SIM Forwarding Information Base (FIB)
In order
to accelerate the forwarding procedure, SIM routers on the paths register
the next hop nodes for each multicast group in SIM Forwarding Information
Base (FIB). SIM FIB entry is in the following format:
( sender,
group) --> ( gen_count, coming-from, next-hop-list )
Each SIM FIB contains of generation counter (gen_count), in-coming
network interface (coming-from) and the next hop nodes list (next-hop-list).
The generation counter of FIB is used for maintain or updating versions
of FIB. The initial value of generation count should be random. A
two tuple of sender unicast address and multicast group address will
be used as key to hash a SIM FIB enry in order to put or look up to
SIM forwarding table.
In the
case of "list mode", a receiver list is attached to all packets in
a flow. A SIM FIB entry can be registered as a cache to decrease the
number of look-ups. Caches can be discarded any time, for example,
when memory is full. In the case of "preset mode", a receiver list
is periodically attached to packets in a flow. A registered SIM FIB
entry is used to forward the following packets that do not have receiver
lists. Except packets with receiver lists, the forwarding processing
cost for SIM might be close to the cost for Simple Multicast and SSM.
In both
modes, a SIM FIB entry will be removed if a router does not observe
a corresponding receiver list for a certain period of time (i.e. soft
state). We define this period of time as SIM_FIB_AGING.
When
the sender wants to change the members of a receiver list, the new
receiver list must be attached to a SIM packet, and the generation
count must be incremented. When the SIM router receives such packet,
the SIM router must create a new SIM FIB entry. The old generation
of SIM FIB entry of the same multicast group should be kept for SIM_FIB_AGING
time. The reason that we cannot delete the old generation of SIM FIB
as soon as we received the new one is that some packets of the old
generation may reach the network out-of-order. Moreover, in the case
that the SIM router does not receive a receiver list for a flow for
SIM_FIB_TIMEOUT time, the corresponding SIM FIB entry must be removed.
2.5
SIM FIB Operations
SIM routers
maintain SIM FIB entries for each multicast group as specified by three
flags in receiver lists. "Preset flag" specifies the operation mode:
list mode or preset mode. List mode is designed for relatively short
flows. In this mode, a receiver list is attached to all packets in a
flow.
Preset
mode is designed for relatively long flows, such as real time traffic.
In this mode, a receiver list is periodically attached to packets
in a flow. The interval time of sending such packets is SIM_FIB_INTERVAL
time. If there is no appropriate packet to attach a receiver list
at the time just before the timer expiration, a SIM packet without
upper-layer protocol and data may be sent.
The
other two flags are "Temporary flag" and "Delete flag". "Temporary
flag" is set when a flow consists of only a few packets that the members
in the receiver list are temporary changed. If "Temporary flag" flag
is set for a SIM packet, SIM routers must use the attached receiver
list to forward the packet even if a corresponding SIM FIB entry exists.
SIM routers must not create nor update a corresponding SIM FIB entry.
If a corresponding SIM FIB entry already exists for this flow, the
entry should be kept. This "Temporary flag" will be very useful when
the sender has to retransmit some packets to only a subset of receivers
in the group.
"Delete
flag" should be set for the last packet of a flow in order to ask
SIM routers to remove a corresponding SIM FIB entry. If a SIM router
receives such SIM packet, the SIM router should remove the entry after
SIM_FIB_AGING time. This SIM_FIB_AGING time is for the packets that
reach the network out-of-order and reach the SIM router after that
last packet of the flow.
3. SIM
Packet Header
In this
paper, we discuss SIM packet for IP version 4. SIM packet header contains
of three parts: the outer IP header, SIM header, and the inner IP header
(See Figure 2). On the outer IP header, the source address is indicates
the sender IP address or a SIM router address, and the destination address
indicates the next hop SIM router. Source address and destination address
of this outer IP header will be rewritten, whenever the packets pass
a SIM branching router.
Figure 2: SIM Packet Header
The
second part is SIM header. SIM header contains of receiver list, generation
count, and header flags. SIM has four operation flags; preset flag,
temporary flag, delete flag, and jump flag. We have already described
the first three flags in the previous section. The jump flag is used
for creating SIM Tunnel described in detail in the next section. The
receiver list will be rewritten when the packets pass a SIM branching
router.
The
last part is the inner IP header. The source address of this inner
IP header indicates the sender IP address, and the destination address
indicates the multicast group address. This header will be used in
identifying the multicast session, and will not be rewritten until
the last branching SIM router.
4. SIM
Tunnel
In preset
mode, SIM can automatically create a SIM Tunnel between a two branching
router in order to decrease the number of routers that need to maintain
states, i.e. SIM FIB. SIM Tunnel will be used to skip non-branching
router. This automatic SIM tunnel is one of the significant features
of SIM. It can be created by using Jump flag on SIM header.
Whenever
the packets forwarded to non-branching router, the jump flag will
be set. When the packets reach the next SIM branching router and the
Jump flag is set, that SIM router will send a "Redirect Message" to
the previous SIM branching router (See Figure 3).
Figure 3: SIM Tunnel
Because
the source address of outer IP header will be changed only when the
packets forwarded from the SIM branching router, SIM router can know
the previous SIM branching router from this source address of the
packets. When the SIM router received the redirect message, it will
put the next SIM branching router to the destination address field
instead of the neighbor SIM non-branching router. And, this will create
a SIM Tunnel during two SIM branching routers.
The
non-branching routers have no need to maintain the SIM FIB entries.
This mechanism accelerates the forwarding process, and also reduces
the number of FIB maintained on SIM routers.
5. SIM
Control Message
SIM has
two types of control message; SIM Hello Message and SIM redirect Message.
These control messages may be assigned to TCP well-known port of SIM
routers. In this section, we describe these two control messages.
5.1
SIM Redirect Message
SIM Redirect
Message is used for creating SIM Tunnel that described in section 4.
During forwarding the packets, SIM routers exchange this control message.
SIM Redirect Message is in the following form:
( SIM
branching router address, Source address, Multicast group address)
5.2
SIM Hello Message
SIM router
can detect the existing of other SIM routers by broadcating SIM Hello
packets periodically to the network. The status returned from neighboring
SIM routers would be one of the following:
- RUNNING
- This
state means the SIM router is running perfectly.
- Any
packet both in list mode and in preset mode can be forwarded
to this SIM router.
- FULL
- This
state means the SIM FIB table is full and no more SIM FIB entry
can be added for a while.
- Packets
in list mode can be forwarded to this SIM router.
- Packets
in preset mode cannot be forwarded to this SIM router, so packets
have to be duplicated for each receiver.
- DOWN
- This
state means the SIM router is down now.
- No
packet can be forwarded to this SIM router. Packets have to
be duplicated for each receiver if possible.
6.
Security Consideration
As discussed
in [13], some forms of denial of service (DoS)
attackers can take advantage of the multicast characteristics to increase
their effects. Such an attack is the smurf attack, which uses an ICMP
Echo request (ping) sending to a multicast address with a source address
that is the target of the attack. The traditional multicast, which uses
multicast address for the destination address, deals with this problem
by setting up a router or a host not to reply ICMP requests with a multicast
address.
In xcast
model, the DoS effect is greatly diminished because of the small number
of members in a multicast group. However, the attacker can use multiple
multicast groups in order to create a DoS attack as effectively as
in the traditional multicast model. It will be more difficult to deal
with this problem, because the destination may not recognize that
it is the xcast traffic. One strategy they proposed in [12]
is to use IPsec for securing explicit multicast traffic. However,
it only provides confidentiality and/or authentication between sender
and receivers. It cannot restrict nodes that can forward packets to
xcast routers. Thus, it may not be a good solution to stop smurfing
DoS attacks.
In the
case of SIM, the same smurfing DoS attacks may be occurred. The attacker
may attack a host by using SIM packets to send ICMP Echo request.
However, similar to xcast protocols, SIM supports only small group
multicast, so we also can say that the smurfing DoS attacks may not
be effective.
Even
though, detection for this DoS attack will probably be provided on
SIM routers. Basically, at the last SIM branching router, the source
and destination fields of the packets will be replaced with the sender
unicast address and the receiver address. Therefore, a receiver cannot
distinguish the receiving ICMP Echo request, whether it was originally
SIM packet or was traditional unicast packet. However, the last SIM
branching router should know the answer. Thus, the detection of this
type of DoS attack should be deployed on the SIM routers. When the
last branching SIM router duplicates a packet for each receiver, it
should check "Protocol" field of IP header for IP version 4. This
"Protocol" field indicates the next level protocol type. And, as assigned
in RFC1700, ICMP has the protocol number "2". Thus, SIM router should
not forward the packet and should discard it, if it detects that protocol
field is "2".
In this
strategy, all SIM branching routers have to check all of the SIM packets.
Thus it may generate more overheads on SIM router. Moreover, this
strategy can only alleviate the effect of smurfing DoS attack, the
strategy to deal with other kinds of DoS attack needs more considertion.
7.
Conclusion
To achieve
incremental deployment of multicast communication widely in the global
Internet, we proposed another multicast mechanism called "Sender Initiated
Multicast" (SIM). SIM will not replace the existing multicast protocol.
It is designed to support small group communication, and will be a subset
of other multicast protocols.
In order
to achieve incremental deployment, SIM has several advantages: explicit
group management scheme, simple and cost effective packet forwarding
mechanism, and easiness to deploy SIM on the global Internet. The
most significant outcome is that SIM can be quite easily deployed.
In order to use SIM, at least the sender and one router on the path
have to implement the protocol. The receivers have no need to modify
their protocol stacks. We believe that this greatly benefits for the
existing applications. And this advantage will make SIM incrementally
deployed on the global Internet.
In this
paper, we have described the design of SIM in detail. SIM is now under
implementation for IP version 4 on FreeBSD. For future works, we have
to evaluate SIM forwarding performance from the implementation. Next
we have to design SIM in detail for IP version 6, and also have to
develop the APIs.
8.
Acknowledgement
We would
like to thank Noritoshi Demizu of Access Co. Ltd. who was the first
developer of SIM. He has provided helpful comments and also helpful
technical information to improve this proposal.
9.
References
-
IETF Reliable Multicast Transport (rmt) Working Group
- S.
Deering, "Host Extensions for IP Multicasting", RFC1112, Aug 1989
- D.
Thaler, M. Handley, D. Estrin, "The Internet Multicast Address Allocation
Architecture", draft-ietf-malloc-arch-04.txt, work in progress,
Jan 2000
- Perlman,
R., Lee, C-Y., Ballardie, A., Crowcroft, J., "A Design for Simple,
Low-Overhead Multicast", work in progress, draft-perlman-simple-multicast-03.txt,
work in progress, Oct 1999
- H.
Holbrook, B. Cain, "Source-Specific Multicast for IP", draft-holbrook-ssm-arch-02.txt,
work in progress, Mar 2001
- R.
Boivie, et. al., "Explicit Multicast (Xcast) Basic Specification",
draft-ooms-xcast-basic-spec-01.txt, work in progress, March 2001
- D.Ooms,
"Taxonomy of xcast/sgm proposals", draft-ooms-xcast-taxonomy-00.txt,
work in progress, Jul 2000
- I.
Yuji, "Multiple Destination option on IPv6 (MDO6)", draft-imai-mdo6-02.txt,
work in progress, Sep 2000
- D.
Ooms, W. Livens, "Connectionless Multicast", draft-ooms-cl-multicast-02.txt,
work in progress, Apr 2000
- L.
Blazevic, J. Le Boudec, "Distributed Core Multicast (DCM): a multicast
routing protocol for many groups with few receivers", ACM CCR Vol.29,
No.5, Oct 1999
- J.
Bion, D. Farinacci, M. Shand, A. Tweedly, "Explicit Route Multicast
(ERM)", draft-shand-ERM-00.txt, work in progress, June 2000
- R.
Boivie, N. Feldman, Ch. Metz: "Small Group Multicast: A New Solution
for Multicasting on the Internet", Internet Computing, Vol. 4, No.
3, May/June 2000
- O.
Paridaens, D. Ooms, "Security Framework for Explicit Multicast",
draft-paridaens-xcast-sec-framework-01.txt, work in progress, November
2000