[Docs] [txt|pdf] [Tracker] [Email] [Nits]

Versions: 00

SAM Research Group                                  Khoa T.P, Nam Thoai
Internet Draft                                                    HCMUT
Intended status: Experimental                     E.Muramoto, K.Ettikan
Expires: July 2009                                            Panasonic
                                                      February 20, 2009





                  Xcast6 Treemap: An extension of Xcast6
                draft-khoa-treemap-xcast6-extension-00.txt




Status of this Memo

   This Internet-Draft is submitted to IETF in full conformance with the
   provisions of BCP 78 and BCP 79.

   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

   This Internet-Draft will expire on July 20, 2009.

Copyright Notice

   Copyright (c) 2009 IETF Trust and the persons identified as the
   document authors. All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document. Please review these documents



Khoa et al.             Expires July 20, 2009                  [Page 1]


Internet-Draft              Xcast6 Treemap                February 2009


   carefully, as they describe your rights and restrictions with respect
   to this document.

Abstract

   Xcast6 (Explicit Multi-unicast for IPv6) is a new multicast scheme
   that supports very large number of small multicast sessions. Xcast6
   sends data via optimal route without traffic redundancy when Xcast-
   aware routers exist; otherwise, data will be sent in daisy-chain
   form. In this document, we propose Xcast6 Treemap - an extension of
   Xcast6. Using Xcast6 Treemap, data can be branched not only at source
   but also at remote hosts, solving the limitation of daisy-chain
   connection. Xcast6 Treemap utilizes existing multicast infrastructure
   (Xcast-aware routers) to improve application performance and reduce
   traffic redundancy on network; also, it automatically switches to
   end-host multicast operation mode in the absence of Xcast-aware
   router. For widely deployment of Xcast6, routers must be upgraded
   gradually. This requires a long term strategy and Xcast6 Treemap is a
   good choice for incremental deployment.

Table of Contents


   1. Introduction...................................................3
   2. Gradual Deployment of Xcast6...................................3
   3. Xcast6 Treemap - An extension of Xcast6........................5
      3.1. Motivation................................................5
      3.2. Routing path knowledge in packet header (Treemap).........7
      3.3. Xcast6 Treemap definition.................................9
         3.3.1. Treemap field.......................................10
         3.3.2. Libtmxcast..........................................10
   4. Operation of Xcast6 Treemap...................................11
      4.1. There is no Xcast-aware router...........................12
      4.2. There is one Xcast-aware router..........................13
      4.3. There are some Xcast routers.............................14
      4.4. There are enough Xcast-aware routers.....................14
   5. A brief comparison of Xcast6 Treemap and other multicast schemes16
      5.1. Xcast6 Treemap vs. Xcast6................................16
      5.2. Xcast6 Treemap vs. Application Layer Multicast (ALM).....16
      5.3. Xcast6 Treemap vs. IP Multicast..........................16
      5.4. Xcast6 Treemap vs. REUNITE...............................16
   6. Security Considerations.......................................18
   7. IANA Considerations...........................................18
   8. Conclusions...................................................18
   9. Acknowledgments...............................................19
   10. References...................................................19
      10.1. Normative References....................................19


Khoa et al              Expires July 20, 2009                  [Page 2]


Internet-Draft              Xcast6 Treemap                February 2009


      10.2. Informative References..................................19
   Author's Addresses...............................................21

1. Introduction

   Multicast is an efficient mechanism to reduce traffic redundancy on
   network. Therefore, it is a useful service for multi-party
   applications. However, IP multicast has difficulties in deployment on
   the Internet because it requires routers to be upgraded
   simultaneously. For this reason, many researchers have suggested to
   move multicast service to application level [3][5][6][8][10][13]. In
   Application Layer Multicast (ALM), instead of changing network
   infrastructure, forwarding function is implemented at end-hosts.
   Logically, in ALM, end-hosts form an overlay network and packets are
   replicated at end-hosts. That means with a suitable overlay route,
   ALM guarantees good quality for applications deployed on it. However,
   ALM cannot reduce traffic like IP Multicast.

   In Xcast6 [RFC5058], using gradual deployment mechanism, end-hosts
   perform forwarding function. Based on destination list in packet
   header, a host will find and send packets to the first undelivered
   node. That means data is only disseminated in daisy-chain form or
   ring multicast [2]. This mechanism ensures packets from root node to
   reach all nodes in group. Furthermore, traffic stress at root node is
   reduced in comparison with traditional unicast. However, daisy-chain
   form cannot send data in an efficient overlay route like ALM. Thus,
   it is necessary to have a new protocol which has combined properties
   of both ALM and Xcast6. This is the motivation of our research to
   propose Xcast6 Treemap. In Xcast6 Treemap, delivery routing tree is
   embedded in the packet header. This provides routing information for
   remote hosts to branch data when needed, solving the problem of
   daisy-chain connection.

2. Gradual Deployment of Xcast6

   Xcast6 can be deployed on network with non-Xcast-aware routers by
   applying tunneling techniques [RFC5058]. This enables the creation of
   a virtual network on top of an existing network [RFC2003]. By this
   way, packets will be tunneled through non-Xcast routers.

   For example: suppose that A tries to distribute packets to B, C, D, E
   and F as shown in Figure 1, where "X" is Xcast-aware router and "R"
   is not.






Khoa et al              Expires July 20, 2009                  [Page 3]


Internet-Draft              Xcast6 Treemap                February 2009


   +------------------------------------------------------------------+
   |                                                                  |
   |                          B       C             D                 |
   |                         /       /             /                  |
   |                        /       /             /                   |
   |               A ---- X1 ---- X2 --- R3 --- X4 --- E              |
   |                                              \                   |
   |                                               \                  |
   |                                                F                 |
   |                                                                  |
   +------------------------------------------------------------------+

                                 Figure 1

   In Figure 1, X1, X2 and X4 are Xcast-aware routers. The source A
   sends an Xcast6 packet which includes a list of destinations (B, C,
   D, E and F) in packet header to router X1. After receiving the
   packet, X1 will send that packet to B and one copy of the packet to
   X2. Similarly, when X2 receives the packet, it will send one copy of
   the packet to C and another copy of the packet to next hop R3 with
   destination address in the outer IP is D. This packet will be
   received by R3 as a unicast packet with destination D, and R3 will
   forward it on, having no knowledge of Xcast6. When X4 receives the
   packet, it will forward that packet as ordinary unicast packet to D,
   E and F. In summary, packets from A will be tunneled through normal
   router R3 and reach all nodes in group (B, C, D, E and F).

   In the special case, Xcast6 can be deployed on network without Xcast-
   aware router. By applying tunneling with one of the destinations as a
   tunnel endpoint, Xcast6 packet will be delivered to all destinations
   when all hosts are Xcast-aware.

   +------------------------------------------------------------------+
   |                                                                  |
   |                          B       C             D                 |
   |                         /       /             /                  |
   |                        /       /             /                   |
   |               A ---- R1 ---- R2 --- R3 --- R4 --- E              |
   |                                              \                   |
   |                                               \                  |
   |                                                F                 |
   |                                                                  |
   +------------------------------------------------------------------+

                                 Figure 2




Khoa et al              Expires July 20, 2009                  [Page 4]


Internet-Draft              Xcast6 Treemap                February 2009


   The network as shown in Figure 2 has no Xcast-aware router. When
   source node A sends data to (B, C, D, E and F), A will create packets
   with destination list in the packet header is (B, C, D, E, F). One of
   destinations will be put in outer IP header (Figure 3).

   +-------------------------------------------------------------------+
   |                          +----------+                             |
   |                          | payload  |                             |
   |                          +----------+                             |
   |                          |   UDP    |                             |
   |                          +----------+                             |
   |                          |  Xcast   |                             |
   |                          +----------+                             |
   |                          | inner IP |                             |
   |                          |  src=A   |                             |
   |                          |dst=All_X_|                             |
   |                          |prot=Xcast|                             |
   |                          +----------+                             |
   |                          |  Xcast   |                             |
   |                          |SP-tunnel |                             |
   |                          |Hop-by-Hop|                             |
   |                          +----------+                             |
   |                          | outer IP |                             |
   |                          |  src=A   |                             |
   |                          |  dst=B   |                             |
   |                          | prot=IP  |                             |
   |                          +----------+                             |
   +-------------------------------------------------------------------+

                                 Figure 3

   Because there is no Xcast-aware router, packets will travel through
   R1 and come to B as normal IPv6 packets. When node B receives a
   packet, it duplicates packet and changes the outer IP which "src = B"
   and "dst = C" before forwarding. This process is repeated so that
   packets are delivered to all nodes as normal unicast packet.
   Obviously, data is always sent in a daisy-chain of A-B-C-D-E-F. This
   causes long latency and unreliable quality for applications deployed
   on it.

3. Xcast6 Treemap - An extension of Xcast6

3.1. Motivation

   In Xcast6, when a node sends packets to group, list of destinations
   will be added to packet header. When there are Xcast-aware routers,
   packets will be replicated and forwarded at routers in optimal route.


Khoa et al              Expires July 20, 2009                  [Page 5]


Internet-Draft              Xcast6 Treemap                February 2009


   However, in the absence of Xcast-aware router, hosts will forward
   packets. Because there is no information for an end host to forward
   packet to more than one next destination, packet will only be
   delivered in daisy-chain form. This ensures data to reach all hosts
   in group but it cannot make data to be sent in efficient overlay
   route.

   For example: suppose that A tries to distribute packets to B, C D and
   E as shown in Figure 4:

   +------------------------------------------------------------------+
   |                                                                  |
   |                             B        D                           |
   |                            /        /                            |
   |                           /        /                             |
   |                   A ---- R1 ---- R2                              |
   |                           \        \                             |
   |                            \        \                            |
   |                             C        E                           |
   |                                                                  |
   |                                                                  |
   +------------------------------------------------------------------+

                                 Figure 4

   Assuming that the network is shown in Figure 4 has no Xcast-aware
   router. R1 and R2 are normal routers. In reality, we do not know the
   network topology, so we hide it as a rectangle "NETWORK" (Figure 5).
   Available upload and download capacity of each node are shown in
   Figure 6.

   +------------------------------------------------------------------+
   |                                                                  |
   |                           +---------+                            |
   |                           |         |---- B                      |
   |                           |         |                            |
   |                           |         |---- C                      |
   |                     A ----| NETWORK |                            |
   |                           |         |---- D                      |
   |                           |         |                            |
   |                           |         |---- E                      |
   |                           +---------+                            |
   |                                                                  |
   +------------------------------------------------------------------+

                                 Figure 5



Khoa et al              Expires July 20, 2009                  [Page 6]


Internet-Draft              Xcast6 Treemap                February 2009


   +------------------------------------------------------------------+
   |                                                                  |
   |                      +-------+--------+---------+                |
   |                      | Node  | Upload | Download|                |
   |                      +-------+--------+---------+                |
   |                      |   A   | 1Mbps  |  1Mbps  |                |
   |                      +-------+--------+---------+                |
   |                      |   B   | 3Mbps  |  3Mbps  |                |
   |                      +-------+--------+---------+                |
   |                      |   C   | 512Kbps|  1Mbps  |                |
   |                      +-------+--------+---------+                |
   |                      |   D   | 1Mbps  |  1Mbps  |                |
   |                      +-------+--------+---------+                |
   |                      |   E   | 1Mbps  |  1Mbps  |                |
   |                      +-------+--------+---------+                |
   |                                                                  |
   +------------------------------------------------------------------+

                                 Figure 6

   With the network in Figure 5, data is transferred as a chain of A-B-
   C-D-E. This is not always a suitable route. For example: when node A
   sends a stream at 512Kbps to B, C, D and E, each node in group will
   receive data at 512Kbps. But when sending rate at node A is increased
   to 1Mbps, only B and C receive stream at 1 Mbps. When C receives data
   from B, because of limited available upload bandwidth, C will forward
   data to D only at 512Kbps. After that, D will forward data to E at
   512Kbps. In this case, because node B has large available upload
   bandwidth, a suitable route can be A-B, B-C, B-D and B-E. That means
   data need to be branched at node B.

   In Xcast, there is no routing information for host, therefore even
   though when we know what a good overlay route is, we cannot tell
   Xcast hosts to transfer data on that route. In next section, we
   propose a technique called "routing path knowledge in packet header"
   (or Treemap) that can be used as an extension for Xcast6 to solve the
   problem of daisy-chain connection.

3.2. Routing path knowledge in packet header (Treemap)

   There are many ways to represent a tree structure [7][11]. The
   technique that uses two arrays: one is to store information
   associated with each node and the other is to hold the parent links
   [11] seems applicable for storing routing tree in packet header. For
   example: to represent a tree like Figure 7, the two arrays that need
   to be used as shown in Figure 8.



Khoa et al              Expires July 20, 2009                  [Page 7]


Internet-Draft              Xcast6 Treemap                February 2009


   +------------------------------------------------------------------+
   |                                                                  |
   |                               A                                  |
   |                               |                                  |
   |                               |                                  |
   |                               B                                  |
   |                              / \                                 |
   |                             /   \                                |
   |                            C     D                               |
   |                                 / \                              |
   |                                /   \                             |
   |                               E     F                            |
   |                                                                  |
   +------------------------------------------------------------------+

                                 Figure 7

   +------------------------------------------------------------------+
   |                                                                  |
   |              index     0   1   2   3   4   5                     |
   |                      +-----------------------+                   |
   |              array1  | A | B | C | D | E | F |                   |
   |                      +-----------------------+                   |
   |                      +-----------------------+                   |
   |              array2  |-1 | 0 | 1 | 1 | 3 | 3 |                   |
   |                      +-----------------------+                   |
   |                                                                  |
   +------------------------------------------------------------------+

                                 Figure 8

   In array2, node A has value "-1", this means A is the root node. Node
   B has value "0" and node A has index "0", meaning B is child node of
   A. Similarly, using two arrays, one is to store IP address and the
   other is to hold parent index, routing tree can be embedded in packet
   header. In our case, when a node receives a packet, this node needs
   to traverse the routing tree to find children nodes to forward
   packet. However, this tree representation is not suitable for top-
   down traverse [4]. For example, when node C receives a packet, it
   needs to check entire "array2" to know that it has no child. This is
   a waste of time for unnecessary check. In this document, we propose a
   tree representation that occupies small space and suitable with top-
   down traverse strategy. This representation consists of two arrays:
   "list of dests" and "Treemap". With the same routing tree in Figure
   7, the structure of "Treemap" is shown in Figure 9. And Figure 10
   illustrates the logic of routing tree (Figure 7) relates to the
   Treemap (Figure 9).


Khoa et al              Expires July 20, 2009                  [Page 8]


Internet-Draft              Xcast6 Treemap                February 2009


   +------------------------------------------------------------------+
   |                                                                  |
   |                                                                  |
   |                 List of dests          Treemap                   |
   |            +------------------+------------------+               |
   |            | A  B  C  D  E  F | 1  2  0  2  0  0 |               |
   |            +------------------+------------------+               |
   |                                                                  |
   |                                                                  |
   +------------------------------------------------------------------+

                                 Figure 9

   +------------------------------------------------------------------+
   |                                                                  |
   |                          A -------> 1                            |
   |                                                                  |
   |                          B -------> 2                            |
   |                                                                  |
   |                          C -------> 0                            |
   |                                                                  |
   |                          D -------> 2                            |
   |                                                                  |
   |                          E -------> 0                            |
   |                                                                  |
   |                          F -------> 0                            |
   |                                                                  |
   +------------------------------------------------------------------+

                                 Figure 10

   Based on routing tree, "List of dests" is a list of node in width
   first order. Similarly, "Treemap" is a list of number children for
   each node in width first order. As shown in Figure 10, node A has one
   child is node B. Node B and D each has two children are C, D and E, F
   respectively. Nodes C, E and F have no child. When a node receives a
   packet, based on the "Treemap" in packet header, node can decide
   which nodes to forward the packet.

3.3. Xcast6 Treemap definition

   In Xcast6, when a node sends data to a group, it must store
   destination IP addresses of all nodes in packet header. That means,
   to apply "Treemap" to Xcast6, we just occupy small additional space
   in Xcast6 header for Treemap field.




Khoa et al              Expires July 20, 2009                  [Page 9]


Internet-Draft              Xcast6 Treemap                February 2009


  3.3.1. Treemap field

   Because Treemap field is only referred by hosts, it is implemented as
   Destination Options header with "Opt Type=Treemap" (Figure 11).

   +-------------------------------------------------------------------+
   |                                                                   |
   | 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 2 |
   | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
   | |  Next header  |   HdrExtLen   |Opt Type=Treemap | Opt Data Len| |
   | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
   | |                           Treemap                             | |
   | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
   |                                                                   |
   +-------------------------------------------------------------------+

                                 Figure 11

   In the overlay route, to prevent a node from accepting too many
   children, each node should be configured with a maximum degree
   constraint. In our work, each node will occupy 4 bits in Treemap
   field. That means we define maximum degree constraint is 15, and
   Treemap field has a fixed length of 32 bytes for maximum of 64 nodes
   in a multicast session.

  3.3.2. Libtmxcast

   In the original Xcast6, before sending data, root node must add
   Xcast6 header into packet. This is done by libxcast - a library which
   provides functions for programmers. Some important functions in
   libxcast are:

   int XcastCreateGroup(int flags, struct sockaddr *src, unsigned short
   maxmbrs): creates Xcast6 group.

   int XcastAddMember(int groupid, struct xcast_member *member): adds
   members to Xcast6 group.

   int XcastSend(int groupid, char *datap, int datalen): sends data to
   all nodes in group.

   In Xcast6 Treemap, after creating and adding members to xcast group,
   "Treemap" must be added to packet header. Therefore, we implement
   "libtmxcast" - an extension of "libxcast". Compared to "libxcast",
   "libtmxcast" has more functions for adding "Treemap" and sending data
   as overlay route defined in "Treemap":


Khoa et al              Expires July 20, 2009                 [Page 10]


Internet-Draft              Xcast6 Treemap                February 2009


   int AddTree(int groupid, OverlayRoute *pOverlayRoute): adds members
   to Xcast group and adds the overlay route to packet header.

   groupid: id of group created by XcastCreateGroup().

   OverlayRoute is a struct which includes two elements: a list of
   destination nodes in width first order and a list of number children
   for each node in width first order.

   int XcastTreemapSend(int treeId, char *datap, int datalen): sends
   data to all nodes in Xcast6 group as routing tree in Treemap.

   treeId: id of the tree that was created by AddTree() function.

   datap and datalen: data and length that need to be transmitted.

4. Operation of Xcast6 Treemap

   As discussed earlier, Xcast6 Treemap sends data as overlay route
   defined in Treemap when there is no Xcast router. However, how does
   Xcast6 Treemap operate in network with both normal routers and Xcast-
   aware routers? In this Section, we give four examples to show the
   complete operation of Xcast6 Treemap.

   In the first example, Xcast6 Treemap sends data in ALM operation mode
   in the absence of Xcast router. The next two examples show the
   operation of Xcast6 Treemap when there are not enough Xcast routers
   on end-to-end. In the last example, Xcast6 Treemap switches to
   original Xcast6 operation mode when there are enough Xcast routers.
   These examples use network topology with 6 hosts and 4 routers as
   shown in Figure 12

   +------------------------------------------------------------------+
   |                                                                  |
   |                          B       C             D                 |
   |                         /       /             /                  |
   |                        /       /             /                   |
   |               A ---- R1 ---- R2 --- R3 --- R4 --- E              |
   |                                              \                   |
   |                                               \                  |
   |                                                F                 |
   |                                                                  |
   +------------------------------------------------------------------+

                                 Figure 12




Khoa et al              Expires July 20, 2009                 [Page 11]


Internet-Draft              Xcast6 Treemap                February 2009


   Assuming that node A sends data to group (B, C, D, E and F) with
   overlay route is shown in Figure 13

   +------------------------------------------------------------------+
   |                                                                  |
   |                               A                                  |
   |                               |                                  |
   |                               |                                  |
   |                               B                                  |
   |                              / \                                 |
   |                             /   \                                |
   |                            C     D                               |
   |                                 / \                              |
   |                                /   \                             |
   |                               E     F                            |
   |                                                                  |
   +------------------------------------------------------------------+

                                 Figure 13

   When A sends data to group, it will create packets with header as
   follows:

   [src=A|dest=(B C D E F)|bitmap = (1 1 1 1 1)|treemap = (2 0 2 0 0)]

   Now, we consider behavior of Xcast6 Treemap with and without the
   support of Xcast routers.

4.1. There is no Xcast-aware router

   Suppose that there is no Xcast-aware router on end-to-end. In Figure
   12, R1, R2, R3 and R4 are normal routers. In this case, packets from
   A go through R1 and come to B as normal unicast packet. When node B
   receives packets, B checks bitmap, treemap, and forwards these
   packets to C and D respectively:

   [src=A| dest=(B C D E F)| bitmap=(0 1 0 0 0)| treemap=(2 0 2 0 0)]

   [src=A| dest=(B C D E F)| bitmap=(0 0 1 1 1)| treemap=(2 0 2 0 0)]

   When C receives packets, C checks bitmap and does not forward these
   packets. Meanwhile, when D receives packets, based on bitmap and
   Treemap, D will duplicate and send these packets to E and F:

   [src=A| dest=(B C D E F)| bitmap=(0 0 0 1 0)| treemap=(2 0 2 0 0)]

   [src=A| dest=(B C D E F)| bitmap=(0 0 0 0 1)| treemap=(2 0 2 0 0)]


Khoa et al              Expires July 20, 2009                 [Page 12]


Internet-Draft              Xcast6 Treemap                February 2009


   When E and F receive packets, they check bitmap and do not forward
   these packets. Obviously, data from A is sent to all nodes as the
   overlay route defined in Treemap, solving daisy-chain problem of
   original Xcast6.

4.2. There is one Xcast-aware router

   Suppose that in Figure 12, R1 is now upgraded to Xcast aware router
   (Figure 14).

   +------------------------------------------------------------------+
   |                                                                  |
   |                          B       C             D                 |
   |                         /       /             /                  |
   |                        /       /             /                   |
   |               A ---- X1 ---- R2 --- R3 --- R4 --- E              |
   |                                              \                   |
   |                                               \                  |
   |                                                F                 |
   |                                                                  |
   +------------------------------------------------------------------+

                                 Figure 14

   When X1 receives packets from A, X1 will check bitmap (router does
   not check Treemap) and forward packets to B and C respectively:

   [src=A|dest=(B C D E F)|bitmap=(1 0 0 0 0)|treemap=(2 0 2 0 0)]

   [src=A|dest=(B C D E F)|bitmap=(0 1 1 1 1)|treemap=(2 0 2 0 0)]

   When B receives packets, base on Treemap, B has two children but
   based on bitmap, B will not forward data. When C receives packets, C
   checks Treemap and sees that it has no child. However, based on
   bitmap, there are some nodes that have not received packet yet.
   Therefore, to ensure data to reach all nodes in group, C will forward
   packet to both its children node and the first undelivered node in
   destination list. In this case, because C has no child, so C only
   forwards packets to node D (the first undelivered node in destination
   list):

   [src=A|dest=(B C D E F)|bitmap=(0 0 1 1 1)|treemap=(2 0 2 0 0)]

   When D receives packets, based on bitmap and treemap, packets will be
   forwarded to E and F.




Khoa et al              Expires July 20, 2009                 [Page 13]


Internet-Draft              Xcast6 Treemap                February 2009


   With only one Xcast-aware router, packet from A to B and C will be
   delivered via optimal route like Xcast6. Packets from D to E and F
   are sent in overlay route. However, because of limited number of
   Xcast router, C will forward packets directly to D like daisy-chain
   form.

4.3. There are some Xcast routers

   Assuming that in Figure 12, R1 and R2 are now changed to Xcast
   routers (X1 and X2). R3 and R4 are normal routers. When X1 receives a
   packet, it will check the bitmap and forward that packet to B and
   next hop X2 respectively as following:

   [src=A|dest=(B C D E F)|bitmap=(1 0 0 0 0)|treemap=(2 0 2 0 0)]

   [src=A|dest=(B C D E F)|bitmap=(0 1 1 1 1)|treemap=(2 0 2 0 0)]

   When X2 receives the packet, it also checks bitmap, then forwards
   packet to C and D:

   [src=A|dest=(B C D E F)|bitmap=(0 1 0 0 0)|treemap=(2 0 2 0 0)]

   [src=A|dest=(B C D E F)|bitmap=(0 0 1 1 1)|treemap=(2 0 2 0 0)]

   When D receives the packet, it checks bitmap, Treemap and forwards
   that packet to E and F.

   In this case, data is transferred like a hybrid of Xcast6 and ALM.
   Packets from A to B, C and D are transferred in optimal route because
   there are Xcast-aware routers. Otherwise, without the support of
   Xcast router, packets from D are delivered to E and F in ALM route.

4.4. There are enough Xcast-aware routers

   The network in Figure 12 is now changed with R1, R2 and R4 are Xcast-
   aware routers, R3 is normal router (Figure 15). Note that for this
   network topology, R1, R2 and R4 are Xcast-aware routers and it is
   enough, R3 does not need to be upgraded.











Khoa et al              Expires July 20, 2009                 [Page 14]


Internet-Draft              Xcast6 Treemap                February 2009


   +------------------------------------------------------------------+
   |                                                                  |
   |                          B       C             D                 |
   |                         /       /             /                  |
   |                        /       /             /                   |
   |               A ---- X1 ---- X2 --- R3 --- X4 --- E              |
   |                                              \                   |
   |                                               \                  |
   |                                                F                 |
   |                                                                  |
   +------------------------------------------------------------------+

                                 Figure 15

   When X1 receives a packet, X1 will check bitmap and forward this
   packet to B and next hop X2 as follows:

   [src=A|dest=(B C D E F)|bitmap=(1 0 0 0 0)|treemap=(2 0 2 0 0)]

   [src=A|dest=(B C D E F)|bitmap=(0 1 1 1 1)|treemap=(2 0 2 0 0)]

   When X2 receives packet, based on bitmap, X2 will forward packet to C
   and next hop R3:

   [src=A|dest=(B C D E F)|bitmap=(0 1 0 0 0)|treemap=(2 0 2 0 0)]

   [src=A|dest=(B C D E F)|bitmap=(0 0 1 1 1)|treemap=(2 0 2 0 0)]

   R3 is non-Xcast-aware router, thus when R3 receives a packet, it will
   forward this packet as normal IPv6 packet to X4. Finally, when X4
   receives packet, X4 will forward this packet respectively to D, E and
   F:

   [src=A|dest=(B C D E F)|bitmap=(0 0 1 0 0)|treemap=(2 0 2 0 0)]

   [src=A|dest=(B C D E F)|bitmap=(0 0 0 1 0)|treemap=(2 0 2 0 0)]

   [src=A|dest=(B C D E F)|bitmap=(0 0 0 0 1)|treemap=(2 0 2 0 0)]

   In this case, X1, X2 and X4 will duplicate and forward packets like
   the original Xcast6. That means data will be transferred in optimal
   route without traffic redundancy on network.







Khoa et al              Expires July 20, 2009                 [Page 15]


Internet-Draft              Xcast6 Treemap                February 2009


5. A brief comparison of Xcast6 Treemap and other multicast schemes

5.1. Xcast6 Treemap vs. Xcast6

   Xcast6 Treemap is inherited from Xcast6, thus it has all properties
   of Xcast6. Compared to Xcast6, Xcast6 Treemap has longer header, and
   it needs more time for handling packet. However, Xcast6 Treemap
   supports ALM when lack of Xcast-aware router. Therefore, with
   suitable routing tree, Xcast6 Treemap will transfer data more
   efficient than Xcast6 in the absence of Xcast-aware router. For
   widely deployment of Xcast6, routers must be upgraded. This needs a
   long term strategy, and Xcast6 Treemap is a good choice for gradual
   deployment.

5.2. Xcast6 Treemap vs. Application Layer Multicast (ALM)

   Both Xcast6 Treemap and ALM can send data in a given overlay route.
   In the absence of Xcast6 router, Xcast6 Treemap causes more traffic
   stress in comparison with ALM due to longer packet header length [9].
   However, the traffic stress will reduce when Xcast6 routers exist.
   Furthermore, with the advantage in fast routing convergence, Xcast6
   Treemap is suitable for real time applications such as video
   conference [9].

5.3. Xcast6 Treemap vs. IP Multicast

   Xcast6 Treemap has all properties of Xcast6. There are two main
   advantages of Xcast6 Treemap in comparison with IP Multicast.
   Firstly, IP Multicast does not have incremental deployment mechanism,
   all routers on end-to-end must support multicast. Meanwhile, Xcast6
   Treemap is good at gradual deployment because it supports ALM in the
   absence of Xcast-aware router. Secondly, in IP Multicast, routers
   must store forwarding state per multicast group, which means it does
   not scale well with a very large number of groups. In Xcast6 Treemap,
   inheriting from Xcast6, routers do not store forwarding state per
   group basis, thus it scales very well with large number of multicast
   sessions. The main limitation of Xcast6 Treemap is that it only
   supports multicast sessions with small size.

5.4. Xcast6 Treemap vs. REUNITE

   REUNITE [12] - a new multicast scheme was proposed to alleviate the
   problems of IP Multicast. REUNITE helps to reduce forwarding states
   at router, thus enhances scalability with large number of multicast
   groups. Xcast6 Treemap has some comparative properties to REUNITE:




Khoa et al              Expires July 20, 2009                 [Page 16]


Internet-Draft              Xcast6 Treemap                February 2009


   - REUNITE enhances scalability by reducing forwarding state at
     routers. Xcast6 Treemap inherits from Xcast6 with no state per
     session at router. This property make Xcast6 Treemap scale better
     with large number of small multicast sessions.

   - REUNITE has native support for incremental deployment. However,
     without the support from routers, REUNITE sends data like unicast
     while Xcast6 Treemap works in ALM mode (it is possible for data to
     be branched not only at source but also at remote host).
     Therefore, Xcast6 Treemap is better than REUNITE in gradual
     deployment.

   - Both REUNITE and Xcast6 Treemap use unicast address, not necessary
     for class D IP address. Therefore, they can support large number
     of simultaneously active multicast sessions.

   - REUNITE has mechanism for load balancing and graceful degradation.
     Xcast6 Treemap does not need this mechanism because there is no
     session state in Xcast-aware router.

   - Both REUNITE and Xcast6 Treemap can support access control by
     authenticating sender at root node.

   - Beside many desirable properties, REUNITE also introduces some
     dynamic behaviors. For example: tree restructuring due to member
     departure, race condition of join and duplicate packets during
     tree restructuring [12]. In Xcast6 Treemap, the membership
     management can be defined as a completely separate mechanism. When
     members join/leave, the source node will be notified to update
     routing path (Treemap) in the packet header. Xcast6 router and
     Xcast6 Treemap capable host do not keep any state at all. They
     just follow the knowledge in the packet header. It means dynamic
     member join/leave does not affect routing mechanism itself.

   - REUNITE has a problem called "Source address spoofing and Ingress
     Filtering". It is because when router duplicates packet, it will
     rewrite destination address but keep source address unchanged.
     Unlike REUNITE, Xcast6 Treemap does not face this kind of problem
     because source address in outer IP is changed.

   - REUNITE uses asymmetric unicast routes to build tree. In some
     cases, it cannot give optimize route. For example:







Khoa et al              Expires July 20, 2009                 [Page 17]


Internet-Draft              Xcast6 Treemap                February 2009


   +------------------------------------------------------------------+
   |                                                                  |
   |                               S                                  |
   |                              / \                                 |
   |                             /   \                                |
   |                            R1    \                               |
   |                           / \    R4                              |
   |                          /   \   |                               |
   |                         R2   R3  |                               |
   |                          \   / \ |                               |
   |                           \ /   \|                               |
   |                            A     B                               |
   |                                                                  |
   +------------------------------------------------------------------+

                                 Figure 16

   Assuming that in Figure 16, asymmetric unicast routes are: S-R1-R3-A,
   A-R2-R1-S, S-R1-R3-B, B-R4-S. When node A joins, it receives data
   from S as route: S-R1-R3-A. After that, when node B joins; data from
   S to A and B will be transferred in route S-R1-R3-A and S-R1-R3-B. In
   this case, although R1, R2, R3 and R4 are REUNITE routers, S still
   delivers data to A, B in unicast route. That means asymmetric unicast
   route may affect the performance of REUNITE. Xcast6 Treemap uses IP
   forwarding table to forward data, therefore it does not face up this
   problem and data from source to destinations is sent in optimal route
   without traffic redundancy.

6. Security Considerations

   Xcast6 Treemap is an extension of Xcast6. Security considerations can
   be same as Xcast6 [RFC5058]. Additional security problem is not found
   currently.

7. IANA Considerations

   Xcast6 Treemap requires the use of protocol numbers maintained by
   IANA. In Destination Options header, we defined "Opt Type = Treemap".
   This Treemap number should be assigned by IANA.

8. Conclusions

   Multicast is an efficient mechanism for multi-party applications.
   Compared to ALM, IP Multicast is better in saving bandwidth, but it
   has more difficulty in deployment. For this reason, in spite of
   smaller benefit, industry has tended to choose ALM with replicated
   unicast [RFC5218]. Xcast6 is a new multicast scheme that suitable for


Khoa et al              Expires July 20, 2009                 [Page 18]


Internet-Draft              Xcast6 Treemap                February 2009


   very large number of small multicast sessions. Xcast6 is easier to
   deploy than IP Multicast because it has gradual deployment mechanism.
   However, in the absence of Xcast-aware router, Xcast6 does not work
   as efficient as ALM. In Xcast6 Treemap - an extension of Xcast6, data
   can be sent in ALM mode when lacking of Xcast routers, otherwise, it
   will automatically switch to original Xcast6 operation mode. The more
   Xcast routers are deployed, the more traffic redundancy is reduced.
   Xcast6 Treemap could be a good protocol for small group applications.

9. Acknowledgments

   The authors would like to thank Harunobu Mizuno, Masaaki Hoshida,
   Yoshio Yasumoto, Masayuki Orihashi, Taisuke Matsumoto, Yasuyuki
   Shintani, Yuji Imai, Takahiro Kurosawa, Dao Duy Binh, Nguyen Hoang
   Phong, Le Van Truong Quy, Pham Hong Cuong and Thuan Tran Ngoc for
   their advice and support.

   This document was prepared using 2-Word-v2.0.template.dot.

10. References

   10.1. Normative References

   [RFC2003] Perkins, C., "IP Encapsulation within IP", RFC 2003,
             October 1996

   [RFC5058] R. Boivie, N. Feldman, Y. Imai, W. Livens, D. Ooms, O.
             Paridaens, "Explicit Multicast (Xcast) Concepts and
             Options", RFC 5058, November 2007.

   [RFC5218] D. Thaler, B. Aboba, "What Make for a Successful Protocol?"
             RFC5218, July 2008.

   10.2. Informative References

   [1]   Cristina Abad, William Yurcik and R. H. Campbell. A Survey and
         Comparison of End-System Overlay Multicast Solutions Suitable
         for Network-Centric Warfare. SPIE Defense and Security
         Symposium/BattleSpace Digitization and Network-Centric Systems
         IV, 2004.

   [2]   S. Banerjee and B. Bhattacharjee. A Comparative Study of
         Application Layer Multicast Protocol






Khoa et al              Expires July 20, 2009                 [Page 19]


Internet-Draft              Xcast6 Treemap                February 2009


   [3]   S. Banerjee and B. Bhattacharjee. Analysis of the NICE -
         Application Layer Multicast Protocol. Technical report, UMIACS-
         TR2002-60 and CS-R4380, Department of Computer Science,
         University of Maryland, College Park, June2002.

   [4]   Boyko B. Bantchev. Representing Trees. In Proc. 36th Spring
         Conf. of the Union of Bulgarian Mathematicians, Varna, April
         2007, pp.193-196.

   [5]   Y.-H. Chu, S. G. Rao, and H. Zhang. A Case for End System
         Multicast. In Proceedings of ACM SIGMETRICS, June2000.

   [6]   P. Francis. Yoid: Extending the Multicast Internet
         Architecture, 1999. White paper http://www.aciri.org/yoid/.

   [7]   Donald E. Knuth. "The Art of Computer Programming", Third
         Edition, Chapter 2.

   [8]   D. Pendarakis, S. Shi, D. Verma, and M. Waldvogel. ALMI: An
         Application Level Multicast Infrastructure. In Proceedings of
         3rd Usenix Symposium on Internet Technologies and Systems,
         March 2001.

   [9]   Khoa Truong Phan, Nam Thoai, Eiichi Muramoto, Khanh Duy Banh,
         Ettikan K Karuppiah, Lim Boon Ping, Yew TP. Xcast6 Treemap - A
         hybrid approach of Xcast6 and Application Layer Multicast.
         (submitted)

   [10]  Lim Boon Ping, Ettikan K Karuppiah, Truong Khoa Phan, Lin En
         Shu, Nam Thoai, Eiichi Muramoto, Yew TP. Bandwidth Fair
         Application Layer Multicast for Multi-party Video Conference
         Application. 6th Annual IEEE Consumer Communications &
         Networking Conference (CCNC), January 2009.

   [11]  Robert Sedgewick. "Algorithms", Second Edition, Chapter 4.

   [12]  I. Stoica, T.S.E Ng, H. Zhan. REUNITE: a recursive unicast
         approach to multicast. In Proc. of IEEE INFOCOM 2000.

   [13]  B.Zhang, S.Jamin, and L.Zhang. Host multicast: A framework for
         delivering multicast to end users. In Proceedings of IEEE
         Infocom, June 2002.







Khoa et al              Expires July 20, 2009                 [Page 20]


Internet-Draft              Xcast6 Treemap                February 2009


Authors' Addresses

   Khoa Truong Phan
   Ho Chi Minh city University of Technology
   268 Ly Thuong Kiet
   District 10, Ho Chi Minh city
   Vietnam

   Email: khoaphan@cse.hcmut.edu.vn


   Nam Thoai
   Ho Chi Minh city University of Technology
   268 Ly Thuong Kiet
   District 10, Ho Chi Minh city
   Vietnam

   Email: nam@cse.hcmut.edu.vn


   Eiichi Muramoto
   Immersive Communication Task Force of Panasonic Corporation
   4-12-4 Higashi-shinagawa
   Shinagawa-ku, Tokyo
   Japan

   Email: muramoto.eiichi@jp.panasonic.com


   Ettikan Kandasamy
   Panasonic R&D Centre Malaysia Sdn.Bhd
   Penthouse Suite Level 4, Quill Building 3, 3501 Jalan Teknokrat 5
   63000 Cyberjaya, Selangor
   Malaysia

   Email: ettikank.k@my.panasonic.com












Khoa et al              Expires July 20, 2009                 [Page 21]


Html markup produced by rfcmarkup 1.129b, available from https://tools.ietf.org/tools/rfcmarkup/