Roteamento Baseado em Crédito/Punição Rafael dos Santos Alves

Roteamento Baseado em Crédito/Punição

Rafael dos Santos Alves

Índice

Introdução Objetivo Sprite Conclusões Referências Perguntas e Respostas

Introdução

Internet Roteadores pertencem a organizações

que desejam cooperar encaminhando o tráfego

Redes ad hoc e Peer-to-peer Tráfego encaminhado por computadores

pessoais Restrições de banda passante e/ou bateria

Objetivo

Apresentar propostas que utilizam incentivos/punições para que nós da rede participem do encaminhamento de pacotes

Sprite

A Simple, Cheat-proof, Credit-based System for Mobile Ad hoc Networks Proposto por Chen et al. [1]

Redes Ad hoc móveis

Incentivos através de créditos

Sprite - Objetivos

Incentivo à cooperação de nós egoístas

Não trata nós defeituosos ou maliciosos

Sprite - Premissas Cada nó conhece o caminho completo

para o destino Utilização de algum protocolo de

roteamento por estado de enlace (por exemplo DSR – Dinamic Source Routing)

Cada nó possui uma identificação confiável Assinatura digital

Sprite - Arquitetura

Credit Clearance Service (CCS) Responsável por atribuir créditos

Nós Computadores equipados com

interfaces sem fio

Sprite - Arquitetura

Internet

Credit Clearance Service (CCS)

Nó 1Nó 2

Nó 3Nó 4

Nó 5

Figura 1: Adaptado de Chen et al. [1]

Sprite - Créditos

Duas formas de receber créditos Comprar créditos usando dinheiro

real Encaminhar mensagens de outros

(preferencial)

Sprite - Funcionamento

Ao receber uma mensagem o nó armazena um receipt da mensagem para enviar posteriormente ao CCS

O nó pode optar por encaminhar ou não a mensagem para o próximo nó

Sprite - receipts

Resumo das mensagens enviadas Redução do espaço de

armazenamento e da banda utilizada para transmissão

Nós não precisam confiar no sigilo do CCS

Sprite - Especificação

Nós possuem par de chaves assimétricas PKi e SKi

Mensagens com número de seqüência SEQi(j,k) – número de seqüência,

armazenadas no nó ni, para mensagens enviadas de nj para nk

Sprite – Especificação (2)

Envio de mensagens Fonte envia:

(m, p, SEQo(o,d),s)

Onde:m = mensagemp = caminho entre no (origem) e nd (destino)

s = assinatura sobre (hash(m), p, SEQo(o,d))

Sprite – Especificação (3) Recepção de mensagens

Nó i verifica: Se ni pertence a p Se o número de seqüência é maior que

SEQi(o,d) Se assinatura é válida

Atualiza SEQi(o,d) Armazena receipt (hash(m),p,SEQi(o,d),s) Decide sobre encaminhar mensagem

p = (n0, ..., ne, ..., nd) ne foi o último nó a receber a mensagem

Fonte deve pagar:C = (d - 1)α + β - (d - e)γβ, α > β, γ< 1

Outros nós em p devem receber:

Sprite - Pagamentos

α > β, γ< 1

Sprite – Pagamentos (2)

Transmissor Nó 1 Nó 2 Nó 3 Nó 4 Destino X

Exemplo: Mensagem não chega ao destino

Créditos: Transmissor: -(4α + β - 2γβ) Nós 1 e 2: γα Nó 3: γβ Nó 4 e Destino: zero

Sprite – Pagamentos (3)

Exemplo: Mensagem chega ao destino

Créditos: Transmissor: -(4α+ β) Nós 1, 2, 3 e 4: α Destino: β

Transmissor Nó 1 DestinoNó 2 Nó 3 Nó 4

Sprite - Segurança

n0 em conluio com ne

ne não envia o receipt ne perde β n0 compensa ne com ε n0 perde ε - γβ Grupo perde β - γβ

Sprite – Segurança (2)

Nós só encaminham receipts e não mensagens Destino não irá reportar recebimento Todos os nós terão pagamentos

multiplicados por γ (γ < 0)

Conclusões Incentivos para roteamento são

necessários Sprite apresenta uma solução segura Entretanto, o Sprite não apresenta uma

forma de os nós conhecerem os créditos dos outros

Forma de pagamento incentiva o uso de caminhos com o menor número de saltos

Referências [1] J. Chen, S. Zhong, Y. Yang. "Sprite: a simple, cheat-proof, credit-based

system for mobile ad- hoc networks", Proceedings of the 22nd IEEE Infocom, 2003, pp. 1987-1997.

[2] A. Blanc, Y.-K. Liu, and A. Vahdat. "Designing Incentives for Peer-to-Peer Routing". 2nd NetEcon, 2004.

[3] Y. Liu and Y.R. Yang. "Reputation Propagation and Agreement in Mobile Ad Hoc Networks", Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), 2003.

[4] C. Tan, S. Bose. "Enforcing Cooperation in an Ad Hoc Network using a Cost-Credit Based Forwarding and Routing Aproach", Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), 2007.

[5] Y. Chen, K. Liu, and Y. Lin. "A Credit- Based On- Demand QoS Routing Protocol over Bluetooth WPANs", Proceedings of The 10th IEEE Symposium on Computers and Communications, (IEEE ISCC 2005), 2005 , pp. 807-812.

[6] D. Levin. "Punishment in selfish wireless networks: A game theoretic analysis". NetEcon, 2006

[7] B. Sartini, G. Garbugio, H. Bortolossi, L. Barreto, P. Santos; "Uma Introdução a Teoria dos Jogos"; II Bienal da SBM, 2004, Salvador - BA, 2004.

[8] M. J. Osborn; "An introduction to game theory"; Oxford University Press; 2004.

[9] M. Kandori; "Social Norms and community enforcement"; Review of Economic Studies, Vol. 59, nº1, 1992, pp 63 - 80.

Perguntas e Respostas

1. Por que sistemas de roteamento que utilizam crédito/punição são necessários?


1. Por que sistemas de roteamento que utilizam crédito/punição são necessários?

Redes que utilizam computadores pessoais para encaminhar o tráfego necessitam que seus usuários sejam incentivados a participar do encaminhamento, visto que essa atividade gera um consumo de recursos do sistema, tais como bateria e banda passante.


2.Qual a responsabilidade do CCS (Credit Clearance Service)?


2.Qual a responsabilidade do CCS (Credit Clearance Service)?

A principal responsabilidade do CCS é atribuir créditos aos nós, realizando a conferência dos receipts recebidos.


3.Quais as formas de um nó receber novos créditos? Qual é a preferencial?


3.Quais as formas de um nó receber novos créditos? Qual é a preferencial?

Os nós podem receber créditos de duas formas, através da compra utilizando dinheiro real, ou encaminhando pacotes de outros. Esta última forma é a preferida, dado que melhora a performance do sistema.


4.Por que os receipts devem ser de tamanho reduzido?


4.Por que os receipts devem ser de tamanho reduzido?

Os receipts precisam ser de tamanho reduzido para impedir que os nós necessitem reservar um grande espaço para seu armazenamento, para reduzir o consumo de banda passante utilizado para transmiti-los e além disso, permitir que os nós não necessitem confiar no sigilo do CCS.


5.Quais são os nós que recebem pagamento?


5.Quais são os nós que recebem pagamento?

Todos os que recebem a mensagem recebem pagamento, através de créditos. Além disso, o nó que originou as mensagens perde créditos proporcionais ao número de nós que recebeu a mensagem.

Roteamento Baseado em Crédito/Punição

Rafael dos Santos Alves

Documents

Roteamento Baseado em Crédito/Punição Rafael dos Santos Alves