Roteamento Baseado em
Crédito/Punição
Rafael dos Santos Alves
Índice






Introdução
Objetivo
Sprite
Conclusões
Referências
Perguntas
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)
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
Credit Clearance Service (CCS)
Internet
Nó 1
Nó 2
Nó 3
Nó 4
Figura 1: Adaptado de Chen et al. [1]
Nó 5
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 = mensagem
p = 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
Armazena receipt (hash(m),p,SEQi(o,d),s)
Decide sobre encaminhar mensagem
Sprite - Pagamentos

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:
α > β, γ< 1
Sprite – Pagamentos (2)

Exemplo: Mensagem chega ao destino
Transmissor

Nó 1
Nó 2
Nó 3
Créditos:



Transmissor: -(4α+ β)
Nós 1, 2, 3 e 4: α
Destino: β
X
Nó 4
Destino

Exemplo: Mensagem chega ao destino
Transmissor

Nó 1
Nó 2
Nó 3
Créditos:



Transmissor: -(4α+ β)
Nós 1, 2, 3 e 4: α
Destino: β
Nó 4
Destino
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. 19871997.
[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 CostCredit 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. 807812.
[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
1.
2.
3.
4.
5.
Por que sistemas de roteamento que
utilizam crédito/punição são necessários?
Qual a responsabilidade do CCS (Credit
Clearance Service)?
Quais as formas de um nó receber novos
créditos? Qual é a preferencial?
Por que os receipts devem ser de tamanho
reduzido?
Quais são os nós que recebem pagamento?
Roteamento Baseado em
Crédito/Punição
Rafael dos Santos Alves