Internet Router
Simulation
Using Packet Routing Graph Algorithm
Bellman-Ford Algorithm
Academic Documentation
By Sohaib Maqsood
Usman Ali
Table of Contents
Right-click the TOC and select "Update Field" to refresh page numbers
Table of Contents...........................................................................................................................2
1. Introduction................................................................................................................................5
1.1 What is Packet Routing?......................................................................................................5
1.2 Why is Routing Important?..................................................................................................5
1.3 Role of Graph Algorithms...................................................................................................5
2. Literature Review......................................................................................................................7
3. System Overview / Methodology..............................................................................................8
3.1 Network as a Graph.............................................................................................................8
3.2 Graph Representation..........................................................................................................8
3.3 Packet Movement Process...................................................................................................9
4. Algorithm Explanation............................................................................................................11
4.1 Algorithm Overview..........................................................................................................11
4.2 Step-by-Step Process.........................................................................................................11
Step 1: Initialize...............................................................................................................11
Step 2: Relax Edges..........................................................................................................11
Step 3: Repeat...................................................................................................................11
Step 4: Detect Negative Cycles........................................................................................11
5. Pseudocode...............................................................................................................................13
6. Dry Run Example....................................................................................................................14
6.1 Example Graph..................................................................................................................14
6.2 Iteration Trace....................................................................................................................14
9. Conclusion................................................................................................................................15
10. References...............................................................................................................................16
Abstract
This project presents a simple simulation of an Internet router system using graph-based
packet routing techniques. In computer networks, routers are responsible for sending data
packets from a source to a destination through the best possible path. To achieve this, the
network is represented as a graph where routers act as nodes and connections between them
act as edges with certain costs such as distance or time.
The main focus of this project is the Bellman-Ford algorithm, which is used to find the
shortest path between nodes in a network. This algorithm is especially useful because it can
handle networks with varying path costs and can detect negative cycles, making it reliable for
real-world routing applications. The working of the algorithm is demonstrated through a step-
by-step dry run and visual representations.
This study also compares different routing algorithms and highlights their advantages and
limitations. The results show that graph algorithms play a very important role in efficient
packet routing and help improve network performance. Overall, this project provides a clear
and beginner-friendly understanding of how routing works in modern computer networks.
1. Introduction
The Internet has become an essential part of modern life, connecting billions of devices
across the globe. At the heart of this massive network are routers, specialized devices that
direct data packets from source to destination. Understanding how routers make decisions
about where to send data is fundamental to comprehending how the Internet functions.
A router is essentially a networking device that forwards data packets between computer
networks. When you send an email, stream a video, or browse a website, your data is broken
into small pieces called packets. Each packet travels through multiple routers before reaching
its destination. The process of determining the best path for these packets is called routing.
1.1 What is Packet Routing?
Packet routing is the process of selecting the best path for data packets to travel from their
source to their destination. Imagine sending a letter through the postal system. The letter
might pass through several sorting facilities before reaching its destination. Similarly, data
packets pass through multiple routers, each making a decision about where to send the packet
next.
The key challenge in routing is finding the most efficient path. This efficiency can be
measured in various ways: the shortest distance, the lowest cost, the fastest transmission time,
or the most reliable connection. Graph algorithms provide mathematical tools to solve these
routing problems systematically.
1.2 Why is Routing Important?
Efficient routing is crucial for several reasons. First, it ensures that data reaches its
destination quickly, providing a smooth user experience. Second, it helps network providers
manage their infrastructure costs by utilizing available bandwidth effectively. Third, robust
routing algorithms can adapt to network changes, such as link failures or congestion,
maintaining connectivity even when problems occur.
1.3 Role of Graph Algorithms
Computer networks can be modeled as graphs, where routers are represented as nodes (or
vertices) and the connections between them are represented as edges. Each edge can have a
weight representing the cost, distance, or delay of that connection. This graph representation
allows us to apply well-established graph algorithms to solve routing problems.
The Bellman-Ford algorithm is one such graph algorithm that has been widely used in
network routing. Unlike some other algorithms, Bellman-Ford can handle negative edge
weights and can detect negative cycles in the graph. These properties make it particularly
useful in certain routing scenarios, such as the Routing Information Protocol (RIP).
Internet Router Simulation using Bellman-Ford Algorithm
2. Literature Review
This section presents a comprehensive review of existing research on routing algorithms and
their applications in network communication. The following table summarizes key
contributions in this field:
Problem Addressed Proposed Method Results / Achievements Limitations
Efficient shortest path Accurate path calculation
Slower performance
computation in Bellman-Ford algorithm with ability to handle
with O(|V|*|E|)
networks with for distance vector negative edge weights
complexity compared
potential negative routing and detect negative
to greedy approaches
weights cycles
Fast shortest path Cannot handle
Dijkstra's algorithm Optimal time complexity
finding in networks negative edge weights
using priority queue of O(|E|+|V|log|V|) for
with non-negative or detect negative
optimization sparse graphs
weights cycles
Requires domain-
Heuristic-based A* search algorithm Significantly reduced specific heuristic
pathfinding in large- with admissible search space and faster design; performance
scale road networks heuristics query response times depends on heuristic
quality
Query times in High preprocessing
Scalable routing in Contraction Hierarchies
milliseconds for time and memory
continental-scale road with node contraction
networks with millions of requirements for graph
networks preprocessing
nodes contraction
Limited to 15 hops
Distributed routing in Simple implementation
RIP protocol using maximum; slow
small to medium with automatic route
distance-vector approach convergence during
autonomous systems convergence
topology changes
Higher memory and
Link-state routing in OSPF protocol with Fast convergence and
CPU requirements on
large enterprise Dijkstra's shortest path hierarchical network
routers compared to
networks first support through areas
distance-vector
Dynamic routing in AODV on-demand Reduced routing Route discovery
mobile ad-hoc distance vector routing overhead by establishing latency and potential
networks protocol routes only when needed for routing loops
7 / 18
Internet Router Simulation using Bellman-Ford Algorithm
Problem Addressed Proposed Method Results / Achievements Limitations
during reconstruction
8 / 18
Internet Router Simulation using Bellman-Ford Algorithm
3. System Overview / Methodology
3.1 Network as a Graph
In our simulation, we model a computer network as a weighted directed graph. This
abstraction allows us to apply graph theory concepts to solve routing problems:
• Nodes (Vertices): Represent routers in the network
• Edges: Represent physical or logical connections between routers
• Weights: Represent the cost, distance, or delay of each connection
Figure 1: Internet Router Network Topology
3.2 Graph Representation
The same network can be represented mathematically as a graph G = (V, E), where V is the
set of vertices (routers) and E is the set of edges (connections). Each edge has an associated
weight representing the cost of traversing that connection.
9 / 18
Internet Router Simulation using Bellman-Ford Algorithm
Figure 2: Weighted Graph Representation of Network
3.3 Packet Movement Process
When a packet needs to be sent from a source router to a destination router, the following
steps occur:
0. Source router checks its routing table to determine the next hop
1. Packet is forwarded to the next router in the path
2. Each intermediate router repeats the process until destination is reached
3. Destination router receives and processes the packet
10 / 18
Internet Router Simulation using Bellman-Ford Algorithm
Figure 3: Packet Flow Through Router Network
11 / 18
Internet Router Simulation using Bellman-Ford Algorithm
4. Algorithm Explanation
The Bellman-Ford algorithm is a single-source shortest path algorithm that computes the
shortest paths from a source vertex to all other vertices in a weighted graph. It is particularly
useful because it can handle negative edge weights and detect negative cycles.
4.1 Algorithm Overview
The algorithm works by iteratively relaxing edges. Relaxation is the process of checking
whether going through a particular edge provides a shorter path to a vertex. By repeating this
process enough times, the algorithm converges to the shortest paths.
4.2 Step-by-Step Process
Step 1: Initialize
Set the distance to the source vertex to 0 and the distance to all other vertices to infinity. This
represents that we know we can reach the source with zero cost, but we do not yet know how
to reach any other vertex.
Step 2: Relax Edges
For each edge (u, v) with weight w, check if the distance to v can be improved by going
through u. If dist[u] + w < dist[v], update dist[v] to dist[u] + w. This is called relaxing the
edge.
Step 3: Repeat
Repeat the relaxation process for all edges |V| - 1 times, where |V| is the number of vertices.
After |V| - 1 iterations, all shortest paths have been found (assuming no negative cycles).
Step 4: Detect Negative Cycles
Perform one more iteration over all edges. If any distance can still be improved, then a
negative cycle exists in the graph. This is because in a graph without negative cycles, all
shortest paths use at most |V| - 1 edges.
12 / 18
Internet Router Simulation using Bellman-Ford Algorithm
Figure 4: Bellman-Ford Algorithm Flowchart
13 / 18
Internet Router Simulation using Bellman-Ford Algorithm
5. Pseudocode
The following pseudocode describes the Bellman-Ford algorithm in a clear and readable
format:
function BellmanFord(Graph, source):
// Step 1: Initialize distances
for each vertex v in Graph:
distance[v] = infinity
predecessor[v] = null
distance[source] = 0
// Step 2: Relax edges repeatedly
for i = 1 to |V| - 1:
for each edge (u, v) with weight w in Graph:
if distance[u] + w < distance[v]:
distance[v] = distance[u] + w
predecessor[v] = u
// Step 3: Check for negative cycles
for each edge (u, v) with weight w in Graph:
if distance[u] + w < distance[v]:
return "Graph contains negative cycle"
return distance, predecessor
Table 2: Bellman-Ford Algorithm Pseudocode
14 / 18
Internet Router Simulation using Bellman-Ford Algorithm
6. Dry Run Example
To illustrate how the Bellman-Ford algorithm works, let us perform a dry run on a simple 5-
node graph. We will trace the algorithm's execution step by step, showing how distances are
updated in each iteration.
6.1 Example Graph
Consider a graph with 5 vertices (A, B, C, D, E) and the following edges with their weights:
• A -> B: 4
• A -> D: 3
• B -> C: 2
• B -> D: 1
• B -> E: 5
• C -> E: 3
• D -> E: 2
6.2 Iteration Trace
Starting from vertex A as the source, the algorithm proceeds as follows:
Iteration Distances (A,B,C,D,E) Updates Made
Initial (0, INF, INF, INF, INF) Source A initialized to 0
1 (0, 4, INF, 3, INF) B=4 (via A), D=3 (via A)
2 (0, 4, 6, 3, 5) C=6 (via B), E=5 (via D)
3 (0, 4, 6, 3, 5) No updates - converged
4 (0, 4, 6, 3, 5) No updates - converged
Table 3: Bellman-Ford Algorithm Dry Run - Iteration Trace
After 4 iterations (|V| - 1 = 5 - 1 = 4), the algorithm has converged. The final shortest
distances from A are: A=0, B=4, C=6, D=3, E=5. A fifth iteration confirms no negative cycles
exist since no distances are updated.
15 / 18
Internet Router Simulation using Bellman-Ford Algorithm
7. Conclusion
This documentation has presented a comprehensive overview of Internet router simulation
using the Bellman-Ford algorithm. We have explored how computer networks can be
modeled as graphs, how the Bellman-Ford algorithm computes shortest paths, and how this
algorithm is applied in real-world routing protocols.
The Bellman-Ford algorithm, despite being one of the older shortest-path algorithms, remains
relevant today due to its unique ability to handle negative weights and detect negative cycles.
While modern networks often use more efficient algorithms like Dijkstra's or specialized
protocols like OSPF, understanding Bellman-Ford provides valuable insights into the
fundamentals of network routing.
For students and practitioners in computer networking, mastering graph algorithms like
Bellman-Ford is essential. These algorithms form the theoretical foundation upon which the
Internet's routing infrastructure is built, enabling the seamless communication that powers
our digital world.
16 / 18
Internet Router Simulation using Bellman-Ford Algorithm
8. References
[1] R. Bellman, "On a Routing Problem," Quarterly of Applied Mathematics, vol. 16, no. 1, pp. 87-90, 1958.
[2] L. R. Ford Jr., "Network Flow Theory," RAND Corporation Paper P-923, 1956.
[3] E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik, vol. 1, pp.
269-271, 1959.
[4] C. E. Perkins and P. Bhagwat, "Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV)
for Mobile Computers," ACM SIGCOMM Computer Communication Review, vol. 24, no. 4, pp. 234-
244, 1994.
[5] A. V. Goldberg and C. Harrelson, "Computing the Shortest Path: A* Search Meets Graph Theory,"
Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 156-165, 2005.
[6] R. Geisberger, P. Sanders, D. Schultes, and D. Delling, "Contraction Hierarchies: Faster and Simpler
Hierarchical Routing in Road Networks," Experimental Algorithms, pp. 319-333, 2008.
[7] J. Moy, "OSPF Version 2," RFC 2328, Internet Engineering Task Force, 1998.
17 / 18
Internet Router Simulation using Bellman-Ford Algorithm
Internet Router Simulation
Using Bellman-Ford Algorithm
Academic Documentation
18 / 18