Simulação


Por Francisco Heron de Carvalho Junior


    Este trabalho foi realizado no contexto da disciplina Análise de Desempenho de Sistemas da Pós-Graduação em Ciências da Computação do Centro de Informática da Universidade Federal de Pernambuco, ministrada pela Profa. Marcília Campos.

Descrição do Trabalho

    Este trabalho consiste em realizar uma simulação de uma rede de computadores utilizando o software NS (Network Simulator), analisando estatisticamente os dados gerados na simulação. Estamos interessados especifcamente nos tempos médios de envio de pacotes entre nós. Na seção 1, apresentaremos a topologia de rede utilizada nesta simulação. Na seção 2, obteremos de arquivos externos os dados obtidos da simulação. A idéia utilizada neste trabalho foi formatar o arquivo 'out.nam', gerado pelo NS gerando um arquivo simulation, o qual foi importado pea ferramenta de banco de dados Access 2000. Dessa forma, podemos usufruir da linguagem de consulta SQL para filtrar e manipular os dados resultantes da simulação. Os dados úteis são então analisados graficamente e estatisticamente pelo software Mathematica, com o qual foi gerado este documento. Na seção 3, construímos gráficos que nos dão uma idéia do comportamento da simulação e nos permitem identificar os transientes da simulação. Na seção 4, fazemos alguns cálculos estatísticos relacionados a intervalos de confiança, cálculos de média e desvio padrão e determinação do tamanho da amostra.

Carregando Pacotes Necessários do Mathematica

[Graphics:Images/index_gr_1.gif]


1. Topologia de Rede Utilizada nesta Simulação

[Graphics:Images/index_gr_2.gif]

    O diagrama apresenta a topologia utilizada na constituição da rede de processos da simulação. Nele, identificamos tamém as velocidades e atrasos do links, expressos respectivamete em bps (bits por segundo) e ms (milisegundos), bem como o tipo, tamanho dos pacotes e intervalo entre pacotes dos nós fontes (nós 1, 2 e 3), os quais deverão enviar dados para o nó 7.
    Para chegar ao Nó 7, os dados provenientes dos nós fonte podem seguir três caminhos a partir do nó intermediário 3. Convencionamos, neste trabalho, chamar de [Graphics:Images/index_gr_3.gif] o caminho que passa pelo Nó 4, [Graphics:Images/index_gr_4.gif] o caminho que passa pelo nó 5 e [Graphics:Images/index_gr_5.gif] o caminho que passa pelo nó 6. A média de velocidade de envio dos pacotes varia muito em função do caminho que o pacote chega. Por isso, buscaremos analisar os dados separadamente para cada caminho.

Programa TCL


    A seguir, apresentamos o programa TCL correspondente a simulação, o qual é submetido ao NS.

[Graphics:Images/index_gr_6.gif]

Tempos de Inicialização e Finalização das Fontes CBR


    Configurando, para uso do Mathematica os tempos em que os nós fonte iniciam e terminam de enviar os pacotes.

[Graphics:Images/index_gr_7.gif]


2. Configurando Dados da Simulação


Nesta seção, são lidos os dados da simulação. O símbolo L[fonte, caminho, destino] corresponde a una lista de elementos do tipo {nº do pacote, tempo de envio}. Assim temos o tempo de envio de todos os pacotes, cujos respectivos números são nº do pacote, enviados com sucesso entre os nós fonte e destino passando pelo nó caminho. O motivo de separarmos os pacotes pelo caminho que eles seguiram é que as médias dos tempos variam em função do caminho, devido as diferentes configurações de cada um deles. No total, tempos nove caminhos e analisaremos o tempo de envio dos pacotes através de  cada um deles.
Como forma de permitir uma melhor análise do comportamento da simulação, estudaremos também o número de pacotes descartados e o tempo de espera dos pacotes na fila. Veremos que esses dados são importantes para entender o comportamento da simulação.

Tempos Médios de Envio (por caminho)

[Graphics:Images/index_gr_8.gif]
[Graphics:Images/index_gr_9.gif]
[Graphics:Images/index_gr_10.gif]
[Graphics:Images/index_gr_11.gif]
[Graphics:Images/index_gr_12.gif]
[Graphics:Images/index_gr_13.gif]
[Graphics:Images/index_gr_14.gif]
[Graphics:Images/index_gr_15.gif]
[Graphics:Images/index_gr_16.gif]

Pacotes Descartados (por caminho e total)

[Graphics:Images/index_gr_17.gif]
[Graphics:Images/index_gr_18.gif]
[Graphics:Images/index_gr_19.gif]

Tempo Médio de Espera nas Filas (por caminho)

[Graphics:Images/index_gr_20.gif]
[Graphics:Images/index_gr_21.gif]
[Graphics:Images/index_gr_22.gif]


3. Análise Gráfica e Pragmática da Simulação


Nesta seção, construíremos gráficos para analisar o comportamento da simulação. Inicialmente, analisaremos os tempos de envio dos pacotes através de cada caminho possível. Dessa forma teremos um gráfico de linha da forma Nº do pacote X Tempo de Envio. Nos primeiros nove gráficos, apresentaremos separadamente os tempos de envio dos pacotes através de cada caminho distinto, enquanto no último juntamos esses gráficos em um gráfico só, para melhor efeito comparativo visual. Observe que, com as fontes são do tipo CBR (dados transmitidos constantemente), podemos utilizar o número dos pacotes como tempo.
Os dados relativos ao descarte de pacotes e tempo de espera nas filas por cada pacote, em cada caminho, serão apresentados de forma coneveniente, pois o comportamento do tempo médio de envio varia em função desses parâmetros. Nos ajudarão, por exemplo, a identificar transientes de forma mais precisa


Configurando o Estilo dos Gráficos

[Graphics:Images/index_gr_23.gif]


Marcadores

    Os marcadores serão usados para mostrar no gráficos os momentos em que os nós CBR iniciam e páram de enviar dados e o momento a partir dos quais pacotes começam a ser descartados. Como marcador de Tempo utiliza-se o número do pacote.

[Graphics:Images/index_gr_24.gif]
[Graphics:Images/index_gr_25.gif]
[Graphics:Images/index_gr_26.gif]
[Graphics:Images/index_gr_27.gif]
[Graphics:Images/index_gr_28.gif]
[Graphics:Images/index_gr_29.gif]


Plotando os Gráficos


Tempo de Envio dos Pacotes de Cada Fonte até o Nó 7


    Os gráficos apresentados a seguir apresentam a evolução do tempo de envio dos pacotes a medida que a simulação prossegue. Temos então no eixo X o número do pacote e no eixo Y o tempo que o pacote levou para ser enviado do nó fonte ao nó destino. Verificamos que, devido as diferentes caractrísticas dos links e nós fontes, o tempo médio varia de acordo com o nó a partir do qual os pacotes foram enviados e o caminho que ele percorreu a partir do [Graphics:Images/index_gr_30.gif] (Caminhos 1, 2 ou 3). Assim, analisaremos a média separadamente para cada fonte e por cada caminho. Como temos três fontes e três caminhos, ao todo teremos nove gráficos.
    Verificamos que,  principalmente  no caso dos pacotes que seguem pelos caminhos 1 e 2,  o comportamento  estabiliza-se a partir do momento que começam a haver perdade de pacote. Até esse ponto o tempo de envio aumenta. Obervamos que pacotes começam a ser perdidos algum tempo após a terceira fonte ser iniciada,  quando o crescimento das filas de espera que surgem nos caminhos 1 e 2 torna-se mais acentuado.Não há formação de filas em nenhum link do caminho 3, por isso não há perda de pacotes por esse caminho e o tempo de envio mantém-se estável desde o início da simulação..
    Baseados nessas informações, concluímos que só devem ser utilizados para estudo estatístico da média dos tempos de envio os pacotes enviados a partir do tempo onde o primeiro pacote é descartado, eliminando o estado transiente. Após esse estado a variação do tempo de envio ao longo do tempo se estabiliza,aproximando-se de nula.
    Tudo o que foi dito aqui pode ser verificado nos gráficos que se seguem. Para facilitar a visualização e permitir ao leitor situar-se no tempo da simulação, mostramos nos gráficos os pontos no tempo onde cada nó fonte inicia e finaliza, bem como o tempo em que o primeiro pacote é descartado. Observe que utilzamos o número do pacote como escala de tempo, uma vez que sabemos que os pacotes são enviados numa função constante, por serem do tipo CBR.

[Graphics:Images/index_gr_31.gif]

[Graphics:Images/index_gr_32.gif]
[Graphics:Images/index_gr_43.gif]
[Graphics:Images/index_gr_44.gif]

[Graphics:Images/index_gr_45.gif]

[Graphics:Images/index_gr_46.gif]

[Graphics:Images/index_gr_47.gif]

[Graphics:Images/index_gr_48.gif]


Pacotes Descartados


    Aqui analisamos os descartes de pacote. No gráfico apresentamos para cada caminho o tempo em que cada pacote foi descartado. Observe que função aproxima-se de uma função linear, o que significa que a taxa de descarte de pacotes é constante. Este fato é esperado, tendo em vista que as fontes são do tipo CBR. Observe que os descartes só iniciam algum tempo após a inicialização da terceira fonte.

[Graphics:Images/index_gr_49.gif]
[Graphics:Images/index_gr_55.gif]
[Graphics:Images/index_gr_56.gif]

[Graphics:Images/index_gr_57.gif]

[Graphics:Images/index_gr_58.gif]


Espera na fila


    Assim como o tempo de envio de pacotes, analisamos o tempo de esoera dos pacotes nas filas de espera, de acordo com o caminho (1,2 ou 3). Observe que o tempo de espera estabiliza-se também a partir do primeiro descarte, o que é de se esperar, uma vez que o tamanho das filas se estabilizam no valor máximo.

[Graphics:Images/index_gr_59.gif]
[Graphics:Images/index_gr_65.gif]
[Graphics:Images/index_gr_66.gif]

[Graphics:Images/index_gr_67.gif]

[Graphics:Images/index_gr_68.gif]

[Graphics:Images/index_gr_69.gif]

[Graphics:Images/index_gr_70.gif]


4. Analisando Estatisticamente os Dados da Simulação


    A seguir, fazemos algumas análise estatísticas dos dados da simulação. Inicialmente, construímos  histogramas para os tempos de envio e número de descartes de pacotes, para observar como os dados se distribuem. A seguir calculamos alguns intervalos de confiança para as médias dos tempos de envio e calculamos o tamanho da amostra para melhorar a precisão da simulação.
    Calcularemos em cima do estado não transiente., que vai do tempo em que o primeiro pacote é descartado até o tempo em que a primeira fonte pára de transmitir . Este último convecionamos o tempo no qual o  pacote2800 foi enviado.


Construindo Histograma para Tempos de Envio


    Nesta seção, construiremos histogramas para os tempos de envio dos pacotes por cada caminho. O objetivo é conhecer como se distribuem os tempos de envio.

Definições

[Graphics:Images/index_gr_71.gif]
[Graphics:Images/index_gr_72.gif]
[Graphics:Images/index_gr_73.gif]

1º Caso:  Pacotes que partem do [Graphics:Images/index_gr_74.gif] e seguem o [Graphics:Images/index_gr_75.gif]

[Graphics:Images/index_gr_76.gif]

[Graphics:Images/index_gr_77.gif]

[Graphics:Images/index_gr_78.gif]

2º Caso:  Pacotes que partem do [Graphics:Images/index_gr_79.gif] e seguem o [Graphics:Images/index_gr_80.gif]

[Graphics:Images/index_gr_81.gif]

[Graphics:Images/index_gr_82.gif]

[Graphics:Images/index_gr_83.gif]

3º Caso:  Pacotes que partem do [Graphics:Images/index_gr_84.gif] e seguem o [Graphics:Images/index_gr_85.gif]

[Graphics:Images/index_gr_86.gif]

[Graphics:Images/index_gr_87.gif]

[Graphics:Images/index_gr_88.gif]

4º Caso:  Pacotes que partem do [Graphics:Images/index_gr_89.gif] e seguem o [Graphics:Images/index_gr_90.gif]

[Graphics:Images/index_gr_91.gif]

[Graphics:Images/index_gr_92.gif]

[Graphics:Images/index_gr_93.gif]

5º Caso:  Pacotes que partem do [Graphics:Images/index_gr_94.gif] e seguem o [Graphics:Images/index_gr_95.gif]

[Graphics:Images/index_gr_96.gif]

[Graphics:Images/index_gr_97.gif]

[Graphics:Images/index_gr_98.gif]

6º Caso:  Pacotes que partem do [Graphics:Images/index_gr_99.gif] e seguem o [Graphics:Images/index_gr_100.gif]

[Graphics:Images/index_gr_101.gif]

[Graphics:Images/index_gr_102.gif]

[Graphics:Images/index_gr_103.gif]

7º Caso:  Pacotes que partem do [Graphics:Images/index_gr_104.gif] e seguem o [Graphics:Images/index_gr_105.gif]

[Graphics:Images/index_gr_106.gif]

[Graphics:Images/index_gr_107.gif]

[Graphics:Images/index_gr_108.gif]

8º Caso:  Pacotes que partem do [Graphics:Images/index_gr_109.gif] e seguem o [Graphics:Images/index_gr_110.gif]

[Graphics:Images/index_gr_111.gif]

[Graphics:Images/index_gr_112.gif]

[Graphics:Images/index_gr_113.gif]

1º Caso:  Pacotes que partem do [Graphics:Images/index_gr_114.gif] e seguem o [Graphics:Images/index_gr_115.gif]

[Graphics:Images/index_gr_116.gif]

[Graphics:Images/index_gr_117.gif]

[Graphics:Images/index_gr_118.gif]


Construido Histograma para Número de Pacotes Descartados (por caminho)


Aqui apresentamos histogramaas para a quantidade de pacotes perdidos para cada caimnho.

[Graphics:Images/index_gr_119.gif]
[Graphics:Images/index_gr_120.gif]
[Graphics:Images/index_gr_121.gif]
[Graphics:Images/index_gr_122.gif]
[Graphics:Images/index_gr_123.gif]

[Graphics:Images/index_gr_124.gif]

[Graphics:Images/index_gr_125.gif]
[Graphics:Images/index_gr_126.gif]
[Graphics:Images/index_gr_127.gif]
[Graphics:Images/index_gr_128.gif]

[Graphics:Images/index_gr_129.gif]

[Graphics:Images/index_gr_130.gif]
[Graphics:Images/index_gr_131.gif]
[Graphics:Images/index_gr_132.gif]
[Graphics:Images/index_gr_133.gif]

[Graphics:Images/index_gr_134.gif]

[Graphics:Images/index_gr_135.gif]


Construindo Intervalos de Confiança para os Tempos Médios de Envio


    Nesta seção, construiremos intervalos de confiança para os tempos médios de envio dos pacotes. Como dito anteriormente, estamos interessados na parte da simulação após a fase transiente. Assumimos que esta fase inicia após o primeiro descarte de pacote, correspondente ao descarte do pacote 1181.

Definições Úteis

[Graphics:Images/index_gr_136.gif]
Cálculo da variância de uma lista de dados (amostra)
[Graphics:Images/index_gr_137.gif]
Intervalo de Confiança para Variânia desconhecida
[Graphics:Images/index_gr_138.gif]
Número de amostras necessárias para o caso de variância desconhecida
[Graphics:Images/index_gr_139.gif]

Intervalos de Confiança

OBS: Os intervalos serão calculados de duas formas: utilizandoa definição das fórmulas descritas acima e utilizando a função MeanCI provida pelo Mathematica, para validação.

Nível de Significância
[Graphics:Images/index_gr_140.gif]
1º Caso: Pacotes que partem do [Graphics:Images/index_gr_141.gif] e seguem o [Graphics:Images/index_gr_142.gif]
[Graphics:Images/index_gr_143.gif]
[Graphics:Images/index_gr_144.gif]
[Graphics:Images/index_gr_145.gif]
[Graphics:Images/index_gr_146.gif]
[Graphics:Images/index_gr_147.gif]
[Graphics:Images/index_gr_148.gif]
[Graphics:Images/index_gr_149.gif]
[Graphics:Images/index_gr_150.gif]
2º Caso: Pacotes que partem do [Graphics:Images/index_gr_151.gif] e seguem o [Graphics:Images/index_gr_152.gif]
[Graphics:Images/index_gr_153.gif]
[Graphics:Images/index_gr_154.gif]
[Graphics:Images/index_gr_155.gif]
[Graphics:Images/index_gr_156.gif]
[Graphics:Images/index_gr_157.gif]
[Graphics:Images/index_gr_158.gif]
[Graphics:Images/index_gr_159.gif]
[Graphics:Images/index_gr_160.gif]
3º Caso: Pacotes que partem do [Graphics:Images/index_gr_161.gif] e seguem o [Graphics:Images/index_gr_162.gif]
[Graphics:Images/index_gr_163.gif]
[Graphics:Images/index_gr_164.gif]
[Graphics:Images/index_gr_165.gif]
[Graphics:Images/index_gr_166.gif]
[Graphics:Images/index_gr_167.gif]
[Graphics:Images/index_gr_168.gif]
[Graphics:Images/index_gr_169.gif]
[Graphics:Images/index_gr_170.gif]
4º Caso: Pacotes que partem do [Graphics:Images/index_gr_171.gif] e seguem o [Graphics:Images/index_gr_172.gif]
[Graphics:Images/index_gr_173.gif]
[Graphics:Images/index_gr_174.gif]
[Graphics:Images/index_gr_175.gif]
[Graphics:Images/index_gr_176.gif]
[Graphics:Images/index_gr_177.gif]
[Graphics:Images/index_gr_178.gif]
[Graphics:Images/index_gr_179.gif]
[Graphics:Images/index_gr_180.gif]
5º Caso: Pacotes que partem do [Graphics:Images/index_gr_181.gif] e seguem o [Graphics:Images/index_gr_182.gif]
[Graphics:Images/index_gr_183.gif]
[Graphics:Images/index_gr_184.gif]
[Graphics:Images/index_gr_185.gif]
[Graphics:Images/index_gr_186.gif]
[Graphics:Images/index_gr_187.gif]
[Graphics:Images/index_gr_188.gif]
[Graphics:Images/index_gr_189.gif]
[Graphics:Images/index_gr_190.gif]
6º Caso: Pacotes que partem do [Graphics:Images/index_gr_191.gif] e seguem o [Graphics:Images/index_gr_192.gif]
[Graphics:Images/index_gr_193.gif]
[Graphics:Images/index_gr_194.gif]
[Graphics:Images/index_gr_195.gif]
[Graphics:Images/index_gr_196.gif]
[Graphics:Images/index_gr_197.gif]
[Graphics:Images/index_gr_198.gif]
[Graphics:Images/index_gr_199.gif]
[Graphics:Images/index_gr_200.gif]
7º Caso: Pacotes que partem do [Graphics:Images/index_gr_201.gif] e seguem o [Graphics:Images/index_gr_202.gif]
[Graphics:Images/index_gr_203.gif]
[Graphics:Images/index_gr_204.gif]
[Graphics:Images/index_gr_205.gif]
[Graphics:Images/index_gr_206.gif]
[Graphics:Images/index_gr_207.gif]
[Graphics:Images/index_gr_208.gif]
[Graphics:Images/index_gr_209.gif]
[Graphics:Images/index_gr_210.gif]
8º Caso: Pacotes que partem do [Graphics:Images/index_gr_211.gif] e seguem o [Graphics:Images/index_gr_212.gif]
[Graphics:Images/index_gr_213.gif]
[Graphics:Images/index_gr_214.gif]
[Graphics:Images/index_gr_215.gif]
[Graphics:Images/index_gr_216.gif]
[Graphics:Images/index_gr_217.gif]
[Graphics:Images/index_gr_218.gif]
[Graphics:Images/index_gr_219.gif]
[Graphics:Images/index_gr_220.gif]
9º Caso: Pacotes que partem do [Graphics:Images/index_gr_221.gif] e seguem o [Graphics:Images/index_gr_222.gif]
[Graphics:Images/index_gr_223.gif]
[Graphics:Images/index_gr_224.gif]
[Graphics:Images/index_gr_225.gif]
[Graphics:Images/index_gr_226.gif]
[Graphics:Images/index_gr_227.gif]
[Graphics:Images/index_gr_228.gif]
[Graphics:Images/index_gr_229.gif]
[Graphics:Images/index_gr_230.gif]
10º Caso: Todos os Pacotes (qualquer origem e por qualquer caminho)
[Graphics:Images/index_gr_231.gif]
[Graphics:Images/index_gr_232.gif]
[Graphics:Images/index_gr_233.gif]
[Graphics:Images/index_gr_234.gif]
[Graphics:Images/index_gr_235.gif]
[Graphics:Images/index_gr_236.gif]
[Graphics:Images/index_gr_237.gif]

Calculando Tamanho da Amostra

1º Caso: Pacotes que partem do [Graphics:Images/index_gr_238.gif] e seguem o [Graphics:Images/index_gr_239.gif]
Erro pretendido: 0.001
[Graphics:Images/index_gr_240.gif]
[Graphics:Images/index_gr_241.gif]
[Graphics:Images/index_gr_242.gif]
2º Caso: Pacotes que partem do [Graphics:Images/index_gr_243.gif] e seguem o [Graphics:Images/index_gr_244.gif]
Erro pretendido: 0.001
[Graphics:Images/index_gr_245.gif]
[Graphics:Images/index_gr_246.gif]
[Graphics:Images/index_gr_247.gif]
3º Caso: Pacotes que partem do [Graphics:Images/index_gr_248.gif] e seguem o [Graphics:Images/index_gr_249.gif]
Erro pretendido: 0.0002
[Graphics:Images/index_gr_250.gif]
[Graphics:Images/index_gr_251.gif]
[Graphics:Images/index_gr_252.gif]
3º Caso:  Pacotes que partem do [Graphics:Images/index_gr_253.gif] e seguem qualquer caminho
Erro pretendido: 0.003
[Graphics:Images/index_gr_254.gif]
[Graphics:Images/index_gr_255.gif]
[Graphics:Images/index_gr_256.gif]


Converted by Mathematica      July 27, 2000