IP forwarding algorithm
 | This article relies largely or entirely on a single source. (June 2010) |
The IP forwarding algorithm, commonly known as IP routing, is a specific implementation of routing for IP networks and gives a more directed approach in forwarding datagrams over a network. In order to achieve a successful transfer of data the algorithm uses a routing table to select a next-hop router as the next destination for a datagram. The IP address that is selected is known as the next-hop address.[1]
When several destinations are matching, the route with the longest subnet mask is chosen (the most specific one). There can be only one default route.
IP Routing algorithm
The IP Forwarding Algorithm states:
Given a destination IP address, D, and network prefix, N:
if ( N matches a directly connected network address )
Deliver datagram to D over that network link;
else if ( The routing table contains a route for N )
Send datagram to the next-hop address listed in the routing table;
else if ( There exists a default route )
Send datagram to the default route;
else
Send a forwarding error message to the originator;
The first case is OSI level 2 routing; the next 2 cases are OSI level 3 routing.
When there is no route available an ICMP error message is sent to the originator of the packet, to inform that host that the packet could not be delivered, and to avoid unnecessary retransmission and possibly subsequent network congestion. The sending host should either stop transmitting, or choose another address or route.
IP Routing types
OSI level 2
A system's own subnet is immediately reachable over the primary network link. An ethernet arp and MAC addressing broadcasting technique will be used to send packets to the target system in this case (OSI level 2/Data link layer).
Sometimes private LAN routing rules are forgotten to be specified. This frequently leads to packet non-delivery. Especially if you have traffic for multiple subnets over the same network segment.
The following subnets cannot be routed (by definition), so they need to always be reacheable via a direct attached network device, via a NIC, a hub, a bridge, or a switch.
Remark that there is no next-hop address, because those subnets are not routeable over the public internet.
route add -net 169.254.0.0 netmask 255.255.0.0 dev eth0 route add -net 192.168.0.0 netmask 255.255.0.0 dev eth0 route add -net 172.16.0.0 netmask 255.240.0.0 dev eth0 route add -net 10.0.0.0 netmask 255.0.0.0 dev eth0
OSI level 3
The next 2 route types are OSI level 3/Network layer:
You can send all traffic for the specified subnet to a specific host:
route add -net 192.168.1.0 netmask 255.255.255.0 gw 192.168.96.1
To specify the default route, the route to the target router should already have been defined:
route add default gw 71.46.14.1
The default route is generally pointing to the uplink (towards the public internet). If you want to change the default route, the previous default route should first be removed:
route del default gw 71.46.14.1
Example
Example of a (small) routing table:
route -n Kernel IP routing table Destination Gateway Genmask Flags Metric Ref Use Iface 0.0.0.0 71.46.14.1 0.0.0.0 UG 0 0 0 ppp0 10.0.0.0 0.0.0.0 255.0.0.0 U 0 0 0 eth0 71.46.14.1 0.0.0.0 255.255.255.255 UH 0 0 0 ppp0 169.254.0.0 0.0.0.0 255.255.0.0 U 0 0 0 eth0 172.16.0.0 0.0.0.0 255.240.0.0 U 0 0 0 eth0 192.168.0.0 0.0.0.0 255.255.0.0 U 0 0 0 eth0 192.168.1.0 192.168.96.1 255.255.255.0 UG 0 0 0 eth0 192.168.96.0 0.0.0.0 255.255.255.0 U 0 0 0 eth0
Network interfaces:
- eth0 is the network interface card (local area network)
- ppp0 is the PPPoE connection (default route).
A default route is recognized by Destination 0.0.0.0 and Flag G.
A network router is identified by a network mask 255.255.255.255 and a Flag H.
Routing flags
| Flag | Description |
|---|---|
| G | Use Gateway (gateway filled in) |
| H | Target is a Host (bit mask of 32 bits) |
| U | Route is Up |
Subnet masks
Newer kernels support a simplified syntax:
route add -net 169.254.0.0/16 dev eth0 route add -net 192.168.0.0/16 dev eth0 route add -net 172.16.0.0/12 dev eth0 route add -net 10.0.0.0/8 dev eth0
Kernel routing tables
route -n Kernel IP routing table Destination Gateway Genmask Flags Metric Ref Use Iface 0.0.0.0 217.136.39.1 0.0.0.0 UG 0 0 0 ppp0 10.0.0.0 0.0.0.0 255.0.0.0 U 0 0 0 eth0 169.254.0.0 0.0.0.0 255.255.0.0 U 0 0 0 eth0 172.16.0.0 0.0.0.0 255.240.0.0 U 0 0 0 eth0 192.168.0.0 0.0.0.0 255.255.0.0 U 0 0 0 eth0 217.136.39.1 0.0.0.0 255.255.255.255 UH 0 0 0 ppp0
Embedded Systems that do not have the route command, can use the following command:
cat /proc/net/route Iface Destination Gateway Flags RefCnt Use Metric Mask MTU Window IRTT ppp0 00000000 012788D9 0003 0 0 0 00000000 0 0 0 eth0 0000000A 00000000 0001 0 0 0 000000FF 0 0 0 eth0 0000FEA9 00000000 0001 0 0 0 0000FFFF 0 0 0 eth0 000010AC 00000000 0001 0 0 0 0000F0FF 0 0 0 eth0 0000A8C0 00000000 0001 0 0 0 0000FFFF 0 0 0 ppp0 012788D9 00000000 0005 0 0 0 FFFFFFFF 0 0 0
You need hexadecimal computing to understand this. Note that the sequence of the bytes in the hex notation, and the (decimal) IP dot notation are reversed.
Routing algorithms
- RIP - Routing Information Protocol (BSD routed daemon)
- EGP - Exterior Gateway Protocol
- BGP - Border Gateway Protocol (Cornell University's gated daemon)
- Multipath routing
See also
For more information you can consult the route man page on Unix systems.
References
- ^ Internetworking with TCP/IP: Principles, protocols, and architecture By Douglas Comer
rfc1812 section 5.2.4.3 Next Hop Address