Dois links entre dois switches são melhores do que um: se um cabo falhar, o outro continua funcionando. Só que esses dois links também formam um loop, e na camada 2 um loop não é problema de desempenho: é rede fora do ar. O () existe para que você possa montar a rede com links redundantes e, mesmo assim, ela se comporte como se não houvesse redundância nenhuma. Para isso, o protocolo desliga de propósito todos os links de que a rede não precisa naquele momento. Aquela porta bloqueada que deixa muita gente intrigada quando liga um switch novo não é defeito. É o protocolo fazendo o trabalho dele.

Por que um loop é fatal na camada 2

Um pacote IP carrega um contador de time-to-live (), que cada roteador diminui em um; por isso, um pacote preso num loop de roteamento morre depois de um número limitado de hops (cada hop é uma passagem por um roteador). O frame (quadro) não tem nada parecido: "Ethernet frames do not have a time to live (TTL) attribute, like IP packets" (Cisco Networking Academy, Scaling Networks). Um broadcast que entra num loop sai copiado por todas as portas, volta e é copiado de novo, até virar um broadcast storm (tempestade de broadcast), ou seja, "so many broadcast frames caught in a Layer 2 loop that all available bandwidth is consumed". Os próprios switches também sofrem: "Instability in the content of the table results from copies of the same frame being received on different ports" (mesma fonte). Na prática, o switch fica reaprendendo o tempo todo em que porta está cada endereço e acaba mandando frames unicast pelo caminho errado.

O artigo de 1985 que apresentou o algoritmo resume o problema em poucas palavras: "congestion caused by infinitely circulating packets" (Perlman, 1985). O guia de troubleshooting da Cisco aponta a causa com a mesma clareza, e é por causa dela que a porta bloqueada importa tanto: um bridging loop "still comes from a port that can block, but instead forwards traffic" (Cisco, troubleshooting de STP), isto é, de uma porta que poderia estar bloqueando e, em vez disso, está encaminhando tráfego.

O algoritmo em quatro decisões

Todos os switches que rodam spanning tree participam do mesmo cálculo, e o resultado é uma árvore: um caminho, e só um, entre quaisquer dois switches.

  1. Eleger o root bridge (o switch raiz). "The bridge with the lowest bridge ID is elected as the root bridge" (Juniper, visão geral do spanning tree). O bridge ID é uma prioridade de dois bytes seguida do endereço MAC (media access control) do switch. No Catalyst 9300 da Cisco, a prioridade é "a 4-bit priority value and a 12-bit extended system ID value equal to the ID", configurável de 0 a 61440 "in increments of 4096; the default is 32768"; quando as prioridades empatam, ganha o menor endereço MAC (Cisco, configuração de STP). Se tudo ficar nos valores padrão, o root bridge vai ser simplesmente o switch com o menor endereço MAC, escolhido pelo acaso, e não por quem projetou a rede. Definir a prioridade de propósito é o primeiro passo de qualquer projeto.
  2. Cada um dos outros switches escolhe uma root port (porta raiz): a única porta que "provides the best path (lowest cost)" até o root bridge (Cisco, como acima).
  3. Cada segmento escolhe uma designated port (porta designada): "A forwarding port elected for every switched segment" (Cisco, como acima), ou seja, a porta do segmento que fica mais perto do root bridge.
  4. Todo o resto fica bloqueado. "All paths that are not needed to reach the root switch from anywhere in the switched network are placed in the spanning-tree blocking mode" (Cisco, como acima).

Path cost: como se calcula a distância até o root bridge

"Melhor caminho" quer dizer a menor soma dos custos das portas (o path cost) até o root bridge, e esses custos dependem da velocidade do link. Há duas escalas em uso, a short e a long. Os valores originais do 802.1D eram números inteiros pequenos; os valores de 32 bits do 802.1t-2001, que vieram depois, dão conta de links muito mais rápidos (Extreme Networks, path costs).

Velocidade do linkCusto short (802.1D-1998)Custo long (802.1t)
10 Mb/s1002.000.000
100 Mb/s19200.000
1 Gb/s420.000
10 Gb/s22.000

Os valores short são os que aparecem no livro da Cisco Networking Academy e na documentação da Juniper ("a 100-Mbps link has a default path cost of 19, a 1000-Mbps link has a default path cost of 4", Juniper; uma tabela da Extreme traz 99 em vez de 100 para 10 Mb/s); os valores long vêm da tabela de valores padrão do guia do Catalyst 9300 da Cisco. A escala que cada switch usa por padrão depende da plataforma e da versão de software, então a regra é simples: numa rede mista, configure todos os switches com o mesmo método, senão dois switches vão discordar sobre qual caminho é o mais barato.

Bridge protocol data units, timers e os 30 a 50 segundos do STP clássico

Os switches trocam essas informações em BPDUs (bridge protocol data units). No STP clássico, o root bridge envia as mensagens de configuração e os outros switches as repassam adiante. O processo usa três timers (temporizadores), com estes valores padrão: hello time de 2 segundos, forward delay de 15 segundos e max age de 20 segundos (Cisco, configuração de STP). Uma porta não vai direto de blocking (bloqueada) para forwarding (encaminhando tráfego): antes, ela passa pelos estados de listening e learning, e "the forward delay is the time spent in the listen and learn state" (Cisco, timers do STP).

Era essa cautela que deixava o spanning tree clássico lento. Quando cai o link do próprio switch em direção ao root bridge, "the recovery takes up to 30 seconds", o equivalente a dois forward delays (Cisco, UplinkFast). Quando a falha acontece em outro ponto da rede e o switch só percebe quando as informações antigas expiram, a espera é "the max_age value (20 seconds) plus twice the fw_delay value (2x15 seconds)", ou seja, "50 seconds with the default parameters" (Cisco, BackboneFast). Meio minuto de rede parada por causa de um único cabo com defeito é uma queda longa demais para qualquer coisa que passe por uma rede hoje.

RSTP: a mesma árvore, montada por handshake

O Rapid Spanning Tree Protocol (), padronizado como 802.1w, mantém a árvore e acaba com a espera. Ele foi "Incorporated into 802.1D-2004" (IEEE 802.1w), e a documentação da Arista diz qual foi a consequência: "Standard 802.1D-2004 incorporates RSTP and obsoletes STP" (Arista, spanning tree). A explicação mais clara do que mudou é a da Cisco (Cisco, como funciona o RSTP):

  • Papéis das portas. "The blocking port role is split into the backup and alternate port roles." Uma alternate port é um segundo caminho até o root bridge, já pronto para assumir, e recebe "more useful BPDUs from another bridge"; uma backup port é um link redundante para o mesmo segmento e recebe essas BPDUs "from the same bridge it is on".
  • Estados. "The 802.1D disabled, blocking, and listening states are merged into a unique 802.1w discarding state." Sobram três: discarding, learning e forwarding.
  • Handshake no lugar dos timers. Uma designated port que quer começar a encaminhar tráfego "sets the proposal bit on the BPDUs it sends out", ou seja, faz uma proposta (proposal) ao vizinho; o vizinho garante que as portas dele não podem formar um loop e responde com um agreement (a concordância), e "once p0 receives that agreement, it can immediately transition to the forwarding state." A Juniper resume o mecanismo como "a handshake mechanism based on point-to-point links instead of the timer-based process used by STP" (Juniper).
  • Edge ports (portas de borda). Uma porta ligada a um host vai direto para forwarding e, no instante em que recebe uma , "immediately loses edge port status", porque BPDU chegando quer dizer que há um switch do outro lado.
  • Hellos como keepalives. Agora todos os switches enviam hellos, e "if hellos are not received three consecutive times, protocol information can be immediately aged out."

Mas convém conhecer o limite: o RSTP "can only achieve rapid transition to the forwarding state on edge ports and on point-to-point links", e o tipo de link é deduzido do duplex: "A port that operates in full-duplex is assumed to be point-to-point, while a half-duplex port is considered as a shared port by default." Onde o mecanismo se aplica, a recuperação leva "sometimes in the order of a few hundred milliseconds" (Cisco, como funciona o RSTP).

MSTP: muitas VLANs, poucas árvores

Com VLANs (LANs virtuais), uma única árvore para a rede inteira desperdiça links: o uplink bloqueado não leva tráfego de nenhuma VLAN. O Multiple Spanning Tree Protocol (MSTP), o IEEE 802.1s, "maps multiple VLANs into a spanning tree instance, with each instance having a spanning tree topology independent of other spanning tree instances" (Juniper, MSTP). Assim, um grupo de VLANs pode bloquear o uplink da esquerda, e outro grupo, o da direita. Essa emenda, de 2002, foi incorporada à edição de 2003 do IEEE 802.1Q (IEEE SA, 802.1s).

O MSTP trabalha com regiões, e o que define uma região é a concordância entre os switches: "All switches in an MST region must have the same name, revision, and VLAN-to-instance map" (Arista). A Cisco informa os tamanhos (um nome de 32 bytes, uma revisão de dois bytes e uma tabela de 4096 posições) e o que acontece se houver qualquer diferença: "If for any reason two switches differ on one or more configuration attribute, the switches are part of different regions" (Cisco, como funciona o MSTP). Vista de fora, "the entire region appears as one virtual bridge"; por dentro, a IST (internal spanning tree) é "an RSTP instance that extends the CST inside the MST region", e a CIST (common and internal spanning tree) liga as regiões entre si e aos switches que rodam apenas RSTP ou STP (Cisco, como acima; Juniper, MSTP). Como basta alterar o mapeamento de uma única VLAN para dividir uma região, a configuração do MSTP é planejada uma vez e aplicada de forma idêntica em todos os switches.

As variantes por VLAN da Cisco e os recursos de proteção

Por padrão, a Cisco roda uma árvore por VLAN: o PVST+ (per-VLAN spanning tree plus) é "based on the standard and Cisco proprietary extensions", e o Rapid PVST+, "a Cisco enhancement of RSTP that uses PVST+", é "the default STP mode" no Catalyst 9300 (Cisco, configuração de STP; Cisco Networking Academy, como acima). Em volta do protocolo existem recursos que o protegem do que acontece na borda da rede:

  • O PortFast "immediately transitions an access or trunk port from the blocking state directly to the forwarding state" (Cisco, PortFast e BPDU Guard); é o nome que a Cisco dá ao que o padrão chama de edge port.
  • O BPDU Guard age assim: se uma porta com PortFast recebe uma BPDU, "the switch immediately shuts the port down by placing it in the errdisable state" (mesma fonte). Com isso, um switch que alguém ligou embaixo da mesa não consegue entrar na árvore.
  • O Root Guard "ensures that the port on which root guard is enabled is the designated port" (Cisco, Root Guard): se chegar uma BPDU superior por essa porta, ela é bloqueada, e o root bridge continua o mesmo. O modelo do IEEE tem o mesmo controle, com o nome restrictedRole (YANG de RSTP do IEEE 802.1Q).
  • O Loop Guard coloca uma porta que parou de receber BPDUs "into the STP loop-inconsistent blocking state", em vez de deixá-la passar para forwarding (Cisco, Loop Guard).

Os recursos mais antigos que a Cisco criou para acelerar o STP clássico, o UplinkFast e o BackboneFast, não são mais necessários: "RSTP natively includes most of the Cisco proprietary enhancements to the 802.1D spanning tree, such as BackboneFast, UplinkFast, and PortFast" (Cisco, como funciona o RSTP).

Onde o padrão está hoje

Não existe mais um padrão separado para o spanning tree: "IEEE Std 802.1D-2004 was superseded by IEEE Std 802.1Q-2014", a edição que "merged IEEE Std 802.1D with IEEE Std 802.1Q in order to create a single bridging standard" (IEEE 802.1, 2021). O RSTP e o MSTP estão especificados na cláusula 13 do 802.1Q (YANG de MSTP do IEEE 802.1Q), cuja edição atual é o 802.1Q-2022 (manutenção do IEEE 802.1).

A engenheira e o poema

O algoritmo é obra de , que trabalhava na Digital Equipment Corporation e o apresentou num artigo publicado em 1985 (Perlman, 1985). O resumo (abstract) desse artigo é um poema, "Algorhyme", que começa assim: "I think that I shall never see / A graph more lovely than a tree" (Heidelberg Laureate Forum). Nas palavras dela: "I spent the remainder of the week working on the poem, which is the abstract of the paper" (LACNIC, 2019). O Internet Hall of Fame a incluiu em 2014 por ter projetado "the spanning tree algorithm that transformed Ethernet" (Internet Hall of Fame). A história das bridges e dos switches em torno do trabalho dela está em uma ideia, resolvida duas vezes.

Para lembrar

  • Frames Ethernet não têm TTL, então o tráfego preso num loop circula para sempre; o spanning tree evita loops bloqueando portas.
  • O switch com o menor bridge ID vira o root bridge; cada um dos outros switches tem uma root port; cada segmento, uma designated port; o resto fica bloqueado. Defina de propósito a prioridade do switch que deve ser o root bridge.
  • O STP clássico levava de 30 a 50 segundos para se recuperar; com o proposal e o agreement do RSTP, a convergência pode levar algumas centenas de milissegundos em links ponto a ponto e em edge ports.
  • O MSTP associa grupos de VLANs a poucas árvores; uma região se define por nome, revisão e mapeamento, iguais em todos os switches.
  • Proteja a borda: edge ports (PortFast) com BPDU Guard nas portas de host, e Root Guard nas portas por onde o root bridge nunca deve aparecer.

Fontes