Unit 3

NETWORK LAYER
NETWORK LAYER
 It is the third layer of OSI model. It responds to service requests from the transport layer
and issues service requests to the data link layer.

 Network layer addresses messages and translates logical addresses and names into physical
addresses. it also determines the route from the source to the destination computer and
manages traffic problems, such as switching. routing, and controlling the congestion of data
packets.

 It describes how a series of exchanges over various data links can deliver data between any
two nodes in a network. This layer defines the addressing and routing structure of the
Internet.
Functions of Network Layer

 It translates logical network address into physical address. Concerned with circuit, message
or packet switching.

 Routers and gateways operate in the network layer. Mechanism is provided by Network
Layer for routing the packets to final destination.

 Connection services are provided including network layer flow control, network layer error
control and packet sequence control.

 Breaks larger packets into small packets.

Circuit-switched vs Packet-switched networks

 Circuit Switched Networks:-Circuit switched networks are connection-oriented networks.

 Here, a dedicated route is established between the source and the destination and the entire
message is transferred through it.

 Normal telephone service is based on a circuit-switching technology, in which a dedicated line

is allocated for transmission between two parties.

 Circuit-switching is ideal when data must be transmitted quickly and must arrive in the same
order in which it's sent.

 This is the case with most real-time data, such as live audio and video.
In the above image, three computers on the left side are connected with three desktops
PCs on the right side with physical links, depending on the four circuit switchers. If the
circuit switching is not used, they need to be connected with point-to-point connections,
where many number of dedicated lines are required, which will not only increase the
connection cost but also increase the complexity of the system.
 Packet Switched Networks :- Packet switched networks are connectionless networks.

 Here, the message is divided and grouped into a number of units called packets that are
individually routed from the source to the destination.

 Each packet is then transmitted individually and can even follow different routes to its
destination.

 Once all the packets forming a message arrive at the destination, they are recompiled into the
original message.

 Most modern Wide Area Network (WAN) protocols, including TCP/IP are based on
packet- switching technologies.

 Packet switching is more efficient and robust for data that can withstand some delays in
transmission, such as e-mail messages and Web pages.
In the above image, 4 PCs are connected with a 4 switch network and the data flow will
be packet switching. As we can see switches are connected with each other and share
the communications path with each other. If we want to transfer data from PC1 to the
PC 4 the path will be directed from the SW1 to SW2 to SW3 and then finally at PC4.
This route is predefined and All SW1, SW2, SW3 are provided with a unique ID to
identify the data paths, so the data is bound by the paths and could not choose another
route.
Forwarding and Routing in Network Layer
The role of the network layer is thus deceptively simple – to move packets from a sending host
to a receiving host. To do so, two important network-layer functions can be identified:

Forwarding:When a packet arrives at a router’s input link, the router must move the packet to the
appropriate output link. For example, a packet arriving from Host H1 to Router R1 must be
forwarded to the next router on a path to H2.

Routing:The network layer must determine the route or path taken by packets as they flow from a
sender to a receiver. The algorithms that calculate these paths are referred to as routing
algorithms. A routing algorithm would determine, for example, the path along which packets
flow from H1 to H2.

 Forwarding refers to the router-local action of transferring packet from an input link interface
to the appropriate output link interface.

 Routing refers to the network-wide process that determines the end-to-end paths that packets
take from source to destination.
ROUTING

 Routing is the process of selecting paths in a network along which to send network traffic.

 Routing is usually performed by a dedicated device called a router

 A router is a networking device that forwards packets between networks using information in
protocol headers and forwarding tables to determine the best next router for each packets.

 Routers work at the network layer of the OSI model and the Internet Layer of TCP/IP for
routing of packets, routing algorithms are used.

 The routing algorithm is that part of the network layer software responsible for deciding
which output line an incoming packet should be transmitted on
Types of Routing

Routing can be classified into three categories:

 Static Routing

 Default Routing

 Dynamic Routing
Static Routing

 Static Routing is also known as Nonadaptive Routing.

 It is a technique in which the administrator manually adds the routes in a routing table.

 A Router can send the packets for the destination along the route defined by theadministrator.

 In this technique, routing decisions are not made based on the condition or topology of the
networks
Dynamic Routing

 It is also known as Adaptive Routing.

 It is a technique in which a router adds a new route in the routing table for each packet in
response to the changes in the condition or topology of the network.

 Dynamic protocols are used to discover the new routes to reach the destination.

 In Dynamic Routing, RIP and OSPF are the protocols used to discover the new routes.

 If any route goes down, then the automatic adjustment will be made to reach the destination.
Default Routing

 Default Routing is a technique in which a router is configured to send all the packets to the
same hop device, and it doesn't matter whether it belongs to a particular network or not. A
Packet is transmitted to the device for which it is configured in default routing.

 Default Routing is used when networks deal with the single exit point.

 It is also useful when the bulk of transmission networks have to transmit the data to the same
hop device.

 When a specific route is mentioned in the routing table, the router will choose the specific
route rather than the default route. The default route is chosen only when a specific route is not
mentioned in the routing table.
Routing table
 Routing table is an electronic document that stores routes to various nodes in a computer
network.

 The nodes may be any kind of electronic device connected to the network.

 The routing table is usually stored in a router or networked computer in the form of a database
or file.

 When data needs to be sent from one node to another on the network, the routing table is
referred to in order to find the best possible route for the transfer of information.

 The routing table consists of at least three information fields:

1: Network ID: i.e., the destination network id.

2: Cost: i.e, the cost or metric of the path through which the packet is to be sent.

3: 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.
Classification of RoutingAlgorithms

Routing is process of establishing the routes that data packets must follow to reach the
destination. In this process, a routing table is created which contains information regarding
routes which data packets follow. Various routing algorithm are used for the purpose of
deciding which route an incoming data packet needs to be transmitted on to reach destination
efficiently.

Classification of Routing Algorithms: The routing algorithms can be classified as follows:

1. Adaptive Algorithms

2. Non-Adaptive Algorithms
1. Adaptive Algorithms –

 These are the algorithms which change their routing decisions whenever network topology or
traffic load changes.

 The changes in routing decisions are reflected in the topology as well as traffic of the network.

 Also known as dynamic routing, these make use of dynamic information such as current
topology, load, delay, etc. to select routes.

 Optimization parameters are distance, number of hops and estimated transit time.
Further these are classified as follows:

a) Isolated – In this method each, node makes its routing decisions using the information it has
without seeking information from other nodes. The sending nodes doesn’t have information
about status of particular link. Disadvantage is that packet may be sent through a congested
network which may result in delay.

a) Centralized – In this method, a centralized node has entire information about the network and
makes all the routing decisions. Advantage of this is only one node is required to keep the
information of entire network and disadvantage is that if central node goes down the entire
network is done.

a) Distributed – In this method, the node receives information from its neighbors and then takes
the decision about routing the packets. Disadvantage is that the packet may be delayed if there
is change in between interval in which it receives information and sends packet.
2. Non-Adaptive Algorithms –

 These are the algorithms which do not change their routing decisions once they have been
selected.

 This is also known as static routing as route to be taken is computed in advance and
downloaded to routers when router is booted.

Further these are classified as follows:

a) Flooding – This adapts the technique in which every incoming packet is sent on every
outgoing line except from which it arrived. One problem with this is that packets may go in
loop and as a result of which a node may receive duplicate packets.

a) Random walk – In this method, packets are sent host by host or node by node to one of its
neighbors randomly. This is highly robust method which is usually implemented by sending
packets onto the link which is least queued.
Routing v/s Flooding:
Shortest Path Routing

Shortest Path Routing is suited for static routing.

 A path selected can be called shortest in many contexts.

 If one selects cost as criteria then the shortest path is the route which is least expensive.

 If distance is the criteria for determining shortest path then minimum length path is taken in to
consideration.
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:

o 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.
o 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.
o 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
o Initial state: Each node knows the cost of its neighbors.
o Final state: Each node knows the entire graph.
Route Calculation
Each node uses Dijkstra's algorithm on the graph to calculate the optimal routes to all
nodes.
o The Link state routing algorithm is also known as Dijkstra's algorithm which is
used to find the shortest path from one node to every other node in the network.
o The Dijkstra's algorithm is an iterative, and it has the property that after kth iteration
of the algorithm, the least cost paths are well known for k destination nodes.
Let's describe some notations:
o c( i , j): Link cost from node i to node j. If i and j nodes are not directly linked, then
c(i , j) = ∞.
o D(v): It defines the cost of the path from source code to destination v that has the
least cost currently.
o P(v): It defines the previous node (neighbor of v) along with current least cost path
from source to v.
o N: It is the total number of nodes available in the network. Algorithm
Initialization
N = {A} // A is a root node. for all nodes v
if v adjacent to A then D(v) = c(A,v) else D(v) = infinity

loop
find w not in N such that D(w) is a minimum. Add w to N
Update D(v) for all v adjacent to w and not in N:
D(v) = min(D(v) , D(w) + c(w,v)) Until all nodes in N

In the above algorithm, an initialization step is followed by the loop. The number of
times the loop is executed is equal to the total number of nodes available in the network.

Let's understand through an example:

In the above figure, source vertex is A.
Step 1:
The first step is an initialization step. The currently known least cost path from A to its
directly attached neighbors, B, C, D are 2,5,1 respectively. The cost from A to B is set
to 2, from A to D is set to 1 and from A to C is set to 5. The cost from A to E and F are
set to infinity as they are not directly linked to A.

Ste N D(B),P(B D(C),P(C D(D),P(D D(E),P(E D(F),P(F

p ) ) ) ) )
1 A 2,A 5,A 1,A ∞ ∞

Step 2:
In the above table, we observe that vertex D contains the least cost path in step 1.
Therefore, it is added in N. Now, we need to determine a least-cost path through D
vertex.

a) Calculating shortest path from A to B

1. v = B, w = D
2. D(B) = min( D(B) , D(D) + c(D,B) )
3. = min( 2, 1+2)>
4. = min( 2, 3)
5. The minimum value is 2. Therefore, the currently shortest path from A to B is 2.
b) Calculating shortest path from A to C
1. v = C, w = D
2. D(B) = min( D(C) , D(D) + c(D,C) )
3. = min( 5, 1+3)
4. = min( 5, 4)
5. The minimum value is 4. Therefore, the currently shortest path from A to C is 4.</
p>
c) Calculating shortest path from A to E
1. v = E, w = D
2. D(B) = min( D(E) , D(D) + c(D,E) )
3. = min( ∞, 1+1)
4. = min(∞, 2)
5. The minimum value is 2. Therefore, the currently shortest path from A to E is 2.
Note: The vertex D has no direct link to vertex E. Therefore, the value of D(F) is
infinity.

Ste N D(B),P(B D(C),P(C D(D),P(D D(E),P(E D(F),P(F

p ) ) ) ) )
1 A 2,A 5,A 1,A ∞ ∞

2 A 2,A 4,D 2,D ∞

D

Step 3:
In the above table, we observe that both E and B have the least cost path in step 2. Let's
consider the E vertex. Now, we determine the least cost path of remaining vertices
through E.

a) Calculating the shortest path from A to B.

1. v = B, w = E
2. D(B) = min( D(B) , D(E) + c(E,B) )
3. = min( 2 , 2+ ∞ )
4. = min( 2, ∞)
5. The minimum value is 2. Therefore, the currently shortest path from A to B is 2.
b) Calculating the shortest path from A to C.
1. v = C, w = E
2. D(B) = min( D(C) , D(E) + c(E,C) )
3. = min( 4 , 2+1 )
4. = min( 4,3)
5. The minimum value is 3. Therefore, the currently shortest path from A to C is 3.
6.
c) Calculating the shortest path from A to F.
1. v = F, w = E
2. D(B) = min( D(F) , D(E) + c(E,F) )
3. = min( ∞ , 2+2 )
4. = min(∞ ,4)
5. The minimum value is 4. Therefore, the currently shortest path from A to F is 4.

Ste N D(B),P(B D(C),P(C D(D),P(D D(E),P(E D(F),P(F

p ) ) ) ) )
1 A 2,A 5,A 1,A ∞ ∞

2 AD 2,A 4,D 2,D ∞

3 AD 2,A 3,E 4,E

E

Step 4:
In the above table, we observe that B vertex has the least cost path in step 3. Therefore,
it is added in N. Now, we determine the least cost path of remaining vertices through B.
a) Calculating the shortest path from A to C.
1. v = C, w = B
2. D(B) = min( D(C) , D(B) + c(B,C) )
3. = min( 3 , 2+3 )
4. = min( 3,5)
5. The minimum value is 3. Therefore, the currently shortest path from A to C is 3.
b) Calculating the shortest path from A to F.
1. v = F, w = B
2. D(B) = min( D(F) , D(B) + c(B,F) )
3. = min( 4, ∞)
4. = min(4, ∞)
5. The minimum value is 4. Therefore, the currently shortest path from A to F is 4.
Ste N D(B),P(B D(C),P(C D(D),P(D D(E),P(E D(F),P(F
p ) ) ) ) )
1 A 2,A 5,A 1,A ∞ ∞

2 AD 2,A 4,D 2,D ∞

3 ADE 2,A 3,E 4,E

4 ADE 3,E 4,E

B
Step 5:
In the above table, we observe that C vertex has the least cost path in step 4. Therefore,
it is added in N. Now, we determine the least cost path of remaining vertices through C.

a) Calculating the shortest path from A to F.

1. v = F, w = C
2. D(B) = min( D(F) , D(C) + c(C,F) )
3. = min( 4, 3+5)
4. = min(4,8)
5. The minimum value is 4. Therefore, the currently shortest path from A to F is 4.
Ste N D(B),P(B D(C),P(C D(D),P(D D(E),P(E D(F),P(F
p ) ) ) ) )
1 A 2,A 5,A 1,A ∞ ∞

2 AD 2,A 4,D 2,D ∞

3 ADE 2,A 3,E 4,E

4 ADEB 3,E 4,E

5 ADEB 4,E
C
Final table:

Ste N D(B),P(B D(C),P(C D(D),P(D D(E),P(E D(F),P(F

p ) ) ) ) )
1 A 2,A 5,A 1,A ∞ ∞

2 AD 2,A 4,D 2,D ∞

3 ADE 2,A 3,E 4,E

4 ADEB 3,E 4,E

5 ADEBC 4,E

6 ADEBC
F

Disadvantage:
Heavy traffic is created in Line state routing due to Flooding. Flooding can cause an
infinite looping; this problem can be solved by using Time-to-leave field.
Distance Vector Routing (DVR) Protocol
A distance-vector routing (DVR) protocol requires that a router inform its neighbors
of topology changes periodically. Historically known as the old ARPANET routing
algorithm (or known as Bellman-Ford algorithm).
Bellman Ford Basics – Each router maintains a Distance Vector table containing the
distance between itself and ALL possible destination nodes. Distances, based on a
chosen metric, are computed using information from the neighbors’ distance vectors.
Information kept by DV router -
 Each router has an ID
 Associated with each link connected to a router,
 There is a link cost (static or dynamic).
 Intermediate hops
Distance Vector Table Initialization -
 Distance to itself = 0
 Distance to ALL other routers = infinity number.
Distance Vector Algorithm –
1. A router transmits its distance vector to each of its neighbors in a routing packet.
2. Each router receives and saves the most recently received distance vector from
each of its neighbors.
3. A router recalculates its distance vector when:
 It receives a distance vector from a neighbor containing different information
than before.
 It discovers that a link to a neighbor has gone down.

The DV calculation is based on minimizing the cost to each destination Dx(y) =

Estimate of least cost from x to y

C(x,v) = Node x knows cost to each neighbor v

Dx = [Dx(y): y ∈ N ] = Node x maintains distance vector Node x also maintains
its neighbors' distance vectors

– For each neighbor v, x maintains Dv = [Dv(y): y ∈ N ]

Note –
 From time-to-time, each node sends its own distance vector estimate to neighbors.
 When a node x receives new DV estimate from any neighbor v, it saves v’s
distance vector and it updates its own DV using B-F equation:

 Dx(y) = min { C(x,v) + Dv(y), Dx(y) } for each node y ∈ N

Example – Consider 3-routers X, Y and Z as shown in figure. Each router have their
routing table. Every routing table will contain distance to the destination nodes.
Consider router X , X will share it routing table to neighbors and neighbors will share it
routing table to it to X and distance from node X to destination will be calculated using
bellmen- ford equation.

Dx(y) = min { C(x,v) + Dv(y)} for each node y ∈ N

As we can see that distance will be less going from X to Z when Y is intermediate
node(hop) so it will be update in routing table X.
Similarly for Z also –
Finally the routing table for all –

Advantages of Distance Vector routing –

 It is simpler to configure and maintain than link state routing.
Disadvantages of Distance Vector routing –
 It is slower to converge than link state.
 It is at risk from the count-to-infinity problem.
 It creates more traffic than link state since a hop count change must be
propagated to all routers and processed on each router. Hop count updates
take place on a periodic basis, even if there are no changes in the network
topology, so bandwidth-wasting broadcasts still occur.
 For larger networks, distance vector routing results in larger routing tables
than link state since each router must know about all other routers. This can
also lead to congestion on WAN links.
Note – Distance Vector routing uses UDP (User datagram protocol) for transportation.

Difference between Distance vector routing and Link State routing

Prerequisite – Classification of Routing Algorithms
Distance Vector Routing –
 It is a dynamic routing algorithm in which each router computes distance between
itself and each possible destination i.e. its immediate neighbors.
 The router shares its knowledge about the whole network to its neighbors and
accordingly updates table based on its neighbors.
 The sharing of information with the neighbors takes place at regular intervals.
 It makes use of Bellman Ford Algorithm for making routing tables.
 Problems – Count to infinity problem which can be solved by splitting horizon.
– Good news spread fast and bad news spread slowly.
– Persistent looping problem i.e. loop will be there forever.
Link State Routing –
 It is a dynamic routing algorithm in which each router shares knowledge of its
neighbors with every other router in the network.
 A router sends its information about its neighbors only to all the routers through
flooding.
 Information sharing takes place only whenever there is a change.
 It makes use of Dijkastra’s Algorithm for making routing tables.
 Problems – Heavy traffic due to flooding of packets.
– Flooding can result in infinite looping which can be solved by using Time to
leave (TTL) field.
Comparison between Distance Vector Routing and Link State Routing:
Routing Protocols

 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 neighbours, and
then throughout the network.

 This way routers gain knowledge of the topology of the network.

1: Interior Gateway Protocols (IGPs):

 The router within an autonomous system uses an interior Gateway Protocol (IGP) to exchange
routing information.

 There are several IGPs available each autonomous system is free to choose its own IGP.

 There are two types Interior Gateway Protocols:

1: Interior gateway protocols type 1, link-state routing protocols, such as Open Shortest paths First
(OSPF)

2: Interior gateway protocols type 2, Distance-vector routing protocols such as routing information
protocol. RIPv2, IGRP. Enhanced Interior Gateway Protocol(EIGRP) is an advanced Distance-
vector routing protocol that is used on a computer network for automating routing decisions
and configuration
1. Distance Vector Routing Protocol – These protocols selects best path in the basis of hop
counts to reach a destination network in the particular direction. Dynamic protocol like RIP is
an example of distance vector routing protocol. Hop count is each router which occurs in
between the source and the destination network. The path with the least hop count will be
chosen as the best path.

1. Link State Routing Protocol – These protocols know more about the Internetwork than any
other distance vector routing protocol. These re also known as SPF (Shortest Path First)
protocol. OSPF is an example of link state routing protocol.

1. Advanced Distance vector routing protocol – It is also known as hybrid routing protocol
which uses the concept of both distance vector and link state routing protocol. Enhanced
Interior Gateway Routing Protocol (EIGRP) is an example of this class if routing protocol.
EIGRP acts as a link state routing protocol as it uses the concept of Hello protocol for neighbor
discovery and forming adjacency. Also, partial updates are triggered when a change occurs.
EIGRP acts as distance vector routing protocol as it learned routes from directly connected
neighbors.
2: Exterior Gateway Protocols (EGPs)

 A router is one autonomous system uses an exterior gateway Protocol (EGP) to exchange
routing information with a router in another autonomous system.

 EGPs are usually more complex to install and operate than IGPs, but EGPs offer more
flexibility and lower overhead.

 To save traffic, an EGP summarises routing information from the autonomous system before
passing it to another autonomous system.

 More important an EGP implements policy constrain that allows a

system manager to determine exactly what information is released outside the
organization

 Exterior gateway protocols are routing protocols used on the internet for exchanging routing
information between autonomous Systems such as border Gateway protocol (BGP) Path Vector
Routing Protocol
Congestion Control

What is congestion?

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

 Congestion occur in a computer network when the resource demands exceed the capacity

 Packets may be lost due to too much queuing in the network.

 During Congestion the network throughput may drop and the path delay may become very
high

 Congestion in a network may occur if users send data into the network at a rate greater than
allowed by network resources.

Effects of Congestion

 As delay increases, performance decreases.

 If delay increases, retransmission occurs, making situation worse.

Causes of Congestion

1. Unpredictable statistical fluctuation of traffic flows

2. Faults conditions within the network

1. Slow processor speed. if the router's CPU speed is very low and performing tasks like queuing
buffer, tables updating etc. queries are built up, even though the line capacity is not fully
utilized

2. Inefficient control policies

1. Bandwidth of the links is important in Congestion. The links to be used must be of high
Bandwidth to avoid Congestion
TYPES OF CONGESTION CONTROLALGORITHMS

 Congestion in a frame relay network is a problem that must be avoided because it decreases
throughput and increases delay

1: Leaky Bucket Algorithm:

 If there is a hole at the bottom of a Bucket, then no matter at what rate the Bucket is filled up,
the water leaks out drop by drop at a constant rate from the hole.

 Each host is connected by an interface that has finite queue acting like leaky Bucket.

 When a packet comes to a host with the queue full, it is discarded. The host 1s allowed to put
one packet per clock tick info the network. This can be enforced by the interface card or by the
operating system.

 This converts an uneven flow of packets from the user process in an even flow of packers onto
the network. Conceptually. Each host is connected to the network by an interface

 Containing a leaky bucket, that is, a finite internal queue. If a packet arrives at the queue when
it is full , the packet is discarded
 In other word, if one or more processes within the host try to send a packet when the maximum
number is already queued, the new packet is unceremoniously discarded.

 This mechanism turns an uneven flow of packets from the user processes inside the host into
an even flow of packets onto the network.
r»u«
 Implementing the original leaky bucket algorithm is easy.

 The leaky bucket consists of a finite queue. When a packet arrives, if there is room on the
queue it is appended to the queue otherwise, it is discarded.

 At every clock tick, one packet is transmitted (unless the queue is empty).

 This arrangement can be simulated in the operating system or can be built into the hardware.

 Implementation of this algorithm is easy and consists of a finite queue.

 Whenever a packet arrives, if there is room in the queue it is queued up and if there is no room
then the packet is discarded
2: Token Bucket Algorithm

 This algorithm allows bursts for short transmission while making sure that no data is lost.

 In contrast to the Leaky Bucket algorithm, not the data that is to be send but tokens are queued
in a time-depended queue.

 One token is needed to send a single portion of data Implementations contain a token counter
that is incremented on every time interval, so that the counter grows over time up until a
maximum counter value is reached.

 The token counter is decremented by one for every data portion sent.

 When the token counter is zero no data can be transmitted.

 For many applications it is better to allow the output to speed up somewhat when a larger burst
arrives than to lose the data.
Main steps of this algorithm can be described as follows:
 In regular intervals tokens are thrown into the bucket.

 The bucket has a maximum capacity.

 If there is a ready packet, a token is removed from the bucket, and the packet is send.

 If there is no token in the bucket, the packet cannot be send.

Token Bucket Algorithm

 Token dependent

 If bucket is full token are discarded, but not the packet.

 Packets can only transmitted when there are enough token.

 It allows large bursts to be sent at faster rate after that constant rate.

 It saves token to send large bursts.

Leaky Bucket Algorithm

 Token independent

 If bucket is full packet or data is discarded.

 Packets are transmitted continuously.

 It sends the packet at constant rate.

 It does not save token.

Congestion Control techniques

Congestion control refers to the techniques used to control or prevent congestion. Congestion
control techniques can be broadly classified into two categories:
1. Open loop congestion control policies are applied to prevent congestion before it
happens. The congestion control is handled either by the source or the destination.

Policies adopted by open loop congestion control –

a)Retransmission Policy :

 It is the policy in which retransmission of the packets are taken care. If the sender
feels that a sent packet is lost or corrupted, the packet needs to be retransmitted. This
transmission may increase the congestion in the network.

 To prevent congestion, retransmission timers must be designed to prevent congestion

and also able to optimize efficiency.

b)Window Policy :

 The type of window at the sender side may also affect the congestion. Several packets
in the Go-back-n window are resent, although some packets may be received
successfully at the receiver side. This duplication may increase the congestion in the
network and making it worse.

 Therefore, Selective repeat window should be adopted as it sends the specific packet
that may have been lost.
c).Discarding Policy : A good discarding policy adopted by the routers is that the routers may
prevent congestion and at the same time partially discards the corrupted or less sensitive
package and also able to maintain the quality of a message.

 In case of audio file transmission, routers can discard less sensitive packets to prevent
congestion and also maintain the quality of the audio file.

d).Acknowledgment Policy :Since acknowledgement are also the part of the load in network, the
acknowledgment policy imposed by the receiver may also affect congestion. Several
approaches can be used to prevent congestion related to acknowledgment.

 The receiver should send acknowledgement for N packets rather than sending
acknowledgement for a single packet. The receiver should send a acknowledgment only if it
has to sent a packet or a timer expires.

e).Admission Policy : In admission policy a mechanism should be used to prevent congestion.

Switches in a flow should first check the resource requirement of a network flow before
transmitting it further.

 If there is a chance of a congestion or there is a congestion in the network, router should deny
establishing a virtual network connection to prevent further congestion.

All the above policies are adopted to prevent congestion before it happens in the network.
2.Closed loop congestion control technique is used to treat or alleviate congestion after it
happens. Several techniques are used by different protocols; some of them are:

a)Backpressure : Backpressure is a technique in which a congested node stop receiving packet

from upstream node.

 This may cause the upstream node or nodes to become congested and rejects receiving data
from above nodes. Backpressure is a node-to-node congestion control technique that propagate
in the opposite direction of data flow.

 The backpressure technique can be applied only to virtual circuit where each node has
information of its above upstream node.
In above diagram the 3rd node is congested and stops receiving packets as a result 2nd node
may be get congested due to slowing down of the output data flow. Similarly 1st node may get
congested and informs the source to slow down.
b)Choke Packet Technique :Choke packet technique is applicable to both virtual networks as
well as datagram subnets. A choke packet is a packet sent by a node to the source to inform it
of congestion.

 Each router monitor its resources and the utilization at each of its output lines. whenever the
resource utilization exceeds the threshold value which is set by the administrator, the router
directly sends a choke packet to the source giving it a feedback to reduce the traffic.

 The intermediate nodes through which the packets has traveled are not warned about
congestion.
c)Implicit Signaling :In implicit signaling, there is no communication between the congested
nodes and the source.

 The source guesses that there is congestion in a network.

 For example when sender sends several packets and there is no acknowledgment for a
while, one assumption is that there is a congestion.

d)Explicit Signaling : In explicit signaling, if a node experiences congestion it can explicitly

sends a packet to the source or destination to inform about congestion.

 The difference between choke packet and explicit signaling is that the signal is included in the
packets that carry data rather than creating different packet as in case of choke packet
technique.

Explicit signaling can occur in either forward or backward direction.

 Forward Signaling : In forward signaling signal is sent in the direction of the

congestion. The destination is warned about congestion. The reciever in this case adopt
policies to prevent further congestion.

 Backward Signaling : In backward signaling signal is sent in the opposite direction of

the congestion. The source is warned about congestion and it needs to slow down.
INTERNETWORKING

 As the computer got smaller, cheaper and yet more powerful. more and more organisation,
companies and people began having their own private network, even Internetworks in case of
large organisations

 Most of them wanted to join the rest of information world by further connecting to the internet.

 some of organisations used internet as a vehicle of communication between their remotely

located private network/ nternetworks

 All of these development saw the Internetworking technology to evolve as an important

technology.

 An Internetworking is a collection of individual networks, connected by intermediate

networking devices, that function as a single large network. there are various types of networks
like LAN,WAN,MAN

 An Internetwork may also be defined as a network of computer communication network every

authorised member of which could communicate with every other authorised member directly
or indirectly

 Ex:Interconnection Of 2 WAN and 1 LAN

IPV4 Header
Format
Subnet (subnetwork)

A subnet, or subnetwork, is a segmented piece of a larger network. More specifically, subnets are a
logical partition of an IP network into multiple, smaller network segments. The Internet Protocol (IP)
is the method for sending data from one computer to another over the internet. Each computer, or
host, on the internet has at least one IP address as a unique identifier.

Organizations will use a subnet to subdivide large networks into smaller, more efficient subnetworks.
One goal of a subnet is to split a large network into a grouping of smaller, interconnected networks to
help minimize traffic. This way, traffic doesn't have to flow through unnecessary routs, increasing
network speeds.

Subnetting, the segmentation of a network address space, improves address allocation efficiency.
Gateway

A gateway is a node (router) in a computer network, a key stopping point for data on its way to or
from other networks. Thanks to gateways, we are able to communicate and send data back and forth.
The Internet wouldn't be any use to us without gateways (as well as a lot of other hardware and
software).
In a workplace, the gateway is the computer that routes traffic from a workstation to the outside
network that is serving up the Web pages. For basic Internet connections at home, the gateway is the
Internet Service Provider that gives you access to the entire Internet.
A node is simply a physical place where the data stops for either transporting or reading/using. (A
computer or modem is a node; a computer cable isn't.) Here are a few node notes:
 On the Internet, the node that's a stopping point can be a gateway or a host node.

 A computer that controls the traffic your Internet Service Provider (ISP) receives is a node. If you

have a wireless network at home that gives your entire family access to the Internet, your gateway
is the modem (or modem-router combo) your ISP provides so you can connect to their network. On
the other end, the computer that controls all of the data traffic your Internet Service Provider (ISP)
takes and sends out is itself a node.