🌲 Distributed Spanning Tree Simulation

A robust, asynchronous simulation of a distributed Spanning Tree algorithm. This project demonstrates how network nodes can dynamically discover the most efficient path to a root node using local communication only, similar to Distance Vector routing protocols.

🌟 Key Features

• Custom Graph Parsing: Uses Regex to parse flexible graph definitions from text files.
• Asynchronous Simulation: Simulates network jitter and asynchronous PDU processing using randomized node selection.
• Convergence Detection: Automatically stops execution when the network stabilizes (no state changes for N rounds).
• Modern Python: Built using dataclasses, type hinting, and pathlib for clean, maintainable code.

---

⚙️ How It Works

The algorithm is based on the Bellman-Ford principle. The node with the lowest ID is statically elected as the Root. Every other node initializes its distance to infinity ($\infty$).

In every round of the simulation, nodes broadcast their current distance to neighbors. A node $v$ updates its distance and "Next Hop" if it receives a PDU from neighbor $u$ satisfying:

$$D_v > D_u + C_{u,v}$$

Where:

• $D_v$ is the current shortest distance of node $v$ to the Root.
• $C_{u,v}$ is the cost of the link between $u$ and $v$.

---

🚀 Getting Started

Prerequisites

• Python 3.8 or higher.
• No external dependencies (Standard Library only).

Installation

Clone the repository:

git clone [https://github.com/yourusername/spanning-tree-sim.git](https://github.com/yourusername/spanning-tree-sim.git)
cd spanning-tree-sim

Usage

1. Create an input file named graph_input.txt in the root directory (see format below).
2. Run the simulation:

python main.py

3. Check the output:
   • Console: Displays the routing table (Next Hop for every node).
   • File: Generates spanning_tree_result.txt containing the final tree structure.

---

📝 File Formats

Input (graph_input.txt)

The parser allows comments (//) and is whitespace-tolerant.

1. Define the Graph Name.
2. Define Nodes (Name=ID;).
3. Define Edges (NodeA-NodeB:Cost;).

Graph MyNetwork // Name of the graph

// Node Definitions
RouterA = 1;
RouterB = 2;
RouterC = 3;

// Edge Definitions (Name-Name: Cost)
RouterA - RouterB : 10;
RouterB - RouterC : 5;
RouterA - RouterC : 20;

Output (spanning_tree_result.txt)

The script exports the edges that form the Minimum Spanning Tree (MST).

Spanning-Tree of MyNetwork {
Root: 1;
RouterB - RouterA;
RouterC - RouterB;
}

---

🧠 Simulation Logic

The core simulation loop runs until the network reaches a stable state (convergence).

Parameter	Value	Description
MAX_ROUNDS	10,000	Failsafe to prevent infinite loops.
STABILITY_THRESHOLD	100	Rounds without change required to declare convergence.
Selection Strategy	Random	A random node acts as the "sender" in each step to simulate async behavior.

Authors

• @kargfel