Intelligent Route Control for Inter-domain Routing

Abstract

The Internet is being increasingly criticized for the poor Quality of Service (QoS) guarantees it provides across the boundaries of Autonomous Systems (AS). The Border Gateway Protocol (BGP) protocol lies at the root of this problem, because its route discovery and path selection mechanisms are agnostic with regard to any performance or QoS metrics. Underlying the work carried out in this thesis is the identification of the unresolved issues concerning the inter-domain QoS Routing (QoSR), and a survey of the approaches that have been adopted to tackle this problem. Most of the solutions that have been devised for this end, adopt an approach that involves extending BGP with a new QoS route attribute to carry the network state information within update messages. However, the QoS Extensions to BGP (q-BGP) failed to address the most critical issues, such as simplicity and scalability, deployment costs, fast path failover, and the end-user network or application-centered QoS. A promising traffic control technique that can be able to satisfy these basic requirements, and has been increasingly adopted by multi-homed stub ASs to deal with BGP flaws, is to perform Intelligent Route Control (IRC). More precisely, this means that special network middleboxes, which are called IRC controllers, supplement the functionality of BGP, so that the active path used by the stubs to deliver traffic to remote peers, can be selected in short timescales, while actively monitoring the end-to-end performance or the quality of all the available paths. The primary objective of this thesis is to study the intelligent route control for inter-domain routing and address some of the key challenges raised by adopting this strategy. The first issue is to be aware that conceiving an IRC system correctly is a challenging task, as currently there are no standard design guidelines. The second is that IRCs may oscillate, especially when a large number of IRCs compete for the same network resources. The third is that selfishness is a common characteristic of the IRCs, as well as of the backbone Traffic Engineering (TE) middleboxes, since the paths are greedily selected by each box, which if there is a misalignment of traffic goals can cause performance degradation of the traffic. This thesis provides the design of an IRC controller and report results on the development of its mechanisms. The functional architecture that has been devised for the IRCs, draws on a set of requirements for inter-domain QoSR and aims at addressing the challenges that they raise. Path monitoring, and path switching algorithms and routing decision policies are devised and evaluated through simulation. This includes a formal analysis of the time needed by IRCs to failover, together with an outline of two mechanisms for handling lost probes: a revision of the Jacobson’s algorithm for congestion control and an algorithm based on the box-plot descriptive statistical tool. Since IRCs may oscillate persistently, we also investigate a number of ways of dealing with this issue (randomized path switching, randomized path monitoring and history-aware path switching). The evaluations show to what extent of the proposed approach and mechanisms employed in this thesis are applicable. First, the results show the feasibility of basing end-user network or application-centric routing on the IRC technique, to improve interdomain QoS. Compared with a BGP-based approach, this technique achieves a better performance with respect to the latency and efficiency of traffic transfers. Second, the results show that when IRCs are blended with the Jacobson or box-plot-based algorithms, they can adapt their timeout timers to network conditions, and above all, protect them against spurious timeouts. Finally, the results show that adding randomness to the route control process is the most effective solution to avoid IRC oscillations, whereas the use of sophisticated IRC algorithms, such as history-aware path switching, is questionable, since they require additional tuning. This thesis also includes the provision of a Social IRC (SRC) strategy for competitive environments. This is a joint work undertaken with the Technical University of Catalonia (UPC) under the auspices of E-NEXT and CONTENT 6º FP IST NoE projects. The simulations show that a simple enhancement of randomized IRCs, like endowing them with a SRC algorithm supported by adaptive filtering techniques, makes it possible to drastically reduce the number of path switches needed to achieve the desired performance bounds of the traffic. Finally, this thesis provides a new cooperative framework to balance the divergent interests between stub and transit networks, which is called an Internet Service Provider (ISP)-friendly IRC COOPerative framework (COOP). This is based on a cooperative strategy between direct neighbors and a feedback method, and is, as far as we know, the first successful strategy that has been employed to tackle the problem of the interactions between the IRC and TE boxes. The evaluation results show the feasibility of applying this framework, since it meets the traffic goals of each party, while ensuring the stability of IRC. Furthermore, it has the added advantage of producing synergistic interactions between both traffic control boxes. We believe that this thesis can help to bring about significant advances in the state-of-the-art of intelligent route control. It is also hoped that the study will provide valuable guidelines for the design of similar systems and further inter-domain QoSR and traffic engineering mechanisms in the future.

Um dos principais problemas da Internet é o fato de não oferecer garantias de Qualidade de Serviço (QdS) para além das fronteiras dos Sistemas Autónomos (SA). Na raiz do problema está protocolo BGP (Border Gateway Protocol), dado que a descoberta e seleção de percursos é agnóstica de métricas de desempenho ou de QdS. Subjacente ao trabalho desenvolvido nesta tese, está a identificação das questões em aberto no encaminhamento inter-domínio com QdS (IDQdS) e o levantamento das abordagens adoptadas à resolução do problema. A maioria das soluções identificadas envolve a adição de extensões ao BGP para distribuição de informação sobre o estado da rede. Contudo, as extensões de QdS ao BGP (q-BGP) falham na resposta a requisitos essenciais, tais como: simplicidade e escalabilidade, contenção de custos, rápida detecção e recuperação de falhas, e suporte da entrega de tráfego centrada nos requisitos de desempenho fim-a-fim ou QdS dos AS nos extremos ou da aplicação. Uma técnica de controlo de tráfego que promete satisfazer estes requisitos básicos que tem vindo a ser adoptada pelos SAs com múltiplas ligações à Internet para lidar com a ineficiência do BGP, é o Controlo Inteligente de Percurso (CIP). Esta envolve o uso de caixas especiais, designadas por controladores ou sistemas CIP com o objectivo de complementar a funcionalidade do BGP, por forma a que a ligação ativa para transmissão do tráfego seja selecionada enquanto é monitorizado o desempenho fim-a-fim ou QdS oferecidos por cada ligação. O principal objectivo desta tese é estudar o CIP e endereçar alguns dos desafios chave suscitados pela adopção desta técnica. O primeiro relaciona-se com a inexistência de recomendações padrão para a concepção de um sistema completo de CIP. O segundo é lidar com o problema da oscilação dos percursos, causado pela sincronização dos sistemas CIP. O terceiro deve-se ao facto dos CIP e as ferramentas de engenharia de tráfego inter-domínio procurarem atingir os objetivos de tráfego de forma egoísta, sendo que uma acentuada divergência entre os mesmos pode conduzir à degradação do desempenho do tráfego. Esta tese fornece a concepção de um sistema CIP e reporta os resultados do desenvolvimento dos seus mecanismos. A arquitetura funcional foi concebida com base num conjunto de requisitos para encaminhamento IDQdS, e visa enfrentar os desafios do CIP. Os mecanismos para monitorização e comutação inteligente de percurso são concebidos e avaliados. É incluída uma análise do tempo necessário a um CIP para contornar a falha de um percurso, conjuntamente com dois algoritmos desenhados para lidar com a perda dos pacotes de prova aos percursos: uma revisão do algoritmo de Jacobson para o controlo de congestão e um algoritmo baseado na ferramenta de análise estatística, a caixa de bigodes. Para se restringir as oscilações nos percursos, são estudadas várias estratégias para se lidar com esta questão (introdução de um factor de acaso na seleção do percurso ou na geração de pacotes de prova, e comutação de percursos com base num histórico). As avaliações mostram até que ponto o CIP e os mecanismos empregues são válidos. Primeiro, os resultados mostram a viabilidade do CIP na melhoria da QdS interdomínio, incluindo os objectivos de tráfego dos ASs extremo ou da aplicação. Comparado com o BGP, o CIP atinge melhor desempenho no que diz respeito à latência e eficiência das transferências de tráfego. Em segundo lugar, os resultados mostram a eficácia de se combinar um CIP com um algoritmo do tipo Jacobson ou baseado na caixa de bigodes, sobretudo na redução do número de detecções intempestivas. Finalmente, os resultados mostram a eficácia das várias estratégias CIP para redução das oscilações, sendo que a introdução do factor de acaso na seleção de percurso a mais promissora, sem ser necessário uma calibração adicional. Esta tese fornece também a concepção de um modelo de controlo de percurso sociável para ambientes competitivos, resultante do trabalho conjunto com a Universidade Politécnica da Catalunha, realizado no âmbito dos projetos E-NEXT e CONTENT do 6º Programa Quadro. Neste modelo, cada CIP implementa um algoritmo de controlo de percurso social que de forma adaptativa restringe o seu egoísmo. Os resultados de simulações, mostram que dotando-se um CIP com um algoritmo sociável suportado por uma técnica de filtragem adaptativa, permite uma drástica redução das oscilações. Finalmente, nesta tese é concebido o esquema – CIP COOPerativo (COOP) – amigo dos fornecedores de serviço Internet, o qual permite conciliar os interesses divergentes do CIP e da engenharia de tráfego inter-domínio. O COOP propõe um desenho conjunto, com base numa estratégia de cooperação e num método de realimentação. Os resultados das avaliações mostram que o COOP supera o cenário em que os CIP e as caixas de engenharia tráfego inter-domínio operam de forma autônoma e egoísta. Para além das vantagens oferecidas pelos CIP, os resultados revelam uma redução efetiva da penalização sobre desempenho da engenharia de tráfego originada pelos CIP, enquanto é assegurada a estabilidade do CIP. Em suma, o COOP pode produzir uma interação sinérgica entre ambos os mecanismos, dado que são satisfeitos os objectivos de tráfego de cada parte, incluindo a estabilidade do CIP. Espera-se que esta tese forneça avanços significativos ao estado da arte do controlo inteligente de percurso e valiosas linhas de orientação à concepção de sistemas similares, e demais futuros protocolos de encaminhamento e mecanismos de engenharia de tráfego inter-domínio.