NETWORK PACKET
ROUTING SIMULATION
Using graphs and bfs queues
Presented [Link] Manya-24261A05A9
By: [Link] reddy-24261A05B0
[Link] Nikki-24261A05B1
Richa Tiwari-24261A05B2
PROBLEM
STATEMENT
• Computers in a network exchange data using packets.
• Packets travel through intermediate computers until they reach the
destination.
• Routing helps find a valid path from source to destination.
• We simulate packet forwarding using graphs and queue-based BFS.
• Realistic model of a network to study and evaluate routing protocols or
network performance under various conditions, focusing on issues like
packet loss, latency, throughput, and congestion. Such a problem
might involve simulating a specific network topology (e.g., wired,
wireless, ad hoc) and traffic patterns to analyze how different routing
algorithms (like OSPF or Dijkstra) perform in finding optimal paths and
ensuring efficient packet delivery.
OBJECTIVE
Model computers as nodes in a graph
→ Each computer in a network can be represented as a node
in a graph, and connections between computers (cables,
links, etc.) are the edges
.
Use Breadth-First Search (BFS) to find a path
→ BFS is ideal for finding the shortest path in an unweighted
network graph (like hops in packet forwarding).
Simulate packet forwarding step-by-step
→ Instead of directly jumping to the destination, the program
shows how the packet moves through intermediate nodes.
Display the routing path from Source → Destination
→ Final output will show the sequence of computers traversed
DESIGN
Algorithm
Graph Representation
• Use Breadth-First Search (BFS) with a
• Nodes = Computers / Routers.
queue.
• Edges = Network Connections
• BFS explores all neighbors of a node
(Ethernet, wireless links).
before moving deeper, so it
• Graph stored as adjacency list
guarantees the shortest path in terms
(saves memory, easier for of hops.
sparse networks). • BFS ensures shortest route in hops.
• Suitable for unweighted networks
(where all links are equal).
Input: Output:
• Source computer (where packet • Routing path (source → … →
originates). destination).
• Destination computer (target • Step-by-step forwarding
node). simulation (packet forwarding
• Network connections (edges log).
between computers).
FLOWCHART
ALGORITHM
[Link] from the source node.
[Link] a queue with the source node and
mark it as visited.
[Link] the queue is not empty:
[Link] the current node.
[Link] it matches the destination, stop and print
the path.
[Link], enqueue all its unvisited neighbors and
mark them visited.
[Link], display the discovered shortest path.
note:BFS ensures that the first time we reach
the destination, we’ve found the shortest path.
EXAMPLE:
GRAPH: SOURCE: A
DESTINATION: F
A -- B -- C
BFS ROUTING STEPS:
| | | • Start at A → neighbors = {B, D}
D -- E -- F • Forward packet to B and D.
• Explore B → neighbors {C, E}.
• Forward packet to C, E.
• Explore C → neighbor {F}.
• Destination F found → STOP.
ROUTING PATH:
A->B->C->F
IMPLEMENTATION
• Language: Python
• Graph Representation:
Adjacency list
(dictionary).
• Algorithm: BFS with
queue
([Link]).
• Tracking: Keep a visited
set and a dictionary
parent to reconstruct
the path.
OUTPUT
CONCLUSIO
• Successfully simulated packet routing in a computer network.
• Used BFS to guarantee shortest path discovery.
• Simulation displayed step-by-step packet forwarding like a real
network.
• Demonstrates how routing works inside protocols like RIP or OSPF
(when unweighted).
• This project builds a foundation to explore weighted routing
algorithms (like Dijkstra’s for OSPF).
Applications(real networking context):
• Routing Protocols: BFS is similar to RIP (Routing Information
Protocol) which finds shortest paths in hop counts.
• Network Simulation: Helps students understand how packets move
in a network.
N
• Troubleshooting: Visualization of packet movement can explain
delays, failures.
• Learning Tool: Demonstrates how routers forward packets.