{"id":922,"date":"2021-08-03T11:16:26","date_gmt":"2021-08-03T09:16:26","guid":{"rendered":"https:\/\/il-mio-ip.it\/?page_id=922"},"modified":"2021-08-03T22:26:05","modified_gmt":"2021-08-03T20:26:05","slug":"algoritmi-di-routing","status":"publish","type":"page","link":"https:\/\/il-mio-ip.it\/?page_id=922","title":{"rendered":"Algoritmi di routing"},"content":{"rendered":"\n<div class=\"wp-block-cover alignfull has-background-dim has-parallax has-background-gradient\" style=\"background-image:url(https:\/\/il-mio-ip.it\/wp-content\/uploads\/2021\/08\/servizi.jpg);min-height:380px;aspect-ratio:unset;\"><span aria-hidden=\"true\" class=\"wp-block-cover__gradient-background\" style=\"background:linear-gradient(100deg,rgb(21,50,67) 0%,rgb(26,108,122) 100%)\"><\/span><div class=\"wp-block-cover__inner-container is-layout-flow wp-block-cover-is-layout-flow\">\n<h1 class=\"has-text-align-center has-white-color has-text-color wp-block-heading\">Algoritmi di routing<\/h1>\n<\/div><\/div>\n\n\n\n<div style=\"height:50px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><span style=\"color: #0693e3;\" class=\"ugb-highlight\"><strong><strong><strong>Algoritmi di routing<\/strong><\/strong><\/strong><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Algoritmi per il routing al volo\/forwarding sono i seguenti:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Routing by Network Address<\/li><li>Label Swapping<\/li><li>Source Routing<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Ogni architettura protocollare tipicamente ne utilizza pi\u00f9 di uno.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Fasi del forwarding<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">All\u2019arrivo del pacchetto si seleziona la porta d\u2019uscita, si effettua lo switching (ovvero la commutazione) su tale porta e quindi si procede alla sua trasmissione.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Nel routing proattivo invece ci sono diversi algoritmi, classificati in due grosse categorie:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Algoritmi non adattativi (statici)<\/li><li>Algoritmi adattativi (dinamici)<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Nel routing statico i percorsi per l\u2019inoltro dei pacchetti sono determinati a priori (ed eventualmente modificati all\u2019occorrenza) dall\u2019amministratore della rete, che si occupa quindi di costruire la tabella di routing. Il principale svantaggio del routing statico \u00e8 la sua impossibilit\u00e0 a reagire autonomamente ad eventuali guasti o cambiamenti topologici della rete. Per ovviare in parte a questo inconveniente, nelle situazioni di routing statico, si prevedono a priori diversi percorsi per raggiungere un altro router della rete in modo da avere diverse possibilit\u00e0 per l\u2019instradamento in caso di problemi ai nodi.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Nel routing dinamico i percorsi per l\u2019inoltro dei pacchetti sono individuati da un determinato protocollo di routing che viene aggiornato in maniera automatica in funzione delle modifiche di topologia o di traffico. Questo sistema risulta senz\u2019altro pi\u00f9 complesso, ma decisamente pi\u00f9 efficiente. Per implementarlo occorre che i router si scambino informazioni sullo stato della rete e dei collegamenti.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Algoritmi non adattativi \u2013 Statici<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Con gli algoritmi statici l\u2019amministratore ha il pieno controllo sulle politiche di instradamento, ma questo algoritmo presenta il grave problema di non adattarsi ad eventuali cambiamenti topologici. I principali sono i seguenti:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Fixed Directory Routing<\/strong>: noto come algoritmo di routing statico che necessita di configurazione manuale.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Flooding<\/strong>: algoritmo selettivo che ha diversi derivati.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Algoritmi adattativi \u2013 Dinamici<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Gli algoritmi adattativi possono prevedere diverse tipologie di routing:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Routing centralizzato<\/li><li>Routing isolato<\/li><li>Routing distribuito (algoritmi Distance Vector e Link State)<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Routing Centralizzato<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Il routing centralizzato utilizza un Routing Control Center (RCC) che calcola e distribuisce le tabelle di routing e che per funzionare ha bisogno di conoscere le informazioni di tutti i nodi della rete.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Questo tipo di routing ottimizza le prestazioni, semplifica il troubleshooting e determina un traffico di rete sostenuti nelle vicinanze dell\u2019RCC. Tuttavia, la presenza dell\u2019RCC come punto fondamentale del sistema ne fa un collo di bottiglia e pu\u00f2 determinare, in caso di malfunzionamento, un blocco di tutta la rete. Tale sistema risulta quindi inadeguato per le reti dinamiche.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Routing Isolato<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Nel routing isolato, ogni nodo decide in maniera indipendente i percorsi che dovranno intraprendere i pacchetti. In questa modalit\u00e0 di routing non c\u2019\u00e8 scambio di informazioni tra i nodi della rete.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Questa modalit\u00e0 unisce i vantaggi del routing isolato e di quello centralizzato:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">i router collaborano nello scambio di informazioni sulla connettivit\u00e0;<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">ogni router decide in maniera autonoma ma coerente;<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Routing Distribuito<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Nel routing distribuito ogni nodo calcola in maniera autonoma le proprie tabelle di instradamento, basandosi su informazioni locali o distribuite, ovvero utilizzando informazioni relative ad altri nodi della rete. Nel caso di routing distribuito deve essere implementato un meccanismo di scambio delle informazioni, ovvero un protocollo.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Algoritmo di Distance Vector<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Questo algoritmo si basa sulla teoria dei grafi e calcola i vettori delle distanze tra i vari nodi. Ogni nodo, che solitamente \u00e8 costituito da un router, pu\u00f2 essere un firewall, un host o comunque un qualsiasi dispositivo o apparato di rete in gradi di replicare i pacchetti.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Il Distance Vector \u00e8 un algoritmo di tipo dinamico e tiene conto del carico istantaneo della rete. In sintesi, ogni nodo misura la distanza che lo separa dai nodi adiacenti, secondo una metrica che include vari fattori, ricevendo i dati dai nodi vicini. A partire da tali dati, usando l\u2019algoritmo di Bellman-Ford, il nodo costruisce una tabella contenente delle informazioni su ogni destinazione (ovvero su ogni nodo) a lui conosciuto.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Queste informazioni sono:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>La stima della distanza che lo separa dalla destinazione;<\/li><li>Il primo passo del percorso calcolato;<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Tutti i nodi della rete aggiorneranno periodicamente le misure di distanza dai nodi adiacenti scambiandosi informazioni con i nodi vicini.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Vantaggi<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Questo algoritmo \u00e8 stato uno dei primi ad essere utilizzati per i suoi meccanismi di implementazione ed aggiornamento molto semplici, ma presenta numerosi limiti sulle reti di grandi dimensioni.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Svantaggi<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Principale inconveniente di questo algoritmo \u00e8 che ogni nodo memorizza nella propria tabella solo il primo passo dei percorsi. Questo implica che se, ad esempio, il nodo A pubblica un percorso verso il nodo C, i nodi vicini di A non possono sapere se sono stati inclusi da A nel percorso che esso ha pubblicato fino a C, quindi si potrebbero creare dei cicli e quando un collegamento si interrompe si potrebbe verificare una situazione di count-to-infinity, ovvero dei tentativi infiniti di instradare il pacchetto.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Ad esempio, se nel percorso da A a C si interrompe il collegamento con B, il nodo B, al momento di aggiornare la propria tabella, vedr\u00e0 che non pu\u00f2 pi\u00f9 raggiungere A tramite il collegamento diretto. Tuttavia, il nodo C, che non conosce la situazione, \u00e8 convinto di poter ancora raggiungere A e quindi mantiene nella tabella il suo percorso per raggiungere A in due passi (attraverso B). B, quindi potrebbe tentare di raggiungere A tramite C in tre passi, senza mai riuscirci.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Questa situazione subisce un progressivo peggioramento sulle reti di grandi dimensioni dove entrano in gioco distanza sempre maggiori.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Alcune soluzioni parziali sono le seguenti:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><strong>Split Horizon<\/strong>: un router, quando inoltra la propria tabella di routing ad un altro router vicini, omette di specificare i percorsi che ha appreso dal vicino al quale sta trasmettendo la propria tabella.<\/li><li><strong>Poison Reverse<\/strong>: in questa modalit\u00e0 un router invier\u00e0 al proprio vicino anche le informazioni che ha appreso da lui, ma con una metrica infinita, ovvero comunicando a quel router che per lui la destinazione \u00e8 sempre raggiungibile.<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Algoritmo di Link State<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">In questo algoritmo tutti i costi dei collegamenti dell\u2019intera topologia della rete sono noti a tutti i router della rete, quindi ogni singolo router acquisisce le informazioni sullo stato dei collegamenti adiacenti e anche sullo stato dei collegamenti di tutti gli altri.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Si tratta quindi di una vera e propria mappa distribuita della rete, che viene regolarmente aggiornata.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Il funzionamento di questo algoritmo \u00e8 basato sul fatto che ogni router descrive compiutamente la topologia della rete intorno a lui e invia questa descrizione a tutta la rete mediante opportuni pacchetti detti LSP, ovvero Link State Packet. Il pacchetto LSP contiene quindi tutte le informazioni necessarie a costruire la topologia della rete come: stato di ogni link connesso al router, identit\u00e0 di ogni vicino connessi, costo del link, numero di sequenza, checksum, lifetime. Un LSP viene generato periodicamente oppure quando viene rilevata una variazione nella topologia della rete. Il pacchetto LSP \u00e8 trasmesso su tutti i link del router e tutti i router del dominio di routing ricevono gli LSP, ottenendo quindi le informazioni necessaria a costruire la topologia completa della rete.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Dal momento che ogni router riceve i pacchetti LSP da tutti gli altri, potr\u00e0 mettere insieme le varie descrizioni per costruire una propria mappa della rete.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Mediante l\u2019algoritmo di Dijkstra (detto anche algoritmo Shortest Path First) ogni nodo \u00e8 quindi in grado di valutare sulla mappa il percorso migliore da far compiere ai pacchetti da inviare per fargli raggiungere una destinazione della rete.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Vantaggi<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">L\u2019algoritmo di Link State \u00e8 quindi caratterizzato da un\u2019elevata stabilit\u00e0 garantendo quindi tempi brevi di convergenza, ovvero i link state si propagano velocemente e non hanno bisogno di nessuna elaborazione prima dell\u2019inoltro. Inoltre, ha una bassissima probabilit\u00e0 di routing loop e genera un traffico di routing limitato assieme ad un basso uso di memoria.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Queste caratteristiche sono conseguenza dell\u2019algoritmo di Dijkstra. Questo algoritmo risolve lo stesso problema di quello di Bellman-Ford, ovvero trovare il cammino minimo di un grafo, ma lo fa in un tempo computazionalmente inferiore, presentando quindi una minore complessit\u00e0 computazionale (L*log(N) per Dijkstra contro N2 di Bellman-Ford, dove N=nodi e L=link).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Altri vantaggi sono la semplicit\u00e0 nel rilevare eventuali guasti, dal momento che tutti i router hanno la stessa tabella.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Svantaggi<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Il suo principale svantaggio \u00e8 l\u2019elevata complessit\u00e0 di implementazione, a causa dell\u2019utilizzo del selective flooding utilizzato per l\u2019invio dei pacchetti LSP, e della conseguente elevata complessit\u00e0 dei protocolli che devono implementare questo algoritmo.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Nel Selective Flooding ogni pacchetto in arrivo in un nodo viene inviato attraverso ogni collegamento in uscita, tranne quello del nodo che lo ha inviato.<\/p>\n\n\n\n<div class=\"wp-block-group alignfull has-background is-layout-flow wp-block-group-is-layout-flow\" style=\"background-color:#f3f9fb\">\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-7387b849 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/il-mio-ip.it\/guida-al-networking\/routing\/\" data-type=\"page\" data-id=\"919\">&lt;&lt; Routing<\/a><\/h3>\n<\/div>\n\n\n\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<h3 class=\"has-text-align-right wp-block-heading\"><a href=\"https:\/\/il-mio-ip.it\/guida-al-networking\/autonomous-system\/\" data-type=\"page\" data-id=\"925\"><strong><strong>Autonomous System<\/strong> <\/strong>>><\/a><\/h3>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Algoritmi di routing Algoritmi per il routing al volo\/forwarding sono i seguenti: Routing by Network Address Label Swapping Source Routing Ogni architettura protocollare tipicamente ne utilizza pi\u00f9 di uno. Fasi del forwarding All\u2019arrivo del pacchetto si seleziona la porta d\u2019uscita, si effettua lo switching (ovvero la commutazione) su tale porta e quindi si procede alla [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":647,"menu_order":39,"comment_status":"closed","ping_status":"closed","template":"","meta":{"site-sidebar-layout":"right-sidebar","site-content-layout":"plain-container","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"disabled","ast-breadcrumbs-content":"","ast-featured-img":"disabled","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"enabled","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[10],"tags":[],"class_list":["post-922","page","type-page","status-publish","hentry","category-guida-al-networking"],"featured_image_urls_v2":{"full":"","thumbnail":"","medium":"","medium_large":"","large":"","1536x1536":"","2048x2048":""},"post_excerpt_stackable_v2":"<p>Algoritmi di routing Algoritmi di routing Algoritmi per il routing al volo\/forwarding sono i seguenti: Routing by Network AddressLabel SwappingSource Routing Ogni architettura protocollare tipicamente ne utilizza pi\u00f9 di uno. Fasi del forwarding All\u2019arrivo del pacchetto si seleziona la porta d\u2019uscita, si effettua lo switching (ovvero la commutazione) su tale porta e quindi si procede alla sua trasmissione. Nel routing proattivo invece ci sono diversi algoritmi, classificati in due grosse categorie: Algoritmi non adattativi (statici)Algoritmi adattativi (dinamici) Nel routing statico i percorsi per l\u2019inoltro dei pacchetti sono determinati a priori (ed eventualmente modificati all\u2019occorrenza) dall\u2019amministratore della rete, che si occupa&hellip;<\/p>\n","category_list_v2":"<a href=\"https:\/\/il-mio-ip.it\/?cat=10\" rel=\"category\">Guida al Networking<\/a>","author_info_v2":{"name":"admin","url":"https:\/\/il-mio-ip.it\/?author=1"},"comments_num_v2":"0 commenti","_links":{"self":[{"href":"https:\/\/il-mio-ip.it\/index.php?rest_route=\/wp\/v2\/pages\/922","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/il-mio-ip.it\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/il-mio-ip.it\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/il-mio-ip.it\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/il-mio-ip.it\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=922"}],"version-history":[{"count":4,"href":"https:\/\/il-mio-ip.it\/index.php?rest_route=\/wp\/v2\/pages\/922\/revisions"}],"predecessor-version":[{"id":939,"href":"https:\/\/il-mio-ip.it\/index.php?rest_route=\/wp\/v2\/pages\/922\/revisions\/939"}],"up":[{"embeddable":true,"href":"https:\/\/il-mio-ip.it\/index.php?rest_route=\/wp\/v2\/pages\/647"}],"wp:attachment":[{"href":"https:\/\/il-mio-ip.it\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=922"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/il-mio-ip.it\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=922"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/il-mio-ip.it\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=922"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}