IMPORTANT: Per accedir als fitxer de subversion: http://acacha.org/svn (sense password). Poc a poc s'aniran migrant els enllaços. Encara però funciona el subversion de la farga però no se sap fins quan... (usuari: prova i la paraula de pas 123456)

Aquest article fa referència a l'encaminament dinàmic. Consulteu l'article encaminament per a consultar qüestions relatives a encaminament estàtic.

Introducció

En xarxes petites o poc complexes sovint s'utilitzen encaminament estàtic, és a dir la configuració de les taules de rutes es va de forma manual. Aquests tipus d'encaminament és prou bo en xarxes que no canviïn la seva forma (topologia).

En xarxes grans i complexes solen tenir topologies més complexes i que poden canviar ràpidament, succeint modificacions en la seva forma i o estat dels enllaços de la xarxa. Aquest tipus de xarxes no es poden gestionar de forma fàcil amb encaminament estàtic. A més l'encaminament estàtic no és un sistema escal·lable.

Aquest tipus de xarxa utilitzen sistemes adaptatius o dinàmics. Aquest tipus de sistemes modifiquen les taules de rutes dels encaminadors de forma automàtica.

Conceptes

  • Tipus de mètriques:
  • Nombre de salts: Aquest tipus de sistemes suposen un cost 1 igual per a tots els enllaços. No és un sistema òptim però si que és un sistema senzill que dona prou bons resultats.
  • Temps de propagació: el cost es mesura segons el temps o retard que té un paquet per tal d'anar d'un node a un altre. Es mesura en unitats de temps (es pot utilitzar per exemple el temps de ping) i cal tenir en compte que no és un valor constant ja que depèn del trànsit que hi hagi a la xarxa.

La mètrica a la comanda route de Linux es pot establir amb:

$ sudo route add default gw 192.168.204.1 metric 1

Observeu el resultat:

$ route -n
Kernel IP routing table
Destination     Gateway         Genmask         Flags Metric Ref    Use Iface
0.0.0.0         192.168.204.1   0.0.0.0         UG    0      0        0 eth0
0.0.0.0         192.168.204.1   0.0.0.0         UG    1      0        0 eth0
169.254.0.0     0.0.0.0         255.255.0.0     U     1000   0        0 eth0
192.168.204.0   0.0.0.0         255.255.255.0   U     1      0        0 eth0

Tipus de protocols

Hi ha dos tipus de protocols:

Alguns protocols es poden utilitzar per a un tipus o un altre, per exemples el protocol BGP que pot ser eBGP o iBGP.

Recursos:

Interior Gateway Protocol

Recursos:

External Gateway Protocol

Algorismes

Hi ha dos tipus principals d'algorismes:

Algorismes de vector de distància

aka com DV o Distance Vector algorithms.

Aquest tipus d'algorismes utilitzen l'algorisme Bellman-Ford o similars. Aquest tipus d'algorismes assignen un número (anomenat cost) a cada enllaç entre nodes. Aquest tipus d'algorismes envien la informació de un node A a un node B utilitzant el camí que sumi el menor cost possible (el cost total és la suma de costos).

Aquests tipus d'algorismes funcionen d'una forma molt senzilla. El primer node només coneix el cost per tal d'accedir als nodes veïns. La informació que conté el node és la següent:

  • Llista de possibles veïns (aka next hops)
  • Per a cada veí, cal guardar el cost per arribar al node veí.

Aquesta informació és coneguda com la taula de distàncies o també com la taula de rutes. Cada node de forma regular, envia a cada node veí la informació que té actualment respecte els costos totals que té aquell node per arribar a les destinacions possibles. Els nodes veïns examinen aquesta informació i la comparen amb la informació pròpia; si a partir de la informació enviada pel veí veuen que tenen una millor ruta per accedir a un node destinació, aleshores actualitzen la seva taula de rutes.

Quan un node cau, els nodes veïns que l'utilitzaven com a següent node (next hop) per algunes destinacions, el descarten i modifiquen/recalculen una nova taula de rutes. Un cop fet això passant la informació als routers veïns i així successivament fins que tota la xarxa rep la informació actualitzada.

Cal destacar les següents característiques:

  • La base de dades que conté cada node és un vector (vector de distàncies) amb els costos per arribar als nodes del resta de la xarxa.
  • Els nodes només intercanvien informació amb els seus veïns
  • Els encaminadors que utilitzen algorismes DV no tenen coneixement del camí complet per arribar a una destinació. Normalment el que saben sobre el camí és només una de les dues opcions següents:
  • La direcció cap a la que cal reenviar (forward) el paquet. En enllaços PtP (punt a punt) només cal saber la interfície i en enllaços PtmP (punt a multipunt) cal saber tant la interfície de xarxa com la adreça del node següent
  • Distància fins a la destinació. TODO: exemples?

Avantatges:

  • Tenen menys complexitat computacional que els algorismes d'estat de l'enllaç ja que només
  • Utilitzen menys missatges per a tal de comunicar informació entre els nodes de la xarxa (menys message overhead)

Llista de protocols que utilitzen encaminament dinàmic:

  • RIP
  • IGRP
  • EGP i BGP no són purament algorismes DVper que no tots els costos del vector de distàncies es calculen segons el cost de l'enllaç (la local route preference té preferència respecte al cost de l'enllaç).

Tot i això es basen en aquest tipus d'algorismes.

Recursos:

Algorismes d'estat de l'enllaç

En aquest tipus d'algorismes, cada node utilitza com a informació fonamental un mapa de la xarxa en forma de graf.

Exemples de protocols:

El concepte bàsic és que cada node (a Internet o en xarxes locals els nodes són routers) construeix un mapa de la connectivitat de la xarxa en forma de graph. Aquest mapa mostra quins nodes estan connectats a altres nodes.

Cada node aleshores calcula a partir d'aquest mapa el millor següent salt (next hop) per a cada ruta possible. La col·leció de millors next hops construeix la taula de rutes del node.

NOTA: observeu que a diferència dels protocols distance-vector, els nodes no intercanvien les taules de ruta sinó que intercanvien dades de connectivitat, és a dir a quins nodes i xarxes tenen accés. De forma informal es pot dir que cada router li dona informació a tot el món sobre els seus veïns.

TODO: graph: To produce this, each node floods the entire network with information about what other nodes it can connect to, and each node  
then independently assembles this information into a map. Using this map, each router then independently determines the least-cost path from 
itself to every other node using a standard shortest paths algorithm such as Dijkstra's algorithm. The result is a tree rooted at the current 
node such that the path through the tree from the root to any other node is the least-cost path to that node. This tree then serves to 
construct the routing table, which specifies the best next hop to get from the current node to any other node.

Recursos:

Algorismes optimitzats d'estat de l'enllaç

TODO

A link-state routing algorithm optimised for mobile ad-hoc networks is the Optimised Link State Routing Protocol (OLSR).[1] OLSR is proactive; it uses Hello and Topology Control (TC) messages to discover and disseminate link state information through the mobile ad-hoc network. Using Hello messages, each node discovers 2-hop neighbor information and elects a set of multipoint relays (MPRs). MPRs distinguish OLSR from other link state routing protocols. [edit] Path vector protocol Main article: Path vector protocol

Distance vector and link state routing are both intra-domain routing protocols. They are used inside an autonomous system, but not between autonomous systems. Both of these routing protocols become intractable in large networks and cannot be used in Inter-domain routing. Distance vector routing is subject to instability if there are more than a few hops in the domain. Link state routing needs huge amount of resources to calculate routing tables. It also creates heavy traffic because of flooding.

Path vector routing is used for inter-domain routing. It is similar to distance vector routing. In path vector routing we assume there is one node (there can be many) in each autonomous system which acts on behalf of the entire autonomous system. This node is called the speaker node. The speaker node creates a routing table and advertises it to neighboring speaker nodes in neighboring autonomous systems. The idea is the same as distance vector routing except that only speaker nodes in each autonomous system can communicate with each other. The speaker node advertises the path, not the metric of the nodes, in its autonomous system or other autonomous systems. Path vector routing is discussed in RFC 1322; the path vector routing algorithm is somewhat similar to the distance vector algorithm in the sense that each border router advertises the destinations it can reach to its neighboring router. However, instead of advertising networks in terms of a destination and the distance to that destination, networks are advertised as destination addresses and path descriptions to reach those destinations. A route is defined as a pairing between a destination and the attributes of the path to that destination, thus the name, path vector routing, where the routers receive a vector that contains paths to a set of destinations. The path, expressed in terms of the domains (or confederations) traversed so far, is carried in a special path attribute that records the sequence of routing domains through which the reachability information has passed. [edit] Comparison of routing algorithms

Distance-vector routing protocols are simple and efficient in small networks and require little, if any, management. However, traditional distance-vector algorithms have poor convergence properties due to the count-to-infinity problem.

This has led to the development of more complex but more scalable algorithms for use in large networks. Interior routing mostly uses link-state routing protocols such as OSPF and IS-IS.

A more recent development is that of loop-free distance-vector protocols (e.g., EIGRP). Loop-free distance-vector protocols are as robust and manageable as naive distance-vector protocols, but avoid counting to infinity, and have good worst-case convergence times.

Encaminament dinàmic a Linux

Vegeu Quagga.

Encaminament dinàmic a routerOS

Vegeu RouterOS#Enrutament_din.C3.A0mic

Llista de protocols

Vegeu també

Enllaços externs