Routing

Routing is the backbone of the Internet. Without it there would be no Internet. Routing is the means by which logically addressed packets are forwarded from their local subnetwork toward their ultimate destination. In large networks packets may be passed to many intermediary destinations before reaching its destination. Routing occurs at layer 3 of the OSI seven-layer model.

The devices that perform the routing function are called routers. See the router article for a description of the hardware technology and manufacturers of routers. The rest of this article describes routing in a hardware-independent way.

Knowing where to send packets requires a knowledge of the structure of the network. In small networks, routing can be very simple, and is often configured by hand. In large networks the topology of the network is complex, and constantly changing, making the problem of constructing the routing tables very complex.

As the best routes can only be recalculated very slowly relative to the rate of arrival of packets, routers keep a routing table that maintains a record of only the best possible routes to certain network destinations and the routing metrics associated with those routes.

Routing protocols are used to exchange routing information between networks, allowing routing tables to be built dynamically. Traditional IP routing is 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 is 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 last thirty years.

Routing algorithms use two basic techologies:

• telling the world who your neighbors are: link-state routing protocols such as OSPF
• telling your neighbors what the world looks like: distance-vector routing protocols such as RIP

A routing metric is any value that is used by routing algorithms to determine whether one route is superior to another. Metrics include such information as bandwidth, delay, hop count, path cost, load, MTU, reliability, and communication cost. Only the best possible routes are stored in the routing table, while all other information may be stored in link-state[?] or topological databases.

Depending on the relationship of the router relative to other autonomous systems there are two main classes of routing protocols:

Ad hoc network routing protocols are used for networks with no or little infrastructure. A list of a couple of the proposed protocols can be found in Ad hoc protocol list

Interior Gateway Protocols (IGPs) are used to exchange routing information within a single autonomous system. Common examples:

• IGRP/EIGRP (Interior Gateway Routing Protocol/ Enhanced IGRP)
• OSPF (Open Shortest Path First)
• RIP (Routing Information Protocol)
• IS-IS (Intermediate System to Intermediate System)

Exterior Gateway Protocols (EGPs) are used for routing 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 is BGPv4)

Topics to be discussed:

• Routing policy[?]
• MPLS routing
• wormhole routing
• ATM routing
• Routing in the PSTN[?]
• "Hot-potato routing"
• "Cold-potato routing"
• Mathematical complexity of routing with multiple metrics
  • and hence the problem of Quality of Service in routing

See also:

• Router (includes a list of manufacturers)
• NAT (Network Address Translation)