Tutorial

Introduction

This page contains a short C-BGP tutorial. This tutorial targets version 2.0.0 of C-BGP. The aim of the tutorial is to build a complete AS-level model of the Internet. We will start with a toy example in order to learn the basics of C-BGP scripting. The tutorial is organized as follows:

Installing and running C-BGP
Simple example
Abilene example
Internet-like example
1. Loading the topology
2. Mining the routing states

1. Installing and running C-BGP

Although the installation of C-BGP is similar to many UNIX projects, it might appear quite cumbersome to unexperienced users. For this reason, let's start this tutorial with a quick review of the installation steps.

In order to install C-BGP, you will need to download its source archive from the Downloads section. In addition, you will need to install the libGDS library. You can obtain libGDS's source archive from here. You will also need to install the PCRE and readline libraries. In this tutorial, we will assume that PCRE and readline are already installed on your system since these are popular packages. We will only focus on building libGDS and C-BGP.

The libGDS library provides the data structure foundations of C-BGP. For this reason, we need to install it prior to C-BGP. First, let's untar the source archive in our home directory. Then, this is a classical configure-based building process. The operation details are given below. Please note that the installation prefix specified in the example with --prefix (/Users/bqu/local) depends on the settings of your own system. The only requirement is that you need read/write access rights to the installation directory. If you don't mention an installation prefix, /usr/local will be used. mortimer:~ bqu$ wget http://sourceforge.net/projects/libgds/files/libgds-2.0.0-rc3.tar.gz mortimer:~ bqu$ tar xvzf libgds-2.0.0-rc3.tar.gz mortimer:~ bqu$ cd libgds-2.0.0-rc3 mortimer:~/libgds-2.0.0-rc3 bqu$ ./configure --prefix=/Users/bqu/local mortimer:~/libgds-2.0.0-rc3 bqu$ make mortimer:~/libgds-2.0.0-rc3 bqu$ make install

Note that if you installed libGDS in a non-standard directory, you will probably need to inform 'pkg-config' about the installation path. 'pkg-config' is the tool used by the ./configure script to locate libGDS. To inform 'pkg-config', you will need to export an updated version of the PKG_CONFIG_PATH environment variable, as follows: mortimer:~ bqu$ export PKG_CONFIG_PATH=/Users/bqu/local/lib/pkgconfig:$PKG_CONFIG_PATH

Once libGDS is installed, you can build C-BGP. The installation operation is similar to that of libGDS, as shown in the example below. mortimer:~ bqu$ wget http://sourceforge.net/projects/c-bgp/files/cbgp-2.0.0-rc3.tar.gz mortimer:~ bqu$ tar xvzf cbgp-2.0.0-rc3.tar.gz mortimer:~ bqu$ cd cbgp-2.0.0-rc3 mortimer:~/cbgp-2.0.0-rc3 bqu$ ./configure --prefix=/Users/bqu/local mortimer:~/cbgp-2.0.0-rc3 bqu$ make mortimer:~/cbgp-2.0.0-rc3 bqu$ make install

You should now be able to run C-BGP and to type in some commands. Note that if the installation directory that you mentionned during the compilation is not in your PATH environment variable, you should either add it to PATH or use the full path when you run C-BGP. Similarly, if libGDS is not in a directory that is used by your linker, you should consider adding its install path to the LD_LIBRARY_PATH environment variable, the DYLD_LIBRARY_PATH environment variable or the /etc/ld.so.conf file. How this is exactly done depends on your operating system and is beyond the scope of this tutorial. For example, under Mac OS X, you would need to update your environment variables as follows: mortimer:~ bqu$ export PATH=/Users/bqu/local/bin:$PATH mortimer:~ bqu$ export DYLD_LIBRARY_PATH=/Users/bqu/local/lib:$DYLD_LIBRARY_PATH

The following console snapshot shows a very short C-BGP session. First, C-BGP is started in interactive mode. It shows that it is initialized and prompts the user for commands. In the example, the show version command is typed in, and C-BGP shows its own version and the version of libGDS. In a second time, the session is terminated by issuing the quit command. mortimer:~ bqu$ cbgp cbgp> init. cbgp> show version cbgp version: 2.0.0-rc3 [bgpdump] libgds version: 2.0.0-rc3 cbgp> quit cbgp> done. mortimer:~ bqu$

2. Simple example

As a starter, we will learn how to build a toy model composed of two different domains, as shown in Fig.1. There are two independent domains, each one composed of several routers. Both domains run an IGP and they exchange routing information using BGP. The complete C-BGP script is available here. You can load this script using the include command.

Fig.1: Toy example's network topology.

2.1. Topology description

In C-BGP, the network topology is modeled at the IP (layer-3) level. That is, C-BGP does not model the physical interconnection between nodes. A node in C-BGP is created using the net add node statement. A node is identified by a dot-separated sequence of 4 integers, exactly as an IPv4 address. This address must be unique in the model. A point-to-point link is created using the net add link statement. A link is identified by its endpoints. The following example creates a topology with 3 nodes arranged in a triangle. net add node 1.0.0.1 net add node 1.0.0.2 net add node 1.0.0.3 net add link 1.0.0.1 1.0.0.2 net add link 1.0.0.1 1.0.0.3 net add link 1.0.0.2 1.0.0.3

C-BGP allows us to check how nodes are interconnected. For example, it is easy to list the adjacencies of a single node with the command net node show links. Here is an example of the output obtained from node 1.0.0.1 after the complete topology has been described. cbgp> net node 1.0.0.1 show links rtr 1.0.0.2/32 1.0.0.2 0 4294967295 UP rtr 1.0.0.3/32 1.0.0.3 0 4294967295 UP rtr 2.0.0.1/32 2.0.0.1 0 4294967295 UP

Note that it is also possible to interconnect nodes with LANs instead of point-to-point links. Have a look at command net add subnet.

2.2. Intradomain routes

In addition to modeling the topology, C-BGP provides a convenient way to compute the routes inside a single domain. To do this, nodes are first assigned to a domain. Then, for each domain C-BGP can compute shortest-path routes between its member nodes, much like an intradomain routing protocol such as IS-IS or OSPF would do. The difference is that, to compute the routes in a domain, C-BGP does not model the messages exchanged between routers but relies on its existing knowledge of the whole topology of that domain.

To create a domain, the net add domain command must be used. Then, each node can be assigned a domain, using the net node domain command. Each link must also be assigned an IGP weight with the net link igp-weight command. Links that are not assigned an IGP weight explicitly have the default maximum metric value (2^32-1) and are not considered during the shortest-path computation. Finally, to compute the intradomain routes, use the net domain compute command. Here is an example: net add domain 1 igp net node 1.0.0.1 domain 1 net node 1.0.0.2 domain 1 net node 1.0.0.3 domain 1 net link 1.0.0.1 1.0.0.2 igp-weight --bidir 5 net link 1.0.0.1 1.0.0.3 igp-weight --bidir 15 net link 1.0.0.2 1.0.0.3 igp-weight --bidir 5 net domain 1 compute

Let's check that everything is defined correctly so far. For this purpose, C-BGP provides many different means to retrieve information from the model, mainly about its routing state. A first interesting command is the equivalent to the well-known ping networking utility, the net node ping command. It allows to check the reachability between two nodes. For instance, let's check that it is possible to reach node 1.0.0.1 from node 1.0.0.3 with the example we have built so far. cbgp> net node 1.0.0.3 ping 1.0.0.1 ping: reply from 1.0.0.1

The result of the ping command shows that 1.0.0.1 has replied. Hence, the reachability is ensured from 1.0.0.3 to 1.0.0.1 and the other way around. Since ping does not inform us on the path that is being used, C-BGP also provides a replacement for the traceroute utility, the net node traceroute command. cbgp> net node 1.0.0.3 traceroute 1.0.0.1 1 1.0.0.2 icmp error (time-exceeded) 2 1.0.0.1 reply

On the above traceroute trace, the result is presented in similar way to the classical traceroute utility. There is one line per probed hop. The first hop reported is 1.0.0.2 (which sent an ICMP time exceeded error). The second hop is 1.0.0.1 (which is the destination). We observe that the path from 1.0.0.3 to 1.0.0.1 appears to be through 1.0.0.2. However, we are not sure that the reverse path from 1.0.0.1 to 1.0.0.3 also goes through 1.0.0.2. To check for this, we can either perform a traceroute in the reverse direction or have a look at the node's routing tables, using the net node show rt command. Here is a dump of 1.0.0.1's routing table. We can easily check that all routes in 1.0.0.1 go through 1.0.0.2. cbgp> net node 1.0.0.1 show rt * 1.0.0.2/32 0.0.0.0 1.0.0.2 5 IGP 1.0.0.3/32 0.0.0.0 1.0.0.2 10 IGP

If we try to ping a node in the other domain, we run into reachability issues, as shown in the example below. Although 2.0.0.1, which is a border router of AS2, is reachable from 1.0.0.3 (it is advertised in the IGP), 2.0.0.1 has no route towards 1.0.0.3. We need BGP to propagate AS1 and AS2's prefixes between each other. cbgp> net node 1.0.0.3 ping 2.0.0.1 cbgp> net node 1.0.0.3 traceroute 2.0.0.1 1 1.0.0.1 icmp error (time-exceeded) 2 * no reply

2.3. eBGP neighbor reachability

In order to establish interdomain BGP sessions (eBGP sessions), the border routers should be able to reach their external neighbors. With the above interdomain routing setup, these neighbor routers are not reachable. We need to add routing information about these neighbors. There are two main ways to do this: (1) setup static routes or (2) add external links to the IGP.

Static routes

Let's first describe how the static routes approach works. We need to statically inject into border routers routing information about their eBGP neighbors. Let's take the example of the eBGP session between 1.0.0.1 and 2.0.0.1. We need to tell 1.0.0.1 that it can reach 2.0.0.1 through its direct link with 2.0.0.1. Symmetrically, we need to tell 2.0.0.1 that it can reach 1.0.0.1 through its direct link with 1.0.0.1. Adding these static routes can be done with the specific command net node route add. The following example adds static routes required by the eBGP session between 1.0.0.1 and 2.0.0.1. net node 1.0.0.1 route add --oif=2.0.0.1 2.0.0.1/32 1 net node 2.0.0.1 route add --oif=1.0.0.1 1.0.0.1/32 1

It is now possible to check what routes are known by router 1.0.0.1 by using the command net node show rt, as shown in the example below: cbgp> net node 1.0.0.1 show rt * 1.0.0.2/32 0.0.0.0 1.0.0.2 5 IGP 1.0.0.3/32 0.0.0.0 1.0.0.2 10 IGP 2.0.0.1/32 0.0.0.0 2.0.0.1 1 STATIC

Announce in the IGP

The second possible approach is to let the IGP also compute routes that go through the external links. Let's again take the example of the link between 1.0.0.1 and 2.0.0.1. To make the IGP in domain 1 compute routes through that link, one only need to set an IGP weight on this link. There is however a difference compared to the computation of intradomain routes described above. When C-BGP traverses the link 1.0.0.1 to 2.0.0.1 to compute routes in domain 1, it reaches node 2.0.0.1 that is not in domain 1 and will therefore not go beyond this node. The following code updates the IGP-weight of link 1.0.0.1 2.0.0.1. Note that it is required to recompute all the routes in domain 1 after this change. net link 1.0.0.1 2.0.0.1 igp-weight --bidir 1 net domain 1 compute

As a consequence, node 1.0.0.1 now contains an IGP route towards 2.0.0.1/32. There is also a more important difference with the use of static routes: every node in domain 1 now has a route towards 2.0.0.1/32.

In the remaining of this example network, we will consider that static routes are used.

2.4. BGP setup

To configure a node as a BGP router, the bgp add router command must be used. The role of this command is to add the support of the BGP protocol on one existing node. You need to specify the ASN of the domain the router belongs to. A new BGP domain with the specified ASN is automaticallu created if it didn't exist before. Once one node supports BGP, it is needed to configure its adjacencies with other BGP routers. Let's take the following example: bgp add router 1 1.0.0.1 bgp router 1.0.0.1 add peer 1 1.0.0.2 peer 1.0.0.2 up add peer 1 1.0.0.3 peer 1.0.0.3 up

In the above example, two adjacencies are added to router 1.0.0.1 by using the add peer command. These are internal (iBGP) BGP sessions. Each adjacency is activated using the peer up command. When there is a large number of routers in one domain, configuring a full-mesh of iBGP sessions quickly becomes tiresome. For this reason, it is possible to build the iBGP configuration of AS1 with the bgp domain full-mesh command, as follows: bgp add router 1 1.0.0.1 bgp add router 1 1.0.0.2 bgp add router 1 1.0.0.3 bgp domain 1 full-mesh

In addition to the iBGP sessions, you need to configure external (eBGP) sessions between border routers of AS1 and AS2. For eBGP sessions, it is mandatory to use the command add peer. Moreover, when static routes are used to reach the eBGP neighbors, there is a subtle detail to understand: the next-hop-self option.

The following example shows the setup of one of the eBGP sessions. The peer next-hop-self statement configures the router to advertise itself as next-hop to its iBGP peers for routes received from the eBGP peer. Huh. Said in a more pragmatic way, when router 1.0.0.1 will receive routes from its peer 2.0.0.1, it will propagate the route in AS1's iBGP mesh. Without the next-hop-self statement, the route's next-hop would be 2.0.0.1 which is not a reachable destination for other routers in AS1. With the next-hop-self statement the next-hop advertised by 1.0.0.1 becomes 1.0.0.1. Try to run the example with and without the next-hop-self statements to observe the impact on BGP route selection. bgp router 1.0.0.1 add peer 2 2.0.0.1 peer 2.0.0.1 next-hop-self peer 2.0.0.1 up exit bgp router 2.0.0.1 add peer 1 1.0.0.1 peer 1.0.0.1 next-hop-self peer 1.0.0.1 up exit

Once every BGP routers and adjacencies have been setup, BGP routes can be originated. There are two ways to advertise BGP routes in C-BGP. First, originate a local network. This is done with the add network command, as shown hereafter: bgp router 1.0.0.1 add network 1.0.0/24 bgp router 2.0.0.1 add network 2.0.0/24

In order to run the simulation, the sim run command must be issued. This will cause all BGP messages that were queued in the simulator to be processed, and the BGP convergence is started. The sim run command will block until BGP has converged. sim run

Once the BGP routes have been propagated, you can check that nodes from AS1 can reach nodes from AS2 by using the traceroute command, as shown in the example below. cbgp> net node 1.0.0.3 traceroute 2.0.0.3 1 1.0.0.2 icmp error (time-exceeded) 2 2.0.0.2 icmp error (time-exceeded) 3 2.0.0.1 icmp error (time-exceeded) 4 2.0.0.3 reply cbgp> net node 2.0.0.3 traceroute 1.0.0.3 1 2.0.0.1 icmp error (time-exceeded) 2 1.0.0.1 icmp error (time-exceeded) 3 1.0.0.2 icmp error (time-exceeded) 4 1.0.0.3 reply

You can easily observe that the forwarding paths are asymmetric, as shown in Fig.2. The traffic from 1.0.0.1 to 2.0.0.3 goes out through the egress 1.0.0.2 and enters AS2 through the ingress 2.0.0.2. On the opposite, the traffic in the reverse direction leaves AS2 through 2.0.0.1 and enters AS1 through 1.0.0.2.

Fig.2 - Forwarding paths between 1.0.0.3 and 2.0.0.3.

Here, the BGP decision process in 1.0.0.3 has selected 1.0.0.2 as egress since it is the nearest next-hop (from the IGP perspective). You can check how one particular router performed its route selection by running the debug dp command. The command will show the available routes at the beginning of the decision process. Then, after each decision process rule that is used, it will show how many routes remain. On the following example, you can observe that there were two different routes towards 2.0.0/24 and only one remains after the Nearest NEXT-HOP rule is executed. cbgp> bgp router 1.0.0.3 debug dp 2.0.0/24 Debug Decision Process ---------------------- AS1, 1.0.0.3, 2.0.0.0/24 [ Current Best route: ] *> 2.0.0.0/24 1.0.0.2 0 4294967295 2 i [ Eligible routes: ] * 2.0.0.0/24 1.0.0.1 0 4294967295 2 i *> 2.0.0.0/24 1.0.0.2 0 4294967295 2 i [ Highest LOCAL-PREF ] [ Shortest AS-PATH ] [ Lowest ORIGIN ] [ Lowest MED ] [ eBGP over iBGP ] [ Nearest NEXT-HOP ] *> 2.0.0.0/24 1.0.0.2 0 4294967295 2 i [ Best route ] *> 2.0.0.0/24 1.0.0.2 0 4294967295 2 i

2.5. Loading BGP routes

One exciting feature of C-BGP (i'm definitely too enthusiastic!) is the ability to load real BGP routes into the model. This is done with virtual peerings, i.e. peerings with routers that do not really exist in the model. The example below shows how you can configure a virtual peering (as shown in Fig.3). Here, 3.0.0.1 is the virtual peer and 2.0.0.3 is the router where the peering is configured. net add node 3.0.0.1 net add link 2.0.0.3 3.0.0.1 0 net node 2.0.0.3 route add 3.0.0.1/32 * 3.0.0.1 0 bgp router 2.0.0.3 add peer 3 3.0.0.1 peer 3.0.0.1 virtual peer 3.0.0.1 next-hop-self peer 3.0.0.1 up exit

There are a few constraints related to the definition of a virtual peering. First, the virtual peer must exist in the topology. This is the reason why you need to add node 3.0.0.1 with the net add node command. It might appear less virtual that you would have thought, but there is a good reason for this: topological changes will also affect routes received from virtual peers. The second requirement is that the node must be reachable. Therefore, you need to connect it to the topology. In the example, it is directly connected to node 2.0.0.3 with the net add link command. In addition to this, the router that connects to this virtual peer must be able to reach it. Router 2.0.0.3 needs a route towards 3.0.0.1. In the example, we choose to add a static route with the route add command, but it could be part of the IGP as well. Finally, the virtual BGP session needs to be configured on router 2.0.0.3. The peer virtual statement defines the BGP session as virtual. That means that the other end of the session needs not exist.

Fig.3: Adding a virtual peering.

It is now possible to inject BGP messages (updates and withdraws) in router 2.0.0.3 by using the peer recv command. The BGP message needs to be encoded in MRT ASCII format, i.e. a sequence of fields separated by a "|" character. The first field defines the protocol and it has to be "BGP4". The second field is the time when that message was collected (it is ignored by C-BGP). The third field indicates whether it is an update ("A") or withdraw ("W") message. The fourth field contains the IP address of the router where the message was collected. In C-BGP we constrain that address: it must be equal to the address of the router where it is injected. The fifth field is the AS number of the router. The sixth field is the announced prefix. The seventh field is the AS-Path. The eighth field is the origin (one of IGP, EGP or INCOMPLETE). The ninth field is the next-hop. The tenth field is the local-pref value. The eleventh field is the MED value.

Once BGP messages have been injected using the peer recv command, these messages have been processed by the destination router. However, if this router has propagated the messages, the sim run command must be issued. bgp router 2.0.0.3 peer 3.0.0.1 recv "BGP4|0|A|2.0.0.3|2|12.0.0.0/8|3 3356 7018|IGP|3.0.0.1|0|0" sim run

3. Abilene example

To be provided...

Fig.2: Abilene network's topology.

3.1. Building the topology

3.2. Configuring BGP

3.3. Loading BGP routes

3.4. Playing a NetFlow trace

!-->

4. Internet example

C-BGP was initially designed to study the macroscopic performance of BGP-based traffic engineering methods. For this purpose, we relied on large AS-level graphs where each vertex represents an AS and each edge represents a business relationship between two ASes.

There are various sources for AS-level Internet-like topologies. The most famous ones are from Subramanian et al and were inferred from real BGP routing tables. They used to put their data on-line in the past, they unfortunately withdrew it a few years ago. You can still obtain a copy of one topology from the Downloads section. The complete Internet-like example script that we will discuss in this section is available here.

4.1. Loading the topology

C-BGP allows you to directly load an AS-level topology, create routers, configure BGP adjacencies and setup routing filters according to business relationships, in a single command. Well almost. Loading an AS-level topology can be done with the bgp topology load comand. The command reads the input file and for each AS found, it creates a single BGP router. The router IP address (identifier) is derived from the AS number. Then, for each AS adjacency found in the input file, a BGP session is created between the corresponding router. To configure BGP route filters according to the business relationships, you need to run the bgp topology policies command. Finally, the bgp topology run command activates each BGP session. bgp topology load "as.relation" bgp topology install bgp topology policies bgp topology run sim run

Once the topology is loaded and the BGP sessions are established, you can propagate prefixes. For this purpose, you need to originate a prefix from a router. This is done with the bgp router add network command. In the example below, three prefixes are originated from different routers. In particular, the prefix 12.0.0.0/8 is originated from AS7018's router (0.0.27.106). Note that this simulation will take a few seconds to converge. bgp router 0.0.27.106 add network 12/8 bgp router 0.0.13.28 add network 4/8 bgp router 0.0.10.51 add network 130.104/16 bgp router 0.0.21.56 add network 81.240/13 sim run

4.2. Mining the routing states

With Internet-wide simulations, there are additional ways to explore the routing state. One convenient way is to perform an AS-level traceroute with the bgp router record-route command. The example below shows the AS-level traceroute performed between router 0.0.27.106 (AS7018) and prefix 130.104/16 (originated by AS2611). The reported AS-Path goes through 7018 3303 and 2611. cbgp> bgp router 0.0.27.106 record-route 130.104/16 0.0.27.106 130.104.0.0/16 SUCCESS 7018 3303 2611

Another possibility consists in looking at the routes received from neighbor routers. This can be done with command bgp router X show adj-rib. The example below show the BGP routes received by router 0.0.27.106 for the destination prefix 130.104/16 (we do not show all routes in the example). cbgp> bgp router 0.0.27.106 show rib-in * 130.104/16 * 130.104.0.0/16 0.0.0.71 80 4294967295 71 3356 2611 i * 130.104.0.0/16 0.0.0.101 80 4294967295 101 4513 2611 i * 130.104.0.0/16 0.0.0.174 80 4294967295 174 3257 2611 i ... * 130.104.0.0/16 0.0.12.228 100 4294967295 3300 3292 2611 i *> 130.104.0.0/16 0.0.12.231 100 4294967295 3303 2611 i * 130.104.0.0/16 0.0.12.248 100 4294967295 3320 3292 2611 i ... * 130.104.0.0/16 0.0.57.153 80 4294967295 14745 3356 2611 i * 130.104.0.0/16 0.0.88.245 100 4294967295 22773 4513 2611 i * 130.104.0.0/16 0.0.100.25 80 4294967295 25625 209 3257 2611 i