COMPUTER COMMUICATION AND NETWORK

Unit - 4
The Network Layer
➢ Network Layer design issues.
➢ Routing Algorithms
• Flooding
• Distance vector routing.
• Hierarchical routing .
• Link state routing .
• congestion

➢ Control Algorithms
• Leaky bucket.
• Token bucket algorithm
• Admission control
• Hop by hop choke packets.
 COMPUTER COMMUICATION AND NETWORK

✓ Network Layer design issues :

▪ The Network Layer is the third layer of the OSI model.
▪ It handles the service requests from the transport layer and further forwards the service request to the data link layer.
▪ The network layer translates the logical addresses into physical addresses.
▪ The network layer or layer 3 of the OSI (Open Systems Interconnection) model is concerned delivery of data packets
from the source to the destination across multiple hops or links.
▪ It is the lowest layer that is concerned with end − to − end transmission.
▪ The designers who are concerned with designing this layer needs to cater to certain issues.
▪ These issues encompasses the services provided to the upper layers as well as internal design of the layer.

The design issues can be elaborated under four heads −

▪ Store − and − Forward Packet Switching

▪ Services to Transport Layer
▪ Providing Connection Oriented Service
▪ Providing Connectionless Service
 COMPUTER COMMUICATION AND NETWORK

Store − and − Forward Packet Switching :

▪ The network layer operates in an environment that uses store and forward packet switching.
▪ The node which has a packet to send, delivers it to the nearest router.
▪ The packet is stored in the router until it has fully arrived and its checksum is verified for error detection.
▪ Once, this is done, the packet is forwarded to the next router.
▪ Since, each router needs to store the entire packet before it can forward it to the next hop, the mechanism is
called store − and − forward switching.

Services to Transport Layer :

▪ The network layer provides service its immediate upper layer, namely transport layer, through the network −
transport layer interface. The two types of services provided are −
▪ Connection − Oriented Service − In this service, a path is setup between the source and the destination, and all the
data packets belonging to a message are routed along this path.
▪ Connectionless Service − In this service, each packet of the message is considered as an independent entity and is
individually routed from the source to the destination.
 COMPUTER COMMUICATION AND NETWORK

The objectives of the network layer while providing these services are −
▪ The services should not be dependent upon the router technology.
▪ The router configuration details should not be of a concern to the transport layer.
▪ A uniform addressing plan should be made available to the transport layer, whether the network is a LAN, MAN or WAN.

Providing Connection Oriented Service :

▪ In connection − oriented services, a path or route called a virtual circuit is setup between the source and the
destination nodes before the transmission starts. All the packets in the message are sent along this route.
▪ Each packet contains an identifier that denotes the virtual circuit to which it belongs to.
▪ When all the packets are transmitted, the virtual circuit is terminated and the connection is released.
▪ An example of connection − oriented service is Multiprotocol Label Switching (MPLS).

Providing Connectionless Service :

▪ In connectionless service, since each packet is transmitted independently, each packet contains its routing information
and is termed as datagram.
▪ The network using datagrams for transmission is called datagram networks or datagram subnets.
▪ No prior setup of routes are needed before transmitting a message.
▪ Each datagram belong to the message follows its own individual route from the source to the destination. An example of
connectionless service is Internet Protocol or IP.
 COMPUTER COMMUICATION AND NETWORK

✓ Routing Algorithms :
▪ In order to transfer the packets from source to the destination, the network layer must determine the best
route through which packets can be transmitted.
▪ Whether the network layer provides datagram service or virtual circuit service, the main job of the network
layer is to provide the best route. The routing protocol provides this job.
▪ The routing protocol is a routing algorithm that provides the best path from the source to the destination. The
best path is the path that has the "least-cost path" from source to the destination.
▪ Routing is the process of forwarding the packets from source to the destination but the best route to send the
packets is determined by the routing algorithm.

Classification of a Routing algorithm

The Routing algorithm is divided into two categories:

1. Adaptive Routing algorithm
2. Non-adaptive Routing algorithm
 COMPUTER COMMUICATION AND NETWORK

1. Adaptive Routing algorithm :

▪ An adaptive routing algorithm is also known as dynamic routing algorithm.

▪ This algorithm makes the routing decisions based on the topology and network traffic.
▪ The main parameters related to this algorithm are hop count, distance and estimated transit time.
An adaptive routing algorithm can be classified into three parts:

▪ Centralized algorithm: It is also known as global routing algorithm as it computes the least-cost path between source and
destination by using complete and global knowledge about the network. This algorithm takes the connectivity between the
nodes and link cost as input, and this information is obtained before actually performing any calculation. Link state
algorithm is referred to as a centralized algorithm since it is aware of the cost of each link in the network.
▪ Isolation algorithm: It is an algorithm that obtains the routing information by using local information rather than gathering
information from other nodes.
▪ Distributed algorithm: It is also known as decentralized algorithm as it computes the least-cost path between source and
destination in an iterative and distributed manner. In the decentralized algorithm, no node has the knowledge about the
cost of all the network links.
 COMPUTER COMMUICATION AND NETWORK

2. Non-Adaptive Routing algorithm :

▪ Non Adaptive routing algorithm is also known as a static routing algorithm.

▪ When booting up the network, the routing information stores to the routers.
▪ Non Adaptive routing algorithms do not take the routing decision based on the network topology or network
traffic.

The Non-Adaptive Routing algorithm is of two types:

1. Flooding: In case of flooding, every incoming packet is sent to all the outgoing links except the one from
it has been reached. The disadvantage of flooding is that node may contain several copies of a
particular packet.

2. Random walks: In case of random walks, a packet sent by the node to one of its neighbors randomly.
An advantage of using random walks is that it uses the alternative routes very efficiently.
 COMPUTER COMMUICATION AND NETWORK

✓Flooding
▪ Flooding is a non-adaptive routing technique following this simple method: when a data packet arrives at a
router, it is sent to all the outgoing links except the one it has arrived on.
▪ For example, let us consider the network in the figure, having six routers that are connected through
transmission lines.

Using flooding technique −

▪ An incoming packet to A, will be sent to B, C and D.

▪ B will send the packet to C and E.
▪ C will send the packet to B, D and F.
▪ D will send the packet to C and F.
▪ E will send the packet to F.
▪ F will send the packet to C and E.
 COMPUTER COMMUICATION AND NETWORK

Types of Flooding :

Flooding may be of three types −

▪ Uncontrolled flooding − Here, each router unconditionally transmits the incoming data packets to all its neigh bours.
▪ Controlled flooding − They use some methods to control the transmission of packets to the neigh bours nodes. The two
popular algorithms for controlled flooding are Sequence Number Controlled Flooding (SNCF) and Reverse Path
Forwarding (RPF).
▪ Selective flooding − Here, the routers don't transmit the incoming packets only along those paths which are heading
towards approximately in the right direction, instead of every available paths.

Advantages of Flooding :

▪ It is very simple to setup and implement, since a router may know only its neigh bours.
▪ It is extremely robust. Even in case of malfunctioning of a large number routers, the packets find a way to reach the
destination.
▪ All nodes which are directly or indirectly connected are visited. So, there are no chances for any node to be left out. This
is a main criteria in case of broadcast messages.
▪ The shortest path is always chosen by flooding.
 COMPUTER COMMUICATION AND NETWORK

Limitations of Flooding :

▪ Flooding tends to create an infinite number of duplicate data packets, unless some measures are adopted to damp
packet generation.
▪ It is wasteful if a single destination needs the packet, since it delivers the data packet to all nodes irrespective of the
destination.
▪ The network may be clogged with unwanted and duplicate data packets. This may hamper delivery of other data
packets.
✓ Distance vector routing.
▪ The Distance vector algorithm is iterative, asynchronous and distributed:

▪ Distributed: It is distributed in that each node receives information from one or more of its directly attached
neighbors, performs calculation and then distributes the result back to its neighbors.
▪ Iterative: It is iterative in that its process continues until no more information is available to be exchanged between
neighbors.
▪ Asynchronous: It does not require that all of its nodes operate in the lock step with each other.
▪ The Distance vector algorithm is a dynamic algorithm.
▪ It is mainly used in ARPANET, and RIP.
▪ Each router maintains a distance table known as Vector.
 COMPUTER COMMUICATION AND NETWORK

✓ Hierarchical routing
▪ In hierarchical routing, the routers are divided into regions.
▪ Each router has complete details about how to route packets to destinations within its own region.
▪ But it does not have any idea about the internal structure of other regions.
▪ As we know, in both LS and DV algorithms, every router needs to save some information about other routers. When
network size is growing, the number of routers in the network will increase.
▪ Therefore, the size of routing table increases, then routers cannot handle network traffic as efficiently.
▪ To overcome this problem we are using hierarchical routing.
▪ In hierarchical routing, routers are classified in groups called regions.
▪ Each router has information about the routers in its own region and it has no information about routers in other
regions. So, routers save one record in their table for every other region.
▪ For huge networks, a two-level hierarchy may be insufficient hence, it may be necessary to group the regions into
clusters, the clusters into zones, the zones into groups and so on.
 COMPUTER COMMUICATION AND NETWORK

✓ Link state routing

Link state routing is a technique in which each router shares the knowledge of its neighborhood with every other router
in the internetwork.

The three keys to understand the Link State Routing algorithm:

▪ Knowledge about the neighborhood: Instead of sending its routing table, a router sends the information about its
neighborhood only. A router broadcast its identities and cost of the directly attached links to other routers.
▪ Flooding: Each router sends the information to every other router on the internetwork except its neighbors. This
process is known as Flooding. Every router that receives the packet sends the copies to all its neighbors. Finally, each
and every router receives a copy of the same information.
▪ Information sharing: A router sends the information to every other router only when the change occurs in the
information.
Link State Routing has two phases:

Reliable Flooding
▪ Initial state: Each node knows the cost of its neighbors.
▪ Final state: Each node knows the entire graph.
 COMPUTER COMMUICATION AND NETWORK

✓congestion
▪ A state occurring in network layer when the message traffic is so heavy that it slows down network response time.

Effects of Congestion :
▪ As delay increases, performance decreases.
▪ If delay increases, retransmission occurs, making situation worse.

Congestion control algorithms :

▪ Congestion Control is a mechanism that controls the entry of data packets into the network, enabling a better use of a
shared network infrastructure and avoiding congestive collapse.
▪ Congestive-Avoidance Algorithms (CAA) are implemented at the TCP layer as the mechanism to avoid congestive collapse in
a network.

✓ Leaky Bucket Algorithm :

▪ The leaky bucket algorithm discovers its use in the context of network traffic shaping or rate-limiting.
▪ A leaky bucket execution and a token bucket execution are predominantly used for traffic shaping algorithms.
▪ This algorithm is used to control the rate at which traffic is sent to the network and shape the burst traffic to a steady traffic
stream.
▪ The disadvantages compared with the leaky-bucket algorithm are the inefficient use of available network resources.
▪ The large area of network resources such as bandwidth is not being used effectively.
 COMPUTER COMMUICATION AND NETWORK

▪ In this algorithm, a bucket with a volume of, say, b bytes and a hole in the Notes bottom is
considered.
▪ If the bucket is null, it means b bytes are available as storage.
▪ A packet with a size smaller than b bytes arrives at the bucket and will forward it.
▪ If the packet's size increases by more than b bytes, it will either be discarded or queued.
▪ It is also considered that the bucket leaks through the hole in its bottom at a constant rate
of r bytes per second.
▪ The outflow is considered constant when there is any packet in the bucket and zero when it
is empty.
▪ This defines that if data flows into the bucket faster than data flows out through the hole,
the bucket overflows.
▪ The disadvantages compared with the leaky-bucket algorithm are the inefficient use of
available network resources.
▪ The leak rate is a fixed parameter.
▪ In the case of the traffic, volume is deficient, the large area of network resources such as
bandwidth is not being used effectively.
▪ The leaky-bucket algorithm does not allow individual flows to burst up to port speed to
effectively consume network resources when there would not be resource contention in the
network.
 COMPUTER COMMUICATION AND NETWORK

✓Token bucket Algorithm :

▪ The leaky bucket algorithm has a rigid output design at an average rate independent of the burst traffic.
▪ In some applications, when large bursts arrive, the output is allowed to speed up.
▪ This calls for a more flexible algorithm, preferably one that never loses information.
▪ Therefore, a token bucket algorithm finds its uses in network traffic shaping or rate-limiting.
▪ It is a control algorithm that indicates when traffic should be sent.
▪ This order comes based on the display of tokens in the bucket.
▪ The bucket contains tokens.
▪ Each of the tokens defines a packet of predetermined size.
▪ Tokens in the bucket are deleted for the ability to share a packet.
▪ When tokens are shown, a flow to transmit traffic appears in the display of tokens.
▪ No token means no flow sends its packets.
▪ Hence, a flow transfers traffic up to its peak burst rate in good tokens in the bucket.
 COMPUTER COMMUICATION AND NETWORK

✓ Admission control
▪ Admission control is a validation process in communication systems where a check is performed before a connection
is established to see if current resources are sufficient for the proposed connection.
▪ It is one of techniques that is widely used in virtual-circuit networks to keep congestion at bay.
▪ The idea is do not set up a new virtual circuit unless the network can carry the added traffic without becoming
congested.
▪ Admission control can also be combined with traffic aware routing by considering routes around traffic hotspots as
part of the setup procedure.

✓Hop by hop choke packets.

▪ A more efficient method is to send to choke packets hop-by-hop packets hop by hop.
▪ This requires each hop to reduce its transmission even before the choke packet transmission even before the choke
packet arrive at the source.