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.
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.
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).
Al llarg del temps s'han creat diferents versions i RFCs:
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:
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ç.
Abans de que una xarxa OSPF sigui completament funcional hi ha les següents fases:
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:
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 (188.8.131.52), then router periodically multicasts its Hello packets to the IP address 184.108.40.206. 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.
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 (220.127.116.11) 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.
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.
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.
Imatge d'un paquet OSPF:
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.
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.
TODO. Consulteu Quagga
Configurant els Linksys WRT54G en mode WDS (repetidor) amb Satori pre3.6:
A routerOS es pot mirar a:
OSPF > LSA