The basic function of a router is to bridge connections between network segments. Routing is considered a layer-three function of the OSI standard model because it makes use of the IP address layer to guide packet movement. Essentially, all routers rely on a routing table to guide the flow of data. The routing table is used to find the best match to a destination IP address of a packet.  

There are several proven algorithms used for efficient routing. One type of routing is dynamic routing, where the algorithms react to changes in the network and topology. Information about the state of the network is shared through a routing protocol on a timed basis or upon a triggered update. Examples of dynamic routing are distance-vector routing and link-state routing. Alternatively, static routing is important and useful for small networks that need specific paths configured between routers. Static routes are non-adaptive, thus have no need to scan topologies or update metrics. These are preset on the router:  

• Shortest path routing: A graph is constructed representing routers on the network. An arc between nodes represents a known link or connection. The algorithm simply finds the shortest path from any source to any destination.  
• Flooding: Every packet is repeated and broadcast from every router to every endpoint on its link. This generates a massive number of duplicate packets and requires a hop counter in the packet header to ensure packets have a limited time to live. An alternative is selective flooding, which only floods a network in the general direction of the destination. Flood networks are the basis of Bluetooth mesh networking.
• Flow-based routing: Inspects the current flow in the network before determining a path. For any given connection, if the capacity and average flow are known, then compute the mean packet delay on that link. This algorithm finds the minimum average.
• Distance-vector routing: The router table contains a best-known distance to each destination. The tables are updated by neighboring routers. The table contains an entry for each router in the subnet. Each entry contains a preferred route/path and the estimated distance to the destination. The distance can be a metric of a number of hops, latency, or queue lengths.
• Link-state routing: A router initially discovers all its neighbors through a special HELLO packet. The router measures the delay to each of its neighbors by sending an ECHO packet. That topology and timing information is then shared with all routers on the subnet. A complete topology is built and shared between all routers. 
• Hierarchical routing: Routers are divided into regions and have a hierarchical topology. Each router maintains an understanding of its own region, but not the entire subnet. Hierarchical routing is also an efficient means of controlling router table size and resources in constrained devices.
• Broadcast routing: Each packet carries a list of destination addresses. A broadcast router investigates the addresses and determines the set of output lines to transmit to the packet. The router will generate a new packet for each output line and include only the destinations needed in that newly formed packet.  
• Multicast routing: The network is partitioned into well-defined groups. An application can send a packet to an entire group rather than a single destination or a broadcast.  

Typical edge routers will support routing protocols such as Border Gateway Protocol (BGP), Open Shortest Path First (OSPF), Routing Information Protocol (RIP), and RIPng. An architect using edge routers in the field needs to be aware of the congestion and costs of using a certain routing protocol over others, especially if the interconnection between routers is a data-capped WAN connection:

• BGP: BGP-4 is the standard for internet domain routing protocols, and is described in RFC 1771; it is used by most ISPs. BGP is a distance-vector dynamic routing algorithm and advertises entire paths in routing update messages. If routing tables are large this requires substantial bandwidth. BGP will send a 19 byte keep-alive message every 60 seconds to maintain a connection. BGP may be a poor routing protocol for mesh topologies since BGP maintains a connection to neighbors. BGP also struggles with the growth of routing tables in large topologies. BGP is also unique as it's one of the only routing protocols based on TCP packets.
• OSPF: This protocol is described in RFC 2328 and provides network scaling and convergence advantages. Internet backbone and enterprise networks use OSPF heavily. OSPF is a link- state algorithm that supports IPv4 and IPV6 (RFC 5340) and operates on IP packets. It has the advantage of detecting dynamic link changes in seconds and responding.  
• RIP: Version two of RIP is a distance-vector routing algorithm based on hop counts using an interior gateway protocol. Originally based on the Bellman-Ford algorithm, it now supports variable-size subnets, overcoming the limitations in the original version. Loops in a routing table are restricted by limiting the maximum number of hops in a path (15). RIP is UDP- based and supports only IPv4 traffic. RIP has a longer convergence time than protocols such as OSPF but is easy to administer for small edge router topologies. Still, convergence for RIP with only a few routers can take several minutes.  
• RIPng: RIPng stands for RIP next generation (RFC 2080). This allows for the support of IPv6 traffic and IPsec for authentication.

A typical routing table used in a product like the Cradlepoint IBR900 router is as follows:

[administrator@IBR900-e11: /]$ route 
Table: wan 
Destination        Gateway    Device UID       Flags    Metric   Type 
default            96.19.152.1  wan            onlink   0        unicast

Table: main 
Destination        Gateway    Device UID       Flags    Metric   Type 
96.19.152.0/21     *            wan                     0        unicast
172.86.160.0/20    *            iface:pertino0          0        unicast
172.86.160.0/20    None         None                    256      blackhole
192.168.1.0/24     *            primarylan              0        unicast
2001:470:813b::/48 *            *iface:pertino0         256      unicast
fe80::/64          *            lan                     256      unicast
 
Table: local 
Destination       Gateway     Device UID       Flags    Metric   Type 
96.19.152.0        *            wan                     0        broadcast
96.19.153.13       *            wan                     0        local 
96.19.159.255      *            wan                     0        broadcast
127.0.0.0          *            *iface:lo               0        broadcast
.
.
.

In this example, there are three tables: wan, main, and local. Each table contains particular routing paths particular to that interface:

• Destination: The complete or partial IP address of the packet destination. If the table contains the IP, it will reference the rest of the entry to resolve the interface to route to a partial address can be given prefixed by /. This specifies the fix bit positions of the address to resolve. For example, /24 in 192.168.1.0/24 specifies the top 24 bits of  192.168.1 are fixed and the lower 8 bits can resolve any address on the 192.168.1.* subnet.
• Gateway: This is the interface to direct packets to that match the destination lookup. In the previous case, the gateway is specified as 96.19.152.1 and the destination is default. This implies the outbound WAN at 96.19.152.1 will be used for all destination addresses. This is essentially an IP passthrough.
• Device UID: This is an alphanumeric identifier for the interface to direct data to. For example, any destination in the 172.19.152.0/21 subnet will route packets to an interface labeled iface:pertino0. Often, this field will be expressed with a numeric IP address rather than a symbolic reference.
• Flags: Used for diagnostics and indicate route state. States could be route up, use gateway.
• Metric: This is the distance to the destination and is usually counted by the number of hops.
• Type: Several route types can be used:
  • unicast: The route is a real path to a destination.
  • unreachable: Destination is unreachable. Packets are discarded and an ICMP message indicating the host is unreachable is generated. The local sender receives an EHOSTUNREACH error.
  • blackhole: Destinations are unreachable. Unlike prohibit types, packets will drop quietly. Local senders get an EINVAL error.
  • prohibit: Destinations are unreachable. Packets will be discarded and ICMP messages generated. Local senders receive an EACCES error.
  • local: Destinations are assigned to this host. The packets are looped back and delivered locally.
  • broadcast: Packets will be sent as broadcasts over the interface to all destinations.
  • throw: Special control route to force packets to drop and generate ICMP unreachable messages.

It should also be noted in the preceding example that IPv6 addresses are intermixed with IPv4 addresses. For example,  2001:470:813b::/48 in the main table is an IPv6 address with a /48 bit subnet.