A Self-Organizing Composition Towards Autonomic Overlay

Networks

Uma Composição Auto-Organizável Para Redes Overlay Autonômicas

I. AL-OQILY, A. KARMOUCH

NETWORK OPERATIONS AND MANAGEMENT SYMPOSIUM, 2008. NOMS 2008. IEEE

Carlo Marcello

Thiago Roberto Borille

Roteiro

Introdução Trabalhos Relacionados Composição auto-organizável de serviços Algoritmo / Funcionamento Regras de aprendizado Experimentos Conclusão

Introdução

SSONs (Service Specific Overlay Networks) Redes Overlay Específicas a Serviços

Computação Autonômica Adapta às alterações do meio Simplifica e automatiza o gerenciamento Economiza tempo e custos de manutenção Composição de entidades autônomas para

atingir objetivos globais

Introdução - Composição de Serviços

Composição Permite que serviços simples formem serviços

complexos Definida como um grafo acíclico dirigido

G(N, L,W) N = número de serviços em Gl(u, v) em L = composição de serviço entre u e v com custo

W Service Path – caminho em G que minimiza um

critério de custoPROBLEMA:

Impossível contar com serviços predeterminados Re-computar G para cada mudança é custoso

Trabalhos Relacionados

Projetos de Composição de Serviços: Gri-PhyN SWORD Libra Ninja CANS

Contam com uma entidade central para tratar da descoberta, integração e composição de serviçosou

Assumem o conhecimento prévio de um grafo de serviços base para seus algoritmos de composição

Composição auto-organizável de serviços

Elementos autonômicos garantem seu gerenciamento

SSONs são compostas de muitos elementos autonômicos

Requerimentos para SSONs: Descentralização Eficiência Robustez Dinamismo

Tipos de composição de serviços

MP (MediaPort)

Composição auto-organizável de serviços

Cada MP conhece os seus serviços e de sua vizinhança. A vizinhança é determinada por MPs de uma sub-área.

Um MediaClient (MC) solicita mídia de um MediaServer (MS)

O problema de composição é determinar um media flow que consegue transformar os dados do MS em um formato aceito pelo MC

O service path montado deve atender ao QoS solicitado pelo MC

Composição auto-organizável de serviços

Suposições e Regras

Cada nó conhece sua localização geográfica; A área é dividida em sub-áreas de tamanho

igual; Cada nó sabe à qual sub-área ele pertence, e

pode passar essa informação para todos os nós da rede;

Inicialmente a requisição é repassada usando somente o conhecimento local;

Requisição enviada somente para nós que estão no caminho direto entre o MC e o MP

Área de Pesquisa

Área de Pesquisa

Onde, (x1,y1) é a posição do MC, (x2,y2) é a posição do MS e (x0,y0) é a posição do MP

MP está na área de busca se

Classificação na ActiveList

R(A,B) = 4, A sabe que junto com B pode prestar um serviço completo;

R(A,B) = 3, A sabe que junto com B pode prestar um serviço parcial;

R(A,B) = 2, A sabe que B pode prestar um serviço completo sem ele;

R(A,B) = 1, A sabe que B pode prestar um serviço parcial sem ele;

R(A,B) = 0, A sabe que B não pode prestar o serviço;

Pacote de Requisição de Composição

Request ID (RID) MediaClient Input (I) MediaServer Output (O) Requisitos de QoS Ângulo α[0,180] Histórico de Composição

Exemplo

Uma Requisição de Composição = RC(S1+S2+S3)

Sendo: S1 = Converter vídeo MPEG em AVI S2 = Inserir o áudio no vídeo AVI S3 = Inserir a legenda no vídeo (já com o

áudio)

Funcionamento

D

C B

A

MC

ID Serviço

Rank

A S1 4

F S1 4

A S4 3

E

F

MS

RC(S1+S2+S3)

Funcionamento

D

C B

A

MC

ID Serviço

Rank

D S2 0

C S2 2

E

F

MS

RC(S1+S2+S3)

Funcionamento

D

C B

A

MC

ID Serviço

Rank

D S3 0

B S3 0

E

F

MS

RC(S1+S2+S3)

Funcionamento

D

C B

A

MC

ID Serviço

Rank

E S3 2

E

F

MS

RC(S1+S2+S3)

Funcionamento

D

C B

A

MC

ID Serviço

Rank

E

F

MS

RC(S1+S2+S3)

Funcionamento

D

C B

A

MCE

F

RC(S1+S2+S3)

MS

• MS aguarda por mensagens recebidas em período de tempo T;• Analisa as mensagens e escolhe um caminho conforme critérios da requisição;

Funcionamento

D

C B

A

MCE

F

MS

MS envia ao MC uma mensagem de falha pelo caminho inverso

RC(S1+S2+S3)

Funcionamento

D

C B

A

MCE

F

MS

• MC aumenta o ângulo(α) de pesquisa;

• MC refaz a pesquisa;

Regras de aprendizado

Aprender com as interações Armazenar informações de outros MPs para uso

futuro; Se a ActiveList estiver cheia, descarta os MPs

com menor Rank; Feedback positivo e negativo

Incrementa e Decrementa o Rank de um nó na ActiveList dependendo da suas cooperação recente para o respectivo serviço;

Movimentação orientada Mover requisição numa direção específica; Previne loops;

Self-Org LF (Limited Flooding com TTL)

Solicitação de composição enviada para todos os vizinhos diretos

Graph Based (GB) Serviços registram em um diretório central Solicitações de composição são enviadas ao

diretório Self-Org+

Self-Org + regras de aprendizado

625 serviços2000 nodos

Experimentos

Experimentos – Network LoadNúmero total de mensagens geradas

Experimentos – Average Composition TimeDiferença entre o tempo inicial da solicitação de composição e a chegada dos resultados completos

Experimentos – Packet StretchNúmero de hops usados por um pacote overlay dividido pelo número de hops que o pacote usa em um caminho de camada IP entre a mesma fonte e destino

Stretch maior = SSON ineficiente, pois rotas longas atrasam os pacotes.

Experimentos – Success RateNúmero de solicitações que recebem respostas positivas, dividido pelo numero de solicitações

Conclusão

Permite que elementos se organizem em SSONs

Uso de regras de aprendizagem derivadas de sistemas biológicos

Eficiente em relação a outras abordagens