Routing algebras provide a formal framework for reasoning about routing problems, algorithms, and protocols. They currently underpin systems that verify the correctness of internet routing protocol configurations prior to deployment. All such protocols—from BGP to IS-IS, OSPF, and EIGRP—can be regarded as solutions to the stable routing problem, namely that of finding an equilibrium choice of forwarding neighbors at each node of a network so as to reach a common destination. To date, only partial conditions for the existence and uniqueness of stable routings have been established. In this paper, we identify an algebraic property of cycles, which we call centripetalism, that characterizes the existence of unique stable routings for all possible destinations in a network and failure scenarios. Building on this characterization, we present the Consistent-Tree algorithm, which either produces a stable routing or reports the presence of a non-centripetal cycle, in O(n2 × m) time, where n and m denote the number of nodes and links in the network, respectively.

With the rapid evolution and diversification of Internet applications, their communication-quality criteria are continuously evolving. To globally optimize communication quality, the Internet's control plane thus needs to optimize inter-domain paths on diverse criteria, and should provide extensibility for adding new criteria or modifying existing ones. However, current inter-domain routing protocols and proposals satisfy these requirements at best to a limited degree.

Clos networks have a long history in networking. In early telephone networks and classic network flow problems, Clos networks have been shown to emulate the performance properties of an ideal macro-switch connecting sources to destinations. Therefore, Clos networks are a natural choice for modern data-centers, and are widely deployed. However, data-centers operate on different traffic assumptions than those prevalent in telephone networks and network flow problems: sources and destinations are not limited to at most one flow, and each flow must be assigned to a single path. Subject to these constraints, the performance of a Clos network is no longer equivalent to that of a macro-switch.

Among the routing protocols deployed in the wired infrastructure of the Internet, the Enhanced Interior Gateway Routing Protocol (EIGRP) has the distinction of being the only one that guarantees loop-free routing of data-packets during transient periods of convergence. However, there is no good proof of this fact and no knowledge of whether the actions and behaviors of EIGRP extend beyond its specific composite metric combining delay and bandwidth. This paper generalizes EIGRP for operation with arbitrary metrics and policies. It shows that generalized-EIGRP (gEIGRP) can be used with a broad class of such metrics and policies, but less so than the protocol to which it is closest in kind, the Border Gateway Protocol (BGP). To reason reliably about the behaviors induced by the actions of gEIGRP, the paper resorts to assertional proof methods. For the class of routing metrics and policies mentioned above, it presents an invariant of gEIGRP from which two safety properties are deduced: loop-free routing at all times, and routing on destination-optimal paths in stable state. Outside that class of metrics and policies, gEIGRP may deadlock in states harboring persistent forwarding loops.

At a suitable level of abstraction, all that standard routing protocols do is iterate extension and election operations on path attributes. An extension operation composes the attribute of a path from those of a link and another path, while an election operation produces the most preferred attribute of a set of candidate attributes, given a total order on them. These protocols are guaranteed to compute optimal paths only if the extension operation and the total order are entwined by the algebraic property of isotonicity, which states that the relative preference between two attributes is not inverted when both are extended by a third attribute. We solve the problem of computing and routing on optimal paths with generality by recognizing that every total order contains a partial order for which isotonicity holds. Then, we design a partial-order vectoring protocol where every election operation produces a subset of attributes from a set of candidate attributes, rather than a single attribute as is the case with a standard vectoring protocol; the election operation is derived from the partial order, ensuring that no attribute of the set of candidate attributes is preferred to an attribute of the elected subset. Moreover, we show how partial-order vectoring protocols can be designed to allow routing on optimal paths concurrently for diverse optimality criteria. Our evaluation over publicly available network topologies and attributes, covering both intra- and inter-AS routing, evince that the sizes of elected subsets of attributes are surprisingly small and that the partial-order vectoring protocol converges fast, sometimes faster than a standard vectoring protocol operating in the absence of isotonicity.

Standard vectoring protocols, such as EIGRP, BGP, DSDV, or Babel, only route on optimal paths when the total order on path attributes that substantiates optimality is consistent with the extension operation that calculates path attributes from link attributes, leaving out many optimality criteria of practical interest. We present a solution to this problem and, more generally, to the problem of routing on multiple optimality criteria. A key idea is the derivation of a partial order on path attributes that is consistent with the extension operation and respects every optimality criterion of a designated collection of such criteria. We design new vectoring protocols that compute on partial orders, with every node capable of electing multiple attributes per destination rather than a single attribute as in standard vectoring protocols. Our evaluation over publicly available network topologies and attributes shows that the proposed protocols converge fast and enable optimal path routing concurrently for many optimality criteria with only a few elected attributes at each node per destination. We further show how predicating computations on partial orders allows incorporation of service chain constraints on optimal path routing.

Despite years of research, the Internet still lacks a routing protocol with guaranteed termination. As is well-known, decentralization of routing decisions among the Autonomous Systems (ASes) that comprise the Internet may result in permanent oscillations of the state of its routing protocol - the Border Gateway Protocol (BGP). Some permanent oscillations are made from routing loops - the propagation of routing messages around the cycles of a network - that come back time and again. We discovered that the routing loop detection capability of BGP can be sharpened to predict which routing loops potentially recur and that the import policies can be adjusted to prevent the recurrence. The resulting protocol, named Self-Stable BGP (SS-BGP), is more stable than BGP. For the broad and common class of isotone routing policies, all permament oscillations are made from recurrent routing loops. For this class of routing policies, SS-BGP terminates. Our simulations with realistic Internet topologies and realistic variations of the Gao-Rexford (GR) inter-AS routing policies show that SS-BGP arrives at stable states at the expense of alterations in the import policies of only a handful of ASes.

Most analyses of routing vector protocols, such as the Border Gateway Protocol (BGP), are conducted in the context of a single destination in a given network. In that context, for arbitrary routing policies, it is computationally intractable to determine whether or not a routing vector protocol behaves correctly. In this paper, we consider the common scenario where routing policies are specified independently of the destination. In this scenario, we demonstrate that the correctness of a routing vector protocol for all destinations in a given network equates to a property of routing policies around its cycles, designated strict absorbency, similarly to the way that the correctness of a distance vector protocol equates to cycles of positive length. A number of pragmatic conclusions can be derived from this theoretical result. For example, we show that all next-hop routing policies, which are popular in inter-domain routing and in the interconnection of routing instances, cannot fully exploit the physical redundancy of a network. As another example, we show how sibling autonomous systems of the Internet can share all routes between them without introducing oscillations into BGP.

The Internet routing system faces serious scalability challenges due to the growing number of IP prefixes that needs to be propagated throughout the network. Although IP prefixes are assigned hierarchically and roughly align with geographic regions, today's Border Gateway Protocol (BGP) and operational practices do not exploit opportunities to aggregate routing information. We present DRAGON, a distributed route-aggregation technique whereby nodes analyze BGP routes across different prefixes to determine which of them can be filtered while respecting the routing policies for forwarding data-packets. DRAGON works with BGP, can be deployed incrementally, and offers incentives for Autonomous Systems (ASs) to upgrade their router software. We illustrate the design of DRAGON through a number of examples, prove its properties while developing a theoretical model of route aggregation, and evaluate its performance. Our experiments with realistic AS-level topologies, assignments of IP prefixes, and routing policies show that DRAGON reduces the number of prefixes in each AS by at least 70% with minimal stretch in the lengths of AS-paths traversed by data packets.

The Internet routing system faces serious scalability challenges, due to the growing number of IP prefixes it needs to propagate throughout the network. For example, the Internet suffered significant outages in August 2014 when the number of globally routable prefixes went past 512K, the default size of the forwarding tables in many older routers. Although IP prefixes are assigned hierarchically, and roughly align with geographic regions, today's Border Gateway Protocol (BGP) and operational practices do not exploit opportunities to aggregate routes. We present a distributed route-aggregation technique (called DRAGON) where nodes analyze BGP routes across different prefixes to determine which of them can be filtered while respecting the routing policies for forwarding data-packets. DRAGON works with BGP, can be deployed incrementally, and offers incentives for ASs to upgrade their router software. We present a theoretical model of route-aggregation, and the design and analysis of DRAGON. Our experiments with realistic assignments of IP prefixes, network topologies, and routing policies show that DRAGON reduces the number of prefixes in each AS by about 80% and significantly curtails the number of routes exchanged during transient periods of convergence.

Many operators run more than one routing instance-more than one routing protocol, or more than one instance of a given routing protocol-in their networks. Route election and route redistribution are mechanisms introduced by router vendors to interconnect routing instances. We show that these mechanisms do not heed basic performance goals. Especially, we show that, in general, they do not allow network configurations that are simultaneously free from routing anomalies and resilient to failures. We then propose a new form of interconnection that overcomes the limitations of route election and route redistribution, permitting the configuration of a resilient and efficient routing system. We conduct a thorough study of this new form of interconnection, presenting conditions for its correctness and optimality. The precepts of the study are applied to routing instances substantiated by the current Internal Gateway Protocols of the Internet: RIP, OSPF, IS-IS, IGRP, and EIGRP.

We present three route aggregation strategies to scale the Internet's inter-domain routing system. These strategies result from a keen understanding on how the customer-provider, peer-peer routing policies propagate routes belonging to long prefixes in relation to how they propagate routes belonging to shorter prefixes that cover the long ones. The first strategy, Coordinated Route Suppression, requires coordination between the Autonomous Systems (ASs) of the Internet, and we present a protocol to perform such coordination. The second strategy, No Import Provider Routes, does not require any coordination between the ASs, but benefits only some of them. The third strategy, Implicit Long Routes, does not rely on any coordination between the ASs either and it is the most efficient strategy. However, it presupposes modifications to the way routers build their forwarding tables. We evaluate the three route aggregation strategies over a publicly available description of the Internet topology and on synthetically generated Internet-like topologies. The results are very promising, with savings in the amount of state information required to sustain inter-domain close to the optimum possible.

Route-vector protocols, such as the Border Gateway Protocol (BGP), have nodes elect and exchange routes in order to discover paths over which to send traffic. We ask the following: What is the minimum number of links whose failure prevents a route-vector protocol from finding such paths? The answer is not obvious because routing policies prohibit some paths from carrying traffic and because, on top of that, a route-vector protocol may hide paths the routing policies would allow. We develop an algebraic theory to address the above and related questions. In particular, we characterize a broad class of routing policies for which we can compute in polynomial time the minimum number of links whose failure leaves a route-vector protocol without a communication path from one given node to another. The theory is applied to a publicly available description of the Internet topology to quantify how much of its intrinsic connectivity is lost due to the traditional customer-provider, peer-peer routing policies and how much can be regained with simple alternative policies.

We investigate the interaction between data and acknowledgment (ACK) traffic in Wireless LANs (WLANs) with hidden nodes. The multiple access protocols considered are Carrier Sense Multiple Access (CSMA) and Request-To-Send- Clear-To-Send (RTS-CTS), with access priority given to ACK packets over data packets, as in the IEEE 802.11 standard. The priority given to ACK packets protects them from being destroyed by data packets. We show the converse to hold under RTS-CTS, but not under CSMA, i.e., under the latter protocol ACK packets can destroy data packets. The resulting system capacity is much lower than that predicted by most of the existing studies, where this effect is not accounted for. To boost the performance of CSMA WLANs, we propose and evaluate a technique for grouping ACKs pertaining to different data packet transmissions. Our conclusions are substantiated by an analytical model and further corroborated by simulation.

There is a shortage of routing protocols that meet the needs of network engineers. This has led to BGP being pressed into service as an IGP, despite its lack of convergence guarantees. The development, standardization, and deployment of routing protocols, or even minor changes to existing protocols, are very difficult tasks. We present an approach called Metarouting that defines routing protocols using a high-level and declarative language. Once an interpreter for a metarouting language is implemented on a router, a network operator would have the freedom to implement and use any routing protocol definable in the language. We enforce a clean separation of protocol mechanisms (link-state, path-vector, adjacency maintenance, and so on) from routing policy (how routes are described and compared). The Routing Algebra framework of Sobrinho [25] is used as the theoretical basis for routing policy languages. We define the Routing Algebra Meta-Language (RAML) that allows for the construction of a large family of routing algebras and has the key property that correctness conditions --- guarantees of convergence with respect to the chosen mechanisms --- can be derived automatically for each expression defining a new routing algebra.

Although request-to-send clear-to-send (RTS-CTS) has been introduced as a uniform improvement over carrier sense multiple access (CSMA) in a wireless LAN environment, it is not. As it tries to solve the hidden-stations problem of CSMA, it creates new problems derived from the interaction among its control and data packets. We systematically identify and classify the sequences of events where CSMA and RTS-CTS depart from an ideal behavior, and we define a reference configuration and an analytical model on the basis of which a comparative study of protocol performance is made. The results show that RTS-CTS falls short of an ideal protocol, in some cases performing even worse than CSMA. This is especially noticeable in situations where the interaction between control packets in RTS-CTS prevents transmissions that under CSMA could occur concurrently and successfully.

We develop a non-classic algebraic theory for the purpose of investigating the convergence properties of dynamic routing protocols. The algebraic theory can be regarded as a generalization of shortest-path routing, where the new concept of free cycle generalizes that of a positive-length cycle. A primary result then states that routing protocols always converge, though not necessarily onto optimal paths, in networks where all cycles are free. Monotonicity and isotonicity are two algebraic properties that strengthen convergence results. Monotonicity implies protocol convergence in every network, and isotonicity assures convergence onto optimal paths. A great many applications arise as particular instances of the algebraic theory. In intra-domain routing, we show that routing protocols can be made to converge to shortest and widest paths, for example, but that the composite metric of Internet Gateway Routing Protocol (IGRP) does not lead to optimal paths. The more interesting applications, however, relate to inter-domain routing and its Border Gateway Protocol (BGP), where the algebraic framework provides a mathematical template for the specification, design, and verification of routing policies. We formulate existing guidelines for inter-domain routing in algebraic terms, propose new guidelines contemplating backup relationships between domains, and derive a sufficient condition for signaling correctness of internal-BGP.

Path vector protocols are currently in the limelight, mainly because the inter-domain routing protocol of the Internet, BGP (Border Gateway Protocol), belongs to this class. In this paper, we cast the operation of path vector protocols into a broad algebraic framework and relate the convergence of the protocol, and the characteristics of the paths to which it converges, with the monotonicity and isotonicity properties of its path compositional operation. Here, monotonicity means that the weight of a path cannot decrease when it is extended, and isotonicity means that the relationship between the weights of any two paths with the same origin is preserved when both are extended to the same node. We show that path vector protocols can be made to converge for every network if and only if the algebra is monotone, and that the resulting paths selected by the nodes are optimal if and only if the algebra is isotone as well.Many practical conclusions can be drawn from instances of the generic algebra. For performance-oriented routing, typical in intra-domain routing, we conclude that path vector protocols can be made to converge to widest or widest-shortest paths, but that the composite metric of IGRP (Interior Gateway Protocol), for example, does not guarantee convergence to optimal paths. For policy-based routing, typical in inter-domain routing, we formulate existing guidelines as instances of the generic algebra and we propose new ones. We also show how a particular instance of the algebra yields a sufficient condition for signaling correctness of internal BGP.

Prompted by the advent of quality-of-service routing in the Internet, we investigate the properties that path weight functions must have so that hop-by-hop routing is possible and optimal paths can be computed with a generalization of E.W. Dijkstra's algorithm (see Numer. Math., vol.1, p.269-71, 1959). We define an algebra of weights which contains a binary operation, for the composition of link weights into path weights, and an order relation. Isotonicity is the key property of the algebra. It states that the order relation between the weights of any two paths is preserved if both of them are either prefixed or appended by a common, third, path. We show that isotonicity is both necessary and sufficient for a generalized Dijkstra's algorithm to yield optimal paths. Likewise, isotonicity is also both necessary and sufficient for hop-by-hop routing. However, without strict isotonicity, hop-by-hop routing based on optimal paths may produce routing loops. They are prevented if every node computes what we call lexicographic-optimal paths. These paths can be computed with an enhanced Dijkstra's algorithm that has the same complexity as the standard one. Our findings are extended to multipath routing as well. As special cases of the general approach, we conclude that shortest-widest paths can neither be computed with a generalized Dijkstra's algorithm nor can packets be routed hop-by-hop over those paths. In addition, loop-free hop-by-hop routing over widest and widest-shortest paths requires each node to compute lexicographic-optimal paths, in general.

Prompted by the advent of QoS routing in the Internet, we investigate the properties that path weight functions must have so that hop-by-hop routing is possible and optimal paths can be computed with a generalized Dijsktra's (1959) algorithm. For this purpose we define an algebra of weights which contains a binary operation, for the composition of link weights into path weights, and an order relation. Isotonicity is the key property of the algebra. It states that the order relation between the weights of any two paths is preserved if both of them are either prefixed or appended by a common, third, path. We show that isotonicity is both necessary and sufficient for a generalized Dijkstra's algorithm to yield optimal paths. Likewise, isotonicity is also both necessary and sufficient for hop-by-hop routing. However, without strict isotonicity, hop by-hop routing based on optimal paths may produce routing loops. They are prevented if every node computes what we call lexicographic-optimal paths. These paths can be computed with an enhanced Dijkstra's algorithm that has the same complexity as the standard one. Our findings are extended to multipath routing as well. As special cases of the general approach, we conclude that shortest-widest paths can neither be computed with a generalized Dijkstra's algorithm nor can packets be routed hop-by-hop over those paths. In addition, loop free hop by hop routing over widest and widest-shortest paths requires that each node computes lexicographic-optimal paths, in general.

Carrier sense multiple access (CSMA) is one of the most pervasive medium access control (MAC) schemes in ad hoc, wireless networks. However, CSMA and its current variants do not provide quality-of-service (QoS) guarantees for real-time traffic support. This paper presents and studies black-burst (BB) contention, which is a distributed MAC scheme that provides QoS real-time access to ad hoc CSMA wireless networks. With this scheme, real-time nodes contend for access to the channel with pulses of energy-so called BBs-the durations of which are a function of the delay incurred by the nodes until the channel became idle. It is shown that real-time packets are not subject to collisions and that they have access priority over data packets. When operated in an ad hoc wireless LAN, BB contention further guarantees bounded and typically very small real-time delays. The performance of the network can approach that attained under ideal time division multiplexing (TDM) via a distributed algorithm that groups real-time packet transmissions into chains. A general analysis of BB contention is given, contemplating several modes of operation. The analysis provides conditions for the scheme to be stable. Its results are complemented with simulations that evaluate the performance of an ad hoc wireless LAN with a mixed population of data and real-time nodes.

EQuB is an overlay mechanism to Ethernet's MAC protocol that provides QoS guarantees to real-time applications. In its basic form, EQuB relies on the sensing and collision detection abilities of standard network interface cards and, in addition, requires only that those cards be capable of sending jam signals-so called black bursts-of pre-specified durations. EQuB gives access priority to real-time traffic, provides round-robin service among real-time hosts and guarantees a small, bounded delay to real-time packets. We also discuss enhancements to the basic EQuB mechanism that improve its performance. Simulation results are presented that assess the performance of 10 and 100 BASE-T Ethernet LANs with a mixed population of data and real-time hosts. We conclude that, in spite of the priority, attained by real-time traffic, data packer delays are not significantly affected as data load is traded for real-time load, and this is because EQuB dispatches packets to the channel much more efficiently than Ethernet's MAC protocol.

An asynchronous multiple access protocol is presented for integrated voice/data communications in wireless networks, whereby the base station coordinates the uplink access of terminals within its cell with short controlling messages. Voice terminals are given access rights to the channel in a round-robin order, and transmit variable length packets to adapt to congestion. On the other hand, data terminals have to contend for air-time with minipackets, on invitation from the base station. Minipacket conflicts, whenever they occur, are expeditiously resolved with a binary splitting tree algorithm. The protocol is developed to allow downlink and uplink traffic to time-share a common radio channel. Voice and data access procedures are multiplexed by the base station with a (T/sub v/,T/sub d/)-scheme, whereby voice and data traffic are served alternately for a maximum of T/sub v/ and T/sub d/ seconds, respectively. The resulting multiple access protocol lends itself to flexible access procedures, while providing an efficient use of the available bandwidth. In addition, very low data packet delays can be achieved without deteriorating the performance of voice traffic.