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]