Data Communication and
Networking
Chapter 2 – Part 1
UNIT- I : Chapter 2
Routing protocols for wired network
Unicast routing protocols: Shortest Path, Flooding, Distance
Vector routing (DVR), Link state routing, Multicast routing
protocols. Interior gateway protocol: Open Shortest Path First
(OSPF), Exterior gateway protocol: Border Gateway Protocol
(BGP).
Network Layer: Delivery, Forwarding, and Routing
Delivery - the way a packet is handled.
Forwarding - the way a packet is delivered to the next station.
Routing - the way routing tables are created to forwarding.
Routing protocols - continuously update the routing tables.
22.1 DELIVERY
The network layer supervises the handling of the packets by the
underlying physical networks.
Direct Versus Indirect Delivery
The delivery of a packet by using two different methods, direct
and indirect, as shown in Figure 22.1.
Direct and Indirect Delivery
Figure 22.1 Direct and indirect delivery
1. 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.
Process – The sender can extract the network address of the
destination (using the mask), and
compare this address with the connected network addresses.
If a match is found, the delivery is direct.
2. Indirect Delivery
If the destination host is not on the same network, the packet is
delivered indirectly.
the packet goes from router to router until its final destination.
A delivery always involves one direct delivery but zero or more
indirect deliveries.
22.2 FORWARDING
Forwarding, place the packet in its route to its destination.
When a host/router has a packet to send/forward, it looks at
routing table to find the route.
As the number of entries increases, the table would be
inefficient.
1. Forwarding Techniques
Several techniques to reduce the size of the routing table and
also handle security issues.
(i). Next-Hop Method Versus Route Method
One technique to reduce the contents is the next-hop method.
Here, the routing table holds only the address of the next hop and
the entries must be consistent.
Figure 22.2 shows how routing tables can be simplified.
(i). Next-Hop Method Versus Route Method
Figure 22.2 Route method versus next-hop method
(ii). Network-Specific Method Versus Host-Specific Method
Figure 22.3 Host-specific versus network-specific method
(ii). Network-Specific Method Versus Host-Specific Method
Reducing and simplifying the searching process.
Here, instead of having an entry for every destination host, we
have only one entry
that defines the address of the destination network.
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.
Figure 22.3 shows the concept.
Host-specific routing is used for checking the route or providing
security measures.
(iii). Default Method
Figure 22.4 Default method
(iii). Default Method
In Figure 22.4 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 [Link]).
Figure 22.4 Default method
2. Forwarding Process
Figure 22.5 Simplified forwarding module in classless address
In classless addressing, the routing table needs to have one row
of information for each block involved.
The table needs to be searched based on the network address.
But the destination address in the packet gives no clue about the
network address.
To solve the problem, we need to include the mask (/n) in the
table.
we need to have an extra column that includes the mask.
Figure 22.5 shows a simple forwarding module for classless
addressing.
In classless addressing, we need at least four columns in a
routing table.
Example 1
Make a routing table for router R1, using the configuration in
Figure 22.6.
Figure 22.6 Configuration for Example 22.1
Solution
Table 22.1 shows the corresponding table.
Table 22.1 Routing table for router RI in Figure 22.6
Example 2
Show the forwarding process if a packet arrives at R1 in Figure 22.6
with the destination address [Link].
Solution
The router performs the following steps:
1. The first mask (/26) is applied to the destination address.
The result is [Link], which does not match the
corresponding network address.
2. The second mask (/25) is applied to the destination
address. The result is [Link], which matches the
corresponding network address.
The next-hop address and the interface number m0 are passed to
ARP for further processing.
Highest mask value
Example 3
Show the forwarding process if a packet arrives at R1 in
Figure 22.6 with the destination address [Link].
Solution
The router performs the following steps:
1. The first mask (/26) is applied to the destination
address. The result is [Link], which does not
match the corresponding network address.
2. The second mask (/25) is applied to the destination address.
The result is [Link], which does not match the corresponding
network address (row 2).
[Link] third mask (/24) is applied to the destination
address. The result is [Link], which matches the
corresponding network address. The destination
address of the packet and the interface number m3 are
passed to ARP.
Example 4
Show the forwarding process if a packet arrives at R1 in Figure 22.6
with the destination address [Link].
Solution
This time all masks are applied, one by one, to the destination address,
but no matching network address is found.
When it reaches the end of the table, the module gives the next-hop
address [Link] and interface number m2 to ARP.
This is probably an outgoing package that needs to be sent, via the
default router, to someplace else in the Internet.
(i). Address Aggregation
When we use classless addressing, the number of routing table
entries will increase.
Because the classless addressing divide the whole address space
into manageable blocks.
This increases in the amount of time needed to search the table.
To solve, the idea of address aggregation was designed.
In Figure 22.7 we have two routers.
Figure 22.7 Address aggregation
Click to add text
Router Rl is connected to networks of four organizations that
each use 64 addresses.
Router Rl has a longer routing table to route correctly.
Router R2, can have a very small routing table.
For R2, any packet with destination [Link] to [Link]
is sent out from interface m0 regardless of the organization
number.
This is called address aggregation.
The four organizations address blocks are aggregated.
But the network for each organization is independent.
In addition, we can have several levels of aggregation.
(ii). Longest Mask Matching
What happens if one of the organizations in Figure 22.7 is not
geographically close to the other three?
For example, if organization 4 cannot be connected to router Rl,
can we still use the address aggregation and still assign block
[Link]/26 to organization 4?
It is possible in classless addressing using longest mask
matching.
The routing table is sorted from the longest to the shortest
mask.
In other words, if there are three masks /27, /26, and /24, the
mask /27 must be the first entry and /24 must be last.
Figure 22.8 shows the situation.
Figure 22.8 Longest mask matching
Suppose a packet arrives for organization 4 with destination
address [Link].
The first mask at router R2 is applied, which gives the network
address [Link].
The packet is routed correctly from interface ml and reaches
organization 4.
If, however, the routing table was not stored with the longest
prefix first, applying the /24 mask would result in the incorrect
routing of the packet to router Rl.
(iii). Hierarchical Routing
To solve the problem of gigantic routing tables, we can create a
sense of hierarchy in the routing tables.
The Internet is divided into international and national ISPs.
National ISPs are divided into regional ISPs, and regional ISPs
are divided into local ISPs.
Like Internet architecture, the routing table can decrease in size.
For example, a local ISP can be assigned a single, but large
block of addresses with a certain prefix length.
The local ISP can divide this block into smaller blocks of
different sizes, and
can assign these to individual users and organizations.
Example
As an example of hierarchical routing, let us consider Figure 22.9. A
regional ISP is granted 16,384 addresses starting from [Link].
The regional ISP has decided to divide this block into four subblocks,
each with 4096 addresses. Three of these subblocks are assigned to
three local ISPs; the second subblock is reserved for future use. Note
that the mask for each block is /20 because the original block with
mask /18 is divided into 4 blocks.
The first local ISP has divided its assigned subblock into 8 smaller
blocks and assigned each to a small ISP. Each small ISP provides
services to 128 households, each using four addresses.
The second local ISP has divided its block into 4 blocks and has
assigned the addresses to four large organizations.
The third local ISP has divided its block into 16 blocks and assigned
each block to a small organization. Each small organization has 256
addresses, and the mask is /24.
There is a sense of hierarchy in this configuration. All routers in the
Internet send a packet with destination address [Link] to
[Link] to the regional ISP.
Figure 22.9 Hierarchical routing with ISPs
(iv). Geographical Routing
To decrease the size even further, hierarchical routing include
geographical routing.
We must divide the entire address space into a few large blocks.
We assign a block to North America, a block to Europe, a block
to Asia, a block to Africa, and so on.
The routers of ISPs outside Europe will have only one entry for
packets to Europe in their routing tables.
The routers of ISPs outside North America will have only one
entry for packets to North America in their routing tables.
And so on.
3. Routing Table
The routing table can be either static or dynamic.
(i). Static Routing Table
Contains information entered manually.
The administrator enters the route for each destination.
When there is a change, the table must be manually altered.
A static routing table can be used in a small internet that does not
change very often.
(ii). Dynamic Routing Table
Updated periodically by using one of the dynamic routing
protocols such as RIP, OSPF, or BGP.
Whenever there is a change, the dynamic routing protocols
update all the tables in the routers automatically.
(iii). Format
A routing table for classless addressing has a minimum of four
columns, Figure 22.10.
Figure 22.10 Common fields in a routing table
Mask - defines the mask applied for the entry.
Network address - defines the network address to which the
packet is finally delivered.
For host-specific routing, it defines the destination host address.
Next-hop address - defines the address of the next-hop router.
Interface - shows the name of the interface.
Reference count - gives the number of users of this route.
Use - the number of packets transmitted through this router.
Flags - defines up to five flags. Flags are on/off switches.
U (up) - indicates the router is up and running. If not present, the
packet cannot be forwarded and is discarded.
G (gateway) - the destination is in another network. If not
present, the destination is in this network (direct delivery).
H (host-specific) - the entry in the network address field is a
host-specific address, otherwise the network address.
D (added by redirection) - routing information has been added
to the host routing table by a redirection message from ICMP.
M (modified by redirection) - the routing information has been
modified by a redirection message from ICMP.
(iv). Utilities
Used to find the routing information and the contents of a
routing table.
Example 22.6
One utility that can be used to find the contents of a routing
table for a host or router is netstat in UNIX or LINUX.
The table shows the list of the contents of a default server.
We have used two options, r and n.
The option r indicates that we are interested in the routing table,
The option n indicates that we are looking for numeric
addresses.
Note that this is a routing table for a host.
The destination column defines the network address.
The term gateway used by UNIX is synonymous with
router.
defines the address of the next hop.
The value [Link] shows that the delivery is direct.
The flag of G, means that the destination can be reached
through a router (default router).
The Iface defines the interface.
More information about the IP address and physical address of the
server can be found by using the ifconfig command on the given
interface (eth0).
Figure 22.11 Configuration ofthe server for Example 22.6
22.3 UNICAST ROUTING PROTOCOLS
A routing table can be either static or dynamic.
A static table is one with manual entries.
A dynamic table, is updated automatically when there is a
change.
Today, an internet needs dynamic routing tables.
Routing protocols have been created for dynamic routing tables.
It is a rules and procedures that inform each other of changes.
The protocols also include procedures for combining information
received from other routers.
1. Optimization
A router receives a packet from a network and passes it to
another network.
A router is usually attached to several networks.
When it receives a packet, to which network should it pass?
The decision is based on optimization:
Which of the available pathways is the optimum pathway?
One approach is to assign a cost (metrics) for passing.
Metric assignment to network depends on the type of protocol.
The Routing Information Protocol (RIP), treat all networks as
equals, one hop count.
So if a packet passes through 10 networks, the total cost is 10
hop counts.
Open Shortest Path First (OSPF) protocol, allow the
administrator to assign a cost based on the type of service.
A route through a network can have different costs (metrics).
If maximum throughput is the desired type of service,
a satellite link has a lower metric than a fiber-optic line.
If minimum delay is the desired type of service,
a fiber-optic line has a lower metric than a satellite link.
Protocol, allows each router to have several routing tables
based on the required type of service.
In the Border Gateway Protocol (BGP), the criterion is the
policy, which can be set by the administrator.
The policy defines what paths should be chosen.
2. Intra- and Interdomain Routing
Since an internet is so large, one routing protocol cannot handle
the routing tables update of all routers.
For this reason, an internet is divided into autonomous systems.
Figure 22.12 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 intradomain routing.
Routing between autonomous systems is interdomain routing.
One or more intradomain routing protocols used to handle
routing inside the autonomous system.
However, only one interdomain routing protocol handles routing
between autonomous systems, Figure 22.12.
Several intradomain and interdomain routing protocols are in
use.
Figure 22.13 Popular routing protocols
Routing Information Protocol (RIP) is an implementation of
the distance vector protocol.
Open Shortest Path First (OSPF) is an implementation of the
link state protocol.
Border Gateway Protocol (BGP) is an implementation of the
path vector protocol.