Enchanter Space Studio: March 2009

Link State Routing Protocols

Responds instantly to network changes.
Sends triggered updates when a network change occurs
Periodic updates are sent at long intervals, such as every 30 minutes.

Link-state routing protocols generate routing updates only when a change occurs in the network.
- The router that detects the change will create a link-state advertisement (LSA) and propagates to all neighboring routers using special mulitcast address.
- Each routing device receives a copy of the LSA, forwards the same copy to all neighboring devices within the area, and updates its link-state database (LSDB).
- Flooding of the LSAs ensures that the routers can update their database with current information and update their routing tables with the new topology.
- The routers apply the Dijkstra algorithm (SPF) against the information on the LSDB to build the SPF tree.
- Each router selects the best paths from their SPF tree and places them in their routing table.
With link-state routing protocols, incorrect information form any particular router is less likely to cause confusion, because each router maintains its own view of the network - each router independently calculates its best paths to all destinations in the network.
The following information must be kept by each router in the network in order to make consistent routing decisions:
- It’s immediate neighbor routers - adjancency information is stored in the OSPF neighbor table, aka adjacency database.
- All other routers in the network (or in its area of the network) and their attached networks - LSAs stored in topology table or database (LSDB).
- The best path to each destination - held in the routing table.

OSPF Terminology

OSPF neighbor table = adjacency database
OPSF topology table = OSPF tpoplogy database = LSDB
Routing table = forwarding database

Distance Vector vs Link-State

One drawback of link-state protocols is the memory resources required to maintain these tables.
- However, link-state protocols have benefits that outweighs the “routing by rumor” limitations of distance vector.
- For instance, because the topology table is identical for all OSPF routers in an area and contains full information about all the routers and links in an area, each router can independently select a loop-free and efficient path, based on cost, to reach every network in the area.
With distance vector routing protocols, routers are not able to see a full picture of the network topology, therefore its routing decisions are based on the information provided by the adjacent neighbors.

OSPF Area Structure

With link-state routing protocols, routing calculations could require complex and significant time needed to compute route paths if the size of the network become too large.
Link-state routing protocols, like OSPF, can reduce the size of the calculations by partitioning the network into areas.
OSPF uses a two-layer area hierarchy:
- Transit Area
  - The primary function of this area is the fast and efficient movement of IP packets.
  - Transit areas interconnect with other OSPF area types.
  - Generally, end users are not found within a transit area.
  - OSPF area 0, also known as the backbone area.
- Regular Area
  - The primary function of this area is to connect users and resources.
  - Generally, it is not used to link to other areas. In other words, in order to travel from one area to another, the traffic must cross area 0 to get to the next area. It does not allow traffic to pass through it.
  - Also known as non-backbone area.
  - Subtypes are;
    - Standard Area
    - Stub Area
    - Totally Stubby Area
    - Not-so-stubby area (NSSA)
OSPF forces a rigid two-layer area hierarchy. The network’s physical connectivity must use the two-layer area structure where all non-backbone areas attaching directly to area 0.

OSPF Areas

The concept of areas, in a way, is a compromise for the problem of including all routing information to all routers involved in an internetwork. In a link-state protocol, all routers keep a copy of the LSDB. If the network grows in size, so does the LSDB that has to include information for each of the additional router in the growing network.
Using the OSPF area concept, routers within the same area can maintain a detailed database of all the links and database in the same area. OSPF can then be configured to contain only general or summary information about routers and links in other areas.

A failed link or router, with a proper OSPF configuration, floods that information to other adjacent routers about the failure only in the same area. Routers outside that area do not get this information.
A properly planned and configured hierarchical structure and limited number of routers in an area allows an OSPF autonomous system to scale to very large sizes.
- A hierarchical structure means that all areas must connect directly to area 0.
- Consider OSPF areas 1, 2, and 3 in the same autonomous system. All of these areas have routers inside these areas. Each of the areas 1, 2, and 3 must connect to the backbone area, or area 0. The router that connects each area to the backbone area 0 is called a Area Border Router (ABR).
- The optimal number of routers that can be inside one area, according to Cisco, is 50 routers per area.

Some OSPF area characteristics are:

Minimizes routing table entries.
Localizes the impact of topology change within an area.
Stops detailed LSA flooding at the area boundary.

Terminologies

Backbone Router
- Routers within area 0.
Area Border Router
- Connects area 0 to non-backbone areas.
- Separates LSA flooding zones
- Becomes the primary point for area address summarization
- Functions regularly as the source of default routes.
- Maintains the LSDB for each area with which it is connected
- The ideal design is to have each ABR connected to two areas only, the backbone and another area. Three areas are the recommended upper limit.

OSPF Adjacencies

The following steps describe how routers form neighbor adjacencies:

A router sends and receives hello packets to and from its neighboring routers. The packets are usually sent by multicasts.
The routers exchange hello packet and check whether certain pieces of information match between the two hello packets. Once they have checked that these information match, they can establish a neighbor relationship. The following list outlines the pieces of information that must match between hello packets:
- Subnet number/subnet mask
- Hello/Dead interval
- Area ID
- Authentication
- Stub Area Flag
Once the neighbor adjacency has been established, they can begin exchanging LSAs and confirm receipt of LSAs, and synchronize their LSDB. This puts the neighbor state between the routers in full adjacency.
If necessary, the routers forward any new LSAs to other neighboring routers, ensuring complete synchronization of link-state information inside the area.

Point-to-Point vs Broadcast Interface Types

On point-to-point serial link, two routers form a full adjacency with each other
OSPF routers on LAN links elect one router as the Designated Router (DR) and another as the Backup Designated Router (BDR)
- All other routers will form full adjacency with the DR and BDR, exchanging each other’s topology information, in the form of LSAs, indirectly through the DR and BDR (?)
- The DR is responsible for updating each routers by sending updates received from one neighbor on the LAN to all the other routers on the same LAN. One on of the main functions of a DR is to ensure that all the routers on the same LAN have an identical LSDB.
- If a new router is introduced to the LAN, the DR will pass its LSDB to the new router.
- Routers on the LAN also maintain a neighbor relationship with other non-DR and non-BDR routers in a two-way adjacency state also known as DROTHERs.

Link State

LSAs, also called link-state protocol data units (PDUs) facilitate the exchange of link-state information.
These LSAs let each routers know about the state of each routers and the links between routers - hence, link state.
LSAs are reliable; they are acknowledge after receipt.
LSAs are flooded throughout the area (or throughout the domain if there is only one area).
LSAs have a sequence number and a set lifetime, so each router recognizes that it has the most current version of the LSA.
LSAs are refreshed periodically to confirm topology information before they age out of the LSDB.

OSPF Metric Calculation

Link-state routing protocols use Dijkstra’s algorithm to calculate the best paths through a network.
- It is a mathematical algorithm created by Edsger Dijkstra.
- The best path to a destination is calculated by assigning a cost to each link in the network, and by placing the specific node at the root of the tree, and adding up the costs toward each given destination. The best path is then added to the routing table.
The interface cost is calculated based on its configured bandwidth.
The default cost is calculated using the formula Reference Bandwidth / Interface Bandwidth, where the reference bandwidth is equal to 100Mbps and the the interface bandwidth is expressed in Mbps (Ethernet interface bandwidth defaults to use kbps)
Alternatively, the OSPF cost for each interface can be manually configured - this overrides the default cost value.

Link-State Data Structures

LSAs carry a link-state age field value of 30 minutes. This acts as an aging timer for the LSAs.
- When the timer expires, the router that originally sent the entry sends the LSA, with a higher sequence number, in a link-state update (LSU). This is done to verify that the link is still active.
- The LSU can contain one or more LSAs
- Compared to a distance-vector router, which sends the whole routing table at short intervals, the LSA validation saves bandwidth by the infrequent (every 30 minutes) sending of the update.
When a router receives an LSU, it does the following:
- If the router does not have the LSA entry it just received in its LSDB, the router adds the entry, sends back an acknowledgement (LSack), floods the information to other routers, runs SPF, and updates its routing table.
- If the entry already exists and the LSA has same sequence number), it is ignored
- If the entry already exists but the has a higher sequence number - which means it has new information, it does the same as the first step.
- If the entry already exists but the LSA includes older information, it sends an LSU to the sender with its newer information

OSPF Packets

Type	Packet Name	Description
1	Hello	Discovers neighbors and builds adjacencies between them. Sent periodically on all interfaces (including virtual links) in order to establish and maintain neighbor relationship.
2	Database Description (DBD)	Checks for database synchronization between routers. These packets are exchanged when an adjacency is being initialized. They describe the contents of the topological database. Multiple packets may be used to describe the database
3	Link-State Request (LSR)	Requests specific link-state record from another router. After exchanging DBDs with a neighbor, a router may find that parts of its topological database are out of date. The LSR packet is used to request pieces of the neighbor’s database that are more up to date. Multiple LSRs may need to be used. The sending of LSRs is the last step in bringing up an adjacency.
4	Link-State Update (LSU)	Sends specifically requested link-state records. These packets implement the flooding of link state advertisements. Each LSU carries a collection of link state advertisements one hop further from its origin. Several link state advertisements may be included in a single packet. In order to be reliable, flooded advertisements are acknowledged in LSack packets.
5	Link-State Acknowledgment (LSack)	Acknowledges the other packet types. Acknowledgment is accomplished through the sending and receiving of LSack packets. Multiple LSAs can be acknowledged in a single LSack packet.

All five OSPF packets are encapsulated directly into an IP packet, bypassing the TCP/IP transport layer completely.
The OSPF packet does not use TCP or UDP, but still need a reliable transport scheme, therefore it defines its own acknowledgment routine using an acknowledgment packet (LSack).
In the IP header, an OSPF packet is identified with a Protocol ID number of 89.
The same header format shown below applies to each OSPF packet type.

The fields on the OSPF header are as follows:

Version number - Version 2 for IPv4
Type - refers to one of the 5 types of OSPF packets (Hello, DBD, LSR, LSU, LSack)
Packet Length - The length of the OSPF packet in bytes.
Router ID - The RID of the source router
Area ID - The OSPF area where the packet originated
Checksum - Used for packet header error detection to ensure that the OSPF packet was not corrupted during transmission.
Authentication Type - Describes either no authentication, cleartext passwords, or encrypted Message Digest 5 (MD5) for router authentication.
Authentication - Used with authentication type.
Data - Contains different information, depending on the OSPF packet type:
- Hello - A list of known neighbors.
- DBD - Summary of the LSDB, which includes all known router IDs and their last sequence number, among a number of other fields.
- LSR - Contains the type of LSU needed and the router ID of the router that has the needed LSU
- LSU - Contains the full LSA entries. Multiple LSA entries can fit in one OSPF update packet.
- LSack - Empty.

Establishing OSPF Neighbor Adjacencies: Hello

The Hello protocol establishes and maintains neighbor relationship by making sure that there is continuous two-way communication between two neighbors.
- A two-way communication is established when a router receives a hello packet from a neighbor and it sees its own RID listed on the packet.
Hello packets use the IP multicast address 224.0.0.5 for sending and receiving.
The following information is contained in a hello packet:
- Router ID
  - A 32-bit number that uniquely identifies the router.
  - The highest active IP address is chosen as the RID unless a loopback interface exsits. A manually configured RID, however, wins over all.
  - RID is also used as tie breakers during the DR and BDR election process.
- Hello Interval
  - Specifies how often a router sends hello packets. 10 seconds is the default for multi-access networks.
- Dead Interval
  - Amount of time that a router waits to hear from a neighbor before considering the link to the neighbor is dead. 40 seconds or four times the hello interval is the default timer.
- Neighbors
  - Lists the neighbor routers that this router has established adjacency.
- Area ID
  - The OSPF area ID.
  - To communicate, two routers must share a common segment and their interfaces must belong to the same OSPF area on that segment.
  - They must also share the same subnet and mask
- Router Priority
  - An 8-bit number that indicates the router’s priority.
  - Priority is used when selecting a DR and BDR.
- DR and BDR IP Address
  - The IP address for the DR and BDR for the specific multiaccess network.
- Authentication password
  - The password for authentication, if enabled
- Stub Area Flag
  - A special area that helps reduce routing updates by replacing them with a default route.

Exchange Process and OSPF Neighbor Adjacency States

Down State - An OSPF process starts in down state before any information is exchanged between two neighboring routers. The exchange process begins with a router sending a hello out each interface that is configured for OSPF. The hello packet is sent out multicast address 224.0.0.5.
Init State - Directly connected routers configured for OSPF receives the packet from the originating router. These routers will add the originating router to their list of neighbors. This state is the init state.
These routers that received the hello packets in turn send unicast reply packet back to the originating router, sending along with it information about themselves. The Neighbor field in the hello packet that they send back lists neighboring routers they know about, including the recently learned router that originally sent the hello packet.
Two-way State - When the originating router receives the hello back from the other neighbors, it notices that its own RID is included in the list of neighbors. At this point a two-way state is reached. They now have bi-directional communication.
On a broadcast link type, such as an Ethernet LAN, a DR and BDR must be elected. The DR will form a bi-directional adjacency with each routers on the LAN link.
- If a new router joins the broadcast network in which a DR and BDR already exist, it will get to the two-way state with all the routers, including the DR and BDR, and those that are DROTHER. The new router will form a bidirectional adjacency with only the DR and BDR.
Every 10 seconds, the routers exchange hello packets to ensure there is still communication established.

The routers are considered to be in the exstart state once the DR and BDR are selected. At this point they are ready to exchange link-state information with other routers and start creating their LSDBs.
The exchange protocol is the process used to discover the network routes and gets the routers to afull state.
The first step in this process is for the DR and BDR to establish adjacencies with each of the the other routers.
Once the adjacent routers are in a full state, they do not repeat the exchange protocol unless the full state changes.

The following lists the exchange protocol process:

Exstart State
- Master and slave relationship between each router and DR and BDR.
- The router with the higher router ID acts as the master during the exchange process.
- Only the DR exchanges information with the other routers. Non-DR and non-BDR routers don’t exchange information.
Exchange State
- DBD packets (also called DDPs) are exchanged between master and slave routers.
- A DBD contains a summary of the LSA entry headers in the sending router’s LSDB.
- The entries can be about a link or a network.
- An LSA entry header includes
  - Information about the link-state type
  - The address of the advertising router
  - The link’s cost
  - Sequence number
- The sequence number determines the “newness” of the received link-state information.
The following actions are performed upon receipt of the DBDs:
- An LSack packet is sent to acknowledge receipt of the DBD
- The received DBD is compared against the contents of the receiving router’s own LSDB.
  - Loading State - if the router finds that the DBD contains a more updated information, it sends an LSR to the other router. The process of sending the LSR is called theloading state.
- The other router sends an LSU that contains the complete information about the requested entry.
- The LSU is received and an LSack is sent back to acknowledge receipt of the LSU
The router then adds the new link-state entries into its LSDB.

The routers are considered synchronized and in full state once all LSRs have been received and updated.
In order to route, all routers must be in full state. When in full state, all routers in the are should have identical LSDB.

Maintaining Routing Information

If something changes in a link-state environment, the routers notify the other routers in the network about the changes.
- The notifications are sent through a flooding process.
- LSUs provide the mechanism for flooding LSAs.
The steps for the flooding process looks like the following:
1. A router notices that a link state change on one of its interface. An LSU packet containing and updated LSA packet is sent out to multicast address 224.0.0.6: This address goes to all DRs and BDRs.
2. The DR sends an LSack back to the original sender. At the same time, the LSU is flooded out to multicast address 224.0.0.5, which goes out to all other OSPF enabled routers.
  - Each router that receives the LSU responds with an LSack to acknowledge receipt.
  - To make the flooding procedure reliable, each LSA must be acknowledged separately.
3. If a router is connected to another network, it floods the LSU to the DR of the other network. That DR, in turn, multicasts the LSU to other routers in the network.
4. Once the LSAs have been received, as delivered by the LSU, the LSDB is updated and recomputes new paths.

OSPF Multicast Address

224.0.0.5 - goes to all OSPF routers.
224.0.0.6 - goes to the DR and BDR.

To simplify OSPF synchronization, only adjacent routers are required to remain synchronized.

Every 30 minutes, summaries of individual link-state entries are sent to ensure LSDB synchronization. Only summaries and not the complete link-state entries are sent.
Each link entry has a timer to determine when the next LSA refresh update must be sent.
The maximum age is 60 minutes, meaning that if an LSA is not refreshed after 60 minutes, it is removed from the LSDB.

NOTE: In a Cisco router, if a route already exists, the routing table is used at the same time the SPF algorithm is calculating. However, if the SPF is calculating a new route, the new route is used only after the SPF calculation is complete.

OSPF Link-State Sequence Numbers

The link-state sequence numbers helps OSPF maintain an up-to-date database, with most recent link-state records.
The link-state sequence number field is found in an LSA header. It is 32 bits long.
The left most bit set starts with 0×80000001 and ends with 0×7FFFFFFF
It is used to detect old and redundant LSA records. The larger the number, the more recent the LSA is.
LSRefreshTime is the interval by which OSPF refreshes each LSA - every 30 minutes.
The sequence number is incremented by 1 each time a record is flooded.
When a new LSA update is received, the maximum age timer is reset.
An LSA never remains in the database for longer than the maximum age of 60 minutes without a refresh.
An LSA can exist in the database for long periods of time as long as it is refreshed every 30 minutes.
If a sequence number has reached the highest bit set (0×7FFFFFFF), it wraps back around and restarts its sequence to 0×80000001. This processes forces the existing LSA to be flushed out by setting the maxage timer immediately to 60 minutes.

sh ip ospf database Command Output

The following shows how the LS age and LS sequence numbers are kept in the database.

Link ID - the ID of the router that created the router LSA
Adv Router (or Advertising Router) - the router ID of teh OSPF router that announced the router LSA.
- The link ID and Adv router for a router LSA are generally the same.
Age - how long ago (in seconds) the last update occured
Seq# - The number of times the LSA for a link has been updated.

In the figure above, the router LSA with link ID 192.168.1.1 has been updated 11 times (seq# 0×8000000B) and the last update occurred 17 seconds ago.

The debug ip ospf packet command is used to troubleshoot and verify that OSPF packets are flowing properly between two routers.

debug ip ospf packet Command Output

The following describes the fields represented in the output:

v: - indentifies the version of OSPF. For IPv4, it is version 2.
t: - Specifies the packet type:
- 1 - hello
- 2 - DBD
- 3 - LSR
- 4 - LSU
- 5 - LSAck
l: - Specifies the OSPF packet length in bytes. 48 bytes in the example above.
rid: - Displays the OSPF router ID
aid: - Displays the OSPF area ID
chk: - Displays the OSPF checksum
aut: - Authentication type:
- 0 - No authentication
- 1 - Simple password
- 2 - MD5
auk: - Specifies authentication key if used
keyid: - Displays MD5 key ID
seq: - Provides the sequence number; only used for MD5 authentication

Enchanter Space Studio

Monday, March 30, 2009

编程入门教程（英文）

Thursday, March 26, 2009

BSCI: OSPF Overview