The Autonomous System's topological database describes a directed
graph. The vertices of the graph consist of routers and networks.
A graph edge connects two routers when they are attached via a
physical point-to-point network. An edge connecting a router to a
network indicates that the router has an interface on the network.
The vertices of the graph can be further typed according to
function. Only some of these types carry transit data traffic; that
is, traffic that is neither locally originated nor locally destined.
Vertices that can carry transit traffic are indicated on the graph
by having both incoming and outgoing edges.
Vertex type Vertex name Transit?
_____________________________________
1 Router yes
2 Network yes
3 Stub network no
Table 1: OSPF vertex types.
OSPF supports the following types of physical networks:
Point-to-point networks
A network that joins a single pair of routers. A 56Kb serial
line is an example of a point-to-point network.
Broadcast networks
Networks supporting many (more than two) attached routers,
together with the capability to address a single physical
message to all of the attached routers (broadcast). Neighboring
routers are discovered dynamically on these nets using OSPF's
Hello Protocol. The Hello Protocol itself takes advantage of
the broadcast capability. The protocol makes further use of
multicast capabilities, if they exist. An ethernet is an
example of a broadcast network.
Non-broadcast networks
Networks supporting many (more than two) routers, but having no
broadcast capability. Neighboring routers are also discovered
on these nets using OSPF's Hello Protocol. However, due to the
lack of broadcast capability, some configuration information is
necessary for the correct operation of the Hello Protocol. On
these networks, OSPF protocol packets that are normally
multicast need to be sent to each neighboring router, in turn.
An X.25 Public Data Network (PDN) is an example of a non-
broadcast network.
The neighborhood of each network node in the graph depends on
whether the network has multi-access capabilities (either broadcast
or non-broadcast) and, if so, the number of routers having an
interface to the network. The three cases are depicted in Figure 1.
Rectangles indicate routers. Circles and oblongs indicate multi-
access networks. Router names are prefixed with the letters RT and
network names with the letter N. Router interface names are
prefixed by the letter I. Lines between routers indicate point-to-
point networks. The left side of the figure shows a network with
its connected routers, with the resulting graph shown on the right.
Two routers joined by a point-to-point network are represented in
the directed graph as being directly connected by a pair of edges,
one in each direction. Interfaces to physical point-to-point
networks need not be assigned IP addresses. Such a point-to-point
network is called unnumbered. The graphical representation of
point-to-point networks is designed so that unnumbered networks can
be supported naturally. When interface addresses exist, they are
modelled as stub routes. Note that each router would then have a
stub connection to the other router's interface address (see Figure
1).
When multiple routers are attached to a multi-access network, the
directed graph shows all routers bidirectionally connected to the
network vertex (again, see Figure 1). If only a single router is
attached to a multi-access network, the network will appear in the
directed graph as a stub connection.
**FROM**
* |RT1|RT2|
+---+Ia +---+ * ------------
|RT1|------|RT2| T RT1| | X |
+---+ Ib+---+ O RT2| X | |
* Ia| | X |
* Ib| X | |
Physical point-to-point networks
**FROM**
+---+ +---+
|RT3| |RT4| |RT3|RT4|RT5|RT6|N2 |
+---+ +---+ * ------------------------
| N2 | * RT3| | | | | X |
+----------------------+ T RT4| | | | | X |
| | O RT5| | | | | X |
+---+ +---+ * RT6| | | | | X |
|RT5| |RT6| * N2| X | X | X | X | |
+---+ +---+
Multi-access networks
**FROM**
+---+ *
|RT7| * |RT7| N3|
+---+ T ------------
| O RT7| | |
+----------------------+ * N3| X | |
N3 *
Stub multi-access networks
Figure 1: Network map components
Networks and routers are represented by vertices.
An edge connects Vertex A to Vertex B iff the
intersection of Column A and Row B is marked with
an X.
Each network (stub or transit) in the graph has an IP address and
associated network mask. The mask indicates the number of nodes on
the network. Hosts attached directly to routers (referred to as
host routes) appear on the graph as stub networks. The network mask
for a host route is always 0xffffffff, which indicates the presence
of a single node.
Figure 2 shows a sample map of an Autonomous System. The rectangle
labelled H1 indicates a host, which has a SLIP connection to Router
RT12. Router RT12 is therefore advertising a host route. Lines
between routers indicate physical point-to-point networks. The only
point-to-point network that has been assigned interface addresses is
the one joining Routers RT6 and RT10. Routers RT5 and RT7 have EGP
connections to other Autonomous Systems. A set of EGP-learned
routes have been displayed for both of these routers.
A cost is associated with the output side of each router interface.
This cost is configurable by the system administrator. The lower
the cost, the more likely the interface is to be used to forward
data traffic. Costs are also associated with the externally derived
routing data (e.g., the EGP-learned routes).
The directed graph resulting from the map in Figure 2 is depicted in
Figure 3. Arcs are labelled with the cost of the corresponding
router output interface. Arcs having no labelled cost have a cost
of 0. Note that arcs leading from networks to routers always have
cost 0; they are significant nonetheless. Note also that the
externally derived routing data appears on the graph as stubs.
The topological database (or what has been referred to above as the
directed graph) is pieced together from link state advertisements
generated by the routers. The neighborhood of each transit vertex
is represented in a single, separate link state advertisement.
Figure 4 shows graphically the link state representation of the two
kinds of transit vertices: routers and multi-access networks.
Router RT12 has an interface to two broadcast networks and a SLIP
line to a host. Network N6 is a broadcast network with three
attached routers. The cost of all links from Network N6 to its
attached routers is 0. Note that the link state advertisement for
Network N6 is actually generated by one of the attached routers: the
router that has been elected Designated Router for the network.
