OSPF: Routing propagation using SPF algorithm
I. Introduction
RIP protocol uses vector distance algorithm to spread routing information in gateways and hosts, the biggest advantage
It is simple. RIP effectively prevents unlimited continuation of the routing cycle by limiting the number of hops on the source address to the destination address path, thereby ensuring the stability of the network. However, with the continuous expansion of the Internet, the shortcomings of the RIP protocol are more serious. The first is that RIP limits the size of the network. Its maximum distance can be used as 15 (16 is not arrogant); the complete routing information overhead exchanged between the second router is too large. Finally, "bad news is slow", so that many update processes are too long.
Open Shortest Path Priority OSPF (Open Shortest Path First) Use the link status algorithm to spread the channel, which uses the SPF algorithm (Dijkstra algorithm). Its points are as follows:
1. All routers maintain a link status database, only link status letters of the reachable adjacent station
Symnastery is stored in the link status database, this database is actually the topology map of the entire interconnection network. The router using the RIP protocol only knows the next stop router of all my destination, but does not know the topology of the whole network.
2, OSPF allows each link state to bring a 32 bit of the serial number (the rate of growth is not exceeded once every 5 seconds), the larger the serial number, the more new. Each router uses data in the link status database to calculate your own routing table.
3. If there is any change in the network topology, the link status database can be updated soon, so that each
A router can recalculate a new routing table.
4, OSPF relies frequent exchange information between each router to establish a link status database and maintains the consistency of this database within the full network (synchronization of the link status database).
5, OSPF is not transmitted using the user data report UDP using the transport layer, but directly with IP.
Data report is transmitted, and the datagram is very short. (figure 1)
IP Data Newspaper (20 bytes)
OSPF packet header (24 bytes)
OSPF packets of type 1 to 5
Figure 1 OSPF uses IP datagram
Since the link state of a router involves only a communication with adjacent routers, it is independent of the size of the entire interconnection network.
Second, the basic concept
1. Link status: "link status" of a router is the router and which networks
The network or router is adjacent to the router, as well as the cost required to send data to these networks or routers.
2. Autonomous system: generally referred to as AS. A autonomous system is an interconnected network. Its most important feature is that it has the right to independily decide what routing protocol should be used in this system.
3. Internal Gateway Protocol IGP: Routing Protocol used inside a self-government system.
4. Region: OSPF allows the interconnect network to be further divided into some areas. Each area contains one
Group neighboring networks and connected hosts, each gateway must be placed in one of them. Topological structures in each region are invisible to the area. Since the independence of the region topology is maintained, the route selection exchange information is smaller than when the AS is not separated. Routers with multiple interfaces can be added to multiple areas, which maintain a separate topology database for each area.
5, link status database: is the overall structure diagram of the network related to the router, which contains from the same
LSA received by all routers in the region (link status notification: contains the link interface, the metering standards and other variable information).
6, OSPF Dind: Responsible for sending routing information between two regions, which is routed by the zone boundary
Made of cross-regional networks and routers connected thereto. The AS boundary router running OSPF is learned from external routes through external gateway protocols or configuration information.
7, the specified router: If there is N gateways on a network, they can form N (N-1) / 2 possible adjoles. Whenever a gateway transmits a message, it transmits the message to all N-1 neighboring gateways, thus circulating (N-1) 2 link status. When a gateway is specified as a specified router, each gateway has neighboring relationship with the specified router, and there is no adjacency relationship with other gateways, and only N gateways connected to a particular network are only N-1 adjacency, transfer. The amount of information is greatly reduced. Another task of specifying the router is to send link state notices for the network, transmit link status update data. 8, Backup Specify Router: When the gateway on multiple access network does not select the specified router, the backup specified router is a specified router, and then the new backup specified router is selected in the remaining gateway. There may be 2N-3 adjacent relationships between N gateways at this time.
Third, OSPF packet format
Version number (1)
Type (1)
Data packet length (2)
Router ID (4)
Area ID (4)
Checksum (2)
Differential type (2)
Identification (8)
Data (variable)
Figure 2 OSPF packet format
The various fields have the following meaning (Figure 2):
Version number field: The version of OSPF is given.
Type field: OSPF has five types of packets:
Type 1: Hello packet, used to discover and maintain the accessibility of the neighboring station;
Type 2: Database Description packet, gives the abstraction to the abstract information of all link status items in its link status database;
Type 3: Link State Request packet, requests details of certain link status items to the other party;
Type 4: Link State Update packet, update the link status by flooding method;
Type 5: Link State Acknowledgment packet, confirmation of link update packets.
Data Packet Length field: The length of the OSPF packet, includes a packet header.
Router ID field: Identify the source of data packets.
Region ID field: Identifies the area to which the group belongs.
Check and field: Test the group content.
Identification Type Field: Data exchange between all OSPF protocol routers require authentication to ensure that only trusted routers can transmit routing information.
Identification field: including authentication information.
Data: OSPF packets of Type 1 to Type 5.
Fourth, the establishment and update of link status database
Each router regularly sends a link state advertisement LSA to provide the adjacency information of the router, or informing the status of other routers to change. By comparing the established adjacent router with the connection state, the failure router can quickly detect the link status database of the network, each router, with which the shortest path tree provides a route according to the calculation of a shortest path tree. Select the table. OSPF specifies that every two adjacent routers are exchanged once a Hello packet every 10 seconds to see which neighbors are up. Only the link status information of the servant adjacent station is stored in the link status database, and thus calculates the routing table. If there is no Hello message sent from an adjacent router, it is considered that the adjacent router can be unreachable, and the link status database should be immediately modified, and the routing table is recalculated.
When a router is just starting to work, it can only know which adjacent routers are working, and the cost required to send data to adjacent routers. OSPF allows each router with Database Description message and the adjacent router exchange this database existing link status summary information (indicating which router's link status information written to the database). The router then uses the Link State Request packet to request details of certain link status items you lack to the other party. Switching through a series of messages, the link status database of the whole network is established. During the network operation, as long as the link state of a router changes, the router uses the link state update packet to update the link status to the entire network with the flooding law. When a duplicate message arrives, the gateway discards the message without sending a copy. To ensure that the link status database is consistent with the status of the whole network, OSPF also specifies every time, such as 30 minutes to refresh the link status in a database.
V. OSPF map theory model
OSPF uses the map theory model of the network topology to calculate the shortest path. Each node in the OSPF topology map or corresponds to a gateway, or corresponds to a network. If there is a physical connection in the network, the OSPF map has a pair of pairs between the two nodes representing the entity, each side has a "right". OSPF establishes a selection route based on the principle of forwarding the datagram taken along the Towels.
Sixth, OSPF limited state machine model
There are two reasons to make Hello especially important for multiple access networks. First, the network hardware does not check or report the crash or restart of the gateway. In order to retain the state information of each other, the two gateways connected to the multiple access network must be exchanged. Second, it is possible to communicate directly between any two gateways connected to a multiple access network, so OSPF must prevent these gateways from forming too much adjacent.
The OSPF standard uses a limited state machine to specify how the gateway using Hello interands with adjacent network.
In general, all adjacent gateways are initially in the DOWN state, indicating that communication is not prepared. When a gateway receives the Hello packet sent by the neighbor gateway, it changes the neighboring network from the DOWN state to the init status. After that, adjacent gateways or enters the 2-WAY state, or enter the exstart state. Where 2-Way status indicates that communication has been established, but there is no adjacency between adjacent gateways and the gateway, and the exstart status indicates that there is not only communication, but there is a neighbor relationship between the two gateways.
When the negotiation ends, the gateway starts to exchange information in the link status database to ensure that they have exactly the same underlying interconnect network topology. One of the two adjacent gateways becomes a "main gateway", which queries information in another gateway database. The non-main gateway returns the database description packet to inform the main gateway to recently received information in the topology map in the topology map. When the neighbor relationship is established, the exchange information is especially important because the information in a gateway may become an outdated information during the network disconnect. Each topology information group contains a serial number, so the gateway can know if the description information in the neighboring gateway database is updated than the information in the gateway itself. After the exchange is completed and all topology information is loaded, the gateway enters the FULL state. In the Full state, the two gateways are regularly switched to keep the connection.
