Back to Search
Start Over
Optimizing Inter-Datacenter Tail Flow Completion Times using Best Worst-case Routing
- Source :
- Allerton
- Publication Year :
- 2019
- Publisher :
- arXiv, 2019.
-
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.<br />Comment: Accepted for publication in the 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)
- Subjects :
- Networking and Internet Architecture (cs.NI)
FOS: Computer and information sciences
Mathematical optimization
Computer Science - Performance
Computer science
020206 networking & telecommunications
02 engineering and technology
Systems and Control (eess.SY)
Network topology
Electrical Engineering and Systems Science - Systems and Control
Upper and lower bounds
Computer Science - Networking and Internet Architecture
Performance (cs.PF)
Flow (mathematics)
020204 information systems
Path (graph theory)
0202 electrical engineering, electronic engineering, information engineering
FOS: Electrical engineering, electronic engineering, information engineering
Routing (electronic design automation)
Heuristics
Performance metric
Flow routing
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- Allerton
- Accession number :
- edsair.doi.dedup.....c9c70554866fc6cc9a7ef24756db0b08
- Full Text :
- https://doi.org/10.48550/arxiv.1908.09070