Tutto quello che devi sapere sul routing

Tutto quello che devi sapere sul routing

Quando un terminale A manda un pacchetto a un terminale B,questo pacchetto attraverso tanti router nella rete. Come fa ogni router che riceve il pacchetto a determinare qual'è il prossimo router più vicino al terminale B ? Questa domanda pone in modo molto semplice il problema del routing.

Prima di andare nello specifico,vediamo cosa fa il router. Il router

Elabora l’indirizzo dei pacchetti IP e determina la subnet in cui si trova l’host

di destinazione.

1. se l’host di destinazione si trova in una delle subnets a cui il router `e
   direttamente connesso affida il pacchetto alla subnet per la consegna;
2. altrimenti determina il router successivo verso cui instradare il pacchetto. L'obbiettivo è di determinare il percorso migliore per ogni terminale possibile.

Il routing è composto da due elementi:

1. Un protocollo di routing per costruire la Routing Table. Viene eseguito periodicamente a prescindere dai pacchetti dati.
2. Un algoritmo di switching, che si applica ad ogni pacchetto in transito.

Una routing table è una tabella che permette di determinare dove mandare il pacchetto analizzando il suo indirizzo ip di destinazione.

In questo articolo,vedremmo gli algoritmi di routing con i protocolli che gli implementano.

Algoritmi di routing

Distance Vector:

Questo algoritmo locale e dinamico è un implementazione di BellMan Ford distribuita. Ogni router mantiene una tabella che dice dove mandare un pacchetto diretto verso uno specifico router e quanto costa questo trasferimento. Quindi la tabella da tre informazioni: destinazione,costo e prossima fermata. Per avere queste informazioni su tutte le destinazioni della rete,Ogni router misura la distanza o costo (secondo una metrica che può includere vari fattori) che lo separa dai nodi adiacenti e riceve la stessa informazione dai nodi vicini .Utilizzando l'algoritmo di Bellman-Ford con i suoi dati e quelli dei nodi adiacenti, il router costruisce una tabella che associa ad ogni destinazione conosciuta: la stima della distanza che lo separa dalla destinazione e il primo passo del percorso calcolato.Periodicamente ogni router manda un aggiornamento ai suoi vicini. Un aggiornamento è una lista di coppie (destinazione,distanza) cioè tutta la tabella di routing.

Il problema con quest'algoritmo resta la formazione di cicli all'interno dei percorsi calcolati. Ci sono varie alternative per evitare la formazione di cicli. Per esempio Split Horizon che segue questa regola:

Quando mandi un aggiornamento al router A,non specificare le destinazioni che raggiungi tramite A.

Un altro svantaggio è la propagazione di un informazione errata attraverso la rete nel caso di un malfunzionamento di un router per esempio.

Link State

Questo è un algoritmo basato sullo stato dei collegamenti della rete che implementa al suo interno Dijkstra.

La strategia usata è quella di mandare dei messaggi a tutti i router (non solo i vicini). I messaggi tratta solo di informazioni sui collegamenti diretti(non di tutta la tabella di routing).

I messaggi sono chiamati Link state Packet e sono composti di un ID (indentifica il nodo che manda il pacchetto),il costo del collegamento a tutti i nodi direttamente connessi a lui,un numero di sequenza e un Time-To-Live (durata di vita del pacchetto).

Il numero di sequenza serve a sapere se un pacchetto è recente o meno rispetto a pacchetti ricevuti in precedenza.

Ogni nodo memorizza i pacchetti ricevuti e costruisce una mappa completa e aggiornata della rete: il Link State Database.

A questo punto ogni router usando l'algoritmo Dijkstra single shortest Path sugli informazioni ottenuti dagli altri nodi calcola il percorso a più basso costo partendo da se stesso.

Quindi in questo caso la topologia dell'intera rete è conosciuta.

È possibile costruire la tabella di routing di un nodo memorizzando per ciascuna destinazione il nodo successivo sul cammino a costo minimo.

Vantaggi e svantaggi

L'utilizzo di un algoritmo di routing Link State, presenta diversi vantaggi:

• può gestire reti composte da un gran numero di nodi;

• converge rapidamente al cammino minimo;

• difficilmente genera cammini ciclici;

• è facile da comprendere poiché ogni nodo ha la mappa della rete;

Il principale svantaggio di un algoritmo Link State è la complessità di realizzazione, anche dovuta alla notevole capacità di memoria ed elaborazione richiesti.

Ora vediamo i protocolli di routing.

Protocolli di routing.

Ci sono 2 grande categorie di routing che hanno a che vedere con l'organizzazione delle reti di internet:Interior Gateway Protocol e Exterior Gateway protocol. Internet è fatta di più sotto reti(AS:autonomous System) connesse fra loro. Interior Gateway Protocol raggruppa l'insieme dei protocolli che si occupa del routing interno a un AS. Exterior Gateway protocol si occupa del routing esterno ad un AS cioè fra due router di bordo .

Interior Gateway Protocol

RIP(routing information protocol)

Il Routing Information Protocol (RIP) è molto usato su reti locali ed aiuta i router ad adattarsi dinamicamente ai cambiamenti dei collegamenti di rete, scambiandosi informazioni riguardo a quali reti possono raggiungere e quanto siano lontane. Il RIP è un'implementazione del Distance Vector che impiega il conteggio dei numeri di passi (hop count) come metrica di routing. Il massimo numero di hop permessi è 15. Ogni router RIP trasmette di default, ogni 30 secondi, la propria tabella completa di routing a tutti i vicini direttamente collegati, generando grandi quantità di traffico di rete. Opzionalmente può utilizzare un meccanismo di ottimizzazione denominato split horizon.

E da notare che il basso numero di hop impone un limite alla grandezza della rete. D'altra parte, è molto facile da configurare.

OSPF(open shortest path first)

Il protocollo Open Shortest Path First(OSPF) è un protocollo, che gestisce le tabelle di routing in una rete con il metodo del Link State. Questo standard è open (aperto) nel senso che è un protocollo non proprietario. Il protocollo utilizza un metodo di instradamento che non si differenzia sostanzialmente dal Link State, ma aggiunge delle altre proprietà:Autenticazione dei messaggi, Bilanciamento del carico,e Aggiunta di un ulteriore grado di gerarchia nei domini.

Inizializzazione del protocollo:

• Inizializzazione e controllo (attraverso livelli inferiori) del funzionamento delle interfacce
• Si inviano pacchetti Hello in broadcast per acquisire le informazioni sui router vicini
• Si ricevono i pacchetti Hello dei vicini
  • I pacchetti Hello vengono anche usati per testare il funzionamento di link (keep alive)

Funzionamento del protocollo:

• i router
  • formano i Link State Advertisement (LSA) che contengono una lista delle reti adiacenti con i relativi costi di raggiungimento
  • gli LSA sono trasmessi a tutti gli altri router
• tutti i router della rete hanno lo stesso insieme di dati e quindi possono costruire lo stesso grafo pesato della rete
• il grafo di rete è utilizzato per determinare i cammini ottimi e quindi l’instradamento

Exterior Gateway Protocol

Border Gateway Protocol

Per stabilire una route i router BGP si scambiano informazioni riguardanti la

raggiungibilità di una rete e una serie di attributi relativi al link (o ai link) tra i

due AS coinvolti:

Weight (prop. Cisco)

E’ un attributo locale (interno ad un router).

Non `e propagato (advertised).

In caso di multipath, viene preferita la route con maggior weight.

Local preference

E’ usato per scegliere la strada di uscita preferita tra due o più router.

In caso di multi-route, viene preferita la route con maggior peso.

Multi-exit discriminator (MED) o metric attribute

MED

E’ usato per suggerire la strada di ingresso preferita tra due o pi `u router.

In caso di multi-route, viene preferita la route con minor peso.

Origin

E’ usato per classificare il modo in cui BGP ha appreso una route.

Le route sono divise in:

IGP - la route e generata da un protocollo IGP ed `e interna all’AS che la

propaga

EGP - la route e stata appresa attraverso un protocollo EGP

Incomplete - la route e di origine sconosciuta o appresa tramite altra via

La classificazione `e usata per la scelta della tabella di routing, ovviamente

preferendo le prime alle altre: IGP >EGP >Incomplete

AS path

usato per determinare i loop:

Ogni router traversato viene aggiunto ad una lista ordinata.

Vengono scartate tutte le routes che contengano loops.

Next hop

usato per indicare il next hop (numero IP del router che fa

l’advertising)

Community

E’ usato per raggruppare destinazioni (comunità) per le quali le decisioni di

routing debbano subire speciali trattamenti.

Per definire le comunità si usano Route maps.

Terminiamo l'articolo dicendo che il RIP è un protocollo molto usato ma è spesso sostituito dal OSPF soprattutto per reti molto grandi.

Grazie per l'attenzione

Riferimenti e approfondimenti:

Slide del Professore Peccorella dell'università degli studi di Firenze

Articoli presi su internet: Wikipedia

Modalità di commutazione dell'informazione

Nelle grande reti come internet,ci sono più sotto reti che sono connesse fra di loro con degli switch (apparecchiatura di rete capace di gestire la comunicazione tra qualsiasi due nodi terminali). Queste reti si chiamano reti a commutazione.

In questo articolo analizzeremo 3 modalità di commutazione:circuito,pacchetto e messaggio.

1 Commutazione a pacchetto

Funzionamento:

Per comunicare un terminale deve chiedere una connessione.

Gli switch della rete riservano dei canali di comunicazione creando cosi un circuito. Il terminale sorgente manda i dati che usufruiranno il circuito creato appositamente. Dopo di che si chiude la comunicazione alla fine del trasferimento cosi i canali riservati in precedenza sono liberati.

Struttura:

Nella commutazione a pacchetto ci sono 3 fasi:

-setup Fase in cui si ricerca il percorso migliore fra sorgente A e destinazione B (End-to-End)

-Utilizzo Fase durante la quale il messaggio è mandato da A a B. Il collegamento è mantenuto e controllato

-Reset o Fine Utilizzo è la fase in cui il collegamento viene chiuso.

I diversi ritardi sono creati dal tempo di setup e di chiusura più il tempo dell'attesa dell'arrivo dei dati.

Questa modalità è usata quando la richiesta di connessione è frequente e la fase di utilizzo dura di più rispetto alle altre.

Lo svantaggio è che non c'è nessun punto di salvataggio nei nodi intermedi.

Applicazione

La rete telefonica nello strato fisico usa la commutazione a circuito. Basta pensare alla modalità di comunicazione. L'utente A chiama (setup) quando i due utenti sono collegati

si possono mandare messaggi vocali (Fase utilizzo) e alla fine si riagganciare (Chiusura)

2 Commutazione a Pacchetto

Principio:

In questa modalità i dati sono divisi in pacchetti di informazione che vengono poi mandati attraverso la rete uno alla volta.

Ci sono due implementazioni della commutazione a pacchetto : circuito virtuale e datagram

1. Commutazione a Datagram

I pacchetti non devo seguire un percorso fisso. Non c'è bisogno di richiedere la connessione. Non c'è prenotazione dei canali di comunicazione che invece vengono allocate dinamicamente. I pacchetti possono arrivare fuori sequenza. Possibilità di lavoro in parallelo cioè un terminale può mandare dati ricevendone altri contemporaneamente il che fa risparmiare un bel po di tempo.

Esempio di una rete che usa questa modalità di commutazione è internet che la implementa nello strato di rete.

2. Commutazione a circuito virtuale

Questa modalità è una via di mezzo fra la commutazione a circuito e quella a datagram.

Come nella commutazione a datagram ,i dati sono suddivisi in pacchetti.

Come nella commutazione a circuito ,ci sono tre fasi setup,utilizzo e fine utilizzo e quindi i pacchetti seguono un percorso fisso. Non c'è il problema dell'ordinazione dei pacchetti all'arrivo.

Per i canali di comunicazione possono essere :

- prenotati come nella commutazione a circuito.

- allocati dinamicamente come nella commutazione a datagram.

Il circuito è detto virtuale perché i suoi rami e collegamenti sono condivisi da altri flussi.

3 Commutazione a Messaggio

In questa modalità il messaggio è inviato interamente su base LINK-to-LINK senza fase di instaurazione e chiusura di connessione.

Si usa questa modalità quando la richiesta di connessione non è frequente e i dati da mandare sono limitati.

Essendo nello strato di rete ,c'è la possibilità di ricevere bit errati.

In conclusione si usa una modalità di commutazione nelle reti a commutazione in base ai requisiti della rete.

Riferimenti e Approfondimenti:

Slide del professore Romano Fantacci dell'universita degli studi di Firenze

Copyright immagini : Mc-Graw Hill

Tutto quello che devi sapere su Ethernet

Con Ethernet , si intende una famiglia di tecnologie per reti locali (LAN) sviluppato inizialmente al livello sperimentale da Robert Metcalfe e David Boggs (suo assistente) allo Xerox PARC e poi ricoperta dalla norma IEEE 802.3.

Il principio di una rete Ethernet è semplice:

Tutti i terminali della rete Ethernet sono connessi allo stesso mezzo di comunicazione, costituito da cavi cilindrici.

Quest’articolo parlerà degli elementi di una rete Ethernet, della sua topologia, del suo Funzionamento. 

componenti di una rete Ethernet:

La rete Ethernet è composta dei nodi della rete e del mezzo trasmissivo.

I nodi sono divisi in due classi:

        1-       Gli apparati terminali: Elementi che sono o la sorgente o la destinazione di un Frame d’informazioni. Come esempio abbiamo PC, Notebook, server, oppure stampanti.

2-       Gli apparati di comunicazione: Elementi intermediari che ricevono e poi spediscono Frame d’informazione attraverso la rete. Come esempio abbiamo i repeater, switch oppure modem.

Il mezzo trasmissivo è comune e definisce percorsi per i segnali elettrici attraverso la rete. Può essere un cavo doppio o un cavo a fibra ottica.

Topologia di una rete Ethernet

Come si è detto all'introduzione un solo mezzo permette di trasportare i frame da una sorgente a una destinazione. Questa ci fa subito pensare a una topologia a bus coassiale.

Questo rappresenta solo la topologia logica della rete cioè, il percorso logico che le informazioni seguono per arrivare a destinazione. Nelle prime reti Ethernet la topologia elettrica corrispondeva anche alla topologia fisica, cioè al modo in cui fisicamente le varie stazioni erano collegate tra loro. In seguito con l’adozione di apparati di comunicazione come repeater o switch, la topologia fisica è cambiata.

Ora vedremo le strutture più semplici che si trovano combinate nelle topologie ethernet fisiche in generale.

La connessione Punto-a-Punto

Rappresenta la struttura più semplice e coinvolge due elementi. Può essere del tipo

AT-a-AT, AT-a-AC oppure AC-a-AC

La struttura doppio bus coassiale.

E una struttura molto usata singolarmente dalle reti ethernet semplici.

Struttura a Stella

Questa struttura si ritrova nelle reti ethernet più complesse.

In queste strutture gli apparati di comunicazione vanno dai repeater (per aumentare la lunghezza dei segmenti di rette) agli switch (per collegare più reti ethernet in un nodo).

     Funzionamento della rete Ethernet

Ethernet fornisce al livello di rete un servizio senza connessione in cui l’informazione è trasmessa in modalità broadcast. Tutti i terminali ricevono l’informazione e solo il terminale destinatario dopo verifica legge tutto il pacchetto mandato.

Non c’è nessun sistema che gestisce l’accesso al mezzo trasmissivo. Il sistema di gestione delle collisioni e dell’accesso condiviso del canale trasmissivo è interno a ogni apparato di rete e si chiama CSMA/CD.

Carrier Sense: ascolto del canale (Ogni Terminale ascolta in continuo il canale per determinare intervalli fra la trasmissione dei Frame.)

Multile Access: accesso multiplo

Collision Detecion: rilevamento di collisione

Ecco come avviene la comunicazione nei diversi scenari possibili: 

·         Ciascun terminale verifica che non via siano comunicazioni sulla linea prima di emettere.

·         Se due terminali emettono contemporaneamente, allora vi sarà collisione (cioè più trame di dati si trovano sulla linea allo stesso momento).

·         I due terminali interrompono le loro comunicazioni e aspetto per un periodo aleatorio, poi sarà la prima che avrà terminato questo periodo a emettere di nuovo.

Questo principio è basato su più limiti:

·         I pacchetti di dati devono avere una dimensione massima.

·         Deve esserci un tempo di attesa fra le due emissioni.

Il tempo di attesa varia secondo la frequenza delle collisioni:

·         Dopo la prima collisione, un terminale aspetta per una data unità di tempo.

·         Dopo la seconda collisione, il terminale aspetta per due unità di tempo.

·         Dopo la terza collisione, il terminale aspetta per quattro unità di tempo.

Dopo ogni trasmissione di un terminale, tutti i terminali avranno di nuovo un’opportunità di accesso al canale con priorità uguale.

Confronto del modello IEEE 802.3 con il modello  OSI

I livelli ethernet sono MAC –Client, MAC e livello fisico.

Il MAC-Client può essere:

• Logical Link Control (LLC), che fornisce un’interfaccia fra il livello MAC e I livelli superiori.
• Un Bridge o Switch, che fornisce un’interfaccia LAN-a-LAN fra rei che usano lo stesso protocollo (Esempio Ethernet-a-Ethernet) oppure protocolli diversi (Esempio Ethernet-a-Token Ring).          

Il Livello Mac ha la responsabilità di:

• Encapsulazione dei dati, incluso assemblaggio e suddivisione del frame prima e dopo la trasmissione, e del controllo e rilevamento di errori dopo la ricezione.
• Accesso al canale trasmissivo, incluso l’inizializzazione del frame e la manutenzione in caso d’insuccesso della trasmissione.

Il livello fisico si occupa della trasmissione dei dati, della cifratura del segnale del tipo di mezzo trasmissivo connettendo due nodi.

Terminiamo l’articolo con i vantaggi che offre la rete ethernet:

1. Facile da capire, implementare e gestire.
2. Costa poco rispetto altre tecnologie LAN.
3. Grande flessibilità nell'estensione e l’installazione della rete.
4. Funziona bene e genera pochi problemi.

Riferimenti e approfondimenti:

Articoli su Ethernet nei siti:

javvin.com

kiokea.net

wikipedia.com

howstuffworks.com

cisco.com

Appunti del prof Necci su Ethernet (uniroma3)