INTERNET DRAFT Kamil Sarac, UCSB December 2001 Kevin C. Almeroth, UCSB Expiration Date: May 2002 Tracetree: A Utility to Discover Multicast Tree Topology in the Network draft-sarac-tracetree-00.txt Status of this Memo This document is an Internet-Draft and is subject to all provisions of Section 10 of RFC2026. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet Drafts. Internet Drafts are draft documents valid for a maximum of six months. Internet Drafts may be updated, replaced, or made obsolete by other documents at any time. It is not appropriate to use Internet Drafts as reference material or to cite them other than as a "working draft" or "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. Copyright Notice Copyright (C) The Internet Society (2001). All Rights Reserved. Abstract This document describes a new mechanism for discovering multicast tree topology in the network. It uses the existing multicast forwarding state information to discovery tree topology in the source-to-receiver(s) direction. Scalability is provided by using a modified version of standard TTL based scoping. This draft identifies important issues necessary for discovering tree topology in the source-to-receiver(s) direction and discusses potential solutions to handle them. Sarac, Almeroth [Page 1] draft-sarac-tracetree-00.txt December 2001 1. Introduction Discovering multicast tree topology in the network has various uses such as in multicast network management, in multicast congestion control protocols, and in discovering network characteristics, etc. Currently this information can be obtained by using multicast routing information in the network. That is, the multicast path information between each group receiver and group source is traced using multicast routing information in the network (using multicast traceroute [1]). This information can then be used to create a map of the multicast tree topology. This approach requires knowing identities of group receivers and is considered to be unscalable. In this draft, we present an alternative approach to discover multicast tree topology in an efficient and scalable way[2]. We call our approach tracetree. In tracetree, the existing multicast forwarding state information in the network is used to discover multicast tree topology in the source-to-receiver(s) direction. Previously, this approach has been considered impractical due to scoping difficulties and its many-to-one communication requirements. In this draft, we explore these issues. We identify the potential problems and propose solutions. We see tracetree as orthogonal to the multicast traceroute (mtrace) tool and believe that the existing mtrace code in routers can be extended to support tree topology discovery functionality. 2. Overview Our general approach is to discover tree topology in the source-to-receiver(s) direction. This approach depends on the ability to send tracetree requests to a multicast group address and have routers recognize and respond to these requests. Since request packets are destined to a multicast group address, we need a mechanism for on-tree routers to distinguish tracetree request packets from the regular data packets in the group. For this we use the IP Router Alert option [3] in the tracetree request packets. This option enables routers to recognize the tracetree request packets and process them. When a querier Q wants to discover the multicast tree topology for a source/group (S,G), it sends a tracetree query message to the first hop router (FHR) at the session source site S. On receiving this query message, FHR creates a response packet and sends it back to the querier Q. In addition, the FHR creates a tracetree request packet and forwards it to the session multicast address G. In forwarding the request, the FHR spoofs the IP address of the session source S and uses it as the IP source for the request packet. This prevents on-tree routers from creating new forwarding state for FHR as a new source in the session which may not even be possible for some multicast routing protocols. In addition, the FHR puts its own IP address as the request forwarder and the IP address of the querier Q as the response Sarac, Almeroth [Page 2] draft-sarac-tracetree-00.txt December 2001 destination into the tracetree protocol header fields. Lastly, FHR sets the IP Router Alert option so that routers receiving this request packet recognize and process it. Each on-tree router, upon receiving a request packet: (1) sends its own response back to the querier and (2) forwards the request packet out on each interface belonging to the tree as long as the scope of the packet allows. During this process, querier node Q collects the incoming response messages to create a representations of the multicast tree topology for the group (S,G). 3. Topology Discovery Issues There are a number of issues that need to be considered for proper tracetree operation. We discuss these issues below. 3.1 Scalability In tracetree, a given query message results in a potentially large number of responses going towards the querier site. If not controlled, these responses may cause an implosion problem at the querier site. In order to control the number of responses going back to the querier, we divide the topology discovery process into "rounds" and discover only a controlled portion of the multicast tree in a round. In each round, we control the number of responses going back to the querier by limiting the number of routers receiving a copy of a tracetree request packet by using a modified-TTL-based scoping. That is, the scope of request packets is controlled using a modified IP TTL value. Routers use a different computation in decrementing this modified TTL value. In this computation, routers use the number of outgoing interfaces that each has for the multicast tree. (In this document, we use the term "outgoing interface" to mean outgoing interfaces on the multicast tree.) This value is used to compute the IP TTL value, TTL_new, for the request packet that they forward on their outgoing interfaces: TTL_current - 1 TTL_new = ---------------. num_neighbor In this computation, TTL_current is the IP TTL value in the incoming tracetree request packet and num_neighbor is the number of outgoing interfaces that the router has on the multicast tree. According to this computation, the TTL_current value limits the number of routers that receive a request packet. In the case of the FHR, it may use either a pre-configured default value or a value received from the querier. The remaining portion of the tree can be discovered in additional rounds. Each round begins by having the querier send new query messages to appropriate on-tree routers to continue topology discovery in a similar way. Sarac, Almeroth [Page 3] draft-sarac-tracetree-00.txt December 2001 3.2 Existence of Non-compliant Routers The existence of non-compliant routers may cause uncontrolled replication of request messages. If not controlled, this replication may cause potential scalability problems in the response collection mechanism. This is because non-compliant routers use the standard TTL decrement mechanism when forwarding request packets. This would interfere with the modified-TTL-based scope control mechanism for requests. In order to detect the existence of non-compliant routers, routers use a technique based on the duplication of the TTL value in request packets. On forwarding a request packet, compliant routers copy the IP TTL value into a field in the tracetree protocol header. This new value is called TTL_tt. Upon receiving a request, routers compare the values in the IP TTL and the TTL_tt fields. The difference between these two values gives the number of non-compliant routers since the last compliant router on the path. After detecting the existence of non-compliant routers, a decision on what to be done must be made. The first compliant router after the non-compliant router(s) uses an Average Branching Factor (ABF) to re-compute the IP TTL value TTL_IP of the incoming request packet. The assumption here is that, on average, each router in the network has a number of outgoing interfaces equal to the ABF. By using the average branching factor and TTL_tt, routers can compute a modified TTL_IP value as TTL_tt TTL_IP' = --------------- ABF^(num_level) where num_level = TTL_tt - TTL_IP. In a recent study, the ABF for internal multicast routers is reported to be approximately 1.57 (depending on the size of the tree)[4]. We can use this value as average branching factor or compute another one based on the network topology. After updating the TTL value of the incoming request packet to TTL_IP', routers may take one of a number of possible actions: (1) continue normal processing, (2) send a response to the querier if TTL_IP' is one or larger, but do not forward the request, and (3) do not respond and do not forward the request. These alternatives have different implications in terms of scalability and completeness. Similar to the case with non-compliant routers, the existence of multi-access links between on-tree routers causes irregularities in scope calculations. When a router has an outgoing interface on a multi-access link, it uses the above equation to calculate the TTL value for the request packet. Sarac, Almeroth [Page 4] draft-sarac-tracetree-00.txt December 2001 3.3 Security Security is an important concern for tracetree operation. This is because the trecetree mechanism can be used to launch third party denial-of-service attacks. A malicious user can spoof the IP address of a third party site and identify itself as a querier causing routers to send a potentially large number of responses to the victim site. In order to make launching this type of attacks difficult, routers use a three-way handshake mechanism in communicating tracetree queries. On receiving a query message, a router generates a random number and sends it to the IP source of the query message asking it to reply with the same number. Then, the router processes the query message only after it receives a response with the correct number from the querier. In addition, routers can regulate tracetree query/request processing rate to reduce the effect of such attacks on victim sites. Finally, the IP TTL field is an 8-bit field which limits the number of responses to 255 per query. The second security issue is the possibility of injecting fake request packets into the tree. We believe that such an attack would be difficult to accomplish due to the multicast forwarding rules, specifically the Reverse Path Forwarding (RPF) check. 3.4 Finding the First Hop Router Before sending a tracetree query message, the querier needs to know the IP address of the first hop router. We assume that the querier obtains this information externally and uses it to initiate the topology collection process. For a network administrator or a local querier, this information is easy to determine. On the other hand, for distant third party queriers this information may be difficult to obtain. One option might be to run a group specific mtrace towards the session source. 3.5 Loss of Router Response Messages Loss of response messages may cause gaps in the collected tree topology. Missing links may occur if a response message from an on-tree router is lost, but the response message coming from its downstream neighbor arrives at the querier site. In such a situation, a querier can send a new tracetree query message to the appropriate on-tree router(s) and ask it to re-send a request message to its downstream neighbors on the tree with a large enough TTL value. This causes the router (whose response message was lost) to respond to the querier again. In general, by using additional control information in the request packets, the querier can better isolate where the missing topology information belongs. Sarac, Almeroth [Page 5] draft-sarac-tracetree-00.txt December 2001 4. Tracetree query message format 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multicast Source Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multicast Group Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | # responses | Round id | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Random Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4.1. Multicast Source Address: 32 bits IP address of the source sending data to the multicast group. 4.2. Multicast Group Address: 32 bits Multicast group address for which the tree topology to be discovered. 4.3. # responses: 8 bits Maximum number of responses expected from on-tree routers for this given tracetree query message. 4.4. Round id: 8 bits Identifies the topology discovery round. 4.5. Reserved: 16 bits Set to zero when sent, ignored when received. 4.6. Random Number: 32 bits Used in three-way handshake between the querier node and the router receiving this query. Set to zero by querier when first sent to the router. Router then puts a generated random number into here and sends it back to querier i.e. to IP source address of the incoming query packet. Querier then sends the exact same message back to the router. Sarac, Almeroth [Page 6] draft-sarac-tracetree-00.txt December 2001 5. Tracetree request message format 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | TTL_tt | Level | Round id | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Request forwarder | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Response destination | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5.1. TTL_tt: 8 bits This field holds a copy of the TTL value in the IP protocol field. 5.2. Level: 8 bits This indicates the depth of the router forwarding this request packet on the multicast tree. It is equal to number of hops between this router and the first router starting the topology discovery of this (sub)tree. 5.3. Round id: 8 bits Identifies the topology discovery round. 5.4. Reserved: 8 bits Set to zero when sent, ignored when received. 5.5. Request forwarder: 32 bits IP address of the interface that this router is forwarding this request packet on the multicast tree. 5.6. Response destination: 32 bits IP address of the querier node to send the response messages to. Sarac, Almeroth [Page 7] draft-sarac-tracetree-00.txt December 2001 6. Tracetree response message format 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Level | Round id | #nghbors|E|Rsv| #non-compls | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Request forwarder | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Request receiving interface | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Bitmap of outgoing interfaces | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | IP of outgoing interface 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | IP of outgoing interface 2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | . | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | . | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | . | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | IP of outgoing interface N | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 6.1. Level: 8 bits This indicates the depth of the router forwarding this request packet on the multicast tree. It is equal to number of hops between this router and the first router starting the topology discovery of this (sub)tree. 6.2. Round id: 8 bits Identifies the topology discovery round. 6.3. # ngbhors: 5 bits Number of outgoing interfaces that this router has on the multicast tree. A value of zero implies that this router is a leaf router. 6.4. E: 1 bit Set to 1 if request scope expires at this router. Otherwise remains 0. E=1 implies that this router did not forward the request packet on its outgoing interfaces. 6.5. Rsv: 3 bits Set to zero when sent, ignored when received. Sarac, Almeroth [Page 8] draft-sarac-tracetree-00.txt December 2001 6.6. #non-compls: 8 bits Number of non-compliant routers between this router and the last compliant router that forwarded the request packet towards this router. 6.7. Request forwarder: 32 bits IP address of the router that has forwarded request packet. 6.8. Request receiving interface: 32 bits IP address of the interface on which this router received this request packet. 6.9. Bitmap of neighbors: 32 bits A bitmap corresponding to each outgoing interface that indicates whether this interface is on point to point link (a zero value in the corresponding bit location) or on a shared access link (a one value in the corresponding bit location). 6.10. IP of outgoing interface: 32 bits IP addresses of outgoing interfaces that this router has on the multicast tree. The maximum number of outgoing interfaces is limited to 32. 7. Intellectual Property The IETF takes no position regarding the validity or scope of any intellectual property or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; neither does it represent that it has made any effort to identify any such rights. Information on the IETF's procedures with respect to rights in standards-track and standards-related documentation can be found in BCP 11 [5]. Copies of claims of rights made available for publication and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementors or users of this specification can be obtained from the IETF Secretariat. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights which may cover technology that may be required to practice this standard. Please address the information to the IETF Executive Director. Sarac, Almeroth [Page 9] draft-sarac-tracetree-00.txt December 2001 8. References [1] W. Fenner and S. Casner, "A traceroute facility for IP multicast", work in progress, March 2000. [2] K. Sarac and K. Almeroth, "Scalable Techniques for Discovering Multicast Tree Topology", NOSSDAV'01, Port Jefferson, NY, USA, June 2001. [3] D. Katz, "IP Router Alert Option", RFC 2001, Cisco Systems, February 1997. [4] R. Chalmers and K. Almeroth, "Modeling the branching characteristics and efficiency gains of global multicast trees", in IEEE Infocom, Anchorage, Alaska, USA, April 2001. [5] R. Hovey and S. Bradner, "The Organizations Involved in the IETF Standards Process," BCP 11, RFC 2028, IETF, October 1996. 9. Full Copyright Statement Copyright (C) The Internet Society (2001). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Sarac, Almeroth [Page 10] draft-sarac-tracetree-00.txt December 2001 10. Authors' Addresses Kamil Sarac Department of Computer Science University of California Santa Barbara, CA 93106, USA Kevin C. Almeroth Department of Computer Science University of California Santa Barbara, CA 93106, USA Sarac, Almeroth [Page 11]