Pith. sign in

REVIEW 4 major objections 3 minor 18 references

Optimizing Inter-Datacenter Tail Flow Completion Times using Best Worst-case Routing

T0 review · 4 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Routing each incoming flow along the path that minimizes the sum of remaining work plus new volume, divided by capacity, cuts mean and tail completion times of inter-datacenter flows by over 1.5x and 2x.

desk verdict A clean, useful simplification (edge-decomposable bound plus Dijkstra) with a plausible but underspecified empirical claim that depends on exact flow-size information. read the letter →

arxiv 1908.09070 v1 pith:7MZM7QXS submitted 2019-08-24 cs.NI cs.PFcs.SYeess.SY

Max Noormohammadpour , Ajitesh Srivastava , Cauligi S. Raghavendra This is my paper · ORCID
classification cs.NIcs.PFcs.SYeess.SY
keywords flowroutingcompletiontimetaillatencyinter-datacenternetworkssoftware-definednetworkingworst-caseboundsizeinformationshortestpath
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper argues that inter-datacenter routing should exploit what the operator already knows: the size of each arriving flow and the unfinished volume of every flow already in the network. It defines Best Worst-case Routing (BWR), which chooses the path that minimizes the new flow's worst-case completion time, and builds on an earlier result that this choice is NP-hard. The practical contribution is BWRHF, a polynomial-time heuristic that assigns each link the weight "unfinished work on the link plus the new flow's volume, divided by capacity" and routes on the minimum-weight path with a standard shortest-path search. In simulations over five real WAN topologies, three traffic distributions, and three scheduling policies, BWRHF reduces mean flow completion times by over 1.5x and tail completion times by over 2x relative to three standard routing heuristics, while staying within 15% of the much slower BWRH. If the result holds, a controller that already knows flow sizes can obtain large tail-latency gains with a simple routing rule and no change to scheduling.

What carries the argument

The carrying object is the per-edge cost of Eq. 3, $$W(e)=\frac{\sum_{F_i\in\mathcal{F}_e} V_i^r + V_{N+1}}{C_e},$$ the sum of the remaining volumes of all flows on edge $e$ plus the new flow's volume, divided by that edge's capacity. Because of the reciprocal-of-minimum inequality $\frac{1}{\min(x_1,\ldots,x_n)} \le \frac{1}{x_1}+\cdots+\frac{1}{x_n}$, the path-wide worst-case bound of Eq. 1, which must account for which edges a path shares with each ongoing flow, relaxes to a sum of independent per-edge terms, converting path selection into a minimum-weight path problem solvable by Dijkstra's algorithm in guaranteed polynomial time. The slower BWRH search, which uses the tighter shared-bottleneck bound with hop-limited exhaustive enumeration, plays the role of a quality reference: it shows the cheap decomposable bound sacrifices at most 15%. The appendix explains why an exact worst-case value would require building a dependency graph of ongoing flows and identifying which flows can transmit in parallel, which is too expensive to repeat per candidate path.

What would settle it

Re-run the paper's simulations over the same five topologies, three traffic distributions, and three scheduling policies, but feed the controller remaining-volume estimates corrupted by multiplicative noise of increasing magnitude, for example log-normal errors of 10%, 25%, and 50%. The claim predicts the 1.5x-2x advantage over Inverse Capacity Shortest Path degrades only gradually as the noise grows; if a small error level erases the advantage on realistic workloads, then size-accuracy is the load-bearing assumption and the practical claim fails.

Watch

Extended reading notes

Core claim

The central claim is that the exact, NP-hard objective of finding the path with the best worst-case completion time for an arriving flow can be replaced by an additive edge-weight rule, and that the replacement costs almost nothing in completion-time quality. The rule sets each edge's cost to the total unfinished volume of flows already using that edge plus the new flow's volume, divided by the edge's capacity, and routes on the minimum-cost path. The mathematical step that makes this work is the inequality $1/\min(x_1,\ldots,x_n) \le 1/x_1 + \cdots + 1/x_n$, which turns a path-wide bound that depends on shared bottleneck segments into a sum of independent per-edge terms, so that any standard shortest-path algorithm applies. The paper shows that this fast heuristic stays within 15% of BWRH, the tighter but exponentially slow hop-limited search, on mean and tail completion times across every topology tested; runs in milliseconds in the worst case rather than tens of seconds; and beats Inverse Capacity Shortest Path, Min-Max Utilization, and Shortest Widest Path by over 1.5x in mean and over 2x in tail flow completion time.

Load-bearing premise

The load-bearing premise is that the network controller knows the exact remaining volume of every ongoing flow and the exact size of each arriving flow at routing time, and that flows are large enough for propagation and queuing delays to be negligible; if the size information is noisy, the edge weights are wrong and the reported gains may shrink or vanish, which the paper itself flags as future work.

Editorial extensions

If this is right

  • An operator that already knows flow sizes can deploy BWRHF with an off-the-shelf shortest-path routine; no new scheduler, queueing policy, or network-wide optimizer is required, and the per-flow decision takes milliseconds in the worst case.
  • Mean and tail flow completion times improve by over 1.5x and 2x respectively compared with Inverse Capacity Shortest Path, Min-Max Utilization, and Shortest Widest Path, with per-scenario tail gains between roughly 1.1x and 2.2x across the tested topologies, traffic patterns, and scheduling policies.
  • The gains hold under FCFS, SRPT, and fair sharing because the worst-case bound being minimized is independent of the scheduling policy, so operators need not change their congestion-control or scheduling layer.
  • The faster heuristic is nearly as good as the expensive one: BWRHF and BWRH differ by less than 15% on mean and tail completion times on every topology tested, making the cheap per-edge bound the practical choice.
  • Because the edge weights are additive, the rule can be rerun quickly after link failures or capacity changes, which an online routing algorithm for a dynamic WAN requires.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural stress test the paper leaves open: feeding the controller noisy remaining-volume estimates (say, log-normal errors of 10-50%) should produce a degradation curve for the 1.5x-2x gains, and heavy-tailed traffic is the sharpest test because a few large flows dominate the edge sums.
  • The same per-edge marginal cost transfers to the multipath setting the authors list as future work: splitting the new flow across paths so that the marginal costs balance would generalize BWRHF from path selection to flow splitting.
  • Because the bound is additive over edges, it can be computed from link-state information that any node could flood; the rule would therefore also work in a distributed link-state routing regime, not only under a logically centralized controller.
  • Combining the worst-case bound with per-flow deadlines could yield a greedy admission rule for deadline-constrained WAN transfers, although the paper does not claim any deadline guarantees.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 3 minor

Summary. The paper addresses online path selection for long inter-datacenter flows, with the goal of minimizing flow completion times (FCTs), especially their tail. Because exact worst-case routing is NP-hard, the authors propose two heuristics: BWRH, which searches paths using a per-flow upper bound on worst-case completion time, and BWRHF, which uses an edge-decomposable upper bound and runs in polynomial time via standard shortest-path algorithms. The paper evaluates both heuristics against inverse-capacity shortest path, min-max utilization, and shortest widest path on five real WAN topologies with light-tailed, heavy-tailed, and Facebook cache-follower traffic under FCFS, SRPT, and fair-sharing scheduling. The headline claim is that BWRHF reduces mean FCT by over 1.5x and tail FCT by over 2x relative to the baselines, while performing essentially as well as the slower BWRH.

Significance. If the quantitative claims are confirmed, this is a practically useful contribution: BWRHF is a simple, polynomial-time, online routing rule that exploits flow-size information available in centralized inter-datacenter WAN controllers, and it can be implemented with a standard Dijkstra computation. The evaluation is broad in topology coverage and scheduling policies, and the paper gives credit for the NP-hardness result to prior work. The derivation of the edge weights is transparent, and a C++ implementation of part of the system is linked. However, the empirical headline depends on simulation details that are not fully pinned down, and the central mechanism relies on an information-accuracy assumption whose sensitivity is explicitly deferred to future work.

major comments (4)
  1. [Section VII, Figures 2 and 3, Abstract] The metric called 'tail flow completion time' is never defined. It is not stated whether 'tail' means the 99th percentile, 95th percentile, maximum, or some other statistic, nor is it explained how the tail is computed across the repeated simulation runs (per-run tail then averaged, or pooled tail across runs). Because the abstract's 'over 2x' tail improvement and the Section VII.B ranges such as '1.4x to 2.2x' depend on this definition, the central quantitative claim is not reproducible as written. Please define the tail estimator precisely and state the aggregation method.
  2. [Section VII, Figure 3 caption] The evaluation protocol is insufficient to reconstruct the reported ratios. The cache-follower distribution is described only as 'inferred from the CDF curves reported in [11]' with no empirical CDF or fitted parameters provided, so this traffic pattern cannot be regenerated from the paper. In addition, the paper does not report the offered load or link utilization in the simulated scenarios; with λ=1, μ=50, 500 arrivals, and link capacities drawn uniformly from 0.2 to 1, it is unclear whether the network is lightly loaded, heavily loaded, or saturated, and the FCT ratios can be strongly affected by this. Please state the load levels, the simulated time horizon, the number of replications used for tail estimation, and provide an actual specification of the inferred Facebook distribution.
  3. [Section II and Section VIII] The paper's own Section VIII lists 'a study of how potentially inaccurate flow size information can affect the performance' as future work, yet accurate remaining volumes and new-flow volumes are exactly what the BWRHF edge weight in Eq. (3) requires. All evaluations appear to use exact flow-size information, so the reported 1.5x/2x gains are measured under the most favorable information assumption. Since this is the mechanism that gives BWRHF its advantage over load- and capacity-based heuristics, the sensitivity of the results to noisy or stale flow-size estimates is load-bearing. Please either add a robustness study with realistic estimation error or explicitly qualify the abstract and conclusion claims as conditional on exact flow-size information.
  4. [Section IV, Eq. (1) and Section V, Eq. (3)] The quantity in Eq. (1) is presented as an upper bound on the worst-case completion time, but under the general system model of Section II it is not always an upper bound. If a current flow shares an edge with candidate path P but has a lower-capacity edge elsewhere on its own path, that lower-capacity edge limits the rate at which the current flow can drain the shared edge; the time until the shared edge is available to the new flow can then exceed V_i^r divided by the minimum capacity of the shared edges. The assumption stated in Section IV that each current flow's bottleneck is the minimum-capacity shared edge is an extra restriction that is not part of the Section II model. The same issue propagates to Eq. (3). Please prove the bound under the stated model or state the restriction explicitly and explain how the evaluation scenarios satisfy it; otherwise, replace the 'upper bound' terminology with a clearly labeled approximation.
minor comments (3)
  1. [Section VII.C] The text says 'In Figure 3(b), we study the effect of various scheduling policies,' but Figure 3(b) varies network topology under the fair-sharing policy; this should read 'effect of network topologies.'
  2. [Figure 2] The subplot labels '=20' and '=50' in Figure 2(a) are not explained in the caption or text; these presumably correspond to λ=20 and λ=50, but this should be stated explicitly.
  3. [Abstract and Section I] The phrase 'while BWRHF being significantly faster' is ungrammatical; it should be 'while BWRHF is significantly faster.'

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the BWRHF edge-weight bound is derived from stated worst-case assumptions, and its gains are measured by simulation rather than fitted or implied by the bound itself.

full rationale

The paper's central derivation is self-contained. BWR defines an exact worst-case completion time; Eq. (1) gives a conservative upper bound by assuming conflicting flows complete sequentially; and Eq. (3) relaxes that bound via 1/min(x_i) <= sum 1/x_i to make it edge-decomposable. BWRHF then runs Dijkstra over these weights. Nothing in this chain is defined in terms of the simulation outcome; the simulator independently computes completion times under FCFS, SRPT, and max-min fair sharing using randomly generated capacities and external flow-size distributions (exponential, Pareto, and Facebook cache-follower). No parameter is fitted to the reported 1.5x/2x mean/tail improvements, so the gains are not forced by construction. The only self-citation, [5], supplies the NP-hardness of exact BWR used to motivate heuristics; it is an external published result and not an input to the simulations. The paper's own Section VIII defers 'a study of how potentially inaccurate flow size information can affect the performance' to future work; that is a genuine assumption/limitation about input accuracy, not circular reasoning. Overall, no circular step meeting the quoted-reduction standard was found.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The central claims rest on simulation parameters (arrival rate, flow size distributions, link capacity draws) and on modeling assumptions about worst-case scheduling and flow-size visibility. No free parameters are fitted to the target result; the derivation is analytic from stated assumptions.

free parameters (5)
  • Poisson arrival rate lambda = 1
    Simulation input controlling the load; chosen by the authors, not fitted to the target result.
  • Average flow size mu = 20 and 50 units
    Chosen to represent long flows; the main evaluation uses mu=50 (Figure 3 caption).
  • Link capacity range = Uniform(0.2, 1) per direction
    Random per-instance capacities to model non-uniform networks; chosen by the authors.
  • Number of flow arrivals per simulation run = 500
    Simulation horizon chosen by the authors.
  • Number of simulation runs per scenario = 10 (Fig. 2) and 20 (Fig. 3)
    Repeat count for averaging; 20 runs in the main comparison.
assumptions (5)
  • domain assumption BWR (finding the path minimizing worst-case FCT) is NP-Hard, as proved in prior work [5].
    Stated in Section I: 'Since BWR is NP-Hard [5]' and used to justify the heuristics; the proof is not reproduced here.
  • domain assumption Accurate remaining flow size information is available for all ongoing flows and the new flow at arrival.
    Assumed in Section II and required for the edge weights in Eq. 3; the paper notes in future work that inaccurate information could affect performance.
  • domain assumption Long flows are large enough that queuing and propagation latency are negligible.
    Section II: 'by aiming at sufficiently large flows, the queuing and propagation latency can be negligible and so can be omitted'.
  • ad hoc to paper The worst-case completion time bound assumes that all current flows sharing an edge with the candidate path complete sequentially before the new flow, each bottlenecked at the minimum shared capacity.
    This modeling assumption underlies Eq. 1 and hence the entire BWRH/BWRHF objective.
  • standard math The inequality 1/min(x1,...,xn) <= 1/x1 + ... + 1/xn for positive xi.
    Used as Eq. 2 to derive the edge-decomposable bound in Eq. 3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimizing Inter-Datacenter Tail Flow Completion Times using Best Worst-case Routing." pith.science (2026). https://pith.science/paper/7MZM7QXS

@misc{pith2026190809070,
  author       = {Pith},
  title        = {Pith review of: Optimizing Inter-Datacenter Tail Flow Completion Times using Best Worst-case Routing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7MZM7QXS}},
  note         = {Machine review of arXiv:1908.09070}
}
abstract

Flow routing over inter-datacenter networks is a well-known problem where the network assigns a path to a newly arriving flow potentially according to the network conditions and the properties of the new flow. An essential system-wide performance metric for a routing algorithm is the flow completion times, which affect the performance of applications running across multiple datacenters. Current static and dynamic routing approaches do not take advantage of flow size information in routing, which is practical in a controlled environment such as inter-datacenter networks that are managed by the datacenter operators. In this paper, we discuss Best Worst-case Routing (BWR), which aims at optimizing the tail completion times of long-running flows over inter-datacenter networks with non-uniform link capacities. Since finding the path with the best worst-case completion time for a new flow is NP-Hard, we investigate two heuristics, BWRH and BWRHF, which use two different upper bounds on the worst-case completion times for routing. We evaluate BWRH and BWRHF against several real WAN topologies and multiple traffic patterns. Although BWRH better models the BWR problem, BWRH and BWRHF show negligible difference across various system-wide performance metrics, while BWRHF being significantly faster. Furthermore, we show that compared to other popular routing heuristics, BWRHF can reduce the mean and tail flow completion times by over $1.5\times$ and $2\times$, respectively.

Figures

Figures reproduced from arXiv: 1908.09070 by the authors.

Figure 1
Figure 1. Example used to demonstrate the two upper bounds for [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Comparison of flow completion times and running time for the two heuristics of [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Flow completion times reported for 500 flow arrivals given [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: A simple scenario with a link capacity of 1.0 for all edges. [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [11]

    Inside the Social Network’s (Datacenter) Network,

    A. Roy, H. Zeng et al. , “Inside the Social Network’s (Datacenter) Network,” SIGCOMM, pp. 123–137, 2015

    work page 2015

  2. [1]

    B4: Experience with a globally-deployed software defined wan,

    S. Jain, A. Kumar et al. , “B4: Experience with a globally-deployed software defined wan,” SIGCOMM, vol. 43, no. 4, pp. 3–14, 2013

    work page 2013

  3. [2]

    B4 and after: Managing hierarchy, parti- tioning, and asymmetry for availability and scale in google’s software- defined wan,

    C.-Y . Hong, S. Mandal et al., “B4 and after: Managing hierarchy, parti- tioning, and asymmetry for availability and scale in google’s software- defined wan,” in SIGCOMM, 2018, pp. 74–87

    work page 2018

  4. [3]

    https://code.facebook.com/posts/1782709872057497/building-express- backbone-facebook-s-new-long-haul-network/

    work page arXiv

  5. [4]

    https://azure.microsoft.com/en-us/blog/how-microsoft-builds-its-fast- and-reliable-global-network/

    work page

  6. [5]

    On minimizing the completion times of long flows over inter-datacenter wan,

    M. Noormohammadpour, A. Srivastava, and C. S. Raghavendra, “On minimizing the completion times of long flows over inter-datacenter wan,” IEEE Communications Letters , vol. 22, no. 12, pp. 2475–2478, Dec 2018

    work page 2018

  7. [6]

    Online multicast routing with bandwidth guarantees: a new approach using multicast network flow,

    M. Kodialam, T. V . Lakshman, and S. Sengupta, “Online multicast routing with bandwidth guarantees: a new approach using multicast network flow,” IEEE/ACM Transactions on Networking , vol. 11, no. 4, pp. 676–686, 2003

    work page 2003

  8. [7]

    http://www.omnisecu.com/cisco-certified-network-associate-ccna/what- is-routing-metric-value.php

    work page

Show all 18 references
  1. [8]

    Calendaring for wide area networks,

    S. Kandula, I. Menache et al. , “Calendaring for wide area networks,” SIGCOMM, vol. 44, no. 4, pp. 515–526, 2015

    2015

  2. [9]

    Guaranteeing deadlines for inter- datacenter transfers,

    H. Zhang, K. Chen, W. Bai et al. , “Guaranteeing deadlines for inter- datacenter transfers,” in EuroSys. ACM, 2015, p. 20

    2015

  3. [10]

    Optimizing bulk transfers with software-defined optical wan,

    X. Jin, Y . Li, D. Wei, S. Li, J. Gao, L. Xu, G. Li, W. Xu, and J. Rexford, “Optimizing bulk transfers with software-defined optical wan,” in SIGCOMM. ACM, 2016, pp. 87–100

    2016

  4. [12]

    Data networks,

    D. Bertsekas and R. Gallager, “Data networks,” 1987

    1987

  5. [13]

    Software-defined networking,

    N. McKeown, “Software-defined networking,” INFOCOM keynote talk , vol. 17, no. 2, pp. 30–32, 2009

    2009

  6. [14]

    Segment routing architecture,

    C. Filsfils, S. Previdi, L. Ginsberg, B. Decraene, S. Litkowski, and R. Shakir, “Segment routing architecture,” Internet Engineering Task Force (IETF), Tech. Rep., 2018

    2018

  7. [15]

    [Online]

    The Internet Topology Zoo (ATT North America). [Online]. Available: http://www.topology-zoo.org/files/AttMpls.gml

  8. [16]

    [Online]

    The Internet Topology Zoo (Cogent). [Online]. Available: http: //www.topology-zoo.org/files/Cogentco.gml

  9. [17]

    [Online]

    The Internet Topology Zoo (Agis). [Online]. Available: http://www. topology-zoo.org/files/Agis.gml

  10. [18]

    [Online]

    The Internet Topology Zoo (ANS). [Online]. Available: http://www. topology-zoo.org/files/Ans.gml f1 f2 f3 P SF DF f4 (a) Computing the worst-case completion time for candidate path P f1 f2 f3 f4 (b) Dependency graph of current flows Fig. 4. A simple scenario with a link capacity...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.