Heuristic routing

Heuristic routing is a system used to describe how deliveries are made when problems in a

of the world.

Heuristic routing is achieved using specific algorithms to determine a better, although not always optimal, path to a destination. When an interruption in a network topology occurs, the software running on the networking electronics can calculate another route to the desired destination via an alternate available path.

According to Shuster & Schur (1974, p. 1):

The heuristic approach to problem solving consists of applying human intelligence, experience, common sense and certain rules of thumb (or heuristics) to develop an acceptable, but not necessarily an optimum, solution to a problem. Of course, determining what constitutes an acceptable solution is part of the task of deciding which approach to use; but broadly defined, an acceptable solution is one that is both reasonably good (close to optimum) and derived within reasonable effort, time, and cost constraints. Often the effort (manpower, computer, and other resources) required, the time limits on when the solution is needed, and the cost to compile, process, and analyze all the data required for deterministic or other complicated procedures preclude their usefulness or favor the faster, simpler heuristic approach. Thus, the heuristic approach is generally used when deterministic techniques or are not available, economical, or practical.

Heuristic routing allows a measure of route optimization in telecommunications networks based on recent empirical knowledge of the state of the network. Data, such as time delay, may be extracted from incoming messages, during specified periods and over different routes, and used to determine the optimum routing for transmitting data back to the sources.

IP routing

The

to compute the shortest path to each destination. Metrics used are based on the number of hops, delay, throughput, traffic, and reliability.

Distance vector algorithms

• RIP uses number of hops, or gateways traversed, as its metric
• IGRP uses bandwidth, delay, hop count, link reliability, load, and MTU
• Diffusing Update Algorithm
• BGP
  uses the distance vector algorithm

Link state algorithms

• Dijkstra algorithm
  .

See also

• Heuristic (computer science)
• Ford–Fulkerson algorithm
• Bellman–Ford algorithm
• Turn restriction routing

References

• Campbell, Ann Melissa; Savelsbergh, Martin (2004). "Efficient insertion heuristics for vehicle routing and scheduling problems".
  JSTOR 25769207
  .
• Malhotra, Ravi (2002). IP routing. Sebastopol, CA: O'Reilly.
  OCLC 49318657
  .
• Robertazzi, Thomas G. (2007). Networks and grids: technology and theory. Information technology: transmission, processing, and storage. New York: Springer.
  OCLC 76935739
  .
• Shuster, Kenneth A; Schur, Dennis A. (1974). Heuristic routing for solid waste collection vehicles. An environmental protection publication (SW-113) in the solid waste management series. Washington, DC:
  OCLC 3207134
  .

 This article incorporates public domain material from Federal Standard 1037C. General Services Administration. Archived from the original on 2022-01-22.