Editing Routing (section)

==Topology distribution==
With [[static routing]], small networks may use manually configured routing tables. Larger networks have complex [[network topology|topologies]] that can change rapidly, making the manual construction of routing tables unfeasible. Nevertheless, most of the [[public switched telephone network]] (PSTN) uses pre-computed routing tables, with fallback routes if the most direct route becomes blocked (see [[routing in the PSTN]]).

[[Dynamic routing]] attempts to solve this problem by constructing routing tables automatically, based on information carried by [[routing protocol]]s, allowing the network to act nearly autonomously in avoiding network failures and blockages. Dynamic routing dominates the Internet. Examples of dynamic-routing protocols and algorithms include [[Routing Information Protocol]] (RIP), [[Open Shortest Path First]] (OSPF) and [[Enhanced Interior Gateway Routing Protocol]] (EIGRP).

===Distance vector algorithms===
{{main|Distance-vector routing protocol}}
Distance vector algorithms use the [[Bellman–Ford algorithm]]. This approach assigns a ''cost'' number to each of the links between each node in the network. Nodes send information from point A to point B via the path that results in the lowest ''total cost'' (i.e. the sum of the costs of the links between the nodes used).

When a node first starts, it only knows of its immediate neighbors and the direct cost involved in reaching them. (This information — the list of destinations, the total cost to each, and the ''next hop'' to send data to get there — makes up the routing table, or ''distance table''.) Each node, on a regular basis, sends to each neighbor node its own current assessment of the total cost to get to all the destinations it knows of. The neighboring nodes examine this information and compare it to what they already know; anything that represents an improvement on what they already have, they insert in their own table. Over time, all the nodes in the network discover the best next hop and total cost for all destinations.

When a network node goes down, any nodes that used it as their next hop discard the entry and convey the updated routing information to all adjacent nodes, which in turn repeat the process. Eventually, all the nodes in the network receive the updates and discover new paths to all the destinations that do not involve the down node.

===Link-state algorithms===
{{main|Link-state routing protocol}}
When applying link-state algorithms, a [[Graph (discrete mathematics)|graphical map]] of the network is the fundamental data used for each node. To produce its map, each node floods the entire network with information about the other nodes it can connect to.  Each node then independently assembles this information into a map. Using this map, each router independently determines the least-cost path from itself to every other node using a standard [[shortest paths]] algorithm such as [[Dijkstra's algorithm]]. The result is a [[tree graph]] rooted at the current node, such that the path through the tree from the root to any other node is the least-cost path to that node. This tree then serves to construct the routing table, which specifies the best next hop to get from the current node to any other node.

===Optimized Link State Routing algorithm===
{{main|Optimized Link State Routing Protocol}}
A link-state routing algorithm optimized for [[mobile ad hoc network]]s is the optimized Link State Routing Protocol (OLSR).<ref>RFC 3626</ref> OLSR is proactive; it uses Hello and Topology Control (TC) messages to discover and disseminate link-state information through the mobile ad hoc network. Using Hello messages, each node discovers 2-hop neighbor information and elects a set of ''multipoint relays'' (MPRs). MPRs distinguish OLSR from other link-state routing protocols.

===Path-vector protocol===
{{main|Path-vector routing protocol}}
Distance vector and link-state routing are both intra-domain routing protocols. They are used inside an [[Autonomous system (Internet)|autonomous system]], but not between autonomous systems. Both of these routing protocols become intractable in large networks and cannot be used in [[inter-domain]] routing. Distance vector routing is subject to instability if there are more than a few hops in the domain. Link state routing needs significant resources to calculate routing tables. It also creates heavy traffic due to flooding.

Path-vector routing is used for inter-domain routing. It is similar to distance vector routing. Path-vector routing assumes that one node (there can be many) in each autonomous system acts on behalf of the entire autonomous system. This node is called the ''speaker node.'' The speaker node creates a routing table and advertises it to neighboring speaker nodes in neighboring autonomous systems. The idea is the same as distance vector routing except that only speaker nodes in each autonomous system can communicate with each other. The speaker node advertises the path, not the metric, of the nodes in its autonomous system or other autonomous systems.

The path-vector routing algorithm is similar to the distance vector algorithm in the sense that each border router advertises the destinations it can reach to its neighboring router. However, instead of advertising networks in terms of a destination and the distance to that destination, networks are advertised as destination addresses and path descriptions to reach those destinations. The path, expressed in terms of the domains (or confederations) traversed so far, is carried in a special path attribute that records the sequence of routing domains through which the reachability information has passed. A route is defined as a pairing between a destination and the attributes of the path to that destination, thus the name, path-vector routing; The routers receive a vector that contains paths to a set of destinations.<ref>{{IETF RFC|1322}}</ref>