Uma Heurística Aleatória com Busca Adaptativa

Transcrição

Anais do XIX Workshop de Gerência e Operação de Redes e Serviços– WGRS 2014
Dependabilidade na Alocação de Recursos em Redes Virtuais:
Uma Heurística Aleatória com Busca Adaptativa
Marcelo Santos, Matheus Santana, Djamel Sadok, Stênio Fernandes
Centro de Informática – Universidade Federal de Pernambuco (UFPE)
Recife – PE – Brasil
{mabs, embs, jamel, sflf}@cin.ufpe.br
Abstract. Network Virtualization has become a central matter for the Future
Internet. Nevertheless, mapping virtual networks on the top of physical
infrastructure topology represents a NP-Hard problem due to its numerous
combinations and many node and link allocation constraints. Virtualized
structures are as failure-prone as its underlying physical infrastructure.
Hence, dependability attributes constitute relevant metrics for virtual network
allocation decision. This work proposes and evaluates a dynamic and random
networks allocation heuristic that takes into account of nodes and links
capacity attributes maximizing availability. Results show that the proposed
heuristic achieves an average availability of 95% while others algorithm
allocation techniques achieve an average of 60% for same dependability
metric.
Resumo. Virtualização de redes vem sendo um dos pilares da Internet do
Futuro. No entanto, mapear redes virtuais em uma topologia física é um
problema NP-difícil devido ao grande número de combinações e às diversas
restrições envolvidas na alocação de nós e enlaces virtuais. Falhas são
inerentes a estas estruturas virtualizadas, uma vez que a infraestrutura física é
propensa a falhas. Portanto, atributos de dependabilidade são importantes
para a decisão de alocação de uma rede virtual. Assim, este trabalho propõe e
avalia uma heurística aleatória adaptativa para alocação de redes virtuais
levando em consideração características de capacidade dos nós e enlaces
juntamente com atributos de dependabilidade buscando maximizar a
disponibilidade. Os resultados mostram que a heurística proposta alcança
uma disponibilidade média nas requisições de 95% contra 60% nas outras
estratégias.
1. Introdução
Redes Virtuais têm recebido grande atenção da comunidade de pesquisa nos últimos
anos. Tratada como umas das tecnologias para a Internet do Futuro, possibilita um meio
de avaliar novos protocolos e serviços figurando como uma importante tecnologia para
superar a barreira da ossificação da Internet. Uma de suas características chave é a
dinamicidade. Redes virtuais permitem a operadores de redes terem negociação em
tempo real sobre uma variedade de serviços entre seus usuários, operadores de serviços
virtuais (Virtual Network Operators -VNO) e provedores de redes virtuais (Virtual
Network Providers - VNP) [Schaffrath et al. (2009)].
As estratégias de gerenciamento de rede dependem de mecanismos de alocação
dinâmica dos recursos para a alocação das redes virtuais de forma eficiente e com alto
47
grau de desempenho. Para este fim, uma série de heurísticas foram propostas na
literatura [Zhu et al. (2006)] [Guo et al. (2011)] [Zhou et al. (2010)] [Chowdhury et al.
(2012)] para alcançar utilização eficiente dos recursos dos elementos de rede, como
enlaces, nós e roteadores, uma vez que a alocação ótima não é possível devido à
natureza NP-Difícil do problema.
Embora a alocação eficiente dos recursos de rede seja uma questão fundamental
a ser abordada, há ainda um ponto importante a ser discutido, originado pelo seguinte
questionamento: quais são os riscos associados a uma determinada rede virtual? É
normal que os riscos sejam inerentes às infraestruturas físicas utilizadas (nós e enlaces),
uma vez que os componentes de rede física subjacente são propensos a falhas. Podemos
citar, por exemplo, o recente acidente na nuvem da Amazon como um alerta de que
falhas técnicas ou de intervenção humana é uma realidade e não devem ser
negligenciadas [Gill et al. (2011)] [Benson et al. (2010)]. A avaliação e análise de risco
dos atributos de dependabilidade são de suma importância, uma vez que se pode
quantificar e dar medidas concretas para serem usadas como fator de decisão no
gerenciamento e controle da rede. Em poucas palavras, a dependabilidade pode ser vista
como um conceito geral que engloba a disponibilidade, confiabilidade, segurança,
confidencialidade, integridade e capacidade de manutenção [Maciel et al. (2011)]
[Laprie et al. 1985]. Dessa forma, expandido outros trabalhos, este artigo propõe e
avalia uma heurística aleatória adaptativa para alocação de redes virtuais levando em
consideração capacidades de nós e enlaces juntamente com atributos de
dependabilidade.
Através da utilização da modelagem baseada em Diagrama de Blocos de
Confiabilidade (RBD) [Guimarães et al. (2011)], nós fornecemos uma heurística para o
problema de mapeamento de redes virtuais (Virtual Networking Mapping Problem VNMP) que leva em consideração os riscos na virtualização de rede por meio de
métricas de dependabilidade. As principais Contribuições deste trabalho são duas: (i)
propomos uma heurística para VNMP que leva em consideração dependabilidade para
tomada de decisão da alocação; e (ii) uma base metodológica que permite o
desenvolvimento da análise de riscos na alocação de redes virtuais.
O restante do artigo é organizado da maneira descrita a seguir. Na seção 2 são
citados os trabalhos relacionados. Na seção 3 há uma breve discussão sobre conceitos de
Dependabilidade. Na seção 4 é dada uma definição sobre VNMP e é exibida a
modelagem do problema. A seção 5 apresenta a heurística desenvolvida. A seção 6
discute a metodologia. Na seção 7 são apresentados os resultados. Na seção 8
discutimos os resultados. Apresentamos as conclusões na seção 9. Por fim são citadas as
referências.
2. Trabalhos Relacionados
Em Sun et al. (2010) é proposto um modelo de dependabilidade para ambientes de
computação em nuvem, usando virtualização de nível de sistema (CDSV) que adota
várias métricas quantitativas para avaliar a dependabilidade. O foco é uma análise sobre
aspectos de segurança e a avaliação do impacto das propriedades de dependabilidade
dos componentes virtualizados em nível de sistema (por exemplo, máquinas virtuais,
hypervisor e afins). Da mesma forma, Saripalli et al. (2010) apresentam um impacto
quantitativo e uma metodologia de avaliação de risco a fim de avaliar riscos de
48
segurança em ambientes de computação em nuvem. Esses trabalhos dão uma visão de
como abordar a avaliação da dependabilidade em cenários com virtualização, porém
possuem um escopo mais simples quando comparados com um cenário de redes
virtualizadas.
Em Fernandes et al. (2012) é proposto um método para análise da
dependabilidade em ambientes de redes virtualizadas com o uso de diagrama de bloco
de confiabilidade (RBD) e Redes de Petri Estocásticas (SPN). Este é o primeiro trabalho
a analisar o impacto da dependabilidade em ambientes dinâmicos de virtualização de
redes. No entanto, este trabalho utiliza como entrada para análise da dependabilidade o
resultado da heurística R-ViNE [Chowdhury et al. (2012)]. É importante destacar que a
heurística R-ViNE não leva em consideração dependabilidade para realizar a alocação
de requisições virtuais. Sendo assim, a relevância se dá pelo vislumbre de uma primeira
avaliação sobre os aspectos de dependabilidade num cenário de redes virtualizadas.
O trabalho mais semelhante encontrado na literatura é realizado por Lira et al.
(2013). Neste trabalho é apresentada uma heurística baseada no GRASP para alocação
de redes virtuais considerando dependabilidade. No entanto, a meta-heurística utilizada
não tem como objetivo a maximização da dependabilidade. A dependabilidade
apresenta-se apenas como uma restrição informada pelo usuário. Ou seja, o objetivo da
alocação é minimizar o custo estabelecido pelos autores que não leva em consideração
atributos de dependabilidade na sua função objetivo, não sendo assim justa uma
comparação com a heurística proposta. Além disso, o trabalho apresenta resultados
preliminares, pois não apresentam dados em relação à carga de recursos físicos
utilizados e à taxa de aceitação das requisições. Dessa forma podemos afirmar que os
trabalhos embrionários de Fernandes et al (2012) e Lira et al (2013) serviram como
motivação para uma análise mais extensa e aprofundada apresentada neste artigo.
Com relação às heurísticas de alocação de redes virtuais, focamos - nos
próximos parágrafos - em dois trabalhos que foram utilizados para comparação de
nossos resultados. Deve-se notar que os trabalhos abaixo não levam em consideração
características de falha em suas soluções de mapeamento de redes virtuais. No entanto,
esta comparação é importante para mensurar o quanto a dependabilidade varia quando é
negligenciada durante o processo de alocação.
Zhu e Ammar (2006) propõem um algoritmo ganancioso cujo objetivo é
balancear a carga sobre os enlaces e nós físicos. No entanto, sua abordagem não
considera aspectos de capacidade, o balanceamento é realizado levando em
consideração apenas a quantidade de nós e enlaces virtuais mapeados sobre a rede
substrato. A ideia principal da estratégia utilizada é mapear um novo nó virtual em um
nó físico considerando a quantidade de nós virtuais nesse nó físico e a carga nos nós e
enlaces físicos vizinhos.
Em Chowdhury et al. (2012) o problema de alocação de redes virtuais é
modelado em função dos custos de receita do servidor com restrições de nós, enlaces e
geo-localização. O problema resultante é NP-difícil e, para resolvê-lo, é realizada uma
redução para um problema de otimização inteira mista e posteriormente há o
relaxamento sobre as restrições, culminando em dois algoritmos de aproximação: DViNE e R-ViNE. D-ViNE possui uma abordagem determinística para mapeamento dos
nós baseada em uma solução linear relaxada. R-ViNE é similar, mas usa um
mapeamento de nós aleatório. Ambos os algoritmos possuem versões em que o enlace
49
virtual é mapeado através do menor caminho ou do particionamento do fluxo virtual em
mais de um caminho físico. É importante destacar que neste trabalho, os autores não
levam em consideração atraso dos enlaces como restrição de alocação. Na prática, tais
restrições são importantes para requisitos de aplicações que executam, por exemplo, na
Internet. Além disso, assume-se que uma mesma máquina física não pode receber mais
de uma máquina virtual de uma mesma requisição, tornando a busca por uma solução de
mapeamento mais difícil. Outra desvantagem é o fato de algumas variações do D-ViNE
e R-ViNE realizarem divisão de caminhos virtuais (mapeamento de um caminho virtual
em dois ou mais caminhos físicos). Na prática isso é difícil de ser realizado, não sendo
comum sua adoção. Por isso, decidimos comparar apenas a abordagem que utiliza a
alocação de enlaces pelo menor caminho chamada D-ViNE-SP.
Este levantamento não tem o objetivo de ser extensivo, dado que apenas os
artigos que consideramos mais similares ao nosso trabalho são citados. Para uma
extensa literatura sobre o problema de alocação de redes virtuais pode-se destacar o
trabalho de Fischer et al. (2013). É importante ressaltar que os autores desconhecem
qualquer trabalho que leve em consideração a dependabilidade como fator durante uma
alocação de uma rede virtual. Desta forma, não há trabalhos que possam ser analisados
diretamente com a heurística proposta, por isso, como no trabalho de análise de
dependabilidade realizado por Fernandes et al. (2012), comparamos nosso trabalho com
heurísticas bem conhecidas na literatura.
3. Dependabilidade
A dependabilidade de um sistema, de maneira simplificada, pode ser entendida como a
sua capacidade de fornecer um conjunto de serviços de forma justificadamente
confiável. Trata-se, em termos mais abrangentes, de um conceito guarda-chuva que
contempla vários atributos como, por exemplo, tolerância a falhas, disponibilidade e
confiabilidade [Laprie (1985)] [Ebeling (1997)]. Métricas de dependabilidade podem
ser calculadas por modelos combinatórios, como os Diagramas de Bloco de
Confiabilidade (Reliability Block Diagram - RBD) e árvores de falha ou por meio de
modelos estocásticos baseados em estado - cadeias de Markov (Markov Chains) e redes
estocásticas de Petri (Stochastics Petri Nets - SPN), por exemplo [Maciel et al. 2011]
[Nicol et al. 2004]. Para uma melhor compreensão dos modelos de confiabilidade podese utilizar as referências [Maciel et al. 2011] e [Nicol et al. 2004].
Uma das principais características utilizadas para a avaliação da dependabilidade
de sistemas é a disponibilidade. A dependabilidade de um sistema pode ser calculada com os supracitados modelos combinatórios, por exemplo - através do cálculo das
disponibilidades dos dispositivos que o compõem. A maneira de se obter a
disponibilidade (A) de um determinado dispositivo é lançar mão das suas características
de tempo até a ocorrência de falha (TTF) e tempo até o reparo de uma falha ocorrida
(TTR). Considerando que essas medidas exatas não estão disponíveis, suas médias são
utilizadas. Valendo-se dos valores de tempo médio para falha (MTTF) e tempo médio
de reparo (MTTR) de um dispositivo, a disponibilidade de estado estacionário (A) pode
ser representada como:
(1)
50
O MTTF pode ser computado considerando a confiabilidade do sistema (R)
como segue:
∫
( )
∫
( )
(2)
Este trabalho adota a disponibilidade como métrica de dependabilidade,
modelada por RBD. Diagramas de bloco de confiabilidade fornecem método para
avaliação de disponibilidade ou confiabilidade através do mapeamento de sistemas (e
seus subsistemas / dispositivos) em blocos que se configuram em série ou paralelo.
Depois de modelado o sistema, a avaliação é feita de acordo com as regras de cálculo
para cada uma das possíveis configurações. Para melhor entendimento da modelagem
com diagramas de bloco de confiabilidade, a referência [Trivedi et al. (2008)] pode ser
consultada.
Neste trabalho o modelo RBD utilizado tem o objetivo de calcular a
dependabilidade de uma requisição virtual alocada sobre uma topologia física. Como
explicado na próxima seção, os blocos que modelam uma requisição são dispostos
totalmente em série, sendo a dependabilidade de uma requisição virtual calculada
através da multiplicação da disponibilidade de todos os nós e enlaces físicos utilizados
no mapeamento da requisição virtual.
4. VNMP e Modelagem do Problema
Com o intuito de deixar o problema atacado neste artigo bem definido, vamos nesta
seção descrever e caracterizar formalmente o problema e sua respectiva modelagem
matemática através da extensão do trabalho de Infuhr et al. (2013). O problema de
alocação de redes virtuais é conhecido na literatura como VNMP (Virtual Network
Mapping Problem). Algumas informações são necessárias para especificar um VNMP:
rede de substrato com seus recursos disponíveis e redes virtuais que precisam ser
alocadas de acordo com seus requisitos e restrições específicas sobre os recursos
virtuais e físicos.
Para modelar a rede de substrato utilizamos um grafo não direcionado com
(
) onde representa o conjunto de nós e o conjunto de enlaces. Cada nó
da rede substrato tem uma capacidade de CPU
. O recurso de CPU
disponível é utilizado por um nó virtual que é mapeado para um nó físico . Enlaces
da rede substrato tem uma capacidade de banda
e um atraso
.
Outro grafo não direcionado
(
) modela a rede virtual. Cada nó
requer uma capacidade de CPU
. Cada enlace virtual
tem um requisito
de banda
e um atraso máximo permitido
. A soma do atraso de todos
os enlaces físicos para qual um enlace virtual foi mapeado não pode exceder . A
capacidade de banda
de cada enlace físico deve ser respeitada, dessa forma a banda
exigida por cada enlace virtual mapeado em um mesmo enlace físico
não deve
ultrapassar
Por fim, a soma da capacidade requerida de CPU
de cada máquina
virtual alocada em um nó não pode exceder a capacidade deste nó físico.
Os nós físicos da rede substrato em que um nó virtual pode ser alocado são
definidos pelo conjunto
, cujo enlace virtual
(
), onde
são nós
virtuais é definido por ( )
e ()
,
que representam
respectivamente fonte e destino. Dois componentes são então requeridos para solucionar
51
( ))
o problema VNMP: Um mapeamento
tal que (
e um
caminho na rede substrato
iniciando em ( ( )) até ( ( )) para cada
cujo o atraso não exceda .
Em nosso caso, o objetivo é maximizar a disponibilidade da requisição virtual a
ser alocada. A disponibilidade do nó físico é dada por
para todo
. Os
enlaces da rede substrato
utilizados no mapeamento de um enlace virtual
possuem disponibilidade
. Com base no modelo RBD definido para modelar a
disponibilidade das requisições virtuais, a disponibilidade de cada requisição é dada
pela multiplicação da disponibilidade de cada nó e enlace físico usados no mapeamento
da rede virtual. Assim, a função objetivo é maximizar a disponibilidade das requisições
virtuais.
5.
Heurística
Esta seção descreve a principal contribuição deste trabalho: uma heurística aleatória
adaptativa (intitulada HRA) utilizada para alocação de redes virtuais em uma topologia
física. A heurística proposta é fortemente inspirada na metaheurística conhecida como
GRASP (Greedy Randomized Adaptive Search Procedure) [Infuhr et al. (2013)]. No
entanto, difere em alguma de suas características, por exemplo, não apresenta nenhum
método de busca local. Sua função objetivo é maximizar a dependabilidade de cada
requisição no momento de sua alocação. A descrição por meio de um pseudocódigo é
importante para que outros pesquisadores consigam replicar os experimentos realizados.
Notem que, devido a questões de espaço, a representação aqui fornecida trata de uma
simplificação do algoritmo implementado de fato.
O seu funcionamento geral é dado pelo algoritmo da Figura 1:
Entrada: SN = grafo da rede substrato,
VNS = coleção de grafos de requisições virtuais,
LIMITE_TENTATIVAS = número inteiro que limita a quantidade de iterações
possíveis quando não se encontra solução
1. início
2. para i ← 1, .., |VNS| faça
3.
allocated ← false
4.
tentativas ← 0
5.
enquanto (tentativas < LIMITE_TENTATIVAS) e (allocated == false) faça
6.
allocated ← alocar_requisição(VNS[i], SN, LIMITE_TENTATIVAS)
7.
tentativas ← tentativas + 1
8.
fim-enquanto
9.
fim-faça
10. fim
Figura 1 – Método principal
O passo-a-passo é bastante direto e deve ser autoexplicativo. Um ponto de
destaque é a chamada à subrotina alocar_requisição (Figura 1), na linha 6. Essa, por sua
vez, funciona de acordo com o seguinte algoritmo:
Entrada: VNR = grafo da requisição virtual a ser alocada, SN, LIMITE_TENTATIVAS
1 início
2.
alocado ← true
52
3. nó_virtual ← escolher_nó_aleatoriamente(VNR)
4.
alocado ← alocar_primeiro_nó(nó_virtual)
5.
se (alocado == false) faça
6.
retorne false
7.
fim-se
8. nó_virtual_base ← nó_virtual
9. nós_pendentes ← []
10. faça
11.
para i ← 1, .., |vizinhos(nó_virtual_base)| faça
12.
nó_virtual_destino ← vizinhos(nó_virtual_base)[i]
13.
alocado ← alocar_nós(nó_virtual_base, nó_virtual_destino, SN, LIMITE_TENTATIVAS)
14.
se (alocado == false) faça
15.
retorne false
16.
fim-se
17.
nós_pendentes ← adicionar_elemento(nós_pendentes, nó_virtual_destino)
18.
nós_pendentes ← remover_elemento(nós_pendentes, nó_virtual_base)
19.
nó_virtual_base ← escolher_nó_aleatoriamente(nós_pendentes)
20.
fim-faça
20. enquanto (|nós_pendentes| > 0)
21. retorne true
22. fim
Figura 2 – Método alocar_requisição
O método alocar_requisição (Figura 2) é chamado para alocação de uma
requisição específica. Ela escolhe, de maneira aleatória, um nó virtual inicial para dar
prosseguimento à alocação dos nós restantes. Após a alocação do primeiro nó virtual em
um nó físico, é realizada uma busca em largura para alocação dos nós virtuais vizinhos
(linhas 11 a 20). É importante salientar que a alocação é feita em pares pela subrotina
alocar_nós (linha 13).
O pseudocódigo da Figura 3 descreve alocar_nós, que usa uma lista de nós
físicos que podem acomodar uma possível alocação do nó virtual recebido na entrada. A
partir dessa lista é realizada uma busca adaptativa aleatória na tentativa de maximizar a
dependabilidade para o segmento da rede a ser alocado (linhas 17 a 29). Vale salientar
que, ao maximizar a disponibilidade da alocação de dois nós virtuais e seus respectivos
enlaces, estamos também maximizando a disponibilidade da requisição -- dado que a
disponibilidade total é calculada através do produto das disponibilidades de todos os
componentes. Isso se dá primacialmente devido à utilização do modelo RBD em série
para o cálculo da dependabilidade.
Entrada: nó_virtual_base, nó_virtual_destino, SN, LIMITE_TENTATIVAS
1. início
2. nó_físico_origem ← nó_físico_subjacente(nó_virtual_base)
3.
solução ← []
4.
se (está_alocado(nó_virtual_destino) == false) faça
5.
para i ← 1, .., |nós_físicos(SN)| faça
6.
nó_físico ← nós_físicos(SN)[i]
7.
se (pode_alocar(nó_físico, nó_virtual_destino)) faça
8.
ok ← checar_caminho_mais_curto(nó_físico_origem, nó_físico, nó_virtual_destino)
9.
se (ok) faça
10.
solução ← adicionar_elemento(solução, nó_físico)
11.
fim-se
53
12.
fim-se
13.
// Filtra a lista com os nós físicos que possuem a maior disponibilidade
14.
solução ← melhores_nós_físicos(solução)
15.
melhor_solução ← 0
16.
tentativas ← 0
17.
enquanto (tentativas < LIMITE_TENTATIVAS) faça
18.
nó_físico ← escolher_nó_aleatoriamente(solução)
19.
disponibilidade ← calcular_disponibilidade(nó_físico_origem, nó_físico, nó_virtual_destino)
20.
se (disponibilidade > melhor_solução) faça
21.
melhor_solução ← disponibilidade
22.
nó_solução ← nó_físico
23.
fim-se
24.
tentativas ← tentativas + 1
25.
solução ← remover_elemento(solução, nó_físico)
26.
fim-enquanto
27.
se (está_definido(nó_solução)) faça
28.
alocado ← alocar_nó_e_caminho(nó_físico_origem, nó_solução, nó_virtual_destino)
29.
fim-se
30.
retorne alocado
31.
fim-se
32. retorne true
33. fim
Figura 3 – Método alocar_nós
6. Metodologia
6.1. Estratégias de Mapeamento
Foram selecionadas as estratégias D-ViNE-SP [Chowdhury et al. (2012)] e G-SP [Zhu e
Ammar (2006)] para comparação com a heurística proposta. D-ViNE-SP e G-SP foram
escolhidos por utilizarem um algoritmo de alocação baseada em um único caminho na
rede de substrato - ao contrário das outras variações do D-ViNE que particionam um
único enlace virtual em caminhos físicos diferentes. Tais trabalhos foram discutidos
mais detalhadamente na seção de trabalhos relacionados. Uma vez que nenhuma dessas
estratégias considera restrição de atraso, nós simulamos uma versão modificada de
nossa heurística para desconsiderar o atraso e quantificar o impacto desta restrição, no
entanto não houve diferença estatística entre as simulações, por isso apenas um caso é
exibido na seção de resultados.
6.2. Parâmetros de Dependabilidade
Dependendo do tamanho e complexidade do sistema (dependências complexas), o
sistema pode ser representado por um modelo ou particionado em modelos menores,
que representam partes do sistema (i.e., subsistemas), que fornecem métricas para a
avaliação de todo o sistema. Dessa forma, podemos considerar a rede virtual como
vários subsistemas. Modelando as relações entre os componentes de rede, os
subsistemas tiveram a disponibilidade calculada usando RBD.
Consideramos que um nó físico é composto por três componentes: CPU, disco
rígido e memória RAM. Assumimos um sistema RBD em série para estes componentes,
dessa forma, obtemos a disponibilidade do nó físico através do produto da
disponibilidade dos componentes que o compõem. A rede virtual formada é também
modelada em um sistema RBD em série, sendo a disponibilidade da requisição virtual
54
dada pela multiplicação da disponibilidade dos nós físicos, nos quais os nós virtuais
foram mapeados, pela multiplicação da disponibilidade dos enlaces físicos - utilizados
para mapear os enlaces virtuais que conectam os nós virtuais. Seus MTTFs e MTTRs
são baseados em [Kim et al. (2009)][ Fernandes et al. (2012)] e são exibidos na Tabela
1 (em horas). Semelhante a Fernandes et al. (2012), números aleatórios foram gerados
uniformemente no intervalo [35,100] para cada componente da rede física a fim de
determinar o seu MTTF de forma aleatória. Este número representa o percentual a ser
considerado para o MTTF. Os MTTRs são mantidos os mesmos para todos os
componentes.
Tabela 1. MMTF e MTTR para componentes do nó e enlace físico
CPU
Disco Rígido
Memória RAM
Enlace
MTTF (h)
2500000
200000
480000
19996
MTTR (h)
1
1
1
12
6.3. Simulação e Métricas
Para executar as estratégias D-ViNE-SP e G-SP utilizamos o simulador desenvolvido no
trabalho de Chowdhury et al. (2012). Para a nossa heurística desenvolvemos um
simulador próprio. As entradas contendo as redes de substrato e requisições físicas
foram retiradas de Infuhr et al. (2012). O benchmark utilizado como entrada é público e
possibilita fácil replicação dos experimentos realizados neste artigo, necessitando de
apenas algumas modificações: transformação do grafo direcionado em não direcionado
e acréscimo dos atributos de dependabilidade na topologia física. Foi necessário ainda
realizar a adaptação do simulador de Chowdhury et al. (2012) para adicionar atributos
de dependabilidade e computar a dependabilidade das requisições alocadas.
As requisições são alocadas de maneira sequencial sem que haja tempo de vida,
ou seja, a última requisição alocada leva a rede ao estresse máximo de utilização de
recursos. Realizamos 30 simulações para cada estratégia de alocação considerando
tamanhos de rede substrato com 20, 30, 50 e 100 nós. Para cada simulação houve 40
requisições com tamanho variável, de acordo com o crescimento da rede física. Notem
que estas características estão definidas nos arquivo de entrada do benchmark utilizado
disponível em Infuhr et al. (2013). As métricas coletadas são descritas na Tabela 2. Para
cada métrica foi calculado o intervalo de confiança com 95% de nível de confiança
podendo ser visualizado em cada gráfico exibido na seção de resultados.
Tabela 2. Métricas coletadas durante as simulações
Métrica
Descrição
Média da disponibilidade por requisição
Média da disponibilidade de um conjunto de
requisições virtuais
Taxa de aceitação
Quantidade de requisições de redes virtuais aceitas
dividida pelo número total de requisições
Utilização dos nós físicos
Média da carga de cada nó físico dividida por sua
respectiva capacidade
Utilização dos enlaces físicos
Média da carga de cada enlace físico dividida por sua
respectiva capacidade
55
Tempo de simulação
Quantidade de tempo de execução de cada simulação
As simulações foram executadas na máquina com as seguintes
E7300 @ 2.66GH; Placa de
configurações: CPU Intel(R) Core(TM)2 Duo CPU
vídeo nVidia GTX 550 TI Memória DDR5 de 2GB; Memória RAM de 2GB DDR2;
Disco rígido de 250GB 5400rpm e sistema operacional LinuxMint Release 14 (nadia).
7. Resultados
Nos gráficos de resultados vamos nos referir à heurística proposta neste artigo como
HRA (Heurística Randômica Adaptativa). Como explicado na seção 6.1, executamos a
heurística HRA com e sem restrição de atraso e não obtivemos resultado
estatisticamente diferente em nenhuma métrica coletada. Por esse motivo, os gráficos de
resultados exibem apenas a abordagem que leva em consideração o atraso por ser mais
próxima de um cenário real.
7.1. Disponibilidade
Retirando a média de cada estratégia de alocação de acordo com o tamanho da
topologia física, podemos ver na Figura 4 que a heurística HRA obtém resultados
estatisticamente bastantes superiores em relação às estratégias G-SP e D-ViNE-SP. A
disponibilidade média de uma requisição em uma rede de 20 nós, utilizando a heurística
HRA, obteve disponibilidade média de 0.9895 e 0.9593 para uma rede com 100 nós. As
demais estratégias obtiveram disponibilidade em torno de 0.6 ou menos.
Figura 4. Disponibilidade média de uma requisição por estratégia de alocação
de rede virtual
7.2. Taxa de Aceitação
Outra métrica importante a ser analisada diz respeito à capacidade de a estratégia
utilizada conseguir alocar o máximo possível de requisições recebidas. Analisando a
Figura 5, vemos que a estratégia HRA possui grande eficiência em conseguir alocar
todas as requisições virtuais recebidas. Mesmo com a variação do tamanho da topologia,
a probabilidade da taxa de aceitação com uma rede física de tamanho 100 foi de 0.9875.
O resultado da heurística HRA tem como um dos seus pilares a simples
estratégia de alocar, em um mesmo nó físico, um ou mais nós virtuais de uma mesma
requisição. Diferentemente de outras estratégias que restringem a alocação de nós
virtuais de uma requisição em nós físicos distintos. Dessa forma, analisando mais
56
detalhadamente em nosso simulador (heurística HRA) o comportamento do
mapeamento dos nós e enlaces virtuais, chegamos ao resultado de nenhuma rejeição por
falta de recurso em nós físicos da rede substrato. As poucas rejeições que ocorreram se
deram pela impossibilidade de formar um caminho que conectasse um dos nós da rede
virtual devido às restrições da requisição (banda ou atraso).
Figura 5. Taxa de aceitação
7.3. Utilização dos Nós
Analisando a utilização (carga/capacidade) média dos nós da rede substrato (Figura 6), a
heurística HRA obteve uma alta utilização dos nós quando comparada a outras
estratégias de alocação. Esse resultado é justificável devido a grande taxa de aceitação
das requisições pela heurística HRA e pelo fato de haver concentração de nós virtuais de
uma mesma requisição em um mesmo nó físico, fazendo com que haja uma utilização
maior nesse nó físico.
Figura 6. Utilização dos Nós físicos da rede substrato
7.4. Utilização dos Enlaces
Quando analisamos a utilização dos enlaces da rede substrato (Figura 7), vemos que
aparentemente a heurística HRA estressa menos os enlaces, mas devido ao intervalo de
confiança sobrepostos, temos resultados estatisticamente equivalentes. Um ponto a ser
destacado é que por alocar mais nós virtuais, a heurística HRA deveria ocupar mais
enlaces físicos após o mapeamento, e consequentemente aumentar a utilização média
dos enlaces físicos. No entanto, quando dois ou mais nós virtuais são alocados num
mesmo nó físico temos, provavelmente, a redução de um enlace virtual que ocuparia
recursos de enlaces físicos. Diferentemente das outras estratégias que não fazem uso
dessa abordagem de alocação.
57
Figura 7. Utilização dos Enlaces da rede substrato
7.5. Tempo de Execução
O tempo de execução médio de cada simulação pode ser visto na Figura 8 utilizando
uma escala medida em segundos. Pode-se observar que a heurística HRA resolve o
problema mais rapidamente na maioria das comparações, não sendo nunca mais lenta.
Note que o tempo de execução para a estratégia D-ViNe com 30 replicações numa
topologia de 100 nós o tempo de execução é de cerca de 10 horas, enquanto a heurística
HRA executa em aproximadamente 3 minutos.
Figura 8. Tempo médio de execução (segundos)
8. Discussão
A heurística HRA obteve resultados expressivos com bons índices de disponibilidade
quando comparada a outras estratégias de alocação bem referenciadas na literatura. Com
requisitos cada vez maiores por parte de clientes para utilização de serviços confiáveis e
acordos mais rígidos de SLAs (Service Level Agreement) a serem cumpridos pelos
provedores de infraestrutura, negligenciar atributos de dependabilidade não é uma
alternativa viável, dados os resultados apresentados neste trabalho.
Um ponto importante a ser destacado é que a heurística HRA possui uma nuance
em relação às outras estratégias comparadas: HRA permite a alocação de um ou mais
nós virtuais de uma mesma requisição virtual num mesmo nó físico. Embora simples
essa diferença mostrou-se significativa, dado que o objetivo da heurística HRA é
maximizar a dependabilidade. Não obstante, a heurística obteve resultados superiores na
taxa de aceitação de requisições e mesmo assim não produziu mais sobrecarga nos
enlaces da rede substrato quando comparada a outras estratégias.
58
Outro aspecto relevante é que ao simularmos os mapeamentos das requisições
ignorando a restrição de atraso não obtivemos diferenças significativas em nenhuma
métrica coletada quando comparamos o HRA com e sem restrição de atraso. Tal
resultado indica uma perspectiva de adaptação da heurística HRA mesmo neste tipo de
cenário. Por fim, por ser uma estratégia que pode ser considerada como gananciosa, a
heurística HRA foi mais rápida em encontrar soluções em praticamente todas as
comparações realizadas, não sendo em nenhum momento mais lenta que as estratégias
comparadas.
9. Conclusão
Este artigo apresentou uma heurística aleatória adaptativa para alocação de redes
virtuais considerando atributos de dependabilidade, requisitos e restrições de atraso,
CPU e banda. O objetivo da heurística é maximizar a disponibilidade de cada requisição
alocada.
A heurística proposta apresentou melhores resultados com as abordagens
comparadas em métricas importantes como taxa de aceitação e carga nos enlaces da
rede. A dependabilidade com o uso da heurística variou entre 95,93% e 98,95% de
acordo com o tamanho da topologia da rede substrato, enquanto outras abordagens se
mantiveram em 60% ou menos, demonstrando que ignorar esta característica torna a
alocação de uma requisição muito mais propensa à falha. Ou seja, comparando outras
estratégias com a heurística HRA, fica claro que o impacto sobre a dependabilidade
quando não se leva em consideração atributos de dependabilidade no processo de
alocação pode consequentemente ocasionar uma grande queda na confiabilidade das
redes virtuais alocadas.
Em trabalhos futuros pretendemos levar em consideração variação da
probabilidade de falha de um nó físico quando a carga desse nó aumenta, inserindo
ainda na modelagem do problema restrição de dependabilidade do cliente e/ou servidor.
Pretendemos utilizar ainda outras métricas de dependabilidade em experimentos futuros,
analisando o problema mais detalhadamente.
Referências
Benson, T., Sahu, S., Akella, A., & Shaikh, A. (2010) “A first look at problems in the
cloud”. 2nd USENIX conference on Hot topics in cloud computing (HotCloud'10)
Chowdhury, M., Rahman, M. R., & Boutaba, R. (2012). “ViNEYard: Virtual network
embedding algorithms with coordinated node and link mapping”. IEEE/ACM
Transactions on Networking (TON), 20(1), 206-219.
Ebeling, C. E. (1997) “An introduction to reliability and maintainability engineering”
(pp. 58-69). New York, NY: McGraw Hill.
Fernandes, S., Tavares, E., Santos, M., Lira, V., & Maciel, P. (2012) “Dependability
assessment of virtualized networks”. In Communications (ICC), 2012 IEEE
International Conference on (pp. 2711-2716). IEEE.
Fischer, A., Botero, J., Beck, M., De Meer, H., & Hesselbach, X. (2013) "Virtual
network embedding: A survey", in IEEE Communications Surveys & Tutorials.
59
Gill, P., Jain, N., & Nagappan, N. (2011) “Understanding network failures in data
centers: measurement, analysis, and implications”. In ACM SIGCOMM Computer
Communication Review (Vol. 41, No. 4, pp. 350-361). ACM.
Guimarães, A., Maciel, P., Matos Jr, R., & Camboim, K. (2011). Dependability analysis
in redundant communication networks using reliability importance. In The 2011
International Conference on Information and Network Technology.
Guo, T., Wang, N., Moessner, K., & Tafazolli, R. (2011) "Shared Backup Network
Provision for Virtual Network Embedding," Communications (ICC), IEEE International
Conference on, pp.1-5, 5-9
Infuhr, J., Raidl, G.R. (2012) "The Virtual Network Mapping Problem benchmark set",:
https://www.ads.tuwien.ac.at/projects/optFI/, acessado em Dezembro de 2012.
Infuhr, J., Raidl, G.R. (2013) "GRASP and Variable Neighborhood Search for the
Virtual Network Mapping Problem.", Hybrid Metaheuristics. Springer Berlin
Heidelberg, 2013. 159-173.
Lira, V. et al., "Virtual Network Resource Allocation Considering Dependability
Issues", In: IEEE 13th International Conference on Computer and Information
Technology (CIT2013), Sidney, 2013
Kim, D. S., Machida, F., & Trivedi, K. S. (2009) “Availability modeling and analysis of
a virtualized system”. In Dependable Computing, 2009. PRDC'09. 15th IEEE Pacific
Rim International Symposium on (pp. 365-371). IEEE.
Laprie, J. C. (1985). “Dependable computing and fault-tolerance”. Digest of Papers
FTCS-15, 2-11.
Maciel, P., Trivedi, K. S., Matias, R., & Kim, D. S. (2011). Performance and
Dependability in Service Computing: Concepts, Techniques and Research Directions,
ser. Premier Reference Source. Igi Global.
Nicol, D. M., Sanders, W. H., & Trivedi, K. S. (2004) “Model-based evaluation: from
dependability to security”. Dependable and Secure Computing, IEEE Transactions.
Saripalli, P., & Walters, B. (2010) “QUIRC: A Quantitative Impact and Risk
Assessment Framework for Cloud Security”. In Cloud Computing (CLOUD), 2010
IEEE 3rd International Conference on (pp. 280-288). IEEE.
Schaffrath, G., Werle, C., Papadimitriou, P., Feldmann, A., Bless, R., Greenhalgh, A.,
& Mathy, L. (2009) “Network virtualization architecture: proposal and initial
prototype”. (VISA '09). ACM, New York, NY, USA, 63-72.
Sun, D., et al. (2010) “A Dependability Model to Enhance Security of Cloud
Environment Using System-Level Virtualization Techniques”. In Pervasive Computing
Signal Processing and Applications (PCSPA), IEEE.
Trivedi, K. S. (2008) “Probability & statistics with reliability, queuing and computer
science applications”. John Wiley & Sons.
Zhou, Y., Li, Y., Sun, G., Jin, D., Su, L., & Zeng, L. (2010) "Game Theory Based
Bandwidth Allocation Scheme for Network Virtualization," IEEE GLOBECOM.
Zhu, Y., & Ammar, M. H. (2006) “Algorithms for Assigning Substrate Network
Resources to Virtual Network Components”. In INFOCOM (pp. 1-12).
60

Uma Heurística Aleatória com Busca Adaptativa

Transcrição

Documentos relacionados

Habbo e comercio de bens virtuais por criancas

Salvar como PDF - Deki Wiki Cercomp

Mundos virtuais e identidade social: processos de formação

processos de formação e mediação através da `lógica do

A comunicação pelas novas mídias

Ambientes Interativos e Colaborativos baseados em Realidade

Personalização de Agentes Pedagógicos Animados

Realidade Aumentada Aplicada a Medicina

BIBLIOTECAS VIRTUAIS TEMÁTICAS

Medindo o Brilho e a Cor das Estrelas