modelli e tecniche per l’adattività del livello di rete

rapporto 4.3.2

polimi, romatre

novembre 2004

2modelli e tecniche per l’adattività del livello di rete

obiettivi

sviluppo di tecniche adattative per il livello di rete

• livello OSI 3

adattatività rispetto alle esigenze dell’applicazione

• Quality of Service

parametri importanti

• delay, jitter, throughput, errori, disponibilità del servizio, ecc.

• orientato al pacchetto o a flussi di pacchetti

3modelli e tecniche per l’adattività del livello di rete

l’approccio

decisione(modelli per la previsione del comportamento della

rete)

rete applicazione

allocazionedelle risorse

(adattamento)

richieste di QoSstato della rete

rifiuto

l’adattamento è una allocazione di risorse su richiesta dell’applicazione

richiede un processo di decisione

4modelli e tecniche per l’adattività del livello di rete

stato dell’arte (vedi R4.3.1)

protocolli per allocare risorse (RSVP)

• API applicativa (RAPI)

tecniche per garantire la QoS sui flussi

• scheduling, buffer management, shaping

architetture

• DiffServ, IntServ, ecc.

admission control

• architetture con Policy Decision Point

ecc.

5modelli e tecniche per l’adattività del livello di rete

contributo

inter-domain (romatre)

• visualizzazione/animazione routing inter-domain

• inferenza delle relazioni customer-provider da tabelle di routing

• semplice architettura adattativa interdomain

intra-domain: modellazione con inviluppi di traffico statistici (polimi)

• probabilità di violazioni di soglia di ritardo

• applicazioni: admission control

inter-domain

romatre

7modelli e tecniche per l’adattività del livello di rete

pubblicazioni

visualizzazione routing inter-domain• G. Di Battista, F. Mariani, M. Patrignani, M. Pizzonia,

"BGPlay: a System for Visualizing the Interdomain Routing Evolution", to appear in Giuseppe Liotta, editor, Graph Drawing (Proc. GD '03), Lecture Notes Comput. Sci., Springer-Verlag.

• G. Di Battista, F. Mariani, M. Patrignani, M. Pizzonia. Archives of BGP Updates: Integration and Visualization. International Workshop on Inter-domain Performance and Simulation. IPS 2003.

inferenze di relazioni customer-provider• G. Di Battista, M. Patrignani, M. Pizzonia. Computing

the Type of Relationships Between Autonomous Systems. IEEE INFOCOM 2003, The Conference on Computer Communications, The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies.

le pubblicazioni sono allegate al deliverable R4.3.2

8modelli e tecniche per l’adattività del livello di rete

BGP: announcements and traffic flows

bgp allows a router to offer connectivity to another router

“offering connectivity” means “promising the delivery to a specific destination”

195.10.14.0/24

bgp announcement

ip traffic (to be delivered to 195.10.14.0/24)

AS100AS100 AS200AS200

9modelli e tecniche per l’adattività del livello di rete

BGP AS-path propagation

193.204.161.0/24

193.204.161.0/24

40 10

prefix

as-path

legenda:

AS10AS10

AS40AS40 AS31AS31

AS60AS60

AS212AS212

193.204.161.0/24

10 193.204.161.0/24

31 40 10

193.204.161.0/24

60 31 40 10

193.204.161.0/24

212 60 31 40 10

10modelli e tecniche per l’adattività del livello di rete

BGP ed politiche commerciali

peer-peer relationship

from a provider from a provider

from a customer from a customer

from a peer

customer-provider relationship

from a provider

from a provider

from a customer

from a customer

from a peer

C

P$ €

11modelli e tecniche per l’adattività del livello di rete

BGP e adattività (esempio)

un esempio• sorgente AS2 • destinazione AS1• richiesta una certa QoS

tutti gli AS verdi supportano la QoS richiesta, AS4 non supporta la QoS (rosso) BGP, di default, scegliere un cammino errato AS1 può forzare l’adattività della rete

• modificando l’AS-path iniziale • inserendo AS4

• di fatto modificandole scelte di BGP

necessarie info su• topolgia• relazioni• QoS supportata

visualizzazione di topologie inferenza di relazioni

AS1

AS2

AS3

AS4

AS5

AS6

customercustomer customer

customercustomer

provider provider

providerprovider

peers

destinatario sorgente

provider

12modelli e tecniche per l’adattività del livello di rete

inferenza delle relazioni commerciali

specifiche• input: tabelle di routing BGP (pubbliche)• output: topologia e relazioni commerciali inferite

risultati• formalizzazione come problema di ottimizzazione

• basata su proprietà combinatorie delle tabelle di routing BGP derivanti dalle relazioni commerciali

• dimostrazione di NP-hardness• algoritmi euristici polinomiali• prototipo per il calcolo

• disponibile on-line:http://www.dia.uniroma3.it/~compunet/relationships/

13modelli e tecniche per l’adattività del livello di rete

BGP collectors

organizations• RIPE’s Routing Information Service (RIS)• Universty of Oregon RouteViews Project

RIS DB query result for all RRC boxes.

State of the local RIB on 20040420.

Prefix Time Peer Next HOP AS path ....

193.0.0.0/21 2003-12-15 22:13:58Z 194.153.154.35 194.153.154.35 20854 3333

193.0.0.0/21 2004-01-15 18:01:03Z 193.0.0.56 193.0.0.56 3333

193.0.0.0/21 2004-01-15 18:01:31Z 195.69.144.68 195.69.144.68 3333

193.0.0.0/21 2004-02-19 03:22:48Z 195.69.144.196 195.69.144.68 6762 3333

.....

Updates between 2004-04-20 00:00:00Z and 2004-04-20 13:08:23Z .

Type Prefix Time Peer Next HOP AS path ...

A 193.0.0.0/21 2004-04-20 00:55:39Z 64.211.147.146 64.211.147.146 3549 1103 3333

A 193.0.0.0/21 2004-04-20 03:27:57Z 64.211.147.146 64.211.147.146 3549 1103 3333

.....

14modelli e tecniche per l’adattività del livello di rete

BGPlay

stable paths(dashed)

unstable paths (solid)

target AS

colors disambiguates

time line

currently visualized instant

bgp event descr.

control panel

collector peer

endtime

starttime

events density

15modelli e tecniche per l’adattività del livello di rete

BGPlay installations

complessivamente una media di circa 150 accessi