Skip to content

BGP simulation

This chapter describes the capabilities of ENP tool for the simulation of BGP (Border Gateway Protocol), and its collaboration with the Interior Gateway Protocol (IGP) for defining the IP routing in the network.

ENP implements the IGP/BGP routing process in a form that permits the user emulate the many routing policies that the richness of IGP/BGP allows. For this, a representative view of BGP decision process (RFC 4271 and related) is simulated.

Internal and external AS nodes

ENP considers two types of IP nodes in the network:

  • Internal nodes. These are regular IP nodes, belonging to one of the autonomous systems (ASs) in the network under study. Internal nodes can be connected among them via configured IP links, named as:

    • Internal intra-AS links, for those links between internal nodes of the same AS.
    • Internal inter-AS links, for those links between internal nodes of different ASs.

    A full mesh of iBGP connections is assumed to exist among the internal nodes of the same AS. Intra-AS routing is controlled by the IGP defined in the AS. An eBGP session is supposed to exist in each inter-AS link.

  • External-prefix nodes. These are IP nodes that represent a set of IP prefixes of external ASs. External-prefix nodes can be external sources or destinations of IP traffic that hit the network under study. The connections between internal nodes and external-prefix nodes are called external injection links. Injection links are abstract bidirectional IP links of infinite capacity, representing the form in which external traffic can reach our network. There can be at most one injection link between an external and an internal node. External-prefix nodes cannot be connected between them.

Traffic to/from external nodes

External nodes can be the source and destination of traffic, and can have one or more injection links, to internal nodes belonging to one or more ASs.

ENP permits the user the application of different policies for deciding how the traffic is injected from the external-prefix node into the network, and, in the opposite direction, how the traffic reaches the external node.

For deciding how the traffic in an external node EXT, with destination node DEST, goes out from EXT into the network, the process occurs as follows:

  • ENP gets its neighbor injection nodes that announce the destination DEST as reachable (this means these nodes are up, and the link to it is up also, and have reachability information towards DEST).
  • ENP keeps the injection nodes that have a higher PREFERENCE value fot destination DEST.
  • For non-filtered out injection nodes, if at least one of them announces an AIGP (Accumulated IGP) attribute, we keep the injection nodes which announce the AIGP attribute, and among them, the ones with minimum AIGP attribute announced.
  • For non-filtered out injection nodes, we keep those which announce a shortest length of the AS-PATH attribute. This attribute keeps a list of the ASs traversed if such next-hop is used to reach DEST
  • If more than one non-filtered out injection node reaches this point, we observe the user-configurable parameter LOAD SHARING for the external node EXT, indicating the maximum number of injection nodes permitted. The injection nodes are ordered according to its BGP ID user-defined parameter, and the ones with lower BGP ID are kept (up to LOAD SHARING value).
  • The traffic from EXT to DEST is uniformly load balanced among the decided injection points.

The form in which traffic arrives to an external node DEST, is dependent on:

  • How injection nodes of DEST node announce the destination DEST.
  • How these announcements are propagated through the rest of the network.

Both aspects are treated in the same form for external and internal destinations.

Overview of IGP/BGP process

The IP routing is governed by the interplay of IGP and BGP processes. ENP is able to accurately simulate the IGP/BGP interplay as described below. At a higher level, the IGP/BGP simulation operates as a sequence of three processes, as follows:

  • IGP process. The IGP process is launched first. According to it, the IGP Routing Information Base (IGP-RIB) of each node of each AS is updated, with the shortest path route or routes to each of the other nodes in the same AS.
  • BGP process. The BGP process is launched after the IGP process is completed. Its objective is to populate the BGP Routing Information Base (BGP-RIB) of each internal node, with the paths selected for destinations outside the AS, and the BGP attributes associated with them. Internally, this process requires several iterations to reflect how reachability information propagates across the ASs through the BGP sessions. The BGP process ends when such an iterative process converges.
  • IP routing process. The IP routing process is launched after the BGP process is completed. Its objective is to create the actual IP routing tables of the nodes, determining how to forward the traffic to any destination. This is performed with the following considerations:
  • The paths to destinations in the same AS are populated using the IGP-RIB information.
  • The paths to destinations in different ASs are populated with the BGP-RIB information.

The BGP-RIB

The BGP-RIB is a routing database in each internal IP node N, which contains the routing information that N has learned for the destinations outside the AS. Each entry in the database is tagged with the following information:

  • DESTINATION. The destination node of the traffic (i.e. representing the IP prefixes associated with that node). It is an external node or an internal node in a different AS.
  • LEARNED-VIA. The form in which the entry has been learned. Possible values are: (i) iBGP if the entry has been learned via an iBGP session, (ii) eBGP-EXT if the entry has been learned via a direct connection to DESTINATION, which is an external node, and (iii) eBGP-INT if the entry was learned via an eBGP connection with a neighbor node of a different AS.
  • LOCALPREF-OR-MED-PRIORITY. This contains the priority assigned, for preferring that entry for the destination. In BGP this priority can be implemented in various forms: (i) the AS can make an internal decision and apply it using the LOCAL PREF attribute in BGP updates, (ii) the neighbor AS can use the Multi-Exit Discriminator (MED) attribute to prioritize among different border nodes, a suggestion that the AS can apply (or not), influencing the internal routing to that destination.
  • AS-PATH. Contains the AS-PATH attribute received in the path announcement. This attribute lists the ASs that would traverse the traffic if forwarded through the next hop, e.g. in the order that would be shown in a traceroute command in normal operation.
  • AIGP. Contains the AIGP attribute announced with the path. This is related to the routing policies based on the Accumulated IGP (AIGP) attribute. The entry is not included when the AS of N has deactivated the AIGP function.
  • NEXT-HOP. The node from where this entry has been learned.

The BGP process

The BGP process is an iterative process with the following higher layer steps:

  1. For each internal node N, the BGP-RIB in N is populated with the destinations of the external nodes directly connected to N, if the associated eBGP session is active. The path is stored with the following attributes:
  2. AS-PATH. Initialized with the external node name, and as many dummy AS names as indicated by the user in the INITIAL-AS-PATH parameter.
  3. AIGP. If AIGP is active in the AS, it is initialized with 0.
  4. For each internal node N, which is also end node of a unicast or multicast demand, the BGP-RIB in N is populated with itself as destination, with the following attributes:
  5. AS-PATH. Initialized with the AS name of the node.
  6. AIGP. If AIGP is active in the AS, it is initialized with 0.
  7. For each active eBGP connection between internal nodes (of different ASs), ENP computes the paths that are announced in one direction and the other, according to the current state of BGP-RIBs. The announced paths received by node N are inserted into the BGP-RIB of N.
  8. For each active iBGP connection between internal nodes (of the same ASs), ENP computes the paths that are announced in one direction and the other, according to the current state of BGP-RIBs. The announced paths received by node N are inserted in the BGP-RIB of N.
  9. For each internal node, the BGP path selection process is applied, filtering out the non-selected paths.
  10. Steps 2-3-4 are repeated until no changes occur in the BGP-RIBs of any node, meaning that a stable BGP routing is achived.

The BGP path selection process

The BGP path selection process in each internal node N, scans the BGP entries in the BGP-RIBs and keeps those that are selected for routing, filtering out the rest. This is perfomed with a loop that sequentially process the different destination nodes that have at least one entry in the BGP-RIB. For each destination DEST, the process:

  1. Looks up the entries stored in the BGP-RIB for that destination, i.e. where DESTINATION field equals to DEST.
  2. Filters-out those entries where the NEXT-HOP node is not reachable according to the IGP.
  3. Filters-out those entries which have the node AS in the AS-PATH attribute, since routing through them would produce a routing loop.
  4. If at least one entry exists learned via iBGP or eBGP-INT, then filters-out the referred entries which have a non-maximum LOCALPREF-OR-MED-PRIORITY attribute, among all the iBGP and eBGP-INT entries for the destination.
  5. (If the AIGP function is active for the AS of N). For each entry ENP computes the estimated cost to destination given by the sum of the AIGP attribute of the entry (or zero if it does not exist), plus the IGP cost to the NEXT-HOP node of the entry. Then, it filters-out those entries which are not shortest paths according to this metric.
  6. Keeps the entries with the lower length (in number of traversed ASs) of the AS-PATH attribute.
  7. Prefers paths learned via eBGP-EXT, then eBGP-INT, then iBGP.
  8. Keeps the entries with the lower IGP cost to the NEXT-HOP node.
  9. If more than one entry exists, BGP observes the BGP LOAD SHARING limit configured in the node N, which determines in this situation the maximum number of next hops to choose. The list is ordered from lower to higher BGP ID of the next hop attribute. The entries kept correspond to those which have as next-hop a node in the top LOAD SHARING positions of the list.

The BGP announcement process in iBGP sessions

When the iBGP announcement step is triggered in node N, ENP processes the current BGP-RIB entries in N one by one (already filtered out by the BGP path selection process) and proceeds as follows:

  • If the entry has been learned via iBGP, N does not announce the entry. This is a regular BGP procedure for avoiding routing loops.
  • If the entry has been learned via eBGP-EXT or eBGP-INT, N announces DEST with the LOCALPREF-OR-MED-PRIORITY attribute value configured by the user for DEST in N

The BGP announcement process in eBGP sessions

When the eBGP announcement step is triggered in node N, ENP proceeds as follows for each eBGP session:

  • Announces all the destinations in the IGP-RIB:
  • AS-PATH attribute is set to a single element, the AS where N is.
  • AIGP. If the AS receiving the announcement has activated the AIGP option, the AIGP attribute is announced with the IGP cost from N to the destination node.
  • Announces all the entries in BGP-RIB learned via iBGP, eBGP-INT or eBGP-EXT as follows:
  • AS-PATH attribute is set to the AS-PATH attribute of the entry, with the AS of N added at the start of the list.
  • AIGP. If the AS of N has activated the AIGP option, the AIGP attribute is announced with the IGP cost from N to the NEXT-HOP node in the entry, plus the current value of AIGP in the entry.

Use cases

This section describes how the ENP IGP/BGP model is able to represent some common routing policies in IP/MPLS networks.

Hot-potato-routing

Hot-potato routing policy means that an AS routes the transit traffic (not destined to it), through the closest possible gateway router with other AS, that announces the destination.

In ENP, an AS makes hot-potato for non-local destinations, when LOCALPREF-OR-MED-PRIORITY is not assigned for the AS border routers that are announcing the destination, and AIGP is not activated in the AS. Then, the traffic will be routed to the closest node according to the IGP metric, among those with the same number of ASs traversed to the destination.

Shortest-path routing

Shortest path routing policy intends to carry the transit traffic to the destination using the path which globally announces a lowest metric to the destination considering all the traversed ASs.

In ENP, this policy can be implemented by activating the AIGP attribute in all the ASs, and no LOCALPREF-OR-MED-PRIORITY option is messing up the decisions (i.e. all LOCALPREF-OR-MED are the same for all nodes).

Manual injection point definition

The aforementioned policies can be tuned by manually setting the injection points for some or all of the destinations. For this, LOCALPREF-OR-MED-PRIORITY parameters can be tuned to reflect the injection point desired for a destination, and/or choosing a decision order for failover.