Jump to content

IP forwarding algorithm: Difference between revisions

Edit links
From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
No edit summary
Has been up for merging for 1+ year ... merging content with main article and redirecting.
Line 1: Line 1:
{{merge|IP forwarding|date=July 2014}}
#redirect [[IP forwarding]]
{{one source|date=June 2010}}
The '''IP forwarding algorithm''', commonly known as '''IP routing''', is a specific implementation of [[routing]] for [[IP network]]s. 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.''<ref>Internetworking with TCP/IP: Principles, protocols, and architecture By Douglas Comer</ref>

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''':
<pre>
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;
</pre>

When there is no route available an [[Internet Control Message Protocol|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 (data networks)|retransmission]] and possibly subsequent [[network congestion]].
The sending host should either stop transmitting, or choose another address or route.

==IP routing types==
===Link layer===
A host's own subnet is immediately reachable over the local network link.
An Ethernet [[Address Resolution Protocol]] (ARP) and [[MAC address]]ing [[broadcast|broadcasting technique]] is used to send packets to the target system.

The following subnets cannot be routed (by definition), so they need to always be reacheable via a [[Local area network|direct attached network]] device, via a [[Network interface controller|NIC]], a [[Ethernet hub|hub]], a [[Bridging_(networking)|bridge]], or a [[Network_switch|switch]].

There is no next-hop address, because those subnets are not routeable over the Internet.
<pre>
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

</pre>

===Internet Layer===
The next two route types involve the Internet Layer for routing across network boundaries. Each destination network may have a specific router node that forwards packets:
<pre>
route add -net 192.168.1.0 netmask 255.255.255.0 gw 192.168.96.1
</pre>
When no specific router is specified for a destination, the default router is used:
<pre>
route add default gw 71.46.14.1
</pre>

==Example==
Example of a routing table:
<pre>
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
</pre>

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 [[Ip_address#IPv4_subnetting|network mask]] 255.255.255.255
and a Flag H.

==Routing flags==
{|class=wikitable
|+Most common 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 [[Kernel (computing)|kernels]] support a simplified syntax:
<pre>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
</pre>

==Kernel routing tables==
<pre>
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
</pre>

In the Linux kernel, the route table is accessible via the /proc file system:
<pre>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
</pre>

==Routing protocols==
*RIP - [[Routing Information Protocol]] ([[BSD]] [[routed daemon]])
*EGP - [[Exterior Gateway Protocol]]
*[[BGP]] - [[Border Gateway Protocol]] ([[Cornell University]]'s [[gated daemon]])
*[[Multipath routing]]

==References==
{{reflist}}

[[Category:Internet Protocol]]
[[Category:Routing algorithms]]

Revision as of 22:49, 17 October 2015

Redirect to:

Retrieved from "https://en.wikipedia.org/w/index.php?title=IP_forwarding_algorithm&oldid=686238902"