Spanning trees (árvores de abrangência)

Para prevenir os congestionamentos broadcast e outros efeitos colaterais indesejados das ligações em loop, a empresa Digital Equipment Corporation criou o protocolo spanning tree (STP), que foi padronizado como a especificação 802.1d pelo IEEE - Institute of Electrical and Electronic Engineers - Instituto dos Engenheiros Elétricos e Eletrônicos (em inglês). Um protocolo spanning tree utiliza um algoritmo spanning tree (STA), que percebe que o switch tem mais de uma maneira de se comunicar com um nó. Este protocolo determina o melhor caminho e bloqueia os outros. Outra vantagem é que ele memoriza os outros caminhos, caso o caminho principal esteja indisponível.

Veja abaixo de que maneira funciona o STP.

• Cada switch administra um grupo de IDs, um para o próprio switch e um para cada porta do switch. O identificador do switch, chamado de ID de ponte (BID), tem 8 bytes que contêm a prioridade da ponte (2 bytes) junto com um dos endereços MAC do switch (6 bytes). Cada ID de porta tem 16 bits formados por duas partes: uma configuração de prioridade de 6 bits e um número de porta de 10 bits.

• Um valor de custo de caminho é atribuído a cada porta. O custo é baseado num guia estabelecido pelo padrão 802.1d. De acordo com a especificação original, o custo é de 1 mil Mbps (1 gigabit por segundo) dividido pela largura de banda do segmento conectado à porta. Portanto, uma conexão de 10 Mbps teria um custo de (1.000/10) 100.

  Para compensar as velocidades de redes que ultrapassam a velocidade de um gigabit, o custo padrão foi levemente modificado. Os novos valores são:

  Largura de banda	Custo do STP
  4 Mbps	250
  10 Mbps	100
  16 Mbps	62
  45 Mbps	39
  100 Mbps	19
  155 Mbps	14
  622 Mbps	6
  1 Gbps	4
  10 Gbps	2

  Também é possível que o administrador da rede atribua um valor arbitrário ao custo de caminho, em vez de usar um dos valores padrão.

• cada switch inicia um processo de exploração para descobrir qual caminho de rede ele deve usar para cada segmento. Essa informação é compartilhada com todos os switches através de uma rede especial de frames conhecida como BPDU (bridge protocol data units - unidades de dados de protocolo de ponte). 
  • BID raiz. Este é o BID da ponte raiz atual.
  • Custo de caminho para a ponte raiz. Determina o quão longe está a ponte raiz. Por exemplo, se os dados trafegam por três segmentos de 100 Mbps para chegar à ponte raiz, o custo é de (19 + 19 + 0) 38. O segmento conectado à ponte raiz normalmente tem um custo de caminho igual a zero.
  • BID remetente. Este é o BID que o switch envia para o BPDU.
  • ID de porta. Esta é a porta real no switch da qual as informações BPDU foram enviadas.

  Todos os switches estão constantemente enviando BPDUs uns para os outros, tentando determinar o melhor caminho entre os vários segmentos. Quando um switch recebe um BPDU (de outro switch) que é melhor do que ele está transmitindo na direção oposta, o switch pára de enviar BPDU para este segmento. Em vez disso, ele armazenará o BPDU do outro switch como referência e para fazer a difusão para segmentos inferiores, como aqueles que estão mais distantes da ponte raiz.

• uma ponte raiz é escolhida com base nos resultados dos processos BPDU entre os switches. Inicialmente, cada switch se considera uma ponte raiz. Quando um switch é conectado à rede, ele envia um BPDU com o seu próprio BID com BID raiz. Quando os outros switches recebem o BPDU, eles comparam este BID com os outros BIDs armazenados como BID raiz. Se o novo BID raiz tiver um valor mais baixo, eles substituem o BID armazenado. Mas se o BID raiz armazenado for menor, um BPDU é enviado para o novo switch com o novo valor. Quando o novo switch recebe o BPDU, ele descobre que não é a ponte raiz e substitui o BID raiz na lista de endereços pelo BID raiz que acabou de receber. O resultado é que o switch que tem o menor BID é eleito pelos outros switches como ponte raiz;

• de acordo com a localização da ponte raiz, os outros switches determinam as portas com o menor custo para a ponte raiz. Estas portas são chamadas portas raízes e cada switch (exceto a ponte raiz atual) deve ter uma;

• os switches determinam quem terá as portas designadas. Uma porta designada é a conexão utilizada para enviar e receber pacotes em um segmento específico. Se existir somente uma porta designada para cada segmento, todos os problemas da ligação em loop estarão resolvidos;

  As portas designadas são selecionadas de acordo com o custo mais baixo para a ponte raiz em cada segmento. Como a ponte raiz tem custo "0", quaisquer de suas portas que estiverem conectadas a segmentos serão portas designadas. Para outros switches, o custo é comparado com o segmento em questão. Se uma porta tiver um custo menor, ela se torna uma porta designada para aquele segmento. Se duas ou mais portas tiverem o mesmo custo, o switch com o menor BID é escolhido.

• uma vez que uma porta designada para o segmento é escolhida, todas as outras portas que se conectam àquele segmento se tornam portas não-designadas. Elas bloqueiam o tráfego naquele caminho e só acessam o segmento através da porta designada.

Cada switch tem uma tabela de BPDUs atualizada constantemente. A rede é configurada como uma única spanning tree. A ponte raiz se torna o tronco da árvore e os outros switches se tornam os galhos. Cada switch se comunica com a ponte raiz através das portas raízes e com cada segmento através das portas designadas. Assim, a rede fica livre de ligações em loop. Se a ponte raiz começar a falhar ou se a rede apresentar problema, o STP permite que outros switches reconfigurem a rede e designem outro switch como ponte raiz. Este processo incrível dá a uma empresa a possibilidade de ter uma rede complexa e tolerante a falhas, mas ainda assim,  fácil de gerenciar.