Network Working Group A. Doria Internet-Draft ETRI Expires: January 17, 2005 E. Davies Nortel Networks July 19, 2004 Analysis of IDR requirements and History draft-irtf-routing-history-01.txt Status of this Memo By submitting this Internet-Draft, we certify that any applicable patent or other IPR claims of which we are aware have been disclosed, and any of which we 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 January 17, 2005. Copyright Notice Copyright (C) The Internet Society (2004). All Rights Reserved. Abstract This document analyses the current state of IDR routing with respect to RFC1026 and other IDR requirements and design efforts. It is the companion document to version 03 of the inter-domain routing requirements draft [41], which is a discussion of requirements for the future routing architecture and future routing protocols. Doria & Davies Expires January 17, 2005 [Page 1] Internet-Draft IDR History July 2004 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Historical Perspective . . . . . . . . . . . . . . . . . . . 4 2.1 The legacy of RFC1126 . . . . . . . . . . . . . . . . . . 4 2.1.1 "General Requirements" . . . . . . . . . . . . . . . . 5 2.1.2 "Functional Requirements" . . . . . . . . . . . . . . 7 2.1.3 "Non-Goals" . . . . . . . . . . . . . . . . . . . . . 14 2.2 Nimrod Requirements . . . . . . . . . . . . . . . . . . . 16 2.3 PNNI . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4 ISO . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.5 Recent Research Work . . . . . . . . . . . . . . . . . . . 18 2.5.1 Developments in Internet Connectivity . . . . . . . . 18 2.5.2 Defending the End To End Principle . . . . . . . . . . 19 3. Existing problems of BGP and the current EGP/IGP Architecture . . . . . . . . . . . . . . . . . . . . . . . . 20 3.1 BGP and Auto-aggregation . . . . . . . . . . . . . . . . . 21 3.2 Convergence and Recovery Issues . . . . . . . . . . . . . 21 3.3 Non-locality of Effects of Instability and Misconfiguration . . . . . . . . . . . . . . . . . . . . . 22 3.4 Multihoming Issues . . . . . . . . . . . . . . . . . . . . 22 3.5 AS-number exhaustion . . . . . . . . . . . . . . . . . . . 23 3.6 Partitioned AS's . . . . . . . . . . . . . . . . . . . . . 24 3.7 Load Sharing . . . . . . . . . . . . . . . . . . . . . . . 24 3.8 Hold down issues . . . . . . . . . . . . . . . . . . . . . 24 3.9 Interaction between Inter domain routing and intra domain routing . . . . . . . . . . . . . . . . . . . . . . 25 3.10 Policy Issues . . . . . . . . . . . . . . . . . . . . . 26 3.11 Security Issues . . . . . . . . . . . . . . . . . . . . 26 3.12 Support of MPLS and VPNS . . . . . . . . . . . . . . . . 26 3.13 IPv4 / IPv6 Ships in the Night . . . . . . . . . . . . . 27 3.14 Existing Tools to Support Effective Deployment of Inter-Domain Routing . . . . . . . . . . . . . . . . . . 27 3.14.1 Routing Policy Specification Language RPSL (RFC 2622, 2650) and RIPE NCC Database (RIPE 157) . . . . 28 4. Security Considerations . . . . . . . . . . . . . . . . . . 28 5. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 29 6. References . . . . . . . . . . . . . . . . . . . . . . . . . 29 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 32 Intellectual Property and Copyright Statements . . . . . . . 33 Doria & Davies Expires January 17, 2005 [Page 2] Internet-Draft IDR History July 2004 1. Introduction It is generally accepted that there are major shortcomings in the inter-domain routing of the Internet today and that these may result in meltdown within an unspecified period of time. Remedying these shortcomings will require extensive research to tie down the exact failure modes that lead to these shortcomings and identify the best techniques to remedy the situation. Various developments in the nature and quality of the services that users want from the Internet are difficult to provide within the current framework as they impose requirements never foreseen by the original architects of the Internet routing system. The advent of IPv6 and the application of IP mechanisms to private commercial networks offering specific service guarantees as an improvement over the best efforts services of the Public Internet epitomize the kind of radical changes which have to be accommodated: Major changes to the inter-domain routing system are inevitable if it is to provide an efficient underpinning for the radically changed and increasingly, commercially-based networks which rely on the IP protocol suite. Current practice stresses the need to separate the concerns of the control plane in a router and the forwarding plane: This document will follow this practice, but we still use the term 'routing' as a global portmanteau to cover all aspects of the system. This draft makes a start on the analysis of domain routing in Section 2 by revisiting the requirements for a future routing system which were last documented in RFC1126 - "Goals and Functional Requirements for Inter-Autonomous System Routing" [4] as a precursor to the design of BGP in 1989. This section also looks at some other work that has been carried out since RFC1126 was published in order to flesh out the historical perspective. Some of the requirements for new routing architectures derive from the problems that are currently being experienced in the Internet today. These will be discussed in Section 3. 1.1 Background Today's Internet uses an addressing and routing structure that has developed in an ad hoc, more or less upwards-compatible fashion. It has progressed from handling a single domain, non-commercial Internet to a solution that is just about controlling today's multi-domain, federated, combination commercial and not-for-profit Internet. The result is not ideal, particularly as regards inter-domain routing mechanisms that have to implement a host of domain specific routing Doria & Davies Expires January 17, 2005 [Page 3] Internet-Draft IDR History July 2004 policies for competing, communicating domains, but it does a pretty fair job at its primary goal of providing any-to-any connectivity to many millions of computers. Based on a large body of anecdotal evidence, but also on a growing body of experimental evidence [11] and analytic work on the stability of BGP under certain policy specifications [12], the main Internet inter-domain routing protocol, BGP4, appears to have a number of problems that need to be resolved. Additionally, the hierarchical nature of the inter-domain routing problem appears to be changing as the connectivity between domains becomes increasingly meshed [13] which alters some of the scaling and structuring assumptions on which BGP4 is built. Patches and fix-ups may relieve some of these problems but others may require a new architecture and new protocols. Since the original version of this draft was published a number of the initiatives mentioned (such as the DARPA NewArch project described in Section 2.5.2) have continued researching the way forwards for the Internet. There have also been continuing efforts in the IETF multi6 working group to resolve the problems of multihoming especially in IPv6. Some of the explosive growth of the routing tables has been quenched by the economic downturn since the end of 2000, but this has not resolved the problems that existed with inter-domain routing. The contents of this draft remain relevant to the Internet today and the intention is to provide further updates to document the research efforts that have been going on over the last couple of years. 2. Historical Perspective 2.1 The legacy of RFC1126 RFC1126 outlined a set of requirements that were to guide the development of BGP. While the network is definitely different then it was in 1989, many of the same requirements remain. As a first step in setting requirements for the future, we need to understand the requirements that were originally set for the current protocols. And in charting a future architecture we must first be sure to do no harm. This means a future domain routing has to support as its base requirement, the level of function that is available today. The following sections each relate to a requirement, or non- requirement listed in RFC1126. In fact the section names are direct quotes from the document. The discussion of these requirements covers the following areas: Doria & Davies Expires January 17, 2005 [Page 4] Internet-Draft IDR History July 2004 Explanation: Optional interpretation for today's audience of the original intent of the requirement Relevance: Is the requirement of RFC1126 still relevant, and to what degree? Should it be understood differently in today's environment? Current practice: How well is the requirement met by current protocols and practice? 2.1.1 "General Requirements" 2.1.1.1 "Route to Destination" Timely routing to all reachable destinations, including multihoming and multicast. Relevance: Valid, but requirements for multihoming need further discussion and elucidation. The requirement should include multiple source multicast routing. Current practice: Multihoming is not efficient and the proposed inter-domain multicast protocol BGMP is an add-on to BGP following many of the same strategies but not integrated into the BGP framework [23]. 2.1.1.2 "Routing is Assured" This requires that a user be notified within a reasonable time period of attempts, about inability to provide a service. Relevance: Valid Current practice: There are ICMP messages for this, but in many cases they are not used, either because of fears about creating message storms or uncertainty about whether the end system can do anything useful with the resulting information. 2.1.1.3 "Large System" The architecture was designed to accommodate the growth of the Internet. Relevance: Valid. Properties of Internet topology might be an issue for future scalability (topology varies from very sparse to quite dense at present). Instead of setting growth in a time-scale, indefinite growth should be accommodated. On the other hand, such growth has to be accommodated without making the protocols too expensive - trade-offs may be necessary. Doria & Davies Expires January 17, 2005 [Page 5] Internet-Draft IDR History July 2004 Current practice: Scalability of the current protocols will not be sufficient under the current rate of growth. There are problems with BGP convergence for large dense topologies, problems with routing information propagation between routers in transit domain, limited support for hierarchy, etc. 2.1.1.4 "Autonomous Operation" Relevance: Valid. There may need to be additional requirements for adjusting policy decisions to the global functionality and for avoiding contradictory policies. This would decrease the possibility of unstable routing behavior. There is a need for handling various degrees of trust in autonomous operations, ranging from no trust (e.g., between separate ISPs) to very high trust where the domains have a common goal of optimizing their mutual policies. Policies for intra domain operations should in some cases be revealed, using suitable abstractions. Current practice: Policy management is in the control of network managers, as required, but there is little support for handling policies at an abstract level for a domain. Cooperating administrative entities decide about the extent of cooperation independently. Lack of coordination combined with global range of effects results in occasional melt-down of Internet routing. 2.1.1.5 "Distributed System" The routing environment is a distributed system. The distributed routing environment supports redundancy and diversity of nodes and links. Both data and operations are distributed. Relevance: Valid. RFC1126 is very clear that we should not be using centralized solutions, but maybe we need a discussion on trade-offs between common knowledge and distribution (i.e., to allow for uniform policy routing, e.g., GSM systems are in a sense centralized, but with hierarchies) Current practice: Routing is very distributed, but lacking abilities to consider optimization over several hops or domains. Doria & Davies Expires January 17, 2005 [Page 6] Internet-Draft IDR History July 2004 2.1.1.6 "Provide A Credible Environment" Routing mechanism information must be integral and secure (credible data, reliable operation). Security from unwanted modification and influence is required. Relevance: Valid. Current practice: BGP provides a mechanism for authentication and security. There are however security problems with current practice. 2.1.1.7 "Be A Managed Entity" Requires that a manager should get enough information on a state of network so that s/he could make informed decisions. Relevance: The requirement is reasonable, but we might need to be more specific on what information should be available, e.g. to prevent routing oscillations. Current practice: All policies are determined locally, where they may appear reasonable but there is limited global coordination through the routing policy databases operated by the Internet registries (ARIN, RIPE, APNIC etc). Operators are not required to register their policies; even when policies are registered, it is difficult to check that the actual policies in use match the declared policies and therefore a manager cannot guarantee to make a globally consistent decision. 2.1.1.8 "Minimize Required Resources" Relevance: Valid, however, the paragraph states that assumptions on significant upgrades shouldn't be made. Although this is reasonable, a new architecture should perhaps be prepared to use upgrades when they occur. Current practice: Most bandwidth is consumed by the exchange of the NLRI. Usage of CPU depends on the stability of the Internet. Both phenomena have a local nature, so there are not scaling problems with bandwidth and CPU usage. Instability of routing increases the consumption of resources in any case. The number of networks in the Internet dominates memory requirements - this is a scaling problem. 2.1.2 "Functional Requirements" Doria & Davies Expires January 17, 2005 [Page 7] Internet-Draft IDR History July 2004 2.1.2.1 "Route Synthesis Requirements" 2.1.2.1.1 "Route around failures dynamically" Relevance: Valid. Should perhaps be stronger. Only providing a best- effort attempt may not be enough if real-time services are to be provided for. Detections may need to be faster than 100ms to avoid being noticed by end-users. Current practice: latency of fail-over is too high; sometimes minutes or longer. 2.1.2.1.2 "Provide loop free paths" Relevance: Valid. Loops should occur only with negligible probability and duration. Current practice: both link-state intra domain routing and BGP inter- domain routing (if correctly configured) are forwarding- loop free after having converged. However, convergence time for BGP can be very long and poorly designed routing policies may result in a number of BGP speakers engaging in a cyclic pattern of advertisements and withdrawals which never converges to a stable result [20]. Perhaps this is one context in which the need for global convergence needs to be reviewed. 2.1.2.1.3 "Know when a path or destination is unavailable" Relevance: Valid to some extent, but there is a trade-off between aggregation and immediate knowledge of reachability. It requires that routing tables contain enough information to determine that the destination is unknown or a path cannot be constructed to reach it. Current practice: Knowledge about lost reachability propagates slowly through the networks due to slow convergence for route withdrawals. 2.1.2.1.4 "Provide paths sensitive to administrative policies" Relevance: Valid. Policy control of routing is of increasingly importance as the Internet has turned into business. Current practice: Supported to some extent. Policies are only possible to apply locally in an AS and not globally. At least there is a very small probability of affecting policies in other AS's. Furthermore, only static policies are supported; between static policies and `policies dependent upon volatile events of great celerity` there should exist events that routing should be aware Doria & Davies Expires January 17, 2005 [Page 8] Internet-Draft IDR History July 2004 of. Lastly, there is no support for policies other than route- properties (such as AS-origin, AS-path, destination prefix, MED-values etc). 2.1.2.1.5 "Provide paths sensitive to user policies" Relevance: Valid to some extent, as they may conflict with the policies of the network administrator. It is likely that this requirement will be met by means of different bit transport services offered by an operator, but at the cost of adequate provisioning, authentication and policing when utilizing the service. Current practice: not supported in normal routing. Can be accomplished to some extent with loose source routing, resulting in inefficient forwarding in the routers. The various attempts to introduce QoS (Integrated Services and DiffServ) can also be seen as means to support this requirement but they have met with limited success. 2.1.2.1.6 "Provide paths which characterize user quality-of-service requirements" Relevance: Valid to some extent, as they may conflict with the policies of the operator. It is likely that this requirement will be met by means of different bit transport services offered by an operator, but at the cost of adequate provisioning, authentication and policing when utilizing the service. It has become clear that offering to provide a particular QoS to any arbitrary destination from a particular source is generally impossible: QoS except in very 'soft' forms such as overall long term average packet delay, is generally associated with connection oriented routing. Current practice: Creating routes with specified QoS is not generally possible at present. 2.1.2.1.7 "Provide autonomy between inter- and intra-autonomous system route synthesis" Relevance: Inter and intra domain routing should stay independent, but one should notice that this to some extent contradicts the previous three requirements. There is a trade-off between abstraction and optimality. Doria & Davies Expires January 17, 2005 [Page 9] Internet-Draft IDR History July 2004 Current practice: inter-domain routing is performed independently of intra-domain routing. Intra-domain routing is, especially in transit domains, very interrelated to inter-domain routing. 2.1.2.2 "Forwarding Requirements" 2.1.2.2.1 "Decouple inter- and intra-autonomous system forwarding decisions" Relevance: Valid. Current practice: As explained in 2.1.2.1.7, intra-domain forwarding in transit domains is codependent with inter-domain forwarding decisions. 2.1.2.2.2 "Do not forward datagrams deemed administratively inappropriate" Relevance: Valid, and increasingly important in the context of enforcing policies correctly expressed through routing advertisements but flouted by rogue peers which send traffic for which a route has not been advertised. On the other hand, packets that have been misrouted due to transient routing problems perhaps should be forwarded to reach the destination, although along an unexpected path. Current practice: at stub domains there is packet filtering, e.g., to catch source address spoofing on outgoing traffic or to filter out unwanted incoming traffic. Filtering can in particular reject traffic (such as unauthorized transit traffic) that has been sent to a domain even when it has not advertised a route for such traffic on a given interface. The growing class of 'mid boxes' (e.g. NATs) is quite likely to apply administrative rules that will prevent forwarding of packets. Note that security policies may deliberately hide administrative denials. In the backbone, intentional packet dropping based on policies is not common. 2.1.2.2.3 "Do not forward datagrams to failed resources" Relevance: Unclear, although it is clearly desirable to minimise waste of forwarding resources by discarding datagrams which cannot be delivered at the earliest opportunity. There is a trade-off between scalability and keeping track of unreachable resources. Equipment closest to a failed node has the highest motivation to keep track of failures so that waste can be minimised. Doria & Davies Expires January 17, 2005 [Page 10] Internet-Draft IDR History July 2004 Current practice: routing protocols use both internal adjacency management sub-protocols (e.g. Hello protocols) and information from equipment and lower layer link watchdogs to keep track of failures in routers and connecting links. Failures will eventually result in the routing protocol reconfiguring the routing to avoid (if possible) a failed resource, but this is generally very slow (30s or more). In the meantime datagrams may well be forwarded to failed resources. In general terms, end hosts and some non- router midboxes do not participate in these notifications and failures of such boxes will not affect the routing system. 2.1.2.2.4 "Forward datagram according to its characteristics" Relevance: Valid. This is necessary in enabling differentiation in the network, based on QoS, precedence, policy or security. Current practice: ingress and egress filtering can be done based on policy. 2.1.2.3 "Information Requirements" 2.1.2.3.1 "Provide a distributed and descriptive information base" Relevance: Valid, however hierarchical information bases might provide more possibilities. Current practice: the information base is distributed, it is unclear whether they support all necessary routing functionality. 2.1.2.3.2 "Determine resource availability" Relevance: Valid. It should be possible for resource availability and levels of resource availability to be determined. This prevents needing to discover unavailability through failure. Resource location and discovery is arguably a separate concern that could be addressed outside the core routing requirements. Current practice: Resource availability is predominantly handled outside of the routing system. 2.1.2.3.3 "Restrain transmission utilization" Relevance: Valid. However certain requirements in the control plane, such as fast detection of faults may be worth consumption of more resources. Similarly, simplicity of implementation may make it cheaper to 'back haul' traffic to central Doria & Davies Expires January 17, 2005 [Page 11] Internet-Draft IDR History July 2004 locations to minimise the cost of routing if bandwidth is cheaper than processing. Current practice: BGP messages probably do not ordinarily consume excessive resources, but might during erroneous conditions. In the data plane, the near universal adoption of shortest path protocols could be considered to result in minimization of transmission utilization. 2.1.2.3.4 "Allow limited information exchange" Relevance: Valid. But perhaps routing could be improved if certain information could be available either globally or at least for a wider defined locality. Current practice: Policies are used to determine which reachability information that is exported. 2.1.2.4 "Environmental Requirements" 2.1.2.4.1 "Support a packet-switching environment" Relevance: Valid but routing system should not be limited to this exclusively. Current practice: supported. 2.1.2.4.2 "Accommodate a connection-less oriented user transport service" Relevance: Valid, but routing system should not be limited to this exclusively. Current practice: accommodated. 2.1.2.4.3 "Accommodate 10K autonomous systems and 100K networks" Relevance: No longer valid. Needs to be increased potentially indefinitely. It is extremely difficult to foresee the future size expansion of the Internet so that the utopian solution would be to achieve an Internet whose architecture is scale invariant. Regrettably, this may not be achievable without introducing undesirable complexity and a suitable trade off between complexity and scalability is likely to be necessary. Current Practice: Supported but perhaps reaching its limit. 2.1.2.4.4 "Allow for arbitrary interconnection of autonomous systems" Relevance: Valid. However perhaps not all interconnections should be accessible globally. Doria & Davies Expires January 17, 2005 [Page 12] Internet-Draft IDR History July 2004 Current practice: BGP-4 allows for arbitrary interconnections. 2.1.2.5 "General Objectives" 2.1.2.5.1 "Provide routing services in a timely manner" Relevance: Valid, as stated before. The more complex a service is the longer it should be allowed to take, but the implementation of services requiring (say) NP-complete calculation should be avoided. Current practice: More or less, with the exception of convergence and fault robustness. 2.1.2.5.2 "Minimize constraints on systems with limited resources" Relevance: Valid Current practice: Systems with limited resources are typically stub domains that advertise very little information. 2.1.2.5.3 "Minimize impact of dissimilarities between autonomous systems" Relevance: Important. This requirement is critical to a future architecture. In a domain routing environment where the internal properties of domains may differ radically, it will be important to be sure that these dissimilarities are minimized at the borders. Current: practice: For the most part this capability isn't required in today's networks since the intra-domain attribute are nearly identical to start with. 2.1.2.5.4 "Accommodate the addressing schemes and protocol mechanisms of the autonomous systems" Relevance: Important, probably more so than when RFC1126 was originally developed because of the potential deployment of IPv6, wider usage of MPLS and the increasing usage of VPNs. Current practice: Largely only one global addressing scheme is supported in most autonomous systems. 2.1.2.5.5 "Must be implementable by network vendors" Relevance: Valid, but note that what can be implemented today is different from what was possible when RFC1126 was written: a future domain routing architecture should not be unreasonably constrained by past limitations. Current practice: BGP was implemented. Doria & Davies Expires January 17, 2005 [Page 13] Internet-Draft IDR History July 2004 2.1.3 "Non-Goals" RFC1126 also included a section discussing non-goals. To what extent are these still non-goals? Does the fact that they were non-goals adversely affect today's IDR system? 2.1.3.1 "Ubiquity" In a sense this 'non-goal' has effectively been achieved by the Internet and IP protocols. This requirement reflects a different worldview where there was serious competition for network protocols, which is really no longer the case. Ubiquitous deployment of inter- domain routing in particular has been achieved and must not be undone by any proposed future domain routing architecture. On the other hand: - ubiquitous connectivity cannot be reached in a policy sensitive environment and should not be an aim, - it must not be required that the same routing mechanisms are used throughout provided that they can interoperate appropriately - the information needed to control routing in a part of the network should not necessarily be ubiquitously available and it must be possible for an operator to hide commercially sensitive information that is not needed outside a domain. Relevance: De facto essential for a future domain routing architecture, but what is required is ubiquity of the routing system rather than ubiquity of connectivity. Current practice: de facto ubiquity achieved. 2.1.3.2 "Congestion control" Relevance: It is not clear if this non-goal was to be applied to routing or forwarding. It is definitely a non-goal to adapt the choice of route at transient congestion. However, to add support for congestion avoidance (e.g., ECN and ICMP messages) in the forwarding process would be a useful addition. There is also extensive work going on in traffic engineering which should result in congestion avoidance through routing as well as in forwarding. Current practice: Some ICMP messages (e.g. source quench) exist to deal with congestion control but these are not generally used as they either make the problem worse or there is no mechanism to reflect the message into the application which is providing the source. Doria & Davies Expires January 17, 2005 [Page 14] Internet-Draft IDR History July 2004 2.1.3.3 "Load splitting" Relevance: This should neither be a non-goal, nor an explicit goal. It might be desirable in some cases and should be considered as an optional architectural feature. Current practice: Can be implemented by exporting different prefixes on different links, but this requires manual configuration and does not consider actual load. 2.1.3.4 "Maximizing the utilization of resources" Relevance: Valid. Cost-efficiency should be strived for; maximizing resource utilization does not always lead to greatest cost-efficiency. Current practice: Not currently part of the system, though often a 'hacked in' feature done with manual configuration. 2.1.3.5 "Schedule to deadline service" This non-goal was put in place to ensure that the IDR did not have to meet real time deadline goals such as might apply to CBR services in ATM. Relevance: The hard form of deadline services is still a non-goal for the future domain routing architecture but overall delay bounds are much more of the essence than was the case when RFC1126 was written. Current Practice: Service providers are now offering overall probabilistic delay bounds on traffic contracts. To implement these contracts there is a requirement for a rather looser form of delay sensitive routing. 2.1.3.6 "Non-interference policies of resource utilization" The requirement in RFC1126 is somewhat opaque, but appears to imply that what we would today call QoS routing is a non-goal and that routing would not seek to control the elastic characteristics of Internet traffic whereby a TCP connection can seek to utilize all the spare bandwidth on a route, possibly to the detriment of other connections sharing the route or crossing it. Relevance: Open Issue. It is not clear whether dynamic QoS routing can or should be implemented. Such a system would seek to control the admission and routing of traffic depending on current or recent resource utilization. This would be particularly problematic where traffic crosses an ownership boundary because of the need for potentially Doria & Davies Expires January 17, 2005 [Page 15] Internet-Draft IDR History July 2004 commercially sensitive information to be made available outside the ownership boundary. Current practice: Routing does not consider dynamic resource availability. Forwarding can support service differentiation. 2.2 Nimrod Requirements Nimrod as expressed by Noel Chiappa in his early document, "A New IP Routing and Addressing Architecture" (1991) and later in the NIMROD Working Group documents RFC 1753 and RFC1992 established a number of requirements that need to be considered by any new routing architecture. The Nimrod requirements took RFC1126 as a starting point and went further. The goals of Nimrod, quoted from RFC1992, were as follows 1. To support a dynamic internetwork of *arbitrary size* (our emphasis) by providing mechanisms to control the amount of routing information that must be known throughout an internetwork. 2. To provide service-specific routing in the presence of multiple constraints imposed by service providers and users. 3. To admit incremental deployment throughout an internetwork. - As discussed in other sections of this document the amount of information needed to maintain the routing system is growing at a rate that does not scale. And yet, as the services and constraints upon those services grow there is a need for more information to be maintained by the routing system. One of the key terms in the first requirements is 'control'. While increasing amounts of information need to be known and maintained in the Internet, the amounts and kinds of information that are distributed can be controlled. This goal should be reflected in the requirements for the future domain architecture. - If anything, the demand for specific services in the Internet has grown since 1996 when the Nimrod architecture was published. Additionally the kinds of constraints that service providers need to impose upon their networks and that services need to impose upon the routing have also increased. Any changes made to the network in the last half-decade have not significantly improved this situation. - The ability to incrementally deploy any new routing architecture within the Internet is still a absolute necessity. It is impossible to imagine that a new routing architecture could supplant the current architecture on a flag day At one point in time Nimrod, with its addressing and routing architectures was seen as a candidate for IPng. History shows that it was not accepted as the IPng, having been ruled out of the Doria & Davies Expires January 17, 2005 [Page 16] Internet-Draft IDR History July 2004 selection process by the IESG in 1994 on the grounds that it was 'too much of a research effort' [35], although input for the requirements of IPng was explicitly solicited from Chiappa [8]. Instead IPv6 has been put forth as the IPng. Without entering a discussion of the relative merits of IPv6 versus Nimrod, it is apparent that IPv6, while it may solve many problems, does not solve the critical routing problems in the Internet today. In fact in some sense it exacerbates them by adding a requirements for support of two internet protocols and their respective addressing methods. In many ways the addition of IPv6 to the mix of methods in today's Internet only points to the fact that the goals, as set forth by the Nimrod team, remain as necessary goals. There is another sense in which study of Nimrod and its architecture may be important to deriving a future domain routing architecture. Nimrod can be said to have two derivatives: - MPLS in that it took the notion of forwarding along well known paths - PNNI in that it took the notion of abstracting topological information and using that information to create connections for traffic. It is important to note, that whilst MPLS and PNNI borrowed ideas from Nimrod, neither of them can be said to be an implementation of this architecture. 2.3 PNNI PNNI was developed under the ATM Forum's auspices as a hierarchical route determination protocol for ATM, a connection oriented architecture. It is reputed to have developed several of it methods from a study of the Nimrod architecture. What can be gained from an analysis of what did and did not succeed in PNNI? The PNNI protocol includes the assumption that all peer groups are willing to cooperate, and that the entire network is under the same top administration. Are there limitations that stem from this 'world node' presupposition? As discussed in [13], the Internet is no longer a clean hierarchy and there is a lot of resistance to having any sort of 'ultimate authority' controlling or even brokering communication. PNNI is the first deployed example of a routing protocol that uses abstract map exchange (as opposed to distance vector or link state mechanisms) for inter-domain routing information exchange. One consequence of this is that domains need not all use the same mechanism for map creation. What were the results of this abstraction and source based route calculation mechanism? Doria & Davies Expires January 17, 2005 [Page 17] Internet-Draft IDR History July 2004 Since the authors of this document do not have experience running a PNNI network, the comments above are from a theoretical perspective. Information on these issues, and any other relevant issues, is solicited from those who do have such operational experience. Any volunteers? 2.4 ISO Note: [At IETF52, a long time ago now a presentation on this draft was made to the IETF routing group was made. I was reminded that ISO had already tackled this problem as well, and that their efforts should be reviewed as well. That work is still pending a year later. Any volunteers to write this section?] 2.5 Recent Research Work 2.5.1 Developments in Internet Connectivity The recent work commissioned from Geoff Huston by the Internet Architecture Board [13] draws a number of conclusions from analysis of BGP routing tables and routing registry databases: - The connectivity between provider ASs is becoming more like a dense mesh than the tree structure that was commonly assumed to be commonplace a couple of years ago. This has been driven by the increasing amounts charged for peering and transit traffic by global service providers. Local direct peering and internet exchanges are becoming steadily more common as the cost of local fibre connections drops. - End user sites are increasingly resorting to multi-homing onto two or more service providers as a way of improving resiliency. This has a knock-on effect of spectacularly fast depletion of the available pool of AS numbers as end user sites require public AS numbers to become multi-homed and corresponding increase in the number of prefixes advertised in BGP. - Multi-homed sites are using advertisement of longer prefixes in BGP as a means of traffic engineering to load spread across their multiple external connections with further impact on the size of the BGP tables. - Operational practices are not uniform, and in some cases lack of knowledge or training is leading to instability and/or excessive advertisement of routes by incorrectly configured BGP speakers. - All these factors are quickly negating the advantages in limiting the expansion of BGP routing tables that were gained by the introduction of CIDR and consequent prefix aggregation in BGP. It is also now impossible for IPv6 to realize the world view in which the default free zone would be limited to perhaps 10,000 prefixes. Doria & Davies Expires January 17, 2005 [Page 18] Internet-Draft IDR History July 2004 - The typical 'width' of the Internet in AS hops is now around five, and much less in many cases. These conclusions have a considerable impact on the requirements for the future domain routing architecture: - Topological hierarchy (e.g. mandating a tree structured connectivity) cannot be relied upon to deliver scalability of a large Internet routing system - Aggregation cannot be relied upon to constrain the size of routing tables for an all-informed routing system 2.5.2 Defending the End To End Principle DARPA is funding a project to think about a new architecture for future generation Internet, called NewArch (http://www.isi.edu/newarch/). Work started in the first half of 2000. When this draft was originally published, work was only just getting under way and little in the way of results had been published. Since then significant work has been done both on addressing architectures and a novel routing paradigm. The main conclusion of the the initial work was that as the Internet becomes mainstream infrastructure, fewer and fewer of the requirements are truly global but may apply with different force or not at all in certain parts of the network. This (it is claimed) makes the compilation of a single, ordered list of requirements deeply problematic. Instead we may have to produce multiple requirement sets with support for differing requirement importance at different times and in different places. This 'meta-requirement' significantly impacts architectural design. Potential new technical requirements identified included: - Commercial environment concerns such as richer inter-provider policy controls and support for a variety of payment models - Trustworthiness - Ubiquitous mobility - Policy driven self-organisation ('deep auto configuration') - Extreme short-time-scale resource variability - Capacity allocation mechanisms - Speed, propagation delay and Delay/BandWidth Product issues Non-technical or political 'requirements' include: - Legal and Policy drivers such as o Privacy and free/anonymous speech o Intellectual property concerns Doria & Davies Expires January 17, 2005 [Page 19] Internet-Draft IDR History July 2004 o Encryption export controls o Law enforcement surveillance regulations o Charging and taxation issues - Reconciling national variations and consistent operation in a world wide infrastructure One of the participants in this work (Dave Clark) with one of his associates has also published a very interesting paper analyzing the impact of some of these new requirements on the end-to-end principle that has guided the development of the Internet to date [32]. Their primary conclusion is that the loss of trust between the users at the ends of end to end has the most fundamental effect on the Internet. This is clear in the context of the routing system, where operators are unwilling to reveal the inner workings of their networks for commercial reasons. Similarly, trusted third parties and their avatars (mainly mid-boxes of one sort or another) have a major impact on the end-to-end principles and the routing mechanisms that went with them. Overall, the end to end principles should be defended so far as is possible - some changes are already too deeply embedded to make it possible to go back to full trust and openness - at least partly as a means of staving off the day when the network will ossify into an unchangeable form and function (much as the telephone network has done). The hope is that by that time a new Internet will appear to offer a context for unfettered innovation. In line with a number of other research and discussion streams, the NewArch project appears to be embracing the necessity of separating the locator and identifier functions of today's IP addresses with the resultant consequences for the inter-domain routing system. A number of interesting papers have now been published covering possible modifications to the addressing architecture (FARA) and an alternative inter-domain routing scheme (NIRA). Pointers to these papers can be found on the NewArch website. 3. Existing problems of BGP and the current EGP/IGP Architecture Although most of the people who have to work with BGP today believe it to be a useful, working protocol, discussions have brought to light a number of areas where BGP or the relationship between BGP and the IGPs in use today could be improved. This section is, to a large extent, a wish list for the future domain routing architecture based on those areas where BGP is seen to be lacking, rather than simply a list of problems with BGP. The shortcomings of today's inter-domain routing system have also been extensively surveyed in 'Architectural Requirements for Inter-Domain Routing in the Internet' [13], particularly with respect to its stability and the problems produced by explosions in the size of the Internet. Doria & Davies Expires January 17, 2005 [Page 20] Internet-Draft IDR History July 2004 3.1 BGP and Auto-aggregation The stability and later linear growth rates of the number of routing objects (prefixes) that was achieved by the introduction of CIDR around 1994, has now been once again been replaced by near- exponential growth of number of routing objects. The granularity of many of the objects advertised in the default free zone is very small (prefix length of 22 or longer): This granularity appears to be a by-product of attempts to perform precision traffic engineering related to increasing levels of multi-homing. At present there is no mechanism in BGP that would allow an AS to aggregate such prefixes without advance knowledge of their existence, even if it was possible to deduce automatically that they could be aggregated. Achieving satisfactory auto-aggregation would also significantly reduce the non-locality problems associated with instability in peripheral ASs. On the other hand, it may be that alterations to the connectivity of the net as described in [13] and Section 2.5.1 may limit the usefulness of auto-aggregation 3.2 Convergence and Recovery Issues BGP today is a stable protocol under most circumstances but this has been achieved at the expense of making the convergence time of the inter-domain routing system very slow under some conditions. This has a detrimental effect on the recovery of the network from failures. The timers that control the behavior of BGP are typically set to values in the region of several tens of seconds to a few minutes, which constrains the responsiveness of BGP to failure conditions. In the early days of deployment of BGP, poor network stability and router software problems lead to storms of withdrawals closely followed by re-advertisements of many prefices. To control the load on routing software imposed by these 'route flaps', route flap damping was introduced into BGP. Most operators have now implemented a degree of route flap damping in their deployments of BGP. This restricts the number of times that the routing tables will be rebuilt even if a route is going up and down very frequently. Unfortunately, the effect of route flap damping is exponential in its behavior that can result in some parts of the Internet being inaccessible for hours at a time. There is evidence ([13] and our own measurements - results yet to be published) that in today's network route flap is disproportionately associated with the fine grain prefices (length 22 or longer) associated with traffic engineering at the periphery of the network. Doria & Davies Expires January 17, 2005 [Page 21] Internet-Draft IDR History July 2004 Auto-aggregation as previously discussed would tend to mask such instability and prevent it being propagated across the whole network. Another question that needs to be studied is the continuing need for an architecture that requires global convergence. Some of our studies (yet to be published) show that, in some localities at least, the network never actually reaches stability; i.e. never really globally converges. Can a global, and beyond, network be designed with the requirement of global convergence? 3.3 Non-locality of Effects of Instability and Misconfiguration There have been a number of instances, some of which are well documented of a mistake in BGP configuration in a single peripheral AS propagating across the whole Internet and resulting in misrouting of most of the traffic in the Internet. Similarly, route flap in a single peripheral AS can require route table recalculation across the entire Internet. This non-locality of effects is highly undesirable, and it would be a considerable improvement if such effects were naturally limited to a small area of the network around the problem. This is another argument for an architecture that does not require global convergence. 3.4 Multihoming Issues As discussed previously, the increasing use of multi-homing as a robustness technique by peripheral ASs requires that multiple routes have to be advertised for such domains. These routes must not be aggregated close in to the multi-homed domain as this would defeat the traffic engineering implied by multi-homing and currently cannot be aggregated further away from the multi-homed domain due to the lack of auto-aggregation capabilities. Consequentially the default free zone routing table is growing exponentially, as it was before CIDR. The longest prefix match routing technique introduced by CIDR, and implemented in BGP4, when combined with provider address allocation is an obstacle to effective multi-homing if load sharing across the multiple links is required: If an AS has been allocated its addresses from an upstream provider, the upstream provider can aggregate those addresses with those of other customers and need only advertise a single prefix for a range of customers. But, if the customer AS is also connected to another provider, the second provider is not able to aggregate the customer addresses because they are not taken from his allocation, and will therefore have to announce a more specific route to the customer AS. The longest match Doria & Davies Expires January 17, 2005 [Page 22] Internet-Draft IDR History July 2004 rule will then direct all traffic through the second provider, which is not as required. Example: AS3 has received its addresses from AS1, which means AS1 can aggregate. But if AS3 want its traffic to be seen equally both ways, AS1 is forced to announce both the aggregate and the more specific route to AS3. \ / AS1 AS2 \ / AS3 This problem has induced many ASs to apply for their own address allocation even though they could have been allocated from an upstream provider further exacerbating the default free zone route table size explosion. This problem also interferes with the desire of many providers in the default free zone to route only prefixes that are equal to or shorter than 20 or 19 bits. Note that some problems which are referred to as multihoming issues are not and should not solvable through the routing system (e.g. where a TCP load distributor is needed), and multihoming is not a panacea for the general problem of robustness in a routing system [38]. Since the original publication of this draft the IETF multi6 working group has been struggling to determine how to provide a mechanism to allow multihoming with IPv6 while maintaining the beneficial effects that strict provider addressing brings to the size of the core routing tables. The process has been long and difficult and a full resolution is not yet in sight. The main conclusion has been, as with the NewArch group, that the locator and identifier functions of the IP address will need to be decoupled which was one of the major proposals of the Nimrod project Section 2.2. One major difficulty is that it is not clear how to solve the problem in such a way that the basic structure of IP in general and IPv6 in particular is not compromised. Many of the proposals considered effectively provide an overlay on IP which may not be the most desirable solution but the alternatives might mean designing yet another new version of IP before IPv6 has been fully deployed. 3.5 AS-number exhaustion The domain identifier or AS-number is a 16-bit number. Allocation of Doria & Davies Expires January 17, 2005 [Page 23] Internet-Draft IDR History July 2004 AS-numbers is currently increasing 51% a year [13] with the result that exhaustion is likely around 2005. The IETF is currently studying proposals to increase the available range of AS-numbers to 32 bits, but this will present a deployment challenge during transition. 3.6 Partitioned AS's Tricks with discontinuous ASs are used by operators, for example, to implement anycast. Discontinuous ASs may also come into being by chance if a multi-homed domain becomes partitioned as a result of a fault and part of the domain can access the Internet through each connection. It may be desirable to make support for this kind of situation more transparent than it is at present. 3.7 Load Sharing Load splitting or sharing was not a goal of the original designers of BGP and it is now a problem for today's network designers and managers. Trying to fool BGP into load sharing between several links is a constantly recurring exercise for most operators today. Traffic engineering extensions to the future domain routing architecture that will facilitate load sharing should be considered. 3.8 Hold down issues As with the interval between 'hello' messages in OSPF, the typical size and defined granularity (seconds to tens of seconds) of the 'keep-alive' time negotiated at start-up for each BGP connection constrains the responsiveness of BGP to link failures. The recommended values and the available lower limit for this timer were set to limit the overhead caused by keep-alive messages when link bandwidths were typically much lower than today. Analysis and experiment ([14], [15] & [33]) indicate that faster links could sustain a much higher rate of keep-alive messages without significantly impacting normal data traffic. This would improve responsiveness to link and node failures but with a corresponding increase in the risk of instability, if the error characteristics of the link are not taken properly into account when setting the keep-alive interval. An additional problem with the hold-down mechanism in BGP is the amount of information that has to be exchanged to re-establish the database of route advertisements on each side of the link when it is re-established after a failure. Currently any failure, however brief forces a full exchange which could perhaps be constrained by retaining some state across limited time failures and using revision Doria & Davies Expires January 17, 2005 [Page 24] Internet-Draft IDR History July 2004 control, transaction and replication techniques to re-synchonise the databases. Various techniques have been implemented to try to reduce this problem but they have not yet been standardised. 3.9 Interaction between Inter domain routing and intra domain routing Today, many operators' backbone routers run both I-BGP and an IGP maintain the routes that reach between the borders of the domain. Exporting routes from BGP into IGP and bringing them back up to BGP is not recommended [29], but it is still necessary for all backbone routers to run both protocols. BGP is used to find the egress point and IGP to find the path (next hop router) to the egress point across the domain. This is not only a management problem but may also create other problems: - BGP is a distance vector protocol, as compared with most IGPs, which are link state protocols, and as such it is not optimised for convergence speed although they generally require less processing power. Incidentally, more efficient distance vector algorithms are available such as [34]. - The metrics used in BGP and the IGP are rarely comparable or combinable. Whilst there are arguments that the optimizations inside a domain may be different from those for end-to-end paths, there are occasions, such as calculating the 'topologically nearest' server when computable or combinable metrics would be of assistance. - The policies that can be implemented using BGP are designed for control of traffic exchange between operators, not for controlling paths within a domain. Policies for BGP are most conveniently expressed in RPSL and this could be extended if thought desirable to include additional policy information. - If the NEXT HOP destination for a set of BGP routes becomes inaccessible because of IGP problems, the routes using the vanished next hop have to be invalidated at the next available UPDATE. Subsequently, if the next hop route reappears, this would normally lead to the BGP speaker requesting a full table from its neighbour(s). Current implementations may attempt to circumvent the effects of IGP route flap by caching the invalid routes for a period in case the next hop is restored. - Synchronization between IGP and EGP is a problem as long as we use different protocols for IGP and EGP, which will most probably be the case even in the future because of the differing requirements in the two situations. Some sort of synchronization between those two protocols would be useful. In the draft 'OSPF Transient Blackhole Avoidance' [22], the IGP side of the story is covered. - Synchronizing in BGP means waiting for the IGP to know about the same networks as the EGP, which can take a significant period of time and slows down the convergence of BGP by adding the IGP convergence time into each cycle. Doria & Davies Expires January 17, 2005 [Page 25] Internet-Draft IDR History July 2004 3.10 Policy Issues There are several classes of issue with current BGP policy: - - Policy is installed in an ad-hoc manner in each autonomous system. There isn't a method for ensuring that the policy installed in one router is coherent with policies installed in other routers. - - As described in Griffin [12] and in McPherson [20] it is possible to create policies for ASs, and instantiate them in routers, that will cause BGP to fail to converge in certain types of topology - - There is no available network model for describing policy in a coherent manner. Policy management is extremely complex and mostly done without the aid of any automated procedures. The extreme complexity means that a highly qualified specialist is required for policy management of border routers. The training of these specialists is quite lengthy and needs to involve long periods of hands-on experience. There is, therefore, a shortage of qualified staff for installing and maintaining the routing policies. Also many training courses cover only the basic configuration aspects and do not cover policy issues. 3.11 Security Issues While many of the issues with BPG security have been traced either to implementation issues or to operational issues, BGP is vulnerable to DDOS attacks. Additionally routers can be used as unwitting forwarders in DDOS attacks on other systems. Though DDOS attacks can be fought in a variety of ways, most filtering methods, it is takes constant vigilance. There is nothing in the current architecture or in the protocols that serves to protect the forwarders from these attacks. 3.12 Support of MPLS and VPNS Recently BGP has been modified to function as a signaling protocol for MPLS and for VPNs [16]. Some people see this over-loading of the BGP protocol as a boon whilst others see it as a problem. While it was certainly convenient as a vehicle for vendors to deliver extra functionality for to their products, it has exacerbated some of the performance and complexity issues of BGP. Two important problems are, the additional state that must be retained and refreshed to support VPN tunnels and that BGP does not provide end-to-end notification making it difficult to confirm that all necessary state has been installed or updated. Doria & Davies Expires January 17, 2005 [Page 26] Internet-Draft IDR History July 2004 In creating the future domain routing architecture, serious consideration must be given to the argument that VPN signaling protocols should remain separate from the route determination protocols. 3.13 IPv4 / IPv6 Ships in the Night The fact that service providers would need to maintain two completely separate networks; one for IPv4 and one for IPv6 has been a real hindrance to the introduction of IPv6. When IPv6 does get widely deployed it will do so without causing the disappearance of IPv4. This means that unless something is done, service providers would need to maintain the two networks in, relative, perpetuity. It is possible to use a single set of BGP speakers with multiprotocol extensions [37] to exchange information about both IPv4 and IPv6 routes between domains, but the use of TCP as the transport protocol for the information exchange results in an asymmetry when choosing to use one of TCP over IPv4 or TCP over IPv6. Successful information exchange confirms one of IPv4 or IPv6 reachability between the speakers but not the other, making it possible that reachability is being advertised for a protocol for which it is not present. Also, current implementations do not allow a route to be advertised for both IPv4 and IPv6 in the same UPDATE message, because it is not possible to explicitly link the reachability information for an address family to the corresponding next hop information. This could be improved, but currently results in independent UPDATEs being exchanged for each address family. 3.14 Existing Tools to Support Effective Deployment of Inter-Domain Routing The tools available to network operators to assist in configuring and maintaining effective inter-domain routing in line with their defined policies are limited, and almost entirely passive. - There are no tools to facilitate the planning of the routing of a domain (either intra- or inter-domain); there are a limited number of display tools that will visualize the routing once it has been configured - There are no tools to assist in converting business policy specifications into the RPSL language; there are limited tools to convert the RPSL into BGP commands and to check, post-facto, that the proposed policies are consistent with the policies in adjacent domains (always provided that these have been revealed and accurately documented). Doria & Davies Expires January 17, 2005 [Page 27] Internet-Draft IDR History July 2004 - There are no tools to monitor BGP route changes in real time and warn the operator about policy inconsistencies and/or instabilities. The following section summarises the tools that are available to assist with the use of RPSL. Note they are all batch mode tools used off-line from a real network. These tools will provide checks for skilled inter-domain routing configurers but limited assistance for the novice. 3.14.1 Routing Policy Specification Language RPSL (RFC 2622, 2650) and RIPE NCC Database (RIPE 157) Routing Policy Specification Language RPSL enables a network operator to describe routes, routers and autonomous systems ASs that are connected to the local AS. Using the RPSL language a distributed database is created to describe routing policies in the Internet as described by each AS independently. The database can be used to check the consistency of routing policies stored in the database. Tools exist (RIPE 81, 181, 103) that can be applied on the database to answer requests of the form, e.g. - Flag when two neighboring network operators specify conflicting or inconsistent routing information exchanges with each other and also detect global inconsistencies where possible; - Extract all AS-paths between two networks that are allowed by routing policy from the routing policy database; display the connectivity a given network has according to current policies. The database queries enable a partial static solution to the convergence problem. They analyze routing policies of very limited part of Internet and verify that they do not contain conflicts that could lead to protocol divergence. The static analysis of convergence of the entire system has exponential time complexity, so approximation algorithms would have to be used. 4. Security Considerations As this is an informational draft on the history of requirements in IDR and on the problems facing the current Internet IDR architecture, it does not as such create any security problems. On the other hand, some of the problems with today's Internet routing architecture do create security problems and these have been discussed in the text above. Doria & Davies Expires January 17, 2005 [Page 28] Internet-Draft IDR History July 2004 5. Acknowledgments The draft is derived from work originally produced by Babylon. Babylon was a loose association of individuals from academia, service providers and vendors whose goal was to discuss issues in Internet routing with the intention of finding solutions for those problems. The individual members who contributed materially to this draft are: Anders Bergsten, Howard Berkowitz, Malin Carlzon, Lenka Carr Motyckova, Elwyn Davies, Avri Doria, Pierre Fransson, Yong Jiang, Dmitri Krioukov, Tove Madsen, Olle Pers, and Olov Schelen. Thanks also go to the members of Babylon and others who did substantial reviews of this material. Specifically we would like to acknowledge the helpful comments and suggestions of the following individuals: Loa Andersson, Tomas Ahlstrom, Erik Aman, Thomas Eriksson, Niklas Borg, Nigel Bragg, Thomas Chmara, Krister Edlund, Owe Grafford, Torbjorn Lundberg, Jasminko Mulahusic, Florian-Daniel Otel, Bernhard Stockman, Tom Worster, Roberto Zamparo. In addition, the authors are indebted to the folks who wrote all the references we have consulted in putting this paper together. This includes not only the references explicitly listed below, but also those who contributed to the mailing lists we have been participating in for years. Finally, it is the editors who are responsible for any lack of clarity, any errors, glaring omissions or misunderstandings. 6 References [1] Clark, D., "Policy Routing in Internet Protocols", RFC 1102, May 1989. [2] Estrin, D., "Requirements for Policy Based Routing in the Research Internet", RFC 1125, Nov 1989. [3] Steenstrup, M., "An Architecture for Inter-Domain Policy Routing", RFC 1478, Jun 1993. [4] Little, M., "Goals and Functional Requirements for Inter-Autonomous System Routing", RFC 1126, Jul 1989. [5] Perlman, R., "Interconnections Second Edition", Addison Wesley Longman Inc., 1999. [6] Perlman, R., "Network Layer Protocols with Byzantine Robust-ness", Ph.D Thesis, Department of Electrical Engineering and Computer Science, MIT, Aug 1988. [7] Castineyra, I., Chiappa, N. and M. Steenstrup, "the Nimrod Routing Architecture", RFC 1992, Aug 1996. Doria & Davies Expires January 17, 2005 [Page 29] Internet-Draft IDR History July 2004 [8] Chiappa, N., "IPng Technical Requirements of the Nimrod Routing and Addressing Architecture", RFC 1753, Dec 1994. [9] Chiappa, N., ""A New IP Routing and Addressing Architecture"", , 2002. [10] Wroclowski, J., "The Metanet White Paper - Workshop on Research Directions for the Next Generation Internet", , 1995. [11] Labovitz, C., Ahuja, A., Farnam, J. and A. Bose, "Experimental Measurement of Delayed Convergence", NANOG , 2002. [12] Griffin, T. and G. Wilfong, "An Analysis of BGP Convergence Properties", , 1999. [13] Huston, G., "Commentary on Inter-Domain Routing in the Internet,RFC 3221", , Dec 2001. [14] Alaettinoglu, C., Jacobson, V. and H. Yu, "", draft-alaettinoglu-isis-convergence-00 (work in progress), Nov 2000. [15] Sandick, H., Squire, M., Cain, B., Duncan, I. and B. Haberman, "Fast LIveness Protocol (FLIP)", draft-sandick-flip-00 (work in progress), Feb 2000. [16] Rosen, E. and Y. Rekhter, "BGP/MPLS VPNs", RFC 2547, Mar 1999. [17] Clark, D., Chapin, L., Cerf, V., Braden, R. and R. Hobby, "towards the Future Internet Architecture", RFC 1287, Dec 1991. [18] Jacobson, V., Nichols, K. and K. Poduri, "The 'Virtual Wire' Behavior Aggregate", draft-ietf-diffserv-pdb-vw-00 (work in progress), Jul 2000. [19] Seddigh, N., Nandy, B. and J. Heinanen, "An Assured Rate Per-Domain Behaviour for Differentiated Services", draft-ietf-diffserv-pdb-ar-00 (work in progress), Feb 2001. [20] McPherson, D., Gill, V., Walton, D. and A. Retana, "BGP Persistent Route Oscillation Condition", RFC 3345, Aug 2002. [21] Hain, T., "Architectural Implications of NAT", RFC 2993, Nov 2000. [22] McPherson, D. and T. Przygienda, "OSPF Transient Blackhole Avoidance", draft-mcpherson-ospf-transient-00 (work in progress), Jul 2000. Doria & Davies Expires January 17, 2005 [Page 30] Internet-Draft IDR History July 2004 [23] Thaler, D., Estrin, D. and D. Meyer, "Border Gateway Multicast Protocol (BGMP): Protocol Specification", draft-ietf-bgmp-spec-06 (work in progress), Nov 2000. [24] Rosen, E., "Multiprotocol Label Switching Architecture", RFC 3031, 2004. [25] Ashwood-Smith, P., "Generalized MPLS - Signaling Functional Description", draft-ietf-mpls-generalized-signaling-09 (work in progress), 2002. [26] "IETF Resource Allocation Protocol working group", , 2002, . [27] "IETF Configuration management with SNMP working group", , 2002, . [28] "IETF Policy working group", , 2002, . [29] Yu, J., "Scalable Routing Design Principles", RFC 2791, 2002. [30] "Telcordia Technologies Netsizer web site http://www.netsizer.com/", , 2002. [31] "Inference of Shared Risk Link Groups", draft-many-inference-srlg-02 (work in progress), 2001. [32] Blumenthal, M. and D. Clark, "Rethinking the design of the Internet: The end to end arguments vs", the brave new world , May 2001, . [33] Lang, "Link Management Protocol", draft-lang-mpls-lmp-02 (work in progress), 2000. [34] Xu, Z., Dai, S. and J. Garcia-Luna-Aceves, "A More Efficient Distance Vector Routing Algorithm", Proc IEEE MILCOM 97, Monterey, California, Nov 1997, . [35] Bradner, S. and A. Mankin, "The Recommendation for the IP Next Generation Protocol", RFC 1752, Jan 1995. [36] ISO/IEC, "Protocol for Exchange of Inter-Domain Routeing Information among Intermediate Systems to support Forwarding of ISO 8473 PDUs", International Standard 10747 , 1993. Doria & Davies Expires January 17, 2005 [Page 31] Internet-Draft IDR History July 2004 [37] Bates, T., Rekhter, Y., Chandra, R. and D. Katz, "Multiprotocol Extensions to BGP-4", RFC 2858, Jun 2000. [38] Berkowitz, H. and D. Krioukov, "To Be Multihomed: Requirements and Definitions", draft-berkowitz-multirqmt-02 (work in progress), 2002. [39] Ferguson, P. and H. Berkowitz, "Network Renumbering Overview: Why would I want it and what is it anyway?", RFC 2071, Jan 1997. [40] Berkowitz, H., "Router Renumbering Guide", RFC 2072, Jan 1997. [41] Doria, "Requirements for Inter-Domain Routing", draft-irtf-routing-reqs-03 (work in progress), 2004. Authors' Addresses Avri Doria ETRI 161 Gajeong-dong Yuseong-gu Daejeon 305-350 Korea Phone: +1 401 663 5024 EMail: avri@acm.org Elwyn B. Davies Nortel Networks Harlow Laboratories London Road Harlow, Essex CM17 9NA UK Phone: +44 1279 405 498 Fax: +44 1279 405 514 EMail: elwynd@nortelnetworks.com Doria & Davies Expires January 17, 2005 [Page 32] Internet-Draft IDR History July 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. Doria & Davies Expires January 17, 2005 [Page 33]