Resilient Operation of Transportation Networks
via Variable Speed Limits
A. Yasin Yazıcıoğlu, Mardavij Roozbehani, and Munther A. Dahleh
Laboratory for Information and Decision Systems
Massachusetts Institute of Technology, Cambridge, MA 02139, USA

arXiv:1609.06700v1 [cs.SY] 21 Sep 2016

yasiny@mit.edu, mardavij@mit.edu, dahleh@mit.edu

Abstract— In this paper, we investigate the use of variable
speed limits for resilient operation of transportation networks,
which are modeled as dynamical flow networks under local
routing decisions. In such systems, some external inflow is
injected to the so-called origin nodes of the network. The total
inflow arriving at each node is routed to its operational outgoing
links based on their current particle densities. The density on
each link has first order dynamics driven by the difference of
its incoming and outgoing flows. A link irreversibly fails if it
reaches its jam density. Such failures may propagate in the
network and cause a systemic failure. We show that larger link
capacities do not necessarily help in preventing systemic failures
under local routing. Accordingly, we propose the use of variable
speed limits to operate the links below their capacities, when
necessary, to compensate for the lack of global information and
coordination in routing decisions. Our main result shows that
systemic failures under feasible external inflows can always be
averted through a proper selection of speed limits if the routing
decisions are sufficiently responsive to local congestion and the
network is initially uncongested. This is an attractive feature as
it is much easier in practice to adjust the speed limits than to
build more physical capacity or to alter routing decisions that
are determined by social behavior.

I. I NTRODUCTION
Resilience is a critical aspect in the design and operation of
infrastructure systems such as transportation, power, water,
and communication networks. In many applications, the
network faces various disturbances and operates under the
actions taken by users with limited information about the
system. Such a distributed operation of the network often
results in a suboptimal global performance (e.g., [1]), and
it may even lead to cascading failures with severe systemic
consequences (e.g., [2], [3]). Accordingly, there has been a
significant research interest in modeling cascading failures
on networks (e.g., [3], [4], [5]), investigating the influence
of network topology on failure propagation (e.g., [6], [7]),
and designing networks (e.g., [8], [9]) and control policies
(e.g, [2], [3], [10], [11]) for resilient operation.
The main focus of this paper is on transporation networks under local routing decisions, which are modeled as
dynamical flow networks as in [2], [3]. In such networks,
some external inflow is injected to the so-called origin
nodes. The total inflow arriving at each node is routed to
its operational outgoing links based on their current particle
densities. The density on each link has first order dynamics
driven by the difference of its incoming and outgoing flows.
A link irreversibly fails if it reaches its jam density. Such

failures may propagate in the network since the outflow of
a link drops to zero when there are no operational links in
its immediate downstream. A systemic failure is observed
if the long-term average inflow to the destination nodes
(throughput) is less than the total external inflow.
Although links with larger capacities can sustain larger
flows, the link capacities do not have a monotonic influence
on the throughput of locally routed network flows [12]. A
link with a larger capacity may attract a larger demand under
local routing, and the resulting flow may cause a systemic
failure by overloading some critical links in its downstream.
Such failures can be avoided if the dynamics yield a sufficient
back-propagation of congestion effects through the densities [10]. Otherwise, additional control and communication
mechanisms are needed to mitigate the fragility arising from
local decisions. One approach in this direction is to make
the global network state accessible via communications. For
instance, GPS-based route guidance systems are used in road
traffic networks to provide the drivers with real-time traffic
data. However, in distributed systems, the availability of
more information does not guarantee the desired global performance in the absence of a properly coordinated response
(e.g., [13], [14], [15]). Alternatively, some system objectives
can be achieved via a controlled operation of the network,
without requiring any global information and coordination in
the user decisions (e.g., [12], [16], [17]).
In this paper, we investigate the provably correct use of
variable speed limits as a flow control mechanism for avoiding systemic failures due to local routing decisions. Our work
is closely related to [2], [3], [10] with the following main
differences: We consider flows that are non-monotonic in
densities due to congestion collapse, and we incorporate the
speed limits as external control inputs in the flow functions.
We show that systemic failures due to local routing decisions
can always be averted through a proper selection of speed
limits if the routing decisions are sufficiently responsive to
local congestion and the initial densities on the links are
sufficiently small. Accordingly, throughput optimality can
be ensured without requiring any global information and
coordination in the routing decisions, even when there is
not a sufficient back-propagation of congestion effects. A
tractable method of designing such speed limits under some
limited knowledge of the routing behavior is also provided
in the paper.

The organization of this paper is as follows: Section II provides some preliminaries. Section III presents the dynamical
model of locally routed network flows. Section IV presents
some motivation and examples. Section V presents our main
results. Finally, Section VI concludes the paper.
II. P RELIMINARIES
A. Notation
For any finite set A with cardinality |A|, we use RA
A
(RA
+ , R++ ) to denote the space of real-valued (nonnegativereal-valued, positive-real-valued) |A| − dimensional vectors
whose components are indexed by the elements of A. Accordingly, for any a ∈ A and x ∈ RA , xa ∈ R denotes the
corresponding entry of x. Similarly, for any A0 ⊆ A, we use
0
xA0 ∈ RA to denote the |A0 |-dimensional vector consisting
only of the components of x whose indices are in A0 . For
any pair of vectors x, x̄ ∈ RA , we use [x, x̄) to denote the set
¯
¯
of vectors x ∈ RA such that x ≤ x < x̄, i.e., xa ≤ xa < x̄a
¯
¯
for all a ∈ A. The all-zero vector, its size being clear from
the context, will be denoted by 0.
B. Graph basics
A directed graph, G = (V, E), consists of a set of nodes,
V, and a set of edges, E ⊆ V × V, given by ordered pairs of
nodes. A graph is a multi-graph if multiple edges are allowed
between the nodes, i.e., if E is a multi-set. Each (v, w) ∈ E
denotes a link from v (the tail) to w (the head). A path is
a sequence of nodes such that (v, w) ∈ E for any pair of
nodes v, w ∈ V that are consecutive in the sequence. For
each v ∈ V, we use Ev− and Ev+ to denote the corresponding
sets of incoming and outgoing links, respectively. Similarly,
for any U ⊆ V,

In this setting, the particles are assumed to move at the
maximum admissible speed, i.e.,
se = min(s̄e (ρe ), ue ),

(2)

where s̄e (ρe ) denotes the maximum speed at which the
particles can travel along e when the density is ρe , and
ue ∈ [0, ūe ] is the speed limit imposed on the link. In transportation networks, s̄e (ρe ) is a monotonically decreasing
function since a higher density corresponds to a shorter
following distance, for which the maximum safe speed is
lower. Furthermore, each ūe ∈ R++ is typically set based on
some safety, efficiency, and environmental considerations.
In light of (1) and (2), the flow on each link is a function
of its density and speed limit, i.e.,
fe : [0, ρ̄e ] × [0, ūe ] 7→ [0, f¯e ],
where f¯e ∈ R++ denotes the finite capacity of the link, that
is, the maximum flow that can be sustained by the link, and
ρ̄e ∈ R++ is the finite jam density, for which s̄e (ρ̄e ) = 0.
Accordingly,
fe (0, ue ) = fe (ρ̄e , ue ) = 0,

∀ue ∈ [0, ūe ].

(3)

Note that the flow becomes a function of only the density
when the speed limit is constant. For instance, fe (ρe , ūe )
represents how the flow depends on the density when the
link is operated constantly with the maximum speed limit.
Assumption 1 Each fe (ρe , ūe ) is continuous in ρe , and
there exists a congestion threshold ρce ∈ (0, ρ̄e ) such that
fe (ρe , ūe ) is strictly increasing on the interval (0, ρce ) and
strictly decreasing on the interval (ρce , ρ̄e ).

In this section, we provide some definitions and the
dynamical model of locally routed flows.

The structure in Assumption 1 is typical for the flow
functions in transportation networks (e.g., [18]). Accordingly,
the capacity of link e is f¯e = fe (ρce , ūe ), and the link is said
to be congested when ρe > ρce .
We focus on networks where the total inflow to each node
is routed locally to its operational outgoing links based on
their current densities. Such routing behavior subject to the
conservation of flow is modeled via local routing policies.

Definition (Flow Network): A flow network is a directed
multi-graph G = (V, E) such that there exists a path from
any node to some destination node v ∈ VD , where

Definition (Local Routing Policy): For any flow network
G = (V, E) with the finite jam densities ρ̄ ∈ RE++ , a local
routing policy R is a family of functions

EU− = {(v, w) ∈ E | v ∈
/ U, w ∈ U},
EU+ = {(v, w) ∈ E | v ∈ U, w ∈
/ U}.
III. S YSTEM M ODEL

VD = {v ∈ V | Ev+ = ∅}.

Furthermore, the set of origin nodes VO is defined as
VO = {v ∈ V |

Ev−

= ∅}.

The nodes that are neither an origin nor a destination
constitute the set of intermediate nodes VI = V \ VO \ VD .

In flow networks, each link e ∈ E has a flow fe ∈ R+ that
is related to the average number of particles per unit length
(density) ρe ∈ R+ and their average speed se ∈ R+ as
fe = ρe se .

E+

Rv : [0, ρ̄Ev+ ] × R+ 7→ R+v , v ∈ V \ VD ,

(1)

such that, for any inflow µv ∈ R+ ,
X
Rve (ρEv+ , µv ) = µv , ∀ρEv+ 6= ρ̄Ev+ ,

(4)

Rve (ρEv+ , µv ) = 0, ∀e ∈ Ev+ : ρe = ρ̄e ,

(5)

e∈Ev+

where Rve (ρEv+ , µv ) is the flow routed to the link e ∈ Ev+ .

Definition (Locally Routed Flow): For any flow network
G = (V, E), flow functions f , local routing policy R, and
O
external inflow λ ∈ RV
+ , the locally routed flow (G, f, R, λ)

is a dynamical system such that, for every e = (v, w) ∈ E,
 v
Re (ρEv+ , µv ) − fe (ρe , ue ), if ρEw+ 6= ρ̄Ew+ ,
,
ρ̇e =
Rve (ρEv+ , µv ),
o.w.
(6)
where µv denotes the total inflow to v, i.e.,

 λv ,
if v ∈ VO ,
P
µv =
,
(7)
fj (ρj , uj ), o.w.

−
j∈Ev

and ue ∈ [0, ūe ] is the speed limit imposed on e.
In light of (3) and (5), each ρ̄e is an equilibrium point
under (6). As such, a link irreversibly stops carrying flow
(fails) if it reaches its jam density. Furthermore, since (6)
implies ρ̇e ≥ 0 for any e = (v, w) ∈ E such that
ρEw+ = ρ̄Ew+ , link failures can propagate in the network. While
some failures may not have a severe impact on the overall
performance, others can cause a cascading failure of some
critical links and lead to a non-transferring system.
Definition (Transferring System): A locally routed flow is
transferring if the long-term average inflow to the destination
nodes (throughput) is equal to the total external inflow, i.e.,
Z
X
1 t X
lim inf
µv (τ )dτ =
λv .
t→∞ t 0
v∈VD

v∈VO

In transferring systems, the amount of particles that are
unable to reach a destination node remains bounded as time
goes to infinity. In contrast, non-transferring systems experience a systemic failure, i.e., at least one origin node, which
has a non-zero external inflow, becomes disconnected from
the network due to link failures (see Lemma 5.1). As such,
eventually it becomes impossible to send the corresponding
portion of the external inflow through the network.
IV. M OTIVATION
Consider any locally routed network flow (G, f, R, λ),
where all the links are operated constantly under their
respective maximum admissible speed limits, i.e., u(t) = ū,
so that they all can sustain flows up to their respective
capacities. If such a system is non-transferring despite the
initial densities being sufficiently small (e.g., ρ(0) = 0), this
failure is due to one of the two possible reasons:
• The external inflow λ is too large (infeasible) and cannot
be transferred under any routing policy.
• The external inflow λ is feasible, yet the routing decisions lead to failure.
In this regard, an external inflow is feasible if the corresponding set of feasible equilibrium flows, i.e.,
¯ λ) = {f ∈ RE | fe ≤ f¯e , ∀e ∈ E
F(f,
+
X
λv =
fe , ∀v ∈ VO
X

e∈Ev−

e∈Ev+

fe =

X

e∈Ev+

fe , ∀v ∈ VI }

(8)

is nonempty. The feasibility of an external inflow can be
checked based on the max-flow min-cut theorem [19], which
¯ λ) 6= ∅ if and only if
implies that F(f,
X
X
f¯e −
λv ≥ 0, ∀U ⊆ V \ VD .
(9)
+
e∈EU

v∈U

Accordingly, for any infeasible external inflow, there exists
some U ⊆ V \ VD , which receives a total external inflow
larger than the total maximum flow sustainable by its outgoing links. In that case, the total density on the links within U
keeps increasing until all the outgoing links of some origin
node in U fail. Hence, infeasible external inflows lead to a
non-transferring system, regardless of the routing behavior.
In light of (9), systemic failures due to infeasible external
inflows cannot be avoided without reducing the external
inflow or building more capacity in the network. However,
this is not the case for failures due to routing decisions.
In fact, we will show that such failures can be avoided by
using the speed limits to intentionally operate some of the
links below their capacity, provided that the routing policy
is sufficiently congestion aware.
Definition (Congestion Awareness): For any flow network
G = (V, E) and flow functions f , a local routing policy R is
congestion aware at a density profile ρ∗ ∈ [0, ρ̄] if, for every
e = (v, w) ∈ E,
X
φj (ρj ),
ρe ≥ ρ∗e ⇒ Rve (ρEv+ , µv ) ≤ φe (ρe ), ∀µv ≤
j∈Ev+

(10)
where φe (ρe ) denotes the maximum sustainable inflow, i.e.,

f¯e ,
if ρe ≤ ρce ,
φe (ρe ) =
(11)
fe (ρe , ūe ), o.w.

Note that, for any ρe ∈ [0, ρ̄e ), φe (ρe ) is the maximum
constant inflow that would not drive the link to failure when
its current density is ρe . As such, (10) indicates some local
failure-avoidance behavior. In particular, when the density
of a link e = (v, w) exceeds the corresponding ρ∗e , the flow
routed to e does not exceed its maximum sustainable inflow
as long as v is receiving a sufficiently small µv .
A. Motivating Example
Consider the flow network in Fig. 1a. Let all the links
have similar characteristics except for their cross-sectional
dimensions. Accordingly, let f0 (ρ0 , u0 ) denote a normalized
flow function such that

ρ
e
, ue , ∀e ∈ E,
fe (ρe , ue ) = ce f0
ce
where ce ∈ R++ is determined by the cross-sectional
dimension of the link e. For instance, each ce may correspond
to the number of lanes in e, whereas f0 denotes the flow
function for a single lane. Let all the links be constantly
operated under the maximum speed limit ū0 ∈ R++ , and
let f0 (ρ0 , ū0 ) be as illustrated in Fig. 1b. Accordingly, the
capacity of each link is f¯e = ce f¯0 and provided next to itself
in Fig. 1a. Suppose that initially there are no particles in the

network, i.e., ρ(0) = 0, and an external inflow of λ = 6f¯0 is
injected. Note that this is a feasible external inflow for this
network since the minimum value for the left side of (9) is
f¯0 , which is obtained for U = {1, 2}.

λ = 6f¯0

3
f¯0

1
4f¯0

2

λ = 6f¯0

4
2f¯0

4f¯0

(a)

4

λ = 6f¯0

f¯0

2

ρ̄0

λ = 6f¯0

f¯0
4f¯0

Fig. 1. A flow network along with the external inflow and link capacities
are illustrated in (a), and the normalized flow function is shown in (b).

Since the external inflow is feasible and ρ(0) = 0, whether
the system is transferring depends on the routing policy.
Consider a local routing policy R such that the flow routed to
each edge is proportional to its maximum sustainable inflow,
that is, for every e = (v, w) ∈ E,
(12)

j∈Ev+

In light of (10), this routing policy is congestion aware
at any ρ∗ ∈ [0, ρ̄]. Furthermore, it can be shown that when
ρ(0) ∈ [0, ρc ] and the maximum speed limits are constantly
applied as u(t) = ū, the tail of the first link that exceeds its
congestion threshold under this policy must have received
an inflow larger than the total capacity of its outgoing links.
For the network in Fig. 1a, it can be easily verified that
node 1 (since λ is less than its total outgoing capacity) and
node 3 (since its total incoming capacity is less than its total
outgoing capacity) never receive such excessive inflows. That
is also true for node 2 since R1 routes λ evenly to the links
in E1+ as long as they are both uncongested. Accordingly, µ2
monotonically increases to 3f¯0 , which is equal to the total
capacity of the links in E2+ . Hence, none of the links exceed
their congestion thresholds in this example, and the resulting
system (G, f, R, λ) is transferring.
As a second example, consider the same network when
c(2,4) is reduced by one due to some disturbance. For
instance, such a reduction can be due to one of the lanes
in the link (2, 4) being closed due to maintenance or an
accident. Note that the external inflow of λ = 6f¯0 is still
feasible under the resulting link capacities as shown in Fig.
2a. Same as the previous case, consider the routing policy
R that satisfies (12) for the flow functions in this example,
and let the system have ρ(0) = 0 and u(t) = ū. Under
the resulting dynamics, the densities of the links in E1+
initially follow the same trajectory as before. However, once
µ2 exceeds 2f¯0 (the total capacity of the links in E2+ ), the
links in E2+ will be driven to their jam densities. Note that
λ is not feasible for the remaining network once those two
links fail, and the failures in Fig. 2d are inevitable. As such,
(G, f, R, λ) is non-transferring for this example.

4f¯0

6f¯0

2

6f¯0

4
f¯0

2

(b)

f¯0

1
4f¯0

(b)

3

3

1

(a)
4f¯0

φe (ρe )
, ∀ρEv+ 6= ρ̄Ev+ .
Rve (ρEv+ , µv ) = µv P
φj (ρj )

4f¯0

6f¯0
f¯0

f0 (ρ0 , ū0 )

Density (ρ0 )

3

1

f¯0

6f¯0

Flow (f0 )

4f¯0

4f¯0

4

λ = 6f¯0

f¯0

6f¯0
f¯0

1
4f¯0

(c)

3

2

4
f¯0

(d)

Fig. 2. A reduction in the capacity of the link (2, 4) as shown in (a) leads
to a cascade of failures as illustrated in (b)-(c)-(d).

To avoid the failures in the second example, a larger
portion of λ should be routed to the link (1, 3) before the
links in E2+ are overloaded. However, local routing policies
only respond to the densities on the immediate links. Hence,
even the routing policies such as (12), which are congestion
aware at every density profile in [0, ρ̄], may fall short in
circumventing systemic failures when the links can sustain
flows that may overload some critical links further in their
downstream. In this regard, the large capacity of the link
(1, 2) was actually a liability in the second example. As
we will show later in the paper, the systemic failure in this
example could actually be avoided by reducing the capacity
of the link (1, 2) so that its outflow never exceeds 2f¯0 .
B. Capacity Allocation via Speed Limits
As illustrated in the previous section, having large link
capacities may also lead to systemic failures when the routing
decisions are local. In this section, we present how speed
limits can be used to address this issue by intentionally
operating certain links below their capacities when necessary.
Given a flow function fe (ρe , ūe ) and some f¯e∗ ∈ [0, f¯e ],
suppose that we would like to design the speed limit ue
such that the flow on the link never exceeds f¯e∗ . In order to
avoid unnecessary delays, it would also be desired to keep
ue as large as possible. The solution to this problem depends
on the available flexibility in the design. For instance, if a
constant speed limit is required, then (1) and (2) together
with Assumption 1 imply that the solution is
ue =

f¯e∗
,
ρ̂e

(13)

where
ρ̂e = max{ρe ∈ [0, ρ̄e ] | fe (ρe , ūe ) = f¯e∗ }.

(14)

Such a constant speed limit may be too conservative when
the density on the link is low. Alternatively, a feedback law
can induce the desired capacity more efficiently. For instance,

the following policy achieves this task while allowing for the
maximum possible speed at all times:
(
ūe , if fe (ρe , ūe ) ≤ f¯e∗ ,
(15)
ue (ρe ) =
f¯e∗
o.w.
ρe ,
Fig. 3 illustrates how the speed limits in (13) and (15)
influence the flow on a link for a typical flow function.
Accordingly, if f¯e∗ is chosen properly, such an operation of
the link ensures that the link accumulates a higher density
itself rather than overloading some critical links further in
its downstream. This way, potential failures due to the lack
of global information can be avoided if the local routing
decisions properly respond to the increasing density on the
link. In the next section, we provide our formal results
regarding such use of speed limits to avert systemic failures
in locally routed flows.

Proof: Since every local routing policy R satisfies (4)
and (5), under the dynamics in (6) and (7),
X
X
X
µv .
(17)
λv −
ρ̇e =
e∈E

v∈VO :ρE + 6=ρ̄E +
v

ρce

Flow (fe )

Flow (fe )

fe (ρe , ūe )

fe (ρe , ue )

e

ρ̄e

ρce

and there is no v ∈ VO satisfying (16). In that case, (17) and
(18) together imply
Z
1 tX
lim inf
ρ̇e (τ )dτ > 0,
t→∞ t 0
e∈E

which leads to

(a)

(b)

Flow (fe )

Density (ρe )

f¯e
f¯e∗

fe (ρe , ue )

(c)
Fig. 3. Capacity allocation via the speed limit policies in (13) and (15) are
illustrated in (b) and (c), respectively. The solid curves show the resulting
flow functions, the dashed curves illustrate the deviation from fe (ρe , ūe ).

V. M AIN R ESULTS
Our main result (Theorem 5.2) shows that, for any locally
routed flow, if the routing policy is congestion aware at a
density profile ρ∗ ∈ [0, ρ̄] that is compatible with the external
inflow, then there exist speed limits u(t) ∈ [0, ū] that ensure
a transferring system for any initial condition ρ(0) ∈ [0, ρ∗ ].
We start our derivations with Lemma 5.1, which will be used
in proving Theorem 5.2.
Lemma 5.1 If a locally routed flow (G, f, R, λ) is nontransferring, then there exists an origin node v ∈ VO such
that its external inflow is non-zero and all its outgoing links
eventually reach their jam densities, i.e.,
lim ρ + (t)
t→∞ Ev

= ρ̄Ev+ .

v∈U

then there exist speed limits u(t) ∈ [0, ū] such
that (G, f, R, λ) is transferring for any initial condition
ρ(0) ∈ [0, ρ∗ ].

ρ̄e

Density (ρe )

λv > 0,

(19)

ρe (t) = +∞.

e∈E

Theorem 5.2 For any locally routed flow (G, f, R, λ), if
R is congestion aware at some ρ∗ ∈ [0, ρ̄] such that the
corresponding maximum sustainable inflows in (11) satisfy
X
X
φe (ρ∗e ) −
λv ≥ 0, ∀U ⊆ V \ VD ,
(20)
+
e∈EU

ρce

X

Note that (19) contradicts with every ρ̄e being finite. Consequently, if (G, f, R, λ) is non-transferring, then there exists
v ∈ VO satisfying (16).
ρ̄e

Density (ρe )

v∈VO

v∈VD

t→∞

f¯e
f¯∗

v∈VD

For the sake of contradiction, suppose that (G, f, R, λ) is
non-transferring, i.e.,
Z
X
1 t X
λv ,
(18)
µv (τ )dτ <
lim inf
t→∞ t 0

lim inf
f¯e

v

(16)

Proof: Let (G, f, R, λ) be any locally routed flow such
that R is congestion aware at some ρ∗ ∈ [0, ρ̄] satisfying
(20). Let F̄ ∗ (φ(ρ∗ ), λ) be the set of feasible capacity allocations that are upper bounded by φ(ρ∗ ) and ensures that the
total outgoing capacity is greater than the external inflow for
each origin node and greater than the total incoming capacity
for each intermediate node, i.e.,
F̄ ∗ (φ(ρ∗ ), λ) = {f¯∗ ∈ RE+ | f¯e∗ ≤ φe (ρ∗e ), ∀e ∈ E
X
λv ≤
f¯e∗ , ∀v ∈ VO
X

e∈Ev−

e∈Ev+

f¯e∗ ≤

X

e∈Ev+

f¯e∗ , ∀v ∈ VI }.(21)

Based on (8), F(φ(ρ∗ ), λ) ⊆ F̄ ∗ (φ(ρ∗ ), λ). Furthermore,
due to (20), F(φ(ρ∗ ), λ) 6= ∅. Hence, F̄ ∗ (φ(ρ∗ ), λ) 6= ∅. Let
the speed limits u(t) ∈ [0, ū] be assigned in accordance with
(13) or (15) for any f¯∗ ∈ F̄ ∗ (φ(ρ∗ ), λ). Such speed limits
ensure that the flow on each link e is upper bounded by f¯e∗ .
Accordingly, (7) and (21) together imply
X
µv (t) ≤
f¯e∗ , ∀v ∈ V, ∀t ≥ 0.
(22)
e∈Ev+

Let ρ̂ denote the vector of densities such that each ρ̂e satisfies
(14). Due to Assumption 1, ρ̂ ∈ [ρ∗ , ρ̄] and
φe (ρe ) ≥ φe (ρ̂e ) = f¯e∗ , ∀ρe ∈ [0, ρ̂e ], ∀e ∈ E.

(23)

As such, (10), (22) and (23) together imply that, under (6),
ρe = ρ̂e ⇒ ρ̇e ≤ 0, ∀ρ ∈ [0, ρ̂], ∀e ∈ E.
Hence, [0, ρ̂] is positively invariant. Also, due to (21),
X
f¯e∗ > 0, ∀v ∈ VO : λv > 0,

∗
f¯(1,2)
= 2f¯0 , f¯e∗ = f¯e , ∀e ∈ E \ {(1, 2)},

e∈Ev+

which implies

ρ̂Ev+ 6= ρ̄Ev+ , ∀v ∈ VO : λv > 0.

(24)

Since [0, ρ̂] is positively invariant, Lemma 5.1 and (24)
together imply that (G, f, R, λ) is transferring for any
ρ(0) ∈ [0, ρ̂]. Since ρ̂ ≥ ρ∗ , we conclude that (G, f, R, λ)
is transferring for any ρ(0) ∈ [0, ρ∗ ].
Theorem 5.2 implies that the systemic failures under any
feasible external inflow can be averted through a proper
selection of speed limits if the local routing policy is sufficiently congestion aware and the initial densities on the
links are sufficiently small. For instance, since φ(ρc ) = f¯
and any feasible external inflow satisfies (9), the theorem
implies that for any (G, f, R, λ) such that λ is feasible and
R is congestion aware at the congestion threshold ρc , there
exist speed limits u(t) ∈ [0, ū] such that (G, f, R, λ) is transferring for any ρ(0) ∈ [0, ρc ]. Accordingly, a proper choice
of speed limits ensures optimal throughput by compensating
for the lack of global information in routing decisions. We
will conclude this section by providing a tractable method
of generating such speed limits.
A. Minimal Capacity Reduction with Maximal Speed Limits
As shown in the constructive proof of Theorem 5.2, one
way to use the speed limits for ensuring a transferring
system is by inducing some capacities f¯∗ ∈ F̄ ∗ (φ(ρ∗ ), λ).
Since each fe (ρe , ue ) is monotonically increasing in ue ,
inducing smaller capacities requires imposing lower speed
limits. Hence, to employ this approach without introducing
unnecessary delays on the individual links, it would be
desired to realize some maximal f¯∗ . For instance, such a
capacity allocation problem can be formulated as
f¯∗ =

argmax

αT f¯0 ,

f¯0 ∈F̄ ∗ (φ(ρ∗ ),λ)

As an application of this method, let us revisit the second
scenario in Section IV-A. Given the external inflow and link
capacities in Fig. 4a, suppose that we would like to assign
the speed limits to ensure a transferring system for any local
routing policy that is congestion aware at ρc and any initial
condition ρ(0) ∈ [0, ρc ]. For this example, (25) has a unique
solution for ρ∗ = ρc and any α ∈ RE++ , i.e.,

(25)

where each αe ∈ R++ denotes the relative importance of
having a larger capacity on e. Note that (25) is a linear program since F̄ ∗ (φ(ρ∗ ), λ) is defined by the linear inequalities
in (21). Since F̄ ∗ (φ(ρ∗ ), λ) is non-empty (see the proof of
Theorem 5.2) and bounded (F̄ ∗ (φ(ρ∗ ), λ) ⊆ [0, φ(ρ∗ )]), a
solution to (25) is guaranteed to exist. Once the capacity
allocation problem is solved, a speed limit policy such as (15)
can be used to realize f¯∗ without unnecessary slowdowns.

which can be realized by using the maximal speed limits in
(15) to achieve the desired performance guarantee. As such,
the resulting speed limits would prevent the systemic failure
illustrated in Fig. 2.
4f¯0
λ = 6f¯0

3
f¯0

1
4f¯0

4f¯0

6f¯0

4

λ = 6f¯0

f¯0

2

(a)

3

6f¯0
f¯0

1
2f¯0

2

4
f¯0

(b)

Fig. 4.
For the network in (a), the solution to the minimal capacity
reduction problem in (25) for ρ∗ = ρc and any α ∈ RE
++ is illustrated in
(b). Accordingly, the systemic failure illustrated in Fig. 2 can be prevented
by using variable speed limits to induce a lower capacity on the link (1, 2).

VI. C ONCLUSIONS
In this paper, we investigated the use of variable speed limits for avoiding systemic failures in transportation networks,
which were modeled as dynamical flow networks under local
routing decisions. We showed that operating the links constantly at their full capacities may lead to systemic failures in
such systems due to the lack of global information in routing
decisions. In particular, the capacity of a link becomes a
liability when it sustains a large flow that will overload some
critical links further in its downstream. Accordingly, variable
speed limits can be employed to operate the links below their
full capacities when necessary to compensate for the lack
of global information. Our main result shows that systemic
failures under feasible external inflows can always be averted
through a proper selection of speed limits if the routing
decisions are sufficiently responsive to local congestion and
the initial densities on the links are sufficiently small. A
tractable method for designing such speed limit policies was
also provided in the paper.
The results of this paper pave the way for the design of
provably correct speed limit policies which not only ensure
a transferring system but also optimize some additional
performance measures such as the average time the particles
spend in the network (average delay). As a future direction,
we plan to investigate the design of such policies under
limited knowledge of the routing behavior. Furthermore, we
plan to investigate how the availability of more information
(e.g., multi-hop densities) in the routing policies would affect
the overall performance under such network operation.

R EFERENCES
[1] T. Roughgarden and É. Tardos, “How bad is selfish routing?,” Journal
of the ACM (JACM), vol. 49, no. 2, pp. 236–259, 2002.
[2] G. Como, K. Savla, D. Acemoglu, M. A. Dahleh, and E. Frazzoli,
“Robust distributed routing in dynamical networks–part I: Locally
responsive policies and weak resilience,” IEEE Transactions on Automatic Control, vol. 58, no. 2, pp. 317–332, 2013.
[3] G. Como, K. Savla, D. Acemoglu, M. A. Dahleh, and E. Frazzoli,
“Robust distributed routing in dynamical networks–part II: Strong
resilience, equilibrium selection and cascaded failures,” IEEE Transactions on Automatic Control, vol. 58, no. 2, pp. 333–348, 2013.
[4] J. Adler, “Bootstrap percolation,” Physica A: Statistical Mechanics
and its Applications, vol. 171, no. 3, pp. 453–470, 1991.
[5] I. Dobson, B. A. Carreras, and D. E. Newman, “A loading-dependent
model of probabilistic cascading failure,” Probability in the Engineering and Informational Sciences, vol. 19, no. 01, pp. 15–32, 2005.
[6] L. Blume, D. Easley, J. Kleinberg, R. Kleinberg, and É. Tardos,
“Which networks are least susceptible to cascading failures?,” in IEEE
Annual Symposium on Foundations of Computer Science, pp. 393–402,
2011.
[7] D. Acemoglu, V. M. Carvalho, A. Ozdaglar, and A. TahbazSalehi, “The network origins of aggregate fluctuations,” Econometrica,
vol. 80, no. 5, pp. 1977–2016, 2012.
[8] J. Ash and D. Newth, “Optimizing complex networks for resilience
against cascading failure,” Physica A: Statistical Mechanics and its
Applications, vol. 380, pp. 673–683, 2007.
[9] A. Y. Yazıcıoğlu, M. Egerstedt, and J. S. Shamma, “Formation of
robust multi-agent networks through self-organizing random regular
graphs,” IEEE Transactions on Network Science and Engineering,
vol. 2, no. 4, pp. 139–151, 2015.
[10] G. Como, E. Lovisari, and K. Savla, “Throughput optimality and overload behavior of dynamical flow networks under monotone distributed
routing,” IEEE Transactions on Control of Network Systems, vol. 2,
no. 1, pp. 57–67, 2015.
[11] A. E. Motter, “Cascade control and defense in complex networks,”
Physical Review Letters, vol. 93, no. 9, p. 098701, 2004.
[12] A. Y. Yazıcıoğlu, M. Roozbehani, and M. A. Dahleh, “Resilience of
locally routed network flows: More capacity is not always better,”
arXiv preprint arXiv:1608.04155, 2016.
[13] R. Arnott, A. De Palma, and R. Lindsey, “Does providing information
to drivers reduce traffic congestion?,” Transportation Research Part A:
General, vol. 25, no. 5, pp. 309–318, 1991.
[14] D. Acemoglu, A. Makhdoumi, A. Malekian, and A. Ozdaglar, “Informational Braess’ paradox: The effect of information on traffic
congestion,” arXiv preprint arXiv:1601.02039, 2016.
[15] M. Roozbehani, M. A. Dahleh, and S. K. Mitter, “Volatility of power
grids under real-time pricing,” IEEE Transactions on Power Systems,
vol. 27, no. 4, pp. 1926–1940, 2012.
[16] S. Coogan, E. A. Gol, M. Arcak, and C. Belta, “Controlling a network
of signalized intersections from temporal logical specifications,” in
American Control Conference (ACC), pp. 3919–3924, 2015.
[17] R. C. Carlson, I. Papamichail, M. Papageorgiou, and A. Messmer,
“Optimal motorway traffic flow control involving variable speed limits
and ramp metering,” Transportation Science, vol. 44, no. 2, pp. 238–
253, 2010.
[18] E. Cascetta, Transportation systems engineering: theory and methods,
vol. 49. Springer, 2001.
[19] P. Elias, A. Feinstein, and C. Shannon, “A note on the maximum flow
through a network,” IRE Transactions on Information Theory, vol. 2,
no. 4, pp. 117–119, 1956.

