link-state routing

Um método de roteamento em que cada roteador faz o flooding da descrição dos próprios enlaces e calcula caminhos sobre o mapa comum.

É a família do OSPF e do IS-IS. Cada roteador mantém um link-state database idêntico ao de todos os roteadores da área e roda o algoritmo de Dijkstra sobre ele, tendo a si mesmo como raiz. As mudanças viajam como anúncios do estado local de cada roteador.

A RFC 2328 descreve o banco de dados como o conjunto do estado local de cada roteador, suas interfaces utilizáveis e vizinhos alcançáveis, distribuído por flooding. Todos os roteadores rodam o mesmo algoritmo em paralelo e cada um monta uma árvore de caminhos mais curtos com ele próprio na raiz; do resultado, só o próximo hop é usado no encaminhamento. A norma chama isso de um afastamento da base Bellman-Ford dos protocolos TCP/IP mais antigos.

Duas salvaguardas mantêm o mapa coerente. Um enlace só entra no cálculo se o roteador da outra ponta também anunciar o enlace de volta, e todo anúncio leva número de sequência, checksum e idade, que decidem qual cópia é mais nova. A RFC 4593 lembra por que isso importa: erros num roteador do algoritmo link-state original da ARPANET criaram três instâncias de um mesmo anúncio, que circularam sem parar até a rede inteira ser religada.

A escala vem da hierarquia, áreas no OSPF e níveis no IS-IS. Um roteador guarda um banco de dados separado para cada área de que participa, e entre áreas do OSPF só passam resumos, o que o FRRouting descreve como roteamento distance-vector entre áreas. O FRRouting também observa que o cálculo em si é quase desprezível nas CPUs atuais; o peso real está no flooding e no banco de dados à medida que a área cresce.

Também conhecido como: link state, link-state protocol, link-state database, lsdb

Fontes

← Todos os verbetes do glossário