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.

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.