computeRoutes method

BGPRoutingTable<T> computeRoutes(Map<T, Map<T, num>> asTopology, T sourceAS, { Map<String, dynamic>? policies, })

Computes complete BGP routing table for a source AS

asTopology - AS topology as adjacency list sourceAS - Source AS for routing table computation policies - Optional routing policies to apply

Returns a complete BGP routing table with optimal paths

Throws ArgumentError if source AS doesn't exist in topology

Implementation

BGPRoutingTable<T> computeRoutes(
  Map<T, Map<T, num>> asTopology,
  T sourceAS, {
  Map<String, dynamic>? policies,
}) {
  // Input validation
  if (!asTopology.containsKey(sourceAS)) {
    throw ArgumentError('Source AS $sourceAS not found in topology');
  }

  // Initialize routing table with direct connections
  final routes = <T, BGPRouteEntry<T>>{};
  final alternativeRoutes = <T, List<BGPRouteEntry<T>>>{};
  final now = DateTime.now();

  // Add source AS to itself
  routes[sourceAS] = BGPRouteEntry<T>(
    destination: sourceAS,
    nextHop: null,
    asPathLength: 0,
    asPath: <int>[],
    origin: BGPOrigin.igp,
    localPreference: _defaultLocalPreference,
    med: 0,
    lastUpdate: now,
    isDirectlyConnected: true,
    advertisingAS: sourceAS as int,
  );

  // Add directly connected ASes
  final directNeighbors = asTopology[sourceAS]!;
  for (final neighbor in directNeighbors.keys) {
    final route = BGPRouteEntry<T>(
      destination: neighbor,
      nextHop: neighbor,
      asPathLength: 1,
      asPath: <int>[sourceAS as int],
      origin: BGPOrigin.egp,
      localPreference: _defaultLocalPreference,
      med: 0,
      lastUpdate: now,
      isDirectlyConnected: true,
      advertisingAS: neighbor as int,
    );

    routes[neighbor] = route;
    alternativeRoutes[neighbor] = [route];
  }

  // BGP path vector routing computation
  for (int iteration = 0; iteration < maxIterations; iteration++) {
    bool hasChanges = false;

    // Process each AS in the topology
    for (final asNum in asTopology.keys) {
      if (asNum == sourceAS) continue;

      final neighbors = asTopology[asNum]!;
      for (final neighbor in neighbors.keys) {
        // Skip if neighbor is not in our routing table
        if (!routes.containsKey(neighbor)) continue;

        final neighborRoute = routes[neighbor]!;
        final newPathLength = neighborRoute.asPathLength + 1;

        // Check AS path length limit
        if (newPathLength > _maxASPathLength) continue;

        // Create new AS path
        final newAsPath = List<int>.from(neighborRoute.asPath)
          ..add(neighbor as int);

        // Check for AS path loops
        if (_hasASPathLoop(newAsPath)) continue;

        // Check if we found a better route
        if (!routes.containsKey(asNum) ||
            _isBetterRoute(neighborRoute, routes[asNum]!)) {
          final newRoute = BGPRouteEntry<T>(
            destination: asNum,
            nextHop: neighbor,
            asPathLength: newPathLength,
            asPath: newAsPath,
            origin: BGPOrigin.egp,
            localPreference: neighborRoute.localPreference,
            med: neighborRoute.med,
            lastUpdate: now,
            isDirectlyConnected: false,
            advertisingAS: neighbor as int,
          );

          routes[asNum] = newRoute;

          // Add to alternative routes
          alternativeRoutes[asNum] ??= <BGPRouteEntry<T>>[];
          alternativeRoutes[asNum]!.add(newRoute);

          hasChanges = true;
        }
      }
    }

    // If no changes in this iteration, we've converged
    if (!hasChanges) break;
  }

  // Apply policy-based route selection if enabled
  if (enablePolicyBasedSelection && policies != null) {
    _applyRoutingPolicies(routes, alternativeRoutes, policies);
  }

  // Select best routes based on BGP decision process
  final bestRoutes = _selectBestRoutes(routes, alternativeRoutes);

  return BGPRoutingTable<T>(
    sourceAS: sourceAS,
    routes: Map.unmodifiable(bestRoutes),
    alternativeRoutes: Map.unmodifiable(alternativeRoutes),
    lastUpdate: now,
    totalRoutes: bestRoutes.length,
    totalASes: asTopology.length,
  );
}