Towards a BGP model in JavaSim

Javasim is a scalable event-driven simulator developed by Hung-Ying Tyan and many others at Ohio-State University. Javasim is written in Java for portability reasons and contains realistic models of various Internet protocols. Although Javasim supports several routing protocols, it did not contain any BGP model. Instead of developing a BGP model from scratch, we choose to port and enhance the BGP implementation developed by B. J. Presmore for SSFNet. This model has been extensively validated and tested and has already been used for several simula-tion studies. We have enhanced it to better support the routing policies that are often used by ISPs as shown earlier.

Download
Description of the extensions
Contacts

Download

You can download CVS snapshots of the patched version of JavaSim as well as the ported BGP model.

Patched JavaSim 1.0 distribution (March 6th, 2003)
BGP model for JavaSim (February 4th, 2003)
Util package for BGP (March 6th, 2003)

Description of the extensions

1. Introduction

This section describes the modifications we have brought to the BGP model and how we have extended it in order to evaluate traffic engineering techniques based on the manipulation of BGP attributes.

2. Towards a BGP model in JavaSim

The first step towards a running BGP model in JavaSim was the alteration of the SSFNet implementation in order to make it use the JavaSim API. Indeed, the BGP model of SSFNet uses a large amount of basic functionnalities that are specific to the SSFNet simulator. These functionnalities are as various as the representation of network addresses, the establishment of a TCP connection, the management of a timer, the creation of a new thread and so on. These functionnalities are available in both the SSFNet and the JavaSim simulators but with quite different programming interfaces and often different ways of working.

For instance, in the SSFNet implementation, the BGP model relies on a very simplified implementation of TCP. In JavaSim, this simple TCP does not exist but instead a full TCP implementation is available and can be accessed through a BSD like socket API. This implementation was nevertheless not completely finished at the time we started working with JavaSim and the SSFNet BGP model. In particular, the JavaSim API lacked asynchronous operations on TCP socket. Such asynchronous operations were required in order to keep the number of threads very low which is an important point for scalable simulations because the operating system may quickly become overloaded when too many threads are running at the same time. We worked with the author of JavaSim to solve this problem.

The second step consisted in provisionning a way to configure BGP routers. In the SSFNet simulator, this can be done with a specific configuration language, DML, while in JavaSim, simulations are usually configured by the way of TCL scripts that directly access Java methods. We have then provided such configuration methods in order to replace the DML configurations from SSFNet. Among these methods are

```
config(AS number, Tie-breaking ID)
```
This is the first method to call in order to setup a BGP router. The method takes two arguments, the AS number and a Tie-breaking ID. The AS number identifies the AS to which the router belongs and the Tie-breaking ID is a number associated to each router to replace the router ID in tie-breaking rules of the BGP decision process as explained in this section.
```
addPeer(IP address, AS number)
```
This method adds a new peer to this BGP router. The method takes two arguments, the IP address of the peer and its AS number. If the AS number is the same as this router, an iBGP session will be established otherwize an eBGP session will be established. Note that the peer must also have this router in its list of peers (also with the addPeer method).
```
setPeerInFilter(IP address, Filter)
```
This method allows the establishment of a filter for routes received from the peer that has the given IP address. This peer must have been configured before with the help of the addPeer method.
```
setPeerOutFilter(IP address, Filter)
```
This method allows the establishment of a filter for routes that have been selected to be redistributed to the peer that has the given IP address. The target peer must have been configured before with the help of the addPeer method.
```
init()
```
This method initializes the BGP router and starts the establishment of BGP sessions with the configured peers.

Once these two porting steps were achieved, we started running small simulations to check that the BGP model was running properly. We also devised validation tests based on the validation suite provided with the BGP model of SSFNet. Then our customization work could start...

3. Extensions

In order to perform our simulations, we had to extend the BGP model ported from SSFNet. This section presents the extensions we made. They consist in bringing a more complete support of routing policies and a full support of Redistribution Communities. A third kind of extension, the addition of a Tie-breaking ID, has been made to perform simulations that can be compared even if non-deterministic BGP choices had to be made.

3.1. Routing policies

The first extension brought to the BGP model concerns the complete support of routing policies. In the SSFNet model, several classes (Rule, Action, Predicate, and so on) were provided to support the establishment of routing policies. However, it was not possible to build filters that could match or change required attributes such as Communities. So we completed the existing classes to achieve these requirements.

Moreover, we have also provided a simple class that makes possible the establishment of routing policies with small scripts in order to make the routing policies configuration task simpler. This class which is named RouteMap is able to translate a small script into an SSFNet routing filter. The following script is an example of a routing policy definition:

community "1"|deny
|community strip

A route map script is composed of a list of lines. Each line contains two parts separated by the symbol ``|''. The first part is a set of predicates which must be validated with the route under test. The second part is a set of actions that will be applied to the route if the predicates in the first part match. In addition, if the predicates in the first part match, the treatment of the script stops and the route is accepted or denied depending on the content of the actions. The above example defines a policy that will first deny each route that contains the Community ``1'' and will remove every Community of other routes that will also subsequently be accepted (for redistribution if this is an output filter or for the Adj-RIB-In if this is an input filter).

Once the support of such routing policies has been correctly implemented in the BGP model, we had to fix a problem in the decision process which did not correctly support ``additive'' routing policies action such as the appending of a new Community value.

And finally, we added in the BGP model the ability for a router to refresh a session with a specific peer. This refresh is used when the output policies are changed so that the attributes attached to routes may be different. Then one router can use the session refresh capability in order to re-announce all the routes to a specific peer. This functionnality is used for the automatic setting of Redistribution Communities in order to balance the traffic load on two access links.

3.2. Redistribution Communities

In order to evaluate the Redistribution Communities which we defined in draft-ietf-ptomaine-bgp-redistribution-01.txt, we have added support of the Extended Communities attribute to the BGP model. The routing policies were also modified in order to permit the addition of Redistribution Communities to specific routes as well as the automatic treatment of routes that have such Redistribution Communities attached. For instance, the route map scripts now support the three actions and filters defined in the Redistribution Communities specifications. The one-line script shown below attaches a new Redistribution Community which requests that the AS-Path of route be prepended twice when they are redistributed to AS3.

|ext_communities append red prepend 2 as 3

3.3. Tie-breaking ID

Another important aspect of the modifications brought to the BGP model is the addition of a tie-breaking ID. This attribute has been added because in our simulations (like in the real Internet), many choices made by BGP do not rely on the AS-Path length but rather on tie-breaking rules. This choice is not deterministic. In the SSFNet model of BGP, the tie-break is based on the IDs of the routers that announced the routes. This method was not appropriate in our simulations because the allocation of IP addresses did not correspond to a realistic one and so the distribution of router IDs had a great influence on the choices made by BGP.

A solution to this problem could have been the addition of a random tie-break. If a non deterministic choice has to be made between two routes, there is a probability of 50% for each of these routes to be chosen. This solution has however the inconvenient that the attained behaviour is not reproductible from one simulation to another with different routing policies for instance.

In order to avoid such a bias, we have decided that each router receives a random ID (the tie-breaking ID) that is then attached to every route it redistributes. The tie-breaking rule is then based on this ID rather than the usual router ID. The tie-breaking ID configured for each router can be kept in a file and re-used from one simulation to another so that final results can be compared.

Contacts

This patched version of JavaSim is developed by the Infonet Group. I you want to contact the authors, you can write to this address.