Introdução
Esquecemos-nos frequentemente que a rede de computadores foi desenvolvida para suportar as já existentes redes humanas - trocas entre pessoas, de informação, conhecimento, ideias, opiniões, visões, e conselhos. Neste texto, olha-se para a tecnologia que foi desenvolvida para descrever e medir as redes humanas – análise de redes sociais – e aplicam-se alguns dos seus princípios e algoritmos no desenho de redes informáticas. À medida que vemos mais modelos de redes peer-to-peer (P2P) baseadas em redes informáticas, as métricas P2P na análise das redes humanas tornam-se ainda mais aplicáveis.
Analistas de redes sociais, vêm sistemas humanos complexos como um sistema interligado de nós (pessoas ou grupos) e laços (relações e fluxos) – muito à semelhança das interligações de routers e links. As redes humanas são normalmente não planeadas, são sistemas emergentes. O seu crescimento é esporádico e auto organizacional (1). Os laços na rede acabam por ser desigualmente distribuídos, com algumas áreas da rede densamente ligadas e outras ligeiramente ligadas. Estas são chamadas de “redes de pequeno mundo” (2). As redes de computadores apresentam normalmente padrões semelhantes de ligações – interligações densas nas subredes, e ligeiras ligando subredes numa rede mais vasta.
Investigadores e consultores de redes sociais focam-se na geodésica – caminho mais curto na rede. Muitos dos actuais algoritmos de redes sociais, baseiam-se num ramo da matemática chamado de teoria dos grafos. Cientistas das redes sociais têm concentrado o seu trabalho, e desta forma os seus algoritmos, nas seguintes áreas:
Centralidade do nó individual dentro da rede mais vasta – dependência da rede e tráfego de routers individuais;
Distribuição final de caminhos – boa ligação sem excessivas tabelas de roteamento;
Melhoria no fluxo de comunicação dentro e entre grupos – desenho de melhores topologias;
Padrões na rede envolvendo ego redes – estratégias para a análise e manipulação individual de ligações;
Análise de fluxos comportamentais da organização cliente – como as redes informáticas podem suportar redes humanas.
Um dos métodos usados na compreensão de redes e dos seus participantes, é o da avaliação da localização dos seus actores. Medir a localização da rede é o mesmo que determinar a centralidade do nó (3). Todas as medições da rede discutidas aqui, baseiam-se na geodésica – o caminho mais curto entre quaisquer dois nós. Iremos analisar a rede social, chamada de kite network, que mostra efectivamente a distinção entre as três medidas de centralidade mais populares – os AIPs (ABCs) – Actividade, Intermedialidade, e Proximidade (Activity, Betweenness, and Closeness).
Este modelo (4) foi primeiramente desenvolvido por David Krackhardt, um investigador pioneiro em redes sociais.
Actividade
A figura 1 mostra uma rede social simples. Uma ligação entre um par de nós, descreve um fluxo bidireccional de informação ou a partilha de conhecimento entre dois indivíduos. Os investigadores das redes sociais medem a actividade da rede para um nó recorrendo ao conceito de graus – o número de ligações directas que um nó tem.
Figura 1 - Rede humana
Nesta rede humana, Diane tem o maior número de ligações directas na rede, fazendo dela o nó mais activo na rede, com a maior contagem de grau. O senso comum em redes sociais é “quanto mais ligações melhor”. Isto nem sempre é verdade. O que realmente importa é o destino dessas ligações – e como elas ligam o que de outra forma estaria desligado! (5) Aqui, Diane está ligada apenas aos que se encontram no grupo imediato – o seu clã. Ela liga-se apenas aqueles que se encontram previamente ligados entre si – terá ela muitas ligações redundantes?
Intermedialidade
Enquanto Diane tem muitas ligações directas, Heather tem poucas – menos do que a média na rede. No entanto, de muitas formas, ela está numa das melhores localizações da rede – ela é a chave inglesa fronteiriça, e interpreta o papel de corretor. Ele está entre dois importantes constituintes, numa tarefa igual ao de um router de fronteira. As boas notícias são as de ela interpretar um importante papel na rede, as más notícias são as de se tratar dum ponto singular de falha. Sem ela, Ike e Jane estarão arredados da informação e conhecimento no grupo de Diane.
Proximidade
Fernando e Garth têm menos ligações que Diane, no entanto, o padrão dos seus laços permite o acesso a todos os nós da rede mais depressa que qualquer outro. Eles têm os caminhos mais curtos para todos os outros – eles estão próximos a qualquer outro. Maximizando a proximidade entre todos os routers, melhora a actualização e minimiza o número de saltos. Maximizando a proximidade de apenas um ou alguns routers, leva a resultados contraproducentes, tal como examinaremos mais a baixo.
A sua posição demonstra que no que diz respeito a ligações na rede, qualidade supera quantidade. Localização, localização, localização – a regra douro do mercado imobiliário também funciona nas redes. No imobiliário é a geografia – a sua vizinhança física. Nas redes, é a sua localização virtual determinada pelas ligações da rede – a sua vizinhança na rede.
Centralidade da rede
Centralidades individuais na rede, são reveladoras da localização individual na rede. A relação entre a centralidade de todos os nós pode ser bastante reveladora da estrutura da rede. Uma rede muito centralizada é dominada por um ou poucos nós muito centrais. Se esses nós forem removidos ou danificados, a rede depressa se fragmenta, em subredes desconectadas. Nós muito centralizados podem-se tornar pontos críticos de falha. Uma rede de baixa centralidade não é dominada por um ou poucos nós – tal rede não possui pontos singulares de falha. É resiliente face a muitas das falhas locais. Muitos nós ou ligações podem falhar, continuando a permitir que os restantes nós comuniquem entre si através de novos caminhos.
Distância média na rede
Quanto mais curto o caminho, menos passos/saltos são necessários para se ir dum nó para outro. Nas redes humanas, caminhos curtos significam rápida comunicação com pouca distorção. Nas redes informáticas, a degradação do sinal e o atraso não normalmente uma questão. No entanto, uma rede com muitos caminhos curtos ligando todos os nós será mais eficiente no transporte de informação e na reconfiguração após uma mudança de topologia.
A distância média na rede está fortemente correlacionada com a proximidade ao longo da rede. Enquanto a proximidade entre os nós (proximidade média), melhora igualmente a distância média na rede.
Topologia de rede
No recente livro de implementação de redes, Advanced IP Network Design (6), os autores definem uma topologia bem definida como a base para uma rede estável e robusta. Mais à frente propõem que “três objectivos contraditórios deverão ser balanceados numa bom desenho de rede”:
Redução do número de saltos;
Redução do número de caminhos disponíveis;
Aumento do número de falhas que a rede pode suportar.
Os nossos algoritmos de rede podem ajudar na medição e no encontro destes objectivos.
Reduzindo o número de saltos induz-se a minimização da distância média na rede – maximizando a proximidade entre cada nó;
A redução do número de caminhos leva à minimização do número da geodésicas na rede;
Aumentando o número de falhas que a rede pode resistir, focando-se na minimização da centralidade de toda a rede.
Nas seguintes linhas, examinaremos vária topologias de rede, e avaliaremos-as recorrendo à unidade de medição das redes sociais, enquanto relembramos os três objectivos antagónicos de dimensionamento de redes.
Os modelos que iremos examinar não cobrem estruturas hierárquicas – com núcleo, distribuição, e níveis de acesso – que se encontram nas redes de centenas ou milhares de routers. Examinaremos topologias simples e não hierárquicas, tais como as que se encontram em pequenas redes informáticas, subredes locais, ou com os backbones. As topologias abordadas são as mais comuns – Estrela, anel, ligação total (full mesh), ligação parcial (partial mesh). Calcularemos os valores das redes sociais em cada uma das topologias e discutiremos como estes valores nos ajudam a atingir os objectivos descritos anteriormente.
Topologia de estrela
A topologia de estrela, presente na figura 2, tem muitas vantagens – mas uma falha importante. As vantagens incluem facilidade de gestão e configuração para administradores de redes. Para esta topologia, os três objectivos definem-se da seguinte maneira:
Redução da contagem de passos: O caminho mais curto (1,75) ao longo da rede atinge bem o objectivo. Qualquer router pode chegar a qualquer outro router em dois passos ou menos;
Redução do número de caminhos: O facto de haver um número mínimo de caminhos disponíveis (56) para se chegar a qualquer nó – não sobrecarregará as tabelas de routeamento, nem causará atrasos durante as suas actualizações. Necessita apenas de sete ligações bidireccionais para se criarem caminhos disponíveis;
Redução de falhas de rede: A rede falha de forma miserável se o router A for abaixo. Igualmente, qualquer falha de ligação isola o router associado – Não existem múltiplos caminhos para se chegar a cada router.
Figura 2 - Routers na topologia de estrela
O router A não é apenas um ponto singular de falha – é também um ponto de estrangulamento – ficará provavelmente sobrecarregado com o fluxo de pacotes e actualizações de tabelas, à medida que mais routers venham a ser adicionados à estrutura de estrela.
O router A recebe a maior pontuação (1,000) para a Actividade, Intermedialidade, e Proximidade. Como resultado, a rede está muito centralizada à volta do router A da perspectiva de todas as medições.
Topologia de anel
A topologia de anel, presente na figura 3, é uma melhoria relativamente à de estrela. Tem algumas das mesmas vantagens, mas não elimina todas as desvantagens das de estrela. As vantagens incluem facilidade de gestão e configuração para os administradores de redes – adicionar outro router é muito simples. Ao contrário da topologia de estrela, a de anel providencia alguma redundância e, desta forma, elimina a falha de ponto único – todos os nós têm um caminho alternativo pelo qual se podem fazer comunicar. Mesmo assim, continua vulnerável à falha de duas ligações ou routers. Para esta topologia, os três objectivos definem-se da seguinte maneira:
Redução da contagem de passos: A distância média de 2,5 é bastante longa para uma rede pequena de oito nós. Alguns routers (ou seja, A e E) requerem quatro passos para comunicarem! Muitos níveis físicos do anel escondem esta complexidade dos níveis IP por forma a tornarem estes passos invisíveis para os protocolos de routeamento;
Redução do número de caminhos: Esta configuração tem uma geodésica maior (64) que a em estrela, no entanto não suficientemente maior para sobrecarregar as tabelas de routeamento, ou causar atrasos durante a sua actualização;
Redução de falhas de rede: Mesmo que a centralização da rede seja minimizada (nenhum nó é mais central que outro), esta rede falha depressa devido à sua fraca redundância. A topologia de anel pode suportar a falha duma ligação ou router e continuar a ser uma rede contínua. Duas falhas simultâneas podem criar segmentos inacessíveis devido à falta de redundância.
Figura 3 - Routers na topologia de anel
A maioria das tecnologias de anel, tais como a Synchronous Optical Network (SONET) ou a da Cisco Dynamic Packet Transport Protocol (DPT) adicionam uma certa redundância recorrendo-se dum duplo anel que se cura a si próprio se uma ligação for cortada. A rede “encapsula” por forma a evitar a linha cortada e opera a velocidades mais baixas. Um caminho de dois passos pode tornar-se num de seis se uma única ligação falhar. Isto pode causar congestionamento na rede, caso o anel duplo original esteja a ser usado no transporte de informação em ambos os sentidos.
Topologia de ligação total
A topologia de ligação total tem importantes vantagens e falhas. As vantagens incluem curta distância (um passo) para todos os outros routers e máxima resiliência a falhas caso ligações ou routers comecem a falhar. As desvantagens envolvem a complexidade criada por esta topologia. Para a topologia de ligação total, os três objectivos definem-se da seguinte maneira:
Redução da contagem de passos: O caminho mais curto possível é conseguido em todas as rotas – todos os nós podem-se contactar num único passo;
Redução do número de caminhos: Existe um número mínimo possível de caminhos disponíveis (56) para se chegar a todos os nós. As entradas de routeamento não sobrecarregarão as tabelas de routeamento, ou causarão atrasos durante a sua actualização;
Redução de falhas de rede: A rede não depende exclusivamente de nenhum nó (centralização = 0,000). Esta configuração representa a mais robusta topologia disponível – são poucas a hipóteses dum número simultâneo de falhas para que a rede se fragmente.
Figura 4 - Routers na topologia de ligação total
As desvantagens da topologia de ligação total centram-se numa importante falha – existem demasiadas ligações físicas. Se os routers estiverem muito distantes, o custo da ligação pode-se tornar de forma rápida proibitivamente caro, devido à explosão geométrica de ligações necessária ao adicionar de routers – brevemente os routers não teriam portas suficientes para suportarem esta topologia. Gerir este sistema e manter o mapa da topologia actualizado torar-se-ia cada vez mais complexo à medida que se adicionariam routers. A rede ilustrada na figura 4, tem 28 ligações bidireccionais. Dobrando o número de routers nesta topologia, a contagem de ligações sobe segundo um factor maior do que 4.
Topologia de ligação parcial
A topologia de ligação parcial é bastante diferente. É a mais difícil de implementar – não há nenhuma regra simples a seguir (regra para a de estrela: ligar todos ao router A; regra para a de ligação total: ligar todos a todos). Se incorrectamente implementada, a disposição desta topologia pode revelar muitas das desvantagens das topologias anteriores sem muitos dos seus benefícios. Caso seja implementada correctamente, o oposto será verdade – mais vantagens, menos desvantagens.
A implementação bem sucedida duma topologia deste género, é onde o uso iterativo das medidas da nossa rede social ganham vida. O desenho abaixo envolveu várias iterações. Para cada iteração, a distância média baixou até um plano, a partir do qual, posteriores alterações não baixaram a contagem de passos sem um aumento significativo de ligações físicas. Para a topologia de ligação parcial, os três objectivos definem-se da seguinte maneira:
Redução da contagem de passos: A média do caminho mais curto (1,667) na rede satisfaz bem este objectivo. Qualquer router pode chegar a qualquer outro em dois passos ou menos. A distância do caminho é menor que a das topologias em estrela ou anel.
Redução do número de caminhos: O número de caminhos operacionais na rede (72) é o maior de todas as topologias, apesar de não significativamente maior que o da topologia de anel. À medida que o número de nós na rede aumenta, isto pode-se tornar num problema – A ralação entre a distância média e o número de caminhos, necessita de ser observada de perto;
Redução de falhas de rede: A centralidade da rede (0,000) é a mesma que a da topologia de ligação total – nenhum router ou ligação, são mais importantes que qualquer outro. À medida que nós e ligações são removidas desta rede, esta não se fragmenta imediatamente. São poucas as hipóteses dum número simultâneo de falhas necessárias à fragmentação da rede. Apesar de termos optimizado a centralidade desta pequena rede, não podemos esperar o mesmo para redes reais. No entanto, o objectivo fixa-se em manter esta métrica o mais pequena possível.
Esta topologia, presente na figura 5, foi implementada com base na de anel – uma arquitectura simples. Uma ligação foi adicionada e a rede foi reavaliada. Seria esta estrutura melhor que a anterior? Assim sendo, manteve-se a actual estrutura e outra ligação foi adicionada, sendo a rede reavaliada novamente. Este processo iterativo foi continuado até não se conseguirem mais melhorias após várias mudanças. Este processo não garante uma solução óptima, no entanto converge rapidamente para uma boa solução – mesmo em redes grandes há uma melhoria rápida só com mais alguma ligações.
Figura 5 - Routers na topologia de ligação parcial
Um aspecto estranho das redes é o de às vezes poder-se subtrair adicionando – adicionando uma ligação à rede, pode-se reduzir a distância média. Às vezes, o oposto também é verdade. Pode-se adicionar subtraindo – remover uma ligação e observar a média de passos aumentar. No entanto, nunca se sabe com certeza qual o efeito de se adicionar ou reduzir uma ligação – não se trata dum fenómeno linear ou local. A dimensão e direcção destas alterações dependem da topologia existente e da localização da ligação adicionada ou removida. É essencial ter-se um modelo que permita conclusões rápidas relativas a várias hipóteses do tipo “e se”.
Experimentemos a remoção de ligações aleatoriamente – uma situação similar à de falha de ligações. Se remover-mos a ligação entre o router A e o router H na figura 5, o número de geodésicas na rede aumenta de 72 para 76, e a distância média aumenta para 1,815. No entanto, removendo uma ligação diferente, G para F, reduz o número de geodésicas na rede de 72 para 66, enquanto a distância média aumenta somente para 1,727. Se nos preocuparmos com o excesso de caminhos na rede, podemos remover outra ligação, B para C. Isto irá diminuir o número de caminhos mais curtos para 60, reduzindo desta forma as ligações físicas para 10. Isto é muito semelhante aos 56 caminhos na muito eficiente topologia de estrela. Onde a de estrela é muito vulnerável devido ao seu singular ponto de falha, esta topologia de ligação parcial, com as duas ligações removidas, mantém-se robusta. Enquanto o número de geodésicas cai, a distância média sobe ligeiramente para 1,80 com a remoção da segunda ligação. A figura 5 não possui caminhos com mais do que dois passos. Com as duas ligações (G para F, B para C) removidas, temos agora 8 geodésicas de três passos, enquanto ao mesmo tempo 12 geodésicas menos para serem inseridas nas tabelas de routeamento, e duas ligações físicas a menos. Trata-se duma constante negociação.
Backbone da NSFnet
A rede backbone da NSFnet, ilustrada na figura 6, ligava os centros de super-computação nos EUA em 1989. Trata-se duma rede de topologia de ligação parcial, que funciona como um exemplo real para testar os nossos algoritmos da rede social.
Figura 6 - NSFnet em 1989
Lembremo-nos das nossas metas antagónicas para um bom desenho de redes.
Reduzir a contagem de passos: comprimento médio em passos;
Reduzir os caminhos disponíveis: total de geodésicas na rede;
Aumentar o número de falhas que a rede pode resistir: centralidade da rede.
O que acontece a esses objectivos à medida que experimentamos falhas nas ligações ou nos nós da rede? A tabela 1 mostra as métricas base da figura 6 e depois mostra o que acontece a essas métricas, e aos nossos objectivos, quando cinco falhas diferentes ocorrem.
Tabela 1 - Falhas possíveis de ligações e nós
A mais destrutiva foi a falha de ligação 4 – a falha de ligação entre NCSA e PSC. Esta ligação une dois dos nós mais centrais da rede. Se os fluxos entre nós forem distribuídos de forma igual, então esta ligação é uma das mais viajadas da rede.
A menos destrutiva foi a do nó 3 – a falha do nó em JVNC. De facto, esta falha melhorou a maioria das métricas! Removendo este nó da rede, o número de caminhos baixou significativamente, a centralidade baixou, o comprimento médio baixou ligeiramente, e o maior caminho mantém os quatro passos.
A topologia original da NSFnet é muito eficiente. Tentou-se duas diferentes estratégias para se melhorar a rede. A primeira estratégia envolveu a deslocação de ligações existentes, para ligar diferentes pares de routers. Nenhuma topologia alternativa obviamente melhor foi encontrada através do rearranjo das ligações entre routers. Não foi possível encontrar um desenho melhor que reduzisse tanto o número de geodésicas como o comprimento médio, sem aumentar significativamente o número de ligações físicas na rede.
A segunda estratégia é contra-intuitiva, no entanto as redes respondem bem as esta abordagem. Trata-se da abordagem “subtraindo adicionando”, descrita anteriormente. Adicionando novas ligações nos locais certos na rede, não só reduzimos as distâncias entre nós, como também, diminuímos o número de geodésicas na rede.
Porque os nós NSFnet têm um limite máximo de três vizinhos directos, começou-se por ligar os nós de grau dois. As opções de 1 a 3 mostram as várias combinações e o seu efeito na totalidade da rede. As melhorias são mínimas, no entanto, cada opção oferece vantagens específicas.
A opção 2 oferece mais melhorias que as outras.
A geodésica mais longa foi reduzida para três passos;
A distância média foi reduzida ao longo da rede;
O número de caminhos para os routers foi ligeiramente reduzido;
A centralidade da rede não aumentou suficientemente para afectar o número de falhas que a rede pudesse suportar.
Table 2 - Melhorias possíveis na rede
A melhoria na opção 2 (nova ligação: NW-SDSC) foi na realidade implementada na versão de 1991 da NSFnet – um exemplo excelente da dinâmica da abordagem “subtraindo adicionando”. As redes são sistemas complexos. Como a rede responde à mudança, baseia-se na distribuição e no padrão das ligações ao longo dela.
Conclusão
No mundo real, podemos não ter a flexibilidade de experimentar com o nosso modelo de rede como o fizemos nos exemplos anteriores. Haverão maiores constrangimentos. Os fluxos de informação na nossa organização podem requerer que pares específicos de routers tenham ligações directas – mesmo que essas ligações não sejam recomendadas pelos algoritmos que temos vindo a examinar. No entanto, quando tiver-mos as nossas ligações “como deve ser” no lugar, podemos experimentar com o posicionamento das ligações restantes, recorrendo às métricas das redes sociais para indicar quando se está perto duma topologia robusta e eficiente.
Dadas as “condições iniciais”, os métodos das redes sociais podem modular as nossas redes informáticas e proporem alterações de ligações (7) para formar uma topologia eficiente que tenha uma pequena contagem média de passos, sem demasiados caminhos, e com a redundância necessária.
Bibliografia
– Valdis Krebs, The Social Life of Routers, Applying Knowledge of Human Networks to the Design of Computer Networks, The Internet Protocol Journal;
- Krebs V., Visualizing Human Networks, Esther Dyson's Monthly Report, February 1996;
- Watts D., Strogatz S., Collective Dynamics of Small World Networks, Nature, 4 June 1998;
- Freeman L., Centrality in Social Networks: A Conceptual Clarification, Social Networks, No. 1, 1979;
- Krackhardt D., Assessing the Political Landscape: Structure, Cognition, and Power in Organizations, Administrative Science Quarterly, No. 35, 1990, page 351;
- Burt, Ronald S., Structural Holes – The Social Structure of Competition, ISBN 0674843711, Harvard University Press, 1992;
- Retana, A., Slice, D., White, R., Advanced IP Network Design, ISBN 1578700973, Cisco Press, 1999;
Hagen G., Discussions with fellow network researcher, Guy Hagen, regarding combinatorial algorithms and models for recommending changes to improve the overall topology of a network.
