Internet e Data Centers: algoritmi di routing nelle reti fisse

Internet and Data Centers

Algoritmi di instradamento per l'infrastruttura di rete fissa

G. Di Battista, M. Patrignani 120-instradamento-02 copyright @2023 g. di battista, m.patrignanicopyright notice all the pages/slides in this presentation, including but not limited to, images, photos, animations, videos, sounds, music, and text (hereby referred to as "material") are protected by copyright · this material, with the exception of some multimedia elements licensed by other organizations, is property of the authors and/or organizations appearing in the first slide · this material, or its parts, can be reproduced and used for didactical purposes within universities and schools, provided that this happens for non-profit purposes " any other use is prohibited, unless explicitly authorized by the authors on the basis of an explicit agreement " this copyright notice must always be redistributed together with the material, or its portions 120-instradamento-02 copyright @2023 g. di battista, m.patrignani

Panoramica

• generalità
• qualità degli algoritmi di instradamento tipi di algoritmi
• algoritmi di instradamento basati su distance vector
• algoritmi di instradamento basati su link state packet

120-instradamento-02 copyright @2023 g. di battista, m.patrignani

Qualità degli algoritmi di instradamento

Efficienza degli algoritmi di instradamento

• per evitare che il calcolo dei cammini verso le destinazioni abbia un peso eccessivo rispetto all'istradamento dei pacchetti
• le cpu e le memorie attualmente disponibili sui router sono talvolta insufficienti se confrontati con la complessità delle reti

Ottimalità nella scelta dei cammini

• rispetto a qualche criterio che deve essere misurabile
• normalmente si usa il numero di hop o il costo delle linee, talvolta assunto inversamente proporzionale alla velocità
• criteri che tengano in considerazione il carico corrente della rete sono difficili da considerare

120-instradamento-02 copyright @2023 g. di battista, m.patrignani

Qualità degli algoritmi di instradamento

Robustezza e adattabilità

• rispetto alle variazioni di topologia
• in una rete di grandi dimensioni possono esserci frequentemente guasti alle linee e/o ai router

Stabilità degli algoritmi

• se non cambia la topologia non devono cambiare i cammini
• a fronte di una variazione di topologia occorre convergere rapidamente ad un nuovo instradamento stabile

Equità e economicità

• nessun nodo deve essere privilegiato o danneggiato
• costi ridotti di configurazione e manutenzione dei protocolli di routing

120-instradamento-02 copyright @2023 g. di battista, m.patrignani

Algoritmi di instradamento

Difficoltà nella scelta di un algoritmo

• i criteri sono talvolta contrastanti
• esempio: minimizzare il ritardo di pacchetti e massimizzare l'utilizzo delle linee
• gli algoritmi complessi possono comportare configurazioni difficili
• le spese per il personale di gestione aumentano

120-instradamento-02 copyright @2023 g. di battista, m.patrignani

Tipi di algoritmi di instradamento

Algoritmi statici

• criteri fissi di instradamento, indipendenti dallo stato della topologia

Algoritmi dinamici

• instradamento in funzione dello stato della topologia e/o del carico

algoritmi di instradamento algoritmi statici algoritmi dinamici 120-instradamento-02 copyright @2023 g. di battista, m.patrignani

Rapporto tra routing statico e dinamico

Parte periferica

topologia ad albero parte centrale topologia fortemente magliata routing statico routing dinamico 120-instradamento-02 copyright @2023 g. di battista, m.patrignani

Tassonomia degli algoritmi di instradamento

algoritmi di instradamento algoritmi statici algoritmi dinamici static routing flooding routing isolato routing centralizzato routing distribuito hot potato backward learning distance vector link state packet 120-instradamento-02 copyright @2023 g. di battista, m.patrignani

Algoritmi statici di instradamento

Static routing

• su ogni nodo c'è una tabella che contiene, per ogni nodo da raggiungere, la linea da usare e la tabella è compilata dall'amministratore di sistema
• che è chiamato ad intervenire in presenza di guasti

Variante quasi-statica

• l'amministratore di sistema fornisce più alternative in ordine di priorità, che vengono scelte in funzione dello stato della rete

120-instradamento-02 copyright @2023 g. di battista, m.patrignani

Static routing

1 Lg L2 Lj A - L3 LG LA L5 indirizzo prima scelta seconda scelta 156.128.16.0/24 L1 L2 128.201.0.0/16 L3 145.200.0.0/16 L5 L3 12. 0.0.0/8 LA 0.0.0.0/0 L7 Lg 120-instradamento-02 copyright @2023 g. di battista, m.patrignani

Algoritmi statici di instradamento

Flooding

• ogni pacchetto viene ritrasmesso su tutte le linee, salvo quella da cui è arrivato

Varianti del flooding

• selective flooding: si ritrasmette solo su un insieme di linee selezionato
• is-is (iso 10598)
• scarto dei pacchetti troppo vecchi
• pacchetti con "age counter" a bordo
• scarto di un pacchetto al suo secondo passaggio su un nodo
• le varianti necessitano di memorie estese e di identificatori di pacchetto

120-instradamento-02 copyright @2023 g. di battista, m.patrignani

Algoritmi dinamici di instradamento

algoritmi dinamici routing isolato routing centralizzato routing distribuito hot potato backward learning distance vector link state packet

Routing isolato

• ogni intermediate system (is) calcola in modo indipendente le proprie tabelle, senza consultare gli altri is

Hot potato routing

• il pacchetto viene inviato sulla linea con coda più breve
• interesse solo teorico

120-instradamento-02 copyright @2023 g. di battista, m.patrignani

Algoritmi dinamici di instradamento

Backward learning

• la linea di uscita del pacchetto viene inferita in base agli indirizzi mittente dei pacchetti in ingresso
• esempio: il filtering dei bridge ieee 802.1D al livello 2

Raffinamento del backward learning

• aggiunta di un campo nei pacchetti che specifica il costo, incrementato ad ogni attraversamento di is - in questo modo si possono mantenere in ogni is più alternative ordinate per costo - svantaggio: si imparano solo le migliorie e non i peggioramenti (perche? tempo di scadenza delle entry!)
• quando la destinazione è ignota si fa flooding
• può generare cicli
• si accoppia usualmente con il calcolo di uno spanning tree

120-instradamento-02 copyright @2023 g. di battista, m.patrignani

Algoritmi dinamici di instradamento

Routing centralizzato

• presuppone l'esistenza di un routing control center (rcc) che conosce la topologia della rete
• ipotesi spesso non realistica

Il routing control center

• riceve da tutti i nodi informazioni sulla topologia
• calcola le tabelle di instradamento
• le distribuisce

Problemi del routing centralizzato

• traffico intenso intorno al rcc
• affidabilità

120-instradamento-02 copyright @2023 g. di battista, m.patrignani

Algoritmi dinamici di instradamento

routing distribuito distance vector link state packet

Routing distribuito

• non esiste un rcc, ma le sue funzionalità sono svolte da tutti gli is
• due principali paradigmi - distance vector - dico ai miei vicini tutto ciò che so del mondo - link state packet - dico a tutto il mondo ciò che so dei miei vicini

120-instradamento-02 copyright @2023 g. di battista, m.patrignani