Online Flow Computation on Unit-Vertex-Capacitated Networks
Online Flow Computation on Unit-Vertex-Capacitated Networks
复制标题
单位顶点容量网络上的在线流计算
DOI：
10.1137/1.9781611976021.9
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Kleinberg, Robert
中科院分区：
文献类型：
--
作者：
Arsenis, Makis;Kleinberg, Robert
In many networking scenarios, long-lived flows can be rerouted to free up resources and accommodate new flows, but doing so comes at a cost in terms of disruption. An archetypical example is the transmission of live streams in a content delivery network: audio and video encoders (clients) generate live streams and connect to a server which rebroadcasts their stream to the rest of the network. Reconnecting a client to a different server mid-stream is very disruptive. We abstract these scenarios in the setting of a capacitated network where clients arrive one by one and request to send a unit of flow to a designated set of servers subject to edge/vertex capacity constraints. An online algorithm maintains a sequence of flows that route the clients present so far to the set of servers. The cost of a sequence of flows is defined as the net switching cost, i.e. total length of all augmenting paths used to transform each flow into its successor. We prove that for unit-vertex-capacitated networks, the algorithm that successively updates the flow using the shortest augmenting path from the new client to a free server incurs a total switching cost ofO(nlog2n), wherenis the number of vertices in the network. This result is obtained by reducing to the online bipartite matching problem studied in prior work and applying their result. Finally, we identify a slightly more general class of networks for which essentially the same reduction idea can be applied to get the same bound.
登录
查看更多内容
DOI：
--
发表时间：
2017
期刊：
Latin American Symposium on Theoretical Informatics
影响因子：
--
作者：
B. Bosek;Dariusz Leniowski;P. Sankowski;Anna Zych
通讯作者：
Anna Zych
DOI：
10.1145/3344999
发表时间：
2017-07
期刊：
Journal of the ACM (JACM)
影响因子：
--
作者：
A. Bernstein;J. Holm;E. Rotenberg
通讯作者：
A. Bernstein;J. Holm;E. Rotenberg
最优动态分布式MIS
DOI：
--
发表时间：
2015
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
K. Censor;Elad Haramaty;Zohar S. Karnin
通讯作者：
Zohar S. Karnin
响应时间的负载平衡
DOI：
--
发表时间：
1995
期刊：
J. Algorithms
影响因子：
--
作者：
J. Westbrook
通讯作者：
J. Westbrook
DOI：
--
发表时间：
2017
期刊：
arXiv.org
影响因子：
--
作者：
B. Bosek;Dariusz Leniowski;Anna Zych;P. Sankowski
通讯作者：
P. Sankowski