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)

Seguretat: http://mdbrasil.com.br/en/downloads/1_Maia.pdf

OSPF o Open Shortest Path First és un protocol d'encaminament dinàmic de gateway interior (aka IGP o Interior Gateway Protocol). Utilitza l'algorisme de Dijkstra enlace-estado o link-state (LSA - Link State Algorithm) per a calcular la ruta més curta possible.

Utilitza el concepte de cost com a mètrica.

A més construeix una base de dades enllaç-estat (link-state database o LSDB) idèntica per a tots els encaminadors d'una zona OSPF. Aquesta base de dades es troba a cada router.

OSPF és probablement el tipus de protocol IGP més utilitzat en xarxes grans.

OSPF pot operar amb seguretat utilitzant MD5 per realitzar connexions segures entre encaminadors veïns.

Al contrari que RIP o BGP, OSPF no utilitza ni TCP ni UDP, sinó que utilitza directament el protocol IP (IP 89) i multicast.

OSPF és el successor natural de RIP i suporta VLSM a més de CIDR.

Una xarxa OSPF es pot descompondre en regions o àreas més petites. Hi ha una àrea especial anomenada backbone que forma part de la xarxa central a la que estan connectades tota la resta de xarxes. Les rutes entre diferents àrees circulen sempre pel backbone, si no es pot fer un enllaç directa amb el backbone es pot fer un enllaç virtual.

Els encaminadors que estan al mateix domini de difusió ja sigui per que estan a la mateixa xarxa LAN o per que estan connectats mitjançant un enllaç PTP, al esta al mateix domini de multidifusió formen enllaços al autodescubrir-se mitjançant paquets multicast (OSPF hello).

Les adreces de multicast (aka multidifusió) utilitzades són 224.0.0.5 i 224.0.0.6.

Avantatges i inconvenients

Avantatges:

  • No hi ha limit per tal de comptar els salts (Hops) (si tenen aquest límit protocols com RIP)
  • S'utilitza multicast per enviar les actualitzacions de la informació de rutes.
  • Les actualitzacions només s'envien quan hi ha canvis a la topologia de la xarxa.
  • Es poden definir àrees. Vegeu OSPF Areas
  • Transfers and tags external routes injected into AS.

Inconvenients:

  • L'algorisme OSPF requereix un ús més intensiu de CPU i memòria (respecte a altres protocols com BGP).
  • És un protocol més complexe d'implementar

Versions

Al llarg del temps s'han creat diferents versions i RFCs:

MikroTik RouterOS implementa la versió 2 (RFC 2328) i la versió 3 (RFC 5340 o OSPF per a IPv6).

També hi ha extensions del protocol no massa esteses com multidifusió per OSPF (MOSPF) que permet "etiquetar" rutes i propagar estes etiquetes per altres rutes.

Recursos:

Terminologia

  • NBMA: xarxa que no suporta Broadcast.
  • Broadcast: xarxa que suporta broadcast i multicast. Per exemple Ethernet
  • Point-to-point: aquest tipus de xarxa no requereixen de DRs ni BDRs. Hi ha un sol veí.
  • DR Designated Router: és el encaminador escollit de tots els possibles per tal de minimitzar el nombre d'adjacències formades.
  • BDR - Backup Designated Router: és el encaminador escollit com a backup del DR. Rep tots les actualitzacions d'encaminament dels routers adjacents però no envia paquets LSA d'actualització.
  • Link State Advertisement (LSA): és un paquet que conté informació de l'estat de l'enllaç (link-state) i informació d'encaminament. Aquest paquets s'intercanvien entre encaminadors veïns OSPF.
  • LSDB/Link State Database:
  • Link cost factors (external metrics): cada interfície d'encaminament té un cost associat. El cost pot utilitzar diferent mètriques com la distància (round-trip time), network throughput de l'enllaç, la disponibilitat del enllaç o la fiabilitat de l'enllaç.
  • Routing Areas: OSPF pot dividir la xarxa en zones per simplificar l'administració. Per conveni és defineix un àrea per defecte coneguda com a backbone o àrea 0, representada pel valor 0.0.0.0. Les altres areas se solen identificar per l'adreça IP del seu ruter principal, però es poden escollir altres formes d'identificació. Cada àrea addicional ha de tenir una connexió directe o virtual amb l'àrea backbone, les connexions entre areas es fan amb routers coneguts com a border routers (ABR).
  • Tipus d'àreas:
  • default: també coneguda com a backbone.
  • Not-so-stubby area (nssa): És un tipus d'stub area que pot importar autonomous system external routes i enviar-les a altres àrees. ut still cannot receive AS-external routes from other areas. NSSA is an extension of the stub area feature that allows the injection of external routes in a limited fashion into the stub area. A case study simulates an NSSA getting around the Stub Area problem of not being able to import external addresses. It visualizes the following activities: the ASBR imports external addresses with a type 7 LSA, the ABR converts a type 7 LSA to type 5 and floods it to other areas, the ABR acts as an "ASBR" for other areas. The ABR's do not take type 5 LSA's and then convert to type 7 LSA's for the area.
  • stub: TODO
  • Neighbour: els veïns són els encaminadors que es troben adjacents a una interfície de xarxa del router OSPF (a una sol salt). Els veïns s'autodescobreixen (no cal definir-los com en altres protocols com BGP) utilitzant multicast i els paquets OSPF Hello.
  • Adjacency: és una connexió lògica entre un encaminador i el corresponents DR i BDR. No s'envia informació d'encaminament a no ser que es formin adjacències.
  • Router-ID: la adreça IP utilitzada per identificar el router o la instància OSPF. Si no es configura manualment aleshores s'utilitzar una de les IPs de l'encaminador.
  • Autonomous System/AS: un autonomous system és un grup d'encaminadors que utilitzen el mateix protocol d'encaminament per a intercanviar informació d'encaminament.

Recursos:

Com funciona?

OSPF és un protocol de link-state protocol. Els protocols d'aquest tipus són protocols que distribueixen i repliquen una base de dades que descriu la topologia de la xarxa. Cada encaminador recull les dades locals de la topologia de xarxa (és a dir les dades de les xarxes que coneix localment) i envia aquesta informació utilitzant link-state advertisements (LSAs). Els paquets LSA s'envien a tots (flood) els encaminadors de la xarxa per tal de que tots els routers coneguin l'estat de tots els nodes de la xarxa. D'aquesta manera tots els routers de la xarxa tenen la mateixa base de dades de l'estat dels enllaços i la topologia de la xarxa.


OSPF defineix els següents tipus de LSA:

  • type 1 aka router LSA: S'envia pels encaminadors d'una mateixa area i inclou una llista de tots els enllaços directes que té el encaminador. Aquests paquets no passen més enllà dels ABR o ASBR.
  • type 2 aka Network LSA: Generated for every “transit network” within an area. A transit network has at least two directly attached OSPF routers. Ethernet is an example of a Transit Network. A Type 2 LSA lists each of the attached routers that make up the transit network and is generated by the DR.
  • type 3: (Summary LSA) The ABR sends Type 3 Summary LSAs. A Type 3 LSA advertises any networks owned by an area to the rest of the areas in the OSPF AS. By default, OSPF advertises Type 3 LSAs for every subnet defined in the originating area, which can cause flooding problems, so it´s a good idea to use a manual summarization at the ABR.
  • type 4: (ASBR-Summary LSA) It announces the ASBR address, it shows “where” the ASBR is located, announcing it´s address instead of it´s routing table.
  • type 5: (External LSA) Announces the Routes learned through the ASBR. External LSAs are flooded to all areas except Stub areas. These LSAs divides in two types: external type 1 and external type2.
  • type 6: (Group Membership LSA) This was defined for Multicast extensions to OSPF and is not used by ROuterOS.
  • type 7: type 7 LSAs are used to tell the ABRs about these external routes imorted in NSSA area. Area Border Router then translates these LSAs to type 5 external LSAs and floods as normal to the rest of the OSPF network
  • type 8: (Link-local only LSA for OSPFv3)

NOTA: Si no hi ha cap ASBR no hi ha LSAs de tipus 4 ni 5

Si es mira la link-state database cada router pot saber quants altres encaminadors hi ha a la xarxa, quantes interfícies tenen, quines xarxes hi ha i els cost de cada enllaç.

Fases

Abans de que una xarxa OSPF sigui completament funcional hi ha les següents fases:

Neighbor discovery

The transmission and reception of Hello packets also allows router to detect failure of the neighbor. If Hello packets are not received within Dead interval (which by default is 40s) router starts to route packets around the failure. Hello protocol ensures that the neighboring routers agree on the Hello interval and Dead interval parameters, preventing situations when not in time received Hello packets mistakenly bring the link down.

Paquet OSPF Hello:

http://wiki.mikrotik.com/wiki/File:Ospf-hello.png

On:

  • network mask: The IP mask of the originating router's interface IP address.
  • hello interval: period between Hello packets (default 10s)
  • options : OSPF options for neighbor information
  • router priority: an 8-bit value used to aid in the election of the DR and BDR. (Not set in p2p links)
  • router dead interval: time interval has to be received before consider the neighbor is down. ( By default four times bigger than Hello interval)
  • DR: the router-id of the current DR
  • BDR: the router-id of the current BDR
  • Neighbor router IDs: a list of router-ids for all the originating router's neighbors


On each type of network segment Hello protocol works a little different. It is clear that on point-to-point segments only one neighbor is possible and no additional actions are required. However if more than one neighbor can be on the segment additional actions are taken to make OSPF functionality even more efficient. Icon-note.png

Note: Network mask, Priority, DR and BDR fields are used only when the neighbors are connected by a broadcast or NBMA network segment.


Two routers do not become neighbors unless the following conditions are met.

   Two way communication between routers is possible. Determined by flooding Hello packets.
   Interface should belong to the same area;
   Interface should belong to the same subnet and have the same network mask, unless it has network-type configured as point-to-point;
   Routers should have the same authentication options, and have to exchange same password (if any);
   Hello and Dead intervals should be the same in Hello packets;
   External routing and NSSA flags should be the same in Hello packets.


Discovery on Broadcast Subnets

Attached node to the broadcast subnet can send single packet and that packet is received by all other attached nodes. This is very useful for auto-configuration and information replication. Another useful capability in broadcast subnets is multicast. This capability allows to send single packet which will be received by nodes configured to receive multicast packet. OSPF is using this capability to find OSPF neighbors and detect bidirectional connectivity.

Consider Ethernet network illustrated in image below.

OSPF Broadcast network Each OSPF router joins the IP multicast group AllSPFRouters (224.0.0.5), then router periodically multicasts its Hello packets to the IP address 224.0.0.5. All other routers that joined the same group will receive multicasted Hello packet. In that way OSPF routers maintain relationships with all other OSPF routers by sending single packet instead of sending separate packet to each neighbor on the segment.

This approach has several advantages:

       Automatic neighbor discovery by multicasting or broadcasting Hello packets. 
       Less bandwidth usage compared to other subnet types. On broadcast segment there are n*(n-1)/2 neighbor relations, but those relations are maintained by sending only n Hellos. 
       If broadcast has multicast capability, then OSPF operates without disturbing non-OSPF nodes on the broadcast segment. If multicast capability is not supported all routers will receive broadcasted Hello packet even if node is not OSPF router. 


Discovery on NBMA Subnets

Nonbroadcast multiaccess (NBMA) segments similar to broadcast supports more than two routers, only difference is that NBMA do not support data-link broadcast capability. Due to this limitation OSPF neighbors must be discovered initially through configuration. On RouterOS NBMA configuration is possible in/routig ospf nbma-neighbor menu. To reduce the amount of Hello traffic, most routers attached to NBMA subnet should be assigned Router Priority of 0 (set by default in RouterOS). Routers that are eligible to become Designated Routers should have priority values other than 0. It ensures that during election of DR and BDR Hellos are sent only to eligible routers.


Discovery on PTMP Subnets

Point-to-MultiPoint treats the network as a collection of point-to-point links.

On PTMP subnets Hello protocol is used only to detect active OSPF neighbors and to detect bidirectional communication between neighbors. Routers on PTMP subnets send Hello packets to all other routers that are directly connected to them. Designated Routers and Backup Designated routers are not elected on Point-to-multipoint subnets.

Database Synchronization

Link-state Database synchronization between OSPF routers are very important. There are two types of database synchronizations:

       initial database synchronization 
       reliable flooding. 

When the connection between two neighbors first come up, initial database synchronization will happen. Unsynchronized databases may lead to calculation of incorrect routing table, resulting in routing loops or black holes. OSPF is using explicit database download when neighbor connections first come up. This procedure is called Database exchange. Instead of sending the entire database, OSPF router sends only its LSA headers in a sequence of OSPF Database Description (DD) packets. Router will send next DD packet only when previous packet is acknowledged. When entire sequence of DD packets has been received, router knows which LSAs it does not have and which LSAs are more recent. The router then sends Link-State Request (LSR) packets requesting desired LSAs, and the neighbor responds by flooding LSAs in Link-State Update (LSU) packets. After all updates are received neighbors are said to be fully adjacent.

Reliable flooding is another database synchronization method. It is used when adjacencies are already established and OSPF router wants to inform other routers about LSA changes. When OSPF router receives such Link State Update, it installs new LSA in link-state database, sends an acknowledgement packet back to sender, repackages LSA in new LSU and sends it out all interfaces except the one that received the LSA in the first place.

OSPF determines if LSAs are up to date by comparing sequence numbers. Sequence numbers start with 0×80000001, the larger the number, the more recent the LSA is. Sequence number is incremented each time the record is flooded and neighbor receiving update resets Maximum age timer. LSAs are refreshed every 30 minutes, but without a refresh LSA remains in the database for maximum age of 60 minutes.

Databases are not always synchronized between all OSPF neighbors, OSPF decides whether databases needs to be synchronized depending on network segment, for example, on point-to-point links databases are always synchronized between routers, but on ethernet networks databases are synchronized between certain neighbor pairs.


Synchronization on Broadcast Subnets

OSPF Broadcast adjacencies

On broadcast segment there are n*(n-1)/2 neighbor relations, it will be huge amount of Link State Updates and Acknowledgements sent over the subnet if OSPF router will try to synchronize with each OSPF router on the subnet.

This problem is solved by electing one Designated Router and one Backup Designated Router for each broadcast subnet. All other routers are synchronizing and forming adjacencies only with those two elected routers. This approach reduces amount of adjacencies from n*(n-1)/2 to only 2n-1.

Image on the right illustrates adjacency formations on broadcast subnets. Routers R1 and R2 are Designated Router and Backup Designated router respectively. For example, R3 wants to flood Link State Update (LSU) to both R1 and R2, router sends LSU to IP multicast address AllDRouters (224.0.0.6) and only DR and BDR listens to this multicast address. Then Designated Router sends LSU addressed to AllSPFRouters, updating the rest of the routers. DR election

DR and BDR routers are elected from data received in Hello packet. The first OSPF router on a subnet is always elected as Designated Router, when second router is added it becomes Backup Designated Router. When existing DR or BDR fails new DR or BDR is elected taking into account configured router priority. Router with the highest priority becomes the new DR or BDR.

Being Designated Router or Backup Designated Router consumes additional resources. If Router Priority is set to 0, then router is not participating in the election process. This is very useful if certain slower routers are not capable of being DR or BDR. Synchronization on NBMA Subnets

Database synchronization on NBMA networks are similar as on broadcast networks. DR and BDR are elected, databases initially are exchanged only with DR and BDR routers and flooding always goes through the DR. The only difference is that Link State Updates must be replicated and sent to each adjacent router separately. Synchronization on PTMP Subnets

On PTMP subnets OSPF router becomes adjacent to all other routes with which it can communicate directly.

Routing calculation

When link-state databases are synchronized OSPF routers are able to calculate routing table.

Link state database describes the routers and links that interconnect them and are appropriate for forwarding. It also contains the cost (metric) of each link. This metric is used to calculate shortest path to destination network. Each router can advertise a different cost for the router's own link direction, making it possible to have asymmetric links (packets to destination travels over one path, but response travels different path). Asymmetric paths are not very popular, because it makes harder to find routing problems. The Cost in RouterOS is set to 10 on all interfaces by default. Value can be changed in ospf interface configuration menu, for example to add ether2 interface with cost of 100:

/routing ospf interface add interface=ether2 cost=100


The cost of an interface on Cisco routers is inversely proportional to the bandwidth of that interface. Higher bandwidth indicates lower cost. If similar costs are necessary on RouterOS, then use following formula:

       Cost = 100000000/bw in bps. 


OSPF router is using Dijkstra's Shortest Path First (SPF) algorithm to calculate shortest path. The algorithm places router at the root of a tree and calculates shortest path to each destination based on the cumulative cost required to reach the destination. Each router calculates own tree even though all routers are using the same link-state database.

SPT calculation

Assume we have the following network. Network consists of 4(four) routers. OSPF costs for outgoing interfaces are shown near the line that represents the link. In order to build shortest path tree for router R1, we need to make R1 the root and calculate the smallest cost for each destination. spt sample network calculated sp tree


As you can see from image above multiple shortest paths have been found to 172.16.1.0 network, allowing load balancing of the traffic to that destination called equal-cost multipath (ECMP). After the shortest path tree is built, router starts to build the routing table accordingly. Networks are reached consequently to the cost calculated in the tree.

Routing table calculation looks quite simple, however when some of the OSPF extensions are used or OSPF areas are calculated, routing calculation gets more complicated.

Protocol OSPF

Imatge d'un paquet OSPF:

Ospf-header.png

on:

  • Packet type: Hi ha diferents tipus de paquets OSPF:
  • Hello packet: s'utilitza per descobrir veïns OSPF i construir adjacències.
  • Database Description (DD) packet: s'utilitza per sincornitzar les bases de dades entre routers. Recordeu que tots els routers tenen la mateixa base de dades un cop la xarxa estabilitzada i si hi ha un canvi a la xarxa s'inicia un procés d'actualització de totes les bases de dades. Aquests paquets s'envien un cop s'han construït les adjacències.
  • Link state request packet': s'utilitza per demanar a un veí actualitzacions de la base de dades de veïns. Out of date parts of routes database are determined after DD exchange???
  • Link State Update packet: conté una col·lecció de registres de link-state que s'han demanat a un vei utilitzant els Link state request packet.
  • Link State Acknowledgment packet (LSack): s'utilitza per confirmar la recepció de la resta de tipus de paquets i així tenir un sistema confiable (recordeu que no utilitzem TCP i per tant està és la forma que tenim de verificar la recepció dels paquets per part dels veïns)
  • Tots aquests paquets excepte el Hello packet s'utilitzen en la fase de sincronització de la base de dades link-state (segona fase).
  • Router ID: és una de les adreces IP del router excepte si s'especifica de forma manual (a la configuració de OSPF) l'adreça que es vol utilitzar.
  • Area ID: Permet a un ruter OSPF asociar el paquet a una aea OSPF concreta.
  • Checksum: Permet comprovar la vàlidesa del paquet OSPF.
  • Authentication fields: s'utilitzen per autenticar els paquets i comprovar la seva identitat i així poder assegurar que els paquets OSPF provenen de veïns autoritzats.

Recursos:

Instàncies

Cada instància té un identificador o router-id.

IMPORTANT: Es proposa posar com identificador la IP d'una interfície que sempre estigui activa, per exemple una interfície tipus bridge. Ha guifi se sol posar en models híbrids la IP del bridge LanLan o WlanLan

Sembla que l'identificador només serveix per identificar localment diverses possibles instàncies d'OSPF. No sembla que s'utilitzen per a res externament al router que es defineixen.

As you can see router-id is 0.0.0.0, it means that router will use one of router's IP addresses as router-id. In most cases it is recommended to set up loopback IP address as router-id. Loopback IP address is virtual, software address that is used for router identification in network. The benefits are that loopback address is always up (active) and can’t be down as physical interface. OSPF protocol used it for communication among routers that identified by router-id. Loopback interface are configured as follows:

Create bridge interface named, for example, “loopback”:

[admin@MikroTikR1] /interface bridge> add name=loopback

Add IP address:

[admin@MikroTikR1] > ip address add address=10.255.255.1/32 interface=loopback 

Configure router-id as loopback:

[admin@MikroTikR1] /routing ospf instance> set 0 router-id=10.255.255.1

This can be done on other routers (R2, R3) as well.

Next step is to configure OSPF area. Backbone area is created during RouterOS installation and additional configuration is not required.

OSPF states

  • state: backup | designated-router | point-to-point | passive

OSPF vs BGP

A:

http://guifi.net/node/27458

Podem veure exemples de com es connecten entre sí amb BGP els núvols OSPF de zones de guifi.net.

Comentari de Sebastian Galeano a les llistes:

El OSPF es solament recomenat pel interior de zones que no tenen redundancies, ni connecten amb mes d'una zona, en els altres casos es recomenat fer servir BGP, pel tema de no 
trencar el AS-PATH.
DiferenciesBGPOSPFRouterOSSegonsGuifi.png

NOTA: Realitzat amb l'eina meld que utilitza diff

OSPF a RouterOS

Consulteu RouterOS#OSPF

OSPF a Quagga

TODO. Consulteu Quagga

OSPF a WRT54G

Configurant els Linksys WRT54G en mode WDS (repetidor) amb Satori pre3.6:

http://guifi.net/node/549

Troubleshooting

Saber l'origen d'una ruta OSPF

A routerOS es pot mirar a:

OSPF > LSA

Exercicis alumnes

Vegeu també

Enllaços externs

http://bestpractices.wikia.com/wiki/OSPF