Editing Routing (section)

==Multiple agents==
In some networks, routing is complicated by the fact that no single entity is responsible for selecting paths; instead, multiple entities are involved in selecting paths or even parts of a single path. Complications or inefficiency can result if these entities choose paths to optimize their own objectives, which may conflict with the objectives of other participants.

A classic example involves traffic in a road system, in which each driver picks a path that minimizes their travel time. With such routing, the [[Nash equilibrium|equilibrium]] routes can be longer than optimal for all drivers. In particular, [[Braess's paradox]] shows that adding a new road can ''lengthen'' travel times for all drivers.

In a single-agent model used, for example, for routing [[automated guided vehicle]]s (AGVs) on a terminal, reservations are made for each vehicle to prevent simultaneous use of the same part of an infrastructure. This approach is also referred to as context-aware routing.<ref>{{cite web |first1=Jonne |last1=Zutt |first2=Arjan J.C. |last2=van Gemund |first3=Mathijs M. |last3=de Weerdt |first4=Cees |last4=Witteveen |date=2010 |url=http://www.st.ewi.tudelft.nl/~mathijs/publications/intinfra09.pdf |title=Dealing with Uncertainty in Operational Transport Planning |url-status=dead |archive-url=https://web.archive.org/web/20170922001342/http://www.st.ewi.tudelft.nl/~mathijs/publications/intinfra09.pdf |archive-date= Sep 22, 2017 }} In R.R. Negenborn and Z. Lukszo and H. Hellendoorn (Eds.) Intelligent Infrastructures, Ch. 14, pp. 355–382. Springer.</ref> 

The Internet is partitioned into [[autonomous system (Internet)|autonomous systems]] (ASs) such as [[internet service provider]]s (ISPs), each of which controls routes involving its network. Routing occurs at multiple levels. First, AS-level paths are selected via the [[BGP]] protocol that produces a sequence of ASs through which packets flow. Each AS may have multiple paths, offered by neighboring ASs, from which to choose. These routing decisions often correlate with business relationships with these neighboring ASs,<ref>Matthew Caesar and [[Jennifer Rexford]]. "[http://www.cs.princeton.edu/~jrex/papers/policies.pdf BGP routing policies in ISP networks]". IEEE Network Magazine, special issue on Interdomain Routing, Nov/Dec 2005.</ref> which may be unrelated to path quality or latency. Second, once an AS-level path has been selected, there are often multiple corresponding router-level paths to choose from. This is due, in part, because two ISPs may be connected through multiple connections. In choosing the single router-level path, it is common practice for each ISP to employ [[hot-potato routing]]: sending traffic along the path that minimizes the distance through the ISP's own network—even if that path lengthens the total distance to the destination.

For example, consider two ISPs, ''A'' and ''B''. Each has a presence in [[New York City|New York]], connected by a fast link with latency {{val|5|ul=ms}}—and each has a presence in [[London]] connected by a 5&nbsp;ms link. Suppose both ISPs have trans-Atlantic links that connect their two networks, but ''A''<nowiki/>'s link has latency 100&nbsp;ms and ''B''<nowiki/>'s has latency 120&nbsp;ms. When routing a message from a source in ''A''<nowiki/>'s London network to a destination in ''B''<nowiki/>'s New York network, ''A'' may choose to immediately send the message to ''B'' in London. This saves ''A'' the work of sending it along an expensive trans-Atlantic link, but causes the message to experience latency 125&nbsp;ms when the other route would have been 20&nbsp;ms faster.

Additionally, a similar routing challenge can be observed in cellular networks, where different packets are destined for various endpoints, and each link exhibits varying spectral efficiency. In this context, the selection of the ''optimal'' path involves considering latency and packet error rate. To address this, multiple independent entities, one for each base station, play a crucial role in path selection while striving to optimize overall network performance.<ref>Shahaf Yamin and Haim H. Permuter. "[https://www.sciencedirect.com/science/article/pii/S1570870523002676 Multi-agent reinforcement learning for network routing in integrated access backhaul networks]". ''Ad Hoc Networks'', Volume 153, 2024, 103347, {{ISSN|1570-8705}}, {{doi|10.1016/j.adhoc.2023.103347}}.</ref>

A 2003 measurement study of Internet routes found that, between pairs of neighboring ISPs, more than 30% of paths have inflated latency due to hot-potato routing, with 5% of paths being delayed by at least 12&nbsp;ms. Inflation due to AS-level path selection, while substantial, was attributed primarily to BGP's lack of a mechanism to directly optimize for latency, rather than to selfish routing policies. It was also suggested that, were an appropriate mechanism in place, ISPs would be willing to cooperate to reduce latency rather than use hot-potato routing.<ref>Neil Spring, Ratul Mahajan, and Thomas Anderson. "[http://www.cs.washington.edu/research/networking/rocketfuel/papers/sigcomm2003.pdf Quantifying the Causes of Path Inflation]". Proc. [[SIGCOMM]] 2003.</ref> Such a mechanism was later published by the same authors, first for the case of two ISPs<ref>Ratul Mahajan, David Wetherall, and Thomas Anderson. "[http://research.microsoft.com/en-us/um/people/ratul/papers/nsdi2005-nexit.pdf Negotiation-Based Routing Between Neighboring ISPs]". Proc. [[NSDI]] 2005.</ref> and then for the global case.<ref>Ratul Mahajan, David Wetherall, and Thomas Anderson. [http://research.microsoft.com/en-us/um/people/ratul/papers/nsdi2007-wiser.pdf Mutually Controlled Routing with Independent ISPs]. Proc. [[NSDI]] 2007.</ref>