03 - Métricas Topológicas (Diâmetro, Grau, Bissecção)

video explicativo

Video explicativoEspaco reservado para o video desta anotação — adicione video: https://youtu.be/... no frontmatter da nota.

Métricas Topológicas (Diâmetro, Grau, Bissecção)

1. Definição e Importância

Métricas topológicas são medidas quantitativas que caracterizam propriedades estruturais de uma rede, permitindo comparações objetivas entre topologias distintas. Sem métricas, escolher entre star, mesh, spine-leaf ou fat-tree seria mera intuição. Com métricas, é possível demonstrar que spine-leaf tem menor diâmetro que 3-tier, que full-mesh tem máxima bissecção mas custo O(n²), e que topologias hierárquicas favorecem agregação mas penalizam tráfego East-West.

Este documento cobre as principais métricas usadas em projeto e análise de topologias de rede, suas fórmulas, interpretação física e aplicações práticas.

2. Métricas Básicas

2.1 Número de Vértices (n) e Arestas (m)

n: número total de nós (roteadores, switches, hosts).
m: número total de enlaces.

Relações fundamentais:

Grafo conexo: m ≥ n − 1 (árvore geradora).
Grafo completo Kₙ: m = n(n-1)/2.
Grafo bipartido completo K_{p,q}: m = p×q.

2.2 Grau e Distribuição de Grau

Grau de um vértice k_v: número de arestas incidentes.

Métrica	Definição
Grau mínimo δ(G)	min_v k_v
Grau máximo Δ(G)	max_v k_v
Grau médio ⟨k⟩	2m/n

Distribuição de grau P(k): probabilidade de um vértice aleatório ter grau k.

Em redes reais:

Distribuição aleatória (Erdős-Rényi): P(k) ~ Poisson(λ).
Scale-free (Barabási-Albert): P(k) ~ k^(-γ), γ ∈ (2,3). Internet e web são scale-free.

Em redes de datacenter, geralmente busca-se grau uniforme (todos os switches com mesmo número de uplinks/downlinks) para balanceamento.

2.3 Densidade

formula$$\rho(G) = \frac{2m}{n(n-1)}$$

Fração de arestas possíveis que realmente existem. ρ = 1 em full-mesh; ρ ≈ 0 em redes esparsas como Internet.

3. Métricas de Distância

3.1 Distância Geodésica

Para vértices u, v: d(u,v) = comprimento do caminho mínimo entre eles.

3.2 Excentricidade

formula$$\epsilon(v) = \max_{u \in V} d(v, u)$$

Máxima distância de v a qualquer outro vértice. Em roteamento, representa o pior caso de hop count.

3.3 Raio e Diâmetro

Raio: rad(G) = min_v ε(v).
Diâmetro: diam(G) = max_v ε(v) = max_{u,v} d(u,v).

Interpretação em redes: diâmetro = pior caso de hops entre dois nós. Menor é melhor para latência.

Diâmetros típicos:

Topologia	Diâmetro
Estrela com n nós	2
Anel com n nós	⌊n/2⌋
Linha (path) com n nós	n − 1
Full mesh Kₙ	1
Árvore binária balanceada	2 log₂ n
Hypercube Q_d (n = 2^d)	d = log₂ n
Spine-Leaf (n_spines × n_leaves)	2
3-tier DC	5-6
Fat-tree (k-ary)	4-6

3.4 Caminho Médio

formula$$\bar{d} = \frac{1}{n(n-1)} \sum_{u \neq v} d(u,v)$$

Média das distâncias entre todos os pares. Pequeno caminho médio é característica de "small-world networks".

4. Métricas de Conectividade e Resiliência

Conectividade de vértices κ(G): mínimo número de nós que precisam ser removidos para desconectar G. κ ≥ 2 em redes resilientes; κ = 1 indica SPOF.
Conectividade de arestas λ(G): mínimo número de arestas que precisam ser removidas. Desigualdade de Whitney: κ(G) ≤ λ(G) ≤ δ(G).
k-conectividade: rede é k-conexa se κ(G) ≥ k. Em produção: k=2 (carrier-grade tradicional), k=4 (DC modernos, 4 caminhos ECMP), k=16+ (SDN com multipath avançado).
Bissecção (Bisection Bandwidth): número de arestas que precisam ser cortadas para dividir G em duas metades iguais. Interpretação: máxima largura de banda para tráfego entre metades. Spine-leaf full: bissecção máxima (n_leaves × n_spines/2); 3-tier: bissecção ~1:4; Fat-tree k-ary: bissecção = k³/8 (full non-blocking). Em tráfego East-West pesado, bissecção é a métrica decisiva.

5. Métricas de Centralidade

Centralidade de grau C_D(v) = deg(v)/(n-1): conta vizinhos diretos. Útil para identificar hubs.
Centralidade de proximidade (closeness) C_C(v) = (n-1)/Σ d(v,u): nó central está próximo de todos. Bom para servidores amplamente acessados.
Centralidade de intermediação (betweenness) C_B(v) = Σ σ_st(v)/σ_st: nó com alta betweenness é "ponte" entre comunidades; removê-lo fragmenta a rede. Switches core tipicamente têm betweenness alto → críticos para redundância.
Centralidade de autovetor: x_v = (1/λ)Σ x_u sobre vizinhos. Nó é central se conectado a nós centrais. Base do PageRank, usado em análise de ASs.

6. Métricas de Clusterização e Comunidades

6.1 Coeficiente de Clusterização Local

formula$$C(v) = \frac{2 \cdot |\{(u,w) : u,w \in N(v), (u,w) \in E\}|}{\deg(v)(\deg(v)-1)}$$

Fração de pares de vizinhos de v que também estão conectados entre si. Redes sociais têm C alto; redes técnicas têm C baixo (topologia de rede ≠ topologia social).

6.2 Coeficiente de Clusterização Global

Média dos C(v) ou versão de Watts-Strogatz. Caracteriza "small-worldness".

6.3 Modularidade (Newman)

formula$$Q = \frac{1}{2m} \sum_{ij} \left[ A_{ij} - \frac{k_i k_j}{2m} \right] \delta(c_i, c_j)$$

Mede qualidade de uma partição em comunidades. Q > 0,3 indica estrutura comunitária significativa.

Em redes de AS, modularidade revela clústeres regionais (ASs brasileiros vs europeus, etc.).

7. Métricas Espectrais

Conectividade algébrica (λ₂): segundo menor autovalor do laplaciano L. Alto λ₂ ⇒ boa resiliência.
Razão espectral λ_n/λ₂: mede "expansão" da rede. Razão baixa → boas expander graphs (topologias de datacenter eficientes).
Energia de grafo E(G) = Σ|λ_i^A|: soma dos valores absolutos dos autovalores de A. Menor energia correlaciona com maior entropia estrutural.

8. Comparação de Topologias Clássicas

Topologia	n nós	m arestas	Diâmetro	Grau médio	Bissecção	κ(G)
Estrela	n	n-1	2	2(n-1)/n	1	1
Anel	n	n	⌊n/2⌋	2	2	2
Linha	n	n-1	n-1	2(n-1)/n	1	1
Full Mesh	n	n(n-1)/2	1	n-1	n²/4	n-1
Árvore binária	n	n-1	2 log₂ n	~2	1	1
Hypercube Q_d	2^d	d·2^(d-1)	d	d	2^(d-1)	d
Spine-Leaf (s,l)	s+l	s·l	2	var	s·l/2	min(s,l)

9. Aplicações em Projeto de Redes

Dimensionamento de DC (10k servidores): 3-tier (diâmetro 5-6, bissecção 1:4, ~25k cabos); Spine-Leaf (diâmetro 2, bissecção 1:1, ~50k cabos); Fat-tree k=20 (diâmetro 6, full non-blocking, ~80k cabos); DCell (recursivo, melhor escala para >50k). Trade-off: custo de cabos vs performance East-West.
Planejamento de WAN (100 PoPs): estrela (diâmetro 2, κ=1, SPOF); ring (diâmetro 50, κ=2); mesh parcial 3-regular (diâmetro ~6-8, κ=3); expander (diâmetro ~4-5, κ=20+).
Análise de ASs: AT&T (AS7018), Lumen (AS3356) têm máxima betweenness → críticos para roteamento global. Ataques de BGP hijack exploram alta betweenness para interceptação.

10. Ferramentas e Índices Compostos

import networkx as nx
G = nx.random_regular_graph(3, 100)  # 3-regular random graph
print("Diâmetro:", nx.diameter(G))
print("Caminho médio:", nx.average_shortest_path_length(G))
print("Clusterização:", nx.average_clustering(G))
print("Conectividade:", nx.edge_connectivity(G))

Ferramenta	Uso
NetworkX	Análise geral Python
igraph	Performance, milhares de nós
GraphTool	Performance C++
SNAP	Redes massivas
Gephi	Visualização interativa

Em redes complexas, métricas individuais não bastam. Índices compostos: small-world coefficient σ = (C/C_rand) / (L/L_rand) — σ > 1 indica small-world; assortatividade r — correlação entre graus de vizinhos (Internet é levemente dissortativa, r ≈ -0,2).

11. Boas Práticas e Conclusão

Sempre calcule múltiplas métricas (nenhuma é suficiente isoladamente); compare com modelos randomizados (Erdős-Rényi, configuration model); visualize distribuições em escala log-log; para redes dinâmicas, calcule métricas em snapshots temporais; valide com dados reais (topologia BGP, LSDB OSPF, NetFlow).

12. Conclusão

Métricas topológicas transformam a discussão sobre topologias de rede de qualitativa para quantitativa. Decisões como "qual topologia para meu datacenter de 10k servidores?" deixam de ser baseadas em preferências pessoais e passam a ser fundamentadas em diâmetro, bissecção, κ-conectividade e custo de cabos. Para qualquer arquiteto de redes que pretenda justificar tecnicamente suas escolhas, dominar estas métricas é tão essencial quanto dominar protocolos. A próxima evolução — redes auto-otimizantes com SDN/AIOps — fará uso intensivo destas métricas em tempo real, tornando seu domínio ainda mais crítico.