Anduo Wang

Carolyn Talcott

Boon Limin Jia
email: liminjia@cmu.edu

Thau Loo

Andre Scedrov
email: scedrov@math.upenn.edu

Boon Thau Loo
email: boonloo@cis.upenn.educlt@csl.sri.com

Analyzing BGP Instances in Maude

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The Internet today runs on a complex routing protocol called the Border Gateway Protocol or BGP in short. BGP enables Internet-service providers (ISP) world-wide to exchange reachability information to destinations over the Internet, and simultaneously, each ISP acts as an autonomous system that imposes its own import and export routing policies on route advertisements exchanged among neighboring ISPs.

Over the past few years, there has been a growing consensus on the complexity and fragility of BGP routing. Even when the basic routing protocol converges, conflicting policy decisions among different ISPs have led to route oscillation and slow convergence. Several empirical studies [START_REF] Labovitz | Internet Routing Instability[END_REF] have shown that there are prolonged periods in which the Internet cannot reliably route data packets to specific destinations due to routing errors induced by BGP. In response, the networking community has proposed several alternative Internet architectures [START_REF] Subramanian | HLP: A Next-generation Interdomain Routing Protocol[END_REF] and policy constraints (or "safety guidelines") that guarantee protocol convergence if universally adopted [START_REF] Gao | Stable internet routing without global coordination[END_REF][START_REF] Feamster | Implications of Autonomy for the Expressiveness of Policy Routing[END_REF][START_REF] Schapira | Putting BGP on the right path: A case for next-hop routing[END_REF].

One of the key requirements for designing new routing architectures and policy guidelines is the ability to study BGP network instances. These instances can come in the form of small topology configurations (called "gadgets"), which serve as examples of safe systems, or counterexamples showing the lack of convergence. They can also come from actual internal router (iBGP) and border gateway (eBGP) router configurations. Today, researchers and network operators analyze these instances by manually examining execution sequences. This process is tedious and error-prone.

The main contribution of this paper is that we present an automated tool for analyzing BGP instances, and thus relieve researchers and network operators of manual analysis. Our tool uses Maude [START_REF] Clavel | All About Maude: A High-Performance Logical Framework[END_REF], a language and tool based on rewriting logic. We encode in Maude the BGP protocol as a transition system driven by rewriting rules. Consequently, we can use the high-performance rewriting engine provided by Maude to analyze BGP instances automatically. Our tool can simulate execution runs, as well as exhaustively explore all execution runs for possible divergence.

More specifically, we developed a set of Maude libraries specifying a generalized path vector protocol that is common to all BGP instances. The generalized path vector protocol utilizes a set of unspecified routing policy functions. These unspecified functions serve as the interface for specific routing policies which are formalized as Stable Path Problems (SPP) [START_REF] Griffin | The stable paths problem and interdomain routing[END_REF]. To use our library, users only need to input the network topology and customize routing policies functions in the form of SPP. We illustrate the use of our tool by analyzing various BGP instances.

Background

BGP

BGP assumes a network model in which routers are grouped into various Autonomous Systems (AS) administrated by Internet Server Provider (ISP). An individual AS exchanges route advertisements with neighboring ASes using the path-vector protocol. Upon receiving a route advertisement, a BGP node may choose to accept or ignore the advertisement based on its import policy. If the route is accepted, the node stores the route as a possible candidate. Each node selects among all candidate routes the best route to each destination based on its local route rankings. Once a best route is selected, the node advertises it to its neighbors. A BGP node may choose to export only selected routes to its neighboring ASes based on its export policy.

BGP systems come in two flavors: external BGP (eBGP), which establishes routes between ASes; and internal BGP (iBGP), which distributes routes within an AS. At the AS-level, a BGP system can be viewed as a network of AS nodes running eBGP. Each AS is represented by one single router node in the network (its internal structure ignored), and its network state includes its neighbors (ASes), selected best path and a routing table. Route advertisements constitute the routing messages exchanged among them. Within an AS, a BGP system can be viewed as a network of two kinds of network nodes running iBGP: gateway routers and internal routers whose network states are similar to eBGP routers. iBGP allows internal routers to learn external routes (to destinations outside the AS) from gateway routers.

We model both eBGP and iBGP systems as network systems with two components: routing dynamics and routing policies. Routing dynamics specify how routers exchange routing messages, and how they update their network states accordingly. Routing policies are part of the static configuration of each router, by which the ISP operator expresses his local traffic interests and influences route decisions.

In our library, we adopt the use of Stable Paths Problems (SPP) [START_REF] Griffin | The stable paths problem and interdomain routing[END_REF] as the formal model of routing policies. An instance of the SPP S is a tuple (G, o, P, Λ), where G is a graph, o is a specific destination node 4 , P is the set of permitted (usable) paths available for each node to reach o, and Λ is the ranking functions for each node. For each node v, λ v is its ranking function, mapping its routes to natural numbers (ranks), and P v are its permitted paths, the set of available paths to reach o. A path assignment is a function π that maps each network node v ∈ V to a path π(v) ∈ P v . A path assignment is stable if each node u selects a path π(u) which is (1) the highest ranked path among its permitted paths, and ( 2) is consistent with the path chosen by the nexthop node. Consistency requires if π(u) = (uv)P then for the next-hop node v, we must have π(v) = P . A solution to the SPP is a stable path assignment.

In this paper, we are interested in analyzing BGP convergence (safety) property in the SPP formalism. A BGP system converges and is said to be safe, if it produces stable routing tables, given any sequence of routing message exchanges. We can study BGP convergence by analyzing its SPP representation: SPP instance for a safe BGP system converges to a solution in all BGP executions. Note that, the existence of an SPP solution does not guarantee convergence.

For example, Figure 1 presents an SPP in-

n0 n1 n2 [n2 n1 n0] [n2 n0] [n1 n2 n0] [n1 n0]
Fig. 1: Disagree Gadget.

stance called the Disagree "gadget". The pernode ranking functions are

λ 1 ([n1 n2 n0]) = 1, λ 1 ([n1 n0]) = 2, λ 2 ([n2 n1 n0]) = 1, and λ 2 ([n2 n0]) = 2.

Rewriting Logic and Maude

Rewriting logic [START_REF] Meseguer | Conditional Rewriting Logic as a Unified Model of Concurrency[END_REF] is a logical formalism that is based on two simple ideas: states of a system can be represented as elements of an algebraic data type, and the behavior of a system can be given by transitions between states described by rewrite rules. By algebraic data type, we mean a set whose elements are constructed from atomic elements by application of constructors. Functions on data types are defined by equations that allow one to compute the result of applying the function. A rewrite rule has the form t ⇒ t if c where t and t are patterns (terms possibly containing variables) and c is a condition (a boolean term). Such a rule applies to a system state s if t can be matched to a part of s by supplying the right values for the variables, and if the condition c holds when supplied with those values. In this case the rule can be applied by replacing the part of s matching t by t using the matching values for variables in t .

Maude [START_REF] Clavel | All About Maude: A High-Performance Logical Framework[END_REF] is a language and tool based on rewriting logic [START_REF][END_REF]. Maude provides a high performance rewriting engine featuring matching modulo associativity, commutativity, and identity axioms; and search and model-checking capabilities. Given a specification S of a concurrent system, Maude can execute this specification and allows one to observe possible behaviors of the system. One can also use the search functionality of Maude to check if a state meeting a given condition can be reached during the system's execution. Furthermore, one can model-check S to check if a temporal property is satisfied, and if not, Maude will produce a counter example. Maude also supports object-oriented specifications that enable the modeling of distributed systems as a multiset of objects that are loosely coupled by message passing. As a result, Maude is particularly amenable to the specification and analysis of network routing protocols.

A Maude Library for Encoding BGP Protocols

This section presents our Maude library for analyzing BGP instances. This library provides specification of the protocol dynamics that are common to BGP instances, and defines a routing policy template in terms of the Stable Path Problem (SPP) so that network designers can customize it to analyze a specific instance. Our library also provides support for detecting route oscillation.

BGP system Maude interpretation

Network Our library is organized into a hierarchy of Maude modules. Table 1 presents the correspondence between concepts in BGP protocols and the Maude code. We first show how our library represents a single network state of BGP system (Section 3.1). Then we explain how to capture the dynamic behavior of a local BGP router using rewrite rules. In doing so, the global network behaviors can be viewed as concurrent applications of the local rewriting rules (Section 3.2). Finally, we discuss the component in the library that detects route oscillation (Section 3.3).

Network State

A network state is represented by a multiset of network nodes (routers) and routing messages used by routers to exchange routing information. Each network node is represented by a Maude object, whose attributes consist of its routing table, best path and neighboring table. We omit the detailed Maude sort definitions, but provide an example encoding of the network node n1 in Disagree gadget show in Figure 1 as follows.

[n1 : router | routingTable: (source: n1,dest: n0,pv:(n1 n0),metric: 2), bestPath: (source: n1,dest: n0,pv:(n1 n0),metric: 2), nb: (mkNeigh(n0,2) mkNeigh(n2,1))]

The constructor for a node is [ : | , , ]. The first two elements (n1:router) specify the node's id n1, and its object class router. The next three elements are the attributes. At a given state, the routing table attribute constructed from routingTable: contains n1's current available routes. Each routing table entry stores the routing information for one particular next-hop. Here, the routing table attribute only contains one entry (source: n1, dest: n0, pv:(n1 n0), metric: 2). This route is specified by its source (source: n1), destination (dest: n0), the path vector that contains the list of nodes along the path (pv: (n1 n0)), and the cost of the route (metric: 2). This route is also used for the best path attribute, constructed from bestPath: , which contains n1's current best path. The last attribute is the neighbor table, constructed from nb: . To extract a node's local neighbor table from the network topology, we further introduce an operator mkNeigh. The first argument of mkNeigh is the identifier of the neighboring node, and the second argument the metric associated with the link to that node. Node n1 has two neighbors, node n0, the cost to which is 2 (mkNeigh(n0,2)); and node n2, the cost to which is 1 (mkNeigh(n2,1)).

Besides router objects, the second part of a network state is routing messages in the network. Typically, network nodes exchange routing information by sending each other routing messages carrying newly-learned routes. In our library, a routing message is constructed from sendPacket( , , , , ). For example, in the Disagree gadget, the initial routing message sent by node n1 to its neighbor n2 is represented by message term: sendPacket(n1,n2,n0,2,n1 n0). This message carries n1's routes to destination n0 with path vector n1 n0 at cost 2. In general, the first two arguments of sendPacket( , , , , ) denote the sender's identifier (node n1), and the receiver's identifier (node n2) respectively. The rest of the arguments specify the identifier of the destination (node n0), the metric representing the cost of the route (2), and the path vector of the routing path (n1 n0).

Protocol Dynamics

We now show how to specify network system dynamics in Maude. By modeling a BGP system as a concurrent system consisting of router objects (and the routing messages), to specify the global BGP evolution, we only need to specify the local rewrite rules governing the state transition of each BGP router.

A BGP node's dynamics can be captured by various equivalent state transitions. To reduce search space in analysis, we adopt a one-state transition: for each BGP node N, when it receives routing messages from a neighbor S, N computes the new path from the received message, updates N's routing table and re-selects best path accordingly, and finally sends out routing messages carrying its new best path information if a different best path is selected. This state transition is encoded as a single rewrite rule of the following form: Here, r1 is the identifier of this rule, and route-update is the name of this rule. Rule r1 is fired when the left-hand side is matched; that is, when a node N consists of routingTable RT, bestPath Pb, and neighboring table NB receives a route advertisement message from neighbor S. The result of applying the rule is shown on the right-hand side: the routing message is consumed, and attributes of router N are updated. Based on the result of the re-selected bestPath attribute, there are three different cases for N to update its state as specified in the three branches. Next, we explain these three cases.

Best path promotion. In any case, node N needs to first compute the new path based on its neighbor S's message asserting that S can reach D via a path PV. We define a function newPath that takes a routing message and the neighbor table as arguments, and returns the new path by first prepending N to the path announced by S, setting the new path attribute according to the local ranking function lookUpRank, and then imposing the import policy by modifying the path metric according to BGP routing policy configuration (import function). Here import and lookUpRank are unspecified routing policy functions. Together with export that we will introduce shortly, they constitute our library's specification interface for defining BGP routing policy. To specify a particular BGP instance's routing policy, the user only needs to specify import, lookUpRank and export accordingly. The first branch (case 1) is specified below. The newly computed path is compared with the current bestPath Pb, if the new one is preferred over the old value Pb, the bestPath attribute will be updated to this new path. Furthermore, if the export policy allows, the new best path value will be re-advertised to all of N's neighbors by sending them routing messages. Here the new state of N is obtained by updating the old routingTable attribute RT (updateRT function), and updating the bestPath attribute by setting it to the new value of bestPath. The updateRT function recursively checks the routing table, and for each nexthop entry, it either inserts the new path (newPath(...)) if no available route is presented; or replaces the old value with the new path. To complete the state transition, for all N's neighbors, routing messages carrying the new path are generated by multiCast function. To impose the export routing policy, before sending the new best path, export is applied to the new path to filter out the routes which are intended to be hidden from neighbors. Similar to import, export is to be instantiated by the user when analyzing a particular BGP instance. If the export routing policy prohibits the new path to be announced, export will transform it to emptyPath, which multiCast will not generate any message.

Best path remains the same. In the second branch (case 2), a new path newPath(...) is computed from the received message as before. However, the new path is no better than the current bestPath Pb. But the next-hop node of the new path and Pb are different, implying that the new path is just an alternative path 5 for N to reach the destination. As a result, the current bestPath value Pb is unchanged, and only the routingTable will be updated with this alternative path (newPath(...)). No routing messages will be generated: Here, updateRT replaces (therefore removes) the outdated Pb with the new path (newPath(...)), and newBest function re-computes the best path from newPath(...) and the remaining paths in routing table. As in case 1, to complete the state transition, the newly selected best path is sent to its neighbors by multiCast(...).

Route Oscillation Detection Support

Our library also provides extra definitions to help detect route oscillation. Our method is based on the observation that if route oscillation occurs during network system evolution, there is at least one path assignment (at a given state for a BGP system, we define the path assignment to be the collection of best paths currently selected by all network nodes) that is visited twice. Therefore, we use the following simple heuristic: we maintain a record of all path assignments for all visited states in BGP execution, and check for recurring path assignment. Note that a path assignment (best path attribute of router object) only constitutes a sub-set of the entire system state (the router objects attributes and routing messages), consequently our heuristic based on this partial system state can have false positives: our analysis may report a false route oscillation when two states are identical only in path assignments, but not the entire system states. Nevertheless, our heuristic is sound and is still helpful in detecting all potential route oscillation: when route oscillation occurs, a recurring path assignment state must occur.

More concretely, in our Maude library, we create a global logger object to keep track of the history of path assignments. For each snapshot of the network state, i.e. whenever a network node makes a local state transition and updates its best path attribute, the logger object is synchronized to create a new path assignment entry that corresponds to the updated best path. We then provide a function that checks for recurring entries in the list of visited path assignments, which can be used directly in Maude's exhaustive search to detect route oscillation.

Logger object. The global logger is represented by an object pa of Logger class which has one attribute history. At a given state, this attribute contains a list (history) of path assignments, each entry of which contains the snapshot of the network's collection of best paths in a visited state.An example logger object for the disagree gadget is the following:

{pa : Logger | history: ({[n1 n2 n0] [n2 n0]} {[n1 n2 n0] [n2 n1 n0]} {[n1 n2 n0] [n2 n0]} {[n1 n0] [n2 n0]})}
The above logger records four snapshots of the Disagree's best paths. For example, the first path assignment On the left-hand side, two objects: a router N and the global logger pa are matched to trigger the transition. As described in 3.2, in the first branch of route update where the node's best path attribute is set to newPath(...), the logger pa updates its path assignment attribute as follows: First, it creates a new path assignment entry to record newPath(...) by function updateAt(...). Then, the new entry updateAt(...) is inserted into the list of previous path assignments HIS by function historyAppend. Here, the new path assignment entry updateAt(...) is computed by updating the latest path assignment entry head(HIS) with newPath(...). The rest of branches 2 and 3 are modified similarly.

Route oscillation detection.

A network state is now a multiset of router objects, routing messages, and one global logger object. The function detectCycle detects re-curring path assignments, as follows:

eq detectCycle([ N : router | routingTable: RT, bestPath: Pb,nb: NB] cf) = detectCycle (cf) . eq detectCycle(message cf) = detectCycle (cf) . eq detectCycle({ pa : Logger | history: HIS } cf) = containCycle? (HIS) .

The first two equations ignore router objects and routing messages in the network state, and the last equation examines logger pa by function containCycle? to check for recurring path assignment entries in HIS. We will revisit the use of detectCycle to search for route oscillation in Section 5.

Specifying BGP Instance

Given a BGP instance with its network topology and routing policies, we show how to specify the instance as a SPP in our library. We discuss examples for both eBGP and iBGP.

eBGP instance

An eBGP instance can be directly modeled by an SPP instance S = (G, o, P, Λ): G, o specifies the instance's network topology, and P, Λ specifies the resulting per-node route ranking function after applying the eBGP instance's routing policies. Our library provides Maude definitions for each SPP element.

Network topology. An eBGP instance's initial network state is generated from its network topology, which is represented by a list of network nodes and links. Our library declares two constants top-Nodes and top-BGP to represent network nodes and links. For example, to specify the topology of the Disagree gadget, the user defines top-Nodes, top-BGP as follows:

eq top-Nodes = n1 n2 . eq top-BGP = (n1,n0 : 2) (n1,n2 : 1) (n2,n1 : 1) (n2,n0 : 2) .

Here, n0 is the identifier of the destination node (o). Each link is associated with its cost. Based on the value of top-Nodes and top-BGP that are input by the user, our library automatically generates Disagree's initial state by init-config function:

eq gadget = init-config (top-Nodes, top-BGP) .
The resulting gadget is a network state which consists of the two network router objects n1,n2, the four initial routing messages, and the initial logger pa, as shown in Section 5.1. In this initial state, the three attributes of each network node -the routing table and best-path and neighbor tables are computed as follows: init-config parses the BGP links in network topology (top-BGP), for each link (ni,nj : M), a new routing table entry for nj with cost M is created, and if nj == n0, then set ni's best path to the one-hop direct path ni n0, and its routing tables containing this one-hop direct route; otherwise if there is no direct link from ni to n0, set ni's best path and the routing table to emptyPath. Initial routing messages and logger pa are computed in a similar manner.

Routing policy. The route ranking function Λ and permitted paths P are the result of applying three BGP policies functions: import, export and lookUpRank. As we have discussed in Section 3, import,export,lookUpRank are three user-defined functions that serve as the specification interface for routing policies.

Functions import and lookUpRank are used to compute new routing paths from a neighbor's routing message: import filters out un-wanted paths, and lookUpRank assigns a rank to the remaining permitted paths. Note that the metric value lookUpRank (N PV) assigned by lookUpRank also determines the route's preference in route selection. export is used to filter out routes the router would like to hide.

As an example, the policy functions for Disagree are defined as follows.

eq export (P) = P . eq import (P) = P . eq lookUpRank (n1 n2 n0) = 1 . eq lookUpRank (n1 n0) = 2 . eq lookUpRank (n2 n1 n0) = 1 . eq lookUpRank (n2 n0) = 2 .

The first line says Disagree does not employ additional import/export policies. Whereas the second and third line asserts that Disagree's two nodes prefers routes through each other: For example the second line encodes node n1's ranking policy that it prefers path (n1 n2 n0) (with higher rank 1) through n2 over the direct path (n1 n0) (rank 2).

iBGP Instance

Our technical report [START_REF] Wang | Analyzing BGP instances in maude[END_REF] shows our SPP encoding of iBGP instances. The main differences between an iBGP and eBGP instances are: (1) iBGP network topology distinguishes between internal routers and gateway routers. Gateway routers runs eBGP to exchange routing information with (gateway routers of) other ISPs, while simultaneously running iBGP to exchange the external routing information with internal routers in the AS. (2) iBGP routing policy utilizes a separate IGP protocol to select best route. Internal to an AS, the ISP uses its own IGP protocol to compute shortest paths among all routers. The shortest path distance between internal routers and gateway routers are used in iBGP route selection: iBGP policy requires the internal routers to pick routes with shortest distance to its gateway router.

As a result, iBGP requires encoding two types of topologies: a signaling topology for gateway routers and internal routers to exchange routes within the AS, and a physical topology on which the IGP protocol is running. Further, an additional destination router denoting the special SPP destination o is added as an external router which is connected with all gateway routers. In our library, we implement and run separately in Maude an IGP protocol (for computing all-pairs shortest paths) and pass the resulting shortest path distances to iBGP protocol.

Analysis

To analyze BGP instances, our library allows us to (1) execute the Maude specification to simulate possible execution runs; and (2) exhaustively search all execution runs to detect route oscillation.

Network Simulation

Network initialization. For any analysis, we need to first generate a BGP instance's initial network state. For a given BGP instance, we have shown how to generate its initial state gadget from its network topology and routing policy, as described in section 4. For example, the initial state generated for Disagree is as follows: This state consists of Disagree's initial logger object pa that holds the initial path assignment [n1 n0] [n2 n0], two router objects n1,n2, and four initial routing messages.

Execution. Unlike many formal specification paradigms used in static network analysis, a Maude specification is executable. To explore one possible execution run from a given initial state gadget, we can directly use Maude's rewrite and frewrite (fair rewriting) commands. For example, we could tell Maude to execute the Disagree gadget with the following command: frew gadget . This command terminates and returns the following final state: On the other hand, with the rew command which employs a different rewriting strategy, divergence scenario is simulated and route oscillation is observed in the simulation. This is because frewrite employs a depth-first position-fair rewriting strategy, while rewrite employs a left-most, outer-most strategy that coincides with the execution trace that leads to divergence.

Route Oscillation Detection

While Maude commands frew/rew explore a small portion of possible runs of the instance, the search command allows us to exhaustively explore the entire execution space. To exhaustively search BGP execution for route oscillation, we only need to first input the BGP instance's network topology and routing policy to generate the corresponding initial state, as described in Section 4; and then use the search command to automatically search for oscillation. For example, for Disagree, we run:

search [1] gadget =>+ X such that detectCycle(X) = true .

Here, gadget is Disagree's initial state, and =>+ X tells Maude to search for any reachable network state X such that at that state, the logger pa contains recurring path assignment (detectCycle(X)=true). search command exhaustively explores Disagree runs and returns with the first Disagree state that exhibits oscillation:

{pa : Logger | history: ({[n1 n2 n0] [n2 n0]} {[n1 n2 n0] [n2 n1 n0]} {[n1 n2 n0] [n2 n0]} {[n1 n0] [n2 n0]})} [n1 : router |...] [n2 : router |...] ...
Here, the resulting path assignment content in pa exhibits an oscillation (line 1, line 3).

In general, Maude allows us to exhaustively search for violation of a safety property P by running the following command: search initialNetwork =>+ X:Configuration such that P(X) == false.

which tells Maude to exhaustively search for a network state X that violates P along all possible execution traces from the initial state initialNetwork. If Maude returns with No solution, we can conclude property P holds for all execution traces.

Case Studies

We have analyzed well-known eBGP instances, including good gadget, bad gadget, disagree [START_REF] Griffin | The stable paths problem and interdomain routing[END_REF]. In addition, we analyze two iBGP configuration instances: a 9-node iBGP gadget [START_REF] Flavel | Stable and flexible iBGP[END_REF] that is known to oscillate, and a 25-node configuration randomly extracted from the Rocketfuel [START_REF] Spring | Measuring ISP topologies with Rocketfuel[END_REF] dataset. Rocketfuel is a well-known dataset on actual iBGP configurations that are made available to the networking community. Given that an ISP has complete knowledge of its internal router configurations, the Rocketfuel experiment presents a practical use case for using our tool to check an actual BGP configuration instance for safety.

For each BGP instance, we simulate its possible executions using rewriting commands (Simulation), and check for route oscillation using exhaustive search (Exhaustive). We summarize our analysis results are as follows:

We have carried out these analysis on a laptop with 1.9 GB memory and 2.40GHz dual-cores running Debian 5.0.6. The version of Maude is Maude 2.4. While route oscillation detection explores the entire state space of the instance execution, the analysis time for rewriting based execution are measured for only one possible terminating execution (that converges to a stable path assignment). Maude. In the first row, each entry shows the simulation time in milliseconds. In the second row, for each entry, the first value denotes exhaustive search time in milliseconds, the second denotes number of states explored, and the third on whether our tool determines the instances to be safe ("Yes") or unsafe ("No").

Here we summarize findings from our case studies. Single-trace simulation is helpful in finding permanent routing oscillation. When simulating the execute trace that diverges, Maude does not terminate (e.g., in executing Bad gadget 6 ). However, simulation can miss temporary oscillations which are only manifested on a particular executing trace. When Maude terminates, single-trace simulation time increases when network size grows. On the other hand, exhaustive search always provides a solid safety proof. For instances of similar network size, the search time for a safe instance (good) is considerably longer than that of an unsafe instance (bad). For instances of different sizes, as network size grows, exhaustive search time grows exponentially. Nevertheless, even for the 25-node scenario, exhaustive search can be completed in 12 minutes. As future work, we are going to scale our analysis technique to larger networks.

Related Work

Maude is a widely used tool for a variety of protocol analysis. In addition to our use of Maude for analyzing BGP instances, there is also a huge literature of using Maude for other complex systems, such as security protocols [START_REF] Goodloe | Formal prototyping in early stages of protocol design[END_REF] , real-time systems [START_REF] Ölveczky | Real-time maude: A tool for simulating and analyzing real-time and hybrid systems[END_REF], and active networking [START_REF] Denker | Formal specification and analysis of active networks and communication protocols: The maude experience[END_REF].

Theorem proving and model checking techniques have been applied to formal verification of network protocols. For instance, in [START_REF] Bhargavan | Formal verification of standards for distance vector routing protocols[END_REF], a routing protocol standard is formalized in the SPIN model checker and HOL theorem prover, where SPIN is used to check convergence of small network instances, and HOL is used to generalize the convergence proof for arbitrary network instances. Their work focuses on basic intra-AS routing protocols such as the distance-vector protocol, and does not consider policy interactions that occur in inter-AS routing protocols such as BGP. However, while our proofs are automated by Maude's built-in simulation and exhaustive search capabilities, we are restricted to analyzing specific network instances. As future work, we plan to generalize our instance-based proofs towards more general properties on BGP stability, by leveraging Maude's connection with existing theorem provers such as PVS [START_REF]PVS Specification and Verification System[END_REF].

Arye et al. [START_REF] Arye | The Next 10,000 BGP Gadgets: Lightweight Modeling for the Stable Paths Problem[END_REF] has attempted a similar formalization of eBGP gadgets in SPP using the Alloy [1] tool. Our approach differs from theirs in the overall goal of the formalization: Ayre et al. uses Alloy to synthesize eBGP instances that exhibit certain behaviors such as divergence, whereas our approach takes an eBGP instance as input and analyzes it via simulation runs and exhaustive search. Our overall goal is to provide an easy-touse library in Maude that eases the entire process of specifying and analyzing a BGP instance. Besides, in addition to eBGP gadgets, our library also supports iBGP instances and handles iBGP route ranking generation based on a separate IGP protocol 4.2.

Conclusion and Future Work

This paper presents our development of a Maude library for specifying and analyzing BGP instances. Our work aims to automate an important task for network designers when designing BGP protocols and safe policy guidelines. Our library uses Maude's object-based specification language and enables the user to easily generate Maude specification by only requiring them to define the network topology and routing policies. To validate the feasibility of our library, we explored a variety of well-known BGP gadgets and an actual BGP instance obtained from the Rocketfuel dataset, and demonstrated the use of Maude's analysis capabilities to detect possible divergence. All Maude code described in this paper is available at http://netdb.cis.upenn. edu/discotec11.

In addition to integrating our framework with the PVS theorem prover, our ongoing work includes: (1) more case studies on BGP instances and recent guidelines to explore the limits of our library, leading to possible extensions of our Maude library; and (2) releasing our tool for network designers to use.

  if getDest(newPath(sendPacket(S,N,D,C,PV),NB))==getDest(Pb) and prefer?(newPath(sendPacket(S,N,D,C,PV),NB),Pb)==true then ([ N : router | routingTable: updatedRT(newPath(sendPacket(S,N,D,C,PV),NB),RT), bestPath: newPath(sendPacket(S,N,D,C,PV),NB), nb: NB ] multiCast(NB, export(newPath(sendPacket(S,N,D,C,PV),NB))))

  if getDest(newPath(sendPacket(S,N,D,C,PV),NB))==getDest(Pb) and getNext(newPath(sendPacket(S,N,D,C,PV),NB))==getNext(Pb) and prefer?(Pb, newPath(sendPacket(S,N,D,C,PV),NB))==true then ([ N : router | routingTable: updateRT(newPath(sendPacket(S,N,D,C,PV),NB),RT), newBest(newPath(sendPacket(S,N,D,C,PV),NB), updateRT(newPath(sendPacket(S,N,D,C,PV),NB),RT)), nb: NB ] multiCast(NB,export(newBest(newPath(sendPacket(S,N,D,C,PV),NB), updateRT(newPath(sendPacket(S,N,D,C,PV),NB), RT))))

Table 1 :

 1 Overview and Interpretation of Maude Library

	nodes	(Router) objects
	Routing messages	Terms of type Msg
	Global Network	Multiset of router objects and terms representing messages
	Protocol dynamics	Local rewriting rules
	Global network behaviors Concurrent rewrites using local rules
	Route oscillation support A Logger object recording the histories of route assignments
		and rewriting rules updating the Logger object

  Best path withdraw. The same as in the second branch, in case 3, the newly computed path newPath(...) is worse than the current bestPath Pb, but it is now routed through the same next-hop S as current bestPath Pb. The fact that S now sends a less preferred path indicates that the previous learned route Pb is no longer available at S. Therefore, we need to withdraw Pb by dropping Pb from routing table, shown as follows:

	if getDest(newPath(sendPacket(S,N,D,C,PV),NB))==getDest(Pb) and
	getNext(newPath(sendPacket(S,N,D,C,PV),NB))=/=getNext(Pb) and
	prefer?(Pb,newPath(sendPacket(S,N,D,C,PV),NB))==true
	then
	[ N : router |
	routingTable: updateRT(newPath(sendPacket(S,N,D,C,PV),NB),RT),
	bestPath: Pb,
	nb: NB ]

  Note that this final state corresponds to one of the stable path assignments of Disagree described in Section 2, where node n1 sets its best path to [n1 n0], and node n2 sets its best path to [n2 n1 n0].

	{pa : Logger |
	history: ({[n1 n0] [n2 n1 n0]} ... {[n1 n0] [n2 n0]})}
	[n1 : router |...
	bestPath: (source: n1,dest: n0,pv:(n1 n0),metric: 2), ...]
	[n2 : router |...
	bestPath: (source: n2,dest: n0,pv:(n2 n1 n0),metric: 1),...]

Table 2 :

 2 Summary of BGP analysis in

Assuming the Internet is symmetric, we can study its routing behavior by studying routing to a single destination.

Different next-hop implies the route is learned from a different neighbor.

Bad gadget always diverges and does not have any stable path assignment, therefore, when we simulate bad gadget with rewriting, Maude does not terminate, and we do not record the statistics.

Acknowledgment The authors would like to thank Yiqing Ren and Wenchao Zhou for their valuable help in generating the iBGP instances (from the Rocketfuel dataset) used in our analysis. This research is funded in part by NSF grants (IIS-0812270, CNS-0830949, CNS-0845552, TC-0905607, and CPS-0932397), AFOSR Grant No. FA9550-08-1-0352 and ONR Grant No. N00014-10-1-0365.


Uli Bornhauser

Peter Martini
email: martini@cs.uni-bonn.de

Martin Horneffer
email: martin.horneffer@telekom.de

Scalability of iBGP Path Diversity Concepts

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

From a global perspective, the Internet we know today is a network of interconnected Autonomous Systems (ASs). Global connectivity across these systems is realized by means of the Border Gateway Protocol (BGP) [START_REF] Rekhter | A Border Gateway Protocol 4 (BGP-4)[END_REF]. BGP distinguishes two operational modes, representing its basic tasks: External BGP (eBGP) terms the inter-AS mode of BGP, used to exchange routing information between ASs. To spread this information within ASs, internal BGP (iBGP), the intra-AS mode, is used. For the following discussions, being familiar with BGP [START_REF] Rekhter | A Border Gateway Protocol 4 (BGP-4)[END_REF] is most helpful.

Motivation

Today, iBGP is the de-facto standard to spread global routing information in ASs that route default-free. Since ASs may cover up to thousand routers, maybe even more, scalability is an important aspect. As a result of this fact, large ASs usually implement iBGP via Route Reflection [START_REF] Bates | BGP Route Reflection -An Alternative to Full Mesh IBGP[END_REF] or AS Confederations [START_REF] Traina | Autonomous System Confederations for BGP[END_REF]. However, the information reduction these architectures induce causes significant disadvantages in real life: Suboptimal or inconsistent routing decisions may be forced [START_REF] Bornhauser | The Scope of the iBGP Routing Anomaly Problem[END_REF], routing processes may behave undesirable [START_REF] Griffin | On the Correctness of IBGP Configuration[END_REF], and convergence may be slowed down [START_REF] Walton | Advertisement of Multiple Paths in BGP[END_REF]. A clear improvement with respect to these aspects can be achieved if the information exchange scheme improves path diversity: Instead of advertising only the best path for every address prefix, cf. [START_REF] Rekhter | A Border Gateway Protocol 4 (BGP-4)[END_REF], routers provide information on several known paths according to a certain scheme.

An improvement of path diversity seems to be the next important step in the iBGP evolution [START_REF] Raszuk | BGP Optimal Route Reflection (BGP-ORR)[END_REF]. The path diversity is determined by the amount and kind of information speakers advertise to their peers. A classical tradeoff is given by the fact that providing more routing information principally improves the system behavior while it worsens scalability. However, even if the latter aspect is of high relevance in practice, proposals for new iBGP schemes only focus on the former aspect. Scalability issues are not adequately studied. This motivated our research.

Related Work

BGP as used today was specified as a consequence of scalability problems caused by class-based IP routing [START_REF] Rekhter | Application of the Border Gateway Protocol in the Internet[END_REF] in the mid 90ies. As scalability was a critical aspect at this time, the observed and expected behavior of BGP was thoroughly studied and documented [START_REF] Traina | Experience with the BGP-4 Protocol[END_REF][START_REF] Traina | BGP-4 Protocol Analysis[END_REF]. In essence, it followed "that BGP should have no scaling problems in the area of link bandwidth and router CPU utilization". However, concerns rise with respect to iBGP, as its full-mesh design ties up many resources. This deficiency was remedied by Route Reflection and AS Confederations [START_REF] Bates | BGP Route Reflection -An Alternative to Full Mesh IBGP[END_REF][START_REF] Traina | Autonomous System Confederations for BGP[END_REF].

In the following years, several studies analyzed the expectable growth of the global routing table and average update rates per path [START_REF] Bu | On Routing Table Growth[END_REF][START_REF] Elmokashfi | On the scalability of bgp: the roles of topology growth and update rate-limiting[END_REF]. But even if they led to highly important results, conclusions on iBGP were never drawn: As routers performed well in practice and an abrupt significant load growth did not have to be expected, this did not seem to be necessary. In 2002, the situation changed drastically with the publication of the first draft of Add-path [START_REF] Walton | Advertisement of Multiple Paths in BGP[END_REF]. Applying Addpath, routers may provide their internal peers with clearly more information than common iBGP allows. The ability to advertise several paths per prefix in parallel led to the development of several path diversity schemes [START_REF] Walton | BGP Persistent Route Oscillation Solutions[END_REF][START_REF] Uttaro | Best Practices for Advertisement of Multiple Paths in BGP[END_REF][START_REF] Bornhauser | An Inherently Anomaly-free iBGP Architecture[END_REF][START_REF] Basu | Route Oscillations in I-BGP with Route Reflection[END_REF]: schemes, that would cause a significant load growth. Analyses for the Route Server architecture showed that scalability can be evaluated efficiently [START_REF] Bornhauser | An Inherently Anomaly-free iBGP Architecture[END_REF]. However, even if several path diversity schemes are already in the standardization process [START_REF] Walton | BGP Persistent Route Oscillation Solutions[END_REF][START_REF] Uttaro | Best Practices for Advertisement of Multiple Paths in BGP[END_REF], their effect on the scalability is still unknown. This is the starting point for our analyses.

Main Contribution and Paper Outline

Scalability is an essential linchpin for using an iBGP scheme productively. Nevertheless, the impact of increasing path diversity according to the proposed schemes is not well understood yet. Closing this gap is the main contribution of our paper. We focus on BGP Route Reflection, because this is the most common iBGP architecture in large ASs.

The rest of the paper is organized as follows: At first, in section 2, we give a basic outline on iBGP path diversity. After that, in section 3, we provide the theoretical groundwork to estimate the information load on routers in arbitrary ASs. In section 4, we exemplary evaluate the information load path diversity schemes induce in a large AS. In section 5, we generalize the system-specific basic results. Finally, in section 6, we close with a short conclusion and sketch future work.

About Add-path and iBGP Path Diversity

A core property of the today's iBGP routing information exchange is that routers only advertise their best path for a prefix. Since this limitation has proven to be a fundamental restriction in practice, Walton et al. started 2002 to specify a draft that relaxes this limitation, cf. [START_REF] Walton | Advertisement of Multiple Paths in BGP[END_REF]. The proposal is well-known as Add-path.

The Add-path Concept

Even if technical aspects are beyond the scope of the paper, basically understanding the Add-path proposal seems helpful. Using classical iBGP, paths are internally keyed by the destination address-prefix they belong to and the peer router they are learned from. Consequently, as shown in figure 1.a), each peer can only provide one path per prefix that is stored and taken into account in the best path selection. As depicted in figure 1.b), the basic idea behind Add-path is to extend the key of a path by another attribute, the path ID. This ID is arbitrarily set by the router that announces the path. As known paths are only replaced if they have the same key, Add-path allows routers to advertise several valid paths in parallel. The Add-path extension defines the semantics of the path ID and the required message exchange formats. However, while this defines the technical precondition for path diversity, Add-path does not specify which paths are to be announced. IBGP routing information exchange schemes are not defined. These schemes are specified in separate working documents [START_REF] Walton | BGP Persistent Route Oscillation Solutions[END_REF][START_REF] Uttaro | Best Practices for Advertisement of Multiple Paths in BGP[END_REF] and iBGP architecture proposals, cf. [START_REF] Bornhauser | An Inherently Anomaly-free iBGP Architecture[END_REF] or [START_REF] Basu | Route Oscillations in I-BGP with Route Reflection[END_REF], for example.

Routing Information Exchange Schemes

Motivated by different use-case scenarios, protocol designers have defined several different sets of paths routers shall be provided with. Due to the space limitation, we focus our studies on the most reasonable and from the scalability perspective most interesting proposals. This covers the following four concepts:

Advertisement of All Paths

The advertisement of all paths is one of the simplest schemes. It claims that routers advertise all known paths to all iBGP peers, provided that the export filters are passed. Usually, only paths are rejected which are already known at the receiver. Further details may be found in [START_REF] Uttaro | Best Practices for Advertisement of Multiple Paths in BGP[END_REF]. The basic idea is illustrated in figure 2.a).

Advertisement of n Global Neighbor-ASs Group Best Paths Advertising global neighbor-AS group best paths is a more complex, but indeed also more scalable concept. It specifies to advertise the first n best paths with respect to every peer-AS group. Knowing these paths solves certain correctness problems [START_REF] Bornhauser | An Inherently Anomaly-free iBGP Architecture[END_REF]. The concept is illustrated in figure 2.b). See [START_REF] Uttaro | Best Practices for Advertisement of Multiple Paths in BGP[END_REF] for details.

Advertisement of Optimal and Local Neighbor-AS Group Best Paths

Another promising scheme is to provide every router with its optimal path and its AS-group best path for every AS it is neighbored to. Under adequate constraints, this scheme leads to consistent and optimal routing decisions. Even if this scheme is more complex than the second one, it further reduces the information routers are provided with. The idea is shown in figure 2.c). Details may be found in [START_REF] Bornhauser | An Inherently Anomaly-free iBGP Architecture[END_REF].

Advertisement of n Best Paths

The advertisement of n best paths generalizes the common iBGP information exchange scheme. Instead of advertising the best path for each prefix, routers advertise the best n paths, cf. figure 2.d), [START_REF] Uttaro | Best Practices for Advertisement of Multiple Paths in BGP[END_REF].

a) b) c) v p 1 p 2 p 3 p 1 p 2 p 3 reflector v reflector AS x AS y AS z p 1 p 2 r 1 q 1 q 2 q 3 p 1 p 2 q 1 q 2 r 1 up to n (=2) paths per peer--AS group v reflector AS x AS z p 1 p 2 p 3 r 1 q 1 q 2 q 1 AS y p 1 AS x p 4 best path for local peer--AS all paths n (=2) best paths op>mal path d) v p 1 p 2 p 3 p 1 p 2 reflector Fig. 2.
The number of paths advertised to v may be unlimited (a), limited per prefix and peer-AS group (b), fitted to the receiver's view (c), or limited to n per prefix (d).

A Theoretical Framework for Scalability Analyses

As the schemes outlined in section 2.2 and proposed in [START_REF] Walton | BGP Persistent Route Oscillation Solutions[END_REF][START_REF] Uttaro | Best Practices for Advertisement of Multiple Paths in BGP[END_REF][START_REF] Bornhauser | An Inherently Anomaly-free iBGP Architecture[END_REF][START_REF] Basu | Route Oscillations in I-BGP with Route Reflection[END_REF] show, path diversity concepts may differ significantly. In this section, we derive an upper bound for the amount of ingoing routing information routers experience if the outlined concepts are applied.

Basic Model

Large ASs in the default-free zone where scalability is a critical aspect usually use Route Reflection to spread BGP data internally. As shown in figure 3.a), common routers in such architectures receive three different classes of paths: Firstly, there are those paths known due to external announcements. For router v, we refer to these paths as P v ext . Secondly, paths may be known due to local configuration [START_REF] Rekhter | A Border Gateway Protocol 4 (BGP-4)[END_REF]. For v, we label these paths as P v loc . The number of paths covered by both sets can be assumed as basically independent of the applied iBGP scheme. Thirdly, there is the group of internally learned paths advertised by the reflectors, labeled as set P v int . The elements and size of this set depend on the AS-internally used iBGP scheme. IBGP architectures ensure that all three sets are disjoint [START_REF] Rekhter | A Border Gateway Protocol 4 (BGP-4)[END_REF]. Thus, the information load on a common router v using iBGP scheme i is given by

|P v | i := |P v ext | + |P v loc | + |P v int | i =: |P v ext | + |P v ¬ext | i . (1)
Problematic (CPU and memory) resource requirements can be expected, if the scheme increases the amount of ingoing information drastically in comparison to common iBGP. We derive the expectable load by predicting

|P v ext | and |P v ¬ext | i .
The number of external paths a router maintains is determined by its external peering. For a fixed BGP session to a peer-AS, it receives one path for every prefix the peer-AS advertises. Generalizing this observation to all sessions a router v ∈ V maintains, cf. figure 3.b), it holds that

|P v ext | ≤ x∈peerAS(v) |pref ix(x, V )| × |session(x, v)|, (2)
where V denotes the set of all routers in the AS, peerAS(X ) the neighbor ASs of a router or a set of routers X , pref ix(x, V ) the prefixes routers in AS x advertise into the own AS, and session(x, X ) the set of sessions kept between x and X . The number of non-external paths a router keeps depends on the iBGP scheme i used in the system. We now explain how to efficiently predict |P v ¬ext | i for the path diversity proposals sketched in section 2.2. We assume that router v is connected to m redundant Route Reflectors.

Implementing the advertisement of all paths, a reflector passes on all available paths v does not already know. These are all paths external or local on any ASinternal router u ∈ V \ {v}. Thus, including the own local paths, v knows around

|P v ¬ext | 1 ≤ m× |IT | + u∈V \{v} x∈peerAS(u) |pref ix(x, V )| × |session(x, u)| (3)
non-external paths. Note that multiplying |IT | by m > 1 is not quite accurate, as routers learn their own local paths P v loc only once. However, since routers usually do not import more than a few hundreds of paths locally, this simplification can be neglected. We proceed analogously for the following estimations.

The main disadvantage of advertising all paths is that keeping several sessions to one neighbor AS generally bloats the amount of information reflectors provide. This problem is addressed if not more than n paths per prefix for every peer-AS group are advertised (scheme II). For each peer-AS x, Route Reflectors advertise n paths per prefix, provided that n or more eBGP sessions are kept between x and the border routers u ∈ V \ {v}. Also taking into account local paths, it holds that v knows around

|P v ¬ext | 2 ≤ m× |IT | + x∈peerAS(V ) |pref ix(x, V )| × min(n, |session(x, V \{v})|) (4)
non-external paths. Recall that peerAS(V ) labels all neighbor ASs of the system. Providing a router per prefix with its optimal path and n best paths for each of its local peer-ASs, the number of received paths becomes topology-dependent. Unknown optimal paths of v must all be provided internally. In the worst case, this covers one path for each globally routable and AS-internal prefix. The former prefixes are well-known and covered by the global routing table GT [START_REF] Huston | BGP Routing Table Analysis Reports (Website)[END_REF]. Latter ones are covered by IT . The unknown AS-group best paths for a router's peer-ASs have to be provided internally, too. For every peer-AS x ∈ peerAS(v), in the worst case, up to n paths per prefix AS x advertises to v must be provided. Thus, applying this scheme, router v may learn up to

|P v ¬ext | 3 ≤ m× |GT |+|IT |+ x∈peerAS(v) |pref ix(x, V )|×min(n, |session(x, V\{v})|) (5)
non-external paths via its reflectors and local configuration. Usually, n = 1 is the most reasonable configuration, cf. [START_REF] Bornhauser | An Inherently Anomaly-free iBGP Architecture[END_REF]. We assume this in what follows. Generalizing the classical iBGP scheme, reflectors can simply advertise their n best paths per prefix. Applying this scheme, a reflector advertises the |IT | ASinternal paths and up to n paths for every globally routable address-prefix. This results in up to

|P v ¬ext | 4 ≤ m × n × |GT | + |IT | (6)
non-external paths v receives. If n = 1, we estimate the non-external information load the common iBGP information exchange scheme induces.

Required Performance Data

The methodology developed in the sections 3.1 and 3.2 reveals how system-specific estimations for the information load can be determined. To apply the estimations to a production system, information on the required basic AS-performance data must be available. Understanding how to gather this information properly finally completes the theoretical framework.

As already mentioned, the number of prefixes the global routing table covers, parameter |GT |, is well known [START_REF] Huston | BGP Routing Table Analysis Reports (Website)[END_REF]. The number of system-internal prefixes |IT | should be known by the AS operator. This also holds for the number of reflectors in the system, parameter m, and the desired path diversity factor n many proposals support. Information on the peer-ASs x ∈ peerAS(u) and the number of kept sessions session(x, u) for all routers u ∈ V can be derived from the routers' BGP configurations. Based on this information, also peerAS(X ) and session(x, X ) for all sets of routers X ⊆ V and peer-ASs x can be determined. The router configurations are usually available for internal use.

The most complex task is to determine the number of prefixes |pref ix(x, V )| each peer-AS x advertises paths for into the system. Gathering exact data for a peer-AS x requires analyzing the routing tables of all internal routers that peer with x. Consequently, to gather exact data for all peer-ASs, the routing tables of all internal eBGP speakers would have to be analyzed. This is hardly realizable in large ASs. However, ASs typically advertise paths for nearly the same prefixes to routers located in the same peer-AS. Consequently, a good approximation for pref ix(x, V ) is usually already given by pref ix(x, ) for any ⊆ V | x ∈ peerAS( ). In practice, analyzing the routing tables of a small number of those routers that peer with the most ASs allows determining approximations for a large proportion of the peer-ASs. For the neighbor ASs not covered by this method, the number of advertised prefixes must be estimated. A simple estimation can be determined on the basis of the business relationship that is kept with the system: Provider ASs advertise paths for nearly all prefixes in the global routing table. For other ASs, the approximations derived for peer-ASs keeping the same business relationship can be averaged. A systematic underestimation is avoided at this point, if is chosen such that the large peer-ASs of each class are covered. They are typically known by the operator. This avoids that scalability problems remain undetected.

Performance Evaluation for a Reference System

The basic framework derived in section 3 allows operators to perform AS-specific scalability analyses for their systems. However, basis for such analyses should be a general understanding of the impact of the different schemes on the information load. For that purpose, we apply the framework to a reference system. Based on the achieved results, we identify the generalizable implications in section 5.

The Reference System AS3320

The reference system we study in this paper is the AS with the registered number 3320, considered at a snapshot in time of August 2009. The system is the Internet Backbone of Deutsche Telekom AG, labeled as AS3320 in what follows. The AS is a comparatively large transit system. At the time the data have been taken, it maintained one customer relationship to a provider AS. All in all, the system peered with 588 neighbor ASs via 1198 sessions, kept by 238 AS-internal eBGP speakers. The relationships to these systems are well-known, too. Besides eBGP speakers, the system also covered 642 exclusive iBGP speakers. At the point in time of data acquisition, the system used around 63,000 internal prefixes. The global table covered around 300,000 prefixes. Most routers learned internal BGP routing information from two redundant Route Reflectors, meaning that m = 2.

Prefix Advertisement by Neighbor-ASs

To gather information on the number of prefixes peer-ASs advertise, we analyzed the routing tables of the ten routers keeping the most eBGP sessions. The basic results are shown in figure 4: The tables allowed us to approximate |pref ix(x, V )| for the only provider and over 70% of the peer ASs. The blue bar chart shows that the provider and, according to the number of advertised prefixes, large peer ASs are connected comparatively often. In addition to provider and peer ASs, we also covered around 20% of the customer ASs. They provide fewer paths and are less often connected. All in all, analyzing the BGP routing tables of ten of 238 eBGP speakers (around 4%) allowed us to cover over 28% of the peer-ASs. The provider AS advertises paths for around 281,000 prefixes and is connected ten eBGP sessions. These are around 15 times more prefixes than a peer AS of AS3320 advertises on average (around 18,500). With around six eBGP sessions on average, peer ASs are also significantly less frequently connected than the provider AS. A customer AS in turn only provides paths for around 200 prefixes on average, which is only about 1.1% of an average peer AS. Customer ASs are also clearly less often connected via eBGP sessions: On average, the covered customer ASs keep around two sessions with AS3320. There also exist small customer and peer ASs which advertise paths only for a single prefix.

AS-specific Information Load Predictions

The expectable information load on common routers in AS3320 using the schemes outlined in section 2. Applying classical iBGP, routers have to manage two to four times more paths than prefixes are routed (black curve). The exact value depends on the externally learned information. Internally, around 2 × (|GT | + |IT |) paths are received, cf. equation 6 with m = 2, n = 1. A significantly higher load (up to the factor of two) arises on routers that learn many paths externally. Such routers keep a session to the provider AS or (several) large peer ASs, cf. the bars on the secondary y-axis.

Exchanging information on all available paths via iBGP, routers must manage 16 to 32 times more paths than today. As it can be expected, the information load would nearly be the same for all routers. Speakers which learn little information from external peers have to maintain approximately 64.1 times more paths than routable prefixes are exchanged. Routers that learn a lot of external information keep around 4% less information, since external paths are only learned once (and not twice via the reflectors). In practice, this load level would for sure increase the required resources significantly. Scalability problems seem likely.

Limiting the number of paths routers learn via an internal session to two per prefix and peer-AS group decreases the load significantly. In case of AS3320, the load could be reduced by a factor of 3.7 to 4.3 in comparison to the advertisement of all paths. The reason for this reduction becomes clear if we have a closer look at the number of sessions large peer-ASs keep, cf. figure 4: ASs advertising paths for many prefixes (i.e. the provider and the peer-ASs listed on the left hand) are mostly connected via clearly more than two eBGP sessions. This results in a lot of paths reflectors provide if the number of advertised paths per prefix and peer-AS group is not limited. Nevertheless, a load increase by a factor of four to eight compared to classical iBGP still defines a massive growth in practice.

Reflecting the two best paths, the information load in comparison to classical iBGP is only increased by a constant factor of m × |GT |, cf. equation 6. As peer-ASs advertise many paths for the same prefixes, this scheme results in a further significant information reduction. Compared to the advertisement of two paths per peer-AS group and prefix, we observed a further reduction by a factor of two to four. Providing the optimal path and the best path for the local peer-ASs, the load is further reduced on the most speakers. For routers that receive only few external data, the expectable load is comparable to classical BGP. This is due to the fact that if router v keeps only sessions with few, mostly small ASs, equation 5 can be estimated by m × (|GT | + |IT |), which is equal to |P v ¬ext | 4 for n = 1. For routers that keep eBGP sessions with the provider or (several) large peer-ASs, a load growth has to be expected. Here, besides the optimal path for every prefix, a wide range of AS-group best paths must be provided internally in the worst case. In case of AS3320, this increases the information load by a factor of up to two on some routers, cf. the routers on the right side of figure 5. Discussions with network engineers of Deutsche Telekom AG showed that for the latter two schemes, the expectable information load should be manageable in practice: Some additionally meshed routers in the reference AS manage the same amount of information today and scalability problems do not appear.

Generalization

Even if the absolute results obtained in section 4 are highly system-specific, they allow drawing general conclusions on the scalability of the studied path diversity schemes. We summarize the main aspects in what follows.

General Results

Large transit ASs in the default-free zone usually keep several sessions with large peer or provider ASs. In system-global terms, this from a forwarding perspective highly desirable property leads to a high number of paths available at the border of the AS. If all these paths are spread across a system, significant load increases in comparison to common iBGP must be expected in general. If the system peers with large-ASs clearly more often than n, exchanging only n paths per prefix and peer-AS group significantly lowers the expectable load. However, as long as paths for a comparatively high number of equal prefixes is received from different peer-ASs, a significant load growth in comparison to common iBGP must be expected. This effect is avoided if not more than a constant number of paths is advertised per prefix. The property that advertising n best paths per prefix leads to a constant load growth of (n-1)×(|IT |+|GT |) can be generalized. It is independent of AS-or other router-specific parameters, cf. equation 6. This makes the expectable load easily, reliably, and precisely predictable. The drawback of this performance behavior is that many routers may need hardware upgrades in the worst case.

Advertising the optimal path and best paths for the local peer-AS groups, the expectable load is heavily dependent on the router's peering. As long as routers peer only with few small ASs (as often the vast majority of routers in an AS do), the load is comparable to common iBGP. Routers that peer with the provider, large peer, or several mid-size peer ASs are provided with significantly more data. Even if the load increase on such routers may exceed the load induced by advertising n best paths, the limitation to few routers may be a significant advantage: Hardware updates on few devices are much easier to realize in practice. Finally, it shall be noted that equation 5 is a worst case estimation: Externally learned optimal and group best paths are not provided by the reflectors. For AS-border routers that peer with large ASs, this may relatively often be the case.

ASs without Route Reflection

A basic assumption for our load predictions is that the analyzed AS realizes the iBGP information exchange by means of Route Reflection. To finish our analyses, we sketch what should be observed if this precondition is relaxed.

Applying full-meshed iBGP (either natively or as part of AS Confederations), routers receive paths from more than m iBGP peers. Exchanging information on all paths, this has no direct influence on the information load, since routers learn the same paths. If internal peer routers limit the number of paths they announce, having more internal peers reduces the effectiveness of the information reduction. For example, if advertising n best paths is implemented, every internal peer may advertise n best paths for every prefix. Having more than m internal iBGP peers that peer with large neighbor ASs, a router may receive significantly more paths than specified by equation 6. Implementing the advertisement of the n best paths per peer-AS group in a full-meshed AS, a significant load reduction compared to exchanging all paths cannot be expected: Generally, eBGP speakers do not keep a high number of sessions to the same peer-AS. Similar reflections can be made for the other proposed path diversity schemes.

Conclusion and Future Work

In this paper, we provided the first in-depth analyses of scalability aspects important iBGP path diversity involves. For four schemes proposed by protocol designers and researchers, we developed the theoretical basis for load predictions. The results allow operators to estimate the expectable load on the basis of few basic parameters. Reference studies for a large carrier AS and their generalization led to an understanding for the pros and cons of the different schemes with respect to scalability. We found that a significant load growth has to be expected if routers spread all or the n best known paths per AS-group and prefix. Limiting the number of advertised paths on a per prefix basis or realizing a receiver-based information reduction improves the scalability usually drastically. However, it should be kept in mind that scalability is not the only relevant aspect: Every scheme comes along with specific (convergence and correctness) properties. Finally, we want to remark that we also studied the accuracy of the predictions in detail. Even if we could not present the data here, we can affirm that the results seem accurate.

Our analyses gave a first valuable insight into the scalability issues improving iBGP path diversity comes along with. However, due to the space limitation, several important and deeply interesting aspects could not be covered by our studies.

Analyzing and discussing these aspects are important aspects for future research. Examples are the composition of the load or details on the effect on the resulting CPU and memory requirements. Another area we could not discuss is iBGP schemes where the information reduction depends on topology independent path attributes as the Local Preferences or the AS-path length. Examples are AS-wide and Best Local Pref. [START_REF] Uttaro | Best Practices for Advertisement of Multiple Paths in BGP[END_REF], specified by Uttaro et al. . Understanding why certain path diversity schemes may cause scalability problems, concepts could be revised and improved. Complementary work covering these aspects is reasonable, too.

Fig. 1 .

 1 Fig. 1. Using classical BGP, routers can only store one path per prefix and peer speaker (a). The path ID removes this restriction (b).

Fig. 3 .

 3 Fig. 3. Routers know paths due to local configuration, external, and internal announcements (a). The number of known external paths depends on the eBGP peer sessions (b).

Fig. 4 .

 4 Fig. 4. Approximated number of prefixes neighbor-ASs of AS3320 advertise paths for.

Fig. 5 .

 5 Fig. 5. Information load predictions for eBGP speakers receiving paths for more than 5% of the internal and global prefixes |IT | + |GT |.

  The set of prefixes locally configured in the AS is called internal routing tableITin what follows. The vast majority of AS-internal prefixes is usually imported only once into the AS-internal BGP routing. Thus, for simplicity we assume that

u∈V |P u loc | ≈ |IT |. Based on this assumption, we can now estimate |P v ¬ext | i . 3.2 Scheme-specific Estimations for Non-external Paths |P v ¬ext | i