Monday, August 13, 2012

OSPF Packet Details & Dijkstra's Algorithm: Shortest Path Video

Taken from http://cisco.iphelp.ru/faq/5/ch08lev1sec1.html#ch08fig01

Dijkstra's Algorithm: Shortest Path - Easy To Understand


OSPF Packet Details

OSPF has five types of packets used for various reasons. Table 8-1 documents the different OSPF packet types and describes their functionality.

Table 8-1. OSPF Packet Types
Type Description Functionality
1 Hello To discover neighbors and form DR/BDR relationship and exchange neighbor capabilities.
2 Database description To elect master/slave for the database exchange process and to exchange the LSA headers and select the first sequence number for database exchange.
3 Link-state request To request a specific LSA that is seen during the DBD exchange process.
4 Link-state update To send the entire LSA to the neighbor who requested the particular LSA through the link request packet. This packet is also used in flooding.
5 Link-state acknowledge To acknowledge the receipt of the link-state update packet.
All the OSPF packet types share a common 20-byte OSPF protocol header. Figure 8-1 shows the common OSPF protocol header format.
Figure 8-1. Common OSPF Protocol Header Format
graphics/08fig01.gif
The list that follows describes the fields in the OSPF protocol header:
  • Version Number— This field represents the current version number of OSPF. The latest version is 2. Version 1 is not compatible with Version 2.
  • Type— This field indicates which of the five types of OSPF packets is appended at the end of this header.
  • Packet Length— This field contains the length of the entire OSPF packet, including the OSPF header.
  • Router ID— This field contains the 4-byte IP address. The router ID is used to uni-quely identify the router throughout the autonomous system. For a Cisco box, this field contains the highest IP address on the box. If loopbacks are configured, the highest loopback becomes the router ID.
    After the router ID is chosen, it will not change unless the router is restarted, the inter-face that is selected as a router ID is shut down, or the IP address has been removed or replaced on that interface.
  • Area ID— This field designates the area number to which this packet belongs. This is also a 4-byte number. The value must be the same on both sides to form neighbor relationships. There are two ways to write this: Area 1 or Area 0.0.0.1. There is no difference between the two.
  • Checksum— This field includes the checksum for the entire OSPF packet, excluding the authentication for data corruption.
  • AuType— This field contains the type code for the authentication:
    - 0 means that there is a null authentication.
    - 1 means that the authentication type is plain text.
    - 2 means that the authentication type is MD5.
  • Authentication— This 64-bit field contains the authentication key in case of plain-text authentication. In case of message digest, the 64-bit Authentication field is redefined into several other parameters. See Appendix D of RFC 2328 for more detail on the MD5 authentication scheme.

Hello Packets

Hello packets are the first type of packets in OSPF. Figure 8-2 illustrates the Hello packet format. Hello packets are used to form a neighbor relationship between two routers. In environments that include broadcast/nonbroadcast media, Hello packets are used to elect the designated (DR) and backup designated (BDR) routers. On broadcast media, the destination address of the Hello packets is 224.0.0.5. On nonbroadcast media, the destination address is unicast.
Figure 8-2. Hello Packet Format
graphics/08fig02.gif
The list that follows describes the fields in the Hello packet:
  • Network Mask— Represents the network mask of the interface on which OSPF is running. The network mask is checked only on broadcast media.
  • Hello Interval— Represents the number of seconds between two Hello packets. This interval must be the same for the two routers that are trying to form an adjacency. The Hello interval is 10 seconds on broadcast and point-to-point media, and 30 seconds on all other media.
  • Options— Represents the optional capabilities supported by the router. The Options field has the following format:
    * O DC EA N/P MC E T
    - O bit is used for opaque LSAs, mentioned in RFC 2370
    - DC is used for demand circuit capabilities, mentioned in RFC 1793
    - EA is the external attribute
    - N/P is used for not-so-stubby area (NSSA) option, mentioned in RFC 1587
    - MC designates multicast OSPF
    - E, when set, means that external LSA are allowed in this area
    - T bit is used for ToS capability (normally set to 0)
    The first bit in the Options field is reserved for future use. Cisco routers also do not use EA and MC bits.
  • Rtr Pri— Used for a router's priority. By default, this value is set to 1. This field plays an important role in electing the DR and the BDR. A higher priority increases the chances that the router will become the DR. A priority of 0 means that this router will not take part in DR election.
  • Router Dead Interval— Represents the number, in seconds, before a neighbor is declared dead. By default, the dead interval is four times the Hello interval.
  • Designated Router— Lists the IP address of the designated router. If there is no DR, this field has a value of 0.0.0.0. The DR is elected through the Hello protocol. The router with the highest priority becomes the DR. If the priorities are equal, the router with the highest router ID becomes the DR. The purpose of the DR is to reduce the amount of flooding on multiaccess media. The DR uses multicasting to reduce the amount of flooding. All routers flood their link-state database to the DR, and the DR then floods that information back to other routers on that segment. No DRs/BDRs exist on point-to-point or point-to-multipoint segments.
  • Backup Designated Router— Identifies the BDR and lists the interface IP address of the BDR. If no BDR exists, this field has a value of 0.0.0.0. The BDR is also elected through the Hello protocol. The purpose of the BDR is to serve as the backup of the DR, for a smoother transition in case the DR dies. BDR remains passive during flooding.
  • Neighbor— Contains the router ID of each neighbor from which a Hello is seen.

Database Description Packets

The second type of OSPF packet, the database description (DBD) packet, is used mostly during the database exchange. The first DBD packet is used to elect the master and slave relationship and to set the initial sequence number elected by the master. The router with the highest router ID becomes the master and initiates the database synchronization. The master sends the sequence number, and the slave acknowledges it. After the master and the slave are elected, the database synchronization starts; in this process, the headers of all the LSAs are exchanged with neighbors. Figure 8-3 illustrates the DBD packet format.
Figure 8-3. Database Description Packet Format
graphics/08fig03.gif
The list that follows describes the fields in the DBD packet:
  • Interface MTU— This field contains the largest data size, in bytes, that can be send through the associated interface. This option has been added starting from RFC 2178. This field must be set to 0 when sending the packet over a virtual link.
  • Options— Options for this field were discussed in the previous section on the Hello packet format.
  • I Bit— When set to 1, this means that this is the first packet in DBD exchange.
  • M Bit— When set to 1, this means that more packets will follow.
  • MS Bit— Use this for master and slave. When this bit is set, it means that the router is a master in the DBD exchange process. If this bit is set to 0, it means that the router is the slave.
  • DBD Sequence Number— This field contains a unique value set by the master. This sequence number is used during database exchange. Only a master can increment the sequence number.
  • LSA Header— This field consists of a list of the link-state database headers.

Link-State Request Packets

The Type 3 OSPF packet, a link-state request packet, is sent if part of the database is missing or out-of-date. The link-state request packet is used to retrieve that precise piece of database information that is missing. Link-state packets are also used after the DBD exchange is finished to request the LSAs that have been seen during the DBD exchange. Figure 8-4 illustrates the link-state request packet format.
Figure 8-4. Link-State Request Packet Format
graphics/08fig04.gif
The list that follows describes the fields in the link-state request packet:
  • LS Type— Identifies what type of LSA is being requested.
  • Link-State ID— Represents the link-state ID of that specific LSA. Link-state ID is discussed later in this chapter.
  • Advertising Router— Contains the router ID of the router that is originating this LSA.

Link-State Update Packets

OSPF packet Type 4, the link-state update packet, implements flooding. Several LSAs are included in a single packet. Link-state update packets are also sent in response to link-state request packets. Flooded LSAs are acknowledged in the LSA acknowledgment packet. If an LSA is not acknowledged, it is retransmitted every retransmit interval (5 seconds, by default). Figure 8-5 illustrates the link-state update packet format.
Figure 8-5. Link-State Update Packet Format
graphics/08fig04.gif
As Figure 8-5 shows, this packet contains the number of LSAs (for example, 10 or 20 LSAs), followed by the LSA itself.

Link-State Acknowledgment Packet

The last type of OSPF packet, the link-state acknowledgment packet, is used to acknow-ledge each LSA. This packet is sent in response to link-state update packets. Multiple LSAs can be acknowledged in a single link-state acknowledgment packet. This packet is respon-sible for the reliable delivery of link-state update packets. Figure 8-6 illustrates the link-state acknowledgment packet format.
Figure 8-6. Link-State Acknowledgment Packet Format
graphics/08fig06.gif
Link-state acknowledgment packets are sent as multicasts. If the state of the router is DR or BDR, the acknowledgment is sent to the OSPF router multicast address of 224.0.0.5. If the state of the router is not DR or BDR, the acknowledgment is sent to the all DR router multicast address of 224.0.0.6.



No comments:

Post a Comment