05 - Árvore (Tree) e Estruturas Hierárquicas

video explicativo

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

Árvore (Tree) e Estruturas Hierárquicas

1. Definição e Caracterização

A topologia em árvore (tree) é uma estrutura hierárquica onde há uma raiz (root), ramos internos e folhas (leaves). Cada nó (exceto a raiz) tem exatamente um pai; cada nó pode ter múltiplos filhos. Em teoria dos grafos, é um grafo conexo acíclico não-dirigido com n vértices e n-1 arestas.

Topologia:

                    [Root]
                   /      \
              [Pai 1]   [Pai 2]
              /    \      /    \
           [F1]  [F2]  [F3]  [F4]

Características formais:

Arestas: n-1 (mínimo para manter conectividade).
Diâmetro: depende da altura (height) da árvore. Em árvore binária balanceada: 2·log₂(n).
Conectividade de vértices κ = 1 (SPOF em qualquer nó interno).
Conectividade de arestas λ = 1 (cada aresta é ponte).

Em redes, a topologia árvore aparece em:

Hierarquia de switches (3-tier de datacenter, modelo core-distribution-access).
Spanning Tree Protocol (STP), que cria árvore geradora sobre topologia física com loops.
Hierarquia DNS (root → TLD → authoritative).
Hierarquia BGP (route reflectors).
Árvores de multicast (PIM-SM, IGMP snooping).

2. Contexto Histórico

Ano	Marco	Detalhe
1980s	Hierarquia de bridges em LANs	Antes do STP, loops causavam broadcast storms
1990	STP (IEEE 802.1D)	Radia Perlman, árvore geradora dinâmica
1995	3-tier datacenter (Cisco)	Core-Aggregation-Access hierárquico
2000s	Hierarquia DNS estabelecida	Root, TLD, authoritative
2010s	Spine-Leaf ameaça 3-tier	Estrutura hierárquica entra em declínio
2015+	SDN controladores hierárquicos	Hierarquia lógica em planos de controle

3. Propriedades Matemáticas

3.1 Definição Formal

Uma árvore T = (V, E) é um grafo tal que:

T é conexo.
T é acíclico.
Equivalentemente: existe exatamente um caminho entre quaisquer dois vértices.

3.2 Terminologia

Raiz (root): nó de topo (sem pai).
Folha (leaf): nó sem filhos.
Nó interno: tem pelo menos um filho.
Altura: comprimento do maior caminho da raiz a uma folha.
Profundidade: distância da raiz ao nó.
Subárvore: subgrafo que é também árvore.

3.3 Tipos de Árvores

Binária: cada nó tem no máximo 2 filhos.
Balanceada: profundidade mínima para n dado.
n-ária: cada nó tem no máximo n filhos.
Spanning tree: subgrafo que cobre todos os vértices do grafo original.

4. Spanning Tree Protocol (STP)

4.1 Motivação

Em redes com múltiplos caminhos (redundância), loops L2 causam:

Broadcast storms: frames broadcast circulam indefinidamente.
Múltiplas cópias:同一个 frame entregue várias vezes.
MAC table instability: switches veem MACs em portas diferentes.

STP resolve isto criando uma árvore geradora lógica sobre a topologia física. Portas redundantes são bloqueadas, eliminando loops.

4.2 Algoritmo STP (802.1D)

Eleição de Root Bridge: switch com menor Bridge ID (Priority + MAC). Default priority = 32768.
Cálculo de Root Path Cost: cada switch calcula custo para chegar à root.
Eleição de Root Port: em cada switch não-root, porta com menor custo para root.
Eleição de Designated Port: em cada segmento, porta com menor custo para root.
Bloqueio de portas redundantes (alternate port state).

              [Root Bridge]
             /      |      \
            /       |       \
        [SW2]     [SW3]    [SW4]
           \       |       /
            \      |      /
             [Hosts]

Custos de path (802.1D-1998):

Velocidade	Custo
10 Mbps	100
100 Mbps	19
1 Gbps	4
10 Gbps	2

Em 802.1D-2004, custos foram revisados:

Velocidade	Custo
10 Mbps	2.000.000
100 Mbps	200.000
1 Gbps	20.000
10 Gbps	2.000
100 Gbps	200

4.3 Port States

Estado	Comportamento
Disabled	Porta desativada administrativamente
Blocking	Não encaminha frames, só escuta BPDUs
Listening	Encaminha BPDUs, não aprende MACs
Learning	Aprende MACs, não encaminha dados
Forwarding	Encaminha dados normalmente

Tempo de convergência clássico: ~50s (15 + 15 + 20 = listening + learning + max age).

4.4 RSTP (802.1w) - Rapid Spanning Tree

Acelera convergência para < 1s em condições ideais. Estados simplificados:

Discarding (substitui disabled/blocking/listening).
Learning.
Forwarding.

Roles de porta estendidos: Root, Designated, Alternate, Backup.

Mecanismos:

Proposal/Agreement: handshake rápido entre switches.
Sync: garante consistência antes de forwarding.

4.5 MSTP (802.1s) - Multiple Spanning Tree

Permite múltiplas instâncias de STP, cada uma com root bridge diferente. VLANs podem ser mapeadas a instâncias distintas, balanceando carga entre caminhos.

5. Hierarquia em Switches de Rede (3-tier)

5.1 Modelo Cisco Tradicional

                 [Core Switches]          ← Tier 1: L3, alta velocidade
                /              \
        [Distribution]    [Distribution] ← Tier 2: L3, ACLs, services
        /         \        /         \
   [Access]   [Access] [Access]   [Access] ← Tier 3: L2, portas de acesso

5.2 Funções por Tier

Tier	Função	Características
Core	Roteamento central, alta velocidade	100G+, par redundante, sem STP
Distribution	Agregação, ACLs, firewall services	10G+ uplinks, SVIs para VLANs
Access	Portas para hosts, PoE+	1G/2.5G, PoE+ 30W ou PoE++ 90W

5.3 Limitações do 3-tier

Oversubscription alto: tipicamente 4:1 entre access e distribution, 2:1 entre distribution e core.
East-West traffic (servidor a servidor) atravessa múltiplos hops.
SPOF: hierarquia precisa de pares redundantes em cada tier.
STP bloqueia uplinks (50% da capacidade desperdiçada).

Por isto, spine-leaf substituiu 3-tier em datacenters modernos.

6. Outras Aplicações de Árvores em Redes

6.1 Hierarquia DNS

            [Root (.)]
           /    |    \
        [com] [org] [br]
        /  \        |
   [example] [google] [gov]
                       |
                    [ansp]

Root servers (13 instâncias lógicas, ~1700 físicas via anycast).
TLDs: .com, .org, .br, etc.
Authoritative servers para domínios específicos.

6.2 BGP Route Reflectors

Em ASs grandes com muitos iBGP peers, full mesh iBGP é O(n²). Route reflectors (RR) criam hierarquia: clientes peer com RR; RR reflete rotas. Reduz vizinhanças de O(n²) para O(n).

              [RR Cluster 1]
             /      |      \
        [PE1]   [PE2]   [PE3]
              [RR Cluster 2]
             /      |      \
        [PE4]   [PE5]   [PE6]

6.3 Multicast Distribution Trees

PIM-SM (Protocol Independent Multicast - Sparse Mode) constrói árvore de distribuição de multicast:

RP (Rendezvous Point): ponto central inicial.
**Shared tree (*, G)**: todos os receptores via RP.
Shortest Path Tree (S, G): caminho direto da fonte ao receptor.

6.4 Clos Networks e Fat-Tree

Topologias de datacenter modernas são variações de árvores recursivas:

Clos (k=4): 3 stages, switches de 4 portas. Pode escalar para milhares de servidores.
Fat-tree: árvores recursivas onde largura de banda aumenta em direção à raiz (elimina oversubscription).

Spine-leaf é Clos de 2 estágios simplificado.

6.5 Spanning Tree em Storage Networks

Em SAN FC, o conceito de spanning tree é diferente (FSPF é link-state), mas a topologia fabric é hierárquica.

7. Vantagens e Desvantagens

7.1 Vantagens

Estrutura clara: facilidade de documentação e operação.
Agregação eficiente: tráfego converge para raiz, simplificando engenharia.
Custo O(n): n-1 arestas, mais barato que mesh.
Hierarquia administrativa: cada tier pode ser gerido por equipe diferente.
Determinismo: STP garante árvore livre de loops.

7.2 Desvantagens

SPOF: queda de qualquer nó interno desconecta subárvore.
Oversubscription: hierarquias físicas acumulam oversubscription em direção à raiz.
Latência: caminhos longos entre folhas (East-West).
Custo de cabos: apesar de O(n), concentração no core exige switches caros.
Convergência STP: tradicionalmente lenta (~50s), mitigada em RSTP.

8. Caso Prático: 3-tier em DC Tradicional

Cenário: datacenter com 8 racks, 16 servidores/rack = 128 servidores.

                 [Core: 2x Cisco Nexus 9500]
                       (10G/40G uplinks)
                /                            \
       [Agg: 2x N9K-C9300]          [Agg: 2x N9K-C9300]
        /        \                   /         \
   [ToR1] [ToR2] [ToR3] [ToR4]  [ToR5] [ToR6] [ToR7] [ToR8]
     16     16     16     16       16     16     16     16  servidores

Uplinks ToR→Agg: 4x 10G (LACP).
Uplinks Agg→Core: 8x 40G (LACP).
STP: MSTP com 2 instâncias, root em Agg1 (primário) e Agg2 (secundário).
VLANs: até 4094, segmentadas por rack.
Oversubmission: ToR→Agg = 1.28:1 (16x1G downlinks / 4x10G uplinks).

9. Comparação: Tree vs Spine-Leaf

Aspecto	Tree 3-tier	Spine-Leaf
Diâmetro	5-6 (entre servidores)	2
Bissecção	~1:4 (oversubscription)	1:1 (full non-blocking)
STP necessário	Sim (sem ele, loops)	Não (L3 do dia 1)
East-West otimizado	Não	Sim
Escalabilidade	Limitada por switches core	Adiciona spines/leaves
Custos	Switches core muito caros	Switches commodity
Aplicação típica	Campus, DC legado	DC moderno, cloud

10. Tendências Modernas

10.1 Spine-Leaf Substituindo 3-tier

Padrão dominante em DC novo. Vantagens:

Sem STP (roteamento L3 do dia 1).
ECMP para múltiplos caminhos.
Diâmetro 2 entre servidores.
Escalabilidade modular.

10.2 Routed Access

Em campus, "routed access" elimina o tier de distribuição. Cada switch de acesso roda OSPF e é vizinho L3 do core. STP não é necessário. Simplifica operação.

10.3 Árvores em Software-defined Storage

Sistemas como Hadoop HDFS, Ceph usam topologias hierárquicas para rack awareness:

Dados replicados em racks distintos para resiliência.
Topologia em árvore conhecida pelo NameNode/Monitor.

10.4 Árvores em Service Discovery

Sistemas de service discovery (Consul, etcd) frequentemente usam árvores hierárquicas para namespace (ex.: /service/web/eu-west-1/i-12345).

11. Boas Práticas

Em hierarquia física, sempre ter pares redundantes em cada tier.
Usar RSTP/MSTP em vez de 802.1D clássico.
Configurar root bridge primário e secundário explicitamente.
Aplicar bpduguard em portas de acesso (proteção contra switches não autorizados).
Documentar topologia hierárquica em ferramenta dedicada (NetBox).
Em datacenter novo, preferir spine-leaf a 3-tier.

12. Diagnóstico

Sintoma	Causa Provável	Ferramenta
Convergência STP > 1 min	STP clássico 802.1D	Migrar para RSTP/MSTP
Portas em blocking permanente	Mudanças de topologia frequentes	`show spanning-tree`
Latência alta entre racks	3-tier oversubscription alto	Adicionar uplinks, migrar para spine-leaf
Root bridge errado	Priority default (32768), MAC baixo em switch de acesso	Configurar priority explicitamente

13. Conclusão

A topologia árvore é a base de hierarquias em redes: da Spanning Tree em L2 ao modelo 3-tier de campus e datacenter, da hierarquia DNS à organização de BGP route reflectors. Embora 3-tier esteja em declínio em datacenters (substituído por spine-leaf), o conceito de árvore permanece essencial em protocolos de controle (STP, IGMP, PIM) e em estruturas lógicas (DNS, BGP, multicast trees). Compreender árvores, suas propriedades matemáticas e protocolos correlatos (STP, RSTP, MSTP) é fundamental para qualquer engenheiro de redes, especialmente em ambientes de campus e em datacenters que ainda mantêm infraestrutura hierárquica legada.