This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2009 proceedings.

MARA: Maximum Alternative Routing Algorithm
Yasuhiro Ohara

Shinji Imahori

Rodney Van Meter

Japan Advanced Institute of
Science and Technology
Ishikawa, Japan 923–1292
Email: yasu@jaist.ac.jp

University of Tokyo
Tokyo, Japan 113–8656
Email: imahori@mist.i.u-tokyo.ac.jp

Keio University
Kanagawa, Japan 252–8520
Email: rdv@sfc.wide.ad.jp

Abstract—In hop-by-hop networks, provision of multipath
routes for all nodes can improve fault tolerance and performance.
In this paper we study the multipath route calculation by
constructing a directed acyclic graph (DAG) which includes
all edges in the network. We define new DAG construction
problems with the objectives of 1) maximizing the minimum
connectivity, 2) maximizing the minimum max-flow, and 3) maximizing the minimum max-flow as an extension of shortest pathrouting. A family of new algorithms called Maximum Alternative
Routing Algorithms (MARAs) is described, proven formallyto solve the problems optimally, and contrasted with existing
multipath algorithms. MARAs are evaluated for the numberof paths, the length of paths, the computational complexity,
and the computation time, using simulations based on several
real Internet Autonomous System (AS) network topologies. We
show that MARAs run in sub-second times on moderate-speed
processors and achieve a significant increase in the number ofpaths compared to existing multipath routing algorithms. These
results should help further the process of deploying multipath
routing in real-world networks.

I. I NTRODUCTION
The most essential task of Internet routing systems is tocalculate routes that do not include routing loops and areconsistent on all routers. The Internet is designed as a hopby-hop network so that routers in the network need not
maintain per-session communication state, improving network
scalability in performance, in number of nodes, and in numberof sessions. Since all routers in the Internet forward packets
autonomously, they must independently make consistent decisions about the path to a destination in order to avoid routing
loops. Configuring consistent loop-free routes for a destination
is synonymous with constructing a Directed Acyclic Graph(DAG).
To a first approximation, the routing in the Internet is singlepath routing. Its goal is to find the shortest path by assigningeach edge a cost and making the routing decision so that, foreach source and destination pair of nodes, the sum of the edge
costs in the path is the minimum. This principle can be seenin all commonly used routing protocols, including RIP [1],OSPF [2], IS-IS [3], and BGP [4].
Compared to the single-path routing commonly used in theInternet, enabling the use of multiple paths simultaneously,
called multipath routing, can improve availability and transportcapacity. However, in the current shortest-path routing, eachrouter usually selects a single shortest path to a destination.
Thus, the routes to the destination form a sink tree to thedestination (called a Shortest Path Tree, or SPT), wheremultiple paths in the network can rarely be used. Although theexisting IP routing architecture allows multipath routes where
the path from the current node to the destination branches
to multiple nexthops, multipaths in the shortest path routing
require the costs to the destination on these paths to be equal,
which rarely happens. The rare multipath routes in the shortest
path routing are called Equal Cost Multi Paths (ECMPs) [2].
Note that both SPT and its ECMP extension are still a kindof DAG1 .
In order to be considered as a viable option for the evolutionof the Internet, multipath routing must be theoretically sound,as well as practically implementable. Prior work has shownthat multipath-aware end nodes are able to actively participate
in failure avoidance [5], [6], [7], but unmodified nodes also
gain benefits from the increase in connectedness and aggregate
throughput. In this paper, we focus on advancing the theory ofmultipath routing and demonstrate via implementation of ouralgorithms that multipath route calculation is indeed feasible.
Thus, multipath is advancing toward a complete, practicalsystem, and this paper checks off important points in the listof work items.
We propose a family of novel multipath route calculation
algorithms, called Maximum Alternative Routing Algorithms(MARAs). MARAs construct a DAG that includes all edges in
the network graph structure, in order to provide a significant
number of alternative paths among all nodes to a destination.
This is the first study of such DAGs for Internet routing, tothe best of our knowledge. We introduce three new graphproblems, all-to-one maximum connectivity routing problem,
all-to-one max-flow routing problem, and all-to-one maximum
shortest path alternatives problem, to describe the objectivesof the algorithms. The new routing algorithms that can solve
the problems optimally, called MARA-MC, MARA-MMMF,
and MARA-SPE, are developed. All of them are essentiallythe applications of an existing algorithm, called Maximum
Adjacency Ordering (MA ordering [8], [9]) algorithm, toInternet routing.
The main contributions of this paper are: (a) the introductionof the new graph routing problems; (b) the proposal of new
multipath routing algorithms that apply MA ordering algo1 An ECMP extension of SPT is no longer precisely a tree. In this paper
we still refer to the ECMP extension as SPT, for ease of explanation.

978-1-4244-3513-5/09/$25.00 ©2009 IEEE

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2009 proceedings.

rithm to the Internet routing; (c) the findings of the optimality
proofs; and (d) the analysis of the algorithms on several
realistic ISP topologies.
The rest of this paper is organized as follows. Concepts andrelated work for multipath routing are presented in Section II.
Section III models the routing problem and reviews the MA
ordering algorithm. Sections IV-A, IV-B, and IV-C describe
the problem, the algorithm, and the optimality proof forthe objectives of improving the connectivity, the transportcapacity, and the transport capacity with the shortest pathrouting compatibility, respectively. Section V evaluates thealgorithms with the analysis of the results (i.e., calculated
number of routes and path length), the computational complexities, and the computation time. Section VI gives theconcluding remarks.
II. M ULTIPATH ROUTING
Multipath routing can contribute to the availability of thecommunication network. Although it is commonly believedthat Internet routing systems avoid failures, in the real world,complex problems that cannot be detected by routing systems
occur, such as hardware malfunctions and software bugs inrouters [10], [11]. In theory, the rich connectivity of the Internet should exhibit high reliability. In practice, Internet routing
protocols reduce the richer graph to a non-redundant tree inmost cases. The non-redundant tree is vulnerable to failures,
which degrade communication performance and connectivity
until the route recomputation completes. For example, there
exist problems in the forwarding plane of routers, which may
remain undetected for extended periods and may ultimately
require manual intervention to correct.
Along with a path switching mechanism that does notdepend on the failure detection of a particular routing system,
advance multipath route calculation can contribute to the availability of a communication system. Examples of such a pathswitching mechanism are Deflection [5] and Drouting [6], [7],where the end host can request a change of the communication
path by changing the packet tag embedded in IP packets.
Multipath routing may also contribute to the transportcapacity of a network. In the case of shortest-path routing,the maximum available bandwidth between a source and a
destination is limited to that of the shortest path. The transportcapacity of the network is unreasonably constrained, despite
the possible availability of alternative paths with additional
bandwidth. Multipath routing can alleviate this problem by
splitting traffic to multipaths to balance the network load.
Although MPLS [12] may be considered to be a multipath
routing mechanism in this sense, this paper also considers
networks that do not employ MPLS.
Maximum flow algorithms such as Dinits’ algorithm [13]consider the max-flow for a source-destination node pair in
the graph, while the all-to-one max-flow routing problem
considers the max-flow among all nodes to a destination.
Some multipath route calculation algorithms have been
proposed in the past. Existing multipath routing methods
are based on, and are extensions of, shortest path routing.

Hence they require the administratively-established routing
cost. MPDA [14] is a link state routing algorithm which
distributes only partial topology information. MDVA [15]is a distance vector routing algorithm that uses diffusing
computation [16]. MPATH [17] is another distance vector
routing algorithm that distributes predecessor node informationof paths. MPDA, MDVA and MPATH calculate multipath
routes that are loop-free, using the Loop Free Invariant (LFI)
condition on the routing metrics.
FIR [18] computes per network interface routing tables byexecuting the Shortest Path First (SPF) calculations separately
for each of its neighbors in order to route around the failure.
In [5], Yang and Wetherall proposed Deflection, which extends
the LFI condition by utilizing the identity of the previous
hop to produce an increased number of nexthops. FIR and
Deflection are multipath routing methods created with the goalof failure avoidance. Because they provide backtracking paths
that transit the same node twice, they require complex pathswitching mechanisms, such as changing a packet’s nexthop
based on the previous hop or the incoming network interface,on a per-packet basis.
MARAs, as proposed in this paper, do not consider theadministrative routing costs normally attached to links. Our
method provides simple hop-by-hop multipath routes without
backtrackings, and thus the modification required in the pathswitching mechanism is rather simple. Furthermore, in contrast
to the LFI, which sometimes fails to utilize all the edges in the
network for routing depending on the routing metric setting,
MARAs always calculate the routes using all edges.
III. P REREQUISITES
A. General routing problem
An undirected graph G = (V, E) and a destination nodet ∈ V are given, as the graph structure of the network on which
the routes are to be calculated. The input graph is assumed tobe connected and may have multiple edges between a pair ofnodes, i.e., multigraph. In the following we utilize notations n
and m for |V | and |E|, respectively. For the destination, it isrequired to calculate routing directions on edges to indicate
routes for the hop-by-hop routing from every node to thedestination on the graph. To avoid routing loops, the resulting
directed graph should not have any directed cycles; i.e., thegoal is to find a directed acyclic graph (DAG) on the input
graph. The DAG is sometimes referred to as a routing graphin this paper.
A number of DAGs is allowed for a hop-by-hop network
to be used as a routing graph. Note that a DAG signifies onlyrouting directions for a single destination node. Thus multiple
DAGs must be calculated to produce routes for all sourcedestination pairs in the network.
This paper discusses undirected graphs as input for easeof explanation. The algorithms in this paper support directed
graphs; that is, for a given directed graph and a destinationnode, a DAG that achieves the particular objective can befound, without any modification required to the presented
algorithms.

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2009 proceedings.

Instead of deciding the direction of each edge independently,
a permutation of nodes is determined by our algorithms (i.e.,
nodes are labeled from 1 to n). A permutation of nodes sets
the direction of each edge from the higher-labeled node to thelower-labeled node. It is known that constructing a DAG on an
undirected graph is equivalent to deciding a topological orderof nodes [19].
In the next section, we review the MA ordering proposed
by Nagamochi and Ibaraki [8] that produces a permutationof nodes. MA ordering is utilized and extended by ouralgorithms, described in Sections IV-A2, IV-B2, and IV-C2.

NETWORK

B. MA OrderingWith G = (V, E) as an input, an ordering v1 , v2 , . . . , vn
of nodes is called an MA ordering if an arbitrary node s ischosen as a starting point v1 , and after choosing the first i
nodes as v1 , v2 , . . . , vi , the (i + 1)-th node vi+1 is chosenfrom the remaining nodes v that have the largest numberof edges between v and {v1 , . . . , vi }. It is known that MA
ordering is useful for various problems on graphs, such as
identifying a minimum cut between two nodes and solving
the edge-connectivity augmentation problem [9]. An algorithm
to compute an MA ordering is given in Algorithm 1, whered(v, S) denotes the number of edges between a node v and aset of nodes S (i.e., the number of edges from v to one of thenodes in S).
Algorithm 1 MA ordering algorithm
1: procedure MA ORDERING(G = (V, E), s ∈ V )2:
v1 ← s, S = {s}, T = V \ {s}
3:
i←2
4:
while i ≤ |V | do
5:choose a node v ∈ T with the largest d(v, S)
6:vi ← v, S = S ∪ {v}, T = T \ {v}
7:
i←i+1
8:
end while
9:
output ordering (v1 , v2 , . . . , vn ) of nodes
10: end procedure

For a capacitated, undirected graph G = (V, E, cap), an
ordering similar to the MA ordering is also defined. In thiscase, instead of choosing a node v ∈T with the largest d(v, S)
in Line 5, a node v with the largest w∈S cap(v, w) is chosen.
An MA ordering can be obtained in O(m + n) time for thecase without link capacity using a custom data structure, andin O(m + n log n) time for the case with link capacity using
Fibonacci heap [20], as shown by Nagamochi and Ibaraki [8].
IV. MARA S
Examples of the multipath routes calculated by MARAs areillustrated in Figure 1. The graph labeled NETWORK denotes
the network topology of AS1221. On the topology, the routes
destined to a node (upper-right in the figure) calculated by
Dijkstra, LFI, and two variants of MARAs (MARA-MC
and MARA-SPE) are shown. Notice that the result of Dijkstra
is almost non-redundant and nearly a tree, and LFI lacks somelinks present in the original graph (e.g., the upper left one).

Dijkstra

LFI

MARA-MCMARA-SPE

Fig. 1. Illustration of routes for a destination computed by Dijkstra, LFI,MARA-MC and MARA-SPE.

LFI and MARA-SPE are supersets of Dijkstra but in different
ways, and MARA-MC has a totally different orientation fromthe others. Only MARAs employ all of the links in the network
for the destination.
A. Improving connectivity
1) All-to-one Maximum Connectivity Routing Problem:
The first objective is to calculate a DAG with robustness.
The robustness of reaching from all nodes to a destinationin the network is determined by the minimum connectivity inthe routing graph. By maximizing the minimum connectivity
among all nodes to the destination node, an ideal routingthat achieves the highest robustness for the destination can beobtained. We define the problem of deciding the directionsof edges in order to maximize the minimum connectivity
among all nodes to a destination as the all-to-one maximum
connectivity routing problem. By calculating such routing forevery destination, the whole routing that achieves the mostrobustness for all source-destination pairs can be obtained.
A formal description of the all-to-one maximum connectivity routing problem is as follows. An undirected graph
G = (V, E) and the destination t ∈ V are given as inputs.
A possible solution (a routing graph, DAG) is expressed byan orientation of edges (a set of directions of all edges).
For each orientation p of the edges, kp (v, t) denotes theedge connectivity from v to t in the DAG determined byThis full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2009 proceedings.

V

kma (vk , t) = gma
V 

v

v

d(v, V  )X
kp (v  , t)(kp (v, t))labelingnFig. 2.

tVkvn , . . . , vl , . . . , vk , . . . , . . . , v1 (= t)vx , . . . , vk , . . . , . . . , vl , . . . , v1 (= t)

ma
opt

V
1

The relation between v, V  , v  , V  , X and t in Lemma 4.1

the orientation p. (kp (t, t) = +∞ is assumed for every
orientation p.) The all-to-one maximum connectivity routing
problem is to find an orientation of edges in the given graphthat maximizes the minimum connectivity among all nodes tothe destination t under the condition that the resulting directed
graph is acyclic. The problem is formulated as follows.
Maximizemin kp (v, t)

subject to

p is an acyclic orientation.

v∈V2) MARA-MC: We propose an algorithm, MARA-MC(Maximum Connectivity), that solves the all-to-one maximum
connectivity routing problem optimally. MARA-MC is very
simple: An MA ordering for an undirected graph G = (V, E)
and an destination node t ∈ V is computed using the destination t as the initial node s in Algorithm 1. Then the directionof each edge is set from the higher-labeled node to the lowerlabeled node. The direction on an edge is interpreted as a routeto the destination, with the head of the directed edge being the
nexthop of the route. The MA ordering calculates routes fromall nodes to the destination t. In order to determine routes
among all source-destination node pairs in the network, theMA ordering algorithm must be executed for each destinationin the network separately, i.e., n times. MARA-MC runs inO(m + n) time for one destination, hence O(mn + n2 ) time
for all source-destination pairs. A node must calculate routes
for all source-destination pairs to find the routes from the node
to all destinations in the network.
Below, we give an optimality proof for MARA-MC. Let v
be the bottleneck node, which is defined as the lowest-labelednode with minimum kp (v, t) in an edge orientation p. First,
in the following lemma, it is shown that the minimum cut
between the bottleneck node v and the destination t is always
the neighboring cut of v.
Lemma 4.1: Let v be the lowest-labeled node with theminimum kp (v, t). Then, kp (v, t) = d(v, V  ) holds, where V 
is the set of nodes which have lower-labels than v.
Proof: By using a relationship between the cut and theconnectivity on a graph, kp (u, t) ≤ d(u, U ) holds for every
node u = t, where U is a set of nodes having lower-labels thanu. In other words, the connectivity from u to t, i.e., kp (u, t),cannot exceed the number of edges in its neighboring cut,d(u, U ).
The equality in Lemma 4.1 is proven by contradiction.
Suppose that kp (v, t) < d(v, V  ) holds. The max-flow min-Fig. 3.

The optimality proof of MARA-MC

cut theorem on a directed graph [21] implies that there exists
a directed cut X (i.e., a partition of nodes) whose size is equal
to the connectivity from v to t, i.e., kp (v, t). Figure 2 shows
the cut X in the center, separated from v by the assumption.
v  is assumed to be the lowest-labeled node such that v and v belong to the same subset of nodes partitioned by X, and thus
is neighboring to X. Then, the following inequalities hold:kp (v, t) ≥ d(v  , V  ) ≥ kp (v  , t),where V  is the set of nodes which have lower-labels thanv  (V  is also shown in Figure 2). This contradicts theassumption that v is the lowest-labeled node with the minimum
connectivity to t.
Theorem 4.2: MARA-MC solves the all-to-one maximum
connectivity routing problem optimally.
Proof: Suppose that the MA ordering algorithm startingfrom the destination node t produced a node-ordering such thatthe label i is given to the node vi for every node in V (thedestination node has label 1, t = v1 ). Call the orientation ofedges from the higher-labeled node to the lower-labeled nodein the node ordering “ma,” and let gma be the objective value
for this orientation, i.e., the minimum connectivity among all
nodes to the destination t. Vi = {v1 , v2 , . . . , vi−1 } denotes
the set of nodes which have smaller labels than vi . By thedefinition of d(v, V  ), d(v, A) ≤ d(v, B) if A ⊆ B holds.
Let vk be the lowest-labeled node whose connectivity to
the destination node t in “ma,” kma (vk , t), is the smallest. By
using Lemma 4.1, the following equalities hold:gma = kma (vk , t) = d(vk , Vk ).
From a property of the MA ordering algorithm (in Line 5 ofAlgorithm 1), d(vi , Vk ) ≤ d(vk , Vk ) holds for i = k + 1, k +2, . . . , n, since vk is chosen earlier than vi .
Assume that there exists the other optimal ordering, whoseorientation is denoted by “opt,” that is better than the MA
ordering (i.e., gopt > gma holds). Figure 3 illustrates theassumption, using the same node labels as ma also for opt.
Let vl be the node with the lowest label in opt among a setof nodes {vk , vk+1 , . . . , vn }. In other words, vl is the node
which is to the left of vk in “ma”, but is the rightmost nodein “opt” among the nodes {vk , vk+1 , . . . , vn }. Thus, assuming
V  be the set of nodes having smaller labels than vl in opt,V  ⊆ Vk holds in Figure 3. Then, the following equalities andinequalities hold:gopt≤ kopt (vl , t) ≤ d(vl , V  ) ≤ d(vl , Vk )≤ d(vk , Vk ) = gma .

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2009 proceedings.

This contradicts the assumption that there exists a betterorientation opt with gopt > gma .
B. Improving transport capacity
1) All-to-one Max-flow Routing Problem: The next objective is to support the highest possible traffic load. A typicalrouting algorithm uses only the shortest path to support traffic
for each source-destination pair. By also using roundaboutpaths, it becomes possible to support a traffic load thatexceeds the capacity of the shortest path. The total traffic
which can be supported from a node to the destination isdetermined by the max-flow of the routing graph. Since theminimum of max-flows among all nodes to the destination
node (called the bottleneck) limits the supported range ofthe traffic demands, it is important to increase the minimum
max-flow. By maximizing the minimum max-flow among all
nodes to the destination, an ideal routing that achieves the best
support for the excess (over capacity) traffic to the destination
can be obtained. We call this maximization problem the allto-one max-flow routing problem. By calculating such routing
for every destination, the routing that achieves the best support
for all source-destination node pairs can be obtained.
A formal description of the all-to-one max-flow routing
problem is as follows. An undirected graph with link capacity
G = (V, E, cap) is given, where cap(v, w) is the capacity ofthe edge (v, w) (cap(v, w) > 0 if (v, w) ∈ E, otherwise 0).
A node t ∈ V is also given as the destination.
A solution (a routing graph, DAG) is expressed by anorientation of edges. For each orientation p of edges, fp (v, t)
denotes the amount of max-flow from v to t in the DAG
determined by the orientation p. (fp (t, t) = +∞ is assumed
for every orientation p.) The all-to-one max-flow routing
problem is to find an orientation of edges in the given graphthat maximizes the minimum max-flow among all nodes tothe destination t under the condition that the resulting directed
graph is acyclic. The problem is formulated as follows.
Maximizesubject to

The optimality proof for MARA-MMMF is very similar tothat of MARA-MC. The optimality of MARA-MMMF canbe obtained by transforming the proof of
MARA-MC whered(v, S) and kp (v, t) are substituted by w∈S cap(v, w) andfp (v, t), respectively.
C. Improving transport capacity with shortest-path compatibility1) All-to-one Maximum Shortest Path Alternatives problem:
Most existing Internet routers employ shortest-path routing.
When creating a new routing graph, it may be preferable toconstruct a DAG such that it includes the SPT. If a new routing
is consistent and is a superset of the shortest path routing, newrouters and shortest path routers can coexist in the network
simultaneously.
The objective of this section is to calculate a DAG that is
consistent and is a superset of the SPT, with the better support
for the excess traffic. We define the problem of deciding the directions of edges to maximize the minimum max-flow among
all nodes to a destination under the constraint of including SPT,
as the all-to-one maximum shortest path alternatives problem.
It is also possible to consider augmentation of connectivity, ifd(v, S) is used instead of w∈S cap(v, w) below.
A formal description of the all-to-one maximum shortest
path alternatives problem is as follows. An undirected graphwith link costs and capacity G = (V, E, cost, cap) is given,
where cost(v, w) > 0 gives the administrative cost of the edge(v, w) if (v, w) ∈ E, otherwise +∞ (the path with cost +∞is considered as unreachable). A node t ∈ V is also given as
the destination.
The all-to-one maximum shortest path alternatives problem
is to find an orientation of edges in the given graph thatmaximizes the minimum max-flow among all nodes to thedestination t under the condition that the resulting DAG(denoted by DAGp ) is a superset of SPT. The problem isformulated as follows.

min fp (v, t)

Maximizemin fp (v, t)

p is an acyclic orientation.

subject to

DAGp ⊇ SPT.

v∈V

Note that, if all link capacities in the input graph are identical, the all-to-one max-flow routing problem is synonymouswith the all-to-one maximum connectivity routing problem,
and the optimal solution would be identical.
2) MARA-MMMF: The algorithm that solves the all-to-one
max-flow routing problem optimally is called MARA-MMMF(Maximizing the Minimum Max-Flow). MARA-MMMF computes an MA ordering for an undirected
graph with link
capacity G = (V, E, cap) using w∈S cap(v, w) instead ofd(v, S) to consider the max-flow rather than the connectivity.
The difference between MARA-MC and MARA-MMMF isonly the input (the graph contains link capacity) and thepreference on the node (larger max-flow is preferred overlarger connectivity). MARA-MMMF runs in O(m + n log n)time for one destination node, and in O(mn + n2 log n) time
for all node pairs.

v∈V2) MARA-SPE: In this section, we propose an algorithm
called MARA-SPE (Shortest Path Extension) that solves
the all-to-one maximum shortest path alternatives problem.
MARA-SPE consists of two stages: (1) an SPT on thegraph G = (V, E, cost, cap) is computed using the destination
node t as the root, such that the SPT sinks to the root2 , and (2)a DAG is calculated so that all edges have identical directions
to the SPT, if the edge is included in the SPT.
In the first stage, MARA-SPE computes a SPT using
Dijkstra’s algorithm. This is done in O(m + n log n) time.
In the second stage, MARA-SPE computes an ordering of nnodes via an algorithm similar to the MA ordering algorithm.
This is formally given in Algorithm 2, where T denotes theset of nodes such that within the SPT, all the ancestors of any
node v ∈ T belong to S.
2 This is the opposite direction from the typical SPT.

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2009 proceedings.

Algorithm 2 MARA-SPE

with others, and is omitted from the simulation below.

1: procedure MARA-SPE(G = (V, E, cost, cap), t ∈ V )2:
v1 ← t, S = {t}
3:
i←2
4:
compute U = {e ∈ E | U is the SPT}
5:
while i ≤ |V | do
6:compute T = {v ∈ V \ S | ∀(v, w) ∈U, w ∈ S}
7:choose a node v ∈ T with the largest w∈S cap(v, w)
8:vi ← v, S = S ∪ {v}
9:
i←i+1
10:
end while
11:
output ordering (v1 , v2 , . . . , vn ) of nodes
12: end procedure
TABLE IT HE SAMPLE NETWORK GRAPHS USED IN THIS PAPER ( COLLECTED BY
ROCKETFUEL ). T HE # NODES AND # LINKS INCLUDE A FEWDISCONNECTED COMPONENTS .
Name
AS1221
AS1239AS1755
AS3257
AS3967
AS6461#nodes
108
315
87
161
79
141

#links
153
972
166
328
147
374

description
TelstraSprintEbone
Tiscali
ExodusAbovenet

The total computation time to update T (Line 6) isO(m + n log n). Choosing the node v ∈ T with the largestw∈S cap(v, w) (Line 7) runs in O(log n) time with a
Fibonacci heap, and the n iterations (Line 5) give a total execution cost of O(n log n). Thus, MARA-SPE runsin O(m + n log n) time for one destination node, and inO(mn + n2 log n) time for all node pairs.
The optimality proof for MARA-SPE is as follows. First,
MARA-SPE always outputs a permutation of n nodes; that is,
the size of node set T is at least 1 for any i ≤ |V | in Line 7,
since the SPT must not have any directed cycles. It is also clearthat the resulting DAG includes all the edges in the SPT withthose correct directions (this property comes from Line 6).
The optimality on the objective value can be obtained in a
fashion similar to that of MARA-MC: Let vk be the bottleneck
node with the lowest label in the orientation of MARA-SPE(denoted by spe), and vl be the node with the smallest label
in opt among a set of nodes {vk , vk+1 , . . . , vn }. Because of
the ordering of the opt, all the ancestors of vl in SPT must
be in the set V  , andthus also in Vk , since V ⊆ Vk . From
the ordering of spe, w∈Vk cap(vl , w) ≤ w∈Vk cap(vk , w)
must hold. This contradicts the assumption that the bottleneckwith the lowest label is the vk .
V. E VALUATIONIn this section MARAs are evaluated for the number and thelength of paths, the computational complexity, and the computation time. The input graphs are drawn from the Rocketfuelproject [22], and summarized in Table I. Since Rocketfuel does
not provide the bandwidth of the links, and since we do notknow any reasonable model for synthetic bandwidth for thelinks, MARA-MMMF cannot be evaluated in fair comparison

A. Number and Length of Paths
MARA-MC and MARA-SPE are evaluated by comparing
the number and the length of the computed paths to that ofDijkstra and LFI, on AS1221, AS1755, AS3257, and AS3967.
The paths are calculated by enumerating all of the paths on
the calculated DAG, for each source-destination pair. Since theenumeration of paths takes time exponential in the number ofedges, the evaluation of two larger ISPs, AS1239 and AS6461,
are omitted here.
MARA-MC and MARA-SPE exhibited a significant improvement. The average and standard deviation of the number,the average length (in nodes), and the maximum length ofpaths among source-destination pairs are shown in Table II.
The table shows that on most topologies, LFI adds onlya small number of multipaths to existing Dijkstra, MARASPE outperforms LFI for the number of additional multipaths
even under the strict restriction to retain the shortest paths,
and MARA-MC succeeds in calculating a huge number ofpaths. In AS3967, LFI seems to outperform MARA-MC and
MARA-SPE in the average number of paths. This is because
LFI computed a large number of paths to a small set ofsource-destination pairs (more than 1000 paths for 1.31% of
the source-destination pairs), and leads to the highest mean
average number of paths (this is sometimes meaningless interms of network robustness; see the distribution and its
discussion below). The average and maximum length of paths
naturally tend to become larger when more multipaths arecalculated. The use of multipaths implicitly presumes the useof longer roundabout paths.
The CCDF of the number, the average length, and the
maximum length of paths are shown in Figure 4. The figure
shows that MARA-MC consistently calculates a large numberof multipaths to a large fraction of source-destination pairs,
MARA-SPE calculates a moderate number, yet outperforms
LFI. The number of multipaths found by LFI is either worse orequivalent to that of MARA-SPE, depending on the topology
and the administrative routing cost setting. For example, inAS1221, MARA-MC calculates more than 15 multipaths for
52.65% of source-destination pairs, MARA-SPE for 34.86%,
while LFI does for only 2.17%. Dijkstra, which calculates
only ECMPs, finds few for most source-destination pairs.
Figure 4 also shows that MARAs exhibit longer path length.
For example, in AS1221, the fraction of source-destination
pairs that has the average path length more than 8 nodes is
14.89% for Dijkstra, and 16.5% for LFI, while it is 39.85%
for MARA-SPE, and 56.13% for MARA-MC.
As mentioned earlier, the average number of paths by LFI
in AS3967 outperformed MARA-MC (Table II). However,examining the distribution of number of paths in AS3967,
we see that MARAs still exhibit preferable characteristics.
In the low range, MARAs provide the same number ofpaths to a larger fraction of source-destination pairs than
LFI (although for MARA-SPE the difference is very small).
For example, LFI provides more than 15 paths to 38.43%

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2009 proceedings.

TABLE IIAVERAGE AND STANDARD DEVIATION OF THE NUMBER , THE AVERAGE LENGTH , AND THE MAXIMUM LENGTH OF PATHS IS DENOTED AS AVG (±STD ).
T HE AVERAGE LENGTH INCREASES WITH MULTIPATH ALGORITHMS DUE TO THE ACTIVE USE OF SECONDARY, LONGER PATHS .
NameAS1221

AS1755

AS3257

AS3967algorithm
Dijkstra
LFI
MARA-SPE
MARA-MC
Dijkstra
LFI
MARA-SPE
MARA-MC
Dijkstra
LFI
MARA-SPE
MARA-MC
Dijkstra
LFI
MARA-SPE
MARA-MC#paths
1.37
3.37
16.18
26.27
2.07
16.59
48.04
872.532.14
607.563743.34
10176.30
1.89
75.98
32.52
42.08

(± 0.62)(± 3.91)(± 22.63)(± 31.47)(± 1.69)(± 44.47)(± 111.18)(± 2335.69)(± 1.97)(± 2999.15)(± 14590.81)(± 37125.45)(± 1.69)(± 232.45)(± 76.92)(± 66.94)

TABLE IIIC OMPUTATIONAL COMPLEXITIES OF ROUTING ALGORITHMS . l DENOTESTHE NUMBER OF NEIGHBORING NODES FOR A NODE , m THE NUMBER OFEDGES IN THE GRAPH , AND n THE NUMBER OF NODES .
Algorithm
Bellman-Ford
Dijkstra
LFI & Deflect-1
MARA-MCMARA-MMMF
MARA-SPEAt each nodeO(mn)O(m + n log n)O(lm + ln log n)O(mn + n2 )O(mn + n2 log n)O(mn + n2 log n)OverallO(mn2 )
O(mn + n2 log n)O(mn + n2 log n)O(mn + n2 )O(mn + n2 log n)O(mn + n2 log n)of source-destination pairs, while MARA-SPE provides 15
paths to 41.5%, and MARA-MC does to 53.03%. For failure
avoidance, providing a small number of multipaths to a larger
part of the network is preferred over providing a large numberof multipaths to a small part of the network.
B. Computational Complexity
Table III gives the computational complexities for several
algorithms. The middle column is the complexity for thealgorithm at each node (router) in the network; the rightcolumn is the network-wide total computation necessary for all
nodes to calculate the routes for all source-destination pairs. ldenotes the number of neighboring nodes for a node.
Bellman-Ford [23] is the routing algorithm utilized in Distance Vector routing algorithms such as RIP. For each node,
it calculates n routes in at most m steps, and globally it
calculates this n times.
The complexity of Dijkstra, used in OSPF and IS-IS, issimilar to that of MA Ordering, in that it is O(m + n log n)
by appropriate use of Fibonacci heap. Since Dijkstra calculates
all routes from a source node to all destinations, globally it
must be calculated n times (once for each source node).
LFI, which is equivalent to Deflection rule-1 (Deflect-1), isused in MPDA, MDVA, and MPATH. For each node, LFI and
Deflect-1 require the Dijkstra calculation for each neighboring
node, and comparisons of the neighbor’s cost with the node’s
cost for each destination, which is O(ln). The complexity of

avg path len
5.79(± 1.78)
6.03(± 1.85)
6.96(± 2.37)
8.24(± 2.99)
6.08(± 2.13)
6.58(± 2.21)7.56(± 2.85)
11.71(± 4.53)
6.82(± 2.74)
7.98(± 3.09)10.36(± 4.26)
12.40(± 4.54)
5.88(± 2.16)
7.02(± 3.01)
7.33(± 2.84)
8.62(± 3.31)

max path len
5.93(± 1.87)
6.35(± 2.01)
8.27(± 3.18)
10.60(± 4.30)
6.23(± 2.22)7.31(± 2.66)
9.32(± 3.97)
16.44(± 6.79)
7.17(± 2.95)
9.66(± 4.33)
14.75(± 6.95)
18.45(± 7.50)
6.08(± 2.37)
8.36(± 4.06)
9.30(± 4.18)
10.95(± 4.64)

LFI and Deflect-1 is globally n times Dijkstra plus m costcomparisons for each destination (O(mn)).
The bottom three lines of the table show the complexity of
our MARA algorithms. The calculation is the same at every
node or router; it is, in theory, possible to share results of thecalculation among multiple nodes if desired.
Of course, the O(·) notation, by definition, hides a constantfactor and transient terms in the execution time. Those terms
can be of critical importance when considering whether todeploy a system in the real world. The next subsection
addresses these concerns.
C. Computation TimeThe CDF of the computation time of 100 executions ofDijkstra, LFI, MARA-MC, and MARA-SPE, for a single
node (not overall), are shown in Figure 5. The algorithms are
implemented in C and executed on a FreeBSD virtual machineon a VMWare ESX Server R with 2-way Dual-Core AMD
Opteron R 2.4GHz CPU and 16 GB memory. The algorithms
use the more practical priority queue, i.e., a basic heap [24],rather than a Fibonacci heap, hence the complexities differ
somewhat from those shown in Section V-B. Our implementation of Dijkstra is O((m + n) log n), LFI O(l(m + n) log n),
and MARA-MC and MARA-SPE O(n(m + n) log n). The
time is measured by reading the processor’s hardware timer
using rdtsc from a user-mode software application, hence
the operating system’s process scheduling may be negatively
affecting the variability of the results.
Carefully implemented, Dijkstra and LFI exhibited very fastcomputation in all topologies. Since theoretically all executionof MARAs at different nodes are identical, the variation incomputation time is believed to be the result of process
scheduling. The price for computing a significant numberof multipath routes in MARA-MC and MARA-SPE is theexhibited significant increase in execution time; however, thecomputation times shown are for real-world network topologies and demonstrate the feasibility of actual deployment ina real network. The average and standard deviation of theFraction of src-dst pairs

0
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

Fraction of src-dst pairs

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0

5 10 15 20 25 30 35 40 45 50#Paths in AS3967

Fig. 4.

Fraction of src-dst pairs
Fraction of src-dst pairs

MARA-MCMARA-SPE
LFI
Dijkstra

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

MARA-MCMARA-SPE
LFI
Dijkstra

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

MARA-MCMARA-SPE
LFI
Dijkstra

0

2

4

6

8 10 12 14 16 18

Average path length in AS3967

MARA-MCMARA-SPE
LFI
Dijkstra0

4 8 12 16 20 24 28 32 36
Maximum path length in AS1755

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

0 2 4 6 8 10 12 14 16 18 20 22 24 26
Average path length in AS3257
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

MARA-MCMARA-SPE
LFI
Dijkstra0 2 4 6 8 10 12 14 16 18 20 22
Maximum path length in AS1221

0 2 4 6 8 10 12 14 16 18 20 22 24
Average path length in AS1755

5 10 15 20 25 30 35 40 45 50#Paths in AS3257
MARA-MCMARA-SPE
LFI
Dijkstra

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

2 4 6 8 10 12 14 16
Average path length in AS1221

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

5 10 15 20 25 30 35 40 45 50#Paths in AS1755
MARA-MCMARA-SPE
LFI
Dijkstra00

Fraction of src-dst pairs

MARA-MCMARA-SPE
LFI
Dijkstra

MARA-MCMARA-SPE
LFI
Dijkstra

MARA-MCMARA-SPE
LFI
Dijkstra0

Fraction of src-dst pairs

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

5 10 15 20 25 30 35 40 45 50#Paths in AS1221
Fraction of src-dst pairs

Fraction of src-dst pairs

0

Fraction of src-dst pairs

MARA-MCMARA-SPE
LFI
DijkstraFraction of src-dst pairs

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

Fraction of src-dst pairs

Fraction of src-dst pairs

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2009 proceedings.

4 8 12 16 20 24 28 32 36 40
Maximum path length in AS3257

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

MARA-MCMARA-SPE
LFI
Dijkstra0 2 4 6 8 10 12 14 16 18 20 22 24
Maximum path length in AS3967

Comparison on distributions on the number, the average, and the maximum length of paths.

computation time are summarized in Table IV. Figure 5 shows
the CDF of the computation time.
VI. C ONCLUSION
Migrating the Internet from essentially single-path routing
to multipath routing can potentially improve the fault resilienceof the network, raise the aggregate bandwidth available between two nodes, and increase the utilization of otherwise idle
resources. One step toward the realization of this goal is thedevelopment of algorithms for finding the multipath routes on
the network graph.
We have developed a family of three optimal algorithms,
which we call MARA-MC, MARA-MMMF, and MARA-SPE.
This family is called MARAs, Maximum Alternative Routing
Algorithms. All three algorithms calculate a DAG that includes

all of the edges in the graph. These routing algorithms computemany multipaths, which may be used in the Internet to improve
failure avoidance. We evaluated MARAs on the number andthe length of paths and on the algorithm’s computational time,using topologies inferred from real, large networks. The results
showed that MARA-MC calculate a significant number ofmultipaths; for the several autonomous systems (ASes) weevaluated, the lowest average number of paths found was morethan twenty-five. The computation time on a modern processor
is sub-one second, verifying its feasibility in practice.
R EFERENCES[1] G. Malkin, “RIP Version 2,” IETF, RFC 2453, Nov. 1998.
[2] J. Moy, “OSPF Version 2,” IETF, RFC 2328, Apr. 1998.

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2009 proceedings.

TABLE IVAVERAGE AND STANDARD DEVIATION ( AVG (± STD )) OF THE COMPUTATION TIME IN MICRO SECONDS (µsec).

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

MARA-SPE
MARA-MC
LFI
Dijkstra0 20 40 60 80 100 120 140 160 180
Computation time (msec) in AS3257

Fig. 5.

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

0 100 200 300 400 500 600 700 800
Computation time (msec) in AS1239

Fraction

Fraction

0
10
20
30
40
50
60
Computation time (msec) in AS1221

MARA-SPE
MARA-MC
LFI
Dijkstra

AS1755(± 129.42)(± 361.14)(± 2,339.74)(± 4,486.81)
AS6461
282.43(± 155.58)
1,767.83(± 1,070.39)
32,992.62(± 7,831.13)
70,674.97(± 14,926.35)
148.60656.71
9,732.54
22,196.77

Fraction

MARA-SPE
MARA-MC
LFI
DijkstraAS1239635.34(± 272.23)
4,546.10(± 4,584.48)
163,202.06(± 34,714.66)
372,349.32(± 84,535.17)
AS3967134.70(± 114.31)
632.77(± 338.44)
8,822.24(± 1,667.75)
19,193.98(± 2,815.41)

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

MARA-SPE
MARA-MC
LFI
Dijkstra0 5 10 15 20 25 30 35 40 45
Computation time (msec) in AS3967

MARA-SPE
MARA-MC
LFI
Dijkstra0 5 10 15 20 25 30 35 40
Computation time (msec) in AS1755

Fraction

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

AS1221(± 100.66)(± 426.14)(± 2,651.98)(± 5,481.52)
AS3257270.71(± 180.51)
1,301.60(± 1,170.92)
30,802.33 (± 12,719.84)
76,288.48 (± 28,535.07)
119.41
468.1810,459.72
22,534.48

Fraction

Fractionalgorithm
Dijkstra
LFI
MARA-MCMARA-SPEalgorithm
Dijkstra
LFI
MARA-MCMARA-SPE

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

MARA-SPE
MARA-MC
LFI
Dijkstra0 20 40 60 80 100 120 140
Computation time (msec) in AS6461

Distribution of computation time of algorithms in milliseconds (msec).

[3] Intermediate system to Intermediate system routeing information exchange protocol for use in conjunction with the Protocol for providing the Connectionless-mode Network Service (ISO 8473), ISO/IEC
10589:2001.
[4] Y. Rekhter, T. Li, and S. Hares, “A border gateway protocol 4 (BGP-4),”
IETF, RFC 4271, Jan. 2006.
[5] X. Yang and D. Wetherall, “Source selectable path diversity via routing
deflections,” in ACM SIGCOMM, 2006, pp. 159–170.
[6] Y. Ohara, H. Kusumoto, O. Nakamura, and J. Murai, “Drouting architecture: Improvement of failure avoidance capability using multipath
routing.” IEICE Transactions, vol. 91-B, no. 5, pp. 1403–1415, 2008.
[7] Y. Ohara, “Routing Architecture for the Dependable Internet,” Ph.D.
dissertation, Keio University, 2008.
[8] H. Nagamochi and T. Ibaraki, “Computing edge-connectivity in multigraphs and capacitated graphs,” SIAM J. Discret. Math., vol. 5, no. 1,
pp. 54–66, 1992.
[9] ——, “Graph connectivity and its augmentation: applications of MA
orderings,” Discrete Appl. Math., vol. 123, no. 1-3, pp. 447–472, 2002.
[10] E. C. Rosen, “Vulnerabilities of network control protocols: an example,”
ACM SIGCOMM Comput. Commun. Rev., vol. 11, no. 3, pp. 10–16,
1981.
[11] T. Nolle, “What we should learn from the AT&T outage,” Network
World, vol. 15, p. 73, May 4 1998.
[12] E. Rosen, A. Viswanathan, and R. Callon, “Multiprotocol Label Switching Architecture,” IETF, RFC 3031, Jan. 2001.
[13] E. A. Dinits, “Algorithm for solution of a problem of maximum flow in
a network with power estimation,” Soviet Mathematics-Doklady, vol. 11,
no. 5, pp. 1277–1280, 1970.

[14] S. Vutukury and J. J. Garcia-Luna-Aceves, “A simple approximation tominimum-delay routing,” in ACM SIGCOMM, 1999, pp. 227–238.
[15] ——, “MDVA: A distance-vector multipath routing protocol.” in IEEE
INFOCOM, 2001, pp. 557–564.
[16] E. W. Dijkstra and C. S. Scholten, “Termination detection for diffusing
computations.” Inf. Process. Lett., vol. 11, no. 1, pp. 1–4, 1980.
[17] S. Vutukury and J. J. Garcia-Luna-Aceves, “An algorithm for multipath
computation using distance-vectors with predecessor information,” inIEEE ICCCN, 1999, pp. 534–539.
[18] S. Lee, Y. Yu, S. Nelakuditi, Z.-L. Zhang, and C.-N. Chuah, “Proactive
vs reactive approaches to failure resilient routing.” in IEEE INFOCOM,
2004, pp. 176–186.
[19] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network flows: theory,algorithms, and applications. Upper Saddle River, NJ, USA: PrenticeHall, Inc., 1993.
[20] M. L. Fredman and R. E. Tarjan, “Fibonacci heaps and their uses in
improved network optimization algorithms,” J. ACM, vol. 34, no. 3, pp.
596–615, 1987.
[21] G. B. Dantzig and D. R. Fulkerson, “On the max flow min cut theoremof networks,” The RAND Corporation, Santa Monica, California, Tech.
Rep., 1955, paper P-826.
[22] N. Spring, R. Mahajan, D. Wetherall, and T. Anderson, “Measuring ISP
topologies with rocketfuel,” IEEE/ACM Trans. Netw., vol. 12, no. 1, pp.
2–16, 2004.
[23] C. Huitema, Routing in the Internet. Upper Saddle River, NJ, USA:
Prentice-Hall, Inc., 1995.
[24] R. Sedgewick, Algorithms in C. Boston, MA, USA: Addison-WesleyLongman Publishing Co., Inc., 2002.