SSF.OS.BGP4 Validation

Methodology

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 (such as setting up and tearing down peering sessions) to more macroscopic tests which check the general characteristics of BGP in larger networks (such as ensuring that packets sent from one part of a network to another reach their destination). The BGP-4 specification [1] leaves room for an essentially limitless number of acceptable variations in behavior, making complete verification a difficult if not impossible task. Our approach here is not an attempt to confirm perfect behavior of the implementation, but simply to reduce the number of possible incorrect behaviors by showing that it conforms to certain restrictions. The validation tests which take the strict and simple approach establish a foundation of basic functional behaviors upon which the more complex behaviors are built. The macroscopic tests blur the details of its behavior, essentially performing a sanity check to ensure that what's getting done at the network level is what we would expect. (Whether or not it's getting done the way that it should be is never guaranteed in this type of test.)

Together, these two types of validation test give us at least some assurance that the behavior is reasonable. Eliminating all possibility for incorrect behavior is almost certainly a fantasy that will never be achieved. However, we can at least make an effort to narrow it down.

Test List

drop-peer:    Terminating a Peering Session
drop-peer2:    Routing Updates after Session Termination
keep-peer:    Maintaining a Peering Session
route-distrib:    Route Distribution between Peers
propagation:    Propagation of Learned Route Information
select:    Selecting from Multiple Route Options
withdrawals:    Handling a Withdrawal Update
loopback:    Using Loopback Addresses
reflection:    Route Reflection
ibgp:    Internal BGP
reconnect:    Reconnecting after Session Termination
goodgadget:    Simple Route Filtering
forwarding1:    Forwarding in a Moderately Sized Network
forwarding2:    Forwarding in a Moderately Size, Hierarchically Addressed Network
forwarding3:    Forwarding in a Moderately Sized Network Including IBGP

General Format

Each test is organized according to the same template. Each test has a shorthand name, such as drop-peer or goodgadget. Let x be the shorthand name for any test. Then x is located in directory BGP4/test/x/ of the distribution. Within that directory there are several files. The DML source file for the model is x.dml, and x.gif is a graphical image of the modeled network. (Additional library DML source files are BGP4/test/dictionary.dml, which contains commonly used network building blocks, and ssfnet/examples/net.dml, which is a schema for verifying the correctness of SSFNet DML code.) Makefile contains specifics about running the model, including the exact command which is used to execute it. That command is essentially

    java SSF.Net.Net <runtime> x.dml ../dictionary.dml ../../../../../../examples/net.dml

where <runtime> is the length of the simulation in seconds. (In Makefile the length of the simulation is defined by the RUNTIME variable.) Some tests require additional source code. If that is the case, the code is located in a directory called BGP4/test/x/src/, and Makefile will automatically compile it before starting the simulation. All output from the simulation is directed to file test-raw.out. This file should look very similar to (but not necessarily exactly the same as) the archived raw output in x-raw.out. The file test.out contains only those lines from test-raw.out which are specifically intended for validation purposes. The file x.out contains the archived validation output. In order for the validation test to be successful, test.out must be exactly the same as x.out.

Terminating a Peering Session

Files specific to this test are located in BGP4/test/drop-peer/.

This test checks the behavior of a BGP speaker when one of its peers is non-responsive.

In this test, a BGP speaker establishes a peering session with a neighbor that is henceforth non-responsive. The test is successful if the BGP speaker eventually sends a Notification message to this peer (when the Hold Timer for that peer expires).

Routing Updates after Session Termination

Files specific to this test are located in BGP4/test/drop-peer2/.

This test checks the behavior of a BGP speaker after a peering session is terminated.

In this test, a BGP speaker establishes two peers, but then the session with one of them is broken. The test is successful if the BGP speaker sends an update to its remaining peer in order to withdraw the former route to the disconnected peer.

Maintaining a Peering Session

Files specific to this test are located in BGP4/test/keep-peer/.

This test checks the mechanisms used to keep an existing peering session intact.

In this test, a BGP speaker establishes a peering session with a neighboring BGP speaker. The test is successful if, after an arbitrary amount of time, the peering session still exists.

Route Distribution between Peers

Files specific to this test are located in BGP4/test/route-distrib/.

This test checks to make sure that a router receives routing information advertised by a peer.

In this test, a BGP speaker has a single peer. Routing information for the BGP speaker's AS is advertised to that peer. The test is successful if the peer correctly adds an entry in its local forwarding table for this routing information.

Propagation of Learned Route Information

Files specific to this test are located in BGP4/test/propagation/.

This test checks that a BGP speaker correctly propagates learned routes to other BGP speakers who may not know of these routes yet.

In this test, there are three ASes connected in a line. (AS X connects to AS Y, and AS Y connects to AS Z.) The test is successful if a route advertised by AS X is propagated through AS Y to AS Z and inserted into the forwarding table at AS Z.

Selecting from Multiple Route Options

Files specific to this test are located in BGP4/test/select/.

This test checks that a BGP speaker chooses routes properly when there is more than one option for forwarding to a particular destination.

In this test, there are three ASes--X, Y and Z--each with one BGP router. Each of these BGP routers has the other two as neighbors. The BGP speaker at AS X advertises routing information about its AS (AS X) to both Y and Z. Y in turn forwards the routing information to Z (and likewise Z also forwards it to Y). Z's policy is to choose routes with the shortest number of hops through other ASes. The test is successful if, after having received the advertisement about X both from X and Y, Z chooses the direct (1-hop) route to X and installs it in the forwarding table at the local router.

Handling a Withdrawal Update

Files specific to this test are located in BGP4/test/withdrawals/.

This test checks that a BGP speaker handles the withdrawal of routing information correctly by removing the route from the local forwarding table.

In this test, one BGP speaker advertises a bogus route to a peer, waits a little while, and then sends a withdrawal for that route. The test is successful if the peer receives the advertisement, adds the route to the local routing table, and later receives the withdrawal and correctly removes the route from the routing table.

Using Loopback Addresses

Files specific to this test are located in BGP4/test/loopback/.

This test checks the use of loopback (virtual) interfaces as destination addresses for Internal BGP connections.

The network in this test is composed of two ASes, AS1 and AS2. AS1 has only a single router, 1:1. AS2 has three routers--2:1, 2:2, and 2:3--with one link from 2:1 to 2:2 and another link from 2:2 to 2:3. There is one inter-AS link from 1:1 to 2:1. BGP is running at all of these routers, and there is a full mesh of IBGP peering sessions between the three routers in AS2. Note that this is in spite of the fact that there are not physical point-to-point links between each pair of routers--2:1 and 2:3 are not directly connected. Each router, in addition to having physical interfaces, also has one virtual, or loopback, interface. All of the Internal BGP peering sessions use loopback addresses for peer destination addresses. This test is to check that peering sessions are properly established when using loopback addresses rather than physical interface addresses. Furthermore, it tests that multihop peering sessions also work correctly. The test is successful if 2:3 receives an advertisement for a route to AS1.

Reconnecting after Session Termination

Files specific to this test are located in BGP4/test/reconnect/.

This test checks the ability of a BGP speaker to reestablish a peering session with a former peer.

In this test, a BGP speaker establishes two peers, but then the session with one of them is broken. The two BGP speakers that got disconnected then attempt to reestablish a session. The test is successful if the third speaker receives two separate updates which both advertise the same route to the speaker which was disconnected. (There will have been a withdrawal for that route in between the two advertisements.)

Internal BGP

Files specific to this test are located in BGP4/test/ibgp/.

This test checks that a BGP speaker correctly forwards updates to its Internal BGP peers.

In this test, there are three ASes connected in a line. AS X connects to AS Y and AS Y connects to AS Z. AS Y, the middle AS, has two BGP routers, while the other two have only one BGP router. The test is successful if AS Z receives an update message advertising a route to AS X. This would imply that Internal BGP worked properly within AS Y.

Route Reflection

Files specific to this test are located in BGP4/test/reflection/.

This test checks the behavior of (Internal BGP) route reflectors.

In this test there are four ASes (see the image file reflection.gif). The AS that is focussed upon (AS M) contains six routers and three reflection clusters (one of them has only a single reflector with no clients). The other three ASes (X, Y and Z) contain only one router apiece, and each attach in one place to the primary AS. The test traces the advertisement of route information injected at one of the auxiliary ASes (X) throughout the entire network. The test is successful if the route information is reflected three times by router RR1 and once by RR2, and if each BGP router in the network receives exactly one update message containing this route information.

Simple Route Filtering

Files specific to this test are located in BGP4/test/goodgadget/.

This test checks the behavior of BGP speakers which filter based on the AS path attribute.

In this test there are four ASes (see the image file goodgadget.gif). The three points of the triangle (AS1, AS2, and AS3) are all configured to give the direct path to AS0 low priority. AS1 and AS2 do not accept counter-clockwise paths (they deny routes advertising those paths) and thus prefer the clockwise paths. AS3 has no preference between clockwise and counterclockwise paths. The test is successful if the local routing information at the routers in AS1, AS2, and AS3 for the path to AS0 is as follows. The router in AS1 must indicate that it has chosen the path [AS3 AS0]. The router in AS2 must indicate that it has chosen the path [AS2 AS3 AS0]. Finally, the router in AS3 must indicate that it has chosen the path [AS1 AS2 AS3 AS0].

Thanks to Tim Griffin for contributing this test network. Refer to the SIGCOMM 1999 paper An Analysis of BGP Convergence Properties (Griffin and Wilfong) for similar examples of network "gadgets" like this one.

Forwarding in a Moderately Sized Network

Files specific to this test are located in BGP4/test/forwarding1/.

This test does not examine a specific aspect of BGP, but is a more general test of BGP's operation on a macroscopic level. It checks that traffic in a network of 32 autonomous systems is being correctly forwarded from source to destination.

In this test, there is a network of 32 autonomous systems, each with one router running BGP and one host. At each host, there is an application running which sends one packet to each of the other 31 hosts in the network. The test is successful if all 31*32=992 messages are received by the correct hosts.

Forwarding in a Moderately Sized, Hierarchically Addressed Network

Files specific to this test are located in BGP4/test/forwarding2/.

This test does not examine a specific aspect of BGP, but is a more general test of BGP's operation on a macroscopic level. It checks that traffic in a hierarchically addressed network of 32 autonomous systems is being correctly forwarded from source to destination.

In this test, there is a network of 32 autonomous systems, each with one router running BGP and one host. At each host, there is an application session running which sends one packet to each of the other 31 hosts in the network. The test is successful if all 31*32=992 messages are received by the correct hosts.

Forwarding in a Moderately Sized Network Including IBGP

Files specific to this test are located in BGP4/test/forwarding3/.

This test does not examine a specific aspect of BGP, but is a more general test of BGP's operation on a macroscopic level. It checks that traffic in a network of 31 autonomous systems is being correctly forwarded from source to destination. The network is hierarchically addressed and utilizes Internal BGP.

In this test, there is a network of 31 autonomous systems, each with a varying number of routers running BGP. For each router in an AS, there is one host connected to it. There are a total of 90 routers and 90 hosts. At each host, there is an application session running which sends one packet to every other host in the network. The test is successful if all 90*89=8010 messages are received by the correct hosts.