RoutingNET/link_state_routing library

🗺️ Link-State Routing Algorithm

Implements a comprehensive link-state routing algorithm that constructs a complete map of the network topology. This algorithm maintains a full network view and computes optimal routes using shortest path algorithms.

• Time Complexity: O(V² + E) for topology construction and route computation
• Space Complexity: O(V²) for link-state database and routing tables
• Convergence: Fast convergence with immediate topology updates
• Network View: Complete network topology visibility
• Route Computation: Uses Dijkstra's algorithm for optimal paths
• Topology Changes: Immediate propagation of network changes

The algorithm maintains a comprehensive link-state database (LSDB) containing complete network topology information and computes optimal routes using shortest path algorithms with full network visibility.

Example:

final network = <String, Map<String, num>>{
  'A': {'B': 10, 'C': 20, 'D': 15},
  'B': {'A': 10, 'C': 5, 'E': 12},
  'C': {'A': 20, 'B': 5, 'D': 8, 'E': 7},
  'D': {'A': 15, 'C': 8, 'F': 9},
  'E': {'B': 12, 'C': 7, 'F': 11},
  'F': {'D': 9, 'E': 11},
};
final lsr = LinkStateRoutingAlgorithm<String>();
final routes = lsr.computeRoutes(network, 'A');
// Result: Complete routing table with optimal paths from full topology

Classes

LinkStateDatabase<T>

Represents a complete link-state database for the network

LinkStateEntry<T>

Represents a link-state entry with complete network information

LinkStateRouteEntry<T>

Represents a routing table entry with complete path information

LinkStateRoutingAlgorithm<T>

Link-State Routing Algorithm implementation

LinkStateRoutingTable<T>

Represents a complete link-state routing table

Enums

LinkStateStatus

Link state status enumeration

Functions

computeLinkStateRoutes<T>(Map<T, Map<T, num>> network, T sourceNode, {Map<String, dynamic>? topologyOptimizations}) → LinkStateRoutingTable<T>

Convenience function for quick link-state route computation