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