A Tale of Two Metrics in Network Delay Optimization

We consider a single-unicast networking scenario where a sender streams a flow at a fixed rate to a receiver across a multi-hop network, possibly using multiple paths. Transmission over a link incurs a traffic-dependent link delay. We optimize network delay concerning two popular metrics, namely maximum delay and average delay. Well-known pessimistic results state that a flow cannot simultaneously achieve a maximum delay and an average delay both within bounded-ratio gaps to optimal. Instead, we pose an optimistic note on the fundamental compatibility of the two delay metrics. Specifically, we design two polynomial-time solutions each of which can deliver (1-ϵ) -fraction of the flow with maximum delay and average delay simultaneously within (1/ϵ) -ratio gap to optimal, for any ϵ ∈  (0,1). We prove that the ratio (1/ϵ) is at least near-tight. Moreover, our solutions can be extended to the multiple-unicast setting. In this setting, the two delay metrics of our solutions are both within a bounded-ratio gap of (R/(R_min· ϵ)) to optimal, where R (resp. R_min) is the aggregate (resp. minimum) flow rate requirement of all sender-receiver pairs. Hence we pose a similar optimistic note. Simulations based on real-world continent-scale network topology show that the empirical delay gaps observed under practical settings can be much smaller than their theoretical counterparts. In addition, our solutions can achieve over 10% reduction on the maximum delay and average delay simultaneously, only in the cost of losing 3% traffic, as compared to a conceivable delay-aware baseline without traffic loss. Our results can be of particular interest to delay-centric networking applications that can tolerate a small fraction of traffic loss, including cloud video conferencing that recently attracts substantial attention.