Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Heuristic routing
open-in-new
<h2 id="ip-routing">IP routing</h2> <p class="note">Main article: <a href="/facts/IP_forwarding/rpLSaNxR">IP forwarding</a></p> <p>The <a href="/facts/IP_routing/rpLSaNxR">IP routing</a> protocols in use today are based on one of two algorithms: <i>distance vector</i> or <i>link state</i>. Distance vector algorithms broadcast routing information to all neighboring routers. Link state routing protocols build a topographical map of the entire network based on updates from neighbor routers, and then use the <a href="/facts/Dijkstra_algorithm/ehun88jl">Dijkstra algorithm</a> to compute the shortest path to each destination. Metrics used are based on the number of hops, delay, throughput, traffic, and reliability. </p> <h3>Distance vector algorithms</h3> <ul><li><a href="/facts/Routing_Information_Protocol/xGeIuGk6">RIP</a> uses number of hops, or gateways traversed, as its metric</li> <li><a href="/facts/IGRP/L6w91wYM">IGRP</a> uses bandwidth, delay, hop count, link reliability, load, and <a href="/facts/Maximum_transmission_unit/l2FdKoLa">MTU</a></li> <li><a href="/facts/EIGRP/KIcfLjbh">EIGRP</a> uses the (DUAL) <a href="/facts/Diffusing_Update_Algorithm/DUsMhERD">Diffusing Update Algorithm</a></li> <li><a href="/facts/BGP/XfYgBzW3">BGP</a> uses the distance vector algorithm</li></ul> <h3>Link state algorithms</h3> <ul><li><a href="/facts/OSPF/PACpGUHb">OSPF</a> uses the <a href="/facts/Dijkstra_algorithm/ehun88jl">Dijkstra algorithm</a>.</li></ul> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Heuristic_(computer_science)/PM2qkoa2">Heuristic (computer science)</a></li> <li><a href="/facts/Ford%25E2%2580%2593Fulkerson_algorithm/wwk3tw52">Ford–Fulkerson algorithm</a></li> <li><a href="/facts/Bellman%25E2%2580%2593Ford_algorithm/Sx6INcdr">Bellman–Ford algorithm</a></li> <li><a href="/facts/Turn_restriction_routing/FsBahNwM">Turn restriction routing</a></li></ul> <ul><li>Campbell, Ann Melissa; Savelsbergh, Martin (2004). "Efficient insertion heuristics for vehicle routing and scheduling problems". <i><a href="/facts/Transportation_Science/BhT8bXcB">Transportation Science</a></i>. 38 (3): 369–378. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.499.8006">10.1.1.499.8006</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1287%2Ftrsc.1030.0046">10.1287/trsc.1030.0046</a>. <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/25769207">25769207</a>.</li> <li>Malhotra, Ravi (2002). <a href="https://archive.org/details/iprouting0000malh"><i>IP routing</i></a>. Sebastopol, CA: O'Reilly. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0596002750. <a href="/facts/OCLC_(identifier)/Yqad8waq">OCLC</a> <a href="https://search.worldcat.org/oclc/49318657">49318657</a>.</li> <li>Robertazzi, Thomas G. (2007). <a href="https://books.google.com/books?id=pikvfY8GdoUC"><i>Networks and grids: technology and theory</i></a>. Information technology: transmission, processing, and storage. New York: Springer. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-0-387-68235-8">10.1007/978-0-387-68235-8</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9780387367583. <a href="/facts/OCLC_(identifier)/Yqad8waq">OCLC</a> <a href="https://search.worldcat.org/oclc/76935739">76935739</a>.</li> <li>Shuster, Kenneth A; Schur, Dennis A. (1974). <i>Heuristic routing for solid waste collection vehicles</i>. An environmental protection publication (SW-113) in the solid waste management series. Washington, DC: <a href="/facts/U.S._Environmental_Protection_Agency/ghI985SI">U.S. Environmental Protection Agency</a>. <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/2027%2Fmdp.39015040701149">2027/mdp.39015040701149</a>. <a href="/facts/OCLC_(identifier)/Yqad8waq">OCLC</a> <a href="https://search.worldcat.org/oclc/3207134">3207134</a>.</li></ul> <p> This article incorporates <a href="/facts/Copyright_status_of_works_by_the_federal_government_of_the_United_States/Q1jvr96g">public domain material</a> from <a href="https://web.archive.org/web/20220122224547/https://www.its.bldrdoc.gov/fs-1037/fs-1037c.htm"><i>Federal Standard 1037C</i></a>. <a href="/facts/General_Services_Administration/Np3opv9x">General Services Administration</a>. Archived from <a href="https://www.its.bldrdoc.gov/fs-1037/fs-1037c.htm">the original</a> on 2022-01-22. </p>