Component Complexity Analysis: Aegis
This document details the algorithmic and memory complexity of the core components in the Aegis framework.
1. Complexity Matrix
| Component | Time Complexity (Average) | Time Complexity (Worst Case) | Space Complexity | Memory Access Patterns |
|---|---|---|---|---|
| Ingestion Reader | $O(1)$ | $O(1)$ | $O(1)$ | Sequential stream read, contiguous writes. |
| SPSC Queue | $O(1)$ | $O(1)$ | $O(N)$ (fixed size) | Ring buffer array access, highly cache-localized. |
| Packet Parser | $O(1)$ (header size) | $O(1)$ | $O(1)$ | Zero-copy offsets, direct casts, L1 cache. |
| Flow Lookup | $O(1)$ | $O(N)$ (table full) | $O(M)$ (fixed table) | Contiguous array probe, cache prefetch-friendly. |
| CIDR IP Matcher | $O(D)$ where $D \le 32$ | $O(32)$ | $O(R)$ (rule count) | Binary trie bit-inspection or mask arrays. |
| Domain Suffix Matcher | $O(K)$ where $K$ = SNI len | $O(K)$ | $O(S)$ (total characters) | Suffix Trie traversal, character comparisons. |
| Rule Hot-Reload | $O(1)$ | $O(1)$ (pointer swap) | $O(R_{new})$ | Atomic pointer exchange, zero worker contention. |
2. Details & Explanations
2.1 SPSC Ring Buffer Queue
- Time Complexity: Push and Pop execute in constant time, $O(1)$.
- Space Complexity: Uses a fixed-size pre-allocated array of capacity $N$. Since $N$ must be a power of 2, modulo operations are replaced by a fast bitwise AND:
index & (N - 1). - Memory Access: Head and tail pointers are separated onto different cache lines, ensuring that cache validation signals are only sent when the queue transitions from empty-to-full or vice-versa.
2.2 Flat Flow Table (Open Addressing)
- Time Complexity: Average lookup is $O(1)$. Under high collision rates or when table load factor approaches 100%, worst-case time degrades to $O(N)$. We keep load factor under 70% to ensure average probes remain $\le 2$.
- Space Complexity: Pre-allocates memory for the maximum number of tracked connections. Memory allocation size is static.
2.3 CIDR Prefix Matcher
- Time Complexity: Matches IPs using a bitwise mask matching loop or Trie search. For IPv4, the maximum number of steps to resolve a lookup is limited by the number of bits (32), giving a worst-case time complexity of $O(32)$, which is equivalent to $O(1)$ constant time.
- Space Complexity: $O(R)$ where $R$ is the number of subnet rules.
2.4 Domain Suffix Matcher
- Time Complexity: Evaluates an SNI string of length $K$ by scanning its suffix characters. Worst-case is $O(K)$ where $K$ is typically $\le 253$ bytes.
- Space Complexity: Trie structures store characters efficiently by sharing prefixes/suffixes.