Border Gateway Protocol-Conformance and Performance Testing

• Introduction
• What is BGP?
  • Internal and External BGP
  • Historical Perspective
• How Does BGP Work?
  • Protocol Overview
  • AS Consistency
  • BGP Route Advertisement
  • Route Flap Damping
  • BGP Path Selection
  • BGP Policies and Traffic Engineering
  • BGP Attributes
• BGP Extensions
  • Route Reflectors
  • As Confederations
  • BGP Multi-Protocol Extensions
  • BGP-MPLS VPN Support
  • Extension for IPv6
  • BGP Security
• BGP Testing
  • Why test for BGP conformance and interoperability?
  • Why test for BGP scalability and performance?
• Ixia's approach to BGP testing
  • Conformance testing
  • IxANVL™
  • Protocol Emulations
  • IxExplorer™
  • IxScriptMate™
• Conclusion
• Test Plans
  1. BGP Conformance Test
  2. BGP Route Capacity Test
  3. BGP Route Convergence Test
  4. BGP Dampening Test
  5. BGP Graceful Restart Test
• Glossary
• Bibliography
• Ackowledgements

Copyright (c) 1998-2004 Ixia. All rights reserved.

The information in this document is furnished for informational use only, is subject to change without notice, and should not be construed as a commitment by Ixia. Ixia assumes no responsibility or liability for any errors or inaccuracies that may appear in this document.

Ixia and the Ixia logo are trademarks of Ixia. All other companies, product names, and logos are trademarks or registered trademarks of their respective holders.


Border Gateway Protocol: Conformance and Performance Testing

Introduction

The relentless evolution of the Internet continues to transform the way individuals, as well as businesses, educational institutions, and government organizations access, share, and communicate information. Convergence of digital voice, video, and data, is further consolidating the Internet as a critical infrastructure. One of the main routing protocols in the Internet and current de facto standard is the Border Gateway Protocol (BGP). Presently ubiquitous, BGP is a critical component of the exponentially growing network of routers that constitutes our contemporary Internet. Carrier networks, as well as most large enterprise organizations with multiple links to one or more service providers use BGP.


The increasing popularity of BGP stems from its broad ability to distribute reachability information by selecting the best route to each destination according to policies specified by network administrators. To manage the complexity of BGP, however, a wide range of services, applications, and hardware must be tested and validated. Indeed, a comprehensive and well-designed conformance and performance testing solution is crucial to successful BGP deployment.

BGP is a protocol for facilitating communications between routers in different autonomous systems. An autonomous system (AS) is a network or group of networks under a shared technical administration and with common routing policies.

Network traffic in an AS is classified as either local traffic or transit traffic. Local traffic either comes from or terminates in that AS, where either the IP host source address or destination address reside. Any other traffic traversing that AS constitutes "transit traffic." A major goal of BGP usage in the Internet is to reduce transit traffic.

BGP advertises routes as a "promise" to carry data to the address space indicated by the IP prefix of the announced route. Generally, all routes in a BGP routing table outline Internet network connections. When a BGP router advertises to a neighbor that it has a path for reaching a specific IP prefix, the neighbor can be confident that the advertising BGP speaker is actively using that path to reach the target destination. Route advertisements in BGP use the AS-Path attribute to announce current routing to neighbor BGP speakers, which includes a list of all transit ASs that must be used to reach the target network. By carrying path information associated with a given destination between autonomous systems, BGP enables loop-free inter-domain routing.


BGP conveys information about AS-Path topologies and achieves inter-AS routing without constraining the underlying network topology. An intra-AS routing protocol--that is, Interior Gateway Protocol (IGP), examples of which are Routing Information Protocol (RIP), Open Shortest Path First (OSPF), etc.--provides the routing within an autonomous system. In some circumstances, BGP is used to exchange routes within an AS. In those cases, it is called Internal BGP (I-BGP), as opposed to External BGP (E-BGP) when used between ASs.

Internal and External BGP

A BGP router can communicate with other BGP routers in its own AS or in other ASs. Both the I-BGP and E-BGP implement the BGP protocol with a few different rules. All I-BGP-speaking routers within the same AS must peer with each other in a fully connected mesh. They are not required to be physical neighbors, just to keep a TCP connection as a reliable transport mechanism. Because there is no loop detection mechanism in I-BGP, all I-BGP-speaking routers must not forward any 3rd-party routing information to their peers. In contrast, E-BGP routers are able to advertise 3rd-party information to their E-BGP peers, by default.

The following figure shows routers R1, R2, and R3 using I-BGP to exchange routing information within the same AS, and router pairs R4-R2, R3-R5, and R4-R5 using E-BGP to exchange routing information between ASs.







Figure 1. Internal BGP (I-BGP) versus external BGP (E-BGP).

Historical Perspective

Originally defined in RFC 1105, BGP became an Internet standard in 1989. It replaced the older Exterior Gateway Protocol (EGP) used on the ARPANET, becoming the EGP of choice for inter-domain routing. Since then, BGP has gone through several enhancement cycles and extensions. In 1990, it was updated to BGP-2 by RFC 1163; and in 1991, it was updated to BGP-3 by RFC 1267. The current version of the Border Gateway Protocol, BGP-4, was defined in RFC 1771 and adopted in 1995. All prior versions are now obsolete.


Several extensions for BGP-4 have been proposed since then. RFC 2283 defines BGP-4+, which includes IPV6 prefix advertisement and other important enhancements, increasingly supported by most Network Equipment Manufacturers. Another proposed extension is BGP's graceful restart capability, to improve recovery times and reduce the effect of software and equipment failures on IP routing. Multiple academic and industry-based contributions coordinated through IETF RFCs continue to modify and expand the scope of BGP.

The foundation of BGP is an asynchronous, distributed, preferred-path vector algorithm that uses TCP as its transport protocol. In contrast with OSPF and RIP, the use of TCP as BGP's transport protocol guarantees transport reliability (such as retransmission) and eliminates the additional complexity related to designing reliability into the protocol itself. BGP protocol data units are enclosed within TCP packets and the reliable transport layer protocol is used for acknowledgement, sequencing, fragmentation, and retransmission. After setting up a BGP session and exchanging initial routes, BGP peers trade incremental routing and notification updates.

Protocol Overview

Routers that run a BGP routing process are often referred to as BGP speakers . A pair of BGP-speaking routers that form a TCP connection to exchange routing information between them are called BGP neighbors or peers . A single router can participate in many peering sessions at any given time. Each BGP session takes place exactly between two nodes, where two routers exchange routing information dynamically, over TCP port 179.

For any two BGP peers in a network to be able to send and receive traffic with each other, all intermediate BGP routers have to forward traffic such that the packets get closer to the destination. Because there can be multiple paths to a given target, BGP routers use a routing table to store all known topology information about the network. Based on its routing table, each BGP router selects the best route to use for every known network destination. That information is stored in a forwarding table together with the outgoing interface for the selected best path.

With BGP, it is not necessary to refresh routing information as with many other routing protocols. Instead, when a router advertises a prefix to one of its BGP neighbors, that information is considered valid until the first router explicitly advertises that the information is no longer valid or until the BGP session itself is lost or closed. It is assumed that the transport connection will deliver all data and eventually close properly in case of an error notification.


There are four possible message types used with BGP, all consisting of a standard header plus specific packet-type contents:

• OPEN: First message to open a BGP session, transmitted when a link to a BGP neighbor comes up. It contains AS number (ASN) and IP address of the router who has sent the message.
  
  
• UPDATE: Message embracing routing information, including path attributes. It contains Network Layer Reachability Information (NLRI), listing IP addresses of new usable routes as well as routes that are no longer active or viable and including both the lengths and attributes of the corresponding paths.
  
  
• NOTIFICATION: Final message transmitted on a link to a BGP neighbor before disconnecting. It usually describes atypical conditions prior to terminating the TCP connection, and provides a mechanism to gracefully close a connection between BGP peers.
  
  
• KEEP-ALIVE: Periodic message between BGP peers to inform neighbor that the connection is still viable by guaranteeing that the transmitter is still alive. It is an application type of message that is independent of the TCP keep-alive option.


The BGP protocol has four main stages:


1. Opening and confirming a BGP connection with a neighbor router. After two BGP peers establish a TCP connection, each one sends an OPEN message to the other.
   
   
2. Maintaining the BGP connection. A BGP router can detect a link or BGP peer host failure through the exchange of periodic keep-alive messages with the peer router. An error is assumed when no messages have been exchanged for the hold timer period. The hold timer period is calculated the smaller of its configured hold time setting and the hold time value received in the OPEN message. BGP utilizes periodic keep-alive messages to ensure that the connection between neighbors does not time out. Keep-alive packets are small header-only BGP packets without any routing data.
   
   
3. Sending reachability information. Routing information is advertised between a pair of BGP neighbors in update messages. Each update message may simultaneously advertise a single feasible route to a neighbor and indicate withdrawal of several infeasible routes from service. Update messages contain NLRI with a list of <length, prefix> tuples designating reachable destinations, and path attributes, including degree of preference for each particular route, and the list of ASs that the route has traversed.
   
   
4. Notifying error conditions. Notification messages are sent to a neighbor router when error conditions (incompatibility, configuration, etc.) are detected. Notification messages consist of a main error code and a more detailed sub-code. Through the notification mechanism, a graceful close guarantees the delivery of all outstanding messages prior to closing the underlying TCP session.


AS consistency

BGP mandates that each AS providing transit to other ASs expose the same view to all other AS's using its services. All BGP speakers of a given AS must be consistent in their representation of the topologies both intra-AS and inter-AS. However, BGP does not specify which method should be used to reach, maintain, and enforce the consistency. For example, OSPF can be used to synchronize router databases for intra-AS topology consistency, and rely on BGP itself can be used for inter-AS topology consistency.

BGP Route Advertisement

After establishing a TCP connection, two adjacent BGP speakers exchange full routing information. Each BGP router may receive multiple advertisements for the same route from multiple sources. Based on the described paths, the router filters them and selects only one as the best path, puts it in its IP routing table, and propagates the path to its neighbors. By sending a route announcement to a neighbor, the advertising BGP router is implicitly agreeing to forward IP traffic to the destination network on behalf of the neighbor. If a BGP router determines that a route is inaccessible, it informs all its BGP neighbors of the withdrawal of the route. When a BGP speaker determines that a route has changed or that a new path for the same prefix is chosen, it advertises the replacement route without requiring a route withdrawal.

For every neighboring BGP speaker, the administrator of a BGP router may set input policy filters to sort out route advertisements and perform attribute manipulation. For example, the filter could allow only advertisements such that paths going through a specific AS will not be used, or that include trustworthy ASs in the AS-Path, leaving out all other route notifications. The BGP routing table consists of only accepted routes that pass through the route-advertisement input filter; duplicates are not included.

A BGP router sends at most one route per destination to its BGP peers. It uses output filters to choose the destinations that will be advertised to each BGP neighbor, and leaves out routes that will not be advertised to one or more neighbors. BGP routers can be configured to modify route attributes before sharing routing information with a particular BGP peer. A BGP speaker can use a particular route while simultaneously choosing not to announce it to an external peer. If the peer has previously received an announcement for it, then the routing BGP speaker must report to the external peer that the previous route is now no longer available.

BGP routers use a table version number to keep track of their present routing table instance, incrementing the number every time the routing table changes. Rapid increase of table version numbers frequently indicates network instability. Therefore, route flap damping and other mechanisms have been implemented to cope with unstable networks that cause rapid table version number increases for any BGP speaker with access to the Internet routing tables. Nonetheless, such rapid increases are typical of large carrier networks connected to a great number of BGP speakers.

Route Flap Damping

Recommended in RFC 2439, BGP supports route flap damping (RFD) to reduce the impact of problems to a localized area in the network. RFD minimizes the instability caused by route flapping by suppressing the propagation of unstable BGP routes. The main parameters characterizing RFD are:
• Penalty: Metric that is incremented every time a route flaps. It is decremented over time at a given rate.
  
  
• Half-life time: Rate at which the penalty value is to be reduced to half the current value.
  
  
• Suppress limit: Threshold above which a route is suppressed.
  
  
• Reuse limit: Threshold below which a suppressed route is reclaimed.
RFD's goal is to reduce router-processing overhead due to instability without sacrificing convergence time for stable routes. Damping is not set up per path but per prefix. To achieve effective stabilization, BGP must distinguish between persistently unstable routes and those routes that only occasionally fail.

BGP Path Selection

BGP uses a preferred path-vector (PV) algorithm, described in RFC 1322, that itemizes the complete path to a destination. The PV routing algorithm supplements the advertisement of reachable destinations with information that describes various properties of the paths to these destinations. A path is the recorded sequence of ASNs through which the reachability information has passed. Each AS is considered equal, independent of its size and internal composition.

Different autonomous domains can have different route optimality notions. This is because PV only standardizes the results of route selection while allowing heterogeneous criteria across domains. Each AS can have its own policies for route selection. To prevent forming loops, BGP routers ignore any routing advertisement that contains their own ASN anywhere in the AS-Path. To originate a route, a BGP router creates an empty--null--path and advertises it to its neighboring BGP routers with its ASN prepended to the otherwise empty AS-Path.

BGP uses the shortest AS-Path routing criterion (lowest number of ASs that the route has traversed through) by default. However, "shortest" does not always mean "best" path to reach a destination prefix. Because the underlying network topology is unknown to BGP, a single AS hop could in fact correspond to multiple router hops. Further, default BGP routing is oblivious to network performance metrics, ignoring network parameters as congestion, packet loss, delay, and jitter. Tuning BGP for optimal or near-optimal routing depends on policies to modify the default behavior, and to allow for the best performing paths even when those are not the shortest ones.





Figure 2. Which is the shortest path? BGP considers AS1-AS5-AS4 shorter than AS1-AS2-AS3-AS4 because it only counts AS hops and not internal router hops.

BGP routers use several route parameters, described by BGP attributes, to delineate routing policies. In addition to BGP attributes, BGP-4 introduced route aggregation mechanisms to reduce the size of the Internet routing tables. The aggregation technique is called classless inter-domain routing (CIDR) (or supernetting). CIDR represents IP addresses with common high-order bits by using shortened subnet masks. For routing purposes, only bits covered by the subnet mask are used, thus making all aggregated addresses to look like members of the same network.

Route calculations are influenced by re-configurable router settings that specify route preferences. For example, the preferences may specify that a destination not be advertised to some neighboring BGP speakers, or that a path through a given AS should not be used or should be edited when passing it to a specific neighbor.

BGP Policies and Traffic Engineering

BGP provides mechanisms for policy-based routing, which enables BGP routers to rank routes and control information redistribution according to their administrator's preference. BGP carries out policy routing by filtering certain routes, based on IP-prefix, AS-Path, or other attributes; or by adjusting selected attributes to influence the route selection process. Policies are not part of the protocol; they are decisions made by the AS administrator, and are specified to BGP by the AS administrator in configuration files. Routing policies are often coupled to security, economic, regulatory, or political considerations.

Through policy-based routing, BGP enables different implementations to specify path selection rules when many options are present and to control information distribution. Beyond using the routing table longest match criterion (which uses the routing table entry table that most specifically matches the target destination) and the shortest AS path, different vendors implement the BGP path selection criteria by checking BGP attributes in a slightly different order. In all cases, when a route is advertised, the ASN of the advertising router is added to the route. By stamping the sequence of ASNs, an AS-Path traces how the route became known to any of the routes in the trail.

One of the advantages of BGP's policy routing is that filtering is a local technique. Thus, changes can be applied promptly and without advertising the policy. However, while policy localization reduces the control overhead of the protocol, the absence of synchronized policies and lack of global information often leads to sub-optimal route selection.

BGP implementations assume that there is a local method of managing a BGP router, constructing a function that takes as input all the information advertised in a BGP update message about a particular destination and outputting a number. After different possible routes are mapped to numbers, the routes can be compared. The preferred route is the one that maps to the smallest number.

本消息共4页,当前在第1页  1  2  3  4