|
Packet forwarding
Packet forwarding is the relaying of packets from one network
segment
to another by nodes in a computer network.
A
unicast
forwarding pattern, typical of many networking technologies including the
overwhelming majority of Internet traffic
A
multicast forwarding pattern, typical
of PIM
A
broadcast
forwarding pattern, typical of bridged Ethernet
The Network Layer of the OSI
Layer
is responsible for Packet Forwarding. 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.
Direct Versus Indirect Delivery
The delivery of a packet to
its final destination is accomplished by using two different methods of
delivery
·
direct
·
indirect
Direct Delivery
In a direct delivery, the
final destination of the packet is a host connected to the same physical
network as the deliverer. Direct delivery occurs when the source and
destination of the packet are located on the same physical network or when
the delivery is between the last router and the destination host.
The sender can easily
determine if the delivery is direct. It
can
extract the network address of the destination (using the mask) and compare
this address with the addresses of the networks to which it is connected.
If a match is found, the delivery is direct.
Indirect Delivery
If
the
destination host is not on the same network as the deliverer, the packet is
delivered indirectly. In an indirect delivery, the packet goes from router
to router until it reaches the one connected to the same physical network
as its final destination. Note that a delivery always involves one direct
delivery but zero or more indirect deliveries.
FIGURE
: DIRECT DELIVERY
FORWARDING
Forwarding means to place the
packet in its route to its destination. Forwarding
requires a host or a router
to have a routing table. When a host has a packet to send or when a router
has received a packet to be forwarded, it looks at this table to find the route
to the final destination. However, this simple solution is impossible today
in an internetwork such as the Internet because the number of entries
needed in the routing table would make table lookups inefficient.
Forwarding
Techniques
Several techniques can make
the size of the routing table manageable and also handle issues such as
security. We briefly discuss these methods here.
Next-Hop Method Versus Route Method
One technique to reduce the
contents of a routing table is called the next-hop method. In this
technique, the routing table holds only the address of the next hop instead
of information about the complete route (route method). The entries of a
routing table must be consistent with one another.
Network-Specific
Method Versus Host-Specific Method
A second technique to reduce
the routing table and simplify the searching process is called the
network-specific method. Here, instead of having an entry for every
destination host connected to the same physical network (host-specific
method), we have only one entry that defines the address of the destination
network itself. In other words, we treat all hosts connected to the same
network as one single entity. For example, if 1000 hosts are attached to
the same network, only one entry exists in the routing table instead of
1000.
Host-specific routing is used
for purposes such as checking the route or providing security measures.
Default Method
Another technique to simplify
routing is called the default method. Host A is connected to a network with
two routers. Router Rl routes the packets to hosts connected to network N2.
However, for the rest of the Internet, router R2 is used. So instead of
listing all networks in the entire Internet, host A can just have one entry
called the default (normally defined as network address 0.0.0.0).
Routing protocol [RGPV/ Dec 2012, Dec 2013, Jun 2014]
A routing protocol specifies how routers communicate with each other, disseminating
information that enables them to select routes between any two nodes on a computer network. Routing algorithms determine the specific choice
of route. Each router has a priori knowledge only of networks attached to it
directly. A routing protocol shares this information first among immediate
neighbors, and then throughout the network. This way, routers gain
knowledge of the topology of the network
FIGURE
: ROUTING PROTOCOL
Routing table
In computer networking a routing table, or routing
information base (RIB), is a data
table
stored in a router or a networked computer that lists the routes to particular
network destinations, and in some cases, metrics (distances) associated with those
routes. The routing table contains information about the topology of the network immediately around it.
The construction of routing tables is the primary goal of routing protocols. Static routes are entries made in a routing table by
non-automatic means and which are fixed rather than being the result of
some network topology "discovery" procedure.
Contents of routing tables
The routing table consists of at least
three information fields:
- the network id: i.e. the destination subnet
- cost/metric: i.e. the cost or metric of the path through which the
packet is to be sent
- next hop: The next hop, or gateway, is the address of the next
station to which the packet is to be sent on the way to its final
destination
Depending on the application and
implementation, it can also contain additional values that refine path
selection:
- quality of service associated with the route. For example, the U flag
indicates that an IP route is up.
- links to filtering criteria/access lists associated with the
route
- interface: such as eth0 for the first Ethernet card, eth1 for the
second Ethernet card, etc.
Routing tables are also a key aspect of
certain security operations, such as unicast reverse path forwarding (uRPF) In this technique, which has
several variants, the router also looks up, in the routing table, the source address of the packet. If
there exists no route back to the source address, the packet is assumed to
be malformed or involved in a network attack, and is dropped.
|
Network id
|
Cost
|
Next hop
|
|
........
|
........
|
........
|
|
........
|
........
|
........
|
FIGURE
: ROUTING TABLE
Static Routing
Table
A static routing table contains
information entered manually. The administrator enters the route for each
destination into the table. When a table is created, it cannot update automatically
when there is a change in the Internet. The table must be manually altered by
the administrator.
A static routing table can be
used in a small internet that does not change very often, or in an
experimental internet for troubleshooting. It is poor strategy to use a
static routing table in a big internet such as the Internet.
Dynamic
Routing Table
A dynamic routing table is
updated periodically by using one of the dynamic routing protocols such as
RIP, OSPF, or BGP. Whenever there is a change in the Internet, such as a
shutdown of a router or breaking of a link, the dynamic routing protocols
update all the tables in the routers (and eventually in the host)
automatically. The routers in a big internet such as the Internet need to
be updated dynamically for efficient delivery of the IP packets.
FIGURE : AUTONOMOUS SYSTEM
Autonomous System
Within the Internet, an autonomous system (AS)
is a collection of connected Internet Protocol (IP) routing prefixes under the control of one or
more network operators that presents a common, clearly defined routing
policy
to the Internet.
Originally the definition required
control by a single entity, typically an Internet service provider or a very large organization with independent
connections to multiple networks, that adhere to a single and clearly
defined routing policy, as originally defined in RFC
1771.
The newer definition in RFC 1930 came into use because multiple
organizations can run BGP using private AS numbers to an ISP that
connects all those organizations to the Internet. Even though there may be
multiple autonomous systems supported by the ISP, the Internet only sees
the routing policy of the ISP. That ISP must have an officially registered autonomous
system number (ASN).
Intra- and Interdomain Routing
Today, an internet can be so
large that one routing protocol cannot handle the task of updating the
routing tables of all routers. For this reason, an internet is divided into
autonomous systems. An autonomous system (AS) is a group of networks and
routers under the authority of a single administration. Routing inside an
autonomous system is referred to as intradomain routing. Routing between
autonomous systems is referred to as interdomain routing. Each autonomous
system can choose one or more intradomain routing protocols to handle
routing inside the autonomous system. However, only one interdomain routing
protocol handles routing between autonomous systems.
Distance-vector routing protocol [RGPV/Dec
2010]
In computer communication theory relating to packet-switched networks, a distance-vector routing protocol
is one of the two major classes of routing protocols, the other major class being the link-state protocol. Distance-vector routing protocols use
the Bellman–Ford algorithm
to calculate paths.
A distance-vector routing protocol
requires that a router informs its neighbors of topology changes
periodically. Compared to link-state protocols, which require a router to inform all
the nodes in a network of topology changes, distance-vector routing
protocols have less computational complexity and message overhead.
The term distance vector refers to the fact that the protocol
manipulates vectors (arrays) of distances to other nodes in the
network. The vector distance algorithm was the original ARPANET routing
algorithm and was also used in the internet under the name of RIP (routing
internet protocol).
Examples of distance-vector routing
protocols include RIPv1 and RIPv2 and IGRP.
Method
Routers
using distance-vector protocol do not have knowledge of the entire path to
a destination. Instead they use two methods:
- Direction in which router or exit
interface a packet should be forwarded.
- Distance from its destination
Distance-vector
protocols are based on calculating the direction and distance to any link
in a network. "Direction" usually means the next hop address and
the exit interface. "Distance" is a measure of the cost to reach
a certain node. The least cost route between any two nodes is the route
with minimum distance. Each node maintains a vector (table) of minimum
distance to every node. The cost of reaching a destination is calculated
using various route metrics. RIP uses the hop count of the destination
whereas IGRP takes into account other information
such as node delay and available bandwidth.
Updates are performed periodically in a
distance-vector protocol where all or part of a router's routing table is
sent to all its neighbors that are configured to use the same
distance-vector routing protocol. RIP supports cross-platform distance
vector routing whereas IGRP is a Cisco
Systems
proprietary distance vector routing protocol. Once a router has this
information it is able to amend its own routing table to reflect the changes
and then inform its neighbors of the changes. This process has been
described as ‘routing by rumor’ because routers are relying on the
information they receive from other routers and cannot determine if the
information is actually valid and true. There are a number of features
which can be used to help with instability and inaccurate routing
information.
EGP and BGP are not pure distance-vector routing
protocols because a distance-vector protocol calculates routes based only
on link costs whereas in BGP, for example, the local route preference value
takes priority over the link cost.
Count-to-infinity problem
The Bellman–Ford algorithm does not prevent routing
loops
from happening and suffers from the count-to-infinity problem. The
core of the count-to-infinity problem is that if A tells B that it has a
path somewhere, there is no way for B to know if the path has B as a part
of it. To see the problem clearly, imagine a subnet connected like
A–B–C–D–E–F, and let the metric between the routers be "number of
jumps". Now suppose that A is taken offline. In the
vector-update-process B notices that the route to A, which was distance 1, is
down – B does not receive the vector update from A. The problem is, B also
gets an update from C, and C is still not aware of the fact that A is down
– so it tells B that A is only two jumps from C (C to B to A), which is
false. This slowly propagates through the network until it reaches infinity
(in which case the algorithm corrects itself, due to the relaxation
property of Bellman–Ford).
Workarounds
and solutions
RIP uses the split horizon with poison
reverse
technique to reduce the chance of forming loops and uses a maximum number
of hops to counter the 'count-to-infinity' problem. These measures avoid
the formation of routing loops in some, but not all, cases. The addition of
a hold time (refusing route updates for a few minutes after a route
retraction) avoids loop formation in virtually all cases, but causes a
significant increase in convergence times.
More recently, a number of loop-free
distance vector protocols have been developed — notable examples are EIGRP, DSDV and Babel. These avoid loop formation in all
cases, but suffer from increased complexity, and their deployment has been
slowed down by the success of link-state routing protocols such as OSPF.
BELLMAN
FORD ALGORITHM [RGPV/Jun 2006 / Dec 2008/Jun 2011/ Dec 2012/ Dec 2013]
FIGURE
: NETWORK
The table for node A shows
how we can reach any node from this node. For example, our least cost to
reach node E is 6. The route passes through C.
Initialization
The tables in Figure are
stable; each node knows how to reach any other node and the cost. At the
beginning, however, this is not the case. Each node can know only the
distance between itself and its immediate neighbors, those directly
connected to it.
So for the moment, we assume
that each node can send a message to the immediate neighbors and find the
distance between itself and these neighbors. Figure shows the initial
tables for each node. The distance for any entry that is not a neighbor is
marked as infinite (unreachable).
Sharing
The whole idea of distance
vector routing is the sharing of information between neighbors. Although
node A does not know about node E, node C does. So if node C shares its
routing table with A, node A can also know how to reach node E. On the
other hand, node C does not know how to reach node D, but node A does. If node A shares its routing table with node
C, node C also knows how to reach node D. In other words, nodes A and C, as
immediate neighbors, can improve their routing tables if they help each other.
There is only one problem. How much of the table must be shared with each neighbor?
A node is not aware of a neighbor's table. The best solution for each node is
to send its entire table to the neighbor and let the neighbor decide what
part to use and what part to discard. However, the third column of a table
(next stop) is not useful for the neighbor. When the neighbor receives a
table, this column needs to be replaced with the sender's name. If any of the rows can be used, the next
node is the sender of the table. A node therefore can send only the first
two columns of its table to any neighbor. In other words, sharing here
means sharing only the first two columns.
Updating
When a node receives a
two-column table from a neighbor, it needs to update its routing table.
Updating takes three steps:
1. The receiving node needs
to add the cost between itself and the sending node to each value in the
second column. The logic is clear. If
node
C claims that its distance to a destination is x mi, and the
distance between A and C is y mi,
then
the distance between A and that destination, via C, is x + y mi.
2. The receiving node needs
to add the name of the sending node to each row as the third column if the
receiving node uses information from any row. The sending node is the next
node in the route.
3. The receiving node needs
to compare each row of its old table with the corresponding row of the
modified version of the received table.
a. If
the
next-node entry is different, the receiving node chooses the row with the smaller
cost. If there is a tie, the old one is kept.
b. If
the
next-node entry is the same, the receiving node chooses the new row. For example,
suppose node C has previously advertised a route to node X with distance 3.
Suppose that now there is no path between C and X; node C now advertises this
route with a distance of infinity. Node A must not ignore this value even
though its old entry is smaller. The old route does not exist any more. The
new route has a distance of infinity.
FIGURE
: BELLMAN FORD ALGORITHM
There are several points we
need to emphasize here. First, as we know from mathematics, when we add any
number to infinity, the result is still infinity. Second, the modified
table shows how to reach A from A via C.
If
A needs to reach itself via C, it needs to go to C and come back, a
distance of 4. Third, the only benefit from this updating of node A is the
last entry, how to reach E. Previously, node A did not know how to reach E
(distance of infinity); now it knows that the cost is 6 via C.
Each node can update its
table by using the tables received from other nodes. In a short time, if
there is no change in the network itself, such as a failure in a link, each
node reaches a stable condition in which the contents of its table remains
the same.
When to Share
The question now is, When
does a node send its partial routing table (only two columns) to all its
immediate neighbors? The table is sent both periodically and when there is
a change in the table.
Periodic
Update
A node sends its routing
table, normally every 30 s, in a periodic update. The period depends on the
protocol that is using distance vector routing.
Triggered
Update
A node sends its two-column
routing table to its neighbors anytime there is a change in its routing
table. This is called a triggered update. The change can result from the
following.
1.
A
node receives a table from a neighbor, resulting in changes in its own
table after updating.
2.
A
node detects some failure in the neighboring links which results in a
distance change to infinity.
RIP
The Routing Information
Protocol (RIP) is an intradomain routing protocol used
inside an autonomous system.
It is a very simple protocol based on distance vector routing. RIP
implements distance vector routing directly with some considerations:
1. In an autonomous system,
we are dealing with routers and networks (links). The routers have routing
tables; networks do not.
2. The destination in a
routing table is a network, which means the first column
defines a network address.
3. The metric used by RIP is
very simple; the distance is defined as the number of links (networks) to
reach the destination. For this reason, the metric in RIP is called a hop
count.
4. Infinity is defined as 16,
which means that any route in an autonomous system using RIP cannot have
more than 15 hops.
5. The next-node column
defines the address of the router to which the packet is to be sent to
reach its destination.
Figure shows an autonomous
system with seven networks and four routers. The
table of each router is also
shown. Let us look at the routing table for Rl. The table has seven entries
to show how to reach each network in the autonomous system. Router Rl is directly
connected to networks 130.10.0.0 and 130.11.0.0, which means that there are
no next-hop entries for these two networks. To send a packet to one of the
three networks at the far left, router Rl needs to deliver the packet to
R2. The next-node entry for these three networks is the interface of router
R2 with IP address 130.10.0.1. To send a packet to the two networks at the
far right, router Rl needs to send the packet to the interface of router R4
with IP address 130.11.0.1.
Link State Routing [RGPV/Dec 2009/ Jun 2010]
Link state routing has a
different philosophy from that of distance vector routing. In link state
routing, if each node in the domain has the entire topology of the domain the
list of nodes and links, how they are connected including the type, cost
(metric), and condition of the links (up or down)-the node can use
Dijkstra's algorithm to build a routing table.
FIGURE:
LINK STATE ROUTING
The figure shows a simple
domain with five nodes. Each node uses the same topology to create a
routing table, but the routing table for each node is unique because the
calculations are based on different interpretations of the topology. This
is analogous to a city map. While each person may have the same map, each
needs to take a different route to reach her specific destination.
The topology must be dynamic,
representing the latest state of each node and each link. If there are changes in any point in the
network (a link is down, for example), the topology must be updated for
each node.
How can a common topology be
dynamic and stored in each node? No node can
know the topology at the
beginning or after a change somewhere in the network. Link state routing is
based on the assumption that, although the global knowledge about the topology
is not clear, each node has partial knowledge: it knows the state (type,
condition, and cost) of its links. In
other words, the whole topology can be compiled from the partial
knowledge of each node. Figure shows the same domain as in Figure, indicating
the part of the knowledge belonging to each node.
FIGURE:
LINK STATE KNOWLEDGE
Node A knows that it is
connected to node B with metric 5, to node C with metric 2, and to node D
with metric 3. Node C knows that it is connected to node A with metric 2, to
node B with metric 4, and to node E with metric 4. Node D knows that it is
connected only to node A with metric 3. And so on. Although there is an
overlap in the knowledge, the overlap guarantees the creation of a common
topology-a picture of the whole domain for each node.
Dijkstra
Algorithm[RGPV/Dec 2007, Dec 2010,Dec 2012]
FIGURE
: DIJKSTRA ALGORITHM FLOW CHART
FIGURE
: DIJKSTRA ALGORITHM
1. We make node A the root of
the tree and move it to the tentative list. Our two lists are Permanent
list: empty Tentative list: A(O)
2. Node A has the shortest
cumulative cost from all nodes in the tentative list. We move A to the permanent
list and add all neighbors of A to the tentative list. Our new lists are
Permanent list: A(O)
Tentative list: B(5), C(2), D(3)
3. Node C has the shortest
cumulative cost from all nodes in the tentative list. We move C to the permanent list. Node C has three neighbors, but node A is already processed, which makes the
unprocessed neighbors just B and E. However, B is already in the tentative
list with a cumulative cost of 5. Node A could also reach node B through C
with a cumulative cost of 6. Since 5 is less than 6, we keep node B with a cumulative
cost of 5 in the tentative list and do not replace it. Our new lists are
Permanent list: A(O), e(2) Tentative list: B(5), 0(3), E(6)
4. Node D has the shortest
cumulative cost of all the nodes in the tentative list. We move D to the
permanent list. Node D has no unprocessed neighbor to be added to the
tentative list. Our new lists are
Permanent list: A(O), C(2),
0(3) Tentative list: B(5), E(6)
5. Node B has the shortest
cumulative cost of all the nodes in the tentative list. We move B to the
permanent list. We need to add all unprocessed neighbors of B to the tentative
list (this is just node E). However, E(6) is already in the list with a
smaller cumulative cost. The cumulative cost to node E, as the neighbor of
B, is 8. We keep node E(6) in the tentative list. Our new lists are
Permanent list: A(O), B(5),
C(2), 0(3) Tentative list: E(6)
6. Node E has the shortest
cumulative cost from all nodes in the tentative list. We move E to the
permanent list. Node E has no neighbor. Now the tentative list is empty. We
stop; our shortest path tree is ready. The final lists are Permanent list:
A(O), B(5), C(2), D(3), E(6) Tentative list: empty
OSPF
The Open Shortest Path First
or OSPF protocol is an intradomain routing protocol based on link state
routing. Its domain is also an autonomous system.
Areas To handle routing
efficiently and in a timely manner, OSPF divide an autonomous system into
areas. An area is a collection of networks, hosts, and routers all contained
within an autonomous system. An autonomous system can be divided into many
different areas. All networks inside an area must be connected. Routers
inside an area flood the area with routing information. At the border of an
area, special routers called area border routers summarize the information
about the area and send it to other areas. Among the areas inside an
autonomous system is a special area called the backbone; all the
areas inside an autonomous system must be connected to the backbone. In
other words, the backbone serves as a primary area and the other areas as
secondary areas. This does not mean that the routers within areas cannot be
connected to each other, however. The routers inside the backbone are
called the backbone routers. Note that a backbone router can also be an
area border router. If, because
of some problem, the connectivity between a backbone and an area is broken,
a virtual link between routers must be created by an administrator to allow
continuity of the functions of the backbone as the primary area. Each area
has area identification. The area identification of the backbone is zero.
Path Vector Routing
Distance vector and link
state routing are both intradomain routing protocols. They can be used
inside an autonomous system, but not between autonomous systems. These two protocols
are not suitable for interdomain routing mostly because of scalability.
Both of these routing protocols become intractable when the domain of
operation becomes large. Distance vector routing is subject to instability
if there are more than a few hops in the domain of operation. Link state
routing needs a huge amount of resources to calculate routing tables. It also creates heavy traffic because of
flooding. There is a need for a third routing protocol which we call path
vector routing. Path vector routing proved to be useful for interdomain
routing. The principle of path vector routing is similar to that of
distance vector routing. In path vector routing, we assume that there is
one node (there can be more, but one is enough for our conceptual discussion)
in each autonomous system that acts on behalf of the entire autonomous system.
Let us call it the speaker node. The speaker node in an AS creates a routing
table and advertises it to speaker nodes in the neighboring ASs. The idea
is the same as for distance vector routing except that only speaker nodes
in each AS can communicate with each other. However, what is advertised is
different. A speaker node advertises the path, not the metric of the nodes,
in its autonomous system or other autonomous systems
BGP
Border Gateway Protocol (BGP)
is an interdomain routing protocol using path vector routing. It first
appeared in 1989 and has gone through four versions. Types of Autonomous
Systems As we said before, the Internet is divided into hierarchical domains
called autonomous systems. For example, a large corporation that manages
its own network and has full control over it is an autonomous system. A
local ISP that provides services to local customers is an autonomous
system. We can divide autonomous systems into three categories: stub,
multihomed, and transit.
Stub AS. A stub AS has only one
connection to another AS. The interdomain data
traffic in a stub AS can be
either created or terminated in the AS. The hosts in the AS can send data
traffic to other ASs. The hosts in the AS can receive data coming from hosts
in other ASs. Data traffic, however, cannot pass through a stub AS. A stub
AS is either a source or a sink. A good example of a stub AS is a small
corporation or a small local ISP.
Multihomed
AS.
A multihomed AS has more than one connection to other ASs,
but it is still only a source
or sink for data traffic. It can receive data traffic from
more than one AS. It can send data traffic to more than one
AS, but there is no transient traffic. It does not allow data coming from
one AS and going to another AS to pass through. A good example of a
multihomed AS is a large corporation that is connected to more than one
regional or national AS that does not allow transient traffic.
Transit
AS.
A transit AS is a multihomed AS that also allows transient traffic. Good examples
of transit ASs are national and international ISPs (Internet backbones).
|
