6.2 Topology Model

The LSAG uses a topology model to generate messages described in the previous section. Apart from generating these messages, the LSAG is also required to efficiently support real-time queries about the network topology, such as ``how many routers does area X have?'' or ``how many interfaces does router X have in area Y?''. This requires a model that can be updated and searched efficiently, and can be scaled to networks consisting of hundreds of routers and thousands of links.

We have designed and implemented a model meeting these goals, which consists of the following six classes:

1.

Area: represents an OSPF area.

2.

Rtr: represents a router.

3.

AreaRtr: represents area-specific parameters of a router. Recall that OSPF does not assign a router to an area. It assigns each interface of a router to an area. Thus, a router can have some interfaces in each of several areas. An AreaRtr object contains the set of interfaces a router has in a given area.

4.

Ntw: represents a subnet or a prefix.

5.

Intf: represents an interface of a router.

6.

Link: represents a unidirectional weighted edge in the topology. The monitor classifies links into three types: intra-area links that represent link between a pair of routers or a router-subnet pair, inter-area links to represent summary routes injected by border routers, and external links to represent external routes redistributed into OSPF. The local and remote ends of each link are objects of one of the above mentioned five classes.

  

Figure 3: Topology model of the LSAG.

 Figure 3 shows the model in terms of ``containment'' relationship between objects of these six classes. For example, at the highest level, the model consists of a set of Area objects representing the areas of the OSPF network. Each Area object in turn contains a set of Ntw objects representing all the subnets of the associated area. AreaRtr objects are special. Since each AreaRtr object represents area-specific parameters of a router, it is contained in two objects: a Rtr object, and an Area object. In our implementation, search, add and delete operations on the objects are implemented via hash tables, enabling scaling to large networks.

Upon receiving an LSA, the LSAG updates the relevant part of the topology model. As an example, consider what happens when the LSAG receives a router LSA. The LSAG has to update the AreaRtr object that represents the router LSA. This may result in addition or deletion of interfaces, or a change in the administrative weight of interfaces. Router LSA can also result in addition or deletion of an AreaRtr object.

The topology model conveniently allows the identification of a flapping node and generation of the associated flap message (see  Section 6.1. The LSAG considers a node to be flapping if the node goes down and comes up n times within a t second time frame, where both n and t are configurable parameters. To identify flaps, each node of the OSPF topology is mapped to a specific object of the topology model. This mapping is shown in  Figure 6.3 by statements of the form ``flapping xxx'' under appropriate objects. For example, an external route is mapped to a Link object in the set of external links in the Rtr object representing the advertising router.

The topology model is also used for identifying LSA storms. As described in   Section 6.1, the LSAG issues an LSA storm message if many new copies of a refresh LSA are received within a short time period. Note that LSAs that indicate change(s) to the model are not considered a part of an LSA storm. More precisely, the LSAG issues a warning about too many LSA copies if it receives n refresh copies of an LSA within t seconds. To identify LSA storms, each LSA is mapped to a specific object of the topology model. The mapping is intuitive in the sense that the LSA essentially describes the status of the object it is mapped to. For example, each router LSA is mapped to an AreaRtr object. Similarly, each external LSA is mapped to a Link object in the set of external links of a Rtr object.