Dhamdhere, A. and Dovrolis, C. 2009. An agent-based model
for the evolution of the internet ecosystem. In Proceedings of
the First international Conference on Communication Systems
and Networks (Bangalore, India, January 05 - 10, 2009). IEEE
Press, Piscataway, NJ, 493-502.
Dárlinton B. F. Carvalho
Maio de 2010
Apresentação
Introdução
Modelos baseado em Agentes
Modelando a Internet
Como usar o modelo
Resultados obtidos
Debate
Introdução
Visões sobre o Ecosistema Internet
 Biologia
• Análise de um ecosistema em evolução
 Economia
• Análise de aspectos econômicos
 Sociologia
• Internet é composta de pessoas – sociedade
 Matemática
• Análise dos aspectos quantitativos da rede
 Computação
• Engenharia da rede e convergência de análises
Modelos baseado em Agentes
 An agent-based model (ABM) is a class
of computational models for simulating the actions
and interactions of autonomous agents (both
individual or collective entities such as organizations
or groups) with a view to assessing their effects on
the system as a whole.
 It combines elements of game theory, complex
systems, emergence, computational sociology, multiagent systems, and evolutionary programming. Monte
Carlo Methods are used to introduce randomness.
 Most agent-based models are composed of:
 (1) numerous agents specified at various scales (typically
referred to as agent-granularity);
 (2) decision-making heuristics;
 (3) learning rules or adaptive processes;
 (4) an interaction topology; and
http://en.wikipedia.org/wiki/
 (5) a non-agent environment.
Agent-based_model
Modelando a Internet
O modelo considera a Internet no nível
interdomínio:
 Nível básico/central da Internet
 Redes autônomas (AS) – domínios –
competem pelo tráfego de dados
• Lucram com sua utilização
 Redes precisam se relacionar com outras redes
para prover conectividade a seus clientes
 Sofre influência de fatores externos e internos
 Baseado em BGP AS-paths de tabelas BGP
disponíveis nos repositórios Route Views
(desde 1997) e RIPE (desde 1999)
Modelando a Internet
 Rede de agentes egoístas que interagem
entre si, cada um objetivando otimizar sua
função utilidade (lucro).
 Um agente possui somente conhecimento
local, e pode mudar somente sua interação
com seus vizinho criando ou removendo
ligações.
 Os agentes possuem vários objetivos e
restrições.
 Considera questões como geografia, multihoming,
trânsito, pareamento, custos operacionais,
diferentes estratégias de escolhas para seleção de
pares e provedores de serviços.
Modelando a Internet
Objetivos:
 X gerador de topologia ou garantir
propriedades estruturais como graus de
distribuição
 Simulação de perguntas “e se” sobre possíveis
caminhos para evoluçao da Internet
• Qual é a melhor estratégia para seleção de
provedores e pares para provedores de trânsito
quando a a matriz de tráfego interdomínio consite em
sua maioria de tráfego cliente servidor?
 Estudar propriedades da rede como topologia,
fluxo de tráfego, economia e desempenho –
em um estádo estável – fim da simulação.
Modelando a Internet
Modelando a Internet
Agentes:
 Enterprise Customers (EC)
• Campus, corporate, residential access networks
 Content Providers (CP)
• Google, Akamai, MSN
 Small Transit Providers (STP)
• France Telecom, Rogers Telecom, Chinacom
 Large Transit Providers (LTP)
• Sprint, AT&T Level 3 Communications
Modelando a Internet
 Trafic model
 Routing model
 Economic model
 Geographical presence
 Provider selection methods
 Price-based (PR), Price-based Selective (SEL),
Performance-based (PF)
 Multihoming
 Peer selection methods
 Peering by necessity (NC), Peering by traffic ratios
(TR), Peering by cost-benefit analysis (CB)
 Network actions
 Provider selection, Try to peer with providers,
Check for potential peering candidates
Modelando a Internet
Modelo canônico
Modelando a Internet
Modelo canônico
Modelando a Internet
Computação do estado estável da rede
 Objetivo:
• Determinar o que acontece com a rede em termos de
topologia, fluxo de tráfego, economia e desempeho
quando STP e LTP usam diferentes estratégias para
provês e selecionar pares.
 O estado estável é uma situação onde
nenhuma rede tem o incentivo de trocar
unilateralmente seu conjunto de provedores ou
pares.
• Resolvido computacionalmente, já que é muito
complexo para ser resolvido analiticamente
Modelando a Internet
Computação do estado estável da rede
 O modelo é resolvido iterativamente em
rodadas permitindo que uma rede jogue (de
acordo com sua estratégia pré-definida a cada
movimento) a cada rodada até que se alcance
um estágio em que nenhuma rede queira
realizar ações.
• Análogo ao conceito de Equilíbrio de Nash em Teoria
dos Jogos
 Não há garantia de convergência!
• Necessidade de pesquisa prevista pelos autores
 Produz ótimos locais
• A ordem em que as redes jogam afetam o estado
estável da rede. Aplica Monte-Carlo para amenizar.
Como usar o modelo
Análise de cenários
 Responder questões de “e se”
Propriedades do estado estável
 Topologia
• Conectividade, fluxo do tráfego, número de pares,
provedores, distância do caminho entre duas redes
 Específico de rede
• Lucratividade da rede, número de consumidores,
pares, provedores
 Econômicos
• Análise da justiça na alocação dos recursos,
viabilidade econômica do sistema no geral e por
classes (LTP vs STP), nível de competição.
Resultados obtidos
 Análise dos últimos 10 anos
 Duas fases de crescimento
• Inicial de crescimento exponencial até o final de 2001
seguido por um crescimento linear
 Mesmo com a rede crescendo, o comprimento do
caminho médio mantém praticamente constante.
• Significa que a rede está ficando mais densa.
 75% dos surgimentos de enlaces estão associados
com ASes já existentes (rewiring versus growth)
 80% do encerramento de enlaces são devidos a
reconexões (rewiring).
 Europe vs North America
Dhamdhere, A. and Dovrolis, C. 2008. Ten years in the evolution of the internet ecosystem. In Proceedings of the
8th ACM SIGCOMM Conference on internet Measurement (Vouliagmeni, Greece, October 20 - 22, 2008). IMC '08.
ACM, New York, NY, 183-196. DOI= http://doi.acm.org/10.1145/1452520.1452543
Debate
É possível construir um modelo para outro
nível da Internet?





Nível de aplicação – ecosistema de aplicações
Quais são os agentes?
Qual é a função utilidade?
Como calibrar o modelo?
Como usar o modelo?
Como aproveitar esses modelos na
engenharia de sistemas?
 Serve apenas como ferramenta de simulação?