About Network coding

Introduzione

Network Information FlowNetwork Coding

Alain Bindele

Corso di Reti Avanzate 2012/2013

14 giugno 2013

Alain Bindele Network Information Flow

Introduzione

Argomenti affrontati:

I Il Network Information Flow ed il Network CodingI Soluzioni proposte: COPE

I Funzionamento del protocolloI Struttura dell’headerI PrestazioniI Interazione con il MAC layerI Miglioramenti proposti

I Coding-Aware routing

I Sviluppi futuri


Introduzione

Problema del Network Information Flow

“In una rete in cui un insieme di nodi sorgenti devono trasmettereinformazioni ad una serie di nodi di destinazione attraverso uninsieme di nodi ripetitori, qual’e il massimo flusso informativo

raggiungibile?”


Introduzione

Un esempio tipico:

(a) (b)

Figura: Configurazione “Alice and Bob” senza network coding (a) e con networkcoding (b)


Introduzione

Un altro esempio tipico:

A B

D E

x

x

C

x,y x,y

(a) (b)

Figura: Rete di comunicazione “a farfalla” senza l’uso del network coding (a) econ network coding (b)


Introduzione

Il protocollo COPE: L’importanza di essere opportunisti...(in sensobuono)


Introduzione

Il protocollo COPE:

I Ascolto Opportunistico

I Coding Opportunistico

I Pseudo-Broadast

I Riscontri Asincroni

I Reception Reports


Introduzione

Il problema della scelta.

P1

P2

P3

P4

Pacchetti

A

Dest.

C

C

D

0 0 0

0 0 0

1 1 1

1 1 1

0 0 0

0 0 0

1 1 1

1 1 1

0 0 0

0 0 0

1 1 1

1 1 1

D

C

BA

P1P2P3P4

P4 P3

P1 P4

P3 P1

P1+P2

(a) Hop successivi dei pacchetti in coda nel nodo B (b) Scelta pessima

0 0

0 0

0 0

0 0

1 1

1 1

1 1

1 1

0 0

0 0

0 0

0 0

0 0

1 1

1 1

1 1

1 1

1 1

0 0

0 0

0 0

0 0

1 1

1 1

1 1

1 1

D

C

BA

P1P2P3P4

P4 P3

P1 P4

P3 P1

P1+P3

0 0

0 0

1 1

1 1

0 0

0 0

0 0

1 1

1 1

1 1

0 0

0 0

1 1

1 1

0 0

0 0

1 1

1 1 D

C

BA

P1P2P3P4

P4 P3

P1 P4

P3 P1

P1+P3+P4

(c)Buona Scelta (d) Miglior scelta

(C può decodificare, A no)

(A e C possono decodificare) (A, C e D possono decodificare)

Figura: Coding opportunistico: nella situazione (a) le diverse scelte portano diversifattori di miglioramento sulle prestazioni.Alain Bindele Network Information Flow

Introduzione

Idea!! Perche allora non utilizzare i protocolli broadcast??Quasi...


Introduzione

Soluzione Pseudo-Broadcastossia: come implementare un meccanismo broadcast su flussi

unicast.


Introduzione

Codifica dei pacchetti: Obiettivi

I Nessun Ritardo!

I Pacchetti Omogenei

I Differenti Destinazioni

I Massima probabilita di ricezione


Introduzione

Decodifica dei pacchettiNiente di piu semplice:Una hashlist ed uno Xor.


Introduzione

L’algoritmo di ricezione e di invio.

Encoded?

Can send

yes

no

Schedule

retransmissions

Add reception reports

To wireless device

Add acks to header

Dequeue head of

Output Queue

Encode if

possible

Encoded?

Packet

arrival

yes

no

Decode and schedule acks

Extract acks meant for me

Update retransmission events

yes

no

Enqueue in

Output Queue

Deliver

to host

Extract Reception Reports

Update Neighbor’s State

Am I nexthop?

Decodable?

Am I destination?

yes

yes

Add to Packet Pool

Add to Packet Pool

(a) Sender side (b) Receiver side

Figura: Flusso dell’algoritmo in codifica e decodificaAlain Bindele Network Information Flow

Introduzione

Struttura dell’header COPE

Figura: Struttura dell’ Header del protocollo COPE.


Introduzione

Prestazioni del protocollo COPE

0.6

0.8

1

1.2

1.4

1.6

1.8

2

1 1.5 2 2.5 3

TC

P G

oo

dp

ut in

Mb

/s

Carico offerto in Mb/s

COPEsenza COPE

0

1

2

3

4

5

6

0 2 4 6 8 10 12 14 16 18 20 22 24

Th

rou

gh

pu

t d

i re

te in

Mb

/s


con COPEsenza COPE

(a) (b)

Figura: a)Prestazioni del protocollo COPE in una rete TCP senza casi di hiddenterminal. b)Prestazioni del protocollo COPE con flussi UDP in una rete wirelessad-hoc.


Introduzione

Prestazioni del protocollo COPE (2)

0

10

20

30

40

50

60

1 2 3 4 5 6

Pe

rce

ntu

ale

N°. pacchetti codificati insieme

Pacchetti Codificati

0

20

40

60

80

100

0 4 8 12 16 20 24

Pe

rce

ntu

ale


Pacchetti codificati probabilisticamente

(a) (b)

Figura: a) Distribuzione del numero di pacchetti codificati nel punto di piccorelativamente all’esperimento della slide precedente. b)Percentuale dei pacchetticodificati tramite considerazioni probabilistiche nel punto di picco relativamenteall’esperimento della slide precedente (parte b).


Introduzione

Prestazioni del protocollo COPE: altre considerazioni

I Effetto Cattura

I Hidden Terminal

I Confronto fra le prestazioni teoriche e pratiche


Introduzione

Interazione tra MAC e COPE

0 0.5 1 1.5 20

0.1

0.2

0.3

0.4

0.5

0.6

0.7

Carico Offerto

Th

rou

gh

pu

t T

ota

le

COPE

Routing

Figura: Funzioni del throughput teoriche con e senza NC


Introduzione

Interazione tra MAC e COPE (Topologia a stella)

A

B

C

D

r

Figura: Esempio di topologia a stella


Introduzione

Miglioramenti per la fairness

Coda del nodo codi�cante

Sequenza pacchetti inviati

Sequenza inviata

Code virtuali del nodo codi�cante

a)

b)

Figura: Esempio: Code dei pacchetti con e senza tecnica di round-robin


Introduzione

Coding-Aware Routing

a) b) c)

Figura: a) Routing semplice. b) Routing che massimizza le opportunita di codificac) Topologia di esempio


Introduzione

Le euristiche:

I SPATH: Routing interference-aware su singolo percorso senzacodifica.

I MPATH: Routing interference-aware su percorso multiplosenza codifica.

I SPATH-CODE: Routing non coding-aware su singolo percorsocon codifica.

I CA-SPATH-CODE: Routing coding-aware su singolo percorsocon codifica.

I CA-MPATH-CODE: Routing coding-aware su percorsi multiplicon codifica.


Introduzione

Confronto tra le euristiche:

Interferenze vs. Opportunita di codifica

I MPATH: buono a basso carico, ad alti carichi soffrel’interferenza

I SPATH-CODE: buone opportunita di codifica ma su singolopercorso

I CA-MPATH-CODE: miglior throughput


Introduzione


Coding-Aware vs. opportunistic listening

I SPATH-CODE + L: +10% rispetto a SPATH-CODE,+30% rispetto a SPATH.

I CA-MPATH-CODE -L: migliore del SPATH-CODE + L


Introduzione


Banda vs. Throughput

I SPATH-CODE: 17% di risparmio rispetto a SPATH

I MPATH: 17% peggiori rispetto a SPATH

I Le migliori performance si ottengono tramite codifica eascolto opportunistico.


Introduzione


a) b)

c) d)

e)


Introduzione

Confronto tra le euristiche (2):

e)


About Network coding

Internet

Transcript of About Network coding