In an Ideal Shortest Path Algorithm (ISPA), at each moment each router in a network sends all of its traffic down the path that will incur the lowest cost to that traffic. In the limit of an infinitesimally small amount of traffic for a particular router, its routing that traffic via an ISPA is optimal, as far as cost incurred by that traffic is concerned. We demonstrate though that in many cases, due to the side-effects of one router's actions on another routers performance, having routers use ISPA's is suboptimal as far as global aggregate cost is concerned, even when only used to route infinitesimally small amounts of traffic. As a particular example of this we present an instance of Braess' paradox for ISPA's, in which adding new links to a network decreases overall throughput. We also demonstrate that load-balancing, in which the routing decisions are made to optimize the global cost incurred by all traffic currently being routed, is suboptimal as far as global cost averaged across time is concerned. This is also due to "side-effects", in this case of current routing decision on future traffic. The theory of COllective INtelligence (COIN) is concerned precisely with the issue of avoiding such deleterious side-effects. We present key concepts from that theory and use them to derive an idealized algorithm whose performance is better than that of the ISPA, even in the infinitesimal limit. We present experiments verifying this, and also showing that a machine-learning-based version of this COIN algorithm in which costs are only imprecisely estimated (a version potentially applicable in the real world) also outperforms the ISPA, despite having access to less information than does the ISPA. In particular, this COIN algorithm avoids Braess' paradox.
翻译:在一个网络中,每个路由器在每时每刻都会将其所有交通量都发送到一个交通量最低的路径上。在特定路由器的交通量极小的限度下,它通过一个路由器的交通量是最佳的,就交通量引起的成本而言,通过一个路由器的交通量是最佳的。虽然我们表明,在许多情况中,由于一个路由器在另一个路由器的性能上的行动的副作用,就全球总成本而言,路由器使用IPSA的交通量并不最理想,即使只是用于极小的交通量。我们举一个例子,我们展示了Braess'的反常现象,其中将新的网络连接降低总体的流量。我们还表明,在很多情况下,由于路由器的运行量决定是优化当前路由所有交通量产生的全球成本,从全球平均成本来看,也是最不理想的,这还由于“正向路由器”的运行量,因此,我们现在的运行量也比现在的运行量要低一些。