IMEISSN 1982-9035

Monografias em Sistemas e Computaon ____/2013

Estudo de mtricas de topologia pararesilincia em redes de computadores

Eduardo Wiegmann VieiraCludia Marcela JustelRonaldo Moreira Salles

Seo de Engenharia de Computao

INSTITUTO MILITAR DE ENGENHARIA

PRAA GENERAL TIBRCIO 80 CEP 22290-270

RIO DE JANEIRO BRASIL

Monografias em Sistemas e Computao, No. /2013 ISSN: 1982-9035Editor: Prof. Setembro, 2013

Anlise de mtricas para resilincia em redes decomputadores

Eduardo Wiegmann Vieira1, Cludia Marcela Justel1, Ronaldo Moreira Salles1 1Instituto Militar de Engenharia (IME)

eduardo.vieira@ymail.com, cjustel@ime.eb.mil.br, salles@ime.eb.br

Abstract. As the use of Internet grows so does its importance as a criticalinfrastructure. It is used for applications that demand connectivity even onadverse scenarios, namely resilient networks. Therefore it is imperative thatwe develop metrics that allow us to understand which topologies are bestsuited to resist targeted and random attacks as well as simple failures. Thiswork aims to show some of the current metrics that are currently used tomeasure the resilience of computer networks as well as some of theircharacteristics.

Keywords: Networks, Metrics, Resilience, Graphs.

Resumo. medida que o uso da Internet cresce, aumenta a suaimportncia como infraestrutura crtica. Hoje a Internet usada paraaplicaes que exigem a conectividade constante mesmo diante decenrios adversos, ou seja, redes resilientes. Assim sendo necessriodesenvolver mtricas que permitam a compreenso de que topologias somais adequadas para resistir ataques direcionados e aleatrios, assim comofalhas simples. Estre trabalho visa a mostrar algumas das mtricas usadasatualmente para medir a resilincia de redes de computadores assim comoalgumas de suas caractersticas.

Palavras-chave: Redes, Mtricas, Resilincia, Grafos.

ii

Responsvel pela publicao:Ricardo Choren NoyaIME Seo de Engenharia de ComputaoPraa General Tibrcio 80, Praia Vermelha22290-270, Rio de Janeiro/RJ, BrasilTel. +55 21 2546-7090E-mail: choren@ime.eb.br

ii

1 Introduo

A importncia crescente da Internet para o funcionamento da sociedade fezcom que interrupes no seu funcionamento se tornassem cada vez maiscrticas (STERBENZ, 2010). Assim sendo, tornou-se imprescindvel apreocupao com o projeto de redes resistentes a falhas e ataques. Vistoque a demanda crescente e os recursos disponveis para a expanso so,em geral, limitados, necessrio tambm estabelecer parmetros queindiquem qual a melhor estratgia para alocao de novas conexes.

Neste cenrio ganha relevncia o estudo de mtricas que indiquem oquanto uma rede capaz de resistir a alteraes no seu funcionamentonormal e que possam indicar ao analista como as redes se comportamdiante de diferentes ataques ou falhas e quais alteraes so necessriaspara obter uma melhor relao custo-benefcio.

Este trabalho tem como objetivo apresentar as tendncias de pesquisamais relevantes no que se refere ao tema assim como mostrar comofunciona uma mtrica tpica.

Para atingir este objetivo, o artigo est dividido em 4 Sees: (1)Apresentao de uma viso geral da rea de pesquisa de resilincia emrededes de computadores; (2) Exposio de conceitos relativos a resilinciae das mtricas mais notveis para resilincia; (3) Testes realizados com umamtrica exemplo (conectividade algbrica) e (4) Concluso.

2 Resilincia em Redes de Computadores

Um dos elementos fundamentais na especificao do protocolo IP era acapacidade de continuar operando mesmo diante da indisponibilidade dealguns enlaces ou ns da rede. Assim sendo, o debate sobre a resilinciaem redes de computadores central para o desenho de qualquerinfraestrutura.

Uma definio qualitativa desta propriedade foi dada por Aggelou (2008,apud MARINO, 2009, p. 16) Resilincia em redes a habilidade de tolerar(resistir e automaticamente se recuperar de) desafios nas condies darede, ataques coordenados e anomalias no trfego.

O primeiro passo para projetar redes resilientes, como lembra (GAO eLIU, 2013) estabelecer medidas que permitam avaliar a resposta dasredes quando sofrem ataques. Para tanto importante estabelecermtricas que permitam comparar redes distintas e avaliar a sua capacidaderelativa de resistir a adversidades. Alm disso os mtodos propostos devemtratar variveis como: a complexidade computacional para o clculo, anecessidade de resultados coerentes para topologias de tamanho e formatodistintos e a importncia de modelar tanto a possibilidade de falhas ouataques nos roteadores ou nos enlaces.

Um dos primeiros trabalhos encontrados a tratar deste problema foi o de(FRANK, 1970), que tratava como medida de resilincia o menor nmero dearestas que, removidas, eram capazes de desconectar um grafo.

1

Trabalhos como o de (DEKKER, 2004) fazem uma relao entre atopologia da rede e a sua resilincia usando mtricas tpicas de grafos(dimetro, grau dos ns, grau mdio, etc) assim como observando ocomportamento desses valores diante de ataques aleatrios oudirecionados.

(NAJJAR, 1990), por sua vez, introduziu a noo de resilincia em redespara uma probabilidade p (NR(p)) como o nmero de falhas que uma redepode sofrer mantendo uma probabilidade de estar conectada de 1-p.

Outros trabalhos como o de (JAMAKOVIC, 2007) usam a definio deconectividade algbrica como uma medida da robustez de um grafo. Outrasmedidas propostas para resolver o referido problema so citadas em(SYDNEY, 2013) e (QIN, 2013) sero expostas na seo a seguir.

2.1 Topologias Lgicas e Fsicas

A maior parte da pesquisa atual focada no estudo do comportamento demodelos lgicos de topologia. Esta modelagem feita associando oselementos da rede analisada a um grafo e tipicamente realizada em umdestes dois nveis de granularidade: nvel de AS (Autonomous System) ounvel de roteador (STERBENZ, 2010).

Em uma modelagem a nvel de AS (Autonomous System), como feita por(WINICK, 2002) cada AS modelado como um n de um grafo e asconexes entre os AS proporcionadas so modeladas como arestas. Aobteno dos dados feita pela anlise das tabelas BGP. Em uma modelagem em nvel de roteador, como feita por (MEDINA,2000), cada roteador modelado como um n do grafo e os enlaces que osligam so modelados como as arestas. A obteno dos dados para amodelagem feita pela anlise das tabelas de roteamento da rede.

Figura 2.1 Representao da rede da provedora Sprint nas perspectivaslgica (do ponto de vista da camada IP), lgica (do ponto de vista doroteamento MPLS) e fsica (disposio fsica das fibras pticas) Para fazer a modelagem fsica, deve-se associar a cada sistemaintermedirio uma aresta no grafo e a cada enlace de comunicao umaaresta e, alm disso, armazenar a disposio geogrfica de cada elemento. A observao da figura 2.1 permite concluir que a modelagem datopologia na camada de roteamento, como feita pela maioria dos estudosde resilincia tem suas limitaes para avaliar o impacto de incidentesocorridos em camadas inferiores. Isto especialmente verdadeiro para ocaso de desastres em larga escala, como podemos observar na Figura 2.1, odesligamento de alguns enlaces devido a um acontecimento na regioNordeste dos EUA desconectaria enlaces at a costa Oeste, produzindo um

2

efeito totalmente diferente do que se imaginaria ao observar a topologialgica (Figura 2.1 (a)). Apesar de se conhecer as limitaes da modelagem lgica, no seconhece a disposio fsica da maior parte dos elementos fsicos queconstituem a Internet, dependendo-se de meios indiretos para a descoberta,como os propostos por (BREITBART, 2000).

3 Conceitos e Mtricas em grafos

3.1 Matriz Laplaciana de um grafo

Como definido por (MERRIS, 1994, traduo nossa) Seja G um grafo com nvrtices. A sua matriz Laplaciana a matriz n-por-n L(G) = D(G)- A(G), ondeA(G) a matriz de adjacncia familiar (0,1) e D(G) a matriz diagonal como grau dos vrtices. A matriz Laplaciana de um grafo importante para efetuar o clculo daconectividade algbrica, que conforme mostra (FIEDLER, 1973) e(JAMAKOVIC, 2007), oferece uma noo geral da dificuldade relativa em sedesconectar os ns de um grafo.

3.2 Conectividade algbrica

Define-se conectividade algbrica como o segundo menor autovalorassociado matriz Laplaciana de um grafo (FIEDLER, 1973). Conformeavaliado por (JAMAKOVIC, 2007), a conectividade algbrica variasignificativamente conforme a topologia analisada, assim sendo, servecomo indicador da robustez de um grafo.

A conectividade algbrica tem algumas propriedades que tornam o seuuso como mtrica atraente como: crescimento monotnico com o aumentodo conjunto de arestas (ou seja, ao adicionar uma aresta a um grafo o valorda conectividade algbrica no diminui); tem uma relao direta com onmero de componentes conectados (o seu valor maior que zero se, esomente, se o grafo conectado); e, alm disso, um grafo com pequenaconectividade algbrica mais fcil de ser desconectado que um grafo commaior conectividade algbrica (GHOSH, 2006).

Apesar disso, o seu uso como mtrica fica limitado por dois fatores,principalmente: (1) topologias similares sofrem aumentos percentuaissignificativos mediante a adio de uma nica aresta, o que significa umaumento desproporcional da conectividade algbrica em relao aoaumento percebido de resilincia da rede e (2) conforme mostrado por(GHOSH, 2006) a conectividade algbrica limitada superiormente pelomenor valor de grau de vrtice do grafo, ou seja, qualquer vrtice com grauum capaz de limitar significativamente o valor da conectividade algbrica,independentemente da estrutura restante.

3.3 Largest Connected Component (LCC)

O maior componente conectado de um grafo (LCC) o nmero de ns doseu maior subgrafo. O intuito dessa medida avaliar qual poro do grafo

3

permanece conectada depois de uma falha ou ataque, ou seja, serve comomedida de disponibilidade. O LCC comumente empregado em simulaes para verificar como ografo se comporta mediante determinados tipos de ataque. Em(BEYGELZIMER, 2005), por exemplo, vemos como essa medida empregada em conjunto com a simulao de ataques direcionados aos nsde maior grau ou aleatrios. O uso do LCC de especial interesse visto queele permanece finito mesmo diante da fragmentao da rede (o que noacontece com o menor caminho entre dois ns, que pode assumir valoresinfinitos conforme a rede se desintegra), decrescente conforme um ataqueou falha aumenta de tamanho e converge para a unidade no caso extremo.

3.4 Coeficiente de Robustez (Piraveenan et al.)

(PIRAVEENAN, 2012) usa o LCC para compor a sua mtrica de robustez,definindo um ndice R para cada tipo de ataque. Por exemplo, considerandoum grafo completo com 11 ns sob um ataque direcionado, temos que aremoo de um n causa a diminuio do seu LCC em uma unidade.

Figura 3.1 Relao entre o nmero de ns no LCC de um grafo completode 11 ns ( direita) e de um grafo menos resiliente ( esquerda) e onmero de ns removidos [PIRAVEENAN, 2012]

A medida da robustez da rede, segundo o artigo, estaria associada reasob a curva. Isto baseado na ideia que, quanto menos resiliente for arede, mais rpido o decaimento do LCC, pois a remoo de um vrticepode ocasionar a desconexo de outros, como ilustrado na figura 3.1. Destaforma, a robustez poderia ser expressa por um quociente entre a rea dogrfico da rede analisada e a rea do grfico do grafo completo, conforme afrmula abaixo, onde Sk o tamanho do LCC aps a retirada de k vrtices eN o tamanho do grafo. Da definio, podemos concluir que o grafocompleto tem R=1 e o valor progressivamente menor conforme diminui aredundncia no grafo.

(3.1) Outro aspecto relevante desta mtrica o fato de ela ser dependente dotipo de ataque sofrido. Ou seja, o grafo pode ter um valor diferente de Rpara ataques aleatrios ou para ataques aos vrtices de maior grau.

4

3.5 Average Inverse Shortest Path Length (AISPL)

Outra maneira de avaliar a queda de performance da rede aps a ocorrnciade um incidente por meio do AISPL. Conforme observado em(BEYGELZIMER, 2005), medida que as arestas so removidas de umarede, fica cada vez mais difcil encontrar o menor caminho entre dois ns.Dessa forma, o aumento do caminho mnimo entre dois ns serviria paramostrar o decaimento do desempenho da rede. Uma vez que nsdesconexos fariam com que a medida do menor caminho perdesse osentido, usa-se o inverso desta medida, tratando pares ns desconexoscomo detentores de AISPL igual a zero, mantendo a coerncia da mtrica.

3.6 Distribuio dos graus nos ns

Pela definio de (MAHADEVAN,2006, traduo nossa) a distribuio de graunos ns a probabilidade de um ns escolhido aleatoriamente ser de grauk.

P(k)=n(k)/n (3.2)A importncia desta mtrica se d principalemente pela relao que foi

descoberta entre ela e a estrutura da Internet, segundo uma relao depotncia como observado por (BARABASI, 2000) e (CHEN, 2002).

3.7 Grau mdio

Para um grafo com n vrtices e m arestas, o grau mdio definido como k= 2m/n. Trata-se de uma das medidas mais simples de robustez de umgrafo mas, como mostra (MAHADEVAN, 2005) e (HADDADI, 2008) grafoscom maior grau mdio tendem a ser maior robustez. Uma limitao claradesta mtrica que o grau mdio pode esconder fragilidades na estruturado grafo pois alguns vrtices dele podem ser a nica ligao entresubgrafos com LCC grande e, em decorrncia disso, a sua remoo podeimplicar em uma fragmentao da rede diante de um ataque direcionado.

3.8 Path diversity

Tendo em vista que a robustez est associada diversidade (RAK, 2010),(ROHRER, 2005) props uma mtrica que considerasse a diversidade decaminhos dentro do grafo analisado que apresentaremos a seguir. Dados um par de vrtices origem (s) e destino (d), um caminho P entreeles um conjunto contendo todos os vrtices N e arestas L atravessados eo comprimento de P igual soma do nmero de elementos de N e L. SejaP0 o menor caminho entre s e d, L0 o conjunto das arestas que soatravessadas para percorrer este caminho e N0 os vrtices atravessados.Para qualquer outro caminho Pk entre a mesma origem e destino, definimosa funo diversidade D(x) com relao a P0 como:

(3.3)

5

Por esta definio a diversidade de caminhos igual a 1 caso P0 e Pksejam disjuntos e 0 caso sejam idnticos.

3.9 K-conectividade

A k-conectividade apresentada como medida de confiabilidade de umarede em (BERTSEKAS, 1992). Sua definio, de acordo com (SKIENA, 2008) Seja G um grafo k conexo. Ento para qualquer par de vrtices A e Bexistem pelo menos k caminhos vrtices-disjuntos entre A e B. Para obter o valor de k para um grafo necessrio testar todas ascombinaes de retirada de k-1 vrtices e testar a conectividade entre osvrtices restantes. Ou seja, para testar se um grafo 3-conexo, temos queverificar todas as combinaes de remoo de 2 vrtices e verificar se aconectividade do grado mantida para todos os vrtices restantes. Como custo computacional aumenta significativamente para grafos commaior nmero de vrtices, a aplicao desta mtrica difcil para redesmaiores. Alm disso, a mtrica mostra a capacidade do grafo em perdervrtices sem que seja interrompida a comunicao entre eles limitando ovalor da resilincia do grafo ao pior caso (isto de certa forma limita aaplicao da medida a ambientes que so absolutamente crticos e nopodem perder a conexo de maneira alguma). Este tipo de raciocnio vai deencontro ao princpio que vemos no uso da mtrica LCC. Nesta mtrica d-se maior importncia manuteno da maior parte de conectividade e aperda de um conjunto pequeno de vrtices no crtica para a rede.

3.10 K-conectividade parcial

Como uma maneira de comparar estruturas que so k-conexas, foi propostoo conceito de k-conectividade parcial. A ideia central da k-conectividadeparcial de, para um grafo com n vrtices, testar a k-conectividade paravalores de 2 a k-1 e verificar quantas combinaes de retirada de vrticesainda mantm a conectividade. Na frmula (3.5) FR o fator de resilincia,n o nmero de vrtices do grafo e k(i) refere-se ao percentual decombinaes conexas de i-conectividade.

(3.4)

3.11 ndice de Robustez R (Herrman et al.)

(HERRMAN, 2011) associou a robustez de um grafo com o tamanho mdiodo maior componente conectado aps a remoo de ns. A robutez R, nestadefinio, soma a frao dos ns no maior componente conectado s(Q) apsa remoo de Q ns de um grafo inicialmente com N ns

(3.5)

6

Figura 3.3 Correspondncia entre o maior componente conectado s(q) e aproporo de ns removidos q para diversas topologias [Herrman, 2011].A robustez, dessa forma, corresponde integral das curvas apresentadasnos grficos da Figura 3.3 e indicaria (indo ao encontro da teoria dapercolao) a partir de que momento a rede se desfaz.

4 Testes Realizados

4.1 Aumento da conectividade algbrica como um problema NP-hard

Conforme mostrado por (JAMAKOVIC, 2007), a conectividade algbrica podeser usada como uma medida do quanto difcil desconectar um grafo(quanto maior o valor, mais difcil desconectar o grafo). Assim sendo, umasoluo que use a conectividade algbrica como mtrica devenecessariamente buscar o maior aumento possvel desta medida. No entanto, como mostra (MOSK-AOYAMA, 2008) o problema de, dado umgrafo, encontrar a aresta que, uma vez includa, provoca o maior aumentopossvel de conectividade algbrica NP-hard. Desta maneira, solues queusem a fora bruta ficam limitadas a grafos com pequeno nmero de

7

vrtices e arestas, uma vez que o nmero de operaes aumentaexponencialmente.

4.2 Heurstica para aumento de conectividade algbrica

Tendo em vista que a conectividade algbrica um autovalor da matrizLaplaciana de um grafo e tem um autovetor associado (tambm conhecidocomo vetor de Fiedler (FIEDLER, 1973)) foi proposto por (GHOSH, 2006) umalgoritmo que usasse as propriedades deste autovetor para promover omaior aumento da conectividade algbrica. O algoritmo consiste em: (1) numerar os vrtices do grafo, (2) construir amatriz Laplaciana correspondente, (3) encontrar o valor da conectividadealgbrica (segundo menor autovalor), (4) calcular o vetor de Fiedler(autovetor associado conectividade algbrica), (5) encontrar no vetor deFiedler os valores mais positivos e mais negativos, (6) acrescentar ao grafoa aresta ligando os vrtices associados aos valores encontrados no passo(5).

4.3 Metodologia empregadaPara avaliar a validade da conectividade algbrica como mtrica assimcomo a eficincia da heurstica proposta por (GHOSH, 2006) foramrealizados testes usando 4 topologias de mesmo nmero de vrtices: (1)grafo caminho com 28 ns, (2) grafo ciclo com 28 ns, (3) rede Ip, da RNP(Fig. 4.1 Disponvel em www.rnp.br/_images/backbone/bkb_ipe-6a.geracao.2013.png Acesso em 4 set. 2013), com 28 ns e 33 arestas,com peso nas arestas igual a um, (4) rede Ip, da RNP (Fig. 4.1.), com 28ns e 33 arestas, com peso nas arestas igual distncia rodoviriaaproximada entre as cidades (este ltimo experimento foi feito paraverificar se a mtrica se mantm coerente mesmo para este tipo de grafo).Como forma de simplificar a modelagem e manter a obedincia dasrestries do algoritmo, foram ignoradas as diferenas de velocidade dosenlaces, tratando apenas a topologia da rede.

8

Figura 4.1 Rede Ip, da RNP 6 Gerao

O objetivo do experimento verificar quais so as sugestes de inclusode aresta para o algoritmo proposto por (GHOSH, 2006), qual o impacto daincluso destas arestas sobre a conectividade algbrica e qual odesempenho do algoritmo proposto por (GHOSH, 2006) em relao aomelhor caso possvel. Para atingir estes objetivos, foi calculado usando o sotware Matlab valoresde conectividade algbrica para os casos enumerados e verificado quais soas incluses propostas pelo algoritmo. Tendo em vista que o nmero devrtices relativamente pequeno (28 vrtices) foi possvel realizar o clculode fora bruta em tempo computacional vivel.

4.4 Resultados obtidos

Tomando como referncia o grafo caminho com 28 vrtices, o algoritmoproposto por (GHOSH, 2006) prope a incluso de uma aresta unindo asextremidades. Para o grafo ciclo, foi proposta a incluso de uma arestacorrepondente ao dimetro do grafo (unindo os vrtices 7 e 14). Assimsendo, para casos simples, pudemos verificar que o algoritmo propesolues coerentes para aumento da resilincia. Aplicado ao grafo da rede Ip sem peso nas arestas, o algoritmo sugeriu aincluso de uma aresta unindo Rio Branco a Fortaleza o que fez aconectividade algbrica mudar de 0,0388 para 0,0762. Aplicando oalgoritmo ao grafo da rede Ip com peso nas arestas, foi proposta a incluso

9

de uma aresta unido Rio Branco a Joo Pessoa e foi observado um aumentoda conectividade algbrica de aproximadamente 10 para 45. O teste de fora bruta verificou que o melhor aumento possvel deconectividade algbrica para o grafo da rede Ip sem peso nas arestasocorre pela incluso de um enlace entre So Lus e So Paulo. Esta inclusofaz o valor da mtrica saltar para 0,1248, em contraste com o valor de0,0762 encontrado pelo algoritmo proposto por (GHOSH, 2006). Apesar de a conectividade algbrica ser uma medida do quanto difcildesconectar uma rede, exatamente como mostra (JAMAKOVIC, 2007) a suaaplicao imediata como mtrica no possvel, como foi mostrado noexperimento, uma vez que a incluso de uma nica aresta em uma redecomplexa como a da RNP no pode ocasionar um aumento da mtrica deresilincia em 96% (para a sugesto do algoritmo) ou 221% (para o melhorcaso). Por sua vez, apesar de o algoritmo proposto por (GHOSH, 2006)proporcionar um aumento bem maior que a mera adio randmica dearestas (mostrado em GHOSH, 2006) seu resultado bem discrepante emrelao ao melhor caso.

5 Concluso

Este artigo buscou apresentar os principais conceitos e tendnciasrelacionados ao estabelecimento de mtricas para avaliar a resilincia deuma topologia de rede computacional. Apesar do progresso observadodesde os primeiros trabalhos publicados, a diversidade natural presente nasredes de computadores, como lembra (STERBENZ, 2010) faz com que sejaintratvel modelar todos os tipos de falhas e ataques possveis a uma redede computadores.

Assim sendo, em vez de elaborar modelos progressivamente maiscomplexos, a soluo para este dilema est em investigar como uma redereage s adversidades e tratar a resilincia como um mapeamento entre oestado da rede e a sua capacidade de prover os servios desejados namesma linha de (STERBENZ, 2010) e (HERRMAN, 2011). Voltando ideia da resilincia como a capacidade da rede de permaneceroperando mesmo sob condies adversas obrigatrio recordar aimportncia da topologia fsica para a resilincia do conjunto. Assim sendo,dados sobre a estrutura fsica devem ser obtidos sempre que possvel,apesar da dificuldade de se obter dados concretos. O tratamento de errosprovido pelas camadas fsica e de enlace no eliminam os efeitos de umapane catastrfica nessas camadas. Da mesma forma, uma topologia lgicaredundante pode esconder uma topologia fsica frgil, altamentedependente de alguns elementos o que, sem dvida limita a resilincia darede.

6 Referncias Bibliogrficas

ALBERT, Rka; JEONG, Hawoong; BARABSI, Albert-Lszl. Error and attacktolerance of complex networks. Nature, v. 406, n. 6794, p. 378-382, 2000.

10

AGGELOU, G. Wireless Mesh Networking. McGraw-Hill Professional, 2008.ISBN 0071482563.BACKBONE REDE IP. In: Rede Nacional de Ensino e Pesquisa. Rio deJaneiro, 2013. Disponvel em:.Acesso em: 4 set. 2013.BARABSI, Albert-Lszl; ALBERT, Rka; JEONG, Hawoong. Scale-freecharacteristics of random networks: the topology of the world-wideweb.Physica A: Statistical Mechanics and its Applications, v. 281, n.1, p. 69-77, 2000. BERTSEKAS, Dimitri P.; GALLAGER, Robert G.; HUMBLET, Pierre. Datanetworks. Prentice-Hall International, 1992. BEYGELZIMER, Alina et al. Improving network robustness by edgemodification. Physica A: Statistical Mechanics and its Applications, v.357, n. 3, p. 593-612, 2005.BREITBART, Yuri et al. Topology discovery in heterogeneous IP networks.In:INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEEComputer and Communications Societies. Proceedings. IEEE. IEEE,2000. p. 265-274. CHEN, Qian et al. The origin of power laws in Internet topologies revisited.In:INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEEComputer and Communications Societies. Proceedings. IEEE. IEEE,2002. p. 608-617. DEKKER, A. H. e COLBERT, B. Scale-free networks and robustness of criticalinfrastructure networks. Em Proceedings of the 7th Asia-Pacific Conferenceon Complex Systems, Complex 2004, Cairns, Australia, December 2004a.FIEDLER, Miroslav. Algebraic connectivity of graphs. CzechoslovakMathematical Journal, v. 23, n. 2, p. 298-305, 1973. FRANK, Howard; FRISCH, I. Analysis and design of survivable networks.Communication Technology, IEEE Transactions on, v. 18, n. 5, p. 501-519, 1970. GAO, Ming; LIM, Ee-Peng; LO, David. R-energy for evaluating robustness ofdynamic networks. In: Proceedings of the 5th Annual ACM WebScience Conference. ACM, 2013. p. 89-98. GAO, Long; LIU, Ruifang. Network robustness under large-scaleattacks. Springer, 2013. GHOSH, Arpita; BOYD, Stephen. Growing well-connected graphs.In:Decision and Control, 2006 45th IEEE Conference on. IEEE, 2006. p.6605-6611. HADDADI, Hamed et al. Network topologies: inference, modeling, andgeneration. Communications Surveys & Tutorials, IEEE, v. 10, n. 2, p.48-69, 2008. HERRMANN, Hans J. et al. Onion-like network topology enhances robustnessagainst malicious attacks. Journal of Statistical Mechanics: Theory andExperiment, v. 2011, n. 01, p. P01027, 2011.

11

JAMAKOVIC, Almerima; UHLIG, Steve. Influence of the network structure onrobustness. In: Networks, 2007. ICON 2007. 15th IEEE InternationalConference on. IEEE, 2007. p. 278-283. JAMAKOVIC, A.; UHLIG, S. On the relationship between the algebraicconnectivity and graph's robustness to node and link failures. In: NextGeneration Internet Networks, 3rd EuroNGI Conference on. IEEE,2007. p. 96-102. JAMAKOVIC, A.; VAN MIEGHEM, Piet. On the robustness of complex networksby using the algebraic connectivity. In: NETWORKING 2008 Ad Hoc andSensor Networks, Wireless Networks, Next Generation Internet.Springer Berlin Heidelberg, 2008. p. 183-194. JUNIOR, D.A.M. Estratgias e Mtricas para Resilincia em Redes deComputadores. 2009. 84 f. Dissertao (Mestrado) Instituto Militar deEngenharia, Seo de Engenharia de Computao, Rio de Janeiro, 2009.MAHADEVAN, Priya et al. Lessons from three views of the Internettopology.arXiv preprint cs/0508033, 2005. MAHADEVAN, Priya et al. Systematic topology analysis and generation usingdegree correlations. ACM SIGCOMM Computer Communication Review,v. 36, n. 4, p. 135-146, 2006. MAHADEVAN, Priya et al. The Internet AS-level topology: three data sourcesand one definitive metric. ACM SIGCOMM Computer CommunicationReview, v. 36, n. 1, p. 17-26, 2006. MEDINA, Alberto; MATTA, Ibrahim; BYERS, John. On the origin of power lawsin Internet topologies. ACM SIGCOMM computer communicationreview, v. 30, n. 2, p. 18-28, 2000. MERRIS, Russell. Laplacian matrices of graphs: a survey. Linear algebraand its applications, v. 197, p. 143-176, 1994. MOSK-AOYAMA, Damon. Maximum algebraic connectivity augmentation isNP-hard. Operations Research Letters, v. 36, n. 6, p. 677-679, 2008. NAJJAR, W. e GAUDIOT, J.-L. Network resilience: A measure of network faulttolerance. IEEE Transactions on Computers, 39(2):174181, 1990.PIRAVEENAN, Mahendra; UDDIN, Shahadat; CHUNG, Kon Shing Kenneth.Measuring topological robustness of networks under sustained targetedattacks. In: Advances in Social Networks Analysis and Mining(ASONAM), 2012 IEEE/ACM International Conference on. IEEE, 2012.p. 38-45. QIN, Jun et al. A quantitative method for determining the robustness ofcomplex networks. Physica D: Nonlinear Phenomena, 2013. RAK, Jacek. -Penalty: a novel approach to find -Disjoint paths withdifferentiated path costs. Communications Letters, IEEE, v. 14, n. 4, p.354-356, 2010. ROHRER, Justin P.; JABBAR, Abdul; STERBENZ, James PG. Pathdiversification: A multipath resilience mechanism. In: Design of ReliableCommunication Networks, 2009. DRCN 2009. 7th InternationalWorkshop on. IEEE, 2009. p. 343-351.

12

SCOTT, Darren M. et al. Network robustness index: A new method foridentifying critical links and evaluating the performance of transportationnetworks. Journal of Transport Geography, v. 14, n. 3, p. 215-227, 2006.SKIENA, Steven. The Algorithm Design Manual: Text. Springer, 1998. STERBENZ, James PG et al. Resilience and survivability in communicationnetworks: Strategies, principles, and survey of disciplines. ComputerNetworks, v. 54, n. 8, p. 1245-1265, 2010. SYDNEY, Ali; SCOGLIO, Caterina; GRUENBACHER, Don. Optimizing algebraicconnectivity by edge rewiring. Applied Mathematics and Computation,v. 219, n. 10, p. 5465-5479, 2013. WINICK, Jared; JAMIN, Sugih. Inet-3.0: Internet topology generator.Technical Report CSE-TR-456-02, University of Michigan, 2002.

13

1 Introduo2 Resilincia em Redes de Computadores2.1 Topologias Lgicas e Fsicas

3 Conceitos e Mtricas em grafos3.1 Matriz Laplaciana de um grafo3.2 Conectividade algbrica3.3 Largest Connected Component (LCC)3.4 Coeficiente de Robustez (Piraveenan et al.)3.5 Average Inverse Shortest Path Length (AISPL)3.6 Distribuio dos graus nos ns3.7 Grau mdio3.8 Path diversity3.9 K-conectividade3.10 K-conectividade parcial3.11 ndice de Robustez R (Herrman et al.)

4 Testes Realizados4.1 Aumento da conectividade algbrica como um problema NP-hard4.2 Heurstica para aumento de conectividade algbrica4.3 Metodologia empregada4.4 Resultados obtidos

5 Concluso6 Referncias Bibliogrficas