04 - Conectividade e Resiliência (Teorema de Menger)
video: https://youtu.be/... no frontmatter da nota.Conectividade e Resiliência (Teorema de Menger)
1. Definição e Importância
Conectividade mede quão robusta é uma topologia de rede à remoção de nós ou enlaces. Resiliência é a capacidade da rede de continuar operando (possivelmente com desempenho degradado) após falhas parciais. Estas duas propriedades são fundamentais em projeto de redes carrier-grade, datacenters de alta disponibilidade e infraestruturas críticas (financeiras, saúde, energia).
O Teorema de Menger (1927) é o pilar teórico que conecta estas duas noções, estabelecendo a equivalência entre:
- Conectividade estrutural (quantos elementos podem falhar antes da rede desconectar).
- Existência de caminhos disjuntos (múltiplas rotas independentes entre origem e destino).
Esta equivalência é a base matemática de todos os protocolos de redundância de rede (MPLS FRR, ECMP, LACP, MPIO, TRILL).
2. Conceitos Fundamentais
2.1 Conectividade de Vértices κ(G)
Mínimo número de vértices que precisam ser removidos (com suas arestas incidentes) para desconectar o grafo ou reduzi-lo a um único nó.
Notação: κ(G). Em grafo desconexo, κ = 0. Em grafo completo Kₙ, κ = n-1.
2.2 Conectividade de Arestas λ(G)
Mínimo número de arestas que precisam ser removidas para desconectar o grafo.
Desigualdade de Whitney (1932):
Onde δ(G) é o grau mínimo.
Interpretação prática:
- Remover nós é mais impactante que remover arestas (κ ≤ λ).
- Não se pode cortar mais arestas do que o grau do nó menos conectado (λ ≤ δ).
2.3 k-Conectividade
Um grafo é k-conexo (k-vertex-connected) se κ(G) ≥ k. Equivalentemente:
- Permanece conexo após a remoção de qualquer k-1 nós.
- Existem k caminhos internamente disjuntos entre quaisquer dois vértices.
Em produção:
| Topologia | κ | Implicações |
|---|---|---|
| Estrela | 1 | Ponto único no hub |
| Anel | 2 | Suporta 1 falha |
| Full mesh Kₙ | n-1 | Máxima resiliência |
| Spine-Leaf (s spines, s≤l leaves) | s | Suporta s-1 falhas de spine |
| Hypercube Q_d | d | Suporta d-1 falhas |
3. Teorema de Menger
3.1 Enunciado (versão arestas)
Sejam u, v dois vértices não adjacentes de um grafo G. O número mínimo de arestas que precisam ser removidas para desconectar u de v é igual ao número máximo de caminhos aresta-disjuntos entre u e v.
3.2 Enunciado (versão vértices)
O número mínimo de vértices (diferentes de u e v) que precisam ser removidos para desconectar u de v é igual ao número máximo de caminhos internamente disjuntos entre u e v.
3.3 Importância Prática
Sempre que possível "provar" que existem k caminhos disjuntos entre dois nós, garante-se que k-1 falhas não os desconectam. Esta é a base teórica:
- MPLS Fast Reroute: LSPs backup preestabelecidos sobre caminhos disjuntos.
- ECMP: múltiplos caminhos equivalentes em IGP.
- LACP: agregação de múltiplos links físicos.
- MPIO (SAN): múltiplos caminhos para storage.
- Multipath TCP (MPTCP): conexões TCP usam múltiplos caminhos.
3.4 Demonstração Intuitiva
Imagine uma rede de água entre duas cidades. Se k canos disjuntos as conectam, é preciso cortar pelo menos k canos para impedir o fluxo. Reciprocamente, se a cidade só consegue enviar água por 1 cano, cortar esse cano interrompe tudo.
Em redes de pacotes, a mesma lógica se aplica: ter k caminhos disjuntos significa que k-1 falhas podem ser absorvidas sem impacto.
4. Caminhos Disjuntos
4.1 Tipos de Disjunção
- Aresta-disjuntos: não compartilham arestas (mas podem compartilhar nós).
- Vértice-disjuntos (internamente): não compartilham arestas nem nós intermediários.
- Totalmente disjuntos: nem sequer compartilham nós terminais (raro).
A disjunção de vértices é mais forte: protege também contra falhas de nós intermediários (switches).
4.2 Cálculo
Para encontrar k caminhos disjuntos entre s e t:
- Aplique max-flow de s a t (capacidade 1 por aresta/nó).
- O valor do fluxo = número máximo de caminhos disjuntos.
- Extraia os caminhos via BFS no grafo residual.
Algoritmo: Edmonds-Karp em O(VE²). Para k-pequeno (k ≤ 8), prático em redes reais.
5. Aplicações em Redes Reais
5.1 MPLS Fast Reroute (FRR)
Estabelece LSP primário e um (ou mais) LSPs backup disjuntos. Quando falha, switching para backup ocorre em < 50 ms (similar ao SONET APS).
┌─────── Link primário ───────┐
PE1 ──────────────────────────── PE2
└────── Link backup (FRR) ────┘
(caminho disjunto)
O backup pode ser:
- Next-Next-Hop (NNHOP): protegido contra falha de nó intermediário.
- Next-Hop (NHP): protegido apenas contra falha de link.
NNHOP exige caminhos internamente disjuntos ⇒ base do Teorema de Menger.
5.2 ECMP (Equal-Cost Multi-Path)
Em OSPF/IS-IS, múltiplas rotas com mesmo custo são anunciadas. O roteador balanceia entre elas. Menger garante que se há k caminhos ECMP, há k-1 proteções contra falhas.
5.3 LACP (802.3ad) / LAG
Agregação de múltiplos links físicos em um logical. Tolerância a falhas de cabo individual.
5.4 MPIO em SAN
Em Fibre Channel, dual-fabric com 2 HBAs por servidor fornece 2 caminhos disjuntos a cada LUN. Falha de 1 fabric = 0 downtime.
5.5 Multipath TCP (RFC 6824)
Conexão TCP usa múltiplos subflows simultâneos, possivelmente sobre interfaces distintas (Wi-Fi + celular). Resiliência a falhas de link sem reconexão.
6. Resiliência em Prática
6.1 Definição Operacional
Resiliência de uma rede = probabilidade de manter conectividade entre pares de nós dado um padrão de falhas (probabilístico ou adversarial).
6.2 Modelo de Falhas
| Modelo | Característica |
|---|---|
| Falha aleatória | Nós falham com prob p uniforme |
| Falha adversarial | Atacante escolhe nós mais críticos |
| Falha correlacionada | Falhas em blocos (corte de cabo,queda de datacenter) |
Redes scale-free são resilientes a falhas aleatórias (κ efetivo alto devido a hubs), porém frágeis a ataques direcionados (remoção de poucos hubs as desconecta).
6.3 Medidas de Resiliência
- Tolerância a falhas: fração de nós que podem falhar antes de desconectar.
- Eficiência global: $\frac{1}{n(n-1)} \sum 1/d(i,j)$ — decai com falhas.
- Tamanho do componente gigante: deve permanecer ~n após k falhas.
- Tempo de convergência: tempo para IGP/BGP restabelecer rotas.
7. k-Conectividade em Projetos
7.1 Topologias Clássicas e κ
| Topologia | κ | λ | δ |
|---|---|---|---|
| Estrela | 1 | 1 | 1 |
| Anel | 2 | 2 | 2 |
| Árvore | 1 | 1 | 1 |
| Full mesh Kₙ | n-1 | n-1 | n-1 |
| Torus 2D (n×n) | 4 | 4 | 4 |
| Hypercube Q_d | d | d | d |
| Spine-Leaf (s,l) | min(s,l) | min(s,l) | s ou l |
7.2 Meta em Projetos Reais
Carrier-grade: κ ≥ 2 (sem SPOF). Datacenter moderno: κ ≥ 4 (até 4 falhas simultâneas). Hyperscale DC: κ ≥ 8+ (camadas Clos multi-stage). Financeiro crítico: κ ≥ 4 + duplicação física (datacenters espelhados).
8. Algoritmos e Cálculo Prático
Para verificar se G é k-conexo: para cada par (s,t), calcule max-flow (capacidade 1 por vértice); se min sobre todos os pares ≥ k, então κ(G) ≥ k. Complexidade O(n² × maxflow).
import networkx as nx
G = nx.karate_club_graph()
print("κ =", nx.node_connectivity(G)) # 5
print("λ =", nx.edge_connectivity(G)) # 5
paths = nx.node_disjoint_paths(G, 0, 33) # Caminhos disjuntos
Articulation points (pontos de articulação): vértice cuja remoção desconecta G (κ < 2). Bridges (pontes): aresta cuja remoção desconecta G (λ < 2). Algoritmo de Tarjan encontra ambos em O(V+E). Em redes, identificar estes pontos é o primeiro passo de hardening.
9. Casos de Estudo
- Resiliência da Internet: AS-graph é scale-free (P(k) ~ k^(-2,1)). Tolerância elevada a falhas aleatórias (hubs protegem) mas vulnerável a ataques direcionados (remoção dos 1% mais conectados desconecta ~50%). BGP hijack em Tier 1 é catastrófico (caso Pakistan YouTube 2008).
- Spine-Leaf DC (6 spines + 48 leaves): κ=6, λ=6, 6 caminhos disjuntos via spines distintos entre qualquer par de servidores; suporta 5 falhas de spine.
- MPLS Carrier Network (100 PoPs 4-regular): κ=4, MPLS FRR com NNHOP garante < 50 ms para qualquer falha.
10. Beyond Menger: Resiliência Multicommodity
Menger trata pares únicos. Em redes reais, queremos resiliência simultânea para múltiplos pares (multicommodity flow), NP-hard em geral. Aproximações: disjoint path pair (2 caminhos disjuntos por par, nem sempre possível globalmente); Shared Risk Link Groups (SRLG) (modela falhas correlacionadas, fibra compartilhada em duto); Survivable Network Design (SND) (otimização de topologia sob restrições de k-conectividade).
11. Boas Práticas e Diagnóstico
Eliminar todo SPOF (cada componente deve ter redundância ≥ 2); aplicar dual-homing em switches de acesso; distribuir uplinks em switches distintos (path diversity); documentar SRLGs (cada link deve ter tag identificando duto físico compartilhado); testar failover periodicamente (chaos engineering); planejar capacidade com margem (falha de 1 link não deve saturar o outro); usar IGP com BFD para detecção sub-segundo.
| Sintoma | Causa | Ferramenta |
|---|---|---|
| Rede cai após 1 falha | κ = 1 (SPOF) | NetworkX, mapeamento físico |
| Latência dobra após falha | Sem ECMP, failover desbalanceado | show route, traceroute |
| Convergência > 1s | BFD ausente | IGP logs, BFD status |
| Re-preferência BGP após reconexão | Route flap | BGP route refresh logs |
12. Conclusão
Conectividade e resiliência são as propriedades mais críticas em topologias de produção. O Teorema de Menger fornece o fundamento matemático que permite transformar o problema qualitativo "minha rede é resiliente?" em questão quantitativa: "quantos caminhos disjuntos existem entre s e t?". Para o engenheiro de redes, dominar κ-conectividade, caminhos disjuntos e SRLGs não é opcional — é o que separa projetos que sobrevivem a falhas reais daqueles que colapsam à primeira indisponibilidade. Em era de cloud, SDN e 5G, com falhas cada vez mais frequentes e correlacionadas, este domínio é cada vez mais crítico.