Monday, March 30, 2009

编程入门教程(英文)

C
Introduction to C Programming
C Optimization Tutorial
Compiling C and C++ Programs on UNIX Systems - gcc/g++
Building and Using Static and Shared C Libraries
Programming in C: UNIX System Calls and Subroutines Using C
C FAQ
C Programming Class Notes
ANSI C for Programmers on UNIX Systems
Sams Teach Yourself C in 24 Hours
Sams Teach Yourself C in 21 Days (4th Ed.)
The Standard C Library for Linux - Part 1: file functions
The Standard C Library for Linux - Part 2: character input/output
The Standard C Library for Linux - Part 3: formatted input/output
The Standard C Library for Linux - Part 4: Character Handling
The Standard C Library for Linux - Part 5: Miscellaneous Functions
Programming in C: A Tutorial
An Introduction to C Development on Linux
C Programming Course
C Language Tutorial
CScene: An Online Magazine for C and C++ Programming

C++
C++ Tutorial
Understanding C++: An Accelerated Introduction
An Introduction to C++ Class Hierarchies
G++ FAQ
Introduction to Object-Oriented Programming Using C++
Compiling C and C++ Programs on UNIX Systems - gcc/g++
C++ FAQ Lite
C++ Programming Language Tutorials
Reducing Dependencies in C++
C++ Exception Handling
Part 1: Unicode
Part 2: A Complete String Class
Making C++ Loadable Modules Work
Sams Teach Yourself C++ in 21 Days (2nd Ed.)
C++ Portability Guide
C++ Tips
C++ Language Tutorial
CScene: An Online Magazine for C and C++ Programming
C++ Libraries FAQ

CGI
CGI Programming Tutorial
CGI Programming 101
CGI Manual of Style
CGI Developer’s Guide
CGI Programming Unleashed
Sams Teach Yourself CGI Programming with Perl 5 in a Week (2nd Ed.)
CGI/Perl Tips, Tricks and Hints
A Tour of HTML Forms and CGI Scripts
Reading CGI Data: URL-Encoding and the CGI Protocol
CGI Programming FAQ

CORBA
CORBA FAQ
A Brief Tutorial on CORBA
CORBA 2.0 Specification
CORBA Tutorials
Sams Teach Yourself CORBA in 14 Days
Linux Network Programming, Part 3 - CORBA: The Software Bus
CORBA Program Development, Part 1
CORBA Program Development, Part 2
CORBA Program Development, Part 3

CSS
CSS2 Tutorial

CVS
CVS Tutorial
Concurrent Version System Tutorial

DHTML
Introduction to Dynamic HTML

Emacs
Emacs: The Software Engineer’s “Swiss Army Knife”
Emacs FAQ
GNU Emacs Lisp Reference Manual
Programming in Emacs Lisp
GNU Emacs Manual
A Tutorial Introduction to Emacs
EMACSulation: Internet-ready!
EMACSulation: Ediff - An Emacs interface to diff and patch
EMACSulation: Emacs as a Server
EMACSulation: Customizing Emacs
Basic Emacs
EMACSulation: Templating Mechanisms
Emacs Macros and the Power-Macros Package
Polyglot Emacs 20.4

Expect
Advanced Programming in Expect: A Bulletproof Interface
Automating Tasks with Expect
What Can you Expect?–A Data Collection Project Using Linux

Fortran
Professional Programmer’s Guide to Fortran 77
Fortran 90 and Computational Science
User Notes on Fortran Programming
Fortran Programming for Physics and Astronomy
A Fortran 90 Tutorial
Using GNU Fortran
Fortran 90: A Course for Fortran 77 Programmers
Fortran 90 for the Fortran 77 Programmer
Introduction to Fortran

GIMP
GIMP Tutorial Index
A Tutorial for Perl GIMP Users
A Scheme Tutorial for GIMP Users
GIMP Guide
The GIMP User Manual
Pseudo 3-D with GIMP
Graphical Photocomposition with GIMP
Creating Text with the GIMP
Creating Fire Effects with the GIMP
Creating and Editing Animations with GIMP
GIMP-Perl: GIMP Scripting for the Rest of Us
Writing a GIMP Plugin
GIMP: The RRU Tutorial
GIMP User FAQ
Script-Fu Tutorial
The Quick Start Guide to the GIMP, Part 1
The Quick Start Guide to the GIMP, Part 2
The Quick Start Guide to the GIMP, Part 3
The Quick Start Guide to the GIMP, Part 4

GNOME
Application Programming Using the GNOME Libraries
Part 1: Everything You Need to Get Started
Part 2: Building a Sample Genealogy Program
Part 3: Adding File Saving and Loading Using libxml
Creating GTK+ Widgets with GOB: An Easier Way to Derive New GTK+ Widgets
Handling Multipel Documents: Using the GnomeMDI Framework
Livening Things Up: Graphics Made Easy Using the GNOME Canvas
Developing Gnome Applications with Python - Part 1

GTK
GDK Reference Manual
GLib Reference Manual
GTK+ Reference Manual
The GIMP Toolkit
GTK+ FAQ
GTK V1.2 Tutorial
Drawing and Event Handling in GTK
An Introduction to the GIMP Tool Kit

Gnuplot
Constrained Dynamics
Continuum Dynamics
Differential Equation Basics
Energy Functions and Stiffness
Particle System Dynamics
An Introduction to Physically Based Modeling
Rigid Body Dynamics I
Rigid Body Dynamics II
Scientific Visualization Tutorials
Gnuplot - An Interactive Plotting Program
GIF Animation Tutorial

HTML
HTML Table Tutorial
HTML by Example
How to Use HTML 3.2
Creating a Client-Side Image Map
Advanced HTML: How to Create Complex Multimedia Documents for the Web
The ABCs of HTML
Sharky’s Netscape Frames Tutorial

ILU
ILU Reference Manual
Using ILU with ANSI C: A Tutorial
Using ILU with Java: A Tutorial
Using ILU with Python: A Tutorial

IP-Masquerading
ipchains: Packet Filtering for Linux 2.2
Setting Up IP Masquerade
Setting Up IP-Masquerading
Ipchains: Easy Links to the Net
Linux Networking Using Ipchains

IPC
Advanced 4.4BSD Interpprocess Communication Tutorial
UNIX Multi-Process Programming and IPC

Java
Enterprise JavaBeans Tutorial
JavaBeans Short Course
Introduction to the JavaBeans API
JDBC Short Course
Essentials of the Java Programming Language, Part 1
Essentials of the Java Programming Language, Part 2
Writing Advanced Applications for the Java Platform
Fundamentals of Java Security
Fundamentals of Java Servlets
Introduction to the Collections Framework
Introduction to CORBA
Fundamentals of RMI
Advanced
Introductory
Intermediate
Java Language Specification
Java Tutorial: Servlet Trail
Java Virtual Machine Specification (2nd Ed.)
Glossary of Java and Related Terms
The Java Language Environment
Java Look and Feel Design Guidelines
Story of a Servlet: An Instant Tutorial
Introduction to Java
Java2D: An Introduction and Tutorial
Java Servlet Tutorial
comp.lang.java FAQ
Brewing Java: A Tutorial
Shlurrrppp … Java: The First User-Friendly Tutorial on Java
Swing Tutorial
Swing: A Quick Tutorial for AWT Programmers
Thinking in Java
Java RMI Tutorial
Java for C++ Programmers
The Advanced Jav/aJ2EE Tutorial
Hacking Java: The Java Professional’s Resource Kit
JFC Unleashed
Java Developer’s Guide
Java Developer’s Reference
Sams Teach Yourself Java in 21 Days (Professional Reference Ed.)
Java Unleashed (2nd Ed.)
Java 1.1 Unleashed (3rd Ed.)
Java Game Programming Tutorial
Java Networking FAQ
Java Tutorial: A Practical Guide for Programmers
Sockets Programming in Java
Programming with Java - Part I
Programming with Java - Part II
Setting Up a Java Development Environment for Linux
Understanding Java
Beginner’s Guide to JDK
GUI Development in Java
Java Servlets: An introduction to writing and running Java servlets on Linux

JavaScript
Introductory JavaScript Tutorials
JavaScript Authoring Guide
Client-Side JavaScript 1.3 Guide
Client-Side JavaScript 1.3 Reference
Core JavaScript 1.4 Guide
Core JavaScript 1.4 Reference
Server-Side JavaScript 1.4 Guide
JavaScript FAQ
JavaScript Tutorial
The Way of JavaScript
Voodoo’s Introduction to JavaScript
JavaScript Tutorial for Programmers
JavaScript Primer
EchoEcho JavaScript Tutorial
Sams Teach Yourself JavaScript 1.1 in a Week (2nd Ed.)

Lisp
Common Lisp Hints
Common Lisp the Language (2nd Ed.)
Lisp FAQ
Lisp Programming Tutorial
Lisp Tutorial
LISP Tutorial
Common Lisp HyperSpec

MIDI
Basic MIDI Tutorials
Tutorial on MIDI and Music Synthesis

ML
ML Tutorial
Programming in Standard ML ‘97
A Gentle Introduction to ML
Moscow ML Owner’s Manual

MPI
An MPI Tutorial
Tutorial on MPI
MPI: Portable Parallel Programming for Scientific Computing
Tuning MPI Applications for Peak Performance
MPI: From Fundamentals to Applications
MPI Tutorial
MPI: The Complete Reference
Introduction to Parallel Programming Using MPI
Basics of MPI Programming

Matlab
Matlab Basics Tutorial
Matlab Summary and Tutorial
Matlab - Official Online Manuals in PDF

Misc
The Soar 8 Tutorial Home Page

Thursday, March 26, 2009

BSCI: OSPF Overview

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

TypePacket NameDescription

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

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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:

  1. 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.
  2. 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.
  3. 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
  4. 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