‘
, NotesNeo
Unit 3 : Routing Algorithms, Transport and Application Layer
Syllabus :
Routing Algorithms: Introduction to routing, Shortest Path Algorithm, Flooding,
Hierarchical Routing, Link State and Distance Vector Routing.
Transport Layer: Transport layer functions and services, Process to Process
Communication, User Datagram Protocol (UDP), Transmission Control Protocol
(TCP), TCP connection management.
Application Layer: Application layer functions and services, Domain Name Space
(DNS), EMAIL, File Transfer Protocol (FTP), HTTP, SNMP.
Section 1 : Routing Algorithms
1.1 Introduction to Routing
Routing is the process of selecting paths within a network along which data can be
transferred from a source to a destination. This function is performed by specialized
devices known as routers.
Routers: Devices that forward data packets between computer networks, making
decisions based on the network's layout.
Key Points
● Router Function: Operates at the network layer in the OSI model and the
internet layer in the TCP/IP model.
● Packet Forwarding: A router forwards packets based on information
available in the packet header and its forwarding table.
● Routing Algorithms: Software responsible for determining the optimal path
for packet transmission.
● Metrics: Used by routing protocols to determine the best path for packet
delivery (e.g., hop count, bandwidth, delay, current load).
Routing Metrics and Costs
Routing metrics and costs help determine the best route to the destination by
evaluating network variables.
Common Metrics
1. Hop Count: The number of intermediary devices (routers) a packet must
traverse to reach its destination. The route with the least hop count is
preferred.
2. Delay: The time taken by a router to process, queue, and transmit a
datagram to an interface. The route with the lowest delay is preferred.
3. Bandwidth: The capacity of a link, measured in bits per second. Higher
bandwidth links are preferred.
1
, NotesNeo
4. Load: The degree to which a network resource (router or link) is busy. It can
be measured by CPU utilization or packets processed per second.
5. Reliability: A metric indicating how often a network link fails and how easily
it can be repaired. It is typically a numeric value assigned by the system
administrator.
Types of Routing
Routing can be classified into three categories: Static Routing, Default Routing, and
Dynamic Routing.
1. Static Routing
● Definition: Also known as Non-adaptive Routing, where routes are manually
added to the routing table by the administrator.
● Characteristics:
○ Routes are predefined and do not change based on network
conditions.
○ No overhead on CPU usage of the router.
○ No bandwidth usage between routers.
○ Provides security through controlled routing.
● Advantages: No CPU overhead, no bandwidth usage, and higher security.
● Disadvantages: Difficult to manage in large networks and requires extensive
knowledge of network topology.
2. Default Routing
● Definition: A technique where a router is configured to send all packets to a
single next-hop device, regardless of the destination network.
● Characteristics:
○ Used when networks have a single exit point.
○ Useful for networks with bulk transmission to the same hop device.
○ The router chooses the default route if no specific route is mentioned.
● Advantages: Simple configuration for networks with a single exit point.
● Disadvantages: Inefficient for networks with multiple exit points.
3. Dynamic Routing
● Definition: Also known as Adaptive Routing, where routers dynamically
discover and adjust routes based on network conditions or topology changes.
● Characteristics:
○ Uses protocols like RIP (Routing Information Protocol) and OSPF
(Open Shortest Path First).
○ Automatically adjusts routes if a link goes down.
○ Routers must use the same dynamic routing protocol to exchange
routes.
○ Changes in network topology are broadcast to all other routers.
● Advantages: Easier to configure, more effective in adapting to changes in
network conditions.
● Disadvantages: Higher CPU and bandwidth usage, less secure compared to
static and default routing.
2
, NotesNeo
1.2 Routing Algorithms
To transfer data packets from source to destination, the network layer must
determine the best route. This is done using routing algorithms, which can be
classified as adaptive or non-adaptive.
Adaptive routing algorithms dynamically adjust to network changes, while non-
adaptive algorithms rely on predefined routes.
Adaptive Routing Algorithm (Dynamic Routing)
Adaptive routing algorithms, also known as dynamic routing algorithms, adjust to
changing network conditions and are dynamic in nature. They continuously adapt to
the current state of the network, such as traffic load and topology changes. These
algorithms are further classified into:
1. Centralized Algorithm
Definition: Known as a global routing algorithm, it computes the least-cost path
using complete and global knowledge of the network's topology and link costs.
Example: Link State Algorithm
● Overview: Each router has complete information about the network
topology. Routers share link state information with all other routers and use
algorithms like Dijkstra’s to compute the shortest path.
● Advantages: Accurate and up-to-date information, quick convergence.
● Disadvantages: High overhead due to flooding of link state information,
complex and resource-intensive.
2. Isolation Algorithm
● Definition: Uses only local information to obtain routing data rather than
gathering information from other nodes in the network.
● Example: Local optimization techniques where decisions are made based on
locally observed parameters without knowledge of the wider network.
3. Distributed Algorithm
Definition: Also known as a decentralized algorithm, it computes the least-cost path
iteratively and in a distributed manner. Each router only knows the costs of its
directly connected links.
Example: Distance Vector Algorithm
● Overview: Each router maintains a table (vector) of the minimum distance to
every other router and shares this information with its immediate neighbors.
● Advantages: Simple to implement, suitable for smaller networks.
● Disadvantages: Slow convergence, prone to routing loops and count-to-
infinity problems.
Non-Adaptive Routing Algorithm (Static Routing)
3
, NotesNeo
Unit 3 : Routing Algorithms, Transport and Application Layer
Syllabus :
Routing Algorithms: Introduction to routing, Shortest Path Algorithm, Flooding,
Hierarchical Routing, Link State and Distance Vector Routing.
Transport Layer: Transport layer functions and services, Process to Process
Communication, User Datagram Protocol (UDP), Transmission Control Protocol
(TCP), TCP connection management.
Application Layer: Application layer functions and services, Domain Name Space
(DNS), EMAIL, File Transfer Protocol (FTP), HTTP, SNMP.
Section 1 : Routing Algorithms
1.1 Introduction to Routing
Routing is the process of selecting paths within a network along which data can be
transferred from a source to a destination. This function is performed by specialized
devices known as routers.
Routers: Devices that forward data packets between computer networks, making
decisions based on the network's layout.
Key Points
● Router Function: Operates at the network layer in the OSI model and the
internet layer in the TCP/IP model.
● Packet Forwarding: A router forwards packets based on information
available in the packet header and its forwarding table.
● Routing Algorithms: Software responsible for determining the optimal path
for packet transmission.
● Metrics: Used by routing protocols to determine the best path for packet
delivery (e.g., hop count, bandwidth, delay, current load).
Routing Metrics and Costs
Routing metrics and costs help determine the best route to the destination by
evaluating network variables.
Common Metrics
1. Hop Count: The number of intermediary devices (routers) a packet must
traverse to reach its destination. The route with the least hop count is
preferred.
2. Delay: The time taken by a router to process, queue, and transmit a
datagram to an interface. The route with the lowest delay is preferred.
3. Bandwidth: The capacity of a link, measured in bits per second. Higher
bandwidth links are preferred.
1
, NotesNeo
4. Load: The degree to which a network resource (router or link) is busy. It can
be measured by CPU utilization or packets processed per second.
5. Reliability: A metric indicating how often a network link fails and how easily
it can be repaired. It is typically a numeric value assigned by the system
administrator.
Types of Routing
Routing can be classified into three categories: Static Routing, Default Routing, and
Dynamic Routing.
1. Static Routing
● Definition: Also known as Non-adaptive Routing, where routes are manually
added to the routing table by the administrator.
● Characteristics:
○ Routes are predefined and do not change based on network
conditions.
○ No overhead on CPU usage of the router.
○ No bandwidth usage between routers.
○ Provides security through controlled routing.
● Advantages: No CPU overhead, no bandwidth usage, and higher security.
● Disadvantages: Difficult to manage in large networks and requires extensive
knowledge of network topology.
2. Default Routing
● Definition: A technique where a router is configured to send all packets to a
single next-hop device, regardless of the destination network.
● Characteristics:
○ Used when networks have a single exit point.
○ Useful for networks with bulk transmission to the same hop device.
○ The router chooses the default route if no specific route is mentioned.
● Advantages: Simple configuration for networks with a single exit point.
● Disadvantages: Inefficient for networks with multiple exit points.
3. Dynamic Routing
● Definition: Also known as Adaptive Routing, where routers dynamically
discover and adjust routes based on network conditions or topology changes.
● Characteristics:
○ Uses protocols like RIP (Routing Information Protocol) and OSPF
(Open Shortest Path First).
○ Automatically adjusts routes if a link goes down.
○ Routers must use the same dynamic routing protocol to exchange
routes.
○ Changes in network topology are broadcast to all other routers.
● Advantages: Easier to configure, more effective in adapting to changes in
network conditions.
● Disadvantages: Higher CPU and bandwidth usage, less secure compared to
static and default routing.
2
, NotesNeo
1.2 Routing Algorithms
To transfer data packets from source to destination, the network layer must
determine the best route. This is done using routing algorithms, which can be
classified as adaptive or non-adaptive.
Adaptive routing algorithms dynamically adjust to network changes, while non-
adaptive algorithms rely on predefined routes.
Adaptive Routing Algorithm (Dynamic Routing)
Adaptive routing algorithms, also known as dynamic routing algorithms, adjust to
changing network conditions and are dynamic in nature. They continuously adapt to
the current state of the network, such as traffic load and topology changes. These
algorithms are further classified into:
1. Centralized Algorithm
Definition: Known as a global routing algorithm, it computes the least-cost path
using complete and global knowledge of the network's topology and link costs.
Example: Link State Algorithm
● Overview: Each router has complete information about the network
topology. Routers share link state information with all other routers and use
algorithms like Dijkstra’s to compute the shortest path.
● Advantages: Accurate and up-to-date information, quick convergence.
● Disadvantages: High overhead due to flooding of link state information,
complex and resource-intensive.
2. Isolation Algorithm
● Definition: Uses only local information to obtain routing data rather than
gathering information from other nodes in the network.
● Example: Local optimization techniques where decisions are made based on
locally observed parameters without knowledge of the wider network.
3. Distributed Algorithm
Definition: Also known as a decentralized algorithm, it computes the least-cost path
iteratively and in a distributed manner. Each router only knows the costs of its
directly connected links.
Example: Distance Vector Algorithm
● Overview: Each router maintains a table (vector) of the minimum distance to
every other router and shares this information with its immediate neighbors.
● Advantages: Simple to implement, suitable for smaller networks.
● Disadvantages: Slow convergence, prone to routing loops and count-to-
infinity problems.
Non-Adaptive Routing Algorithm (Static Routing)
3
