Uma abordagem para redução da tabela de encaminhamento sob a ótica da interface de saída dos pacotes
Resumo
O aumento da tabela de roteamento global é um obstáculo para o crescimento da Internet. Além disso, o uso da virtualização em datacenter e as Redes Definidas por Software (SDN) intensificaram a demanda por recursos de processamento e armazenamento, aumentando ainda mais os custos das plataformas de roteamento. Este trabalho propõe um algoritmo que reduz o tamanho da tabela de encaminhamento (FIB) a partir de cálculos realizados com base na tabela de roteamento (RIB) sob a ótica da interface de saída para uma dada rota. Esta abordagem possibilita a redução da FIB de acordo com a topologia da rede empregada. Experimentos com o algoritmo proposto foram realizados com o software de roteamento BIRD em máquinas virtuais LXC no kernel do Linux. Medidas relativas ao tamanho da tabela de encaminhamento e à latência na rede foram obtidas e analisadas para um cenário que representa dois provedores de serviço de Internet anunciando prefixos com o protocolo BGP.
Referências
Alderson, D., Li, L., Willinger, W., and Doyle, J. C. (2005). Understanding internet topology: principles, models, and validation. Networking, IEEE/ACM Transactions on, 13(6):1205–1218.
Ballani, H., Francis, P., Cao, T., and Wang, J. (2009). Making Routers Last Longer with ViAggre. In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation, NSDI'09, pages 453–466, Berkeley, CA, USA. USENIX Association.
Berkowitz, H., Davies, E. B., Hares, S., Krishnaswamy, P., and Lepp, M. (2005). Terminology for Benchmarking BGP Device Convergence in the Control Plane. RFC 4098 (Informational). In RFC 4098. IETF Network Working Group. June 2005. Category: Informational. Online. Acessado em Agosto/2013. Disponível em: http://tools.ietf.org/html/rfc4098.
Bonaventure, O., Filsls, C., and Francois, P. (2007). Archieving Sub-50 Milliseconds Recovery Upon BGP Peering Link Failures. Networking, IEEE/ACM Transactions on, 15(5):1123–1135.
Caida (2014). The Cooperative Association for Internet Data Analysis. University of California San Diego Supercomputer Center. Acessado em Março/2014. Disponível em: http://www.caida.org.
Corrêa, C., Lucena, S., Rothenberg, C., and Salvador, M. (2012). Uma plataforma de ro- teamento como serviço baseada em redes denidas por software. In XVII Workshop de Gerência e Operação de Redes e Serviços. SBC - Sociedade Brasileira de Computação.
de Farias, L. F. T., Diniz, M. C., de Lucena, S. C., and Corrêa, C. N. A. (2013). Um Estudo Comparativo de Softwares de Roteamento para Uso em Redes Denidas por Software. In Workshop em Desempenho de Sistemas Computacionais e de Comunicação. SBC - Sociedade Brasileira de Computação.
Draves, R. P., King, C., Venkatachary, S., and Zill, B. D. (1999). Constructing optimal ip routing tables. In INFOCOM'99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, volume 1, pages 88–97. IEEE.
Fuller, V. and Li, T. (2006). Classless Inter-domain Routing (CIDR): The Internet Address Assignment and Aggregation Plan. In RFC 4632. IETF Network Working Group. Au- gust 2006. Category: Best Current Practice. The Internet Society. Online. Acessado em Novembro/2013. Disponível em: http://tools.ietf.org/html/rfc4632.
Huston, G. (2013). BGP Routing Table Analysis Reports. In Personal site of Geoff Huston that provides updated statistical analysis and reports on Internet BGP data. Online. Acessado em Setembro/2013. Disponível em: http://bgp.potaroo.net.
Kumar, M. and Kumar, S. (2013). Improving routing in large networks inside autonomous International Journal of System Assurance Engineering and Management, system. pages 1–8. Springer India.
Liu, Y., Zhang, B., and Wang, L. (2013). FIFA: Fast incremental FIB aggregation. In INFOCOM, 2013 Proceedings IEEE, pages 1–9. IEEE.
Mai, J. and Du, J. (2013). BGP performance analysis for large scale VPN. In Information Science and Technology (ICIST), 2013 International Conference on, pages 722–725.
Manral, V., White, R., and Shaikh, A. (2005). Benchmarking basic ospf single router control plane convergence. In RFC 4061. IETF Internet Requests for Comments. April 2005. Category: Informational. Online. Acessado em Junho/2012. Disponível em: http://tools.ietf.org/html/rfc4061.
Meyer, D., Zhang, L., and Fall, K. (2007). Report from the IAB Workshop on Routing & Addressing. In RFC 4984. IETF Network Working Group. April 2007. Category: Internet-Draft. Online. Acessado em Junho/2013. Disponível em: http://tools. ietf.org/html/draft-iab-raws-report-02.
Mohamed, H., Bashandy, A., and Shaheen, S. I. (2012). Protocol based selective FIB download for distributed forwarding architecture. In Globecom Workshops (GC Wkshps), 2012 IEEE, pages 7–12. IEEE.
Morrison, D. R. (1968). Patricia—practical algorithm to retrieve information coded in alphanumeric. Journal of the ACM (JACM), 15(4):514–534.
Raszuk, R., Heitz, J., Lo, A., Zhang, L., and Xu, X. (2012). Report from the IAB Workshop on Routing & Addressing. In RFC 6769. IETF Internet Requests for Com- ments. October 2012. Category: Informational. Online. Acessado em Junho/2013. Disponível em: http://tools.ietf.org/html/rfc6769.
Rottenstreich, O., Radan, M., Cassuto, Y., Keslassy, I., Arad, C., Mizrahi, T., Revah, Y., and Hassidim, A. (2013). Compressing forwarding tables. In INFOCOM, 2013 Proceedings IEEE, pages 1231–1239.
Routeviews (2014). Route Views Project. University of Oregon. Acessado em Março/2014. Disponível em: http://www.routeviews.org.
Sánchez, B. C. (2013). Virtual Aggregation in OpenFlow Networks. Master's thesis, KTH Royal Institute of Technology, Stockholm, Sweden.
Trotter, G. (2001). Terminology for forwarding information base (b) based router per- formance. In RFC 3222. IETF Internet Requests for Comments. December 2001. Ca- tegory: Informational. Online. Acessado em Agosto/2013. Disponível em: http:// tools.ietf.org/html/rfc3222.
Uzmi, Z. A., Nebel, M., Tariq, A., Jawad, S., Chen, R., Shaikh, A., Wang, J., and Francis, In Proceedings P. (2011). SMALTA: Practical and Near-optimal FIB Aggregation. of the Seventh COnference on Emerging Networking EXperiments and Technologies, CoNEXT '11, pages 29:1–29:12, New York, NY, USA. ACM.
Ballani, H., Francis, P., Cao, T., and Wang, J. (2009). Making Routers Last Longer with ViAggre. In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation, NSDI'09, pages 453–466, Berkeley, CA, USA. USENIX Association.
Berkowitz, H., Davies, E. B., Hares, S., Krishnaswamy, P., and Lepp, M. (2005). Terminology for Benchmarking BGP Device Convergence in the Control Plane. RFC 4098 (Informational). In RFC 4098. IETF Network Working Group. June 2005. Category: Informational. Online. Acessado em Agosto/2013. Disponível em: http://tools.ietf.org/html/rfc4098.
Bonaventure, O., Filsls, C., and Francois, P. (2007). Archieving Sub-50 Milliseconds Recovery Upon BGP Peering Link Failures. Networking, IEEE/ACM Transactions on, 15(5):1123–1135.
Caida (2014). The Cooperative Association for Internet Data Analysis. University of California San Diego Supercomputer Center. Acessado em Março/2014. Disponível em: http://www.caida.org.
Corrêa, C., Lucena, S., Rothenberg, C., and Salvador, M. (2012). Uma plataforma de ro- teamento como serviço baseada em redes denidas por software. In XVII Workshop de Gerência e Operação de Redes e Serviços. SBC - Sociedade Brasileira de Computação.
de Farias, L. F. T., Diniz, M. C., de Lucena, S. C., and Corrêa, C. N. A. (2013). Um Estudo Comparativo de Softwares de Roteamento para Uso em Redes Denidas por Software. In Workshop em Desempenho de Sistemas Computacionais e de Comunicação. SBC - Sociedade Brasileira de Computação.
Draves, R. P., King, C., Venkatachary, S., and Zill, B. D. (1999). Constructing optimal ip routing tables. In INFOCOM'99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, volume 1, pages 88–97. IEEE.
Fuller, V. and Li, T. (2006). Classless Inter-domain Routing (CIDR): The Internet Address Assignment and Aggregation Plan. In RFC 4632. IETF Network Working Group. Au- gust 2006. Category: Best Current Practice. The Internet Society. Online. Acessado em Novembro/2013. Disponível em: http://tools.ietf.org/html/rfc4632.
Huston, G. (2013). BGP Routing Table Analysis Reports. In Personal site of Geoff Huston that provides updated statistical analysis and reports on Internet BGP data. Online. Acessado em Setembro/2013. Disponível em: http://bgp.potaroo.net.
Kumar, M. and Kumar, S. (2013). Improving routing in large networks inside autonomous International Journal of System Assurance Engineering and Management, system. pages 1–8. Springer India.
Liu, Y., Zhang, B., and Wang, L. (2013). FIFA: Fast incremental FIB aggregation. In INFOCOM, 2013 Proceedings IEEE, pages 1–9. IEEE.
Mai, J. and Du, J. (2013). BGP performance analysis for large scale VPN. In Information Science and Technology (ICIST), 2013 International Conference on, pages 722–725.
Manral, V., White, R., and Shaikh, A. (2005). Benchmarking basic ospf single router control plane convergence. In RFC 4061. IETF Internet Requests for Comments. April 2005. Category: Informational. Online. Acessado em Junho/2012. Disponível em: http://tools.ietf.org/html/rfc4061.
Meyer, D., Zhang, L., and Fall, K. (2007). Report from the IAB Workshop on Routing & Addressing. In RFC 4984. IETF Network Working Group. April 2007. Category: Internet-Draft. Online. Acessado em Junho/2013. Disponível em: http://tools. ietf.org/html/draft-iab-raws-report-02.
Mohamed, H., Bashandy, A., and Shaheen, S. I. (2012). Protocol based selective FIB download for distributed forwarding architecture. In Globecom Workshops (GC Wkshps), 2012 IEEE, pages 7–12. IEEE.
Morrison, D. R. (1968). Patricia—practical algorithm to retrieve information coded in alphanumeric. Journal of the ACM (JACM), 15(4):514–534.
Raszuk, R., Heitz, J., Lo, A., Zhang, L., and Xu, X. (2012). Report from the IAB Workshop on Routing & Addressing. In RFC 6769. IETF Internet Requests for Com- ments. October 2012. Category: Informational. Online. Acessado em Junho/2013. Disponível em: http://tools.ietf.org/html/rfc6769.
Rottenstreich, O., Radan, M., Cassuto, Y., Keslassy, I., Arad, C., Mizrahi, T., Revah, Y., and Hassidim, A. (2013). Compressing forwarding tables. In INFOCOM, 2013 Proceedings IEEE, pages 1231–1239.
Routeviews (2014). Route Views Project. University of Oregon. Acessado em Março/2014. Disponível em: http://www.routeviews.org.
Sánchez, B. C. (2013). Virtual Aggregation in OpenFlow Networks. Master's thesis, KTH Royal Institute of Technology, Stockholm, Sweden.
Trotter, G. (2001). Terminology for forwarding information base (b) based router per- formance. In RFC 3222. IETF Internet Requests for Comments. December 2001. Ca- tegory: Informational. Online. Acessado em Agosto/2013. Disponível em: http:// tools.ietf.org/html/rfc3222.
Uzmi, Z. A., Nebel, M., Tariq, A., Jawad, S., Chen, R., Shaikh, A., Wang, J., and Francis, In Proceedings P. (2011). SMALTA: Practical and Near-optimal FIB Aggregation. of the Seventh COnference on Emerging Networking EXperiments and Technologies, CoNEXT '11, pages 29:1–29:12, New York, NY, USA. ACM.
Publicado
28/07/2014
Como Citar
DE FARIAS, Luiz Fernando; DINIZ, Morganna; DE LUCENA, Sidney.
Uma abordagem para redução da tabela de encaminhamento sob a ótica da interface de saída dos pacotes. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (WPERFORMANCE), 13. , 2014, Brasília.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2014
.
p. 40-53.
ISSN 2595-6167.
