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

Versions: 00 01 02 03 04 05 06 07 08 09 10 RFC 5773

IRTF Routing Research                             Avri Doria (co-editor)
Internet Draft                            Lulea University of Technology
                                                Elwyn Davies (co-editor)
                                                         Nortel Networks
Informational Track

Document: draft-irtf-routing-history-00.txt               February, 2002

                  Analysis of IDR requirements and History
                           Group B contribution
                    <draft-irtf-routing-history-00.txt>


Status of this Memo

   This document is an Internet Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.  Internet Drafts are working
   documents of the Internet Engineering Task Force (IETF), its Areas,
   and its Working Groups.  Note that other groups may also distribute
   working documents as Internet Drafts.

   Internet Drafts are draft documents valid for a maximum of six
   months.  Internet Drafts may be updated, replaced, or obsoleted by
   other documents at any time.  It is not appropriate to use Internet
   Drafts as reference material or to cite them other than as a "working
   draft" or "work in progress".

   The list of current Internet-Drafts can be accessed at
        http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories can be accessed at
        http://www.ietf.org/shadow.html.

   Discussion and suggestions for improvement are requested.  This
   document will expire before August, 2002. Distribution of this draft
   is unlimited.

Copyright Notice
   Copyright (C) The Internet Society (2002).  All Rights Reserved.
Abstract

   This draft is the product of Group B, which is one of, at least, two
   subgroups in the IRTF-Routing Research Group working on requirements
   for routing solutions for the future.  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
   draft-irtf-routing-reqs-groupb-00.txt, which is a discussion of
   requirements for the future routing architecture and future routing
   protocols.






 Group B                                                               1

INTERNET DRAFT                IDR History                 February, 2002

Acknowledgements

   The draft is derived from draft-davies-fdr-reqs-01.txt, which was
   produced by Babylon.  Babylon is a loose association of individuals
   from academia, service providers and vendors whose goal is to discuss
   issues in Internet routing with the intention of finding solutions
   for those problems.

   The individual members who contributed text 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 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 Ahlstr÷m, Niklas Borg, Nigel Bragg, Thomas Chmara,
   Krister Edlund, Owe Grafford, Torbj÷rn 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, all errors, any omissions or misunderstandings.


Changes from Draft-davies-fdr-reqs-01.txt

   - The Future Domain Routing requirements have been separated into
   another I-D. This ID is being presented as one of the contributions
   to the IRTF for consideration as a RG document.




















Group B                  Expires: September 2002                      2

INTERNET DRAFT                IDR History                 February, 2002

    CONTENTS

   1. Introduction....................................................4
      1.1  Background.................................................4
   2. Historical Perspective..........................................5
      2.1  The legacy of RFC1126......................................5
      2.2  Nimrod Requirements.......................................15
      2.3  PNNI......................................................17
      2.4  Recent Research Work......................................17
   3. Existing problems of BGP and the current EGP/IGP Architecture..19
      3.1  BGP and Auto-aggregation..................................20
      3.2  Convergence and Recovery Issues...........................20
      3.3  Non-locality of Effects of Instability and Misconfiguration21
      3.4  Multihoming Issues........................................21
      3.5  AS-number exhaustion......................................22
      3.6  Partitioned AS's..........................................22
      3.7  Load Sharing..............................................22
      3.8  Hold down issues..........................................22
      3.9  Interaction between Inter domain routing and intra domain
              routing................................................23
      3.10    Policy Issues..........................................24
      3.11    Security Issues........................................24
      3.12    Support of MPLS and VPNS...............................25
      3.13    IPv4 / IPv6 Ships in the Night.........................25
      3.14    Existing Tools to Support Effective Deployment of Inter-
              Domain Routing.........................................25
   4. References.....................................................27
   5. Author's Addresses.............................................30



























Group B                  Expires: September 2002                      3

INTERNET DRAFT                IDR History                 February, 2002

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
   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

Group B                  Expires: September 2002                      4

INTERNET DRAFT                IDR History                 February, 2002

   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.

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:

      Optionally, 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].



Group B                  Expires: September 2002                      5

INTERNET DRAFT                IDR History                 February, 2002

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.

   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


Group B                  Expires: September 2002                      6

INTERNET DRAFT                IDR History                 February, 2002

              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.

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


Group B                  Expires: September 2002                      7

INTERNET DRAFT                IDR History                 February, 2002

              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"

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.



Group B                  Expires: September 2002                      8

INTERNET DRAFT                IDR History                 February, 2002

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 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"



Group B                  Expires: September 2002                      9

INTERNET DRAFT                IDR History                 February, 2002

   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.

   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.

Group B                  Expires: September 2002                      10

INTERNET DRAFT                IDR History                 February, 2002


   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 locations to minimise the cost of routing if
              bandwidth is cheaper than processing.



Group B                  Expires: September 2002                      11

INTERNET DRAFT                IDR History                 February, 2002

   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.

   Current practice: BGP-4 allows for arbitrary interconnections.

2.1.2.5 "General Objectives"


Group B                  Expires: September 2002                      12

INTERNET DRAFT                IDR History                 February, 2002

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"³

   Requirement: 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.

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?

Group B                  Expires: September 2002                      13

INTERNET DRAFT                IDR History                 February, 2002


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.

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.



Group B                  Expires: September 2002                      14

INTERNET DRAFT                IDR History                 February, 2002

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
              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


Group B                  Expires: September 2002                      15

INTERNET DRAFT                IDR History                 February, 2002

   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.

   It is certain that these goals should be considered requirements for
   any new domain routing architecture.

     - 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
   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

Group B                  Expires: September 2002                      16

INTERNET DRAFT                IDR History                 February, 2002

   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?

   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 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 pending. Any volunteers to write this section?]

2.5 Recent Research Work



Group B                  Expires: September 2002                      17

INTERNET DRAFT                IDR History                 February, 2002

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.
   - 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 but the published results are limited.

   The main development so far is to conclude 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

Group B                  Expires: September 2002                      18

INTERNET DRAFT                IDR History                 February, 2002

   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 so far include:
   - 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
       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.

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],

Group B                  Expires: September 2002                      19

INTERNET DRAFT                IDR History                 February, 2002

   particularly with respect to its stability and the problems produced
   by explosions in the size of the Internet.

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.
   Auto-aggregation as previously discussed would tend to mask such
   instability and prevent it being propagated across the whole network.


Group B                  Expires: September 2002                      20

INTERNET DRAFT                IDR History                 February, 2002

   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
   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


Group B                  Expires: September 2002                      21

INTERNET DRAFT                IDR History                 February, 2002

      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].

3.5 AS-number exhaustion

   The domain identifier or AS-number is a 16-bit number. Allocation of
   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


Group B                  Expires: September 2002                      22

INTERNET DRAFT                IDR History                 February, 2002

   '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
   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.


Group B                  Expires: September 2002                      23

INTERNET DRAFT                IDR History                 February, 2002

   -  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.

3.10Policy 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.11Security 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

Group B                  Expires: September 2002                      24

INTERNET DRAFT                IDR History                 February, 2002

   in the current architecture or in the protocols that serves to
   protect the forwarders from these attacks.

3.12Support 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.

   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.13IPv4 / 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.14Existing 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.

   For example:

Group B                  Expires: September 2002                      25

INTERNET DRAFT                IDR History                 February, 2002

   -  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).
   -  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.







Group B                  Expires: September 2002                      26

INTERNET DRAFT                IDR History                 February, 2002



4. References

   The following were consulted in the writing of this document.  Not
   all are specifically referred to in the document, but all helped in
   forming this work.  These references are not intended as normative.

     [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,
                    November 1989.

     [3]            Steenstrup, M,. "An Architecture for Inter-Domain
                    Policy Routing",  RFC 1478, June 1993

     [4]            Little, M., "Goals and Functional Requirements
                    for Inter-Autonomous System Routing", RFC 1126,
                    July 1989.

     [5]            Perlman, R., "Interconnections Second Edition",
                    1999, Addison Wesley Longman, Inc.

     [6]            Perlman, R., "Network Layer Protocols with
                    Byzantine Robust-ness", Ph.D. Thesis, Department
                    of Electrical Engineering and Computer Science,
                    MIT, August 1988.

     [7]            Castineyra, I., Chiappa, N., Steenstrup, M., "the
                    Nimrod Routing Architecture", RFC1992, Aug 1996

     [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"

     [10]           Wroclowski, J., The Metanet White Paper -
                    Workshop on Research Directions for the Next
                    Generation Internet, 1995

     [11]           Labovitz, C., Ahuja, A., Farnam J., Bose, A.,
                    Experimental Measurement of Delayed Convergence,
                    NANOG

     [12]           Griffin, T.G., Wilfong, G., An Analysis of BGP
                    Convergence Properties, SIGCOMM 1999

     [13]           Huston, G., Commentary on Inter-Domain Routing in
                    the Internet,RFC 3221, Dec 2001


Group B                  Expires: September 2002                      27

INTERNET DRAFT                IDR History                 February, 2002

     [14]           Alaettinoglu, C.,  Jacobson, V. and Yu, H, ,
                    Towards Milli-Second IGP Convergence, Internet
                    Draft - draft-alaettinoglu-isis-convergence-00,
                    Nov 2000 Work in Progress

     [15]           Sandick, H., Squire, M., Cain, B., Duncan, I.,
                    Haberman, B., Fast LIveness Protocol (FLIP),
                    Internet Draft - draft-sandiick-flip-00,
                    Feb 2000, Work in Progress

     [16]           Rosen, E. and Rekhter, Y., BGP/MPLS VPNs,
                    RFC2547, March 1999

     [17]           Clark, D., Chapin, L., Cerf, V., Braden, R.,
                    Hobby, R., "towards the Future Internet
                    Architecture", RFC1287, December 1991

     [18]           Jacobson, V., Nichols, K. and Poduri, K., The
                    'Virtual Wire' Behavior Aggregate, Internet Draft
                    - draft-ietf-diffserv-pdb-vw-00, July 2000, Work
                    in Progress

     [19]           Seddigh, N., Nandy, B., and Heinanen, J.,
                    An Assured Rate Per-Domain Behaviour for
                    Differentiated Services, Internet Draft -
                    draft-ietf-diffserv-pdb-ar-00, Feb 2001, Work in
                    Progress

     [20]           McPherson, D., Gill, V., Walton, D. and Retana,
                    A., "BGP Persistent Route Oscillation Condition",
                    Internet Draft - draft-mcpherson-bgp-route-
                    oscillation-00, Dec 2000, Work in Progress

     [21]           Hain, T, "Architectural Implications of NAT", RFC
                    2993, November 2000

     [22]           McPherson, D. and Przygienda, T., OSPF Transient
                    Blackhole Avoidance, Internet Draft - draft-
                    mcpherson-ospf-transient-00, July 2000 Work In
                    Progress

     [23]           Thaler, D., Estrin, D. and Meyer, D. (editors),
                    Border Gateway Multicast Protocol (BGMP):
                    Protocol Specification, Internet Draft - draft-
                    ietf-bgmp-spec-02, Nov 2000 Work in progress

     [24]           Rosen, E. Et al., Multiprotocol Label Switching
                    Architecture, RFC 3031

     [25]           Ashwood-Smith, P. Et al., Generalized MPLS -
                    Signaling Functional Description, Internet Draft
                    - draft-ietf-mpls-generalized-signaling-01.txt,
                    Work in progress


Group B                  Expires: September 2002                      28

INTERNET DRAFT                IDR History                 February, 2002

     [26]           IETF Resource Allocation Protocol working group,
                    http://www.ietf.org/html.charters/rap-
                    charter.html

     [27]           IETF Configuration management with SNMP working
                    group,
                    http://www.ietf.org/html.charters/snmpconf-
                    charter.html

     [28]           IETF Policy working group,
                    http://www.ietf.org/html.charters/policy-
                    charter.html

     [29]           Yu J., "Scalable Routing Design Principles", RFC
                    2791

     [30]           Telcordia Technologies Netsizer web site
                    http://www.netsizer.com/

     [31]           Inference of Shared Risk Link Groups,
                    draft-many-inference-srlg-00.txt,
                    Work in progress

     [32]           Blumenthal, Marjory S. and Clark, David D.,
                    Rethinking the design of the Internet:
                    The end to end arguments vs. the brave new world,
                    May 2001,
                    http://ana-www.lcs.mit.edu/anaweb/papers.html

     [33]           Lang et al, Link Management Protocol,
                    draft-lang-mpls-lmp-02.txt,
                    Work in progress

     [34]           Xu, Z., Dai, S. and Garcia-Luna-Aceves, J.J.,
                    A More Efficient Distance Vector Routing
                    Algorithm, Proc. IEEE MILCOM 97, Monterey,
                    California, November 2-5, 1997,
                    http://www.cse.ucsc.edu/research/ccrg/
                    publications/zhengyu.milcom97.pdf

     [35]           Bradner, S. and Mankin, A., "The Recommendation
                    for the IP Next Generation Protocol", RFC 1752,
                    January 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,
                    ISO/IEC JTC 1,Switzerland 1993

     [37]           Bates, T., Rekhter, Y., Chandra, R. and Katz, D,
                    "Multiprotocol Extensions to BGP-4",
                    RFC2858, June 2000


Group B                  Expires: September 2002                      29

INTERNET DRAFT                IDR History                 February, 2002

     [38]           Berkowitz, H. and Krioukov, D, "To Be Multihomed:
                    Requirements and Definitions",
                    draft-berkowitz-multirqmt-02.txt,
                    Work in progress.

     [39]           Ferguson, P. and Berkowitz, H. "Network
                    Renumbering Overview: Why would I want it and
                    what is it anyway?", RFC2071, January 1997

     [40]           Berkowitz, H., "Router Renumbering Guide",
                    RFC2072, January 1997

     [41]           [FDR-REQS] Doria (ed), draft-groupb-irtf-rr-reqs-
                    00.txt, work in progress

5. Author's Addresses


  Elwyn Davies
  Nortel Networks
  London Road
  Harlow, Essex CM17 9NA
  UK
  Phone: +44-1279-405498
  Email:  elwynd@nortelnetworks.com

  Avri Doria
  Div. of Computer Communications
  Lulea University of Technology
  S-971 87 Lulea
  Sweden
  Phone: (+46) 920 46 3030
  Email: avri@sm.luth.se

  Howard Berkowitz
  Gett Communications
  5012 25th Street South
  Arlington, VA 22206
  USA
  Phone +1 703 998 5819
  Email: hcb@gettcomm.com


  Dmitri Krioukov
  Nortel Networks
  2325 Dulles Corner Boulevard
  11th Floor
  Herndon
  VA 20171, USA
  Phone: +1 571 331 1104
  Email: dima@krioukov.net




Group B                  Expires: September 2002                      30

INTERNET DRAFT                IDR History                 February, 2002

  Malin Carlzon
  Royal Institute of Technology
  Network Operating Centre
  KTHNOC
  SE-100 44 Stockholm
  Sweden
  Phone: +46 70 269 6519
  Email: malin@sunet.se

  Anders Bergsten
  Telia Research AB
  Aurorum 6
  S-977 75 Lulea
  Sweden
  Phone: +46 920 754 50
  Email: anders.p.bergsten@telia.se

  Olle Pers
  Telia Research AB
  S- 123 86 Farsta
  Sweden
  Phone: +46 8 713 8182
  Email: olle.k.pers@telia.se

  Yong Jiang
  Telia Research AB
  S- 123 86 Farsta
  Sweden
  Phone: +46 8 713 8125
  Email: yong.b.jiang@telia.se

  Lenka Carr Motyckova
  Div. of Computer Communications
  Lulea University of Technology
  S-971 87 Lulea
  Sweden
  Phone: +46 920 91769
  Email: lenka@sm.luth.se

  Pierre Fransson
  Div. of Computer Communications
  Lulea University of Technology
  S-971 87 Lulea
  Sweden
  Phone: +46 70 646 0384
  Email: pierre@cdt.luth.se

  Olov Schelen
  Div. of Computer Communications
  Lulea University of Technology
  S-971 87 Lulea
  Sweden
  Phone: +46 70 536 2030
  Email: Olov.Schelen@cdt.luth.se

Group B                  Expires: September 2002                      31

INTERNET DRAFT                IDR History                 February, 2002

   Tove Madsen
   Utfors Bredband AB
   R…sundav„gen 12
   P.O. Box 525
   SE-169 29 Solna
   Sweden
   Phone: +46 8 5270 5040
   Email: tove.madsen@utfors.se















































Group B                  Expires: September 2002                      32


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