routing protocol OSPF OSPF routing protocol
Role the router is to route packets between different networks. For that, based on its routing table contains the necessary elements (@ network mask, router IP @ target, output interface) to transfer the packet. In addition, the router must have a routing table containing all network numbers for which there shall be capable of routing (or use a default route).
To avoid tedious manual configuration of routing tables, especially if the number of networks and subnets is important, we use dynamic routing protocols called done by routing protocols.
There are two main categories: internal protocols (IGP: Interior Gateway Protocol) to establish the routing tables of routers belonging to a single entity called AS (Autonomous System: Standalone) and external protocols (EGP: Exterior Gateway Protocol) for the exchange of information between autonomous systems.
In-house protocols, there are two types: distance vector protocols (Distant Vector Protocol) that use the router as jump metric, and link state protocols (Link State Protocol), much more efficient than precedents, we shall see in detail through OSPF
OSPF (Open Shortest Path First) OSPF
was designed in the late 80s to address the main shortcomings of distance vector protocols (limiting the number jumps to 15 max, convergence time too important ...). It is an open protocol (no copyright), version 2 (latest) has been defined and standardized by the IETF (Internet Engineering Task Force) in 1998 by RFC (Request For Comment) No. 2328, a Version 3 (RFC 2740) was designed for IPv6.
OSPF is an internal routing protocol Link-state operating in the battery TCP / IP, it is placed directly over IP protocol (No. 89).
Its principle is simple, each router determines the state of its connections (links) with routers neighbors, it broadcasts its information to all routers belonging to a single area. This information forms a database, which must match all routers in the same area. Given an autonomous system (AS) consists of several parts, all of these databases is the topology of the AS. From this database, each router will calculate its routing table using the algorithm SPF (Short Path First).
CONCEPTS
logical topology and hierarchy (AS) AS
or autonomous system: a set of networks governed by an administrative authority, routing tables are calculated and disseminated to all routers in the AS with the same internal routing protocol (IGP).
AREA or area: a way to better manage an autonomous system of great importance and reduce the exchange of information, we have divided it into several regions called Area. Each area has its own topology and knows no other. A link or network belongs to a single area, the boundaries area to lie on the routers and not on links. Each area is identified by a number of 32-bit (area ID) is independent of network addressing plan. The areas "are structured in a star around a particular area or area called area 0 backbone.
Type area:
-Area 0 (backbone area): it consists of routers BR (Backbone Router) connecting two or more areas "is the path required to move from one area to another. There may be a backbone router, connecting two zones is not physically connected to area 0, then it connects through a virtual link.
-area high school (standard area): it consists of routers IR (Internal Router) knowing only the topology of the area, they calculate the local routing tables.
-terminal area (stub area): same behavior as the standard area except that there is no external storage drive (outside the autonomous system).
There are three types of communication: Intra-area-
: exchange of information specific to this area.
-inter-area: The minimum information exchange to connect the areas.
-Inter-AS: communication for the connection between autonomous systems.
OSPF defines a role for each router and a special operation:
Router type:
-IR (Internal Router): it works within an area (other than backbone), it creates and maintains a Link-State -Database (database link state) depending on all the networks in its area and sends its information to all other routers in the area. This
-Link-State Database is identical to all the IR area.
-ABR (Area Border Router): edge router connecting two or more zones. It has the Link-State Database of the areas it connects. It distributes that information to Bacbone area. In addition it summarizes (summarization of routes) to minimize the information updated.
-BR (Backbone Router): Every field must be connected to area 0 and this through Backbone Router. It functions as an ABR.
-ASBR (Autonomous System Boundary Router): This border router acts as a gateway between autonomous systems. For that it connects to a peer ASBR (another AS) external routes to learn and disseminate its own.
physical topology and hierarchy (Level Area)
For that routers exchange routing information, they must be adjacent, ie they must discover each other. This adjacency will be built using the HELLO protocol (allows the discovery of neighbors and check that they are always accessible). Moreover it is dependent on the type of physical network interfaces for OSPF defines three types of network:
Point to Point (PPP, HDLC) is a segment that connects two routers.
-BMA: Broadcast Multiple Access (Ethernet) segment to connect multiple routers.
-NBMA: Non-Broadcast Multiple Access (X25, Frame Relay, ISDN): segment to connect multiple routers.
On Types and NBMA BMA, many routers can be connected and if each router must establish an adjacency with all other exchanges will cause an overload in the area. We will therefore designate a router (DR: Designated Router) will become adjacent to all others. It will collect state information from other routers link and then rebroadcast to all. This county is becoming a focal point of the segment, to secure this system we will designate a backup router: the BDR (Backup Designated Router).
This system takes the form of election and is based on the IP @ interface of the router. Cons by the election of the DR and BDR applies only to the BMA and NBMA networks.
OSPF uses multicast to send its packets: concretely, packets addressed to all routers in the area use the @ 224.0.0.5 multicast, while only packets addressed to the DR and BDR to use the multicast @ 224.0 .0.6.
OPERATION
General description:
The routing table is achieved through the final implementation of the algorithm SPF (Short Path First) on the basis of information describing the links between the routers of a area. A link is a router interface and its state is the description of this interface (@ IP, mask, routers connected ...). This database is called a Link State Topology Database or table, it is identical to all routers in the area. At startup, a router must be aware of others, he uses the HELLO protocol, then it generates an LSA (Link State Advertisement) representing all the states of links near the router. This exchange link state between routers is done by flooding (flooding). Updates link state (Lin State Update) can upgrade all the routers. When the databases are synchronized (Identical among all routers in the area), each router will calculate the "tree of shortest path" by applying the algorithm SPF (Dijkstra algorithm). It will construct and its routing table (routing table or forwarding table).
Process Flow:
(State interfaces) STEP 1: Discovery of the neighbors (adjacency routers)
(Down state) No exchange of information, waiting for a HELLO packet.
(Init state), routers send HELLO packets (all 10s) to establish a relationship with his neighbor. Upon receiving a HELLO it passes to the next state.
(Two-way state) two possibilities: either there are only two routers (point to point), then the routers become adjacent (we go to Step 3), there are several routers in the case BMA and NBMA networks, we go to step 2.
STEP 2: Election of the DR and BDR
-1: OSPF selects a random router R1 which examines all the others who have reached the state "Two-way".
-2: It removes those with priority 0 (fields "Router priority" HELLO packet, a default value to max and 255 to force a election).
-3: He chooses the one whose priority is highest and named BDR, if tied to the order, he will choose the one whose ID (fields "Router ID" of the HELLO packet) is the most elevated. This ID is the IP @ of the physical interface or (for Cisco routers including) the @ IP loopback interface.
-4: If no router expressed DR in OSPF transforms the DR and BDR resumes steps 2 and 3 to elect the BDR.
-5: The county built the adjacencies with the other (as well as the BDR).
STEP 3: Route Discovery
(ExStart state) Establishing a master / slave relationship between routers, the router with ID (fields "Router ID") the greater becomes the master. The county is still the master.
(Exchange state), routers describe their Link-Database to others. This is the master who initiates the exchange of packets type 2 DBD (Database Description). These packets contain a description of the LDB (Link-State Database) with a sequence number. Routers confirm the receipt of packets by type 5 (LSAck) containing the sequence number. Everyone compares its information with the information received, whichever is the latest the router switches to "Loading".
(Loading state), the router sends packets of type 3 LSR (Link-state Request) to update its link state database of the router LSA with the latest, it responds by sending a packet of type 4 (LSU: link-state update), these are charged by LSU LSAck. These packets contain the Link-state Advertisements (LSA) are the link state information complete.
(Full Adjacency) Loading When the state is complete, the link-state database is synchronized, ie identical in all routers in the area, and each router establishes a list of neighboring routers (adjcency database).
STEP 4: Solution routes (routing table)
When the router has established its link-state database, it can create its routing table. It uses the SPF algorithm that takes into account the link bandwidth (see algorithm SPF).
STEP 5: Maintenance of routing tables
When there is a link status change (eg if an interface no longer receives HELLO packet from another interface, it considers the link "down") the router sends an LSU with the new information to its DR and BDR. These innondent then LSU other routers, new routing tables are created. If no topological change takes place, the information is refreshed, the LSA, by default, a lifetime of 30 minutes.
EXAMPLE OF EXCHANGE OF LSA
ALGORITHMS
algorithm SPF (Short Path First) algorithm or Dijkstra algorithm
Dijkstra (Dutch mathematician) is used to calculate routing tables. The goal is to establish the shortest path between a source and destination, the algorithm uses two structures: the structure PATH contains the path to get from one router to another and in a cost structure that contains TENT attempts path not the best cost. In summary, SPF is the sum of costs from itself (root router) to all destination networks, where there are several possible paths to a destination is one that has the lowest cost is chosen .
The cost depends on the bandwidth, the more it diminishes the higher the cost is high, according to the formula: cost = 108/Bandwith.
TDSP algorithm (Two Disjoint Shortest Paths) in OSPF
project has significantly reduced the convergence time compared to the protocol distance vector RIP, but after a single failure, it exceeds the minute, which is too long for real time applications. This convergence time is due to three factors: the time taken by a router to determine that a neighbor router is down, time to resynchronize the database topological and time required to recalculate the routing table. This new algorithm reduces the convergence time. It is actually a modified version of Dijkstra's algorithm based on the calculation of two paths (one backup path disjoint from the first path) used for each possible destination network and a single pass. This removes the two last time factors mentioned above.
SECURITY
By default the information is received by routers without sender authentication.
can activate a mechanism for authenticating OSPF messages. There are two types of authentication: one by a simple password and the other by a process of hash (message digest authentication: MD5). These authentications will be shared within the same area.
Athentification by simple-password: all routers share a password that will pass in the clear.
-MD5 Authentication: a key (key: password) and a key-id are configirés on each router. Each router will generate a borrowed 64-bit OSPF packet to send according to its key and its key-id with the MD5 hash algorithm. The destination router will perform the same operation, by comparing its result with the message digest received, it can be sure of the sender.
CONCLUSION
OSPF was developed to overcome the many problems of RIP and meet the need of routing on large networks.
Its main advantages are: fast convergence
-no-limit routers 'RIP is limited to 15 hops)
-supports VLSM and CIDR to reduce road
-specific metric (depending on bandwidth)
-load distribution (load balancing) through management of multiple routes for same destination .
-security by authenticating routing
-use of multicast and incremental update and not full. By
cons OSPF requires for its calculations consumption of CPU and memory very important on routers.
APPENDICES
Header OSPF
version 2
type 1 Hello 2 Database Description (used for adjacent routers) 3 Link State Request (used for adjacent routers) 4 Link State Update 5 Link State Ack (returned to the sender of the Link State Update, after a random time t)
packet length in bytes of header + data
ospf router id, the source router (each router must have a unique ID in the autonomous system)
ID area id of the area concerned
header checksum checksum + data authentication
auType authentication type: 0: null 1: single 2:
cryptographic Authentication Data authentication: type 0: insignificant type 1: type 2 password: data (key number used, sequence number, etc.).. In this case hash (paquet_ospf clé_secrete_connue_de_tous_les_routeurs +) is added at the end of the packet.
HELLO message
network mask netmask associated with the interface
hellointerval number of seconds between sending Hello
options options supported by this router (not detailed)
rtrpri router priority: if true 0 is ineligible as a désigné or Backup Designated Router
RouterDeadInterval number seconds necessary before declaring this router as dead
DR Designated Router for this network. 0.0.0.0 if there is no Backup Designated
BDR of the network. 0.0.0.0 if there is no ID
neighbor routers that it has received Hello packets
