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.
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" . 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 . (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 220.127.116.11). 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 , 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 . 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  and RIPE 210 , 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.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.
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 [ 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.
ProtocolSessionattribute (refer to attribute
.schemas.graph.ProtocolSessionof the SSFNet schema (file
ssfnet/examples/net.dmlin the SSFNet distribution)). Such a
ProtocolSessionattribute must have a subattribute
namewith a value of
bgpas well as a subattribute
usewith a value of
SSF.OS.BGP4.BGPSession. A minimal BGP
ProtocolSessionwould 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
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
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 (
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.
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
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.
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
Net attribute. Table 5 summarizes each of these
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 ]
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
bgpoptions attribute (to give the attributes global scope), or
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 ] ]
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" ]
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
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
VerbosePlayer.java in the
BGP4/Players/ directory for an example of how this can be done.
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]
Archived Java source:
Modification history: BGP4/doc/HISTORY
Further examples are available on the Internet at
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.
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.
RFC 1771: A Border Gateway Protocol 4 (BGP-4)
RFC 1557: Definitions of Managed Objects for the Fourth Version of the Border Gateway Protocol (BGP-4) using SMIv2
RFC 1772: Application of the Border Gateway Protocol in the Internet
RFC 1773: Experience with the BGP-4 protocol
RFC 1774: BGP-4 Protocol Analysis
RFC 2796: BGP Route Reflection--An Alternative to Full Mesh IBGP
BGP4: Inter-Domain Routing in the Internet by John W. Stewart III
Internet Routing Architectures by Bassam Halabi
RFC 2439: BGP Route Flap Damping
RIPE 210: RIPE Routing-WG Recommendation for coordinated route-flap damping parameters
BJ Premore is the primary author of SSF.OS.BGP4. The route flap damping code was contributed by Z. Morley Mao.