Routing algorithms:-

Routing algorithms are a fundamental aspect of computer networking that determines the best path for
data packets to travel from a source to a destination in a network.

They are crucial for efficient data transmission and are used in various network types, including the
internet, local area networks (LANs), and wide area networks (WANs).

a. Static (Non-Adaptive) Routing Algorithms:

 In Static Routing Algorithms, The network connection is established between source and
destination depending on any parameter.
 The Routing decision is made off line on estimates of current traffic and topology.
 The pre-calculated paths are then loaded to the routing table and are fixed for a longer
period.
 Static routing is suitable for small networks.
 The disadvantage of static routing is its inability to respond quickly to network failure.
 Static Algorithms are the following:
o Shortest Path Routing
o Flooding
o Flow Based Routing
b. Dynamic (Adaptive) Routing Algorithms:
 Dynamic Routing Algorithms change their routing decision if there is change in topology,
traffic.
 Each router continuously checks the network status by communicating with neighbours.
 Thus a change in network topology is eventually propagated to all the routers.
 Based on this information gathered, each router computes the suitable path to the
destination.
 The main disadvantage of dynamic routing is its complexity in the router.
 Dynamic Algorithms are the following:
 o Distance Vector Routing
o Link State Routing
o Hierarchical Routing
o Broadcast Routing

• Shortest Path Routing:

• It is a non-adaptive routing algorithm that is very simple, easy to understand and easy to
implement.

• In this algorithm, a graph of subnet is drawn, with each node of the graph representing a
router and each arc of the graph representing a communication link.

• To choose a route between a pair of routers this algorithm finds the shortest path between
them on the graph.

• The path length between each node is measured as a function of distance, average traffic,
communication cost, bandwidth etc.

• There are many algorithms to computer the shortest path between two nodes of a graph. The
main are:

– Dijkstra’s Shortest Path Algorithm

• Dijkstra's Algorithm: It finds the shortest path between nodes in a graph. It's commonly
used in network routing protocols and helps in determining the best path based on the least
accumulated cost.

• Example: Consider a scenario where a GPS application finds the shortest path between two
locations.

Distance Vector Routing:

 It is the type of routing protocol that was originally used on the internet.
 In distance vector routing, each router periodically shares its knowledge about the entire
network with its neighbours.
 In this routing, each router maintains a routing table containing one entry for each router in
the subnet.
 A route using a distance vector routing protocol does not have the knowledge of the entire
path to a destination network.
Advantages of Distance Vector Routing:

 Simple and efficient in small networks.

 The algorithm required to calculate routing tables from the routing information received from
other routers is simple.
 Simple implementation and maintenance.
 Low resource requirements.

Disadvantages of Distance Vector Routing:

 Slow Convergence.
 Limited Scalability.
 Routing Loops.
 Heavy Administrative Burden.
 Distance Vector Routing Algorithm Is Bellman Ford Algo.

 Bellman-Ford Algorithm: Similar to Dijkstra's algorithm, it computes the shortest path in a

weighted graph but can handle negative edge weights. It's used in distance vector routing
protocols like RIP (Routing Information Protocol).

Link State Routing Algorithm:

 It is more robust and used more widely in larger networks.

 Link State Routing Protocols can transmit routing information to all other routers running the
same protocol, not just directly connected neighbor’s.

The Link State Routing is simple and each router performs the following functions:

 Discover its neighbors and obtain their network addresses.

 Measures the delay or cost to each of its neighbors.
 Construct a packet containing the network addresses and the cost/delay of all the neighbors.
 Send this packet to all other routers.
 Compute the shortest path to every other router. Dijkstra’s algorithm is used for this purpose.

Advantages of Link State Routing:

 Link State Routing reacts more quickly, and in a bounded amount of time, to connectivity
changes.
 Low network overhead.
 Low convergence time.
 The ability to scale to large and very large networks.
  Changes in topology can be sent out immediately, so convergence can be quicker.

Disadvantages of Link State Routing:

 More complex and difficult to configure.

 Requires additional memory to create and maintain the link state database.
 Requires more CPU processing than distance vector routing protocol.
 Requires more storage and more computing to run.

Congestion:

 Rushing of too many packets to a node or a part of network, may sometimes affect the
network.
 The network performance may degrade because of this.
 Such situation is called as Congestion.
 Congestion in a network may occur if the load on the network is greater than the capacity of
the network.

Congestion Control:

 It refers to the mechanisms and techniques to control the congestion and keep the load below
the capacity.
 Congestion control is a crucial aspect of computer networking that involves managing the
flow of data in a network to prevent congestion and maintain optimal performance.
Several congestion control mechanisms are employed in networking to address these
issues:
 Flow Control:
 End-to-End Flow Control: In end-to-end flow control, the source and destination systems
regulate the rate at which data is sent and received. This helps prevent congestion by
adjusting the transmission rate based on network conditions.
 Traffic Policing and Shaping:
 Traffic Policing: Involves monitoring and controlling the rate of data traffic to ensure it
adheres to pre-defined policies. If the traffic exceeds the specified limits, it can be dropped or
marked for further action.

Algorithms to control the congestion are:

Leaky Bucket Algorithm:

 The leaky bucket algorithm is used to control the rate at which traffic is sent to the network.
  It provides a mechanism by which bursty traffic can be shaped to present a steady stream of
traffic to the network, as opposed to traffic with irregular bursts of low volume and high
volume flows.

The Algorithm is as follows:

 Arriving packets are placed in a bucket with a hole in the bottom.

 The bucket can queue at most b bytes.
 A packet that arrives when the bucket is full is discarded.
 Packets drain through the hole in the bucket into the network at a constant rate of r bytes
per second, thus smoothing traffic bursts.

Hierarchical Routing:

 It is a technique commonly used while building large networks.

 As a network grows, the resource requirements for the network’s management and control
functions also grow.
 It does not know anything about the internal structure of other regions.
 Routers just save one record in their table for every other region.
 Hierarchical Routing is a natural way for routing to scale size, network administration and
governance.
 It is important because internet is an interconnection of unequal networks.

Advantages of Hierarchical Routing:

 It reduces the overhead by structuring the network on more levels.

 It needs lesser calculations and updates of routing tables.
 It saves the routing table space.

Disadvantages of Hierarchical Routing:

 The complexity of maintaining the hierarchy may compromise the performance of the routing
protocol.
 The hierarchical routing may face implementation difficulty, because a node selected as a
cluster head may not necessarily have higher processing capability than the other nodes.

Virtual Circuit:-
  Virtual Circuit is the computer network providing connection-oriented service. It is a
connection-oriented network.
 In virtual circuit resource are reserve for the time interval of data transmission between two
nodes.
 This network is a highly reliable medium of transfer.
 Virtual circuits are costly to implement.

Advantages of Virtual Circuit:

 Packets are delivered to the receiver in the same order sent by the sender.
 Virtual circuit is a reliable network circuit.
 There is no need for overhead in each packet.
 Single global packet overhead is used in virtual circuit.
Disadvantages of Virtual Circuit:
 Virtual circuit is costly to implement.
 It provides only connection-oriented service.
 Always a new connection set up is required for transmission.

Datagrams:

 In datagram approach, each packet is routed independently through the network.

 Header is attached to each packet.
 It provides all the information required to route the packet to its destination.
 Each packet is delivered to the destination using a different path and hence they are out of
order.
 Packet shares the transmission line with other packets.
 Datagram approach is also called Connectionless.
 The datagram service is unreliable.
 Failures and Congestions are more frequent in these networks.
 Datagram system is similar to postal system.

• Flooding :-

• In computer networking, Flooding is a routing technique in which a router sends data packets
to all routers connected to it.
• In Flooding, when a data packet arrives at a router, it is broadcasted to all outgoing links. This
means that the packet is sent to all directly connected routers without any specific routing
logic.

• Flooding is commonly used in routing protocols such as OSPF (Open Shortest Path First). In
this context, Flooding helps in the exchange of routing information among routers to
determine the shortest path to a destination.

• An incoming packet to A, will be sent to B, C and D.

• B will send the packet to C and E.

• C will send the packet to B, D and F.

• D will send the packet to C and F.

• E will send the packet to F.

• F will send the packet to C and E.

• Types of Flooding

• 1.Uncontrolled Flooding: Uncontrolled Flooding refers to a type of Flooding in which the

transmission of data packets is not regulated. In this scenario, each router forwards all
incoming data packets to all its neighboring routers indiscriminately. There is no specific
control mechanism in place to manage or limit the propagation of these packets.

• Controlled Flooding: Controlled Flooding is a type of Flooding in which the transmission of

data packets is regulated and managed using specific techniques. Unlike Uncontrolled
Flooding, Controlled Flooding employs methods to control and optimize the dissemination of
data packets within the network.
 • Selective Flooding: Selective Flooding is a routing technique where, instead of broadcasting
a data packet to all available paths, a router selectively forwards the packet only along those
paths that lead in the correct direction or are deemed appropriate based on the network's
routing logic.

• Advantage of flooding:-

• The primary benefit of this is its ease of implementation.

• It is a highly resilient technique. Even if a significant number of routers fail, the packets can
still find a way to reach their destination.

• It always chooses the shortest path.

• All nodes are visited in this technique.

• Disadvantage of flooding

• It generates duplicate data packets, leading to network congestion.

• Sometimes, this technique becomes inefficient.

• When a DOS attack occurs, the reliability of the network decreases due to flooding.

• It consumes a significant amount of bandwidth.

Authentication:-

 Authentication is a crucial component of network security, serving as a mechanism to verify

the identity of users, systems, or entities attempting to access a network or its resources.
 The primary goal of authentication is to ensure that only authorized individuals or systems
gain access to sensitive information or services.
 There are various authentication methods and protocols used in network security. Here are
some key aspects of authentication in network security:

Types of Authentication:

 Password-based Authentication: Users provide a unique combination of characters

(password) to prove their identity.
 Biometric Authentication: This involves the use of physiological or behavioral
characteristics such as fingerprints, retina scans, or voice recognition.
 Multi-Factor Authentication (MFA): Combining two or more authentication factors (e.g.,
password, token, fingerprint) to enhance security.
 Certificate-based Authentication: Involves digital certificates to authenticate the identity of
users or systems.