UNIT – III
NETWORK LAYER
Network Layer Design Issues:
1. Store‐and‐Forward Packet Switching
⎯ Data is divided into small parts (packets).
⎯ Packets are transmitted from node to node, processed and forwarded.
⎯ It known as store‐and‐forward packet switching.
⎯ The major components of the network are the Internet Service Provider’s (ISP’s)
equipment (routers connected by transmission lines), and the customers’ equipment.
⎯ Host H1 is directly connected to one of the ISP’s routers, A, perhaps as a home
computer that is plugged into a DSL modem.
⎯ In contrast, H2 is on a LAN, which might be an office Ethernet, with a router, F, owned
and operated by the customer.
⎯ This router has a leased line to the ISP’s equipment.
⎯ We have shown F as being outside the oval because it does not belong to the ISP.
⎯ For the purposes of this chapter, however, routers on customer premises are considered
part of the ISP network because they run the same algorithms as the ISP’s routers
⎯ A host with a packet to send transmits it to the nearest router.
⎯ The packet is stored there until it has fully arrived and the link has finished its
processing by verifying the checksum.
⎯ Then it is forwarded to the next router along the path until it reaches the destination
host, where it is delivered.
2. Services Provided to the Transport Layer
The network layer provides a list of services to the transport layer at the network layer/transport
layer interface.
⎯ The services should be independent of the router technology.
⎯ The transport layer should be shielded from the number, type, and topology of the
routers present.
⎯ The network addresses made available to the transport layer should use a uniform
numbering plan, even across LANs and WANs.
3. Connection-oriented Service (Virtual Circuit)
⎯ Path from source to destination must be established before any data can be sent.
⎯ Connection is called a virtual circuit (VC).
⎯ Avoid choosing new route for each packet.
⎯ Same route used for all packets in connection.
⎯ Each packet has ID for which VC it belongs to
4. Connectionless Service (Datagram)
⎯ No connection setup.
⎯ Message is broken into packets (datagrams)
⎯ Each packet is individually routed and each may follow different paths
⎯ Not guaranteed to arrive in order.
Comparison of Connection-oriented and connectionless
Issue Datagram Network Virtual Circuit Network
1. Circuit setup Not needed Required
Each packet contains the full source Each packet contains a short
2. Addressing
address and destination address VC number
Router do not hold state information Each VC requires router table
3. State Information
about connections space for connection
Route chosen when VC is
4. Routing Each packet is routed Independently
setup; all packets follow it
5. Effect of router None, except for packets lost during All VCs that passed through
failure the crash the failed router are terminated
6. Congestion Control Difficult Easy
Routing
⎯ The main function of the network layer is routing packets from the source node to the
destination node.
⎯ In most networks, packets will require multiple hops/intermediate nodes to make the
route.
⎯ In some cases, routing is an issue, if the source and destination are not on the same
network.
⎯ The algorithms that choose the routes and the data structures that they use are a major
area of network layer design.
Routing Algorithms
⎯ The routing algorithm is that part of the network layer software responsible for deciding
which output line an incoming packet should be transmitted on.
⎯ If the network uses virtual circuits internally, routing decisions are made only when a
new virtual circuit is being set up.
⎯ If the network uses datagrams internally, this decision must be made a new for every
arriving data packet since the best route may have changed since last time.
Classification of routing algorithms:
A. Non adaptive or Static routing – Do not change their routing decisions on any measurements
or estimates of the current topology.
Examples: Shortest path routing, Flooding, and Flow-based routing algorithm
B. Adaptive or Dynamic routing – Change their routing decisions to reflect changes in the
topology, and sometimes changes in the traffic as well.
Examples: Distance vector routing, Hierarchical routing, Broadcast and Multicast routing
All of the routing algorithms we describe here make decisions based on the topology;
The Optimality Principle
Before we get into specific algorithms, it may be helpful to note that one can make a general
statement about optimal routes without regard to network topology or traffic. This statement is
known as the optimality principle.
As a direct consequence of the optimality principle, we can see that the set of optimal routes
from all sources to a given destination form a tree rooted at the destination. Such a tree is called
a sink tree.
NON-ADAPTIVE OR STATIC ROUTING ALGORITHMS
1. Shortest-Path Routing Algorithm
It is a simple technique for computing optimal paths given a complete picture of the network.
The concept of a shortest path is measuring based on following metrics:
⎯ First metric is the number of hops between Source and Destination.
⎯ Another metric is the geographic distance.
⎯ Other factors for measuring are bandwidth, average traffic, communication cost,
measured delay.
By changing the weighting function, the algorithm would then compute the ‘‘shortest’’ path
measured according to any one of a number of criteria or to a combination of criteria.
Several algorithms for computing the shortest path between two nodes of a graph are known.
Dijkstra and finds the shortest paths between a source and all destinations in the network.
Dijkstra’s Algorithm:
⎯ Each node is labeled (in parentheses) with its distance from the source node along the
best-known path.
⎯ The distances must be non-negative, as they will be if they are based on real quantities
like bandwidth and delay.
⎯ Initially, no paths are known, so all nodes are labeled with infinity.
⎯ As the algorithm proceeds and paths are found, the labels may change, reflecting better
paths.
⎯ A label may be either tentative or permanent.
⎯ Initially, all labels are tentative.
⎯ When it is discovered that a label represents the shortest possible path from the source
to that node, it is made permanent and never changed thereafter.
2. Flooding
⎯ A simple local technique is flooding, in which every incoming packet is sent out on
every outgoing line except the one it arrived on.
⎯ Flooding obviously generates vast numbers of duplicate packets (Disadvantage)
How we can Eliminate Duplicate Packets:
i. Using HOP counter:
⎯ One such measure is to have a hop counter contained in the header of each packet.
i.e. decremented at each hop, with the packet being discarded when the counter
reaches zero.
⎯ Ideally, the hop counter should be initialized to the length of the path from source to
destination.
⎯ If the sender does not know how long the path is, it can initialize the counter to the
worst case, namely, the full diameter of the network.
ii. Using Sequence Number:
⎯ A better technique for damming the flood is to have routers keep track of which packets
have been flooded, to avoid sending them out a second time.
⎯ One way to achieve this goal is to have the source router put a sequence number in each
packet it receives from its hosts.
⎯ Each router then needs a list per source router telling which sequence numbers
originating at that source have already been seen.
iii. Selective Flooding:
⎯ Use only those lines that are going approximate in right direction.
ADAPTIVE OR DYNAMIC ALGORITHMS
1. Broadcast Routing (ONE-to ALL)
⎯ The Router may forward the received packet through ALL of its interfaces.
⎯ Broadcast routing can be done in two ways:
1. A router creates a data packet and then sends it to each host one by one. In this
case, the router creates multiple copies of single data packet with different
destination addresses. All packets are sent as unicast but because they are sent
to all, it simulates as if router is broadcasting.
This method consumes lots of bandwidth.
2. Secondly, when router receives a packet that is to be broadcasted, it simply
floods those packets out of all interfaces. All routers are configured in the same
way.
This method is easy on router’s CPU.
2. Multicast Routing (ONE-to-SEVERAL)
⎯ The Router forwards the received packet through only selected of its interfaces.
⎯ Multicast routing is a networking method for efficient distribution of one-to-many
traffic.
3. Hierarchal Routing
⎯ As networks grow in size, the router routing tables grow proportionally.
⎯ When hierarchical routing is used, the routers are divided into what we will call regions.
⎯ Each router knows all the details about how to route packets to destinations within its
own region but knows nothing about the internal structure of other regions.
⎯ When different networks are interconnected, it is natural to regard each one as a
separate region to free the routers in one network from having to know the topological
structure of the other ones.
⎯ For huge networks, a two-level hierarchy may be insufficient;
⎯ It may be necessary to group the regions into clusters, the clusters into zones, the zones
into groups, and so on.
Full Routing Table for 1A
Destination Line Hops distance
1A - -
1B 1B 1
1C 1C 1
2A 1B 2
2B 1B 3
2C 1B 3
2D 1B 4
3A 1C 3
3B 1C 2
4A 1C 3
4B 1C 4
4C 1C 4
5A 1C 4
5B 1C 5
5C 1B 5
5D 1C 6
5E 1C 5
Hierarchical Table for 1A
Destination Line Hops distance
1A - -
1B 1B 1
1C 1C 1
2 1B 2
3 1C 2
4 1C 3
5 1C 4
Congestion
Network congestion in data networking is the reduced quality of service that occurs when
a network node or link is carrying more data than it can handle. (in other words)
The presence of congestion means that the load is (temporarily) greater than the resources (in
a part of the network) can handle. (in other words)
Congestion is a network may occur if the load on the network is greater that capacity of
network.
Typical effects include packet delay, packet loss or the blocking of new connections.
Congestion Control Mechanisms
Refers to the mechanism or techniques that can either PREVENT congestion before it happens
(or) REMOVE congestion after it happened.
OPEN LOOP – Prevent Congestion before it happens
1. Retransmission:
⎯ The sender can retransmit the packet if the previous one is lost or corrupted.
⎯ E.g. Timer is good for retransmission and reduce the congestion,
2. Window policy:
⎯ Use Selective Repeat window and Go-Back-N window methods for congestion control
⎯ In case of Go-Back-N window method, the sender can retransmit all the packets again
to the destination.
⎯ For example, if sender sent 3 packets (P1, P2, and P3) to destination but only 2 (P1 and
P3) packets arrived.
⎯ Sender again retransmit three packets (P1, P2, and P3) to destination instead of P2 alone.
⎯ There is a chance to occur duplicate packets (P1 and P3) and increase the load in the
data transmission path.
⎯ In case of Selective Repeat window method, the sender can retransmit only missing
packet to the destination.
⎯ For Example, ONLY the packet P2 can be retransmit
⎯ Then reduce the data load on the path.
3. Acknowledgement (ACK) Policy:
⎯ Sender sends a few packets and receiver sends positive ACK for each time.
⎯ For Example, (P1, P2, and P3) are the packets transmitted by sender one by one.
⎯ The same way receiver sends ACK packets for each time
⎯ Here there is chance to occur duplicate congestion.
⎯ Instead of each time, the receiver waits some time for all packets receiving from sender
and send ACK packet at once.
⎯ So, we can reduce the congestion with this policy.
4. Discarding Policy:
⎯ We can explain this policy with an example
⎯ Example → Audio Transmission
⎯ Less Sensitive packet can be discarded, then Quality of Audio is providing and prevent
the congestion using this policy.
5. Admission Policy:
⎯ Quality of Service (QoS) mechanism also prevent congestion in Virtual Circuit (VC)
network.
⎯ Switches first check resource requirement of a flow before admitting to network
⎯ Router deny establishing VC connection is chances of future congestion in network.
CLOSED LOOP – Try to remove the congestion after it happens
1. Back Pressure:
⎯ If any congestion occurs then it sends a message towards source through each
intermediate router or node.
⎯ Towards Source noted as Upstream and in reverse known as Downstream.
⎯ The back-pressure message travelled in upstream direction.
2. Choke Packet:
⎯ Here, if congestion occurs at any node then it sends a direct message to the source.
⎯ For example, at node 3 congestion occurs and it sends a direct message called choke
packet and it can intimate about the congestion.
⎯ Then source will slowdown the data flow and reduce the congestion.
3. Implicit Signalling:
⎯ There is NO communication between Source and Congested Node.
⎯ Source guess congestion by delay in acknowledgment and slow down.
4. Explicit Signaling:
⎯ Congested node explicitly send signal to source or destination.
