Distance Vector Routing Algorithm

o The Distance vector algorithm is iterative, asynchronous and distributed.

o 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.

o Iterative: It is iterative in that its process continues until no more information is

available to be exchanged between neighbors.

o Asynchronous: It does not require that all of its nodes operate in the lock step with
each other.

o The Distance vector algorithm is a dynamic algorithm.

o It is mainly used in ARPANET, and RIP.

o Each router maintains a distance table known as Vector.

Three Keys to understand the working of Distance Vector Routing Algorithm:

o Knowledge about the whole network: Each router shares its knowledge through the entire
network. The Router sends its collected knowledge about the network to its neighbors.

o Routing only to neighbors: The router sends its knowledge about the network to only those
routers which have direct links. The router sends whatever it has about the network through
the ports. The information is received by the router and uses the information to update its own
routing table.

o Information sharing at regular intervals: Within 30 seconds, the router sends the
information to the neighboring routers.

Note: In Distance vector algorithm, node x update its table when it either see any cost change in one
directly linked nodes or receives any vector update from some neighbor.

Let's understand through an example:

o In the above figure, each cloud represents the network, and the number inside the cloud
represents the network ID.
 o All the LANs are connected by routers, and they are represented in boxes labeled as A, B, C,
D, E, F.

o Distance vector routing algorithm simplifies the routing process by assuming the cost of every
link is one unit. Therefore, the efficiency of transmission can be measured by the number of
links to reach the destination.

o In Distance vector routing, the cost is based on hop count.

In the above figure, we observe that the router sends the knowledge to the immediate neighbors. The
neighbors add this knowledge to their own knowledge and sends the updated table to their own
neighbors. In this way, routers get its own information plus the new information about the neighbors.

Routing Table

Two process occurs:

o Creating the Table

o Updating the Table

Creating the Table

Initially, the routing table is created for each router that contains atleast three types of information
such as Network ID, the cost and the next hop.

o NET ID: The Network ID defines the final destination of the packet.

o Cost: The cost is the number of hops that packet must take to get there.

o Next hop: It is the router to which the packet must be delivered.

 o In the above figure, the original routing tables are shown of all the routers. In a routing table,
the first column represents the network ID, the second column represents the cost of the link,
and the third column is empty.

o These routing tables are sent to all the neighbors.

For Example:

1. A sends its routing table to B, F & E.

2. B sends its routing table to A & C.

3. C sends its routing table to B & D.

4. D sends its routing table to E & C.

5. E sends its routing table to A & D.

6. F sends its routing table to A.

Updating the Table

o When A receives a routing table from B, then it uses its information to update the table.

o The routing table of B shows how the packets can move to the networks 1 and 4.

o The B is a neighbor to the A router, the packets from A to B can reach in one hop. So, 1 is
added to all the costs given in the B's table and the sum will be the cost to reach a particular
network.

o After adjustment, A then combines this table with its own table to create a combined table.
 o The combined table may contain some duplicate data. In the above figure, the combined table
of router A contains the duplicate data, so it keeps only those data which has the lowest cost.
For example, A can send the data to network 1 in two ways. The first, which uses no next
router, so it costs one hop. The second requires two hops (A to B, then B to Network 1). The
first option has the lowest cost, therefore it is kept and the second one is dropped.

o The process of creating the routing table continues for all routers. Every router receives the
information from the neighbors, and update the routing table.

Final routing tables of all the routers are given below:

Count to Infinity Problem in Distance Vector Routing

Since the Bellman-Ford algorithm is unable to prevent loops, the fundamental problem with Distance
Vector Routing (DVR) protocols is Routing Loops. The Count to Infinity Problem is brought on by
this routing loop in the DVR network. When two routers deliver updates simultaneously or when an
interface goes down, routing loops frequently happen.

Count to Infinity:

Distance-vector routing has the drawback that while cost increases (bad news) propagate slowly, cost
decreases (positive news) propagate quickly. Distance-vector routing takes some time for all other
routers to become aware of a broken connection (cost becomes infinity), which is necessary for a
routing protocol to function properly. Counting to infinity is the name given to the issue. A broken
link's cost may not always be registered as infinite by all routers until numerous updates have passed.

Two Node Loop:

The two-node loop issue is an example of count to infinity. Let's examine the case shown in Figure to
better grasp the issue.

o A system with three nodes is depicted in the figure. Only the elements of the forwarding table
required for our discussion have been displayed. Nodes A and B are first able to connect to
node X. However, the connection between A and X abruptly breaks down. The table of Node
A is altered. Everything will be good if A can quickly transmit its table to B. If B, instead of
waiting for A to transmit its forwarding table, sends its forwarding table to A first, the system
becomes unstable.
 o When Node A receives the update, it instantly updates its forwarding table in the event that B
has managed to connect to X. A has just updated B and sent it a fresh message. B has now
updated its forwarding table as it believes that something has changed around A. Until it
approaches infinity, the price of getting to X rises gradually. Both A and B are aware that X
cannot be reached at this time. In contrast, the system is unstable at the present time.

o Node A believes that node B is the path to X, while node B believes that node A is the way to
X. When A gets a packet intended for X, the packet first travels to B before returning to A.
Similar to this, if B receives a packet meant for X, it travels to A before returning to B. A two-
node loop problem is caused by packets bouncing between A and B. There are a few remedies
that have been suggested for this form of instability.

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 k th 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.

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.

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

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.

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

1 A 2,A 5,A 1,A ∞ ∞

2 AD 2,A 4,D 2,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.

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.

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

1 A 2,A 5,A 1,A ∞ ∞

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

3 ADE 2,A 3,E 4,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.

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

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

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.

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

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

Final table:

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

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 ADEBCF

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.

Transmission Control Protocol (TCP)

TCP stands for Transmission Control Protocol. It is a transport layer protocol that facilitates the
transmission of packets from source to destination. It is a connection-oriented protocol that means it
establishes the connection prior to the communication that occurs between the computing devices in a
network. This protocol is used with an IP protocol, so together, they are referred to as a TCP/IP.

The main functionality of the TCP is to take the data from the application layer. Then it divides the
data into a several packets, provides numbering to these packets, and finally transmits these packets to
the destination. The TCP, on the other side, will reassemble the packets and transmits them to the
application layer. As we know that TCP is a connection-oriented protocol, so the connection will
remain established until the communication is not completed between the sender and the receiver.

Features of TCP protocol

The following are the features of a TCP protocol:

o Transport Layer Protocol:TCP is a transport layer protocol as it is used in transmitting the

data from the sender to the receiver.

o Reliable:TCP is a reliable protocol as it follows the flow and error control mechanism. It also
supports the acknowledgment mechanism, which checks the state and sound arrival of the
data. In the acknowledgment mechanism, the receiver sends either positive or negative
acknowledgment to the sender so that the sender can get to know whether the data packet has
been received or needs to resend.

o Order of the data is maintained:This protocol ensures that the data reaches the intended
receiver in the same order in which it is sent. It orders and numbers each segment so that the
TCP layer on the destination side can reassemble them based on their ordering.

o Connection-oriented:It is a connection-oriented service that means the data exchange occurs

only after the connection establishment. When the data transfer is completed, then the
connection will get terminated.

o Full duplex:It is a full-duplex means that the data can transfer in both directions at the same
time.

o Stream-oriented:TCP is a stream-oriented protocol as it allows the sender to send the data in

the form of a stream of bytes and also allows the receiver to accept the data in the form of a
stream of bytes. TCP creates an environment in which both the sender and receiver are
 connected by an imaginary tube known as a virtual circuit. This virtual circuit carries the
stream of bytes across the internet.

Working of TCP

In TCP, the connection is established by using three-way handshaking. The client sends the segment
with its sequence number. The server, in return, sends its segment with its own sequence number as
well as the acknowledgement sequence, which is one more than the client sequence number. When the
client receives the acknowledgment of its segment, then it sends the acknowledgment to the server. In
this way, the connection is established between the client and the server.

Advantages of TCP

o It provides a connection-oriented reliable service, which means that it guarantees the delivery
of data packets. If the data packet is lost across the network, then the TCP will resend the lost
packets.

o It provides a flow control mechanism using a sliding window protocol.

o It provides error detection by using checksum and error control by using Go Back or ARP
protocol.
 o It eliminates the congestion by using a network congestion avoidance algorithm that includes
various schemes such as additive increase/multiplicative decrease (AIMD), slow start, and
congestion window.

Disadvantage of TCP: It increases a large amount of overhead as each segment gets its own TCP
header, so fragmentation by the router increases the overhead.

TCP Header Format

o Source port: It defines the port of the application, which is sending the data. So, this field
contains the source port address, which is 16 bits.

o Destination port: It defines the port of the application on the receiving side. So, this field
contains the destination port address, which is 16 bits.

o Sequence number: This field contains the sequence number of data bytes in a particular
session.

o Acknowledgment number: When the ACK flag is set, then this contains the next sequence
number of the data byte and works as an acknowledgment for the previous data received. For
example, if the receiver receives the segment number 'x', then it responds 'x+1' as an
acknowledgment number.

o HLEN: It specifies the length of the header indicated by the 4-byte words in the header. The
size of the header lies between 20 and 60 bytes. Therefore, the value of this field would lie
between 5 and 15.

o Reserved: It is a 4-bit field reserved for future use, and by default, all are set to zero.

o Flags
There are six control bits or flags:

o URG: It represents an urgent pointer. If it is set, then the data is processed urgently.

o ACK: If the ACK is set to 0, then it means that the data packet does not contain an
acknowledgment.
 o PSH: If this field is set, then it requests the receiving device to push the data to the
receiving application without buffering it.

o RST: If it is set, then it requests to restart a connection.

o SYN: It is used to establish a connection between the hosts.

o FIN: It is used to release a connection, and no further data exchange will happen.

o Window size
It is a 16-bit field. It contains the size of data that the receiver can accept. This field is used
for the flow control between the sender and receiver and also determines the amount of buffer
allocated by the receiver for a segment. The value of this field is determined by the receiver.

o Checksum
It is a 16-bit field. This field is optional in UDP, but in the case of TCP/IP, this field is
mandatory.

o Urgent pointer
It is a pointer that points to the urgent data byte if the URG flag is set to 1. It defines a value
that will be added to the sequence number to get the sequence number of the last urgent byte.

o Options
It provides additional options. The optional field is represented in 32-bits. If this field
contains the data less than 32-bit, then padding is required to obtain the remaining bits.

User Datagram Protocol (UDP)

User Datagram Protocol (UDP) is a Transport Layer protocol. UDP is a part of the Internet Protocol
suite, referred to as UDP/IP suite. Unlike TCP, it is an unreliable and connectionless protocol. So,
there is no need to establish a connection before data transfer. The UDP helps to establish low-latency
and loss-tolerating connections over the network. The UDP enables process-to-process
communication.

UDP Header

UDP header is an 8-byte fixed and simple header, while for TCP it may vary from 20 bytes to 60
bytes. The first 8 Bytes contain all necessary header information and the remaining part consists of
data. UDP port number fields are each 16 bits long, therefore the range for port numbers is defined
from 0 to 65535; port number 0 is reserved. Port numbers help to distinguish different user requests or
processes.
UDP Header

 Source Port: Source Port is a 2 Byte long field used to identify the port number of the source.

 Destination Port: It is a 2 Byte long field, used to identify the port of the destined packet.

 Length: Length is the length of UDP including the header and the data. It is a 16-bits field.

 Checksum: Checksum is 2 Bytes long field. It is the 16-bit one’s complement of the one’s
complement sum of the UDP header, the pseudo-header of information from the IP header,
and the data, padded with zero octets at the end (if necessary) to make a multiple of two
octets.

Notes – Unlike TCP, the Checksum calculation is not mandatory in UDP. No Error control or flow
control is provided by UDP. Hence UDP depends on IP and ICMP for error reporting. Also UDP
provides port numbers so that is can differentiate between users requests.

Applications of UDP

 Used for simple request-response communication when the size of data is less and hence there
is lesser concern about flow and error control.

 It is a suitable protocol for multicasting as UDP supports packet switching.

 UDP is used for some routing update protocols like RIP(Routing Information Protocol).

 Normally used for real-time applications which can not tolerate uneven delays between
sections of a received message.

 VoIP (Voice over Internet Protocol) services, such as Skype and WhatsApp, use UDP for real-
time voice communication. The delay in voice communication can be noticeable if packets
are delayed due to congestion control, so UDP is used to ensure fast and efficient data
transmission.

 DNS (Domain Name System) also uses UDP for its query/response messages. DNS queries
are typically small and require a quick response time, making UDP a suitable protocol for this
application.

 DHCP (Dynamic Host Configuration Protocol) uses UDP to dynamically assign IP addresses
to devices on a network. DHCP messages are typically small, and the delay caused by packet
loss or retransmission is generally not critical for this application.

 Following implementations uses UDP as a transport layer protocol:

o NTP (Network Time Protocol)

 o DNS (Domain Name Service)

o BOOTP, DHCP.

o NNP (Network News Protocol)

o Quote of the day protocol

o TFTP, RTSP, RIP.

 The application layer can do some of the tasks through UDP-

o Trace Route

o Record Route

o Timestamp

 UDP takes a datagram from Network Layer , attaches its header, and sends it to the user. So, it
works fast.

TCP vs UDP

Basis Transmission Control Protocol (TCP) User Datagram Protocol (UDP)

UDP is the Datagram-oriented

TCP is a connection-oriented protocol. protocol. This is because there
Connection orientation means that the is no overhead for opening a
communicating devices should establish a connection, maintaining a
connection before transmitting data and connection, or terminating a
should close the connection after connection. UDP is efficient for
transmitting the data. broadcast and multicast types of
Type of Service network transmission.

The delivery of data to the

TCP is reliable as it guarantees the delivery
destination cannot be
of data to the destination router.
Reliability guaranteed in UDP.

TCP provides extensive error-checking UDP has only the basic error-
Error checking mechanisms. It is because it provides flow checking mechanism using
mechanism control and acknowledgment of data. checksums.

Acknowledgme
An acknowledgment segment is present. No acknowledgment segment.
nt

Sequence Sequencing of data is a feature of There is no sequencing of data

Basis Transmission Control Protocol (TCP) User Datagram Protocol (UDP)

Transmission Control Protocol (TCP). this in UDP. If the order is required,

means that packets arrive in order at the it has to be managed by the
receiver. application layer.

UDP is faster, simpler, and more

TCP is comparatively slower than UDP.
Speed efficient than TCP.

There is no retransmission of
Retransmission of lost packets is possible in
lost packets in the User
TCP, but not in UDP.
Retransmission Datagram Protocol (UDP).

TCP has a (20-60) bytes variable length UDP has an 8 bytes fixed-length
Header Length header. header.

Weight TCP is heavy-weight. UDP is lightweight.

Handshaking Uses handshakes such as SYN, ACK, SYN- It’s a connectionless protocol
Techniques ACK i.e. No handshake

Broadcasting TCP doesn’t support Broadcasting. UDP supports Broadcasting.

TCP is used by HTTP, UDP is used by DNS, DHCP,

Protocols HTTPs , FTP , SMTP and Telnet . TFTP, SNMP , RIP, and VoIP.

UDP connection is a message

The TCP connection is a byte stream.
Stream Type stream.

Overhead Low but higher than UDP. Very low.

Applications This protocol is primarily utilized in This protocol is used in

situations when a safe and trustworthy situations where quick
communication procedure is necessary, such communication is necessary but
as in email, on the web surfing, and where dependability is not a
Basis Transmission Control Protocol (TCP) User Datagram Protocol (UDP)

concern, such as VoIP, game

in military services. streaming, video, and music
streaming, etc.

Advantages of UDP

 Speed: UDP is faster than TCP because it does not have the overhead of establishing a
connection and ensuring reliable data delivery.

 Lower latency: Since there is no connection establishment, there is lower latency and faster
response time.

 Simplicity: UDP has a simpler protocol design than TCP, making it easier to implement and
manage.

 Broadcast support: UDP supports broadcasting to multiple recipients, making it useful for
applications such as video streaming and online gaming.

 Smaller packet size: UDP uses smaller packet sizes than TCP, which can reduce network
congestion and improve overall network performance.

 User Datagram Protocol (UDP) is more efficient in terms of both latency and bandwidth.

Disadvantages of UDP

 No reliability: UDP does not guarantee delivery of packets or order of delivery, which can
lead to missing or duplicate data.

 No congestion control: UDP does not have congestion control, which means that it can send
packets at a rate that can cause network congestion.

 Vulnerable to attacks: UDP is vulnerable to denial-of-service attacks , where an attacker can

flood a network with UDP packets, overwhelming the network and causing it to crash.

 Limited use cases: UDP is not suitable for applications that require reliable data delivery, such
as email or file transfers, and is better suited for applications that can tolerate some data loss,
such as video streaming or online gaming.

Congestion Control

Congestion control is a crucial concept in computer networks. It refers to the methods used to prevent
network overload and ensure smooth data flow. When too much data is sent through the network at
once, it can cause delays and data loss. Congestion control techniques help manage the traffic, so all
users can enjoy a stable and efficient network connection. These techniques are essential for
maintaining the performance and reliability of modern networks.

What is Congestion?

Congestion in a computer network happens when there is too much data being sent at the same time,
causing the network to slow down. Just like traffic congestion on a busy road, network congestion
leads to delays and sometimes data loss. When the network can’t handle all the incoming data, it gets
“clogged,” making it difficult for information to travel smoothly from one place to another.

Effects of Congestion in Computer Network

 Improved Network Stability: Congestion control helps keep the network stable by
preventing it from getting overloaded. It manages the flow of data so the network doesn’t
crash or fail due to too much traffic.

 Reduced Latency and Packet Loss: Without congestion control, data transmission can
slow down, causing delays and data loss. Congestion control helps manage traffic better,
reducing these delays and ensuring fewer data packets are lost, making data transfer faster and
the network more responsive.

 Enhanced Throughput: By avoiding congestion, the network can use its resources more
effectively. This means more data can be sent in a shorter time, which is important for
handling large amounts of data and supporting high-speed applications.

 Fairness in Resource Allocation: Congestion control ensures that network resources are
shared fairly among users. No single user or application can take up all the bandwidth,
allowing everyone to have a fair share.

 Better User Experience: When data flows smoothly and quickly, users have a better
experience. Websites, online services, and applications work more reliably and without
annoying delays.

 Mitigation of Network Congestion Collapse: Without congestion control, a sudden spike in

data traffic can overwhelm the network, causing severe congestion and making it almost
unusable. Congestion control helps prevent this by managing traffic efficiently and avoiding
such critical breakdowns.

Congestion Control Algorithm

 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.

 There are two congestion control algorithms which are as follows:

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.

Let us consider an example to understand Imagine a bucket with a small hole in the bottom. No matter
at what rate water enters the bucket, the outflow is at constant rate. When the bucket is full with water
additional water entering spills over the sides and is lost.

Similarly, each network interface contains a leaky bucket and the following steps are involved in
leaky bucket algorithm:

 When host wants to send packet, packet is thrown into the bucket.

 The bucket leaks at a constant rate, meaning the network interface transmits packets at a
constant rate.

 Bursty traffic is converted to a uniform traffic by the leaky bucket.

 In practice the bucket is a finite queue that outputs at a finite rate.

Token Bucket Algorithm

 The leaky bucket algorithm has a rigid output design at an average rate independent of the
bursty 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..

Need of Token Bucket Algorithm

The leaky bucket algorithm enforces output pattern at the average rate, no matter how bursty the
traffic is. So in order to deal with the bursty traffic we need a flexible algorithm so that the data is not
lost. One such algorithm is token bucket algorithm.
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 sent.

 If there is no token in the bucket, the packet cannot be sent.

Let’s understand with an example, In figure (A) we see a bucket holding three tokens, with five
packets waiting to be transmitted. For a packet to be transmitted, it must capture and destroy one
token. In figure (B) We see that three of the five packets have gotten through, but the other two are
stuck waiting for more tokens to be generated.

Advantages

 Stable Network Operation: Congestion control ensures that networks remain stable and
operational by preventing them from becoming overloaded with too much data traffic.

 Reduced Delays: It minimizes delays in data transmission by managing traffic flow

effectively, ensuring that data packets reach their destinations promptly.

 Less Data Loss: By regulating the amount of data in the network at any given time,
congestion control reduces the likelihood of data packets being lost or discarded.

 Optimal Resource Utilization: It helps networks use their resources efficiently, allowing for
better throughput and ensuring that users can access data and services without interruptions.

 Scalability: Congestion control mechanisms are scalable, allowing networks to handle

increasing volumes of data traffic as they grow without compromising performance.

 Adaptability: Modern congestion control algorithms can adapt to changing network

conditions, ensuring optimal performance even in dynamic and unpredictable environments.

Disadvantages

 Complexity: Implementing congestion control algorithms can add complexity to network

management, requiring sophisticated systems and configurations.

 Overhead: Some congestion control techniques introduce additional overhead, which can
consume network resources and affect overall performance.

 Algorithm Sensitivity: The effectiveness of congestion control algorithms can be sensitive to

network conditions and configurations, requiring fine-tuning for optimal performance.

 Resource Allocation Issues: Fairness in resource allocation, while a benefit, can also pose
challenges when trying to prioritize critical applications over less essential ones.

 Dependency on Network Infrastructure: Congestion control relies on the underlying

network infrastructure and may be less effective in environments with outdated or unreliable
equipment.

Difference Between Token Bucket Algorithm and Leaky Bucket Algorithm

Token Bucket Algorithm Leaky Bucket Algorithm

It depends on tokens. It does not depend on tokens.

If bucket is full, token is discarded but not the

If bucket is full, then packets are discarded.
packet.

Packets can only transmit when there are

Packets are transmitted continuously.
enough tokens.

Allows large bursts to be sent at faster rate.

Sends the packet at a constant rate.
Bucket has maximum capacity.

The bucket holds tokens generated at regular When the host has to send a packet , packet is
intervals of time. thrown in bucket.

If there is a ready packet , a token is removed Bursty traffic is converted into uniform traffic
from Bucket and packet is send. by leaky bucket.

If there is no token in the bucket, then the In practice bucket is a finite queue outputs at
packet cannot be sent. finite rate.

Computer Network Security

Computer network security consists of measures taken by business or some organizations to monitor
and prevent unauthorized access from the outside attackers.

Different approaches to computer network security management have different requirements

depending on the size of the computer network. For example, a home office requires basic network
security while large businesses require high maintenance to prevent the network from malicious
attacks.

Network Administrator controls access to the data and software on the network. A network
administrator assigns the user ID and password to the authorized person.

Advantages of Network Security

o Network security is essential for safeguarding client data and information, maintaining the
security of shared data, guaranteeing dependable network performance, and defending against
online attacks.

o An effective network security solution lowers overhead costs and protects businesses from
significant losses brought on by a data breach or other security event.

o Ensuring appropriate access to systems, applications, and data facilitates company operations
and customer service.

Aspects of Network Security

Following are the desirable properties to achieve secure communication:

 o Privacy: Privacy means both the sender and the receiver expects confidentiality. The
transmitted message should be sent only to the intended receiver while the message should be
opaque for other users. Only the sender and receiver should be able to understand the
transmitted message as eavesdroppers can intercept the message. Therefore, there is a
requirement to encrypt the message so that the message cannot be intercepted. This aspect of
confidentiality is commonly used to achieve secure communication.

o Message Integrity: Data integrity means that the data must arrive at the receiver exactly as it
was sent. There must be no changes in the data content during transmission, either
maliciously or accident, in a transit. As there are more and more monetary exchanges over the
internet, data integrity is more crucial. The data integrity must be preserved for secure
communication.

o End-point authentication: Authentication means that the receiver is sure of the sender?s
identity, i.e., no imposter has sent the message.

o Non-Repudiation: Non-Repudiation means that the receiver must be able to prove that the
received message has come from a specific sender. The sender must not deny sending a
message that he or she send. The burden of proving the identity comes on the receiver. For
example, if a customer sends a request to transfer the money from one account to another
account, then the bank must have a proof that the customer has requested for the transaction.

Network Security Implementation

In the modern environment, no method can guarantee complete security. However, measures may be
taken to protect data when it is sent across an unprotected network or the internet. The most popular
method is cryptography. Encrypting plain-text data using cryptography makes it more difficult to
decipher and understand. Today, a variety of cryptographic algorithms are accessible, as follows:

1. Secret Key Cryptography:

The sender and the receiver share one secret key. The data is encrypted at the sender's end using this
secret key. Data is encrypted before being transferred to the recipient via a public network. The
recipient may readily decipher the encrypted data packets because they are both aware of and possess
the Secret Key.

The Data Encryption Standard (DES) is an illustration of secret key encryption. It is challenging to
administer Secret Key encryption since each computer on the network needs a unique key.

2. Public Key Cryptography

Each user in this encryption scheme has a unique Secret Key that is not kept in the common domain.
The secret key is kept from the public. Every user has a unique but public key in addition to a secret
key. Senders encrypt the data using a public key that is always made available to the public. Using the
user's personal Secret Key, he can quickly decode the encrypted data once he receives it. Rivest-
Shamir-Adleman (RSA), a kind of public key encryption, is an illustration.

3. Message Digest

In this approach, a hash value is computed and delivered in place of actual data. The second end user
generates its hash value and contrasts it with the most recent one. It is approved if both hash values
match; otherwise, it is refused.

Message Digest example using MD5 hashing. It is mostly utilized in authentication processes when
server passwords are compared against user passwords.

Privacy

The concept of how to achieve privacy has not been changed for thousands of years: the message
cannot be encrypted. The message must be rendered as opaque to all the unauthorized parties. A good
encryption/decryption technique is used to achieve privacy to some extent. This technique ensures
that the eavesdropper cannot understand the contents of the message.

Encryption/Decryption

Encryption: Encryption means that the sender converts the original information into another form
and sends the unintelligible message over the network.

Decryption: Decryption reverses the Encryption process in order to transform the message back to
the original form.

The data which is to be encrypted at the sender site is known as plaintext, and the encrypted data is
known as ciphertext. The data is decrypted at the receiver site.

Advertisement

There are two types of Encryption/Decryption techniques:

o Privacy with secret key Encryption/Decryption

o Privacy with public key Encryption/Decryption

Secret Key Encryption/Decryption technique

 o In Secret Key Encryption/Decryption technique, the same key is used by both the parties, i.e.,
the sender and receiver.

o The sender uses the secret key and encryption algorithm to encrypt the data; the receiver uses
this key and decryption algorithm to decrypt the data.

o In Secret Key Encryption/Decryption technique, the algorithm used for encryption is the
inverse of the algorithm used for decryption. It means that if the encryption algorithm uses a
combination of addition and multiplication, then the decryption algorithm uses a combination
of subtraction and division.

o The secret key encryption algorithm is also known as symmetric encryption algorithm
because the same secret key is used in bidirectional communication.

o In secret key encryption/decryption algorithm, the secret code is used by the computer to
encrypt the information before it is sent over the network to another computer.

o The secret key requires that we should know which computers are talking to each other so
that we can install the key on each computer.

Data Encryption Standard (DES)

o The Data Encryption Standard (DES) was designed by IBM and adopted by the U.S.
government as the standard encryption method for nonmilitary and nonclassified use.

o The Data Encryption Standard is a standard used for encryption, and it is a form of
Secret Key Cryptography.

Advantage

Efficient: The secret key algorithms are more efficient as it takes less time to encrypt the message
than to encrypt the message by using a public key encryption algorithm. The reason for this is that the
size of the key is small. Due to this reason, Secret Key Algorithms are mainly used for encryption and
decryption.

Disadvantages of Secret Key Encryption

The Secret Key Encryption/Decryption has the following disadvantages:

o Each pair of users must have a secret key. If the number of people wants to use this method in
the world is N, then there are N(N-1)/2 secret keys. For example, for one million people, then
there are half billion secret keys.
 o The distribution of keys among different parties can be very difficult. This problem can be
resolved by combining the Secret Key Encryption/Decryption with the Public Key
Encryption/Decryption algorithm.

Public Key Encryption/Decryption technique

o There are two keys in public key encryption: a private key and a public key.

o The private key is given to the receiver while the public key is provided to the public.

In the above figure, we see that A is sending the message to user B. 'A' uses the public key to encrypt
the data while 'B' uses the private key to decrypt the data.

o In public key Encryption/Decryption, the public key used by the sender is different from the
private key used by the receiver.

o The public key is available to the public while the private key is kept by each individual.

o The most commonly used public key algorithm is known as RSA.

Advantages of Public Key Encryption

o The main restriction of private key encryption is the sharing of a secret key. A third party
cannot use this key. In public key encryption, each entity creates a pair of keys, and they keep
the private one and distribute the public key.

o The number of keys in public key encryption is reduced tremendously. For example, for one
million users to communicate, only two million keys are required, not a half-billion keys as in
the case of secret key encryption.

Disadvantages of Public Key Encryption

o Speed: One of the major disadvantage of the public-key encryption is that it is slower than
secret-key encryption. In secret key encryption, a single shared key is used to encrypt and
decrypt the message which speeds up the process while in public key encryption, different
two keys are used, both related to each other by a complex mathematical process. Therefore,
we can say that encryption and decryption take more time in public key encryption.
 o Authentication: A public key encryption does not have a built-in authentication. Without
authentication, the message can be interpreted or intercepted without the user's knowledge.

o Inefficient: The main disadvantage of the public key is its complexity. If we want the method
to be effective, large numbers are needed. But in public key encryption, converting the
plaintext into ciphertext using long keys takes a lot of time. Therefore, the public key
encryption algorithms are efficient for short messages not for long messages.

Differences b/w Secret Key Encryption & Public Key Encryption

Basis for Comparison Secret Key Encryption Public Key Encryption

Secret Key Encryption is Public Key Encryption is

defined as the technique defined as the technique
Define that uses a single shared that uses two different keys
key to encrypt and decrypt for encryption and
the message. decryption.

It is efficient as this It is inefficient as this

Efficieny technique is recommended technique is used only for
for large amounts of text. short messages.

It is also known as
It is also known as
Other name Asymmetric Key
Symmetric Key encryption.
Encryption.

Its speed is slow as it uses

two different keys, both
Its speed is high as it uses a
keys are related to each
Speed single key for encryption
other through the
and decryption.
complicated mathematical
process.

The Secret key algorithms

The Public key algorithms
Algorithms are DES, 3DES, AES &
are Diffie-Hellman, RSA.
RCA.

The main purpose of the The main purpose of the

Purpose secret key algorithm is to public key algorithm is to
transmit the bulk data. share the keys securely.

Digital Signature

The Digital Signature is a technique which is used to validate the authenticity and integrity of the
message. We know that there are four aspects of security: privacy, authentication, integrity, and non-
repudiation. We have already discussed the first aspect of security and other three aspects can be
achieved by using a digital signature.

The basic idea behind the Digital Signature is to sign a document. When we send a document
electronically, we can also sign it. We can sign a document in two ways: to sign a whole document
and to sign a digest.

Signing the Whole Document

 o In Digital Signature, a public key encryption technique is used to sign a document. However,
the roles of a public key and private key are different here. The sender uses a private key to
encrypt the message while the receiver uses the public key of the sender to decrypt the
message.

o In Digital Signature, the private key is used for encryption while the public key is used for
decryption.

o Digital Signature cannot be achieved by using secret key encryption.

Digital Signature is used to achieve the following three aspects:

o Integrity: The Digital Signature preserves the integrity of a message because, if any
malicious attack intercepts a message and partially or totally changes it, then the decrypted
message would be impossible.

o Authentication: We can use the following reasoning to show how the message is
authenticated. If an intruder (user X) sends a message pretending that it is coming from
someone else (user A), user X uses her own private key to encrypt the message. The message
is decrypted by using the public key of user A. Therefore this makes the message unreadable.
Encryption with X's private key and decryption with A's public key results in garbage value.

o Non-Repudiation: Digital Signature also provides non-repudiation. If the sender denies

sending the message, then her private key corresponding to her public key is tested on the
plaintext. If the decrypted message is the same as the original message, then we know that the
sender has sent the message.

Note: Digital Signature does not provide privacy. If there is a need for privacy, then another layer of
encryption/decryption is applied.

Signing the Digest

o Public key encryption is efficient if the message is short. If the message is long, a public key
encryption is inefficient to use. The solution to this problem is to let the sender sign a digest
of the document instead of the whole document.

o The sender creates a miniature version (digest) of the document and then signs it, the receiver
checks the signature of the miniature version.
 o The hash function is used to create a digest of the message. The hash function creates a fixed-
size digest from the variable-length message.

o The two most common hash functions used: MD5 (Message Digest 5) and SHA-1 (Secure
Hash Algorithm 1). The first one produces 120-bit digest while the second one produces a
160-bit digest.

o A hash function must have two properties to ensure the success:

o First, the digest must be one way, i.e., the digest can only be created from the
message but not vice versa.
o Second, hashing is a one-to-one function, i.e., two messages should not create the
same digest.

Following are the steps taken to ensure security:

o The miniature version (digest) of the message is created by using a hash function.

o The digest is encrypted by using the sender's private key.

o After the digest is encrypted, then the encrypted digest is attached to the original message and
sent to the receiver.

o The receiver receives the original message and encrypted digest and separates the two. The
receiver implements the hash function on the original message to create the second digest, and
it also decrypts the received digest by using the public key of the sender. If both the digests
are same, then all the aspects of security are preserved.

At the Sender site

At the Receiver site