O problema dos caminhos estáveis e o roteamento entre domínios

Protocolos de roteamento dinâmico, como RIP e OSPF, implementam essencialmente algoritmos distribuídos para resolver o problema dos caminhos mais curtos. O protocolo de gateway de borda (BGP) é atualmente o único protocolo de roteamento entre domínios implantado na Internet. O BGP não resolve um problema de caminhos mais curtos, uma vez que qualquer protocolo interdomínio deve permitir que métricas baseadas em políticas substituam métricas baseadas em distância e habilitem sistemas autônomos a definirem independentemente suas políticas de roteamento com pouca ou nenhuma coordenação global. É natural, então, perguntar se o BGP pode ser visto como um algoritmo distribuído para resolver algum problema fundamental. Introduzimos o problema dos caminhos estáveis e mostramos que o BGP pode ser visto como um algoritmo distribuído para resolver esse problema. Ao contrário de uma árvore de caminhos mais curtos, tal solução não representa um ótimo global, mas sim um ponto de equilíbrio em que cada nó é atribuído ao seu ótimo local. Estudamos o problema dos caminhos estáveis usando uma estrutura derivada chamada roda de disputa, representando políticas de roteamento conflitantes em vários nós. Mostramos que, se nenhuma roda de disputa puder ser construída, então existe uma solução única para o problema dos caminhos estáveis. Definimos o protocolo de vetor de caminho simples (SPVP), um algoritmo distribuído para resolver o problema dos caminhos estáveis. O SPVP tem a intenção de capturar o comportamento dinâmico do BGP em um nível abstrato. Se o SPVP converge, então o estado resultante corresponde a uma solução de caminhos estáveis. Se não houver solução, então o SPVP sempre diverge. De fato, o SPVP pode até divergir quando uma solução existe. Mostramos que o SPVP convergirá para a solução única de uma instância do problema dos caminhos estáveis, se nenhuma roda de disputa existir.