Encaminament
L'Encaminament o Enrutament (en anglès: Routing) és la funció de buscar un camí entre tots els possibles en una xarxa de paquets les topologies dels quals posseeixen una gran connectivitat. Atès que es tracta de trobar la millor ruta possible, el primer serà definir què s'entén per "millor ruta" i en conseqüència quin és la "mètrica" que s'ha d'utilitzar per mesurar-la.
L'encaminament en sentit estricte es refereix l'encaminament IP i s'oposa al bridging. L'encaminament assumeix que les adreces de xarxa estan estructurades i que adreces similars impliquen proximitat dins de la xarxa. Les adreces estructurades permeten una sola entrada de taula de rutes per representar la ruta a un grup de dispositius. A les xarxes grans, l'adreçament estructurat (encaminament en sentit estricte) supera a l'adreçament no estructurat (bridging). L'encaminament s'ha convertit en la forma dominant d'adreçament en Internet. El bridging encara s'usa àmpliament a les xarxes d'àrea local.
Paràmetres
[modifica]Mètrica de xarxa
[modifica]Pot ser, per exemple, el nombre de salts necessaris per anar d'un punt a un altre. Encara que aquesta no és una mètrica òptima, ja que suposa “1” per a tots els enllaços, és senzilla i sol oferir bons resultats.
Un altre tipus de mètrica és el mesurament del retard de trànsit entre nodes veïns, en la qual la mètrica s'expressa en unitats de temps i els seus valors no són constants sinó que depenen del tràfic de la xarxa.
La mètrica simplement és un valor que prenen els diferents protocols d'encaminament per poder determinar com és la millor ruta cap a una xarxa de destinació. No és difícil trobar-se amb situacions on un router tingui més d'un únic camí cap a una xarxa de destinació i, per tant, haurà d'utilitzar algun mètode per determinar com d'aquests camins li convé més. En alguns casos el router determinarà que el millor camí és aquell la distància del qual és menor o en altres casos determinarà que la millor ruta és aquella que té millor amplada de banda. Això va a dependre de qual sigui el protocol d'encaminament que s'estigui utilitzant, ja que cadascun usa una mètrica diferent.
Millor ruta
[modifica]Entenem per millor ruta aquella que compleix les següents condicions:
- Aconsegueix mantenir fitat el retard entre parells de nodes de la xarxa.
- Aconsegueix oferir altes cadències efectives independentment del retard mitjà de trànsit.
- Permet oferir el menor cost.
El criteri més senzill és triar el camí més curt, és a dir la ruta que passa pel menor nombre de nodes. Una generalització d'aquest criteri és el de “cost mínim”. En general, el concepte de distància o cost d'un canal és una mesura de la qualitat de l'enllaç basat en la mètrica que s'hagi definit. En la pràctica s'utilitzen diverses mètriques simultàniament.
Encaminament en xarxes de circuits virtuals i de datagrames
[modifica]Quan la xarxa de commutació de paquets funciona en manera circuit virtual, generalment la funció d'encaminament estableix una ruta que no canvia durant el temps de vida d'aquest circuit virtual. En aquest cas l'encaminament es decideix per sessió.
Una xarxa que funciona en manera datagrama no té el compromís de garantir el lliurament ordenat dels paquets, per la qual cosa els nodes poden canviar el criteri d'encaminament per a cada paquet que ha de manar. Qualsevol canvi en la topologia de la xarxa té fàcil solució quant a encaminament es refereix, una vegada que l'algorisme corresponent hagi descobert el nou camí òptim.
Classificació dels mètodes d'encaminament
[modifica]Els algorismes d'encaminament poden agrupar-se en:
Deterministes o estàtics
[modifica]No tenen en compte l'estat de la subxarxa en prendre les decisions d'encaminament. Les taules d'encaminament dels nodes es configuren de forma manual i romanen inalterables fins que no es torna a actuar sobre elles. Per tant, l'adaptació en temps real als canvis de les condicions de la xarxa és nul·la.
El càlcul de la ruta òptima és també fora de línia (off-line) pel que no importa ni la complexitat de l'algorisme ni el temps requerit per a la seva convergència. Ex: algorisme de Dijkstra.
Aquests algorismes són rígids, ràpids i de disseny simple, no obstant això tenen baixa tolerancia a fallades. Ex: si un router o enllaç deixa de funcionar, la connectivitat entre origen i destí pot quedar interrompuda amb facilitat.
Per altra banda, aquests algorismes d'encaminament, pel fet de ser estatics, permeten determinar amb facilitat el comportament de cada paquet a la xarxa (la ruta que cada paquet segueix, els punts de la topologia on hi haurà congestió de paquests,....) i per tant, permeten estimar el temps que triga cada paquet en anar d'un punt de la xarxa a un altre. Aquesta propietat és especialment important en sistemes que executen aplicacions de temps real on determinar els temps de viatge de cada paquet entre origen i destí és rellevant.
Adaptatius o dinàmics
[modifica]Poden fer més tolerants a canvis en la subxarxa tals com a variacions en el tràfic, increment del retard o falles en la topologia. L'encaminament dinàmic o adaptatiu es pot classificar al seu torn en tres categories, depenent d'on es prenguin les decisions i de l'origen de la informació intercanviada:
- Adaptatiu centralitzat: tots els nodes de la xarxa són iguals excepte un node central que és qui recull la informació de control i les dades dels altres nodes per calcular amb ells la taula d'encaminament. Aquest mètode té l'inconvenient que consumi abundants recursos de la pròpia xarxa.
- Adaptatiu distribuït: aquest tipus d'encaminament es caracteritza pel fet que l'algorisme corresponent s'executa per igual en tots els nodes de la subxarxa. Cada node recalcula contínuament la taula d'encaminament a partir d'aquesta informació i de la qual conté en la seva pròpia base de dades. A aquest tipus pertanyen dos dels més utilitzats en Internet que són els algorismes per vector de distàncies i els de estat d'enllaç.
- Adaptatiu aïllat: es caracteritzen per la senzillesa del mètode que utilitzen per adaptar-se a l'estat canviant de la xarxa. La seva resposta als canvis de tràfic o de topologia s'obté a partir de la informació pròpia i local de cada node. Un cas típic és l'encaminament “per inundació” el mecanisme de la qual consisteix a reexpedir cada paquet rebut amb destinació a altres nodes, per tots els enllaços excepte pel qual va arribar.[1][2]
|
Encaminament adaptatiu amb algorismes distribuïts
[modifica]L'encaminament mitjançant algorismes distribuïts constitueix el prototip de model d'encaminament adaptatiu. Els algorismes s'executen en els nodes de la xarxa amb les últimes dades que han rebut sobre el seu estat i convergeixen ràpidament optimitzant les seves noves rutes.
El resultat és que les taules d'encaminament s'adapten automàticament als canvis de la xarxa i a les sobrecàrregues de tràfic. A canvi, els algorismes tenen una major complexitat. Existeixen dos tipus principals d'algorismes d'encaminament adaptatiu distribuït.[3]
Algorismes per “vector de distàncies”
[modifica]Aquests mètodes utilitzen l'algorisme de Bellman-Ford. Cerca la ruta de menor cost pel mètode de cerca indirecta El vector de distàncies associat al node d'una xarxa, és un paquet de control que conté la distància als nodes de la xarxa coneguts fins al moment.
Cada node envia als seus veïns les distàncies que coneix a través d'aquest paquet. Els nodes veïns examinen aquesta informació i la comparen amb la qual ja tenen, actualitzant la seva taula d'encaminament.
Exemples de protocols per vector de distàncies: r. i. p. (versió 1 i 2), IGRP.
Algorismes de “estat d'enllaç”
[modifica]Aquest tipus d'encaminament es basa que cada node arribi a conèixer la topologia de la xarxa i els costos (retards) associats als enllaços, perquè a partir d'aquestes dades, pugui obtenir l'arbre i la taula d'encaminament després d'aplicar l'algorisme de cost mínim (algorisme de Dijkstra) al graf de la xarxa
Els protocols estat d'enllaç inclouen OSPF i IS-IS.
Protocols d'encaminament i sistemes autònoms
[modifica]|
Esquemes d'enrutament de difusió (cast)
|
|---|
|
Unidifusió (unicast)
|
|
|
|
Multidifusió (multicast)
|
|
Difusió àmplia (broadcast)
|
|
Geodifusió (geocast)
|
En Internet, un sistema autònom (AS) es tratar un conjunt de xarxes IP i routers que es troben sota el control d'una mateixa entitat (en ocasions vàries) i que posseeixen una política d'encaminament similar a Internet. Depenent de la relació d'un router amb un sistema autònom (AS), trobem diferents classificacions de protocols:
- Protocols d'encaminament Ad hoc. Es troben en aquelles xarxes que tenen poca o cap infraestructura.
- IGP (Interior Gateway Protocols): intercanvien informació d'encaminament dins d'un únic sistema autònom. Els exemples més comuns són:
- IGRP (Interior Gateway Routing Protocol): la diferència amb la r. i. p. és la mètrica de enrutamiento.
- EIGRP (Enhanced Interior Gateway Routing Protocol): és un protocol de enrutamiento vector-distancia i estat d'enllaç.
- OSPF (Open Shortest Path First): enrutamiento jeràrquic de passarel·la interior.
- RIPv2T (Routing Information Protocol): no suporta conceptes de sistemes autònoms.
- IS-IS (Intermediate System to Intermediate System): protocol d'intercanvi enrutador de sistema intermedi a sistema intermedi.
- EGP (Exterior Gateway Protocol): intercanvien rutes entre diferents sistemes autònoms. Trobem:
Vegeu també
[modifica]- Router
- Estat d'enllaç
- Vector de distàncies
- IGRP
- IS-IS
- OSPF
- RIP
- BGP
- Zebra - Maneja r. i. p., OSPF, MPLS, BGP, etcètera
- Quagga - Desenvolupat a partir de Zebra
Referències
[modifica]- ↑ M. Noormohammadpour; C. S. Raghavendra. «Poster Abstract: Minimizing Flow Completion Times using Adaptive Routing over Inter-Datacenter Wide Area Networks», 2018.
- ↑ M. Noormohammadpour; C. S. Raghavendra. «Minimizing Flow Completion Times using Adaptive Routing over Inter-Datacenter Wide Area Networks», 2018.
- ↑ RFC 3626
- ↑ Error en el títol o la url.«».
Enllaços externs
[modifica]- Comprenent el concepte de mètrica Arxivat 2014-10-31 a Wayback Machine..