Partially optimal routing
Partially optimal routing
复制标题
DOI：
10.1109/jsac.2007.070809
复制
发表时间：
2007-08-01
影响因子：
16.4
通讯作者：
Ozdaglar, Asuman
中科院分区：
文献类型：
--
作者：
Acemoglu, Daron;Johari, Ramesh;Ozdaglar, Asuman
大多数大规模的通信网络，如互联网，由相互连接的管理域组成。虽然源（或自私）路由，其中传输遵循每个源的最低成本路径，是合理的跨域，服务提供商通常从事流量工程，以提高自己的网络内的操作性能。出于这一观察，我们开发和分析了一个模型的部分最优路由，在子网内的最优路由覆盖与自私的跨域路由。我们证明，在一个子网内的最佳路由并不一定提高整个网络的性能。特别地，当网络中出现Braess' paradox时，部分最优路由可能导致更差的整体网络性能。我们提供了由于部分最优路由而可能发生的最坏情况下效率损失的界限。例如，当所有拥塞成本可以由仿射延迟函数表示并且所有管理域都具有单个入口和出口点时，相对于最优解，最坏情况下的效率损失不差于25%。然而，在存在包含多个入口和/或出口点的管理域的情况下，即使使用线性延迟，部分最优路由的性能也可能是任意低效的。我们还为流量工程提供条件，使其成为服务提供商的最佳选择。
Most large-scale communication networks, such as the Internet, consist of interconnected administrative domains. While source (or selfish) routing, where transmission follows the least cost path for each source, is reasonable across domains, service providers typically engage in traffic engineering to improve operating performance within their own network. Motivated by this observation, we develop and analyze a model of partially optimal routing, where optimal routing within subnetworks is overlaid with selfish routing across domains. We demonstrate that optimal routing within a subnetwork does not necessarily improve the performance of the overall network. In particular, when Braess' paradox occurs in the network, partially optimal routing may lead to worse overall network performance. We provide bounds on the worst-case loss of efficiency that can occur due,to partially optimal routing. For example, when all congestion costs can be represented by affine latency functions and all administrative domains have a single entry and exit point, the worst-case loss of efficiency is no worse than 25% relative to the optimal solution. In the presence of administrative domains incorporating multiple entry and/or exit points, however, the performance of partially optimal routing can be arbitrarily inefficient even with linear latencies. We also provide conditions for traffic engineering to be individually optimal for service providers.