IETF Next Steps in Signaling C. Shen Internet-Draft H. Schulzrinne Expires: April 2005 Columbia U. S. Lee Samsung AIT October 2004 Internet Routing Dynamics and NSIS Related Considerations draft-shen-nsis-routing-00.txt Status of this Memo This document is an Internet-Draft and is subject to all provisions of section 3 of RFC 3667. By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she become aware will be disclosed, in accordance with RFC 3668. 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 April 2005. Copyright Notice Copyright (C) The Internet Society (2004). Abstract This document presents the main results from a recent Internet routing dynamics measurement and discusses their impact on NSIS protocol design. It also provides an evaluation of the simple, low cost packet TTL monitoring route change detection mechanism in the context of different NSIS deployment models. Shen, et al. Expires April 2005 [Page 1] Internet-Draft NSIS and Internet Routing Dynamics October 2004 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Measuring and Analyzing Internet Routing Dynamics from NSIS . 3 2.1 Measurement Methodology and Data Sets . . . . . . . . . . 3 2.2 Summary of Findings from an NSIS Perspective . . . . . . . 4 2.2.1 Route Prevalence and Route Persistence . . . . . . . . 4 2.2.2 Different Types of Route Changes . . . . . . . . . . . 4 2.2.3 Accuracy of Measuring Path Characteristics . . . . . . 5 2.2.4 Impact of Multi-Homing . . . . . . . . . . . . . . . . 5 3. NSIS-Concerned Route Changes and NSIS Deployment Models . . . 5 4. Evaluation of Packet TTL Monitoring Based Route Change Detection . . . . . . . . . . . . . . . . . . . . . . . . . . 7 5. Conclusions and Future Work . . . . . . . . . . . . . . . . . 8 6. Security Considerations . . . . . . . . . . . . . . . . . . . 8 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 8 8. Informative References . . . . . . . . . . . . . . . . . . . . 9 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 9 Intellectual Property and Copyright Statements . . . . . . . . 11 Shen, et al. Expires April 2005 [Page 2] Internet-Draft NSIS and Internet Routing Dynamics October 2004 1. Introduction Interaction with IP routing is an important aspect in Next Step In Signaling (NSIS) protocol design [1]. Solving this problem requires a good characterization of today's Internet's routing behavior. In this memo we summarize the main results from a routing measurement experiment conducted between April and August 2004, and discuss their impact to the design of NSIS. The focus of our routing study is route change. We look at the types, duration and likely causes of different route changes observed. Various route change detection mechanisms have been proposed in [2]. Some of them are simple and low cost, such as packet TTL monitoring. It will be very helpful to know how good such a mechanism will be. We evaluate the effectiveness of packet TTL monitoring in detecting route changes based on our measurement experiments. We also introduce the concept of NSIS-concerned route changes, and look at the TTL monitoring method in the context of different NSIS deployment models. For details about our measurements and analysis, the readers are referred to our technical report [5]. 2. Measuring and Analyzing Internet Routing Dynamics from NSIS 2.1 Measurement Methodology and Data Sets We collected four data sets in our measurements that involved totally 24 public traceroute servers located in US, Iceland, Netherlands, Australia, Germany, Switzerland, Bulgaria, Sweden, and Thailand. Data Set I (DS I) contains 12 sites and is collected from April 9, 05:14:02 AM EDT 2004 to April 24, 00:09:34 AM EDT 2004, at an average per-site exponential sampling rate of one traceroute every 15 minutes. This corresponds to an average of 2.75 hours sampling interval for each path. The independent and exponential sampling allows us to approximate the amount of time that the Internet spends in a particular route from the number of times we observe that particular route in our measurements. Data Set II (DS II) and Data Set III (DS III) contain 24 sites. Each site is exponentially sampled on average every 30 minutes. This corresponds to an average of 11.5 hours sampling interval for each path. Data Set II is taken from May 22 12:20:11 AM EDT to Jun 13 12:24:19 PM EDT, 2004 and Data Set III is taken from June 14 03:05:23 PM EDT to July 06 10:34:14 AM EDT, 2004. Shen, et al. Expires April 2005 [Page 3] Internet-Draft NSIS and Internet Routing Dynamics October 2004 Data Set IV (DS IV) contains both a ten-minute fixed interval and a two-hour exponential interval measurement conducted between four designated paths that are believed to be showing typical routing characteristics, i.e., they are not paths that display extremely high route fluctuations. DS IV is collected from July 14 to August 3, 2004. The purpose of this data set is to provide additional insights on short scale routing dynamics and also to obtain some understanding about impacts of longer measurement intervals (posed by infrastructure restrictions) on the accuracy of measurements. 2.2 Summary of Findings from an NSIS Perspective 2.2.1 Route Prevalence and Route Persistence We identified the most frequently observed route, or dominant route, for each path, and computed the prevalence of each dominant route, which is the number of times the dominant route is sampled divided by the total number of samples for that path. We also studied how long the path is likely to stay in one route, or route persistence, and obtained the duration distribution of long-lived routes. The results confirmed some of the conclusions from earlier measurements [3][4], i.e., Internet paths are strongly dominated by a single route, but significant site to site variation exists. The strong dominance of a single route is good for NSIS. To cope with significant site to site variations, it will be helpful for NSIS to employ an adaptive approach in dealing with routing dynamics. For example, the NSIS protocol should be more aggressive in detecting route changes on a path that is particularly instable, by using a shorter path refresh interval, or advanced route change detection mechanisms. 2.2.2 Different Types of Route Changes Our statistics of route changes shows that route changes occur over a wide range of time scales, ranging from seconds to days, and over different network scales, ranging from intra-AS changes to inter-AS changes. The majority of route changes are found to be involving no change of total number of hops (i.e., TTL-invisible). However, a large proportion of these TTL-invisible route changes are caused only by a small set of (mostly local) router pairs belonging to the same service provider or host network, which are probably doing route splitting and load balancing. The router administrators have the best information on how the routers are configured and therefore are the best persons to take care of these route changes. Route splitting is a cause to extremely short period route changes (called route fluttering [3]), at the scale of seconds or minutes. It is controlled by a special option of an IPv4 router and can be turned off [5]. Load balancing usually leads to short or medium Shen, et al. Expires April 2005 [Page 4] Internet-Draft NSIS and Internet Routing Dynamics October 2004 scale route changes and are seen in routers within both host and service provider networks. Extra mechanisms need to be deployed in these networks to allow proper functioning of NSIS in the presence of load balancing. These may include special route monitoring mechanisms to quickly detect the route change and notify related NSIS modules about the change, or establishing redundant state information in load balancing routers. The latter approach tends to cost more resources but gives a more prompt response time. 2.2.3 Accuracy of Measuring Path Characteristics Our analysis of DS IV showed that the accuracy of measuring the path characteristics with a longer measurement interval depends heavily on the stability of the path being studied. Using a ten-minute fixed interval and a two-hour exponential interval measurement, we have seen examples where both measurements capture the same number of routes, AS-paths and their changes; we have also seen examples where the two-hour interval measurement missed about half the number of unique routes, AS-paths and their changes. (During our processing of other data sets, we used several techniques to remove outliers that showed great instability in order to counter this effect.) This issue is essentially the same as the site to site variation problem mentioned in 3.2.1 and calls for adaptive NSIS mechanisms to characterize or interact with path dynamics. An example will be an NSIS refresh mechanism that starts with a short interval value and gradually increases that interval depending on the actual routing characteristics it observes. 2.2.4 Impact of Multi-Homing Multi-homing is often seen in our measurements and causes AS level route changes as well as asymmetric routing. A particular example we encountered in DS IV is a site that uses one ISP as the incoming ISP and another as the outgoing ISP. We've also seen the same site using one ISP as its primary outgoing ISP in May and June and then switch to another one as primary outgoing ISP in July. The result is a dramatic change of route characteristics, from a very stable route to a very fluctuating route. Moreover, the site still occasionally uses the old AS-path for a while, causing short term AS level route changes. If the multi-homed site has control over such behaviors, it should deploy appropriate mechanisms to notify related NSIS entities about the switch to allow a fast NSIS recovery. 3. NSIS-Concerned Route Changes and NSIS Deployment Models We have mentioned that the majority of route changes are local and Shen, et al. Expires April 2005 [Page 5] Internet-Draft NSIS and Internet Routing Dynamics October 2004 TTL-invisible so they are best tackled by the router administrators, or by keeping NSIS in mind when turning on related routing options. The remaining of the route changes, many of which non-trivial in that they could affect more than one hops in different geometrical locations, tend to have bigger impact on the applications using NSIS protocol and are more concerned by the NSIS community. It will be very nice if many of these changes can be detected by simple mechanisms like packet TTL monitoring, without special routing monitoring mechanisms installed by service provider or host network administrators. We will look at what our experiments show about the effectiveness of the TTL monitoring method. But before that, we introduce the concept of NSIS-concerned route changes and NSIS deployment models. From a network perspective, generic route changes can be classified into inter-AS and intra-AS route changes depending on whether the route change affects the AS set in the path. Intra-AS route changes may further be divided into ingress-point, egress-point and mid-point route change, depending on the location of the routers in the AS where the route change occurred. NSIS needs to deal with all generic route changes only in a full NSIS network where all nodes are NSIS Entities (NEs). A far more likely network scenario will be a mixed deployment of NEs and normal routers. In this case, only a subset of all generic route changes will involve change of NEs. These are NSIS-concerned route changes that should be dealt with by NSIS. To better understand NSIS-concerned route changes, we need to make assumptions about the actual NSIS deployment models. We list below possible NSIS deployment models in a mixed environment of NEs and normal routers, together with the corresponding NSIS-concerned route changes in each model. - AS model: in the AS model each AS deploys a central NE that is responsible for NSIS related signaling for this AS. The NSIS-concerned route changes in AS model include all route changes that involve AS changes, i.e., inter-AS route changes. - Entry model: in the entry model the ingress routers of each AS are NEs. NSIS-concerned route changes in this model include inter-AS and intra-AS ingress point route changes. - Border model: in the border model both ingress and egress routers of each AS are NEs. NSIS specific route changes in this model include inter-AS, intra-AS ingress point and intra-AS egress point changes. Shen, et al. Expires April 2005 [Page 6] Internet-Draft NSIS and Internet Routing Dynamics October 2004 - Edge model: in the edge model the access routers of the source and destination sites are NEs. NSIS-concerned route changes in this model include inter-AS route change involving the first or last AS, intra-AS ingress point route change in the first AS as well as intra-AS egress point route change in the last AS. - Generic model: we define the generic model as all other mixed deployments that cannot be clearly mapped to any of the above four categories. It might be a combination of the above models plus more NEs in certain parts of the network. There is no straightforward way to define an NSIS-concerned route change in this case other than to observe whether a change of NEs is involved once a route change has occurred. 4. Evaluation of Packet TTL Monitoring Based Route Change Detection The data in this section is abstracted from our routing measurements (Section 3). We started by assuming a full NE deployment model where all route changes count. Table 1 shows the proportion of TTL visible route changes and AS path changes in our data sets I, II and III. +------------------------------+------+-------+--------+ | Item description | DS I | DS II | DS III | +------------------------------+------+-------+--------+ | TTL-visible route changes | 38% | 25% | 23% | | AS level route changes | 18% | 8% | 8% | | TTL-visible AS level changes | 77% | 83% | 88% | +------------------------------+------+-------+--------+ Table 1: TTL-visible route changes and AS changes The percentage of overall TTL-visible route changes does not seem very promising. However, even in an all NE network, the route changes that concern us most are always non-trivial ones. If we focus on those AS level changes, we can see that TTL does a fairly good job in detecting roughly 4 out of 5 such changes. We also examined the effectiveness of TTL in detecting NSIS-concerned route changes in four mixed NSIS deployment models as shown in Table 2. Clearly the TTL detection mechanism works better in these mixed models than in the all NE model. This is because NSIS-concerned route changes in all these four models are usually non-trivial changes, where TTL monitoring tends to be more effective. The table also shows that the successful TTL detection ratio tends to be higher when the deployment model is sparser in terms of NEs and thus fewer route changes become NSIS-concerned. Therefore, the edge model and Shen, et al. Expires April 2005 [Page 7] Internet-Draft NSIS and Internet Routing Dynamics October 2004 the AS model have higher detection ratio than the entry and border models. It is not possible to check the effectiveness of TTL detection mechanism in a generic mixed model when detailed deployment information is unknown, but the answer is expected to fall between the full NE model and the four mixed models we have studied. +--------------+------+-------+--------+ | NSIS model | DS I | DS II | DS III | +--------------+------+-------+--------+ | AS model | 77% | 83% | 88% | | Entry model | 51% | 41% | 40% | | Border model | 45% | 39% | 38% | | Edge model | 74% | 90% | 92% | +--------------+------+-------+--------+ Table 2: Effectiveness of TTL detection in the four mixed models Overall, the TTL monitoring method appears to be a reasonably good way to find non-trivial route changes, although this mechanism alone is hardly enough to detect all NSIS-concerned route changes. 5. Conclusions and Future Work We performed a routing measurement on today's Internet and studied the impact of general Internet routing dynamics, especially route changes, on NSIS design. We concluded that different types of route changes require different handling. Frequent yet local route changes caused by route splitting or load balancing are best handled by routing monitoring inside the network; many non-trivial NSIS-concerned route changes may be detected by hosts employing simple packet TTL monitoring mechanism, as we have seen in typical NSIS deployment models. We are currently also investigating other route change detection methods to see when and how they are likely to be useful. 6. Security Considerations There are no explicit security issues associated with current version of this document. 7. Acknowledgements Shen, et al. Expires April 2005 [Page 8] Internet-Draft NSIS and Internet Routing Dynamics October 2004 We would like to thank Jongho Bang for their comments and support in this work.We would also like to thank all traceroute server sites that participated in our measurement. 8 Informative References [1] Hancock, R., "Next Steps in Signaling: Framework", draft-ietf-nsis-fw-06 (work in progress), July 2004. [2] Schulzrinne, H., "GIMPS: General Internet Messaging Protocol for Signaling", draft-ietf-nsis-ntlp-04 (work in progress), October 2004. [3] Paxson, V., "Measurements and Analysis of End-to-End Internet Dynamics", PhD thesis, University of California, Berkeley, 1997. [4] Zhang, Y., "Characterizing End-to-End Internet Performance", PhD thesis, Cornell University, 2001. [5] Baker, F., "Requirements for IP Version 4 Routers", RFC 1812, June 1995. [6] Shen, C. and H. Schulzrinne, "Internet Routing Dynamics and NSIS Related Considerations", technical report, Columbia University, October 2004. Authors' Addresses Charles Shen Columbia University Department of Computer Science 1214 Amsterdam Avenue, MC 0401 New York, NY 10027 USA Phone: +1 212 854 5599 EMail: charles@cs.columbia.edu Henning Schulzrinne Columbia University Department of Computer Science 1214 Amsterdam Avenue, MC 0401 New York, NY 10027 USA Shen, et al. Expires April 2005 [Page 9] Internet-Draft NSIS and Internet Routing Dynamics October 2004 Phone: +1 212 939 7004 EMail: schulzrinne@cs.columbia.edu Sung-Hyuck Lee SAMSUNG Advanced Institute of Technology San 14-1, Nongseo-ri, Giheung-eup Yongin-si, Gyeonggi-do 449-712 KOREA Phone: +82 31 280 9585 EMail: starsu.lee@samsung.com Shen, et al. Expires April 2005 [Page 10] Internet-Draft NSIS and Internet Routing Dynamics October 2004 Intellectual Property Statement The IETF takes no position regarding the validity or scope of any Intellectual Property Rights 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; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat 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 implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM 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. Copyright Statement Copyright (C) The Internet Society (2004). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Shen, et al. Expires April 2005 [Page 11]