ospf_fundamentals.texi 20 KB

  1. @c Copyright 2006 Sun Microsystems, Inc. All Rights Reserved.
  2. @cindex OSPF Fundamentals
  3. @node OSPF Fundamentals
  4. @section OSPF Fundamentals
  5. @cindex Link-state routing protocol
  6. @cindex Distance-vector routing protocol
  7. @acronym{OSPF} is, mostly, a link-state routing protocol. In contrast
  8. to @dfn{distance-vector} protocols, such as @acronym{RIP} or
  9. @acronym{BGP}, where routers describe available @dfn{paths} (i.e@. routes)
  10. to each other, in @dfn{link-state} protocols routers instead
  11. describe the state of their links to their immediate neighbouring
  12. routers.
  13. @cindex Link State Announcement
  14. @cindex Link State Advertisement
  15. @cindex LSA flooding
  16. @cindex Link State DataBase
  17. Each router describes their link-state information in a message known
  18. as an @acronym{LSA,Link State Advertisement}, which is then propogated
  19. through to all other routers in a link-state routing domain, by a
  20. process called @dfn{flooding}. Each router thus builds up an
  21. @acronym{LSDB,Link State Database} of all the link-state messages. From
  22. this collection of LSAs in the LSDB, each router can then calculate the
  23. shortest path to any other router, based on some common metric, by
  24. using an algorithm such as @url{http://www.cs.utexas.edu/users/EWD/,
  25. Edgser Dijkstra}'s @acronym{SPF,Shortest Path First}.
  26. @cindex Link-state routing protocol advantages
  27. By describing connectivity of a network in this way, in terms of
  28. routers and links rather than in terms of the paths through a network,
  29. a link-state protocol can use less bandwidth and converge more quickly
  30. than other protocols. A link-state protocol need distribute only one
  31. link-state message throughout the link-state domain when a link on any
  32. single given router changes state, in order for all routers to
  33. reconverge on the best paths through the network. In contrast, distance
  34. vector protocols can require a progression of different path update
  35. messages from a series of different routers in order to converge.
  36. @cindex Link-state routing protocol disadvantages
  37. The disadvantage to a link-state protocol is that the process of
  38. computing the best paths can be relatively intensive when compared to
  39. distance-vector protocols, in which near to no computation need be done
  40. other than (potentially) select between multiple routes. This overhead
  41. is mostly negligible for modern embedded CPUs, even for networks with
  42. thousands of nodes. The primary scaling overhead lies more in coping
  43. with the ever greater frequency of LSA updates as the size of a
  44. link-state area increases, in managing the @acronym{LSDB} and required
  45. flooding.
  46. This section aims to give a distilled, but accurate, description of the
  47. more important workings of @acronym{OSPF}@ which an administrator may need
  48. to know to be able best configure and trouble-shoot @acronym{OSPF}@.
  49. @subsection OSPF Mechanisms
  50. @acronym{OSPF} defines a range of mechanisms, concerned with detecting,
  51. describing and propogating state through a network. These mechanisms
  52. will nearly all be covered in greater detail further on. They may be
  53. broadly classed as:
  54. @table @dfn
  55. @cindex OSPF Hello Protocol overview
  56. @item The Hello Protocol
  57. @cindex OSPF Hello Protocol
  58. The OSPF Hello protocol allows OSPF to quickly detect changes in
  59. two-way reachability between routers on a link. OSPF can additionally
  60. avail of other sources of reachability information, such as link-state
  61. information provided by hardware, or through dedicated reachability
  62. protocols such as @acronym{BFD,Bi-directional Forwarding Detection}.
  63. OSPF also uses the Hello protocol to propagate certain state between
  64. routers sharing a link, for example:
  65. @itemize @bullet
  66. @item Hello protocol configured state, such as the dead-interval.
  67. @item Router priority, for DR/BDR election.
  68. @item DR/BDR election results.
  69. @item Any optional capabilities supported by each router.
  70. @end itemize
  71. The Hello protocol is comparatively trivial and will not be explored in
  72. greater detail than here.
  73. @cindex OSPF LSA overview
  74. @item LSAs
  75. At the heart of @acronym{OSPF} are @acronym{LSA,Link State
  76. Advertisement} messages. Despite the name, some @acronym{LSA}s do not,
  77. strictly speaking, describe link-state information. Common
  78. @acronym{LSA}s describe information such as:
  79. @itemize @bullet
  80. @item
  81. Routers, in terms of their links.
  82. @item
  83. Networks, in terms of attached routers.
  84. @item
  85. Routes, external to a link-state domain:
  86. @itemize @bullet
  87. @item External Routes
  88. Routes entirely external to @acronym{OSPF}@. Routers originating such
  89. routes are known as @acronym{ASBR,Autonomous-System Border Router}
  90. routers.
  91. @item Summary Routes
  92. Routes which summarise routing information relating to OSPF areas
  93. external to the OSPF link-state area at hand, originated by
  94. @acronym{ABR,Area Boundary Router} routers.
  95. @end itemize
  96. @end itemize
  97. @item LSA Flooding
  98. OSPF defines several related mechanisms, used to manage synchronisation of
  99. @acronym{LSDB}s between neighbours as neighbours form adjacencies and
  100. the propogation, or @dfn{flooding} of new or updated @acronym{LSA}s.
  101. @xref{OSPF Flooding}.
  102. @cindex OSPF Areas overview
  103. @item Areas
  104. OSPF provides for the protocol to be broken up into multiple smaller
  105. and independent link-state areas. Each area must be connected to a
  106. common backbone area by an @acronym{ABR,Area Boundary Router}. These
  107. @acronym{ABR} routers are responsible for summarising the link-state
  108. routing information of an area into @dfn{Summary LSAs}, possibly in a
  109. condensed (i.e. aggregated) form, and then originating these summaries
  110. into all other areas the @acronym{ABR} is connected to.
  111. Note that only summaries and external routes are passed between areas.
  112. As these describe @emph{paths}, rather than any router link-states,
  113. routing between areas hence is by @dfn{distance-vector}, @strong{not}
  114. link-state.
  115. @xref{OSPF Areas}.
  116. @end table
  117. @subsection OSPF LSAs
  118. @acronym{LSA}s are the core object in OSPF@. Everything else in OSPF
  119. revolves around detecting what to describe in LSAs, when to update
  120. them, how to flood them throughout a network and how to calculate
  121. routes from them.
  122. There are a variety of different @acronym{LSA}s, for purposes such
  123. as describing actual link-state information, describing paths (i.e.
  124. routes), describing bandwidth usage of links for
  125. @acronym{TE,Traffic Engineering} purposes, and even arbitrary data
  126. by way of @emph{Opaque} @acronym{LSA}s.
  127. @subsubsection LSA Header
  128. All LSAs share a common header with the following information:
  129. @itemize @bullet
  130. @item Type
  131. Different types of @acronym{LSA}s describe different things in
  132. @acronym{OSPF}@. Types include:
  133. @itemize @bullet
  134. @item Router LSA
  135. @item Network LSA
  136. @item Network Summary LSA
  137. @item Router Summary LSA
  138. @item AS-External LSA
  139. @end itemize
  140. The specifics of the different types of LSA are examined below.
  141. @item Advertising Router
  142. The Router ID of the router originating the LSA, see @ref{ospf router-id}.
  143. @item LSA ID
  144. The ID of the LSA, which is typically derived in some way from the
  145. information the LSA describes, e.g. a Router LSA uses the Router ID as
  146. the LSA ID, a Network LSA will have the IP address of the @acronym{DR}
  147. as its LSA ID@.
  148. The combination of the Type, ID and Advertising Router ID must uniquely
  149. identify the @acronym{LSA}@. There can however be multiple instances of
  150. an LSA with the same Type, LSA ID and Advertising Router ID, see
  151. @ref{OSPF LSA sequence number,,LSA Sequence Number}.
  152. @item Age
  153. A number to allow stale @acronym{LSA}s to, eventually, be purged by routers
  154. from their @acronym{LSDB}s.
  155. The value nominally is one of seconds. An age of 3600, i.e. 1 hour, is
  156. called the @dfn{MaxAge}. MaxAge LSAs are ignored in routing
  157. calculations. LSAs must be periodically refreshed by their Advertising
  158. Router before reaching MaxAge if they are to remain valid.
  159. Routers may deliberately flood LSAs with the age artificially set to
  160. 3600 to indicate an LSA is no longer valid. This is called
  161. @dfn{flushing} of an LSA@.
  162. It is not abnormal to see stale LSAs in the LSDB, this can occur where
  163. a router has shutdown without flushing its LSA(s), e.g. where it has
  164. become disconnected from the network. Such LSAs do little harm.
  165. @anchor{OSPF LSA sequence number}
  166. @item Sequence Number
  167. A number used to distinguish newer instances of an LSA from older instances.
  168. @end itemize
  169. @subsubsection Link-State LSAs
  170. Of all the various kinds of @acronym{LSA}s, just two types comprise the
  171. actual link-state part of @acronym{OSPF}, Router @acronym{LSA}s and
  172. Network @acronym{LSA}s. These LSA types are absolutely core to the
  173. protocol.
  174. Instances of these LSAs are specific to the link-state area in which
  175. they are originated. Routes calculated from these two LSA types are
  176. called @dfn{intra-area routes}.
  177. @itemize @bullet
  178. @item Router LSA
  179. Each OSPF Router must originate a router @acronym{LSA} to describe
  180. itself. In it, the router lists each of its @acronym{OSPF} enabled
  181. interfaces, for the given link-state area, in terms of:
  182. @itemize @bullet
  183. @item Cost
  184. The output cost of that interface, scaled inversely to some commonly known
  185. reference value, @xref{OSPF auto-cost reference-bandwidth,,auto-cost
  186. reference-bandwidth}.
  187. @item Link Type
  188. @itemize @bullet
  189. @item Transit Network
  190. A link to a multi-access network, on which the router has at least one
  191. Full adjacency with another router.
  192. @item @acronym{PtP,Point-to-Point}
  193. A link to a single remote router, with a Full adjacency. No
  194. @acronym{DR, Designated Router} is elected on such links; no network
  195. LSA is originated for such a link.
  196. @item Stub
  197. A link with no adjacent neighbours, or a host route.
  198. @end itemize
  199. @item Link ID and Data
  200. These values depend on the Link Type:
  201. @multitable @columnfractions .18 .32 .32
  202. @headitem Link Type @tab Link ID @tab Link Data
  203. @item Transit
  204. @tab Link IP address of the @acronym{DR}
  205. @tab Interface IP address
  206. @item Point-to-Point
  207. @tab Router ID of the remote router
  208. @tab Local interface IP address,
  209. or the @acronym{ifindex,MIB-II interface index}
  210. for unnumbered links
  211. @item Stub
  212. @tab IP address
  213. @tab Subnet Mask
  214. @end multitable
  215. @end itemize
  216. Links on a router may be listed multiple times in the Router LSA, e.g.
  217. a @acronym{PtP} interface on which OSPF is enabled must @emph{always}
  218. be described by a Stub link in the Router @acronym{LSA}, in addition to
  219. being listed as PtP link in the Router @acronym{LSA} if the adjacency
  220. with the remote router is Full.
  221. Stub links may also be used as a way to describe links on which OSPF is
  222. @emph{not} spoken, known as @dfn{passive interfaces}, see @ref{OSPF
  223. passive-interface,,passive-interface}.
  224. @item Network LSA
  225. On multi-access links (e.g. ethernets, certain kinds of ATM and X@.25
  226. configurations), routers elect a @acronym{DR}@. The @acronym{DR} is
  227. responsible for originating a Network @acronym{LSA}, which helps reduce
  228. the information needed to describe multi-access networks with multiple
  229. routers attached. The @acronym{DR} also acts as a hub for the flooding of
  230. @acronym{LSA}s on that link, thus reducing flooding overheads.
  231. The contents of the Network LSA describes the:
  232. @itemize @bullet
  233. @item Subnet Mask
  234. As the @acronym{LSA} ID of a Network LSA must be the IP address of the
  235. @acronym{DR}, the Subnet Mask together with the @acronym{LSA} ID gives
  236. you the network address.
  237. @item Attached Routers
  238. Each router fully-adjacent with the @acronym{DR} is listed in the LSA,
  239. by their Router-ID. This allows the corresponding Router @acronym{LSA}s to be
  240. easily retrieved from the @acronym{LSDB}@.
  241. @end itemize
  242. @end itemize
  243. Summary of Link State LSAs:
  244. @multitable @columnfractions .18 .32 .40
  245. @headitem LSA Type @tab LSA ID Describes @tab LSA Data Describes
  246. @item Router LSA
  247. @tab The Router ID
  248. @tab The @acronym{OSPF} enabled links of the router, within
  249. a specific link-state area.
  250. @item Network LSA
  251. @tab The IP address of the @acronym{DR} for the network
  252. @tab The Subnet Mask of the network, and the Router IDs of all routers
  253. on the network.
  254. @end multitable
  255. With an LSDB composed of just these two types of @acronym{LSA}, it is
  256. possible to construct a directed graph of the connectivity between all
  257. routers and networks in a given OSPF link-state area. So, not
  258. surprisingly, when OSPF routers build updated routing tables, the first
  259. stage of @acronym{SPF} calculation concerns itself only with these two
  260. LSA types.
  261. @subsubsection Link-State LSA Examples
  262. The example below (@pxref{OSPF Link-State LSA Example}) shows two
  263. @acronym{LSA}s, both originated by the same router (Router ID
  264. and with the same @acronym{LSA} ID (, but of
  265. different LSA types.
  266. The first LSA being the router LSA describing's links: 2 links
  267. to multi-access networks with fully-adjacent neighbours (i.e. Transit
  268. links) and 1 being a Stub link (no adjacent neighbours).
  269. The second LSA being a Network LSA, for which is the
  270. @acronym{DR}, listing the Router IDs of 4 routers on that network which
  271. are fully adjacent with
  272. @anchor{OSPF Link-State LSA Example}
  273. @example
  274. # show ip ospf database router
  275. OSPF Router with ID (
  276. Router Link States (Area
  277. LS age: 38
  278. Options: 0x2 : *|-|-|-|-|-|E|*
  279. LS Flags: 0x6
  280. Flags: 0x2 : ASBR
  281. LS Type: router-LSA
  282. Link State ID:
  283. Advertising Router:
  284. LS Seq Number: 80000f90
  285. Checksum: 0x518b
  286. Length: 60
  287. Number of Links: 3
  288. Link connected to: a Transit Network
  289. (Link ID) Designated Router address:
  290. (Link Data) Router Interface address:
  291. Number of TOS metrics: 0
  292. TOS 0 Metric: 10
  293. Link connected to: a Transit Network
  294. (Link ID) Designated Router address:
  295. (Link Data) Router Interface address:
  296. Number of TOS metrics: 0
  297. TOS 0 Metric: 10
  298. Link connected to: Stub Network
  299. (Link ID) Net:
  300. (Link Data) Network Mask:
  301. Number of TOS metrics: 0
  302. TOS 0 Metric: 39063
  303. # show ip ospf database network
  304. OSPF Router with ID (
  305. Net Link States (Area
  306. LS age: 285
  307. Options: 0x2 : *|-|-|-|-|-|E|*
  308. LS Flags: 0x6
  309. LS Type: network-LSA
  310. Link State ID: (address of Designated Router)
  311. Advertising Router:
  312. LS Seq Number: 80000074
  313. Checksum: 0x0103
  314. Length: 40
  315. Network Mask: /29
  316. Attached Router:
  317. Attached Router:
  318. Attached Router:
  319. Attached Router:
  320. @end example
  321. Note that from one LSA, you can find the other. E.g. Given the
  322. Network-LSA you have a list of Router IDs on that network, from which
  323. you can then look up, in the local @acronym{LSDB}, the matching Router
  324. LSA@. From that Router-LSA you may (potentially) find links to other
  325. Transit networks and Routers IDs which can be used to lookup the
  326. corresponding Router or Network LSA@. And in that fashion, one can find
  327. all the Routers and Networks reachable from that starting @acronym{LSA}@.
  328. Given the Router LSA instead, you have the IP address of the
  329. @acronym{DR} of any attached transit links. Network LSAs will have that IP
  330. as their LSA ID, so you can then look up that Network LSA and from that
  331. find all the attached routers on that link, leading potentially to more
  332. links and Network and Router LSAs, etc. etc.
  333. From just the above two @acronym{LSA}s, one can already see the
  334. following partial topology:
  335. @example
  336. @group
  337. --------------------- Network: ......
  338. | Designated Router IP:
  339. |
  340. IP:
  341. (transit link)
  342. (cost: 10)
  343. Router ID: IP:
  344. (cost: 10) (cost: 39063)
  345. (transit link)
  346. IP:
  347. |
  348. |
  349. ------------------------------ Network:
  350. | | | Designated Router IP:
  351. | | |
  352. | | Router ID:
  353. | |
  354. | Router ID:
  355. |
  356. Router ID:
  357. @end group
  358. @end example
  359. Note the Router IDs, though they look like IP addresses and often are
  360. IP addresses, are not strictly speaking IP addresses, nor need they be
  361. reachable addresses (though, OSPF will calculate routes to Router IDs).
  362. @subsubsection External LSAs
  363. External, or "Type 5", @acronym{LSA}s describe routing information which is
  364. entirely external to @acronym{OSPF}, and is "injected" into
  365. @acronym{OSPF}@. Such routing information may have come from another
  366. routing protocol, such as RIP or BGP, they may represent static routes
  367. or they may represent a default route.
  368. An @acronym{OSPF} router which originates External @acronym{LSA}s is known as an
  369. @acronym{ASBR,AS Boundary Router}. Unlike the link-state @acronym{LSA}s, and
  370. most other @acronym{LSA}s, which are flooded only within the area in
  371. which they originate, External @acronym{LSA}s are flooded through-out
  372. the @acronym{OSPF} network to all areas capable of carrying External
  373. @acronym{LSA}s (@pxref{OSPF Areas}).
  374. Routes internal to OSPF (intra-area or inter-area) are always preferred
  375. over external routes.
  376. The External @acronym{LSA} describes the following:
  377. @itemize @bullet
  378. @item IP Network number
  379. The IP Network number of the route is described by the @acronym{LSA} ID
  380. field.
  381. @item IP Network Mask
  382. The body of the External LSA describes the IP Network Mask of the
  383. route. This, together with the @acronym{LSA} ID, describes the prefix
  384. of the IP route concerned.
  385. @item Metric
  386. The cost of the External Route. This cost may be an OSPF cost (also
  387. known as a "Type 1" metric), i.e. equivalent to the normal OSPF costs,
  388. or an externally derived cost ("Type 2" metric) which is not comparable
  389. to OSPF costs and always considered larger than any OSPF cost. Where
  390. there are both Type 1 and 2 External routes for a route, the Type 1 is
  391. always preferred.
  392. @item Forwarding Address
  393. The address of the router to forward packets to for the route. This may
  394. be, and usually is, left as 0 to specify that the ASBR originating the
  395. External @acronym{LSA} should be used. There must be an internal OSPF
  396. route to the forwarding address, for the forwarding address to be
  397. useable.
  398. @item Tag
  399. An arbitrary 4-bytes of data, not interpreted by OSPF, which may
  400. carry whatever information about the route which OSPF speakers desire.
  401. @end itemize
  402. @subsubsection AS External LSA Example
  403. To illustrate, below is an example of an External @acronym{LSA} in the
  404. @acronym{LSDB} of an OSPF router. It describes a route to the IP prefix
  405. of, originated by the ASBR with Router-ID
  406. The metric of 20 is external to OSPF. The forwarding
  407. address is 0, so the route should forward to the originating ASBR if
  408. selected.
  409. @example
  410. @group
  411. # show ip ospf database external
  412. LS age: 995
  413. Options: 0x2 : *|-|-|-|-|-|E|*
  414. LS Flags: 0x9
  415. LS Type: AS-external-LSA
  416. Link State ID: (External Network Number)
  417. Advertising Router:
  418. LS Seq Number: 800001d8
  419. Checksum: 0xea27
  420. Length: 36
  421. Network Mask: /24
  422. Metric Type: 2 (Larger than any link state path)
  423. TOS: 0
  424. Metric: 20
  425. Forward Address:
  426. External Route Tag: 0
  427. @end group
  428. @end example
  429. We can add this to our partial topology from above, which now looks
  430. like:
  431. @example
  432. @group
  433. --------------------- Network: ......
  434. | Designated Router IP:
  435. |
  436. IP: /---- External route:
  437. (transit link) / Cost: 20 (External metric)
  438. (cost: 10) /
  439. Router ID: IP:
  440. (cost: 10) (cost: 39063)
  441. (transit link)
  442. IP:
  443. |
  444. |
  445. ------------------------------ Network:
  446. | | | Designated Router IP:
  447. | | |
  448. | | Router ID:
  449. | |
  450. | Router ID:
  451. |
  452. Router ID:
  453. @end group
  454. @end example
  455. @subsubsection Summary LSAs
  456. Summary LSAs are created by @acronym{ABR}s to summarise the destinations available within one area to other areas. These LSAs may describe IP networks, potentially in aggregated form, or @acronym{ASBR} routers.
  457. @anchor{OSPF Flooding}
  458. @subsection OSPF Flooding
  459. @anchor{OSPF Areas}
  460. @subsection OSPF Areas