SSF Implementation of BGP-4 v1.5.0


Contents
1 Background
2 Implementation Summary and Notes
3 Known Shortcomings
4 Configuration
5 Source Code
6 Examples
7 Validation
8 Questions and Help
9 References
10 Authors

1 Background

The Border Gateway Protocol (BGP) is the de facto standard inter-domain routing protocol in today's global Internet. Its purpose is to build up forwarding tables (often incorrectly referred to as "routing tables") to be used by a router when forwarding data packets around an internetwork. It does so in a distributed fashion: all routers running BGP in the entire internetwork share reachability information with each other. When faced with multiple routes to the same destination, a selection is made based on several factors, many of which can be configured by the administrator. Most commonly, shortest autonomous system (AS) path length is the primary factor.

"Gateway" is simply a dated term for a router. A "border gateway", then, is a router on the "border" of an autonomous system (an administrative domain, roughly). That is to say, it handles routing between its AS and neighboring ASes, but it does not deal with routing internal to the AS (that's left to intra-domain routing protocols, such as OSPF).

Routing should not be confused with forwarding. Routing is the process of building up repositories of information about routes. Forwarding is the process of using this information to direct packets toward their destinations (forwarding is basically just doing a look-up in a table). It is for this reason that the term "forwarding table" is preferred to "routing table" when referring to the repository of route information.

It should be noted that although BGP does not perform intra-domain routing, two routers in the same AS which both run BGP can communicate with each other using BGP (in fact, they must). There are slightly different rules for BGP communication of this nature, and two communicatiing BGP routers in the same AS are said to have an internal BGP (IBGP) session with each other. It should be noted that IBGP is not a protocol itself, but merely a part of BGP. Similarly, BGP sessions between ASes are sometimes referred to as external BGP (EBGP) sessions, in order to distinguish them from IBGP sessions. The purpose of IBGP is to make sure that if there are multiple routers running BGP in the same AS, the routing information between each of them is kept synchronized.

2 Implementation Summary and Notes

The specifications upon which this implementation is based are given in the Internet Engineering Task Force's Request for Comments number 1771 (RFC 1771), "A Border Gateway Protocol 4" [1]. Following are the details of the implementation and how it differs from this specification.

2.1 IBGP/EBGP This implementation simulates both Internal BGP and External BGP (see Background). Route reflection--an extension for IBGP--has also been implemented [6]. (See section 9.2.1 of RFC 1771 for a discussion of Internal BGP.)

2.2 RIB The Routing Information Base (RIB), which stores route information, is implemented with a type of binary tree called a radix tree (the specification leaves the specific implementation of the RIB up to the implementor). As described in section 3.2 of RFC 1771, there are three sections to the RIB, each of which has been implemented in compliance with the specification.

2.3 Messages All message types used by BGP (Open, Update, Notification, and KeepAlive) contain the same fields as given in the specification, with a few exceptions. Fields which specify the length in bytes of a message and any fields used for authentication have been omitted. In addition, no attempt is made to make fields the exact size (in number of bits or bytes) as given in the specification, as these are irrelevant in the simulation.

2.4 Error Handling No error handling (as per section 6 of the specification) is implemented. Error handling is typically used for catching syntactical errors in messages.

2.5 Update Message Handling The handling of Update messages (the type which carry route information) is fully implemented.

2.6 Path Attributes All standard path attributes have been implemented, though some have not been extensively tested.

2.7 Timers All five timers used by BGP are implemented, with time interval defaults as suggested in Appendix section 6.4 of RFC 1771.

2.8 Jitter RFC 1771 requires that three of the timers be jittered (Minimum AS Origination, Keep Alive, and Minimum Route Advertisement--see section 9.2.2.3). Jitter on any or all of them can be turned off by using the proper configuration parameters (see Configuration).

2.9 Finite State Machine The primary behavior of BGP is defined in one method which handles all BGP messages and events (method BGPSession.handle_event()). It reacts to the incoming message/event based on its type and the current state of BGP. From here, some helper methods may be called to manipulate the RIB and to compose and send messages, if necessary.

2.10 Route Reflection Route reflection, which is a BGP extension [6], is fully implemented.

2.11 Policy (Route Filtering) This implementation also supports, in addition to the core required behaviors, a policy configuration (route filtering) scheme along the lines of those used by well-known vendors and following the suggestions in RFC 1772 [3]. This feature has not yet been exercised as fully as most others, and should be used with care.

2.12 Route Flap Damping Support for route flap damping, as described in RFC 2439 [9] and RIPE 210 [10], is included.

2.13 Validation All of the required behaviors of BGP have been implemented to our knowledge, though we are still constantly evaluating and testing it to attempt to verify its correctness. To this end, a series of validation tests have been composed which exercise these required behaviors.

3 Known Shortcomings

3.1 One Advertisement Per Update When multiple prefixes with the same path attributes are sent to a peer, they are never put in the same update message even though they could be. (Updates can contain multilple withdrawals, however.)

3.2 Unchecked Update Message Size When update messages are sent, the number of bytes required may exceed the maximum allowed size of 4096.

3.3 No Aggregation Though several parts of automatic prefix aggregation have been implemented, it is not mature enough to be enabled.

4 Configuration

As with the rest of SSFNet, SSF.OS.BGP4 is configured using DML. To run BGP on a router during a simulation, simply add the following DML code to the graph attribute of the router:

ProtocolSession [
  name bgp
  use SSF.OS.BGP4.BGPSession
]

BGP also requires that Sockets, TCP, and IP are running on the router. So if they do not already appear, the following additional ProtocolSessions should be added after BGP's ProtocolSession:

ProtocolSession [
  name socket
  use SSF.OS.Socket.socketMaster
]
ProtocolSession [
  name tcp
  use SSF.OS.TCP.tcpSessionMaster
]
ProtocolSession [
  name ip
  use SSF.OS.IP
]

This is the minimal configuration for including BGP in an SSFNet model, though additional attributes can be specified if the modeler wishes to have more precise control over the protocol. Each of these additional BGP-related options fit into one of three categories of configuration types. The first is configuration of behavior. Options of this type are subdivided into global and individual options, and control exactly how BGP is to behave during the simulation. The second type is configuration of presentation. Options of this type deal with what output is generated and how it is to be presented to the user. Options which configure presentation never affect the actual behavior of the model. The third type is configuration of optimizations, in which certain functionality can be traded off for improvements in model execution. In particular, there are several memory usage optimizations available.

4.1 Configuration of Behavior

These options control exactly how BGP is to behave during a simulation. There are two categories of behavioral configuration: individual and global.

4.1.1 Configuration of Individual Behavior

Each individual BGP protocol session instance, or BGP speaker, must be configured separately. The configuration of an individual BGP speaker takes place within a ProtocolSession attribute (refer to attribute .schemas.graph.ProtocolSession of the SSFNet schema (file ssfnet/examples/net.dml in the SSFNet distribution)). Such a ProtocolSession attribute must have a subattribute name with a value of bgp as well as a subattribute use with a value of SSF.OS.BGP4.BGPSession. A minimal BGP ProtocolSession would look something like this:

ProtocolSession [
  name bgp
  use SSF.OS.BGP4.BGPSession
]

There are currently two basic options for configuring an individual BGP speaker:

Figure 1 contains the schema for all attributes of BGP which are configurable on a per-BGP speaker basis in this implementation. (It is not the complete schema, though, which contains additional global attributes, output options, and debugging options.) The tables following the figure contain detailed descriptions of each attribute and their allowed usages.

Figure 1  SSFNet BGP-4 DML schema excerpt: [new window] [same window]

Tables 1 through 3 summarize the individual behavioral attributes, and a fourth table provides some additional details on policy configuration. Table 1 describes attributes which appear immediately within the ProtocolSession attribute. Table 2 describes attributes which appear immediately within the neighbor attribute. Table 3 describes all attributes which apply to policy configuration. Table 4 contains usage information for configuring an atomic predicate in a policy rule.

Table 1  Immediate Subattributes of ProtocolSession: [new window] [same window]
Table 2  Immediate Subattributes of neighbor: [new window] [same window]
Table 3  Subattributes of infilter and outfilter: [new window] [same window]
Table 4  Usage of clause.predicate.atom: [new window] [same window]

ProtocolSession blocks are in turn attributes of a graph block (a protocol graph), which is an attribute of a router configuration block. That is, if the modeler would like to configure the attributes of an instance of BGP with values other than the defaults used in autoconfiguration, the appropriate ProtocolSession attribute in the associated router should contain the attributes to be configured. (For example, if the modeler wants router 123 to run BGP and wishes to set a value other than the default for the Connect Retry Interval, then the DML configuration code in router123.dml could be used.)

Note that there are no compromises between the two configuration options. That is, when autoconfiguration is used, the modeler provides no information about a BGP speaker, and when it is not used, the modeler must provide all information about the BGP speaker (with possible exceptions when global default attributes are in use). In the above example (router123.dml), the configuration of the BGP protocol session indicates that the BGP speaker has one neighbor. The relevant addresses, timer values, and filtering policy rules are provided, even though they may be the same as the defaults used by autoconfiguration. Though it can be done, mixing autoconfigured and manually configured BGP speakers should be avoided if possible. It is least preferable to mix them within the same AS--separating them by an AS boundary is less likely to cause compatibility problems between the two configuration schemes.

autoconfig.dml and manualconfig.dml are example DML files, each of which configures a simple network of two directly connected routers. Autoconfiguration is used in the first but not the second.

When using manual configuration, the modeler may wish to use virtual (loopback) interfaces, particularly for Internal BGP peering sessions. A good example of DML code which does this is in the validation test file BGP4/test/loopback/loopback.dml.

For more examples of BGP configuration, see the example simulations on the Internet and the validation tests included in this distribution. There are also several debugging options which were intended for the developer but may be of use to the modeler in certain cases. Refer to the full SSFNet BGP-4 DML schema.

4.1.2 Configuration of Global Behavior

Certain global behavioral options exist to simplify configuration. None of them are required. If used, however, they must appear immediately within the bgpoptions attribute, which itself must appear immediately within the top-level Net attribute. Table 5 summarizes each of these attributes.

Table 5  Global Behavioral DML Attributes: [new window] [same window]

For example, the bgpoptions attribute for a simulation which changes the global values used for some of the BGP timers might look like this:

bgpoptions [
  global_ebgp_mrai 50
  global_keep_alive_time 100
]

4.2 Configuration of Presentation

Several options are available for configuring the presentation of BGP-related output in an SSFNet simulation. There are two independent types of output which can be used during a simulation. Streamed output sends output records (messages) to a specified output file in a special encoded byte format. Printed output sends records (messages) to the standard output stream. Streamed output is good for models which produce large volumes of output, as it is typically more time and space efficient. However, it requires some additional work in order to be useful. First, any BGP router generating output must be configured with an additional protocol session, called a probe, which helps collect and multiplex the output. Second, a separate program, called a player, must be run in order to process the output stream. Players of any kind may be composed (in Java) to perform arbitrary analysis on the output records. Included with this distribution is a player which converts the byte records into human-readable ASCII format (which is the same as the printed output). Printed output is much simpler, and is very useful for models with smaller amounts of output, as well as for simple debugging.

Each output-related option can be specified in at least one of two places: in the bgpoptions attribute (to give the attributes global scope), or in the monitor attribute of a BGP session (so that the attribute affects only that particular BGP session). Table 6 lists the attributes available for configuring presentation. Most of the attributes can be used both globally and locally, but some can only be used in one of the two ways (they are noted as such in the table).

Table 6  DML Attributes for Presentation Configuration: [new window] [same window]

Global configuration looks much the same as for global configuration of behavior (see section 4.1.2). Local configuration might look something like this:

ProtocolSession [
  name bgp
  use SSF.OS.BGP4.BGPSession
  monitor [
    show_snd_update true
    dump_loc_rib true
  ]
]

4.2.1 Configuring and Using Streamed Output

In order to send simulation output to an encoded byte stream (and ultimately to a file), first the streaming option must be set to true (see section 4.2 and Table 6). In addition to this, each router which generates BGP output must be configured to have one additional protocol session in its protocol graph by way of an additional ProtocolSession attribute. This attribute must look as follows:

ProtocolSession [
  name probe
  use SSF.OS.ProbeSession
  file "some-file-name"
  stream "some-stream-name"
]

where some-file-name is a file name of your choice, and some-stream-name is a stream name of your choice. Currently, each probe protocol session in a single model specification should use the same file name throughout. It should also use the same stream name throughout. Refer to streaming.dml for a full DML model which uses streaming. When the simulation is complete, the file some-file-name.0 will have been created containing stream some-stream-name.0. (Note that two characters, a dot and a zero (".0"), are appended to the file and stream names.) To "play back" the contents of the record stream, you may want to use the VerbosePlayer program (in the BGP4/Players/ directory) like this:

java SSF.OS.BGP4.Players.VerbosePlayer some-file-name.0 some-stream-name.0

This will print human-readable output corresponding to the byte-encoded output. Additional customized players which perform arbitrary operations (analysis, presentation, etc.) on output record streams can be composed. Refer to AbstractPlayer.java and VerbosePlayer.java in the BGP4/Players/ directory for an example of how this can be done.

4.3 Configuration of Optimizations

Several options exist in which functionality can be traded for improvements in model execution. In particular, memory improvements (which often lead to shorter execution times) can often be gained in models which only use basic BGP options. Table 7 summarizes all of these options and their implications.

Table 7  DML Attributes for Optimizations Configuration: [new window] [same window]

5 Source Code

Archived Java source: http://www.ssfnet.org/bgp/
Modification history: BGP4/doc/HISTORY

6 Examples

Further examples are available on the Internet at http://www.ssfnet.org/bgp/examples/

7 Validation

No well-established method currently exists for validating an implementation of BGP, so we began composing our own validation tests for SSF.OS.BGP4. They vary from very simple, strict verifications of the most basic behaviors of BGP to more macroscopic tests which check the general characteristics of BGP in larger networks.

8 Questions and Help

SSFNet uses an interactive FAQ (the SSFNet Faq-O-Matic) which contains several answers to frequently asked questions about SSFNet and all of its components, including SSF.OS.BGP4. Users can also log in and post new questions, which others in the SSFNet modeling community can respond to by posting their own answers. The SSFNet Faq-O-Matic is located at http://www.cs.dartmouth.edu/research/ssfnet/faq/fom.cgi.

9 References

   [1]   RFC 1771: A Border Gateway Protocol 4 (BGP-4)

   [2]   RFC 1557: Definitions of Managed Objects for the Fourth Version of the Border Gateway Protocol (BGP-4) using SMIv2

   [3]   RFC 1772: Application of the Border Gateway Protocol in the Internet

   [4]   RFC 1773: Experience with the BGP-4 protocol

   [5]   RFC 1774: BGP-4 Protocol Analysis

   [6]   RFC 2796: BGP Route Reflection--An Alternative to Full Mesh IBGP

   [7]   BGP4: Inter-Domain Routing in the Internet by John W. Stewart III

   [8]   Internet Routing Architectures by Bassam Halabi

   [9]   RFC 2439: BGP Route Flap Damping

   [10]  RIPE 210: RIPE Routing-WG Recommendation for coordinated route-flap damping parameters

10 Authors

BJ Premore is the primary author of SSF.OS.BGP4. The route flap damping code was contributed by Z. Morley Mao.