INTERNET DRAFT Jae-Hoon Jeong
Expires: December 2002 Jung-Soo Park
ETRI
June, 2002
Unicast Routing based Multicast Routing Protocol
for Mobile Ad Hoc Networks (UMR)
<draft-jeong-umr-manet-00.txt>
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC 2026 except that the right to
produce derivative works is not granted.
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 document describes a protocol for multicast in mobile ad-hoc
networks - named Unicast Routing based Multicast Routing Protocol
for Mobile Ad Hoc Networks (UMR). The protocol uses a new scheme
for mobile ad-hoc network that has dynamic topology without
managing multicast tree and depending on simple flooding. It is the
multicast routing protocol that works in use of unicast routing
protocol. Any ad-hoc unicast routing protocol can be used.
Table of Contents
Jeong, Park Expires December 2002 [Page 1]
INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002
Status of this Memo
Abstract
1. Introduction
2. Assumptions
3. Terminology
4. UMR Overview
5. Encoding of UMR header
5.1 UMR header
5.2 UMR Messages
6. Protocol Operations
6.1 Registration of Multicast Group Member
6.2 Registration of Multicast Group Source
6.3 Leave of Multicast Group Member
6.4 Leave of Multicast Group Source
7. Implementation Considerations
8. IANA Considerations
9. Security Considerations
10. References
Authors' Addresses
1. Introduction
UMR, the protocol specified in this document is designed to provide
multicast functionality without managing multicast tree and with
the minimum control information and the routing information
provided by ad-hoc unicast routing in mobile ad-hoc networks. It
utilizes the unicast routing to update the information for
multicast routing. Any ad-hoc unicast routing that is based on
table-driven or on-demand method can be used.
It can provide the efficient multicasting in mobile ad-hoc network
that changes its network topology very frequently because of not
using multicast tree and using only unicast routing. It eliminates
the per session signaling and per session state information of
tree-based multicast schemes [MAODV]. It also maximizes the
utilization of bandwidth because it doesn't depend on simple
flooding [SIMPLE]. This allows UMR to support very large numbers of
multicast sessions in ad-hoc network.
It adopts the concept of Xcast and Xcast+ to deliver the multicast
data packet to multicast group members [XCAST, XCAST+].
2. Assumptions
We assume that all mobile nodes wishing to communicate with other
nodes within the mobile ad-hoc network are willing to participate
fully in the protocols of the network. In particular, each node
participating in the network should also be willing to forward
packets for other nodes in the network.
We also assume that all mobile nodes run the same ad-hoc unicast
Jeong, Park Expires December 2002 [Page 2]
INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002
routing as is either table-driven or on-demand.
Packets may be lost or corrupted in transmission on the wireless
network. A node receiving a corrupted packet can detect the error
and discard the packet.
3. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in
this document are to be interpreted as described in RFC 2119
[RFC2119]. New terms are defined below:
Mobile Node (MN) The mobile node that is host and plays a
role of router.
Multicast Member The table for multicasting that is used by
Table (MMT) multicast source node per multicast group.
The fields consists of group-member,
next-hop, hop-count and status.
Multicast Source The table for multicasting that is used by
Table (MST) multicast group member node per multicast
group. The fields consists of group-source,
next-hop, hop-count and status.
4. UMR Overview
In the traditional multicast model, Host Group Model, the multicast
packet is identified by a multicast address of all group members.
But, in UMR, the multicast source node keeps track of the
destinations in the multicast group that it wants to send packets
to.
The source node encodes the list of multicast group members in the
UMR header, and then sends an adjacent MN the multicast data
packet. Each intermediate MN that plays a role of router along the
way towards to all the destinations in the list of UMR header
parses the header, partitions the destinations based on each
destination's next hop, and forwards a packet with an appropriate
new UMR header to each of the next hops.
For example, let's assume that multicast source SRC_1 is trying to
send a multicast packet to all the members of multicast group G
that have already been registered in SRC_1 - from RCV_1 to RCV_6 -
in Figure 1 below:
Jeong, Park Expires December 2002 [Page 3]
INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002
RT_3 ---- RCV_1 RCV_2
/ /
/ /
SRC_1----- RT_1 ---- RT_2 ---- RT_4 ---- RT_5 --- RCV_3
\ \
\ \
RT_6 ---- RCV_5 RCV_4
\
\
RCV_6
where SRC : Source, RT : Router & RCV : Receiver
Figure 1. Example of multicast packet delivery in UMR
The delivery of a multicast packet is accomplished as follows:
SRC_1 sends a UMR multicast packet with the list of destinations in
its UMR header to the first router, RT_1.
As we ignore the details, the multicast packet that SRC_1 sends to
RT_1 looks like this:
[src = SRC_1 | dest = RCV_1 RCV_2 RCV_3 RCV_4 RCV_5 RCV_6 | group=G
| payload]
When RT_1 receives this packet, it needs to properly process the
UMR header. The processing that each transit MN does on receiving
the UMR multicast packet is performed as the following steps:
Step 1. Lookup of unicast routing table for determining the next
hop for each of the destinations listed in the multicast
packet.
Step 2. Partition of the set of destinations based on their next
hops.
Step 3. Copy of the multicast packet for each different next hop.
Step 4. Modification of the list of destinations in each of the
copies so that the list in each copy includes just the
destinations that ought to be routed through each
corresponding next hop.
Step 5. Transmission of the modified copies of the multicast
packet on to the next hops.
By the above procedure, when RT_2 receives the multicast packet, it
will send one copy of the packet to next hop RT_3 with a UMR list
of {RCV_1}, send one copy of the packet to next hop RT_4 with a UMR
list of {RCV_2 RCV_3 RCV_4}, and send one copy of the packet to
next hop RT_6 with a UMR list of {RCV_5 RCV_6}.
Jeong, Park Expires December 2002 [Page 4]
INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002
When RT_3 receives a UMR multicast packet destined to RCV_1, RT_3
converts the UMR multicast packet into a standard multicast packet
and multicasts the packet to multicast group G [XCAST+]. Because
RCV_1 has joined multicast group G, it can receive the packet.
With the similar way, the rest of multicast group members - RCV_2,
RCV_3, RCV_4, RCV_5 & RCV_6 - can receive the multicast packet from
SRC_1.
Note that when network topology changes, the routing for UMR
multicasting will automatically adapt to the new topology since the
path that a UMR multicast packet takes to each multicast group
member always follows the ad-hoc unicast routing for each
destination.
5. Encoding of UMR header
The source address field of the IP header contains the address of
the UMR sender. The destination address field contains the All-
UMR-Routers address that is to have a fixed value. Every UMR MN
joins this multicast group to receive any UMR multicast packet. The
protocol field contains the UMR protocol number, PROTO_UMR, that is
to have a fixed value.
The list of destinations that are multicast group members will be
encoded in a separate header. The UMR header is contained between
the IP header and the transport layer header as follows:
[IP header | UMR header | transport header | payload ]
Note that since the UMR header is included to the data portion of
the IP datagram, if the multicast source node wishes to avoid IP
fragmentation, it must take the size of the UMR header into
account.
We consider IPv4 currently.
5.1 UMR header
The UMR header is depicted in Figure 2. It consists of two parts:
a fixed part (first 16 octets) and a variable length part that is
specified by the fixed part.
Jeong, Park Expires December 2002 [Page 5]
INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002
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| Type | Code | Num_of_Address| Reserve |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Group_Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Sequence_Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next_Protocol | Length | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| List_of_Addresses |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 2. UMR header
Version 4-bit UMR version number. This document
describes version 1.
Type 8-bit UMR message type. This field identifies
UMR packet.
Code 4-bit unsigned integer. This supplements Type
field to represent the status information or
the return value.
Num_of_Address 8-bit unsigned integer. This field indicates
the number of addresses that are contained in
the following field, List of Addresses.
Reserve 8-bit reserved field.
Group_Address 32-bit multicast group address.
Sequence_Number 32-bit unsigned integer. This field is used
to identify duplicate packet. Each MN
maintains its own squence number for this field.
Next_Protocol 8-bit unsigned integer. This field indicates
the protocol of the following header
Length 8-bit unsigned integer. This field indicates
the length of the UMR header in 4-octet words.
Checksum 16-bit checksum. This field is the checksum on
the UMR header only. This is verified and
recomputed at each point that the UMR header is
processed. The checksum field is the 16-bit
one's complement of the one's complement sum of
all the bytes in the header.
List_of_Addresses The list of addresses. Each address size is four
Jeong, Park Expires December 2002 [Page 6]
INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002
octets.
5.2 UMR Messages
The kinds of UMR packet are two; (a) Data packet and (b) Control
packet.
UMR Data packet is the packet that contains the multicast data sent
by source node.
UMR Control packet is the packet that contains the multicast-
related control information such as join and leave.
The Type field of UMR header identifies the kind of UMR packet.
The values of Type field are as follows;
1 UMR_DATA UMR Data packet.
2 UMR_CONTROL_MEMBER_REGISTRATION UMR Control packet for
registering a multicast
group member in any
multicast group source.
3 UMR_CONTROL_MEMBER_LEAVE UMR Control packet for
informing all the multicast
group sources of leaving
the multicast group.
4 UMR_CONTROL_SOURCE_REGISTRATION UMR Control packet for
registering a multicast
group source in any
multicast group member.
5 UMR_CONTROL_SOUCE_LEAVE UMR Control packet for
informing all the multicast
group members of the stop
of sending multicast data.
The Code field of UMR header provides more detailed control
information. The values of Code field are as follows;
1 CODE_REQUEST UMR Control packet that
requests the operation
indicated by Type field.
2 CODE_ACK UMR Control packet that
acknowledges the result of
the requested operation.
3 ERROR UMR Control packet that
informs the other party of
Jeong, Park Expires December 2002 [Page 7]
INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002
the occurrence of an error.
At this time, the field
Num_of_Address contains
the value of detailed
error.
6. Protocol Operations
UMR can work after ad-hoc unicast routing is set up.
6.1 Registration of Multicast Group Member
When a wanted multicast group member joins multicast group, it
broadcasts a UMR control packet indicating the registration of
multicast group member.
The destination field of IP header contains 255.255.255.255 for
broadcasting. The Type field of UMR header contains
UMR_CONTROL_MEMBER_REGISTRATION. The Code field of UMR header
contains CODE_REQUEST.
The control packet is distributed towards any multicast group
source. Note that any intermediate MN doesn't broadcast the packet
that has broadcast just before. Each MN identifies the duplicate
packet with the Sequence_Number field of UMR header.
When a multicast group source receives the packet, the following
procedure is performed.
Step 1. Registration of multicast group member in MMT.
The source registers the IP address of the multicast group
member in the group-member field of MMT and fills the
other fields of MMT such as next-hop, hop-count and status
with the unicast routing table. next-hop is the next hop
towards the group member. hop-count is the distance from
source to group member by the number of hops. status
indicates the connectivity status for group member in
unicast routing. The connected status is represented as 1
and disconnected status is represented as 0. Of course, by
the change of unicast routing, the other fields of MMT
except group-member are changed appropriately.
Step 2. Acknowledgement of the registration packet.
Source makes a UMR Control packet for acknowledging the
completion of the registration and sends it to the group
member in unicast. The Type field of UMR header contains
the same as that of the registration packet. The Code
field contains CODE_ACK. The List_of_Addresses field
contains the IP address of the source.
When the group member receives the acknowledgement packet for
registration, it registers the IP address of the source in the
Jeong, Park Expires December 2002 [Page 8]
INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002
group-source field of MST. The other fields of MST are filled
appropriately with the unicast routing table.
6.2 Registration of Multicast Group Source
Before a new multicast group sender sends multicast data packets,
it broadcasts a control packet indicating the registration of
multicast group source.
The destination field of IP header contains 255.255.255.255 for
broadcasting. The Type field of UMR header contains
UMR_CONTROL_SOURCE_REGISTRATION. The Code field of UMR header
contains CODE_REQUEST.
The control packet is distributed towards any multicast group
member.
When a multicast group member receives the packet, the following
procedure is performed.
Step 1. Registration of multicast group source in MST.
The member registers the IP address of the multicast group
source in the group-source field of MST and fills the
other fields of MST such as next-hop, hop-count and status
with the unicast routing table. next-hop is the next hop
towards the group member. hop-count is the distance from
group member to source by the number of hops. status
indicates the connectivity status for source in unicast
routing. The connected status is represented as 1 and
disconnected status is represented as 0. Of course, by the
change of unicast routing, the other fields of MST except
group-source are changed appropriately.
Step 2. Acknowledgement of the registration packet.
Member makes a UMR Control packet for acknowledging the
completion of the registration and sends it to the group
source in unicast. The Type field of UMR header contains
the same as that of the registration packet. The Code
field contains CODE_ACK. The List_of_Addresses field
contains the IP address of the member.
When the group source receives the acknowledgement packet for
registration, it registers the IP address of the member in the
group-member field of MMT. The other fields of MMT are filled
appropriately with the unicast routing table.
6.3 Leave of Multicast Group Member
When a multicast group member leaves multicast group, it multicasts
a control packet indicating the leave of multicast group member.
The destination field of IP header contains All-UMR-Routers address
Jeong, Park Expires December 2002 [Page 9]
INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002
with the list of addresses of multicast group sources in the UMR
header that are stored in MST.
The Type field of UMR header contains UMR_CONTROL_MEMBER_LEAVE. The
Code field of UMR header contains CODE_REQUEST.
When the packet arrives in the just previous MN of a multicast
group member, unlike a UMR multicast data packet of which the Type
field of UMR header contains UMR_DATA, the packet isn't converted
to a standard multicast packet and is converted to UMR unicast
packet(s) of which the destination field of IP header is the
address selected from the list of addresses contained in the
List_of_Addresses field of UMR header.
When a multicast group source receives the packet, the following
procedure is performed.
Step 1. Deletion of multicast group member in MMT.
The source deletes the entry in MMT that corresponds to
the IP address of the group member.
Step 2. Acknowledgement of the leave packet.
Source makes a UMR Control packet for acknowledging the
completion of the leave and sends it to the group member
in unicast. The Type field of UMR header contains the same
as that of the leave packet. The Code field contains
CODE_ACK. The List_of_Addresses field contains the IP
address of the source.
When the group member receives the acknowledgement packet for
leave, it deletes the entry in MST that corresponds to the IP
address of the source.
6.4 Leave of Multicast Group Source
When a multicast group source stops sending multicast data, it
multicasts a control packet indicating the leave of multicast group
source.
The destination field of IP header contains All-UMR-Routers address
with the list of addresses of multicast group members in the UMR
header that are stored in MMT.
The Type field of UMR header contains UMR_CONTROL_SOURCE_LEAVE.The
Code field of UMR header contains CODE_REQUEST.
When the packet arrives in the just previous MN of a multicast
group member, the packet is processed in the same way as Leave of
Multicast Group Member.
When a multicast group member receives the packet, the following
procedure is performed.
Jeong, Park Expires December 2002 [Page 10]
INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002
Step 1. Deletion of multicast group source in MST.
The member deletes the entry in MST that corresponds to
the IP address of the group source.
Step 2. Acknowledgement of the leave packet.
Member makes a UMR Control packet for acknowledging the
completion of the leave and sends it to the group source
in unicast. The Type field of UMR header contains the same
as that of the leave packet. The Code field contains
CODE_ACK. The List_of_Addresses field contains the IP
address of the member.
When the group source receives the acknowledgement packet for
leave, it deletes the entry in MMT that corresponds to the IP
address of the member. When the source becomes to receive the
acknowledgement from all the group members in MMT, it removes MMT.
7. Implementation Considerations
We should consider the checksum calculation in UDP and ICMP. We
should also consider the process of IGMP messages in order to use
the current multicast applications without modification.
8. IANA Considerations
All-UMR-Routers address and UMR protocol number should be defined
by IANA.
9. Security Considerations
Security issues related to the representative ad-hoc unicast
routing protocols such as AODV and DSR apply to the protocol
described here [AODV, DSR].
10. References
[RFC2119] S. Bradner, "Key words for use in RFCs to Indicate
Requirement Levels", RFC 2119, March 1997.
[MAODV] Elizabeth M. Royer and Charles E. Perkins, "Multicast
Ad hoc On-Demand Distance Vector (MAODV) Routing",
I-D draft-ietf-manet-maodv-00, July 2000.
[SIMPLE] Jorjeta G. Jetcheva et al., "A Simple Protocol for
Multicast and Broadcast in Mobile Ad Hoc Networks",
I-D draft-ietf-manet-simple-mcast-01, July 2001.
[XCAST] R. Boivie et al., "Explicit Multicast (Xcast) Basic
Specification", I-D draft-ooms-xcast-basic-spec-02,
October 2001.
[XCAST+] Myung-Ki Shin, Yong-Jin Kim and Sang-Ha Kim, "Explicit
Jeong, Park Expires December 2002 [Page 11]
INTERNET-DRAFT Unicast Routing based Multicast Routing June 2002
Multicast Extension (Xcast+) Supporting Receiver
Initiated Join", I-D draft-shin-xcast-receiver-join-01,
March 2002.
[AODV] Charles E. Perkins, Elizabeth M. Royer and Samir R. Das,
"Ad hoc On-Demand Distance Vector (AODV) Routing",
I-D draft-ietf-manet-aodv-10, January 2002.
[DSR] David B. Johnson et al., "The Dynamic Source Routing
Protocol for Mobile Ad Hoc Networks (DSR)",
I-D draft-ietf-manet-dsr-07.txt, February 2002.
Authors' Addresses
Jae-Hoon Jeong
ETRI / PEC
161 Gajong-Dong, Yusong-Gu
Daejon 305-350
Korea
Phone: +82 42 860 1664
EMail: paul@etri.re.kr
Jung-Soo Park
ETRI / PEC
161 Gajong-Dong, Yusong-Gu
Daejon 305-350
Korea
Phone: +82 42 860 6514
EMail: pjs@etri.re.kr
Expiration date: December 2002
Jeong, Park Expires December 2002 [Page 12]