RoutingNET/ospf_algorithm library

🌐 OSPF (Open Shortest Path First) Algorithm

Implements the Open Shortest Path First routing protocol based on Dijkstra's algorithm for link-state routing. OSPF constructs a complete network topology and computes shortest paths using link costs and network state information.

• Time Complexity: O(V² + E) for Dijkstra's algorithm
• Space Complexity: O(V²) for link-state database and routing tables
• Convergence: Fast convergence with link-state updates
• Area Support: Hierarchical routing with areas and backbone
• Link Types: Point-to-point, broadcast, non-broadcast, point-to-multipoint

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

Example:

final network = <String, Map<String, num>>{
  'A': {'B': 10, 'C': 20},
  'B': {'A': 10, 'D': 15},
  'C': {'A': 20, 'D': 25},
  'D': {'B': 15, 'C': 25},
};
final ospf = OSPFAlgorithm<String>();
final routes = ospf.computeRoutes(network, 'A');
// Result: Complete routing table with optimal paths

Classes

LinkStateAdvertisement<T>

Represents a link-state advertisement (LSA) with network information

OSPFAlgorithm<T>

OSPF Algorithm implementation with area support and link-state database

OSPFRouteEntry<T>

Represents a routing table entry with OSPF-specific information

OSPFRoutingTable<T>

Represents the OSPF routing table with area support

Enums

LinkStateType

Types of link-state advertisements

Functions

computeOSPFRoutes<T>(Map<T, Map<T, num>> network, T sourceRouter, {int areaId = 0}) → OSPFRoutingTable<T>

Convenience function for quick OSPF route computation