Dinic's Maxflow¶

Before s.a.u deletes a NAT Gateway, it needs a mathematical proof that your network won't partition. Dinic's algorithm provides that proof.

Network Flow Modeling¶

Cloud infrastructure maps to a directed graph: nodes \(v \in V\) are hardware (instances, gateways), edges \((u,v) \in E\) are routing flows. Each edge gets a capacity \(c(u,v) \ge 0\) determined by the hardware's network bandwidth.

Removing a target node \(t\) simulates a topology fracture. s.a.u assigns a mathematical source node \(s\) (e.g., an Application Load Balancer egress point) and measures whether maximum flow through the subgraph drops below a critical failure threshold.

Dinic's Algorithm Implementation¶

Dinic's runs natively in pkg/engine/solver/flow.go. It resolves max flow in \(O(V^2 E)\): significantly faster than Edmonds-Karp's \(O(VE^2)\) in dense cloud graphs.

The algorithm builds a Level Graph via BFS (isolating paths where distance strictly increases), then runs DFS blocking flow pushes along those paths.

type Edge struct {
    to  int
    cap int
    rev int // index of reverse edge in adjacency list
}

func (g *FlowGraph) BFS(s, t int) bool {
    // Computes exact shortest paths from s to all nodes.
    // Populates g.level map. Returns true if t is reachable.
    for i := range g.level {
        g.level[i] = -1
    }
    g.level[s] = 0

    // ... BFS queue iteration
    return g.level[t] != -1
}

func (g *FlowGraph) DFS(v, t, minFlow int) int {
    if v == t || minFlow == 0 {
        return minFlow
    }
    for ; g.ptr[v] < len(g.adj[v]); g.ptr[v]++ {
        e := &g.adj[v][g.ptr[v]]
        // Strict Level Graph adherence
        if g.level[e.to] != g.level[v]+1 || e.cap == 0 {
            continue
        }
        pushed := g.DFS(e.to, t, min(minFlow, e.cap))
        if pushed > 0 {
            e.cap -= pushed
            g.adj[e.to][e.rev].cap += pushed
            return pushed
        }
    }
    return 0
}

func (g *FlowGraph) DinicMaxFlow(s, t int) int {
    flow := 0
    for g.BFS(s, t) {
        for i := range g.ptr {
            g.ptr[i] = 0
        }
        for {
            pushed := g.DFS(s, t, math.MaxInt32)
            if pushed == 0 {
                break
            }
            flow += pushed
        }
    }
    return flow
}

Disruption Validation¶

When s.a.u simulates terminating target \(t\), the daemon builds a subgraph omitting \(t\) and recalculates DinicMaxFlow(). If \(Flow_{new} < Flow_{original}\) and the variance exceeds the load balancing tolerance threshold, s.a.u raises a TopologicalFracture exception and aborts the quarantine saga to preserve application health.