1. Explain Shortest Path Routing Algorithm. (GTU Style – Long Answer)
Definition:
The Shortest Path Routing Algorithm is a routing technique used in computer networks to find the minimum cost path between source and destination.
It helps the router choose the best path for sending data packets.
The shortest path can be based on:
Minimum distance
Minimum delay
Minimum number of hops
Minimum cost
Its main goal is to improve speed and reduce network traffic.
Basic Idea:
In this algorithm, the network is represented as a graph.
Router/Computer = Node (Vertex)
Connection between routers = Link (Edge)
Value assigned to link = Cost (Weight)
The router calculates all possible paths and selects the path with the lowest cost.
Working of Shortest Path Routing Algorithm:
The working is as follows:
1. Create Network Graph
The entire network is shown as a graph where nodes are connected by links.
2. Assign Cost to Each Link
Each link has a cost value like distance or delay.
Example:
Smaller cost = better path
Larger cost = longer path
3. Select Source Node
The starting node is selected.
4. Calculate Path Cost
The algorithm checks all possible routes from source to destination.
5. Choose Minimum Cost Path
The path having the smallest total cost is selected.
6. Send Data
Data packets are sent through that selected shortest path.
Steps of Shortest Path Algorithm:
Start from source node.
Set source node cost = 0.
Set all other node costs = ∞ (infinity).
Select the nearest unvisited node.
Update cost of neighboring nodes.
Mark current node as visited.
Repeat until destination is reached.
Example:
Consider the following network:
2
A ------- B
| |
|4 3|
| |
C ------- D
1
Find shortest path from A to D
Possible paths:
Path 1:
A → B → D
Cost = 2 + 3 = 5
Path 2:
A → C → D
Cost = 4 + 1 = 5
Both paths have equal cost.
So shortest path = 5
Router can choose any one.
Algorithms used in Shortest Path Routing:
1. Dijkstra’s Algorithm
Most commonly used
Finds shortest path from one source to all nodes
Used in many routing protocols
2. Bellman-Ford Algorithm
Used when network changes frequently
Can handle changing costs
Advantages:
1. Efficient Routing
Finds best path quickly.
2. Less Delay
Data reaches destination faster.
3. Better Performance
Improves network speed.
4. Saves Bandwidth
Avoids unnecessary long routes.
5. Reliable Communication
Helps in proper packet delivery.
Disadvantages:
1. More Calculation
Needs continuous cost calculation.
2. Complex for Large Network
Difficult when network size increases.
3. More Memory Required
Stores routing tables.
4. Recalculation Needed
If network changes, path must be recalculated.
Conclusion:
Shortest Path Routing Algorithm is one of the most important routing methods in computer networks. It helps in selecting the best and lowest cost path for packet transmission. It increases speed, reduces delay, and improves overall network efficiency.
2. Explain Distance Vector Routing Algorithm. (GTU Style – Long & Easy)
Definition:
Distance Vector Routing Algorithm is a routing algorithm in which every router maintains a routing table that stores the distance and direction to reach all other nodes in the network.
It is called:
Distance → Shows how far the destination is.
Vector → Shows in which direction (next router) to send the packet.
In simple words, each router tells its neighbors:
“How far I am from all destinations.”
This helps routers find the shortest path.
Basic Concept:
In this algorithm:
Every router knows only about its direct neighbors.
Each router keeps a routing table.
Routers exchange their routing tables with neighbors regularly.
After receiving information, routers update their own tables.
This process continues until all routers get the best path.
This is called convergence.
Routing Table Contains:
Each routing table has:
| Destination | Distance | Next Hop |
|---|---|---|
| A | 0 | - |
| B | 2 | B |
| C | 5 | B |
Where:
Destination = final node
Distance = cost to reach
Next hop = next router
Working of Distance Vector Routing:
The working of this algorithm is as follows:
1. Initial Table Creation
Each router creates its routing table.
It knows:
Its own distance = 0
Direct neighbor distance = actual cost
Other nodes = infinity (∞)
2. Share Routing Table
Each router sends its table to all neighboring routers.
This sharing happens periodically.
3. Receive Neighbor Information
Router receives routing tables from neighbors.
Now it gets information about other possible routes.
4. Compare Path Cost
Router checks:
New cost = Neighbor cost + Link cost
If new cost is smaller, update the table.
5. Update Routing Table
Router changes:
Distance
Next hop
if better path is found.
6. Repeat Process
This process continues until no more changes occur.
That means shortest path is found.
Easy Steps of Distance Vector Algorithm:
Each router knows only direct neighbors.
Create initial routing table.
Send table to neighbors.
Receive neighbor tables.
Compare costs.
Update if shorter path is found.
Repeat until all best paths are fixed.
Example:
Consider this network:
A ----1---- B ----2---- C
Initial routing table:
Router A:
| Destination | Cost |
|---|---|
| A | 0 |
| B | 1 |
| C | ∞ |
Router B:
| Destination | Cost |
|---|---|
| A | 1 |
| B | 0 |
| C | 2 |
After B shares its table:
A learns:
To reach C through B:
A → B → C
Cost = 1 + 2 = 3
So A updates:
| Destination | Cost |
|---|---|
| C | 3 |
Now A can reach C.
Formula Used:
New Distance = Distance to Neighbor + Neighbor’s Distance to Destination
Example:
A to B = 2
B to C = 4
Then:
A to C = 2 + 4 = 6
Advantages:
1. Simple to Implement
Easy to understand and use.
2. Less Complex
Works with simple calculations.
3. Automatic Route Updates
Routes update automatically.
4. Good for Small Networks
Efficient in small-size networks.
5. Low Processing Power
Requires less CPU power.
Disadvantages:
1. Slow Convergence
Takes more time to update all routers.
2. Routing Loops
Packets may move in circles.
3. Count to Infinity Problem
Wrong route information may spread.
4. More Traffic
Frequent routing updates increase traffic.
5. Not Suitable for Large Networks
Performance becomes poor.
Example of Protocol:
The best example of Distance Vector Routing is:
RIP (Routing Information Protocol)
RIP uses this algorithm.
Maximum hop count in RIP = 15
Conclusion:
Distance Vector Routing Algorithm is a simple and important routing technique in computer networks. It works by exchanging routing tables with neighbors and finding the shortest path. It is easy to use but slower for large networks.
3. Explain Link State Routing. (GTU Style – Long & Easy)
Definition:
Link State Routing is a routing algorithm in which each router collects complete information about the network and calculates the shortest path by itself.
In this method, every router knows the full network topology.
Unlike Distance Vector Routing, routers do not send the whole routing table.
They send only the state of their links.
Link state means:
Which neighbors are connected
What is the cost of each link
This helps in finding the best route quickly.
Basic Concept:
In Link State Routing:
Each router creates information about its directly connected links.
This information is sent to all routers in the network.
Every router builds the same network map.
Then each router uses the shortest path algorithm to find best route.
Most commonly it uses Dijkstra's algorithm.
Working of Link State Routing:
The working is as follows:
1. Discover Neighbors
Each router finds its directly connected neighboring routers.
2. Measure Link Cost
Router calculates cost like:
Distance
Delay
Bandwidth
3. Create Link State Packet (LSP)
Router prepares a packet containing:
Router ID
Neighbor list
Cost of each link
4. Flood LSP to All Routers
The LSP is sent to all routers in the network.
This process is called flooding.
5. Build Network Topology
Each router collects all LSPs and creates a complete network map.
6. Calculate Shortest Path
Each router uses Dijkstra’s Algorithm to find shortest path.
7. Update Routing Table
Finally, router stores best path in routing table.
Easy Steps of Link State Routing:
Find neighboring routers.
Measure link cost.
Create Link State Packet (LSP).
Send LSP to all routers.
Build network map.
Apply shortest path algorithm.
Store best route in routing table.
Example:
Consider network:
A ----2---- B
| |
4 3
| |
C ----1---- D
Suppose router A sends:
A to B = 2
A to C = 4
Other routers also send their LSPs.
Now every router builds the full map.
Using Dijkstra:
From A to D:
Path 1: A → B → D = 2 + 3 = 5
Path 2: A → C → D = 4 + 1 = 5
Shortest path cost = 5
Link State Packet (LSP) Contains:
Source router ID
Sequence number
Age
Neighbor list
Link cost
Advantages:
1. Fast Convergence
Updates quickly.
2. No Routing Loops
More reliable.
3. Better for Large Networks
Works efficiently in large networks.
4. Accurate Routing
Complete network information gives better decisions.
5. Less Unnecessary Traffic
Only link changes are sent.
Disadvantages:
1. Complex Algorithm
More difficult than Distance Vector.
2. More Memory Needed
Stores full network map.
3. High CPU Usage
Calculates shortest path frequently.
4. Flooding Overhead
LSP flooding creates extra load.
Example of Protocol:
The best example of Link State Routing is:
OSPF (Open Shortest Path First)
OSPF uses Link State Routing.
Difference from Distance Vector:
| Link State | Distance Vector |
|---|---|
| Sends link information | Sends full routing table |
| Faster | Slower |
| No loops | Loops possible |
| More complex | Simpler |
4. Explain Congestion Control. (GTU Style – Long & Easy)
Definition:
Congestion Control is a technique used in computer networks to control the amount of data entering the network so that the network does not become overloaded.
Congestion happens when too many packets are sent at the same time and the network cannot handle them.
This causes:
Delay in packet delivery
Packet loss
Slow network performance
Congestion control helps to reduce these problems.
What is Congestion?
Congestion means the network is carrying more data than its capacity.
It happens when:
Incoming packets > Processing capacity
Example:
If a router can process 100 packets/sec but receives 200 packets/sec, congestion occurs.
Need of Congestion Control:
Congestion control is important because:
1. To avoid packet loss
Too many packets may be dropped.
2. To reduce delay
Packets can reach faster.
3. To improve network performance
Network works smoothly.
4. To use bandwidth properly
Avoids unnecessary traffic.
Causes of Congestion:
1. High Traffic Load
Many users sending data together.
2. Slow Routers
Router cannot process data fast.
3. Limited Bandwidth
Small capacity causes overload.
4. Retransmission of Lost Packets
Lost packets increase traffic.
5. Poor Network Design
Improper routing may create congestion.
Working of Congestion Control:
The working is:
1. Detect Congestion
Network checks if traffic is increasing.
2. Inform Sender
Receiver/router informs sender about congestion.
3. Reduce Sending Rate
Sender decreases speed of sending packets.
4. Recover Network
After traffic becomes normal, speed increases.
Methods of Congestion Control:
There are mainly two methods:
1. Open Loop Congestion Control
This method tries to prevent congestion before it happens.
It does not use feedback.
Techniques:
a) Retransmission Policy
Controls unnecessary retransmissions.
b) Window Policy
Uses proper window size.
c) Acknowledgement Policy
Reduces extra acknowledgements.
d) Discarding Policy
Drops less important packets.
e) Admission Policy
Checks network load before accepting data.
2. Closed Loop Congestion Control
This method detects congestion and takes action.
It uses feedback.
Techniques:
a) Backpressure
Router informs previous router to slow down.
b) Choke Packet
Router sends warning packet to sender.
c) Implicit Signaling
Sender guesses congestion by delay or loss.
d) Explicit Signaling
Network directly informs sender.
Example:
Suppose:
Router capacity = 50 packets/sec
Incoming packets = 90 packets/sec
Since 90 > 50
Congestion occurs.
Router sends signal to sender.
Sender reduces speed.
Traffic becomes normal.
Effects of Congestion:
1. Packet Loss
Packets may be dropped.
2. Increased Delay
Delivery becomes slow.
3. Low Throughput
Less data reaches destination.
4. Wastage of Bandwidth
Retransmissions waste bandwidth.
Advantages of Congestion Control:
1. Better network performance
2. Less packet loss
3. Faster communication
4. Proper bandwidth usage
5. Stable network operation
Disadvantages:
1. Extra control mechanisms needed
2. May reduce transmission speed
3. More complexity in network
Q.5 Explain TCP Three-Way Handshake for Connection Establishment.
Definition
TCP Three-Way Handshake is a process used by the Transmission Control Protocol (TCP) to establish a reliable connection between a client and a server before data transmission begins. It ensures that both devices are ready to communicate and synchronizes their sequence numbers.
Purpose of TCP Three-Way Handshake
Establishes a reliable connection.
Synchronizes sequence numbers between client and server.
Confirms that both devices are ready for communication.
Prevents data loss during connection setup.
Establishes a reliable connection.
Synchronizes sequence numbers between client and server.
Confirms that both devices are ready for communication.
Prevents data loss during connection setup.
Working of TCP Three-Way Handshake
The connection establishment process consists of three steps:
Step 1: SYN (Synchronize)
The client sends a SYN packet to the server requesting a connection.
Client -------- SYN --------> Server
This packet contains the client's initial sequence number.
Step 2: SYN-ACK (Synchronize Acknowledgment)
The server receives the SYN packet and responds with a SYN-ACK packet.
Client <----- SYN + ACK ----- Server
SYN indicates the server is ready to communicate.
ACK acknowledges the client's request.
Step 3: ACK (Acknowledgment)
The client sends an ACK packet to the server.
Client -------- ACK --------> Server
After receiving this ACK, the server knows that the client is ready and the connection is established.
Diagram
Example
Suppose a user opens a website in a browser.
The browser (client) sends a SYN packet to the web server.
The web server responds with a SYN-ACK packet.
The browser sends an ACK packet.
The TCP connection is established.
The server starts sending the requested web page data.
Advantages
Provides reliable communication.
Ensures both sides are ready before data transfer.
Synchronizes sequence numbers.
Reduces the chances of communication errors.
Provides reliable communication.
Ensures both sides are ready before data transfer.
Synchronizes sequence numbers.
Reduces the chances of communication errors.
Disadvantages
Requires extra time for connection setup.
Generates additional network traffic.
Slightly increases communication overhead.
Requires extra time for connection setup.
Generates additional network traffic.
Slightly increases communication overhead.
Conclusion
TCP Three-Way Handshake is the connection establishment process used by TCP. It consists of three steps: SYN, SYN-ACK, and ACK. This process creates a reliable connection between the client and server, ensuring accurate and secure data transmission.
6. Explain Transport Service Primitives. (GTU Style – Long & Easy)
Definition:
Transport Service Primitives are the basic operations provided by the transport layer to establish communication between sender and receiver.
These primitives help in:
Establishing connection
Sending data
Receiving data
Disconnecting connection
In simple words, transport service primitives are commands used for communication between two devices.
The transport layer provides these services to the application layer.
Need of Transport Service Primitives:
They are needed to:
Start communication
Transfer data properly
Control connection
End communication safely
Without these primitives, communication would not be organized.
Main Transport Service Primitives:
There are mainly five transport service primitives:
1. LISTEN
This primitive is used by the server to wait for a connection request.
It means:
"I am ready to accept connection."
Example:
A web server waits for client request.
Function:
Waits for incoming connection
Keeps server ready
Waits for incoming connection
Keeps server ready
2. CONNECT
This primitive is used by the client to establish connection with server.
It means:
"I want to connect."
Example:
A client sends request to server.
Function:
Starts communication
Creates connection
Starts communication
Creates connection
3. SEND
This primitive is used to send data.
After connection establishment, sender uses SEND.
It means:
"Send this data."
Example:
Sending a message or file.
Function:
Transfers data from sender to receiver
Transfers data from sender to receiver
4. RECEIVE
This primitive is used to receive data.
Receiver uses RECEIVE to accept data.
It means:
"Receive incoming data."
Example:
Receiving email or message.
Function:
Collects incoming data
Collects incoming data
5. DISCONNECT
This primitive is used to close the connection.
After data transfer is complete, DISCONNECT ends communication.
It means:
"Communication finished."
Function:
Terminates connection
Releases resources
Terminates connection
Releases resources
Sequence of Transport Service Primitives:
The communication process follows:
Server Side Client Side
LISTEN <---------> CONNECT
RECEIVE <---------> SEND
DISCONNECT <-------> DISCONNECT
Flow:
Server waits using LISTEN
Client starts using CONNECT
Client sends data using SEND
Server gets data using RECEIVE
Both close connection using DISCONNECT
Example:
Suppose you open a website:
Step 1:
Server uses LISTEN.
Step 2:
Browser uses CONNECT.
Step 3:
Browser sends request using SEND.
Step 4:
Server receives request using RECEIVE.
Step 5:
After response, connection closes using DISCONNECT.
Advantages:
1. Organized Communication
Makes communication systematic.
2. Easy Connection Handling
Easy to establish and close connection.
3. Reliable Data Transfer
Ensures proper sending and receiving.
4. Better Resource Management
Releases resources after communication.
Disadvantages:
1. Extra Time for Connection Setup
2. More Control Operations
3. Slightly Complex Process
Conclusion:
Transport Service Primitives are essential functions of the transport layer that help establish, manage, transfer, and terminate communication between sender and receiver. They make communication reliable and organized in a network.
7. Differentiate UDP and TCP. (GTU Style – Long & Easy)
Introduction:
Transmission Control Protocol (TCP) and User Datagram Protocol (UDP) are transport layer protocols used for communication in computer networks.
Both are used to send data from one device to another, but their working is different.
- TCP provides reliable communication.
- UDP provides fast communication.
>TCP (Transmission Control Protocol)
TCP is a connection-oriented protocol.
It establishes connection before sending data.
Example:
- Web browsing
- File transfer
>UDP (User Datagram Protocol)
UDP is a connectionless protocol.
It sends data directly without establishing connection.
Example:
-
Video streaming
-
Online gaming
-
Voice calls
UDP is a connectionless protocol.
It sends data directly without establishing connection.
Example:
- Video streaming
- Online gaming
- Voice calls
Difference between Transmission Control Protocol (TCP) and User Datagram Protocol (UDP):
| TCP | UDP |
|---|---|
TCP stands for Transmission Control Protocol. | UDP stands for User Datagram Protocol. |
TCP is a connection-oriented protocol because it establishes connection before sending data. | UDP is a connectionless protocol because it sends data without establishing connection. |
TCP provides reliable data transfer. | UDP provides unreliable data transfer. |
In TCP, data packets are delivered in the correct order. | In UDP, data packets may not be delivered in order. |
TCP uses acknowledgements to confirm packet delivery. | UDP does not use acknowledgements for packet delivery. |
TCP is slower because it performs more checking and control. | UDP is faster because it has less control and overhead. |
TCP has a larger header size of 20 bytes. | UDP has a smaller header size of 8 bytes. |
TCP provides error checking and retransmits lost packets. | UDP only checks errors but does not retransmit lost packets. |
TCP provides flow control to manage data transfer speed. | UDP does not provide flow control. |
TCP provides congestion control to avoid network overload. | UDP does not provide congestion control. |
TCP is suitable for applications like file transfer, email, and web browsing. | UDP is suitable for applications like video streaming, gaming, and voice calls. |
TCP is more secure and reliable for important data transfer. | UDP is mainly used where speed is more important than reliability. |
Example:
TCP Example:
When downloading a file:
If one packet is lost, TCP sends it again.
So data remains complete.
UDP Example:
In video call:
If one packet is lost, it is ignored.
Because speed is more important than perfect delivery.
8. Difference between Error Control and Flow Control. (GTU Style – Long & Easy)
Introduction:
Both Error Control and Flow Control are important mechanisms in computer networks.
They help in reliable data transmission between sender and receiver.
But their purpose is different:
Error Control checks and corrects errors in data.
Flow Control controls the speed of data transfer.
Difference between Error Control and Flow Control:
| Error Control | Flow Control |
|---|---|
| Error control is a technique used to detect and correct errors during data transmission. | Flow control is a technique used to control the rate of data transmission between sender and receiver. |
| Its main purpose is to ensure that data is received correctly without errors. | Its main purpose is to ensure that the sender does not send data faster than the receiver can handle. |
It deals with damaged, lost, or duplicate packets. | It deals with matching the speed of sender and receiver. |
Error control improves the reliability of communication. | Flow control improves the efficiency of communication. |
It uses methods like error detection and retransmission. | It uses methods like stop-and-wait and sliding window. |
If an error is found, the sender retransmits the data. | If receiver is busy, flow control slows down the sender. |
It mainly focuses on data correctness. | It mainly focuses on data speed management. |
Error control is related to reliability of data transfer. | Flow control is related to controlling data traffic. |
Example: Lost packet is sent again. | Example: Sender waits if receiver is slow. |
Example:
Error Control Example:
If a packet gets damaged during transmission, error control detects it and sends it again.
Flow Control Example:
If the sender sends data too fast and the receiver cannot process it, flow control tells sender to slow down.
9. Explain Connection Establishment and Connection Release. (GTU Style – Long & Easy)
Introduction:
In computer networks, before data transfer starts, a connection must be established between sender and receiver.
After communication is completed, that connection must be released.
This process is handled by the transport layer.
Connection management has two parts:
Connection Establishment
Connection Release
These are important for reliable communication.
1. Connection Establishment
Definition:
Connection Establishment is the process of creating a connection between sender and receiver before sending data.
It ensures that both sides are ready for communication.
This process is mainly used in Transmission Control Protocol (TCP).
Need of Connection Establishment:
It is needed to:
Make sure receiver is ready
Synchronize communication
Allocate resources
Start reliable data transfer
Three-Way Handshake (Connection Establishment)
TCP uses the Three-Way Handshake method.
It has three steps:
Step 1: SYN
Sender sends a SYN (synchronize) message to receiver.
It means:
"I want to start communication."
Step 2: SYN + ACK
Receiver sends SYN + ACK.
It means:
"I am ready and I received your request."
Step 3: ACK
Sender sends ACK.
It means:
"Connection confirmed."
Now connection is established.
Diagram of Connection Establishment:
Sender Receiver
SYN -------------------->
<-------------------- SYN + ACK
ACK -------------------->
Connection Established
Sender Receiver
SYN -------------------->
<-------------------- SYN + ACK
ACK -------------------->
Connection Established
2. Connection Release
Definition:
Connection Release is the process of terminating the connection after data transfer is completed.
It frees network resources.
Need of Connection Release:
It is needed to:
End communication properly
Free memory and resources
Avoid unnecessary connection
Four-Way Handshake (Connection Release)
TCP uses Four-Way Handshake.
It has four steps:
Step 1: FIN
Sender sends FIN (finish).
It means:
"I have finished sending data."
Step 2: ACK
Receiver sends ACK.
It means:
"I received your finish request."
Step 3: FIN
Receiver sends its own FIN.
It means:
"I have also finished."
Step 4: ACK
Sender sends final ACK.
Connection is closed.
Diagram of Connection Release:
Sender Receiver
FIN -------------------->
<-------------------- ACK
<-------------------- FIN
ACK -------------------->
Connection Released
Sender Receiver
FIN -------------------->
<-------------------- ACK
<-------------------- FIN
ACK -------------------->
Connection Released
Advantages of Connection Establishment and Release:
1. Reliable Communication
Ensures proper connection before data transfer.
2. Proper Resource Management
Resources are allocated and released correctly.
3. Safe Termination
Connection ends without data loss.
4. Better Synchronization
Both sender and receiver stay coordinated.
Disadvantages:
1. Takes Extra Time
Connection setup and release need extra steps.
2. More Overhead
Control packets increase traffic.
Conclusion:
Connection Establishment and Connection Release are important processes in transport layer communication. Connection establishment creates a reliable communication path, and connection release safely closes it after data transfer. Together, they ensure organized and reliable communication.
No comments:
Post a Comment