Editing Routing (section)

==Path selection==
Path selection involves applying a [[routing metric]] to multiple routes to select (or predict) the best route. Most routing algorithms use only one network path at a time. [[Multipath routing]] and specifically [[equal-cost multi-path routing]] techniques enable the use of multiple alternative paths.

In computer networking, the metric is computed by a routing algorithm, and can cover information such as [[Bandwidth (computing)|bandwidth]], [[network delay]], [[hop count]], path cost, load, [[maximum transmission unit]], reliability, and communication cost.<ref>{{citation |url=http://rainer.baumann.info/public/tik262.pdf |first1=Rainer |last1=Baumann |first2=Simon |last2=Heimlicher |first3=Mario |last3=Strasser |first4=Andreas |last4=Weibel |title=A Survey on Routing Metrics |date=February 10, 2007 |access-date=2020-05-04}}</ref> The routing table stores only the best possible routes, while [[link-state]] or topological databases may store all other information as well.

In case of overlapping or equal routes, algorithms consider the following elements in priority order to decide which routes to install into the routing table:
#''Prefix length'': A matching route table entry with a longer subnet mask is always preferred as it specifies the destination more exactly.
#''[[Metrics (networking)|Metric]]'': When comparing routes learned via the same routing protocol, a lower metric is preferred. Metrics cannot be compared between routes learned from different routing protocols.
#''[[Administrative distance]]'': When comparing route table entries from different sources such as different routing protocols and static configuration, a lower administrative distance indicates a more reliable source and thus a preferred route.

Because a routing metric is specific to a given routing protocol, multi-protocol routers must use some external [[heuristic]] to select between routes learned from different routing protocols. [[Cisco]] routers, for example, attribute a value known as the [[administrative distance]] to each route, where smaller administrative distances indicate routes learned from a protocol assumed to be more reliable.

A local administrator can set up host-specific routes that provide more control over network usage, permits testing, and better overall security. This is useful for debugging network connections or routing tables.

In some small systems, a single central device decides ahead of time the complete path of every packet. In some other small systems, whichever edge device injects a packet into the network decides ahead of time the complete path of that particular packet. In either case, the route-planning device needs to know a lot of information about what devices are connected to the network and how they are connected to each other. Once it has this information, it can use an algorithm such as [[A* search algorithm]] to find the best path.

In high-speed systems, there are so many packets transmitted every second that it is infeasible for a single device to calculate the complete path for each and every packet. Early high-speed systems dealt with this with [[circuit switching]] by setting up a path once for the first packet between some source and some destination; later packets between that same source and that same destination continue to follow the same path without recalculating until the circuit [[teardown (communications)|teardown]]. Later high-speed systems inject packets into the network without any one device ever calculating a complete path for packets.

In large systems, there are so many connections between devices, and those connections change so frequently, that it is infeasible for any one device to even know how all the devices are connected to each other, much less calculate a complete path through them. Such systems generally use [[hop (networking)#Next hop|next-hop]] routing.

Most systems use a deterministic [[dynamic routing]] algorithm. When a device chooses a path to a particular final destination, that device always chooses the same path to that destination until it receives information that makes it think some other path is better.

A few routing algorithms do not use a deterministic algorithm to find the best link for a packet to get from its original source to its final destination. Instead, to avoid congestion hot spots in packet systems, a few algorithms use a randomized algorithm—Valiant's paradigm—that routes a path to a randomly picked intermediate destination, and from there to its true final destination.<ref>{{citation |author1=Michael Mitzenmacher |author2=Andréa W. Richa |author3=Ramesh Sitaraman |url=http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf |title=The Power of Two Random Choices: A Survey of Techniques and Results |section=Randomized Protocols for Circuit Routing |page=34 |url-status=live |archive-url=https://web.archive.org/web/20231213082735/https://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf |archive-date= Dec 13, 2023 }}</ref><ref>{{citation |author=Stefan Haas |url=http://inspirehep.net/record/887357/files/cer-002474543.pdf |website=INSPIRE |title=The IEEE 1355 Standard: Developments, Performance and Application in High Energy Physics |date=1998 |page=15 |quote=To eliminate network hot spots, ... a two phase routing algorithm. This involves every packet being first sent to a randomly chosen intermediate destination; from the intermediate destination it is forwarded to its final destination. This algorithm, referred to as Universal Routing, is designed to maximize capacity and minimize delay under conditions of heavy load. |url-status=live |archive-url=https://web.archive.org/web/20190516092754/http://inspirehep.net/record/887357/files/cer-002474543.pdf |archive-date= May 16, 2019 }}</ref> In many early telephone switches, a randomizer was often used to select the start of a path through a [[1ESS switch#Switching fabric|multistage switching fabric]].

Depending on the application for which path selection is performed, different metrics can be used. For example, for web requests one can use minimum latency paths to minimize web page load time, or for bulk data transfers one can choose the least utilized path to balance load across the network and increase throughput. A popular path selection objective is to reduce the average completion times of traffic flows and the total network bandwidth consumption. Recently, a path selection metric was proposed that computes the total number of bytes scheduled on the edges per path as selection metric.<ref>{{Cite book |chapter= Poster Abstract: Minimizing Flow Completion Times using Adaptive Routing over Inter-Datacenter Wide Area Networks |first1= M. |last1=Noormohammadpour |first2=C. S. |last2=Raghavendra |title= IEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS) |via=ResearchGate |doi=10.1109/INFCOMW.2018.8406853 |date= Apr 2018 |pages= 1–2 |arxiv= 1802.09080 |isbn= 978-1-5386-5979-3 |chapter-url=https://www.researchgate.net/publication/323411017}}</ref> An empirical analysis of several path selection metrics, including this new proposal, has been made available.<ref>{{Cite web |title= Minimizing Flow Completion Times using Adaptive Routing over Inter-Datacenter Wide Area Networks |first1=M |last1=Noormohammadpour |first2=C. S. |last2=Raghavendra |via=ResearchGate |doi=10.13140/RG.2.2.36009.90720 |doi-access=free |date= Apr 2018 |url=https://www.researchgate.net/publication/323723167}}</ref>