1

Minimizing the Maximum End-to-End Network
Delay: Hardness, Algorithm, and Performance

arXiv:1707.02650v3 [] 16 Feb 2018

Qingyu Liu, Lei Deng, Haibo Zeng, Minghua Chen

Abstract—We consider the scenario where a source streams a
flow at a fixed rate to a receiver across the network, possibly
using multiple paths. Each link has a finite capacity constraint.
Transmission over a link incurs an integer delay if the rate is
within the link capacity, and an unbounded delay otherwise.
The objective is to minimize the maximum end-to-end delay
experienced by the flow. The problem, denoted as Min-MaxDelay, appears in various practical scenarios, e.g., delay-critical
video conferencing using inter-datacenter networks. In this paper,
we first show that Min-Max-Delay is NP-hard in the weak sense
and develop an exact algorithm with pseudo-polynomial time
complexity. We then propose a Fully Polynomial Time Approximation Scheme (FPTAS) that obtains a (1 + )-approximate
solution in polynomial time. These results reveal fundamental
difference between the Min-Max-Delay problem and a similar
maximum latency problem studied in the literature, for which is
APX-hard and no PTAS1 exists unless P = NP. Moreover, there
exists no exact pseudo-polynomial-time algorithm or constantapproximate algorithm for the maximum latency problem. We
demonstrate the effectiveness of our algorithms in the scenario of routing delay-critical video-conferencing traffic over
multiple paths of inter-datacenter networks, using simulations
based on Amazon EC2 inter-datacenter topology. Both of our
algorithms achieve the optimal maximum delay performance
in all simulation instances, consistently outperforming all stateof-the-art solutions which only obtain sub-optimal maximum
delay performance in certain instances. Furthermore, simulation
results show that our achieved optimal delay performance always
meet the end-to-end delay requirement for video conferencing
applications, while the sub-optimal delay performance obtained
by the alternatives fail to satisfy the video-conferencing delay
requirement for up to 15% of simulation instances between
certain cross-continental source-receiver pair.
Index Terms—Delay-aware network flow, maximum delay optimization, video traffic, inter-datacenter networks, exact pseudopolynomial time algorithm, approximate algorithm.

I. I NTRODUCTION
A. Motivation
We consider the scenario where a source streams a flow at
a fixed rate to a receiver across a multi-hop network, possibly
Manuscript received ...
Part of this work has been presented at the IEEE Information Theory
Workshop (ITW), Kaohsiung, Taiwan, November 6 - 10, 2017 [1].
Q. Liu, and H. Zeng are with the Department of Electrical and Computer Engineering, Virginia Tech, Blacksburg, USA (e-mail: qyliu14@vt.edu,
haibo.zeng@gmail.com).
L. Deng is with the School of Electrical Engineering & Intelligentization,
Dongguan University of Technology, China (e-mail: denglei@dgut.edu.cn).
M. Chen is with the Department of Information Engineering,
The Chinese University of Hong Kong, Hong Kong, China (e-mail:
minghua@ie.cuhk.edu.hk).
1 Unless P = NP, it holds that FPTAS ( PTAS in that the runtime of a
PTAS is required to be polynomial in problem input but not 1/, while the
runtime of an FPTAS is polynomial in both the problem input and 1/ [2].

using multiple paths, to minimize the maximum end-to-end
delay. We denote the problem as Min-Max-Delay. Transmission over a link is assumed to experience an integer delay
if the rate is within the finite link capacity, and unbounded
delay otherwise. This models many practical applications,
particularly the routing of delay-critical video conferencing
traffic over inter-datacenter networks. We note that using
multiple paths for delay minimization is necessary when the
shortest path is insufficient to support the fix-rate flow due to
the bandwidth limitation.
According to recent reports from Microsoft [3] and
Google [4], most real-world inter-datacenter networks are
characterized by sharing link bandwidth for different applications with over-provisioned link capacities. (i) Real-world
inter-datacenter networks nowadays are utilized to simultaneously support traffic from various services, some of which have
stringent delay requirements (e.g., video conferencing) while
others are bandwidth-hungry and less sensitive to delay (e.g.,
data backup and data maintenance). Link capacity is often
reserved separately for different types of services depending on their characteristics, e.g., bandwidth-hungry (delayinsensitive) services are reserved with a larger capacity. (ii)
Cloud providers typically over-provision their inter-datacenter
link capacity by 2 − 3 times on a dedicated backbone to
guarantee reliability, and the average link-capacity utilizations
(the aggregate utilization of applications, not the bandwidthutilization of individual applications) for busy links are 30 −
60% [5]. As such, in most real-world inter-datacenter networks
queuing delays are negligible and the constant propagation
delays dominate the end-to-end delay, as evaluated by [5] in a
realistic network of Amazon EC22 . These observations justify
our link capacity and delay model, especially for the problem
of routing delay-critical video-conferencing traffic over interdatacenter networks.
Our optimization objective of minimizing the end-to-end
maximum delay is motivated by increasing interests on supporting delay-critical traffic to serve various communication
applications, e.g., the video conferencing services [5], [6].
It is reported that 51 million users per month attend WebEx meetings [7], 3 billion minutes of calls per day use
Skype [8], and 75% of high-growth innovators use video
collaboration [9]. Low cross-network delay is vital for the
video conferencing applications. As recommended by the
2 Note again that there may not be over-provisioning for individual applications/services of their respective reserved link capacities. Since their traffic
peaks may not appear at the same time, the overall effect is that within the
allocated (reserved) bandwidth, traffics of individual applications experience
constant propagation delays; otherwise, they experience unbounded delay.

2

International Telecommunication Union (ITU) [10], for video
conferencing, it is desirable to keep the cross-network oneway delay as low as possible. A delay less than 150ms can
provide a transparent interactivity while delays above 400ms
are unacceptable.
In the delay-sensitive communication field, it is well-known
that flow problems with objectives/constraints related to both
throughput and maximum delay are highly non-trivial. In
fact, it still remains open to characterize the hardness of the
problem Min-Max-Delay and design efficient algorithms with
performance guarantee, in spite of the practical relevance of
Min-Max-Delay for delay-sensitive communications.
The problem Min-Max-Delay models the link delay as a
constant if the link rate is below the capacity and unbounded
otherwise. It is an important special case of the maximum
latency problem in the literature [11]–[13] which assumes the
link delay as a general function of the link traffic rate. It
is known that the maximum latency problem is NP-hard, in
particular APX-hard [12]. This implies that unless P = NP, no
PTAS exists, and there is even no polynomial time algorithm
that can obtain a constant approximation ratio.
In contrast, we show that the problem Min-Max-Delay
is NP-hard in the weak sense, and we design a pseudopolynomial time exact algorithm as well as an FPTAS. Hence,
while Min-Max-Delay is a special case of the maximum
latency problem, they are fundamentally different in terms of
hardness and admitting good exact/approximation algorithms.
We summarize the differences in Tab. I.
B. Contributions
In this paper we focus on the Min-Max-Delay problem and
make following contributions:
B We prove Min-Max-Delay is NP-hard (Thm. 1, Sec. III),
but is in the weak sense (Thm. 3, Sec. IV). Specifically,
we first prove it is NP-hard, and then develop a pseudopolynomial time algorithm (Algorithm 1, Sec. IV) to solve
Min-Max-Delay optimally. The algorithm has a time complexity of O((N 2 dmax )3.5 log(N 2 dmax ) log R), where N ,
max{|V |, |E|}, R is the flow rate (or throughput equivalently)
requirement, and dmax is the maximum link delay. The time
complexity is pseudo-polynomial because it is polynomial in
the numeric value of the input dmax , but is exponential in the
bit length of dmax , i.e., log(dmax ) [14].
B We further propose an FPTAS (Algorithm 3, Sec. V) to
solve Min-Max-Delay approximately. The algorithm achieves
a (1 + )-approximation ratio for any  > 0 with a time complexity of O((N M )3.5 log R log(N M )(L + log N )), where
M = |E|(1+1/) and L is the bit complexity for representing
dmax . The time complexity is polynomial in the problem input
and 1/.
B We demonstrate the effectiveness of our algorithms in the
scenario of delay-critical inter-datacenter video-conferencing
traffic routing over multiple paths, using simulations based on
Amazon EC2 inter-datacenter topology. Both of our algorithms
achieve optimal maximum delay performance in all simulation
instances, which always the meet practically acceptable endto-end delay requirement for video conferencing. In contrast,

the state-of-the-art solutions only obtain sub-optimal maximum delay performance, which fail to satisfy the videoconferencing delay requirement for up to 15% of simulation
instances between certain cross-continental source-receiver
pair.
C. Paper organization
The rest of the paper is organized as follows. Sec. II gives
our system model and defines the problem Min-Max-Delay.
Sec. III proves Min-Max-Delay to be NP-hard. We propose a
pseudo-polynomial time algorithm in Sec. IV and an FPTAS
in Sec. V. The NP-hardness proof together with the proposed
pseudo-polynomial time algorithm show that the problem MinMax-Delay is NP-hard in the weak sense. Sec. VI presents our
experiments and Sec. VII reviews existing studies, followed by
the conclusion in Sec. VIII.
II. S YSTEM M ODEL AND P ROBLEM F ORMULATION
We consider a multi-hop network modeled as a directed
graph G , (V, E) with |V | nodes and |E| links. Each link
e ∈ E has a non-negative capacity ce and a non-negative
integer delay de . We define N , max{|V |, |E|} to describe
the size of the network, and dmax , max de as the maximum
e∈E
link delay. A source s ∈ V needs to stream a flow at a positive
rate R to a receiver t ∈ V \{s}, possibly using multiple paths.
We denote P as the set of all paths from s to t. For any
path p ∈ P , we denote its path delay as
X
dp ,
de ,
(1)
e∈E:e∈p

i.e., the summation of link delays along the path. A flow
solution f is defined as the assigned flow rate over P , i.e.,
f , {xp : xp ≥ 0, p ∈ P }. For a flow solution f , we define
X
xe ,
xp
(2)
p∈P :e∈p

as the link rate of link e ∈ E. We further denote the total flow
rate of a flow solution f by |f |, namely
X
|f | =
xp .
(3)
p∈P

The maximum delay of a flow solution f is defined as
D(f ) ,

max

p∈P :xp >0

dp ,

(4)

i.e., the maximum delay among paths with positive rates.
Another well-known end-to-end delay metric for a flow in the
literature is the total delay, defined as
X
X
T (f ) ,
(xp · dp ) =
(xe · de ),
(5)
p∈P

e∈E

i.e., the total delay experienced by all flow units.
We consider the problem of finding a flow solution f to
minimize the maximum delay D(f ) while satisfying both
the flow rate requirement subject to link capacity constraints.

3

TABLE I: Summary of the difference in hardness and admitting exact/approximation algorithms of the Maximum Latency
Problem studied in the literature and problem Min-Max-Delay studied in this paper.
Problem

Hardness

Maximum latency problem

APX-hard [12]
Weakly NP-hard
(Thm. 3, Sec. IV)

Min-Max-Delay

Exact algorithm with pseudo
-polynomial time complexity
7

Polynomial-time algorithm with
constant approximation ratio
7

3(Algorithm 1, Sec. IV)

3(Algorithm 3, Sec. V)

We denote the problem as Min-Max-Delay which can be
formulated as
min D
X
s.t.
xp = R,

(6a)

v1

w0

w1

(6b)

p∈P

X

xe =

p

x ≤ ce , ∀e ∈ E,

p∈P :e∈p
p

xp (d − D) ≤ 0, ∀p ∈ P,
vars.

p

x ≥ 0, ∀p ∈ P,

(6c)

v2

vn

w2

...

wn-1

wn

Link with capacity 1 and positive delay

Source

Link with capacity 1 and delay 0

Receiver

Fig. 1: Reduced network graph from partition problem.

(6d)
(6e)

where (6a) together with (6d) define our objective to minimize
the maximum path delay for s−t paths that carry positive flow
rates (called flow-carrying paths). Constraint (6b) restricts that
the source s sends R rate to the receiver t, and constraint (6c)
requires that the flow rate on link e does not exceed its capacity
ce . In this paper we use fMM to denote the Min-Max-Delay
flow, namely the optimal flow to our problem Min-Max-Delay,
and hence D(fMM ) is the optimal maximum delay supporting
a flow rate of R.
From formulation (6) we observe two difficulties to solve
Min-Max-Delay: (i) the number of paths (number of variables)
is in general exponential in the network size, and (ii) formulation (6) is non-convex due to constraint (6d). In fact, later
in Sec. III we prove Min-Max-Delay is NP-hard. Therefore,
we cannot obtain fMM within polynomial time unless P = NP.
III. NP- HARDNESS
In this section, we analyze the computational complexity of
Min-Max-Delay. Specifically, we prove that Min-Max-Delay
is NP-hard based on the reduction from the well-known NPcomplete partition problem [14]. Thus, even as a special case
of the NP-hard maximum latency problem, Min-Max-Delay
is still NP-hard and it is impossible to solve in polynomial
time unless P = NP.

The partition problem is known to be NP-complete [14] (in
the weak sense). We now leverage it to prove that Min-MaxDelay is NP-hard.
Theorem 1. Min-Max-Delay problem is NP-hard.
Proof: For any partition problem (Definition 2), we can
construct a graph G0 with (2n + 1) nodes and 3n links as
in Fig. 1. All links in the graph have unit capacity. Each
dashed link (wi−1 , wi ) has a delay of ai for any i = 1, · · · , n,
and solid links (wi−1 , vi ) and (vi , wi ) have a delay of zero.
Obviously it takes polynomial time to construct the graph G0
from any given partition problem.
Now we consider the decision version of a Min-Max-Delay
problem instance: in graph G0 with source s = w0 , receiver
t = wn , and flow rate requirement R = 2, is there any feasible
flow f such that the maximum delay D(f ) ≤ b?
In the following we prove the partition problem answers
“Yes” if and only if the decision version of above Min-MaxDelay problem instance answers “Yes”.
If Part. If the decision problem of Min-Max-Delay answers
“Yes”, then there exists a flow f such that D(f ) ≤ b. Since f
is feasible, the total rate from w0 to wn in f is R = 2. Now
due to the capacity constraint and flow conservation, any link
must exactly be assigned a flow rate of 1 to satisfy the total
requirement R = 2. The total delay in flow f is
X

xp dp =

p∈P

X

xe de =

e∈E

X
e∈E

1 · de =

n
X

ai = 2b.

(9)

i=1

Definition 1 (Partition). Given a non-empty set A, its partition
is a set of non-empty subsets such that each element in A is
in exactly one of these subsets.

Since D(f ) ≤ b, we have

Definition 2 (Partition Problem [14]). Given a set of n positive
integers A = {a1 , a2 , ..., an } with sum
X
ai = 2b.
(7)

Also, because the total flow rate is equal to 2, we have
X
X
X
2b =
xp dp =
xp dp ≤ b ×
xp = 2b.

dp ≤ D(f ) ≤ b, ∀p ∈ P with xp > 0.

p∈P

p∈P :xp >0

p∈P :xp >0

(11)

ai ∈A

The partition problem asks is there a partition {A1 , A2 } of A
such that
X
X
ai =
aj = b?
(8)
ai ∈A1

(10)

aj ∈A2

As both ends in (11) are the same, it must be
dp = b, ∀p ∈ P with xp > 0.

(12)

Therefore, all flow-carrying paths have a path delay of b.
We choose an arbitrary flow-carrying path p. Since all solid

4

links have a delay of 0, the path delay of p is the delay of
all dashed links belonging to p. We consider the set A1 that
contains ai if (wi−1 , wi ) ∈ p. Clearly, it holds that
X
ai = b.
(13)
ai ∈A1

We then define A2 = A\A1 . It shall be
X
X
X
ai = 2b − b = b.
aj =
ak −
aj ∈A2

ak ∈A

(14)

ai ∈A1

A1 and A2 are thus a partition of set A and meet the
requirement of the partition problem. Hence, the partition
problem answers “Yes”.
Only If Part. If the partition problem answers “Yes”, then
there exists a partition {A1 , A2 } such that
X
X
aj = b.
(15)
ai =
ai ∈A1

A. DCMF: maximize the flow subject to delay constraint
A closely-related problem to Min-Max-Delay is the DelayConstrained Maximum Flow problem [15], denoted as DCMax-Flow: given a graph G, a source s, a receiver t, and a
deadline T which is a path delay upper bound for all flowcarrying paths from s to t, the problem requires to find a
feasible s − t flow with a maximized flow rate. If we denote
P T as the set of all s − t paths whose path delay does not
exceed T , the DC-Max-Flow can be formulated as
X
xp ,
max
(17a)
p∈P T

aj ∈A2

We then construct the flow f with only two flow-carrying
paths p1 and p2 and set xp1 = xp2 = 1. Since p1 and p2
are disjoint, the capacity constraint is satisfied. Also, since
xp1 + xp2 = R = 2, the rate requirement is satisfied. Thus f
is a feasible flow with maximum delay D(f ) ≤ b. Therefore,
the decision problem of Min-Max-Delay answers “Yes”.
Since the partition problem is NP-complete [14] and the
reduction can be done in polynomial time, the Min-Max-Delay
problem is NP-hard.
Similar to the maximum latency problem, Min-Max-Delay
is NP-hard. However, since in the following section a pseudopolynomial time algorithm is proposed to solve Min-MaxDelay optimally, Min-Max-Delay is actually NP-hard in the
weak sense which is fundamentally different from the maximum latency problem that has been proved to be APX-hard.
IV. E XACT P SEUDO - POLYNOMIAL T IME A LGORITHM
In this section we propose an exact pseudo-polynomial time
algorithm to solve Min-Max-Delay optimally. This, combined
with the NP-hardness result in Thm. 1, shows that Min-MaxDelay is NP-hard in the weak sense. This result, combined
with the existence of FPTAS described later in our Sec. V,
shows that the Min-Max-Delay problem is fundamentally
different from the maximum latency problem studied in the
literature, which is APX-hard and admits no PTAS exists
unless P = NP. Moreover, in our experiments (Sec. VI),

X

xe =

s.t.

aj ∈A2

We now construct two paths p1 and p2 .
• ∀i ∈ [1, n], if ai ∈ A1 , we put (wi−1 , wi ) into path p1 ;
otherwise, we put (wi−1 , vi ) and (vi , wi ) into p1 .
• Similarly, for any i, if ai ∈ A2 , we put (wi−1 , wi ) into
p2 ; otherwise, we put (wi−1 , vi ) and (vi , wi ) into p2 .
Due to the definition of a partition (see Definition 1), A1
and A2 are two disjoint sets, i.e., A1 ∩ A2 = ∅. Thus, we can
easily see that p1 and p2 are two disjoint s − t paths, i.e., p1
and p2 do not share any common link. Furthermore, it clearly
holds that
X
X
dp1 =
ai = b, dp2 =
aj = b.
(16)
ai ∈A1

extensive simulations show that the proposed exact algorithm
always generates the optimal solution in 0.5 second empirically, implying that the exact algorithm is practically efficient.

xp ≤ ce ,

(17b)

p∈P T :e∈p

xp ≥ 0, ∀p ∈ P T .

vars.

(17c)

Since the size of P T could increase exponentially in the
network size, formulation (17) can have an exponential number
of variables. However, Wang and Chen [15] show that DCMax-Flow can be solved efficiently by an edge-based flow
formulation which is a linear program with at most |E|·T variables. They implicitly use the idea of hop-expanded graph [15]
by converting a delay-constrained max-flow problem in the
original graph into a delay-unconstrained max-flow problem
in the hop-expanded graph. In [15], the links are assumed
to have unit-delay, but it is easy to generalize the results to
integer-delay links. Overall the algorithm to solve problem
DC-Max-Flow optimally with input (G, s, t, T ), denoted by
DCMF(G, s, t, T ) in this paper, is to solve the following linear
program [15, Proposition 1],
max

T
X X

xe(d)

(18a)

e∈In(t) d=0

s.t.

X

e)
x(d
=
e

X

xe(d) =

e∈In(v)

x(d)
e ,

xe(d+de ) ,

e∈Out(v)

∀v ∈ V \{s, t}, d ∈ [0, T ]
T
X

vars.

d=0
x(d)
e

(18b)

e∈In(t) d=0

e∈Out(s)

X

T
X X

x(d)
e ≤ ce ,
≥ 0,

(18c)

∀e ∈ E

(18d)

∀e ∈ E, d ∈ [0, T ]

(18e)

where In(v) , {e = (w, v) : e ∈ E, w ∈ V } is the set
containing all incoming links of node v. Similarly, Out(v) ,
{e = (v, w) : e ∈ E, w ∈ V } is the set of outgoing links
(d)
of node v, and xe is the total flow rate that experiences a
delay of d after passing link e from the source s. The objective
(18a) is the total flow rate that arrives at the receiver t within
the deadline T . Constraint (18b) requires the rate entering
the network should equal to the rate leaving the network.
Constraints (18c) are the flow conservation constraints in the

5

expanded graph. Note that by convention, for any link e ∈ E,
(d)
we set xe = 0 for d < 0 and d > T . Constraints (18d) are the
link capacity constraints which describe that flow rate assigned
on the same link but experiencing different delays from the
source should jointly respect the link capacity constraint.
B. MMD: minimize the delay subject to flow requirement
Comparing the problem Min-Max-Delay to the problem
DC-Max-Flow, from a source s to a receiver t in a graph G, if
we denote d∗ (R) as the minimized maximum delay subject to
a rate requirement R (the optimal value of Min-Max-Delay),
and we denote r∗ (T ) as the maximized flow rate subject to a
deadline constraint T (the optimal value of DC-Max-Flow),
we have the following lemma which is helpful to design an
exact algorithm to solve Min-Max-Delay.
Lemma 1. d∗ (R) ≤ T if and only if r∗ (T ) ≥ R.
Proof: If Part. If r∗ (T ) ≥ R, then there exists a flow
solution over P T , i.e., f = {xp : p ∈ P T } such that
X
xp ≥ R.
(19)
p∈P T

We can thus decrease the flow solution f to construct another
flow solution f˜ such that
X
x̃p = R.
(20)
p∈P T

Since f satisfies the capacity constraints, f˜ must also satisfy
the capacity constraints. Thus, f˜ is a feasible solution to
Min-Max-Delay with rate requirement R. In addition, since
all flow-carrying paths in f˜ belong to the set P T , we have
d∗ (R) ≤ D(f˜) ≤ T .
Only If Part. If d∗ (R) ≤ T , then there exists a flow solution
f where the path delay of any flow-carrying path does not
exceed T . Thus all flow-carrying paths belong to P T and f is
also a feasible solution to DC-Max-Flow with a delay bound
T . Thus, it holds that
X
r∗ (T ) ≥
xp = R.
(21)
p∈P T

Lem. 1 suggests a binary search scheme to solve Min-MaxDelay optimally, namely our Algorithm 1. Given a lower
bound Tl (= 0 initially) and an upper bound Tu (= U
initially and U can be the maximum delay of any feasible flow
satisfying rate requirement R) of the optimal maximum delay,
in each iteration we solve the problem DC-Max-Flow with
input (G, s, t, T ) where T = d(Tl + Tu )/2e. We compare the
optimal value of (18), i.e., r∗ (T ) with the rate requirement R.
If r∗ (T ) ≥ R, we decrease the upper bound as Tu = T − 1.
Otherwise, if r∗ (T ) < R, we increase the lower bound as
Tl = T + 1. In the end we can achieve a feasible s − t flow
with maximum flow-carrying path delay optimized and the
given flow rate requirement satisfied.
Theorem 2. Algorithm 1 solves Min-Max-Delay optimally and has a pseudo-polynomial time complexity of
O((N U )3.5 log(N U ) log R) where N , max{|V |, |E|}.

Algorithm 1 MMD(G, R, s, t, U ): solve Min-Max-Delay optimally in pseudo-polynomial time
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

Input: G = (V, E), R, s, t, U
Output: fMM
procedure
Tl = 0, Tu = U , T ∗ = Tu
while Tu ≥ Tl do
T = d(Tl + Tu )/2e
f = DCMF(G, s, t, T )
r∗ (T ) = |f |
if r∗ (T ) ≥ R then
fMM = f , T ∗ = T
Tu = T − 1
else
Tl = T + 1
end if
end while
return fMM
end procedure

Proof: The optimality of the binary search scheme directly follows from Lem. 1.
Our binary search scheme terminates in O(log U ) iterations
where U must be upper bounded by |E| · dmax even in the
worst case. In each iteration given a T ≤ U , we need to solve
the linear program (18). Obviously the number of variables
in (18) is O(|E| · T ). The conservation constraint (18c) is
formulated for v ∈ V \{s, t} and d ∈ [0, T ]. Thus the number
of conservation constraint is O(|V | · T ). Clearly the number
of capacity constraint (18d) is |E|. Overall, the number of
constraints in formulation (18) is O(N T ).
[16] has proposed an algorithm to solve a linear program
within time O((g + h)1.5 hL) where g is the number of
constraints, h is the number of variables, and L denotes the
standard “bit complexity” of the linear program. Therefore,
it takes O((N T )2.5 (log R + N T log(N T ))) time to solve
formulation (18) based on the calculation of L [17] and the
Hadamard’s inequality. Since T ≤ U , the overall time complexity is O((N U )2.5 (log R+N U log(N U )) log U ) which can
be described by O((N U )3.5 log(N U ) log R).
Without loss of generality, clearly it holds that U ≤
|E| · dmax which is an upper bound for the path
delay of any simple source-receiver paths, and hence
the time complexity in Thm. 2 can be described by
O((N 2 dmax )3.5 log(N 2 dmax ) log R). The time complexity is
pseudo-polynomial in the sense that it is polynomial in the
numeric value of the input dmax , but it is exponential in the
bit length of the dmax . In the next section we design an FPTAS
for our problem Min-Max-Delay. For any  > 0, the FPTAS
can find a (1+)-approximate solution and the time complexity
is polynomial with the problem input and 1/.
A direct result of Thm. 2 is as follows.
Theorem 3. Min-Max-Delay is NP-hard in the weak sense.
Proof: It follows from Thm. 1 and Thm. 2.
Note that in the end of Algorithm 1, solving linear program

6

(18) gives an edge-based flow with the optimal maximum
delay d∗ (R). We need to do a flow decomposition on the
hop-expanded graph with a deadline constraint T = d∗ (R) in
order to get a path-based flow. The number of nodes and links
in the expanded graph are both O(N d∗ (R)). And since the
flow decomposition in a graph Ĝ(V̂ , Ê) has a time complexity
of O(|Ê|(|V̂ | + |Ê|)) [18], the time complexity to get the
path-based flow by decomposition in the expanded graph will
be O((N U )2 ), which does not affect the time complexity of
Algorithm 1 presented in Thm. 2.
V. F ULLY-P OLYNOMIAL T IME A PPROXIMATION S CHEME
In this section, we propose an FPTAS to solve Min-MaxDelay (1 + )-approximately in polynomial time with all the
problem input and 1/. The existence of FPTAS for the MinMax-Delay problem reveals its fundamental difference to the
maximum latency problem, which is APX-hard and admits no
PTAS unless P = NP.
Recall that our exact algorithm solves Min-Max-Delay
optimally by pursuing the minimum T ∗ = D(fMM ) ∈
{0, 1, 2, ..., U } iteratively such that the problem DC-MaxFlow with input (G, s, t, T ∗ ) can return a feasible s − t flow
with a flow rate r∗ (T ∗ ) ≥ R. Due to the binary search scheme,
the number of iterations to achieve the optimal solution is
O(log U ), which is not a problem to achieve a polynomial time
complexity considering that U ≤ |E| · dmax . The difficulty of
developing polynomial time algorithms in fact is the pseudopolynomial size (O(N T ), T ∈ {0, 1, 2, ..., U }) of the linear
program (18), namely in each iteration, it takes pseudopolynomial time to solve DC-Max-Flow with deadline T .
In order to solve Min-Max-Delay approximately in polynomial time, a natural idea is to follow the similar binary search
procedure of our proposed exact algorithm MMD(·) but in
each iteration quantize T to make the size of the problem
DC-Max-Flow independent of T and polynomial with all
the problem input and 1/, which is challenging since we
also need to maintain certain maximum delay performance
guarantee simultaneously. Our proposed FPTAS in this section
utilizes an adaptive quantization technique on link delay de
and T to address the challenge, and in the end a (1 + )approximate solution is guaranteed in fully polynomial time.
A. Quantized DC-Max-Flow algorithm
Given a deadline T , we first introduce a procedure QDCMF(·) in Algorithm 2 which solves a DC-Max-Flow problem after the quantization of de and T . The procedure must
return a feasible flow with a total flow rate no smaller than
R in polynomial time, if T is an upper bound of the optimal
solution to Min-Max-Delay, i.e. our Algorithm 2 must return
a flow fˆ in polynomial time with |fˆ| ≥ R if T ≥ D[fMM ] (see
our Lem. 3). The procedure will be used iteratively in a binary
search scheme later in our FPTAS, similar to the structure of
our exact algorithm MMD(·) (Algorithm 1).
First, each link delay is quantized (line 5) to be the multiple
of an appropriately defined ∆T (line 4). Then we define the
quantized network Ĝ as the network G with each link delay
de replaced by dˆe (line 7). Besides, T is also quantized to

Algorithm 2 QDCMF(G, s, t, T, ): quantized DC-Max-Flow
algorithm
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

input: G = (V, E), s, t, T , 
output: fˆ
procedure
∆T = T /|E|
dˆe = dde /∆T e, ∀e ∈ E
T̂ = dT /∆T e + |E|
Ĝ(V, E): G(V, E) with each de replaced by dˆe
fˆ = DCMF(Ĝ, s, t, T̂ )
return fˆ
end procedure

be T̂ based on ∆T (line 6). Due to that T̂ = d|E|/e + |E|
which is independent of link delay, clearly the DC-Max-Flow
in the graph Ĝ with the input deadline T̂ is polynomial-timesolvable. Moreover, such T̂ can guarantee that the quantized
deadline T̂ is still an upper bound for the maximum delay
of fMM in the quantized network Ĝ, if the deadline T is an
upper bound for the maximum delay of fMM in G, which will
be proved later in our Lem. 3. Finally in line 8, the returned
solution fˆ is the optimal solution to problem DC-Max-Flow
in the quantized network Ĝ with the quantized deadline T̂ .
Since Ĝ and G share the same network topology and link
capacity, obviously a flow f is feasible in Ĝ if and only if it is
feasible in G. Due to the difference of link delay in those two
networks, the maximum delay of f in Ĝ may be different from
the maximum delay of the same flow f in G. In order to avoid
possible confusion in the following lemmas and theorems, we
use DĜ (f ) to denote the maximum delay of f in the quantized
network Ĝ. Similarly, DG (f ) is the maximum delay of f in
the original network G. Without loss of generality, D(f ) is
same to DG (f ) since G is the input to Min-Max-Delay.
Now first we prove Lem. 2 which will be used later
to prove the (1 + )-approximation ratio for our FPTAS.
Then we give Lem. 3 to show the solution fˆ of algorithm
QDCMF(G, s, t, T, ) (Algorithm 2) must satisfy |fˆ| ≥ R if
D(fMM ) ≤ T .
Lemma 2. It holds that DG (f ) ≤ ∆T · DĜ (f ) where Ĝ and
∆T is defined in Algorithm 2.
Proof: Suppose Pf is the flow-carrying path set of f .
Since the only difference between G and Ĝ is the link delay,
clearly Pf does not change in G and in Ĝ.
Now the lemma holds due to the following proof:

DG (f ) = max

X

p:p∈Pf

= ∆T · max

p:p∈Pf

e:e∈p

X

de ≤ max

p:p∈Pf

X

[∆T dde /∆T e]

e:e∈p

dˆe = ∆T · DĜ (f )

e:e∈p

Lemma 3. If T ≥ D(fMM ), QDCMF(G, s, t, T, ) must return
a feasible flow solution fˆ and |fˆ| ≥ R.

7

Proof: Since T ≥ D(fMM ), by Lem. 1, the solution to
problem DCMF(G, s, t, T ), denoted as f , must satisfy
|f | ≥ R and DG (f ) ≤ T,

(22)

due to the assumption d∗ (R) = D(fMM ) ≤ T , namely there
must exist a feasible flow f in G with a total flow rate lower
bounded by R and a maximum delay upper bounded by T ,
assuming T is an upper bound for the optimal to Min-MaxDelay. As long as we can prove DĜ (f ) ≤ T̂ , namely the
maximum delay of f in Ĝ is no larger than T̂ , we can prove
Lem. 3 since f is a feasible solution to DCMF(Ĝ, s, t, T̂ )
with |f | ≥ R and furthermore fˆ is the optimal solution to
DCMF(Ĝ, s, t, T̂ ) which maximizes the flow rate from s to t,
leading to the conclusion of |fˆ| ≥ |f | ≥ R.
The detailed proof is shown below assuming Pf is the flowcarrying path set of f :
X
DĜ (f ) = max
dde /∆T e
p:p∈Pf

X

≤ max

p:p∈Pf

≤ max

(de /∆T + 1)

p:p∈Pf

X

7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

input: G = (V, E), R, s, t, U , 
output: fFPTAS
procedure
Tu = U , Tl = 0, T ∗ = Tu
while Tu ≥ Tl do
T = d(Tu + Tl )/2e
fˆ = QDCMF(G, s, t, T, )
if |fˆ| < R then
Tl = T + 1
else
T ∗ = T , Tu = T − 1
end if
end while
fFPTAS = QMMD(G, R, s, t, T ∗ , )
return fFPTAS
end procedure

Algorithm 4 QMMD(G, R, s, t, T, ): quantized Min-MaxDelay algorithm
1:

(de /∆T ) + |E|

e:e∈p

X
1
· max
de + |E|
=
∆T p:p∈Pf e:e∈p
=

1:
2:
3:
4:
5:
6:

e:e∈p

e:e∈p

(a)

Algorithm 3 FPTAS to solve Min-Max-Delay

1
· DG (f ) + |E|
∆T

2:
3:
4:
5:
6:
7:

(b)

≤ dDG (f )/∆T e + |E| ≤ T̂
Inequality (a) holds since the number of links on any flowcarrying path is upper bound by |E| in f without loss of
generality. Inequality (b) holds due to the inequality (22).
Next we prove the polynomial time complexity for QDCMF(G, s, t, T, ).
Lemma 4. Algorithm 2 has a fully polynomial time complexity
of O((N M )3.5 log R log(N M )) where M = |E|(1+1/)+1.
Proof: It is straightforward that the overall time complexity of QDCMF(G, s, t, T, ) is dominated by the time
complexity of DCMF(Ĝ, s, t, T̂ ) (line 8). Now considering
that
T̂ = dT /∆T e + |E| = d|E|/e + |E| ≤ |E|(1 + 1/) + 1,
following the similar procedure in Thm. 2 we can get the
proposed time complexity.
B. FPTAS to solve Min-Max-Delay
We describe our FPTAS in Algorithm 3, which follows a
similar structure as our MMD(G, R, s, t, U ) (Algorithm 1) that
solves Min-Max-Delay optimally in pseudo-polynomial time,
except for two differences:
(i) in each iteration, FPTAS solves a quantized DC-MaxFlow problem optimally (line 7) while MMD solves the exact
DC-Max-Flow problem optimally, and
(ii) in the algorithm MMD, when the binary search terminates, associated T ∗ is the optimal maximum delay, and thus

8:
9:
10:

input: G = (V, E), R, s, t, T , 
output: fˆ
procedure
∆T = T /|E|
dˆe = dde /∆T e, ∀e ∈ E
T̂ = dT /∆T e + |E|
Ĝ(V, E): G(V, E) with each de replaced by dˆe
fˆ = MMD(Ĝ, R, s, t, T̂ )
return fˆ
end procedure

the solution to problem DC-Max-Flow with deadline T ∗ is the
optimal solution to our Min-Max-Delay. However, when the
binary search terminates in the FPTAS, associated T ∗ may not
be the optimal maximum delay, and the (1 + )-approximate
solution is the solution to problem QMMD(G, R, s, t, T ∗ , )
(line 14), which is the problem Min-Max-Delay (not the
problem DC-Max-Flow) in the quantized network Ĝ with a
maximum delay upper bound T̂ ∗ = dT ∗ /∆T ∗ e + |E|.
The quantization approach in QMMD(·) (Algorithm 4)
is same as in QDCMF(·) (Algorithm 2) with the size of
formulation (18) to be d|E|/e + |E| which is independent
of dmax and polynomial with problem input and 1/, clearly
leading to a polynomial time complexity of our FPTAS. Next
we will prove the (1 + )-approximate performance guarantee.
Lemma 5. In the end of Algorithm 3, it holds that T ∗ ≤
D(fMM ).
Proof: Suppose Topt is the maximum delay performance
of the optimal solution to Min-Max-Delay, namely Topt =
D(fMM ). According to Lem. 3, QDCMF(G, s, t, T, ) always
returns a feasible flow fˆ and |fˆ| ≥ R for any T ∈ [Topt , U ],
and may or may not return such a flow for T ∈ [0, Topt ).
Considering the property of the binary search structure of our
FPTAS, in the end, clearly that T ∗ ≤ Topt = D(fMM ).
Note that in the end of our FPTAS, T ∗ may not be

8

the minimum integer among T ∈ [0, U ] such that QDCMF(G, s, t, T, ) returns a feasible flow with a total rate
no smaller than R. In fact, our FPTAS only requires that
T ∗ ≤ D(fMM ) to guarantee a (1 + ) approximation ratio,
as proved in the following theorem.
Theorem 4. Algorithm 3 is a (1 + )-approximate algorithm
for the Min-Max-Delay problem, namely
D(fFPTAS ) ≤ (1 + )D(fMM )
Proof: The theorem holds due to the following proof:
(a)

(b)

DG (fFPTAS ) ≤ ∆T ∗ · DĜ (fFPTAS ) ≤ ∆T ∗ · DĜ (fMM )
X
= ∆T ∗ · max
dde /∆T ∗ e
p:p∈PfMM

≤ ∆T ∗ · max

p:p∈PfMM

≤ ∆T ∗ · max

p:p∈PfMM

Fig. 2: Topology of the 6 Amazon EC2 datacenters.
TABLE II: Link delays (in ms) for Amazon EC2 [6], (OR:
Oregon, VA: Virginia, IR: Ireland, TO: Tokyo, SI: Singapore,
SP: Sao Paulo).

e:e∈p

X

(de /∆T ∗ + 1)

e:e∈p

X

(de /∆T ∗ ) + ∆T ∗ |E|

e:e∈p

OR
VA
IR
TO
SI
SP

OR
N/A
-

VA
41
N/A
-

IR
86
54
N/A
-

TO
68
101
138
N/A
-

SI
117
127
117
45
N/A
-

SP
104
82
120
151
182
N/A

= DG (fMM ) + ∆T ∗ |E| = DG (fMM ) + T ∗
(c)

≤ (1 + )DG (fMM )
Inequality (a) holds due to Lem. 2. Inequality (b) is true
because fFPTAS is the optimal to problem Min-Max-Delay in
the graph Ĝ (our Algorithm 4). Inequality (c) is true due to
Lem. 5.
Theorem 5. Algorithm 3 has a fully polynomial time complexity of O((N M )3.5 log R log(N M )(L + log N )) where
M = |E|(1 + 1/) + 1 and L is the bit complexity for
representing dmax .
Proof: Assume we need L bits to represent dmax ,
namely dmax = O(2L ). According to Lem. 4, in each
iteration of Algorithm 3, corresponding time complexity is
O((N M )3.5 log R log(N M )). Due to the fact that the initial
upper bound U for the optimal maximum delay is definitely
upper bounded by |E| · dmax , namely U ≤ |E| · dmax , in
the binary search scheme in our FPTAS we need at most
O(log(|E| · dmax )) iterations, leading to the proposed time
complexity in the end. Note that in the running time of
QMMD(·) (line 14) of Algorithm 3 is not a dominating part
according to Thm. 2 and does not affect the time complexity.
Thm. 4 together with Thm. 5 shows that our proposed
Algorithm 3 can guarantee an approximation ratio of (1 + )
within polynomial time for any  > 0, and hence Algorithm 3
is an FPTAS for the problem Min-Max-Delay. In contrast, as
a generalization of our Min-Max-Delay, the maximum latency
problem studied in the literature has been proved to be APXhard [12] and admits no PTAS unless P = NP. Thus, although
Min-Max-Delay is an important special case of the maximum
latency problem which has been proved to be quite difficult to
approximate, there exist efficient approximate algorithms, e.g.
our proposed Algorithm 3, to solve the Min-Max-Delay with
an approximation ratio arbitrarily close to one in polynomial
time. This result reveals a fundamental difference between the
two problems.

VI. P ERFORMANCE E VALUATION
In this section we evaluate our proposed algorithms and see
how the empirically achieved maximum delay performance
meets the video-conferencing end-to-end delay requirement
(400ms as suggested by [10]), comparing our algorithms to
state-of-the-art approaches using a real-world continent-scale
inter-datacenter network topology of 6 globally distributed
Amazon EC2 datacenters as shown in Fig. 2, modeled as a
complete undirected graph. Each undirected link is treated
as two directed links that operate independently and have
identical capacities, a common way to model an undirected
graph by a directed one, e.g. in [19]. We set integer link delays
(see Tab. II) and link capacities (see Tab. III) according to
practical evaluations on Amazon EC2 from studies [5], [6].
We do extensive simulations to solve Min-Max-Delay problem instances belonging to 4 different experimental cases (see
Tab. IV). For each case characterized by a specific sourcereceiver pair, we solve Min-Max-Delay instances with flow
rate requirement enumerated from Rmin to Rmax with a unit
step. In this paper, Rmin is set to be the minimum flow rate
when multiple paths (≥ 2 paths) must be used for delay
minimization while supporting the required flow rate, since
otherwise the Min-Max-Delay problem can be reduced to the
simple shortest path problem that is polynomial-time solvable
by Dijkstra’s algorithm [20] and is not our focus. We set Rmax
to be the maximum flow rate that can be sent from the source
TABLE III: Link capacities (in Mbps) for Amazon EC2 [5],
(OR: Oregon, VA: Virginia, IR: Ireland, TO: Tokyo, SI:
Singapore, SP: Sao Paulo).
OR
VA
IR
TO
SI
SP

OR
N/A
-

VA
82
N/A
-

IR
86
72
N/A
-

TO
138
41
56
N/A
-

SI
74
52
44
166
N/A
-

SP
67
70
61
41
33
N/A

9

to the receiver.
Our test environment is an Intel Core i5 (2.40 GHz) processor with 8 GB memory running Windows 64-bit operating
system. All the experiments are implemented in C++ and
linear programs are solved using CPLEX [21].
A. Baseline algorithms
In order to evaluate the performance of our exact algorithm
and FPTAS, we compare them to three existing approaches.
1) the System-Optimal flow algorithm (SO): the systemoptimal flow is a γ(L)-approximate solution to the maximum
latency problem of minimizing the maximum delay with flowdependent link delay model, but theoretically it is not a good
solution to Min-Max-Delay with link capacity constraint and
integer link delay because its maximum delay performance
can become infinitely large compared to the optimal. In the
experiments we obtain the system-optimal flow by solving its
well-known edge-based linear programming formulation:
X
min
(de · xe )
(23a)
e∈E

s.t.

X
e∈Out(s)

xe = R,

(23b)

xe , ∀v ∈ V \{s, t},

(23c)

e∈In(t)

X

X

xe =

e∈Out(v)

vars.

X

xe =

e∈In(v)

xe ≤ ce , ∀e ∈ E,

(23d)

xe ≥ 0, ∀e ∈ E.

(23e)

In order to get the path-based system-optimal flow and associated maximum delay result, we do flow decomposition [18]
on the optimal solution to the linear program (23).
2) the heuristic Iterative Shortest Path algorithm
(ISP) [22]: the ISP approach is proposed by [22] to
solve the maximum latency problem, and it can be used
to handle our Min-Max-Delay directly with additional link
capacity constraint involved. However, ISP is a heuristic
approach with no maximum delay performance guarantee both
in the maximum latency problem and in our Min-Max-Delay.
ISP finds the shortest path from source to receiver iteratively, and in each iteration it assigns as much flow rate as
possible to corresponding returned path. In our experiments
we use Dijkstra’s algorithm [20] to get the shortest path.
3) the heuristic Iterative Linear Relaxation algorithm
(ILR) [5]: the study in [5] optimizes three different endto-end-delay-related objectives in a general multi-commodity
multi-cast scenario with constant link delay and constant link
capacity. And our Min-Max-Delay problem in the singleunicast scenario can be casted by one of the three problems
in [5] with the following formulation:
X
min max{dp φ(xp )} + β
φ(xp )
(24a)
p∈P

s.t.

X

p∈P
p

x = R,

(24b)

p∈P

X
vars.

e∈E:e∈p
p

xp ≤ ce , ∀e ∈ E,

x ≥ 0, ∀p ∈ P.

(24c)
(24d)

TABLE IV: Respective failure (%) of baseline algorithms
to satisfy the video-conferencing delay requirement for 4
different experimental cases.
Source
Receiver
Flow rate,
[Rmin , Rmax ]
ISP
Failure of
ILR
Algo. (%)
SO

Case 1
OR
TO

Case 2
VA
IR

Case 3
VA
SI

Case 4
IR
SI

[139, 442]

[73, 317]

[53, 317]

[45, 319]

7
7
7

2
1
2

0
0
0

9
15
0

where φ(·) is an identity function defined as
(
1, if x > 0,
φ(x) =
0, if x = 0.
The work in [5] defines variables as the flow rate assigned
on the source-receiver paths with upper bounded length to
reduce the time complexity. But in our experiments in order to
minimize the maximum delay, we consider all source-receiver
paths, namely the path set P . In the objective (24a), β is used
by [5] as a penalty when too many paths are utilized to carry
flow rates because the authors of [5] try to get a sparse network
flow solution. However, in our experiments β is set to be 0 to
optimize the maximum delay performance.
Formulation (24) is hard to solve because of the identity
function φ(·). The study in [5] proposes the ILR heuristic
approach to overcome the difficulty by solving linear programs
which are relaxations to formulation (24) iteratively. Details
of ILR are referred to the paper [5]. As discussed later in our
related work section, ILR has neither maximum delay performance guarantee nor running time performance guarantee
theoretically.
B. Experiments of our pseudo-polynomial time algorithm
We first evaluate the performance of our pseudo-polynomial
time algorithm MMD (Algorithm 1) which can solve MinMax-Delay optimally. In the experiments, TU is set to be
the maximum delay of the flow solution to ISP, and thus
the running time of the heuristic approach ISP is part of the
total running time of MMD. We do simulations for extensive
Min-Max-Delay instances as described in our Tab. IV, using
algorithms including SO, ISP, ILR and our MMD.
Recall as discussed in our introduction, to guarantee a
real-time interaction for video conferencing, 400ms is the
maximum acceptable end-to-end delay budget according to the
suggestion from ITU [10]. Note that an end-to-end delay is in
fact the delay experienced by the video and audio through
a video conferencing, i.e. from source camera to receiver
screen, which is a sum of coding delay at source, decoding
delay at receiver and the network transmission delay. In this
paper, however, we only target minimizing the transmission
delay. According to [23], [24], a normal delay for the source
(receiver) to process the video data can be 70ms, and such a
processing delay can be reduced to 35ms for devices with
advanced low-latency technology, e.g. the Sensoray Model
2253 audio/video codec [24].

10

TABLE V: Average empirical maximum delay improvement
(%) comparing the optimal solution of Min-Max-Delay which
can be obtained by our MMD (Algorithm 1) to each of the
baselines in non-trivial problem instances with relatively large
flow rate requirement.
Source
Receiver
Flow rate
Max-delay
imprv. (%)

ISP
ILR
SO

Case 1
OR
TO
[422, 442]
13
11
13

Case 2
VA
IR
[305, 317]
11
6
11

Case 3
VA
SI
[296, 317]
8
8
0

Case 4
IR
SI
[296, 319]
7
8
0

We reasonably assume a 35ms processing delay both for
source and receiver, and hence the transmission delay upper
bound to guarantee an acceptable video-conferencing service
will be 330ms. In any simulation instance, the optimal maximum delay performance which can be obtained by MMD is
always below the 330ms budget, while the maximum delay
achieved by any baseline algorithm violates the 330ms upper
bound and hence fail to provide an acceptable video conferencing in multiple instances with detailed results of failure in
percentage provided in Tab. IV. As shown in the table, baseline
algorithms fail to satisfy the 330ms video-conferencing delay
budget for up to 15% of simulation instances between certain
source-receiver pair (the maximum failure in percentage of
baselines are 7%, 2%, 0% and 15% respectively for the 4
experimental cases). Besides, the baseline ISP (resp. ILR and
SO) fails for up to 9% (resp. 15% and 7%) of all simulation
instances in order to route the video-conferencing traffic within
acceptable delay budget from certain source to certain receiver.
In our simulations, for trivial problem instances with
small/media rate requirement, all algorithms have the same
and optimal maximum delay performance since only two or
three paths will be used. We provide the detailed maximum
delay and running time results for non-trivial problem instances with relatively large flow rate requirement in Fig. 3,
where clearly any of the three baselines fail to solve our
problem optimally in certain instances. In Tab. V, we give
the average maximum delay improvement, namely the average
of (D(f ) − D(fMM ))/D(f ), comparing fMM which is the
optimal to our problem Min-Max-Delay and is the solution
of our MMD, to the flow f which is the solution of individual
baselines, in those non-trivial problem instances.
The running time results are also presented in Fig. 3.
According to the figure, the running time of SO and ISP
is so small that can be ignored, compared with the results of
MMD and ILR. Although our MMD, which can always find
the optimal solution, consumes more time than SO and ISP,
it in fact runs pretty fast in our experiments (less than 0.5
second) for all simulation instances.
C. Experiments of our FPTAS
For our problem Min-Max-Delay, because the exact algorithm (Algorithm 1) has an pseudo-polynomial time complexity theoretically, in Sec. V-B, we develop an FPTAS
(Algorithm 3) which can guarantee a (1 + )-approximate
solution within fully polynomial time. In this section, we

evaluate the performance of our FPTAS for traffic from
Oregon to Tokyo (case 1 in Tab. V) and for traffic from North
Virginia to Singapore (case 3 in Tab. V). In both cases, the
approximation parameter  is increased from 0 to 3 with a step
of 0.1, and we obtain the maximum delay and running time
results of the FPTAS for problem instances with different flow
rate requirements, as shown in Fig. 4.
According to the figure, in both experimental cases either
from Oregon to Tokyo or from North Virginia to Singapore,
obviously larger flow rate requirement results in a solution
flow with larger optimal maximum delay. Although theoretically the maximum delay performance of the FPTAS is only
upper bounded by a ratio of (1 + ) compared to the optimal
solution, empirically our FPTAS is able to achieve the optimal
maximum delay in all experimental cases for any  ∈ (0, 3]
(the maximum delay result remains to be a constant with
 as shown in the figure). According to the running time
results, clearly smaller rate requirement and larger  lead to
better running time results, particularly true for  < 0.5 when
theoretically our FPTAS always gives a feasible flow with
the maximum delay no worse than 1.5 × OPT where OPT
denotes the optimal maximum delay performance of our MinMax-Delay problem instance.
VII. R ELATED WORK
The maximum latency problem models link delay as a
function with the link aggregated flow rate. Since our MinMax-Delay problem which is characterized by an integer link
delay within finite link capacity can be viewed as a special
case of the maximum latency problem, existing algorithms
for the maximum latency problem can be applied to solve
our problem by assuming the delay function to be an integer
within capacity and go to infinity otherwise. Although most
existing algorithms can solve the maximum latency problem
efficiently, compared to the optimal delay performance, none
of them can achieve theoretically upper bounded maximum
delay for our Min-Max-Delay problem.
Correa et al. in [11], [12] prove the maximum latency
problem is NP-hard, in particular APX-hard, and propose that
compared to the optimal maximum delay, a tight maximum
delay gap of the well-known system-optimal flow is γ(L)
and a tight maximum delay gap of the Nash equilibrium
flow is α(L). Both γ(L) and α(L) are constants that rely on
the link delay function. However, for the link delay model
in our Min-Max-Delay problem, both γ(L) and α(L) are
infinitely large, implying neither the system-optimal flow nor
the Nash equilibrium flow can guarantee a maximum delay
within a finite-ratio gap to the optimal solution to our problem Min-Max-Delay. Roughgarden [13] shows that the Nash
equilibrium also admits a maximum delay no worse than a
network-dependent ratio of (|V |−1) for the maximum latency
problem. Obviously the gap (|V | − 1) is too large for practical
applications. Devetak et al. [22] have introduced fast heuristic
algorithms to optimize maximum delay, but the maximum
delay performance of returned solutions has no performance
guarantee compared to the optimal solution, theoretically.
To our best knowledge, [5] is the only existing study targeting the maximum delay optimization scenario with constant

11

Fig. 3: Running time and achieved maximum delay results of problem instances with large flow rate requirement for 4
experimental cases, comparing our pseudo-polynomial time algorithm (MMD) to three baselines.

Fig. 4: Running time and achieved maximum delay results of our FPTAS for problem instances with different flow rate
requirements and approximation parameter .

link delay and finite link capacity involved. The heuristic
approach in [5] for minimizing the maximum delay has two
limitations: (i) the time complexity could be high because the
number of variables in the approach increases exponentially
in the network size, and (ii) there is not yet theoretical
performance guarantee of the achieved solution.
VIII. C ONCLUSION
We study a delay-critical information flow problem which
optimizes the maximum end-to-end cross-network delay in
the single-unicast scenario, denoted as the Min-Max-Delay
problem. Transmission over a link incurs an integer delay if
the rate is within the finite link capacity, and an unbounded

delay otherwise. Many practical applications, e.g. the routing
of video conferencing traffic over inter-datacenter networks,
can be formulated as such problems.
We prove Min-Max-Delay is NP-hard in the weak sense
and propose two algorithms: (i) an exact algorithm that can
find the optimal solution with a pseudo-polynomial time complexity of O((N 2 dmax )3.5 log(N 2 dmax ) log R), where N ,
max{|V |, |E|} describes the network size, R is the flow rate
requirement, and dmax is the maximum link delay, and (ii) an
FPTAS with a (1 + )-approximation ratio and a polynomial
time complexity of O((N M )3.5 log R log(N M )(L + log N ))
for any  > 0, where M = |E|(1 + 1/) + 1 and L is
the bit complexity for representing dmax . Our results reveal

12

fundamental differences between the Min-Max-Delay problem
and the maximum latency problem studied in the literature,
which is APX-hard and admits no PTAS unless P = NP.
Moreover, there has not yet been exact pseudo-polynomialtime algorithm or constant-approximate algorithm for the
maximum latency problem.
We demonstrate the effectiveness of our algorithms in the
scenario of delay-critical inter-datacenter video-conferencing
traffic routing over multiple paths, using simulations based
on the Amazon EC2 inter-datacenter topology. Both of our
algorithms achieve the optimal maximum delay performance
in all simulation instances, and they always meet the endto-end delay requirement for video conferencing applications.
On the contrary, the state-of-the-art solutions only obtain suboptimal maximum delay performance in certain instances, and
fail to satisfy the video-conferencing delay requirement for
up to 15% of simulation instances between certain crosscontinental source-receiver pair.
R EFERENCES
[1] Q. Liu, L. Deng, H. Zeng, and M. Chen, “On the min-max-delay
problem: Np-completeness, algorithm, and integrality gap,” in IEEE
Information Theory Workshop, 2017.
[2] WIKI. Polynomial time approximation scheme. [Online]. Available:
https://en.wikipedia.org/wiki/Polynomial-time approximation scheme
[3] C.-Y. Hong, S. Kandula, R. Mahajan, M. Zhang, V. Gill, M. Nanduri,
and R. Wattenhofer, “Achieving high utilization with software-driven
wan,” in ACM SIGCOMM Computer Communication Review, vol. 43,
no. 4. ACM, 2013, pp. 15–26.
[4] S. Jain, A. Kumar, S. Mandal, J. Ong, L. Poutievski, A. Singh,
S. Venkata, J. Wanderer, J. Zhou, M. Zhu et al., “B4: Experience with
a globally-deployed software defined wan,” ACM SIGCOMM Computer
Communication Review, vol. 43, no. 4, pp. 3–14, 2013.
[5] Y. Liu, D. Niu, and B. Li, “Delay-optimized video traffic routing
in software-defined interdatacenter networks,” IEEE Transactions on
Multimedia, vol. 18, no. 5, pp. 865–878, 2016.
[6] M. H. Hajiesmaili, L. T. Mak, Z. Wang, C. Wu, M. Chen, and
A. Khonsari, “Cost-effective low-delay design for multi-party cloud
video conferencing,” IEEE Transactions on Multimedia, 2017.
[7] WebEx. [Online]. Available: https://blog.webex.com/2016/01/fivereasons-to-join-a-webex-now/
[8] Skype. [Online]. Available: https://news.microsoft.com/bythenumbers/
skype-calls
[9] Cisco. [Online]. Available: http://www.cisco.com/c/dam/en/us/solutions/
collateral/collaboration/midsize-collaboration-solutions/high-growthinnovative-companies.pdf
[10] ITU, “Series g: Transmission systems and media, digital systems and
networks,” 2003.
[11] J. Correa, A. Schulz, and N. Moses, “Computational complexity, fairness, and the price of anarchy of the maximum latency problem,” in Inter.
Conf. Integer Programming and Combinatorial Optimization, 2004.
[12] J. Correa, A. Schulz, and N. Stier-Moses, “Fast, fair, and efficient flows
in networks,” Operations Research, vol. 55, no. 2, pp. 215–225, 2007.
[13] T. Roughgarden, “The maximum latency of selfish routing,” CORNELL
UNIV ITHACA NY DEPT OF COMPUTER SCIENCE, Tech. Rep.,
2004.
[14] M. R. Garey and D. S. Johnson, ““strong” np-completeness results:
motivation, examples, and implications,” Journal of the ACM, vol. 25,
no. 3, pp. 499–508, 1978.
[15] C.-C. Wang and M. Chen, “Sending perishable information: Coding
improves delay-constrained throughput even for single unicast,” in IEEE
International Symposium on Information Theory, 2014.
[16] P. M. Vaidya, “Speeding-up linear programming using fast matrix
multiplication,” in IEEE Symp. Foundations of Computer Science, 1989.
[17] Y. Lee and A. Sidford, “Path finding
methods for linear programming:
√
Solving linear programs in Õ( rank) iterations and faster algorithms
for maximum flow,” in Symp. Foundations of Computer Science, 2014.
[18] L. Ford and D. Fulkerson, “Constructing maximal dynamic flows from
static flows,” Operations Research, vol. 6, no. 3, pp. 419–433, 1958.

[19] B. Grimmer and S. Kapoor, “Nash equilibrium and the price of anarchy
in priority based network routing,” in Computer Communications, IEEE
INFOCOM 2016-The 35th Annual IEEE International Conference on.
IEEE, 2016, pp. 1–9.
[20] E. W. Dijkstra, “A note on two problems in connexion with graphs,”
Numerische mathematik, vol. 1, no. 1, pp. 269–271, 1959.
[21] IBM, “Cplex optimizer,” 2017. [Online]. Available: https://www01.ibm.com/software/commerce/optimization/cplex-optimizer/
[22] F. Devetak, J. Shin, T. Anjali, and S. Kapoor, “Minimizing path delay
in multipath networks,” in IEEE Conf. Communications, 2011.
[23] P. Eberlein. Understanding video latency: what is video
latency
and
why
do
we
care
about
it?
[Online]. Available: http://www.vision-systems.com/content/dam/VSD/
solutionsinvision/Resources/Sensoray video-latency article FINAL.pdf
[24] I. Sensoray Company. Usb audio/video codec model 2253 hardware
manual. [Online]. Available: http://www.sensoray.com/downloads/man
2253 hw 1.2.1.pdf

