Routing

This article discusses routing in computer networks. For other meanings, see routing (disambiguation).

Routing is the means of discovering paths in computer networks along which information (split up into packets) can be sent. Circuit-based networks, such as the voice telephone network, also perform routing, to find paths for telephone calls through the network fabric.

Routing is usually directed by routing tables, which maintain a record of the best routes to various network locations in order to keep up with the packet arrival rate.

Small networks may involve hand configuration. Large networks involve complex topologies and may change constantly, making the constructing of routing tables very problematic. Nevertheless, most of the PSTN uses pre-computed routing tables, with fallback routes if the most direct rote is blocked: see routing in the PSTN. Automatic routing protocols attempt to solve this problem with dynamically updated routing tables. These are updated intermittently by the routing software, based on information carried by the routing protocol, and allow the network to be nearly autonomous in avoiding network failures and blockages.

Routing directs forwarding, the passing of logically addressed packets from their local subnetwork toward their ultimate destination. In large networks, packets may pass through many intermediary destinations before reaching their destination. Routing and forwarding both occur at layer 3 of the OSI seven-layer model.

The hardware used in routing includes hubs, switches and routers.

Dynamic routing basics

If a router on a designated path on a routing table is no longer available, the existing routers must determine an alternate route to get their data to its destination. This is usually accomplished through the use of distance vector algorithms and link state algorithms, which account for nearly every routing algorithm in use on the Internet.

Distance vector algorithms

When distance vector algorithms are used, the distance between each router is assigned a number. Routers will send information from point A to point B via the path that results in the lowest 'cost' or sum of the distances between the routers used. When one of the routers involved goes down, each router tests the 'distance' to adjacent routers and creates a new distance table. This is then used to determine the next best route.

Link state algorithms

When link state algorithms are used, the best route is determined through each node finding the cost to get to every other node in the network. Then, each node asks each adjacent node what the cost is for it to get to all of its adjacent nodes. This continues until each node knows the best way to get from itself to any other node in the network.

Routed versus routing protocol

There is often confusion between routed protocol and routing protocol:

• Routed protocol: Any network protocol that provides enough information in its network layer address to allow a packet to be forwarded from one host to another host based on the addressing scheme. Routed protocols define the format and use of the fields within a packet. Packets generally are conveyed from end system to end system. IP is an example of a routed protocol.

• Routing protocols: facilitate the exchange of routing information between networks, allowing routers to build routing tables dynamically. Traditional IP routing stays simple because it uses next-hop routing where the router only needs to consider where it sends the packet, and does not need to consider the subsequent path of the packet on the remaining hops.

Although this dynamic routing can become very complex, it makes the Internet very flexible, and has allowed it to grow in size by more than eight orders of magnitude over the years since adopting IP i Note: The impression in various Cisco marketing documents to the contrary, EIGRP is definitely not a link-state protocol, or any sort of "hybrid" thereof.

A routing metric consists of any value used by routing algorithms to determine whether one route is superior to another. Metrics can cover such information as bandwidth, delay, hop count, path cost, load, MTU, reliability, and communication cost. The routing table stores only the best possible routes, while link-state or topological databases may store all other information.

Administrative distance is the feature used by routers to select the best path when there are two or more different routes to the same destination from two different routing protocols. Administrative distance defines the reliability of a routing protocol. Each routing protocol is prioritized in order of most to least reliable using an administrative distance value.

Depending on the relationship of the router relative to other autonomous systems, various classes of routing protocols exist:

• Ad hoc network routing protocols appear in networks with no or little infrastructure. For a list of a couple of the proposed protocols, see the Ad hoc protocol list

• Interior Gateway Protocols (IGPs) exchange routing information within a single autonomous system. Common examples include:
  • IGRP (Interior Gateway Routing Protocol)
  • EIGRP (Enhanced Interior Gateway Routing Protocol)
  • OSPF (Open Shortest Path First)
  • RIP (Routing Information Protocol)
  • IS-IS (Intermediate System to Intermediate System)

• Exterior Gateway Protocols (EGPs) route between separate autonomous systems. EGPs include:
  • EGP (the original Exterior Gateway Protocol used to connect to the former Internet backbone network -- now obsolete)
  • BGP (Border Gateway Protocol: current version, BGPv4, was adopted around 1995)

See also

• Network address translation (NAT)
• IP spoofing (Security)
• Classless inter-domain routing (CIDR)
• Deflection routing
• Policy based routing
• MPLS routing
• wormhole routing
• ATM routing
• Routing in the PSTN
• "Hot-potato routing"
• "Cold-potato routing"
• Adaptive Routing
• Routing algorithms:
  • Bellman-Ford algorithm
  • Dijkstra's algorithm
  • Edge Disjoint Shortest Pair Algorithm
  • distance-vector routing protocol
  • Hierarchical routing
  • Link-state routing protocol
• Mathematical complexity of routing with multiple metrics
  • and hence the problem of Quality of Service in routing

References

• . ISBN 321227352. {{cite book}}: Missing or empty |title= (help); Unknown parameter |Author= ignored (|author= suggested) (help); Unknown parameter |Publisher= ignored (|publisher= suggested) (help); Unknown parameter |Title= ignored (|title= suggested) (help); Unknown parameter |Year= ignored (|year= suggested) (help)

External links

• Routing, A diagram on how routing works
• ITPRC's IP Routing Resource Center
• Router Troubleshooting Primer - Take a look at the proper steps to troubleshooting routing problems