Packet forwarding
 | This article needs additional citations for verification. (July 2009) |
Packet forwarding is the relaying of packets from one network segment to another by nodes in a computer network.
The Network Layer of the OSI Layer is responsible for Packet Forwarding.[1] The simplest forwarding model—unicasting—involves a packet being relayed from link to link along a chain leading from the packet's source to its destination. However, other forwarding strategies are commonly used. Broadcasting requires a packet to be duplicated and copies sent on multiple links with the goal of delivering a copy to every device on the network. In practice, broadcast packets are not forwarded everywhere on a network, but only to devices within a broadcast domain, making broadcast a relative term. Less common than broadcasting, but perhaps of greater utility and theoretical significance, is multicasting, where a packet is selectively duplicated and copies delivered to each of a set of recipients.
Networking technologies tend to naturally support certain forwarding models. For example, fiber optics and copper cables run directly from one machine to another to form a natural unicast media – data transmitted at one end is received by only one machine at the other end. However, as illustrated in the diagrams, nodes can forward packets to create multicast or broadcast distributions from naturally unicast media. Likewise, traditional Ethernet (10BASE5 and 10BASE2, but not the more modern 10BASE-T) are natural broadcast media – all the nodes are attached to a single long cable and a packet transmitted by one device is seen by every other device attached to the cable. Ethernet nodes implement unicast by ignoring packets not directly addressed to them. A wireless network is naturally multicast – all devices within a reception radius of a transmitter can receive its packets. Wireless nodes ignore packets addressed to other devices, but require forwarding to reach nodes outside their reception radius.
At nodes where multiple outgoing links are available, the choice of which, all, or any to use for forwarding a given packet requires a decision making process that, while simple in concept, is sometimes bewilderingly complex. Since a forwarding decision must be made for every packet handled by a node, the total time required for this can become a major limiting factor in overall network performance. Much of the design effort of high-speed routers and switches has been focused on making rapid forwarding decisions for large numbers of packets.
The forwarding decision is generally made using one of two processes: routing, which uses information encoded in a device's address to infer its location on the network, or bridging, which makes no assumptions about where addresses are located and depends heavily on broadcasting to locate unknown addresses. The heavy overhead of broadcasting has led to the dominance of routing in large networks, particularly the Internet; bridging is largely relegated to small networks where the overhead of broadcasting is tolerable. However, since large networks are usually composed of many smaller networks linked together, it would be inaccurate to state that bridging has no use on the Internet; rather, its use is localized.
A network can use one of two different methods to forward packets: store-and-forward or cut through.[2]
IP forwarding also known as IP routing or Internet routing is a process used to determine which path a packet or datagram can be sent.The process uses routing information to make decisions and is designed to send a packet over multiple networks.
Generally, networks are separated from each other by routers.For packets to travel between networks, they must be “routed” from one network to another. These routers contain a routing table that can contain specific instructions on how to send packets to a destination network (known as a route), or a set of generic instructions on where to send packets that do not match any of the other specified routes (called a default route), or both. These routes can either be hard-coded into the router by the network administrator (called a static route), or learned dynamically via a routing protocol. These routes give the routers instructions on how to utilize the physical network infrastructure that is in place to get packets to their destination, regardless of the number of hops that they must take to get there.
Ideally, IP forwarding algorithms would take into account a datagram's length, the type of service specified in the datagram's header, and the network load to determine the best path to send a packet to its intended destination. In general, most routing software determines its route through a shortest path algorithm. However, there are other routing protocols that use other factors (known as metrics) to determine the best path. Each path is given a “cost,” and the algorithms within a router’s operating system use this cost to determine where and how to send the packets. The calculation of these costs can include the bandwidth or utilization of the link between routers, or the speed that the connection is operating at. Different protocols are also used for different applications (for example, protocols such as Open Shortest Path First are generally used for routing packets between subnetworks within an organization’s network, and protocols such as Border Gateway Protocol are used for routing outside of them).[3]
In addition to calculating route cost, routing protocols also broadcast and share their known routes to other routers. This functionality comes with several benefits. Instead of requiring a network administrator to program each individual router with the relevant routes, he or she would only need to program a small number of routers (from which the other would learn the programmed routes). This has the added flexibility of being able to recover from an outage automatically. If a route becomes unavailable for some reason, the routing protocol can detect this and automatically send packets over an alternate route. This functionality can be invaluable in situations where network redundancy is required.
Advances in Packet Forwarding
 | This section reads like a press release or a news article. |
The Mimo-Mesh Project of Kyushu University based in Fukuoka City, Fukuoka Prefecture, Japan, has developed and put into use new packet forwarding technology for building wide-area wireless infrastructure.
IPT, Intermittent Periodic Transmit, is a proprietary packet-forwarding scheme that is designed to reduce radio interference in the forwarding path of mesh networks. IPT forwarding eliminates packet collisions and therefore enables high throughput in long hop relays, permitting creation of a large scale mesh.
In 2010, hundreds of wireless LAN access points incorporating the technology were installed in the commercial shopping and entertainment complex, Canal City Hakata, resulting in the successful operation of one of the world's largest indoor wireless multi-hop backhauls.
IP routing algorithm
The IP forwarding algorithm is a specific implementation of routing for IP networks. 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.[4]
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.
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;
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.
Example
Example of a 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 interface name of the network interface card
- ppp0 is the PPPoE connection, which is configured as the 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 |
Routing protocols
- RIP - Routing Information Protocol (BSD routed daemon)
- EGP - Exterior Gateway Protocol
- BGP - Border Gateway Protocol (Cornell University's gated daemon)
- Multipath routing
See also
References
- ^ Gheorghe, Daniel. "Cisco CCDA Simplified". Reality Press Ltd., 2012, p. 6.
- ^ Stefan Haas (1998). "The IEEE 1355 Standard: Developments, Performance and Application in High Energy Physics" (PDF): 58. Retrieved 2015-01-16.
{{cite journal}}: Cite journal requires|journal=(help) - ^ Comer, Douglas E. (2000). Internetworking with TCP/IP (4 ed.). Prentice Hall: Upper Saddle River, NJ.
- ^ Internetworking with TCP/IP: Principles, protocols, and architecture By Douglas Comer