NETWORK-LAYER SERVICES
Packetizing
Encapsulating the payload (data received from upper layer) in a network-layer packet at the
source and decapsulating the payload from the network-layer packet at the destination.
Routing
The network layer is responsible for routing the packet from its source to the destination.
Forwarding
Forwarding can be defined as the action applied by each router when a packet arrives at one
of its interfaces. The forwarding process is as shown in the following figure.
PACKET SWITCHING
Datagram Approach: Connectionless Service
A connectionless packet-switched network is as shown in the following figure
Each packet is routed based on the information contained in its header: source and destination
addresses.
The destination address defines where it should go; the source address defines where it comes
from.
The router in this case routes the packet based only on the destination address.
The forwarding process in a router when used in a connectionless network is as shown in the
following figure
Virtual-Circuit Approach: Connection-Oriented Service
Refer Module 1
IPV4 ADDRESSES
Address Space
An address space is the total number of addresses used by the protocol. If a protocol uses b
bits to define an address, the address space is 2b because each bit can have two different
values (0 or 1). IPv4 uses 32-bit addresses, which means that the address space is 232 or
4,294,967,296.
Three different notations in IPv4 addressing are as shown in the following figure
A 32-bit IPv4 address is hierarchical as shown in the following figure, divided only into two
parts. The first part of the address, called the prefix, defines the network; the second part of
the address, called the suffix, defines the node (connection of a device to the Internet).
Classful Addressing
Occupation of the address space in classful addressing is as shown in the following figure
Classless Addressing
In classless addressing, the whole address space is divided into variable length blocks as
shown in the following figure. The prefix in an address defines the block (network); the
suffix defines the node (device).
Prefix Length: Slash Notation
The prefix length, n, is added to the address, separated by a slash as shown in the following
figure . The notation is informally referred to as slash notation and formally as classless
interdomain routing or CIDR.
Problems: Refer class notes
Dynamic Host Configuration Protocol (DHCP)
Address assignment in an organization can be done automatically using the Dynamic Host
Configuration Protocol (DHCP).
The DHCP Message Format is as shown in the following figure
The operation of DHCP is as shown in the following figure.
1. The joining host creates a DHCPDISCOVER message in which only the transaction-
ID field is set to a random number. This message is encapsulated in a UDP user
datagram with the source port set to 68 and the destination port set to 67. The user
datagram is encapsulated in an IP datagram with the source address set to [Link]
(“this host”) and the destination address set to [Link].
2. The DHCP server or servers (if more than one) responds with a DHCPOFFER
message in which the your address field defines the offered IP address for the joining
host and the server address field includes the IP address of the server.
3. The joining host receives one or more offers and selects the best of them. The joining
host then sends a DHCPREQUEST message to the server that has given the best
offer.
4. Finally, the selected server responds with a DHCPACK message to the client if the
offered IP address is valid. If the server cannot keep its offer (for example, if the
address is offered to another host in between), the server sends a DHCPNACK
message.
Network Address Translation (NAT)
The technology allows a site to use a set of private addresses for internal communication and
a set of global Internet addresses (at least one) for communication with the rest of the world.
The following figure shows the implementation of NAT
The address translation is as shown in the following figure. All of the outgoing packets go
through the NAT router, which replaces the source address in the packet with the global NAT
address. All incoming packets also pass through the NAT router, which replaces the
destination address in the packet (the NAT router global address) with the appropriate private
address.
The address translation is carried out with the help of Translation Table as shown in the
following table
ROUTING ALGORITHMS
Distance-Vector Routing
The distance vector can represent least-cost paths in a least-cost tree as shown in the
following figure.
The first distance vector for a network is as shown in the following figure.
Updating distance vectors is as shown in the following figure
The Distance-Vector Routing Algorithm is given by
Distance_Vector_Routing ( )
{
// Initialize (create initial vectors for the node)
D[myself ] = 0
for (y = 1 to N)
{
if (y is a neighbor)
D[y] = c[myself ][y]
else
D[y] = ∞
}
send vector {D[1], D[2], .... , D[N]} to all neighbours
// Update (improve the vector with the vector received from a neighbor)
repeat (forever)
{
wait (for a vector Dw from a neighbor w or any change in the link)
for (y = 1 to N)
{
D[y] = min [D[y], (c[myself ][w] + Dw[y ])] // Bellman-Ford equation
}
if (any change in the vector)
send vector {D[1], D[2], ... , D[N]} to all neighbours
}
}
Problem: Refer class notes
Link-State Routing
Each node needs to have a complete map of the network, which means it needs to know the
state of each link. The collection of states for all links is called the link-state database
(LSDB) as shown in the following figure
LSPs created and sent out by each node to build LSDB is as shown in the following figure
To create least cost tree from each node Dijkstra’s algorithm is used. The Dijkstra’s
algorithm is given by
Dijkstra’s Algorithm ( )
{
// Initialization
Tree = {root} // Tree is made only of the root
for (y = 1 to N) // N is the number of nodes
{
if (y is the root)
D[y] = 0 // D[y] is shortest distance from root to node y
else if (y is a neighbor)
D[y] = c[root][y] // c[x][y] is cost between nodes x and y in LSDB
else
D[y] = ∞
}
// Calculation
repeat
{
find a node w, with D[w] minimum among all nodes not in the Tree
Tree = Tree U {w} // Add w to tree
// Update distances for all neighbors of w
for (every node x, which is a neighbor of w and not in the Tree)
{
D[x] = min{D[x], (D[w] + c[w][x])}
}
} until (all nodes included in the Tree)
} // End of Dijkstra
Path-Vector Routing
The best route is determined by the source using the policy it imposes on the route. In other
words, the source can control the path.
Spanning trees in path-vector routing are shown below
We can define this equation as
Path(x, y) = best {Path(x, y), [(x + Path(v, y)]} for all v’s in the internet.
Path vectors made at booting time are shown below
Updating path vectors as shown below
Path-vector algorithm for a node is given by
Path_Vector_Routing ( )
{
// Initialization
{
for (y = 1 to N)
{
if (y is myself)
Path[y] = myself
else if (y is a neighbor)
Path[y] = myself + neighbor node
else
Path[y] = empty
}
Send vector {Path[1], Path[2]......Path[y]} to all neighbours
// Update
repeat (forever)
{
wait (for a vector Pathw from a neighbor w)
for (y = 1 to N)
{
if (Pathw includes myself)
discard the path
else
Path[y] = best {Path[y], (myself + Pathw[y])}
}
If (there is a change in the vector)
Send vector {Path[1], Path[2], ..... , Path[y]} to all neighbours
}
}
UNICAST ROUTING PROTOCOLS
Routing Information Protocol (RIP)
Hop counts in RIP is as shown below
The hop count is the number of networks between router and destination network.
The forwarding table for each router in the above network is given by
The RIP message format is given by
The RIP algorithm is given by
1. A router needs to send the whole contents of its forwarding table in a response
message.
2. The receiver adds one hop to each cost and changes the next router field to the address
of the sending router. We call each route in the modified forwarding table the
received route and each route in the old forwarding table the old route.
3. The received router selects the old routes as the new ones except in the following
three cases:
If the received route does not exist in the old forwarding table, it
should be added to the route.
If the cost of the received route is lower than the cost of the old one,
the received route should be selected as the new one.
If the cost of the received route is higher than the cost of the old one,
but the value of the next router is the same in both routes, the received
route should be selected as the new one.
Example of an autonomous system using RIP is given by
Open Shortest Path First (OSPF)
Metric in OSPF is given by
Each link (network) can be assigned a weight based on the throughput, round-trip time,
reliability, and so on.
Forwarding tables in OSPF are shown below
Areas in an autonomous system are as shown below
Each router in an area needs to know the information about the link states not only in its area
but also in other areas. For this reason, one of the areas in the AS is designated as the
backbone area, responsible for gluing the areas together.
Five different LSPs are explained below
1. Router link
A router link advertises the existence of a router as a node.
A transient link announces a link to a transient network, a network that is connected to the
rest of the networks by one or more routers.
A stub link advertises a link to a stub network, a network that is not a through network.
A point-to-point link should define the address of the router at the end of the point-to-point
line.
2. Network link
A network link advertises the network as a node.
One of the routers is assigned as the designated router and does the advertising.
3. Summary link to network
This is done by an area border router; it advertises the summary of links collected by the
backbone to an area or the summary of links.
4. Summary link to AS
This is done by an AS router that advertises the summary links from other ASs to the
backbone area of the current AS, information which later can be disseminated to the areas so
that they will know about the networks in other ASs.
5. External link
This is also done by an AS router to announce the existence of a single network outside the
AS to the backbone area to be disseminated into the areas.
Border Gateway Protocol Version 4 (BGP4)
BGP is inter-domain protocol. The router uses the BGP to know how to reach networks
which belongs other AS.
There are two versions of BGP namely External BGP (eBGP) and Internal BGP (iBGP). The
eBGP is installed only in border routers. The iBGP is installed both in border routers and
remaining routers.
Router uses intra-domain protocols such as RIP or OSPF to know about how to reach
networks within their own autonomous systems.
Operation of External BGP (eBGP) is as shown in the following figure
The messages exchanged between border routers of autonomous systems.
1. The router R1 shares the information to R5 that N1, N2, N3 and N4 are reachable
from R1 which belongs to AS1.
2. The router R5 shares the information to R1 that N8 and N9 are reachable from R5
which belongs to AS2.
(Provide similar explanation to other messages)
Operation of Internal BGP (iBGP) is as shown in the following figure
1. The border router R1 shares messages to all routers in its autonomous system. The
message is networks N8 and N9 are reachable from R1.
(Provide similar explanation for other messages)
Multicast Link State (MOSPF)
A router goes through the following steps to forward a multicast packet received from source
S and to be sent to destination G (a group of recipients):
1. The router uses the Dijkstra’s algorithm to create a shortest-path tree with S as the
root and all destinations in the internet as the leaves. The root of the tree is the source
of the packet defined in the source address of the packet.
2. The router creates a shortest-path subtree with itself as the root of the subtree.
3. The shortest-path subtree is actually a broadcast subtree with the router as the root and
all networks as the leaves. The router now uses a strategy similar to the one we
describe in the case of DVMRP to prune the broadcast tree and to change it to a
multicast tree.
4. The router can now forward the received packet out of only those interfaces that
correspond to the branches of the multicast tree.
Example,