code.delx.au - gnu-emacs/blob - test/etags/ps-src/rfc1245.ps

   1 %!
   2 %%BoundingBox: (atend)
   3 %%Pages: (atend)
   4 %%DocumentFonts: (atend)
   5 %%EndComments
   6 %
   7 % FrameMaker PostScript Prolog 2.0, for use with FrameMaker 2.0
   8 % Copyright (c) 1986,87,89 by Frame Technology, Inc.  All rights reserved.
   9 %
  10 % Known Problems:
  11 %       Due to bugs in Transcript, the 'PS-Adobe-' is omitted from line 1
  12 /FMversion (2.0) def
  13 % Set up Color vs. Black-and-White
  14         /FMPrintInColor systemdict /colorimage known def
  15 % Uncomment this line to force b&w on color printer
  16 %   /FMPrintInColor false def
  17 /FrameDict 190 dict def
  18 systemdict /errordict known not {/errordict 10 dict def
  19                 errordict /rangecheck {stop} put} if
  20 % The readline in 23.0 doesn't recognize cr's as nl's on AppleTalk
  21 FrameDict /tmprangecheck errordict /rangecheck get put
  22 errordict /rangecheck {FrameDict /bug true put} put
  23 FrameDict /bug false put
  24 mark
  25 % Some PS machines read past the CR, so keep the following 3 lines together!
  26 currentfile 5 string readline
  27 00
  28 0000000000
  29 cleartomark
  30 errordict /rangecheck FrameDict /tmprangecheck get put
  31 FrameDict /bug get {
  32         /readline {
  33                 /gstring exch def
  34                 /gfile exch def
  35                 /gindex 0 def
  36                 {
  37                         gfile read pop
  38                         dup 10 eq {exit} if
  39                         dup 13 eq {exit} if
  40                         gstring exch gindex exch put
  41                         /gindex gindex 1 add def
  42                 } loop
  43                 pop
  44                 gstring 0 gindex getinterval true
  45                 } def
  46         } if
  47 /FMVERSION {
  48         FMversion ne {
  49                 /Times-Roman findfont 18 scalefont setfont
  50                 100 100 moveto
  51                 (FrameMaker version does not match postscript_prolog!)
  52                 dup =
  53                 show showpage
  54                 } if
  55         } def
  56 /FMLOCAL {
  57         FrameDict begin
  58         0 def
  59         end
  60         } def
  61         /gstring FMLOCAL
  62         /gfile FMLOCAL
  63         /gindex FMLOCAL
  64         /orgxfer FMLOCAL
  65         /orgproc FMLOCAL
  66         /organgle FMLOCAL
  67         /orgfreq FMLOCAL
  68         /yscale FMLOCAL
  69         /xscale FMLOCAL
  70         /manualfeed FMLOCAL
  71         /paperheight FMLOCAL
  72         /paperwidth FMLOCAL
  73 /FMDOCUMENT {
  74         array /FMfonts exch def
  75         /#copies exch def
  76         FrameDict begin
  77         0 ne dup {setmanualfeed} if
  78         /manualfeed exch def
  79         /paperheight exch def
  80         /paperwidth exch def
  81         setpapername
  82         manualfeed {true} {papersize} ifelse
  83         {manualpapersize} {false} ifelse
  84         {desperatepapersize} if
  85         /yscale exch def
  86         /xscale exch def
  87         currenttransfer cvlit /orgxfer exch def
  88         currentscreen cvlit /orgproc exch def
  89         /organgle exch def /orgfreq exch def
  90         end
  91         } def
  92         /pagesave FMLOCAL
  93         /orgmatrix FMLOCAL
  94         /landscape FMLOCAL
  95 /FMBEGINPAGE {
  96         FrameDict begin
  97         /pagesave save def
  98         3.86 setmiterlimit
  99         /landscape exch 0 ne def
 100         landscape {
 101                 90 rotate 0 exch neg translate pop
 102                 }
 103                 {pop pop}
 104                 ifelse
 105         xscale yscale scale
 106         /orgmatrix matrix def
 107         gsave
 108         } def
 109 /FMENDPAGE {
 110         grestore
 111         pagesave restore
 112         end
 113         showpage
 114         } def
 115 /FMDEFINEFONT {
 116         FrameDict begin
 117         findfont
 118         ReEncode
 119         2 index exch
 120         definefont exch
 121         scalefont
 122         FMfonts 3 1 roll
 123         put
 124         end
 125         } bind def
 126 /FMNORMALIZEGRAPHICS {
 127         newpath
 128         0.0 0.0 moveto
 129         1 setlinewidth
 130         0 setlinecap
 131         0 0 0 sethsbcolor
 132         0 setgray
 133         } bind def
 134         /fx FMLOCAL
 135         /fy FMLOCAL
 136         /fh FMLOCAL
 137         /fw FMLOCAL
 138         /llx FMLOCAL
 139         /lly FMLOCAL
 140         /urx FMLOCAL
 141         /ury FMLOCAL
 142 /FMBEGINEPSF {
 143         end
 144         /FMEPSF save def
 145         /showpage {} def
 146         FMNORMALIZEGRAPHICS
 147         [/fy /fx /fh /fw /ury /urx /lly /llx] {exch def} forall
 148         fx fy translate
 149         rotate
 150         fw urx llx sub div fh ury lly sub div scale
 151         llx neg lly neg translate
 152         } bind def
 153 /FMENDEPSF {
 154         FMEPSF restore
 155         FrameDict begin
 156         } bind def
 157 FrameDict begin
 158 /setmanualfeed {
 159 %%BeginFeature *ManualFeed True
 160          statusdict /manualfeed true put
 161 %%EndFeature
 162         } def
 163 /max {2 copy lt {exch} if pop} bind def
 164 /min {2 copy gt {exch} if pop} bind def
 165 /inch {72 mul} def
 166 /pagedimen {
 167         paperheight sub abs 16 lt exch
 168         paperwidth sub abs 16 lt and
 169         {/papername exch def} {pop} ifelse
 170         } def
 171         /papersizedict FMLOCAL
 172 /setpapername {
 173         /papersizedict 14 dict def
 174         papersizedict begin
 175         /papername /unknown def
 176                 /Letter 8.5 inch 11.0 inch pagedimen
 177                 /LetterSmall 7.68 inch 10.16 inch pagedimen
 178                 /Tabloid 11.0 inch 17.0 inch pagedimen
 179                 /Ledger 17.0 inch 11.0 inch pagedimen
 180                 /Legal 8.5 inch 14.0 inch pagedimen
 181                 /Statement 5.5 inch 8.5 inch pagedimen
 182                 /Executive 7.5 inch 10.0 inch pagedimen
 183                 /A3 11.69 inch 16.5 inch pagedimen
 184                 /A4 8.26 inch 11.69 inch pagedimen
 185                 /A4Small 7.47 inch 10.85 inch pagedimen
 186                 /B4 10.125 inch 14.33 inch pagedimen
 187                 /B5 7.16 inch 10.125 inch pagedimen
 188         end
 189         } def
 190 /papersize {
 191         papersizedict begin
 192                 /Letter {lettertray} def
 193                 /LetterSmall {lettertray lettersmall} def
 194                 /Tabloid {11x17tray} def
 195                 /Ledger {ledgertray} def
 196                 /Legal {legaltray} def
 197                 /Statement {statementtray} def
 198                 /Executive {executivetray} def
 199                 /A3 {a3tray} def
 200                 /A4 {a4tray} def
 201                 /A4Small {a4tray a4small} def
 202                 /B4 {b4tray} def
 203                 /B5 {b5tray} def
 204                 /unknown {unknown} def
 205         papersizedict dup papername known {papername} {/unknown} ifelse get
 206         end
 207         /FMdicttop countdictstack 1 add def
 208         statusdict begin stopped end
 209         countdictstack -1 FMdicttop {pop end} for
 210         } def
 211 /manualpapersize {
 212         papersizedict begin
 213                 /Letter {letter} def
 214                 /LetterSmall {lettersmall} def
 215                 /Tabloid {11x17} def
 216                 /Ledger {ledger} def
 217                 /Legal {legal} def
 218                 /Statement {statement} def
 219                 /Executive {executive} def
 220                 /A3 {a3} def
 221                 /A4 {a4} def
 222                 /A4Small {a4small} def
 223                 /B4 {b4} def
 224                 /B5 {b5} def
 225                 /unknown {unknown} def
 226         papersizedict dup papername known {papername} {/unknown} ifelse get
 227         end
 228         stopped
 229         } def
 230 /desperatepapersize {
 231         statusdict /setpageparams known
 232                 {
 233                 paperwidth paperheight 0 1
 234                 statusdict begin
 235                 {setpageparams} stopped pop
 236                 end
 237                 } if
 238         } def
 239 /savematrix {
 240         orgmatrix currentmatrix pop
 241         } bind def
 242 /restorematrix {
 243         orgmatrix setmatrix
 244         } bind def
 245 /dmatrix matrix def
 246 /dpi    72 0 dmatrix defaultmatrix dtransform
 247     dup mul exch   dup mul add   sqrt def
 248 /freq dpi 18.75 div 8 div round dup 0 eq {pop 1} if 8 mul dpi exch div def
 249 /sangle 1 0 dmatrix defaultmatrix dtransform exch atan def
 250 /DiacriticEncoding [
 251 /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
 252 /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
 253 /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
 254 /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
 255 /.notdef /.notdef /.notdef /.notdef /space /exclam /quotedbl
 256 /numbersign /dollar /percent /ampersand /quotesingle /parenleft
 257 /parenright /asterisk /plus /comma /hyphen /period /slash /zero /one
 258 /two /three /four /five /six /seven /eight /nine /colon /semicolon
 259 /less /equal /greater /question /at /A /B /C /D /E /F /G /H /I /J /K
 260 /L /M /N /O /P /Q /R /S /T /U /V /W /X /Y /Z /bracketleft /backslash
 261 /bracketright /asciicircum /underscore /grave /a /b /c /d /e /f /g /h
 262 /i /j /k /l /m /n /o /p /q /r /s /t /u /v /w /x /y /z /braceleft /bar
 263 /braceright /asciitilde /.notdef /Adieresis /Aring /Ccedilla /Eacute
 264 /Ntilde /Odieresis /Udieresis /aacute /agrave /acircumflex /adieresis
 265 /atilde /aring /ccedilla /eacute /egrave /ecircumflex /edieresis
 266 /iacute /igrave /icircumflex /idieresis /ntilde /oacute /ograve
 267 /ocircumflex /odieresis /otilde /uacute /ugrave /ucircumflex
 268 /udieresis /dagger /.notdef /cent /sterling /section /bullet
 269 /paragraph /germandbls /registered /copyright /trademark /acute
 270 /dieresis /.notdef /AE /Oslash /.notdef /.notdef /.notdef /.notdef
 271 /yen /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
 272 /ordfeminine /ordmasculine /.notdef /ae /oslash /questiondown
 273 /exclamdown /logicalnot /.notdef /florin /.notdef /.notdef
 274 /guillemotleft /guillemotright /ellipsis /.notdef /Agrave /Atilde
 275 /Otilde /OE /oe /endash /emdash /quotedblleft /quotedblright
 276 /quoteleft /quoteright /.notdef /.notdef /ydieresis /Ydieresis
 277 /fraction /currency /guilsinglleft /guilsinglright /fi /fl /daggerdbl
 278 /periodcentered /quotesinglbase /quotedblbase /perthousand
 279 /Acircumflex /Ecircumflex /Aacute /Edieresis /Egrave /Iacute
 280 /Icircumflex /Idieresis /Igrave /Oacute /Ocircumflex /.notdef /Ograve
 281 /Uacute /Ucircumflex /Ugrave /dotlessi /circumflex /tilde /macron
 282 /breve /dotaccent /ring /cedilla /hungarumlaut /ogonek /caron
 283 ] def
 284 /ReEncode {
 285         dup
 286         length
 287         dict begin
 288         {
 289         1 index /FID ne
 290                 {def}
 291                 {pop pop} ifelse
 292         } forall
 293         Encoding StandardEncoding eq
 294         {
 295                 /Encoding DiacriticEncoding def
 296         }if
 297         currentdict
 298         end
 299         } bind def
 300 /graymode true def
 301         /bwidth FMLOCAL
 302         /bpside FMLOCAL
 303         /bstring FMLOCAL
 304         /onbits FMLOCAL
 305         /offbits FMLOCAL
 306         /xindex FMLOCAL
 307         /yindex FMLOCAL
 308         /x FMLOCAL
 309         /y FMLOCAL
 310 /setpattern {
 311          /bwidth  exch def
 312          /bpside  exch def
 313          /bstring exch def
 314          /onbits 0 def  /offbits 0 def
 315          freq sangle landscape {90 add} if
 316                 {/y exch def
 317                  /x exch def
 318                  /xindex x 1 add 2 div bpside mul cvi def
 319                  /yindex y 1 add 2 div bpside mul cvi def
 320                  bstring yindex bwidth mul xindex 8 idiv add get
 321                  1 7 xindex 8 mod sub bitshift and 0 ne
 322                  {/onbits  onbits  1 add def 1}
 323                  {/offbits offbits 1 add def 0}
 324                  ifelse
 325                 }
 326                 setscreen
 327          {} settransfer
 328          offbits offbits onbits add div FMsetgray
 329         /graymode false def
 330         } bind def
 331 /grayness {
 332         FMsetgray
 333         graymode not {
 334                 /graymode true def
 335                 orgxfer cvx settransfer
 336                 orgfreq organgle orgproc cvx setscreen
 337                 } if
 338         } bind def
 339         /HUE FMLOCAL
 340         /SAT FMLOCAL
 341         /BRIGHT FMLOCAL
 342         /Colors FMLOCAL
 343 FMPrintInColor
 344
 345         {
 346         /HUE 0 def
 347         /SAT 0 def
 348         /BRIGHT 0 def
 349         % array of arrays Hue and Sat values for the separations [HUE BRIGHT]
 350         /Colors
 351         [[0    0  ]    % black
 352          [0    0  ]    % white
 353          [0.00 1.0]    % red
 354          [0.37 1.0]    % green
 355          [0.60 1.0]    % blue
 356          [0.50 1.0]    % cyan
 357          [0.83 1.0]    % magenta
 358          [0.16 1.0]    % comment / yellow
 359          ] def
 360
 361         /BEGINBITMAPCOLOR {
 362                 BITMAPCOLOR} def
 363         /BEGINBITMAPCOLORc {
 364                 BITMAPCOLORc} def
 365         /K {
 366                 Colors exch get dup
 367                 0 get /HUE exch store
 368                 1 get /BRIGHT exch store
 369                   HUE 0 eq BRIGHT 0 eq and
 370                         {1.0 SAT sub setgray}
 371                         {HUE SAT BRIGHT sethsbcolor}
 372                   ifelse
 373                 } def
 374         /FMsetgray {
 375                 /SAT exch 1.0 exch sub store
 376                   HUE 0 eq BRIGHT 0 eq and
 377                         {1.0 SAT sub setgray}
 378                         {HUE SAT BRIGHT sethsbcolor}
 379                   ifelse
 380                 } bind def
 381         }
 382
 383         {
 384         /BEGINBITMAPCOLOR {
 385                 BITMAPGRAY} def
 386         /BEGINBITMAPCOLORc {
 387                 BITMAPGRAYc} def
 388         /FMsetgray {setgray} bind def
 389         /K {
 390                 pop
 391                 } def
 392         }
 393 ifelse
 394 /normalize {
 395         transform round exch round exch itransform
 396         } bind def
 397 /dnormalize {
 398         dtransform round exch round exch idtransform
 399         } bind def
 400 /lnormalize {
 401         0 dtransform exch cvi 2 idiv 2 mul 1 add exch idtransform pop
 402         } bind def
 403 /H {
 404         lnormalize setlinewidth
 405         } bind def
 406 /Z {
 407         setlinecap
 408         } bind def
 409 /X {
 410         fillprocs exch get exec
 411         } bind def
 412 /V {
 413         gsave eofill grestore
 414         } bind def
 415 /N {
 416         stroke
 417         } bind def
 418 /M {newpath moveto} bind def
 419 /E {lineto} bind def
 420 /D {curveto} bind def
 421 /O {closepath} bind def
 422         /n FMLOCAL
 423 /L {
 424         /n exch def
 425         newpath
 426         normalize
 427         moveto
 428         2 1 n {pop normalize lineto} for
 429         } bind def
 430 /Y {
 431         L
 432         closepath
 433         } bind def
 434         /x1 FMLOCAL
 435         /x2 FMLOCAL
 436         /y1 FMLOCAL
 437         /y2 FMLOCAL
 438         /rad FMLOCAL
 439 /R {
 440         /y2 exch def
 441         /x2 exch def
 442         /y1 exch def
 443         /x1 exch def
 444         x1 y1
 445         x2 y1
 446         x2 y2
 447         x1 y2
 448         4 Y
 449         } bind def
 450 /RR {
 451         /rad exch def
 452         normalize
 453         /y2 exch def
 454         /x2 exch def
 455         normalize
 456         /y1 exch def
 457         /x1 exch def
 458         newpath
 459         x1 y1 rad add moveto
 460         x1 y2 x2 y2 rad arcto
 461         x2 y2 x2 y1 rad arcto
 462         x2 y1 x1 y1 rad arcto
 463         x1 y1 x1 y2 rad arcto
 464         closepath
 465         16 {pop} repeat
 466         } bind def
 467 /C {
 468         grestore
 469         gsave
 470         R
 471         clip
 472         } bind def
 473 /U {
 474         grestore
 475         gsave
 476         } bind def
 477 /F {
 478         FMfonts exch get
 479         setfont
 480         } bind def
 481 /T {
 482         moveto show
 483         } bind def
 484 /RF {
 485         rotate
 486         0 ne {-1 1 scale} if
 487         } bind def
 488 /TF {
 489         gsave
 490         moveto
 491         RF
 492         show
 493         grestore
 494         } bind def
 495 /P {
 496         moveto
 497         0 32 3 2 roll widthshow
 498         } bind def
 499 /PF {
 500         gsave
 501         moveto
 502         RF
 503         0 32 3 2 roll widthshow
 504         grestore
 505         } bind def
 506 /S {
 507         moveto
 508         0 exch ashow
 509         } bind def
 510 /SF {
 511         gsave
 512         moveto
 513         RF
 514         0 exch ashow
 515         grestore
 516         } bind def
 517 /B {
 518         moveto
 519         0 32 4 2 roll 0 exch awidthshow
 520         } bind def
 521 /BF {
 522         gsave
 523         moveto
 524         RF
 525         0 32 4 2 roll 0 exch awidthshow
 526         grestore
 527         } bind def
 528         /x FMLOCAL
 529         /y FMLOCAL
 530         /dx FMLOCAL
 531         /dy FMLOCAL
 532         /dl FMLOCAL
 533         /t FMLOCAL
 534         /t2 FMLOCAL
 535         /Cos FMLOCAL
 536         /Sin FMLOCAL
 537         /r FMLOCAL
 538 /W {
 539         dnormalize
 540         /dy exch def
 541         /dx exch def
 542         normalize
 543         /y  exch def
 544         /x  exch def
 545         /dl dx dx mul dy dy mul add sqrt def
 546         dl 0.0 gt {
 547                 /t currentlinewidth def
 548                 savematrix
 549                 /Cos dx dl div def
 550                 /Sin dy dl div def
 551                 /r [Cos Sin Sin neg Cos 0.0 0.0] def
 552                 /t2 t 2.5 mul 3.5 max def
 553                 newpath
 554                 x y translate
 555                 r concat
 556                 0.0 0.0 moveto
 557                 dl t 2.7 mul sub 0.0 rlineto
 558                 stroke
 559                 restorematrix
 560                 x dx add y dy add translate
 561                 r concat
 562                 t 0.67 mul setlinewidth
 563                 t 1.61 mul neg  0.0 translate
 564                 0.0 0.0 moveto
 565                 t2 1.7 mul neg  t2 2.0 div     moveto
 566                 0.0 0.0 lineto
 567                 t2 1.7 mul neg  t2 2.0 div neg lineto
 568                 stroke
 569                 t setlinewidth
 570                 restorematrix
 571                 } if
 572         } bind def
 573 /G {
 574         gsave
 575         newpath
 576         normalize translate 0.0 0.0 moveto
 577         dnormalize scale
 578         0.0 0.0 1.0 5 3 roll arc
 579         closepath fill
 580         grestore
 581         } bind def
 582 /A {
 583         gsave
 584         savematrix
 585         newpath
 586         2 index 2 div add exch 3 index 2 div sub exch
 587         normalize 2 index 2 div sub exch 3 index 2 div add exch
 588         translate
 589         scale
 590         0.0 0.0 1.0 5 3 roll arc
 591         restorematrix
 592         stroke
 593         grestore
 594         } bind def
 595         /x FMLOCAL
 596         /y FMLOCAL
 597         /w FMLOCAL
 598         /h FMLOCAL
 599         /xx FMLOCAL
 600         /yy FMLOCAL
 601         /ww FMLOCAL
 602         /hh FMLOCAL
 603         /FMsaveobject FMLOCAL
 604         /FMoptop FMLOCAL
 605         /FMdicttop FMLOCAL
 606 /BEGINPRINTCODE {
 607         /FMdicttop countdictstack 1 add def
 608         /FMoptop count 4 sub def
 609         /FMsaveobject save def
 610         userdict begin
 611         /showpage {} def
 612         FMNORMALIZEGRAPHICS
 613         3 index neg 3 index neg translate
 614         } bind def
 615 /ENDPRINTCODE {
 616         count -1 FMoptop {pop pop} for
 617         countdictstack -1 FMdicttop {pop end} for
 618         FMsaveobject restore
 619         } bind def
 620 /gn {
 621         0
 622         {       46 mul
 623                 cf read pop
 624                 32 sub
 625                 dup 46 lt {exit} if
 626                 46 sub add
 627                 } loop
 628         add
 629         } bind def
 630         /str FMLOCAL
 631 /cfs {
 632         /str sl string def
 633         0 1 sl 1 sub {str exch val put} for
 634         str def
 635         } bind def
 636 /ic [
 637         0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0223
 638         0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0223
 639         0
 640         {0 hx} {1 hx} {2 hx} {3 hx} {4 hx} {5 hx} {6 hx} {7 hx} {8 hx} {9 hx}
 641         {10 hx} {11 hx} {12 hx} {13 hx} {14 hx} {15 hx} {16 hx} {17 hx} {18 hx}
 642         {19 hx} {gn hx} {0} {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12}
 643         {13} {14} {15} {16} {17} {18} {19} {gn} {0 wh} {1 wh} {2 wh} {3 wh}
 644         {4 wh} {5 wh} {6 wh} {7 wh} {8 wh} {9 wh} {10 wh} {11 wh} {12 wh}
 645         {13 wh} {14 wh} {gn wh} {0 bl} {1 bl} {2 bl} {3 bl} {4 bl} {5 bl} {6 bl}
 646         {7 bl} {8 bl} {9 bl} {10 bl} {11 bl} {12 bl} {13 bl} {14 bl} {gn bl}
 647         {0 fl} {1 fl} {2 fl} {3 fl} {4 fl} {5 fl} {6 fl} {7 fl} {8 fl} {9 fl}
 648         {10 fl} {11 fl} {12 fl} {13 fl} {14 fl} {gn fl}
 649         ] def
 650         /sl FMLOCAL
 651         /val FMLOCAL
 652         /ws FMLOCAL
 653         /im FMLOCAL
 654         /bs FMLOCAL
 655         /cs FMLOCAL
 656         /len FMLOCAL
 657         /pos FMLOCAL
 658 /ms {
 659         /sl exch def
 660         /val 255 def
 661         /ws cfs
 662         /im cfs
 663         /val 0 def
 664         /bs cfs
 665         /cs cfs
 666         } bind def
 667 400 ms
 668 /ip {
 669         is
 670         0
 671         cf cs readline pop
 672         {       ic exch get exec
 673                 add
 674                 } forall
 675         pop
 676
 677         } bind def
 678 /wh {
 679         /len exch def
 680         /pos exch def
 681         ws 0 len getinterval im pos len getinterval copy pop
 682         pos len
 683         } bind def
 684 /bl {
 685         /len exch def
 686         /pos exch def
 687         bs 0 len getinterval im pos len getinterval copy pop
 688         pos len
 689         } bind def
 690 /s1 1 string def
 691 /fl {
 692         /len exch def
 693         /pos exch def
 694         /val cf s1 readhexstring pop 0 get def
 695         pos 1 pos len add 1 sub {im exch val put} for
 696         pos len
 697         } bind def
 698 /hx {
 699         3 copy getinterval
 700         cf exch readhexstring pop pop
 701         } bind def
 702         /h FMLOCAL
 703         /w FMLOCAL
 704         /d FMLOCAL
 705         /lb FMLOCAL
 706         /bitmapsave FMLOCAL
 707         /is FMLOCAL
 708         /cf FMLOCAL
 709 /wbytes {
 710         dup
 711         8 eq {pop} {1 eq {7 add 8 idiv} {3 add 4 idiv} ifelse} ifelse
 712         } bind def
 713 /BEGINBITMAPBWc {
 714         1 {} COMMONBITMAPc
 715         } bind def
 716 /BEGINBITMAPGRAYc {
 717         8 {} COMMONBITMAPc
 718         } bind def
 719 /BEGINBITMAP2BITc {
 720         2 {} COMMONBITMAPc
 721         } bind def
 722 /COMMONBITMAPc {
 723         /r exch def
 724         /d exch def
 725         gsave
 726         translate rotate scale /h exch def /w exch def
 727         /lb w d wbytes def
 728         sl lb lt {lb ms} if
 729         /bitmapsave save def
 730         r
 731         /is im 0 lb getinterval def
 732         ws 0 lb getinterval is copy pop
 733         /cf currentfile def
 734         w h d [w 0 0 h neg 0 h]
 735         {ip} image
 736         bitmapsave restore
 737         grestore
 738         } bind def
 739 /BEGINBITMAPBW {
 740         1 {} COMMONBITMAP
 741         } bind def
 742 /BEGINBITMAPGRAY {
 743         8 {} COMMONBITMAP
 744         } bind def
 745 /BEGINBITMAP2BIT {
 746         2 {} COMMONBITMAP
 747         } bind def
 748 /COMMONBITMAP {
 749         /r exch def
 750         /d exch def
 751         gsave
 752         translate rotate scale /h exch def /w exch def
 753         /bitmapsave save def
 754         r
 755         /is w d wbytes string def
 756         /cf currentfile def
 757         w h d [w 0 0 h neg 0 h]
 758         {cf is readhexstring pop} image
 759         bitmapsave restore
 760         grestore
 761         } bind def
 762         /proc1 FMLOCAL
 763         /proc2 FMLOCAL
 764         /newproc FMLOCAL
 765 /Fmcc {
 766     /proc2 exch cvlit def
 767     /proc1 exch cvlit def
 768     /newproc proc1 length proc2 length add array def
 769     newproc 0 proc1 putinterval
 770     newproc proc1 length proc2 putinterval
 771     newproc cvx
 772 } bind def
 773 /ngrayt 256 array def
 774 /nredt 256 array def
 775 /nbluet 256 array def
 776 /ngreent 256 array def
 777         /gryt FMLOCAL
 778         /blut FMLOCAL
 779         /grnt FMLOCAL
 780         /redt FMLOCAL
 781         /indx FMLOCAL
 782         /cynu FMLOCAL
 783         /magu FMLOCAL
 784         /yelu FMLOCAL
 785         /k FMLOCAL
 786         /u FMLOCAL
 787 /colorsetup {
 788         currentcolortransfer
 789         /gryt exch def
 790         /blut exch def
 791         /grnt exch def
 792         /redt exch def
 793         0 1 255 {
 794                 /indx exch def
 795                 /cynu 1 red indx get 255 div sub def
 796                 /magu 1 green indx get 255 div sub def
 797                 /yelu 1 blue indx get 255 div sub def
 798                 /k cynu magu min yelu min def
 799                 /u k currentundercolorremoval exec def
 800                 nredt indx 1 0 cynu u sub max sub redt exec put
 801                 ngreent indx 1 0 magu u sub max sub grnt exec put
 802                 nbluet indx 1 0 yelu u sub max sub blut exec put
 803                 ngrayt indx 1 k currentblackgeneration exec sub gryt exec put
 804         } for
 805         {255 mul cvi nredt exch get}
 806         {255 mul cvi ngreent exch get}
 807         {255 mul cvi nbluet exch get}
 808         {255 mul cvi ngrayt exch get}
 809         setcolortransfer
 810         {pop 0} setundercolorremoval
 811         {} setblackgeneration
 812         } bind def
 813         /tran FMLOCAL
 814 /fakecolorsetup {
 815         /tran 256 string def
 816         0 1 255 {/indx exch def
 817                 tran indx
 818                 red indx get 77 mul
 819                 green indx get 151 mul
 820                 blue indx get 28 mul
 821                 add add 256 idiv put} for
 822         currenttransfer
 823         {255 mul cvi tran exch get 255.0 div}
 824         exch Fmcc settransfer
 825 } bind def
 826 /BITMAPCOLOR {
 827         /d 8 def
 828         gsave
 829         translate rotate scale /h exch def /w exch def
 830         /bitmapsave save def
 831         colorsetup
 832         /is w d wbytes string def
 833         /cf currentfile def
 834         w h d [w 0 0 h neg 0 h]
 835         {cf is readhexstring pop} {is} {is} true 3 colorimage
 836         bitmapsave restore
 837         grestore
 838         } bind def
 839 /BITMAPCOLORc {
 840         /d 8 def
 841         gsave
 842         translate rotate scale /h exch def /w exch def
 843         /lb w d wbytes def
 844         sl lb lt {lb ms} if
 845         /bitmapsave save def
 846         colorsetup
 847         /is im 0 lb getinterval def
 848         ws 0 lb getinterval is copy pop
 849         /cf currentfile def
 850         w h d [w 0 0 h neg 0 h]
 851         {ip} {is} {is} true 3 colorimage
 852         bitmapsave restore
 853         grestore
 854         } bind def
 855 /BITMAPGRAY {
 856         8 {fakecolorsetup} COMMONBITMAP
 857         } bind def
 858 /BITMAPGRAYc {
 859         8 {fakecolorsetup} COMMONBITMAPc
 860         } bind def
 861 /ENDBITMAP {
 862         } bind def
 863 end
 864 %%EndProlog
 865 %%BeginSetup
 866 (2.0) FMVERSION
 867 1 1 612 792 0 1 7 FMDOCUMENT
 868 /fillprocs 32 array def
 869 fillprocs 0 { 0.000000 grayness } put
 870 fillprocs 1 { 0.100000 grayness } put
 871 fillprocs 2 { 0.300000 grayness } put
 872 fillprocs 3 { 0.500000 grayness } put
 873 fillprocs 4 { 0.700000 grayness } put
 874 fillprocs 5 { 0.900000 grayness } put
 875 fillprocs 6 { 0.970000 grayness } put
 876 fillprocs 7 { 1.000000 grayness } put
 877 fillprocs 8 {<0f87c3e1f0783c1e> 8 1 setpattern } put
 878 fillprocs 9 {<0f1e3c78f0e1c387> 8 1 setpattern } put
 879 fillprocs 10 {<cccccccccccccccc> 8 1 setpattern } put
 880 fillprocs 11 {<ffff0000ffff0000> 8 1 setpattern } put
 881 fillprocs 12 {<8142241818244281> 8 1 setpattern } put
 882 fillprocs 13 {<8040201008040201> 8 1 setpattern } put
 883 fillprocs 14 {<03060c183060c081> 8 1 setpattern } put
 884 fillprocs 15 {} put
 885 fillprocs 16 { 1.000000 grayness } put
 886 fillprocs 17 { 0.900000 grayness } put
 887 fillprocs 18 { 0.700000 grayness } put
 888 fillprocs 19 { 0.500000 grayness } put
 889 fillprocs 20 { 0.300000 grayness } put
 890 fillprocs 21 { 0.100000 grayness } put
 891 fillprocs 22 { 0.030000 grayness } put
 892 fillprocs 23 { 0.000000 grayness } put
 893 fillprocs 24 {<f0783c1e0f87c3e1> 8 1 setpattern } put
 894 fillprocs 25 {<f0e1c3870f1e3c78> 8 1 setpattern } put
 895 fillprocs 26 {<3333333333333333> 8 1 setpattern } put
 896 fillprocs 27 {<0000ffff0000ffff> 8 1 setpattern } put
 897 fillprocs 28 {<7ebddbe7e7dbbd7e> 8 1 setpattern } put
 898 fillprocs 29 {<7fbfdfeff7fbfdfe> 8 1 setpattern } put
 899 fillprocs 30 {<fcf9f3e7cf9f3f7e> 8 1 setpattern } put
 900 fillprocs 31 {} put
 901 %%EndSetup
 902 0 12 /Times-Roman FMDEFINEFONT
 903 1 24 /Times-Roman FMDEFINEFONT
 904 2 16 /Times-Bold FMDEFINEFONT
 905 %%Page: "1" 1
 906 %%BeginPaperSize: Letter
 907 %%EndPaperSize
 908 612 792 0 FMBEGINPAGE
 909 72 675 540 720 R
 910 7 X
 911 0 K
 912 V
 913 0 F
 914 0 X
 915 (Network Working Group) 72 712 T
 916 (J. Moy, Editor) 470.7 712 T
 917 (Request for Comments: 1245) 72 698 T
 918 (Proteon, Inc.) 478.38 698 T
 919 (July 1991) 493.02 684 T
 920 72 72 540 83.95 R
 921 7 X
 922 V
 923 0 X
 924 ([Moy]) 72 75.95 T
 925 ([Page 1]) 499.7 75.95 T
 926 72 117 540 603 R
 927 7 X
 928 V
 929 1 F
 930 0 X
 931 (OSPF protocol analysis) 192.72 587 T
 932 2 F
 933 (Status of this Memo) 72 514.33 T
 934 0 F
 935 -0.23 (This memo provides information for the Internet community) 72 487 P
 936 -0.23 (. It does not specify any Internet stan-) 360.42 487 P
 937 (dard. Distribution of this memo is unlimited.) 72 473 T
 938 2 F
 939 (Abstract) 72 447 T
 940 0 F
 941 -0.11 (This is the \336rst of two reports on the OSPF protocol. These reports are required by the IAB/IESG ) 72 421 P
 942 (in order for an Internet routing protocol to advance to Draft Standard Status. OSPF is a TCP/IP ) 72 407 T
 943 -0.28 (routing protocol, designed to be used internal to an Autonomous System \050in other words, OSPF is ) 72 393 P
 944 (an Interior Gateway Protocol\051.) 72 379 T
 945 -0.09 (V) 72 353 P
 946 -0.09 (ersion 1 of the OSPF protocol was published in RFC 1) 79.33 353 P
 947 -0.09 (131. Since then OSPF version 2 has been ) 339.85 353 P
 948 -0.22 (developed. V) 72 339 P
 949 -0.22 (ersion 2 has been documented in RFC 1247. The changes between version 1 and ver-) 134.4 339 P
 950 -0 (sion 2 of the OSPF protocol are explained in Appendix F of RFC 1247. It is OSPF V) 72 325 P
 951 -0 (ersion 2 that ) 477.72 325 P
 952 (is the subject of this report.) 72 311 T
 953 (This report attempts to summarize the key features of OSPF V2. It also attempts to analyze how ) 72 285 T
 954 (the protocol will perform and scale in the Internet.) 72 271 T
 955 (Please send comments to ospf@trantor) 72 245 T
 956 (.umd.edu.) 258.27 245 T
 957 FMENDPAGE
 958 %%EndPage: "1" 2
 959 1 10 /Times-Roman FMDEFINEFONT
 960 %%Page: "2" 2
 961 612 792 0 FMBEGINPAGE
 962 72 702 540 720 R
 963 7 X
 964 0 K
 965 V
 966 0 F
 967 0 X
 968 (RFC 1245) 72 712 T
 969 (OSPF protocol analysis) 249.36 712 T
 970 (July 1991) 493.02 712 T
 971 72 69.05 540 81 R
 972 7 X
 973 V
 974 0 X
 975 ([Moy]) 72 73 T
 976 ([Page 2]) 499.7 73 T
 977 72 108 540 684 R
 978 7 X
 979 V
 980 2 F
 981 0 X
 982 (T) 72 673.33 T
 983 (able of Contents) 81.19 673.33 T
 984 0 F
 985 (1.0) 72 650 T
 986 (Introduction) 108 650 T
 987 (..............................................................................................................) 167.91 650 T
 988 (3) 498 650 T
 989 1 F
 990 (1.1) 108 635.33 T
 991 (Acknowledgments) 144 635.33 T
 992 (...............................................................................................................) 219.88 635.33 T
 993 (3) 499 635.33 T
 994 0 F
 995 (2.0) 72 616 T
 996 (Key features of the OSPF protocol) 108 616 T
 997 (..........................................................................) 275.85 616 T
 998 (4) 498 616 T
 999 (3.0) 72 596 T
1000 (Cost of the protocol) 108 596 T
1001 (..................................................................................................) 203.89 596 T
1002 (7) 498 596 T
1003 1 F
1004 (3.1) 108 581.33 T
1005 ( Operational data) 144 581.33 T
1006 (.................................................................................................................) 214.88 581.33 T
1007 (7) 499 581.33 T
1008 (3.2) 108 567.33 T
1009 (Link bandwidth) 144 567.33 T
1010 (...................................................................................................................) 209.88 567.33 T
1011 (9) 499 567.33 T
1012 (3.3) 108 553.33 T
1013 (Router memory) 144 553.33 T
1014 (....................................................................................................................) 207.39 553.33 T
1015 (9) 499 553.33 T
1016 (3.4) 108 539.33 T
1017 (Router CPU) 144 539.33 T
1018 (.......................................................................................................................) 194.89 539.33 T
1019 (10) 494.01 539.33 T
1020 (3.5) 108 525.33 T
1021 (Role of Designated Router) 144 525.33 T
1022 (................................................................................................) 252.36 525.33 T
1023 (1) 494.38 525.33 T
1024 (1) 499 525.33 T
1025 (3.6) 108 511.33 T
1026 (Summary) 144 511.33 T
1027 (...........................................................................................................................) 184.9 511.33 T
1028 (1) 494.38 511.33 T
1029 (1) 499 511.33 T
1030 0 F
1031 (4.0) 72 492 T
1032 (Suitable environments) 108 492 T
1033 (............................................................................................) 215.88 492 T
1034 (13) 492.01 492 T
1035 (5.0) 72 472 T
1036 (Unsuitable environments) 108 472 T
1037 (.......................................................................................) 230.87 472 T
1038 (13) 492.01 472 T
1039 (6.0) 72 452 T
1040 (Reference Documents) 108 452 T
1041 (............................................................................................) 215.88 452 T
1042 (14) 492.01 452 T
1043 FMENDPAGE
1044 %%EndPage: "2" 3
1045 3 14 /Times-Bold FMDEFINEFONT
1046 %%Page: "3" 3
1047 612 792 0 FMBEGINPAGE
1048 72 702 540 720 R
1049 7 X
1050 0 K
1051 V
1052 0 F
1053 0 X
1054 (RFC 1245) 72 712 T
1055 (OSPF protocol analysis) 249.36 712 T
1056 (July 1991) 493.02 712 T
1057 72 69.05 540 81 R
1058 7 X
1059 V
1060 0 X
1061 ([Moy]) 72 73 T
1062 ([Page 3]) 499.7 73 T
1063 72 108 540 684 R
1064 7 X
1065 V
1066 2 F
1067 0 X
1068 (1.0  Intr) 72 673.33 T
1069 (oduction) 127.23 673.33 T
1070 0 F
1071 -0.02 (This document addresses, for OSPF V2, the requirements set forth by the IAB/IESG for an Inter-) 72 646 P
1072 -0.19 (net routing protocol to advance to Draft Standard state. This requirements are brie\337y summarized ) 72 632 P
1073 (below) 72 618 T
1074 (. The remaining sections of this report document how OSPF V2 satis\336es these require-) 100.53 618 T
1075 (ments:) 72 604 T
1076 (\245) 72 584 T
1077 (What are the key features and algorithms of the protocol?) 85.54 584 T
1078 (\245) 72 564 T
1079 (How much link bandwidth, router memory and router CPU cycles does the protocol consume ) 85.54 564 T
1080 (under normal conditions?) 85.54 550 T
1081 (\245) 72 530 T
1082 (For these metrics, how does the usage scale as the routing environment grows? This should ) 85.54 530 T
1083 (include topologies at least an order of magnitude lar) 85.54 516 T
1084 (ger than the current environment.) 335.14 516 T
1085 (\245) 72 496 T
1086 (What are the limits of the protocol for these metrics? \050i.e., when will the routing protocol ) 85.54 496 T
1087 (break?\051 ) 85.54 482 T
1088 (\245) 72 462 T
1089 (For what environments is the protocol well suited, and for what is it not suitable? ) 85.54 462 T
1090 3 F
1091 (1.1  Acknowledgments) 72 428.67 T
1092 0 F
1093 -0.03 (The OSPF protocol has been developed by the OSPF W) 72 402 P
1094 -0.03 (orking Group of the Internet Engineering ) 339.64 402 P
1095 (T) 72 388 T
1096 (ask Force. ) 78.49 388 T
1097 FMENDPAGE
1098 %%EndPage: "3" 4
1099 4 12 /Times-Bold FMDEFINEFONT
1100 %%Page: "4" 4
1101 612 792 0 FMBEGINPAGE
1102 72 702 540 720 R
1103 7 X
1104 0 K
1105 V
1106 0 F
1107 0 X
1108 (RFC 1245) 72 712 T
1109 (OSPF protocol analysis) 249.36 712 T
1110 (July 1991) 493.02 712 T
1111 72 69.05 540 81 R
1112 7 X
1113 V
1114 0 X
1115 ([Moy]) 72 73 T
1116 ([Page 4]) 499.7 73 T
1117 72 108 540 684 R
1118 7 X
1119 V
1120 2 F
1121 0 X
1122 (2.0  Key featur) 72 673.33 T
1123 (es of the OSPF pr) 172.97 673.33 T
1124 (otocol) 293.49 673.33 T
1125 0 F
1126 (This section summarizes the key features of the OSPF protocol. OSPF is an) 72 646 T
1127 4 F
1128 ( Internal gateway ) 434.78 646 T
1129 -0.2 (pr) 72 632 P
1130 -0.2 (otocol) 83.78 632 P
1131 0 F
1132 -0.2 (; it is designed to be used internal to a single Autonomous System. OSPF uses) 114.42 632 P
1133 4 F
1134 -0.2 ( link-state ) 486.43 632 P
1135 -0.36 (or SPF-based) 72 618 P
1136 0 F
1137 -0.36 ( technology \050as compared to the distance-vector or Bellman-Ford technology found ) 140.6 618 P
1138 -0.48 (in routing protocols such as RIP\051. Individual ) 72 604 P
1139 4 F
1140 -0.48 (link state advertisements \050LSAs\051) 285.2 604 P
1141 0 F
1142 -0.48 ( describe pieces of ) 449.99 604 P
1143 -0.13 (the OSPF routing domain \050Autonomous System\051. These LSAs are \337ooded throughout the routing ) 72 590 P
1144 (domain, forming the ) 72 576 T
1145 4 F
1146 (link state database) 173.27 576 T
1147 0 F
1148 (. Each router has an identical link state database; syn-) 268.56 576 T
1149 (chronization of link state databases is maintained via a ) 72 562 T
1150 4 F
1151 (r) 336.81 562 T
1152 (eliable \337ooding algorithm) 341.92 562 T
1153 0 F
1154 (. From this ) 473.2 562 T
1155 (link state database, each router builds a routing table by calculating a shortest-path tree, with the ) 72 548 T
1156 (root of the tree being the calculating router itself. This calculation is commonly referred to as the ) 72 534 T
1157 4 F
1158 (Dijkstra pr) 72 520 T
1159 (ocedur) 129.41 520 T
1160 (e) 164.51 520 T
1161 0 F
1162 (.) 169.83 520 T
1163 (Link state advertisements are small. Each advertisement describes a small pieces of the OSPF ) 72 494 T
1164 (routing domain, namely either: the neighborhood of a single router) 72 480 T
1165 (, the neighborhood of a single ) 391.97 480 T
1166 (transit network, a single inter) 72 466 T
1167 (-area route \050see below\051 or a single external route.) 212 466 T
1168 (The other key features of the OSPF protocol are:) 72 440 T
1169 (\245) 72 420 T
1170 4 F
1171 -0.31 (Adjacency bringup) 85.54 420 P
1172 0 F
1173 -0.31 (. ) 183.51 420 P
1174 4 F
1175 -0.31 (Certain pairs of OSPF r) 189.2 420 P
1176 -0.31 (outers become \322adjacent\323) 311.01 420 P
1177 0 F
1178 -0.31 (. As an adjacency is ) 442.96 420 P
1179 (formed, the two routers synchronize their link state databases by ) 85.54 406 T
1180 4 F
1181 (exchanging database sum-) 397.64 406 T
1182 (maries) 85.54 392 T
1183 0 F
1184 ( in the form of OSPF Database Exchange packets. Adjacent routers then maintain syn-) 120.17 392 T
1185 (chronization of their link state databases through the ) 85.54 378 T
1186 4 F
1187 (r) 340.02 378 T
1188 (eliable \337ooding algorithm) 345.13 378 T
1189 0 F
1190 (. Routers ) 476.41 378 T
1191 -0.27 (connected by serial lines always become adjacent. On multi-access networks \050e.g., ethernets or ) 85.54 364 P
1192 (X.25 PDNs\051, all routers attached to the network become adjacent to both the Designated ) 85.54 350 T
1193 (Router and the Backup Designated router) 85.54 336 T
1194 (.) 283.73 336 T
1195 (\245) 72 316 T
1196 4 F
1197 -0.02 (Designated r) 85.54 316 P
1198 -0.02 (outer) 150.26 316 P
1199 -0.02 (.) 176.46 316 P
1200 0 F
1201 -0.02 ( A Designated Router is elected on all multi-access networks \050e.g., ether-) 179.46 316 P
1202 (nets or X.25 PDNs\051. The network\325) 85.54 302 T
1203 (s Designated Router ) 250.42 302 T
1204 4 F
1205 (originates the network LSA) 350.69 302 T
1206 0 F
1207 ( describ-) 492.27 302 T
1208 (ing the network\325) 85.54 288 T
1209 (s local environment. It also plays a ) 164.15 288 T
1210 4 F
1211 (special r) 334.04 288 T
1212 (ole in the \337ooding algorithm) 376.8 288 T
1213 0 F
1214 (, ) 521.4 288 T
1215 (since all routers on the network are synchronizing their link state databases by sending and ) 85.54 274 T
1216 (receiving LSAs to/from the Designated Router during the \337ooding process.) 85.54 260 T
1217 (\245) 72 240 T
1218 4 F
1219 -0.46 (Backup Designated Router) 85.54 240 P
1220 0 F
1221 -0.46 (. A Backup Designated Router is elected on multi-access networks ) 221.87 240 P
1222 (to speed/ease the transition of Designated Routers when the current Designated Router disap-) 85.54 226 T
1223 (pears. In that event, the Backup DR takes over) 85.54 212 T
1224 (, and does not need to go through the adjacency ) 308.22 212 T
1225 -0.13 (bringup process on the LAN \050since it already had done this in its Backup capacity\051. Also, even ) 85.54 198 P
1226 (before the disappearance of the Designated Router is noticed, the Backup DR will enable the ) 85.54 184 T
1227 (reliable \337ooding algorithm to proceed in the DR\325) 85.54 170 T
1228 (s absence.) 320.39 170 T
1229 FMENDPAGE
1230 %%EndPage: "4" 5
1231 %%Page: "5" 5
1232 612 792 0 FMBEGINPAGE
1233 72 702 540 720 R
1234 7 X
1235 0 K
1236 V
1237 0 F
1238 0 X
1239 (RFC 1245) 72 712 T
1240 (OSPF protocol analysis) 249.36 712 T
1241 (July 1991) 493.02 712 T
1242 72 69.05 540 81 R
1243 7 X
1244 V
1245 0 X
1246 ([Moy]) 72 73 T
1247 ([Page 5]) 499.7 73 T
1248 72 108 540 684 R
1249 7 X
1250 V
1251 0 X
1252 (\245) 72 676 T
1253 4 F
1254 (Non-br) 85.54 676 T
1255 (oadcast multi-access network support.) 122.63 676 T
1256 0 F
1257 ( OSPF treats these networks \050e.g., X.25 ) 318.51 676 T
1258 -0.01 (PDNs\051 pretty much as if they were LANs \050i.e., a DR is elected, and a network LSA is gener-) 85.54 662 P
1259 -0.29 (ated\051. Additional con\336guration information is needed however for routers attached to these net-) 85.54 648 P
1260 (work to initially \336nd each other) 85.54 634 T
1261 (.) 236.45 634 T
1262 (\245) 72 614 T
1263 4 F
1264 (OSPF ar) 85.54 614 T
1265 (eas) 130.29 614 T
1266 0 F
1267 (. OSPF allows the Autonomous Systems to be broken up into regions call areas. ) 146.28 614 T
1268 (This is useful for several reasons. First, it provides an extra level of ) 85.54 600 T
1269 4 F
1270 (r) 411.64 600 T
1271 (outing pr) 416.75 600 T
1272 (otection) 464.18 600 T
1273 0 F
1274 (: rout-) 504.81 600 T
1275 -0.29 (ing within an area is protected from all information external to the area. Second, by splitting an ) 85.54 586 P
1276 -0.3 (Autonomous System into areas the ) 85.54 572 P
1277 4 F
1278 -0.3 (cost of the Dijkstra pr) 254.27 572 P
1279 -0.3 (ocedur) 365.44 572 P
1280 -0.3 (e ) 400.53 572 P
1281 0 F
1282 -0.3 (\050in terms of CPU cycles\051 is ) 408.55 572 P
1283 (reduced.) 85.54 558 T
1284 (\245) 72 538 T
1285 4 F
1286 (Flexible import of external r) 85.54 538 T
1287 (outing information.) 230.55 538 T
1288 0 F
1289 ( In OSPF) 330.5 538 T
1290 (, ) 374.19 538 T
1291 4 F
1292 (each external r) 380.19 538 T
1293 (oute) 456.58 538 T
1294 0 F
1295 ( is imported ) 478.56 538 T
1296 (into the Autonomous System in ) 85.54 524 T
1297 4 F
1298 (a separate LSA) 240.47 524 T
1299 0 F
1300 (. This reduces the amount of \337ooding traf) 319.08 524 T
1301 (\336c ) 518.07 524 T
1302 (\050since external routes change often, and you want to only \337ood the changes\051. It also enables ) 85.54 510 T
1303 4 F
1304 -0.43 (partial r) 85.54 496 P
1305 -0.43 (outing table updates) 127.86 496 P
1306 0 F
1307 -0.43 ( when only a single external route changes. OSPF external LSAs ) 230.96 496 P
1308 (also provide the following features. A ) 85.54 482 T
1309 4 F
1310 (forwarding addr) 270.4 482 T
1311 (ess) 355.81 482 T
1312 0 F
1313 ( can be included in the external ) 370.46 482 T
1314 (LSA, eliminating extra-hops at the edge of the Autonomous System. There are two levels of ) 85.54 468 T
1315 (external metrics that can be speci\336ed, ) 85.54 454 T
1316 4 F
1317 (type 1) 269.06 454 T
1318 0 F
1319 ( and ) 300.04 454 T
1320 4 F
1321 (type 2) 323.35 454 T
1322 0 F
1323 (. Also, external routes can be tagged ) 354.33 454 T
1324 (with a 32-bit number \050the ) 85.54 440 T
1325 4 F
1326 (external r) 211.12 440 T
1327 (oute tag) 261.19 440 T
1328 0 F
1329 (; commonly used as an AS number of the route\325) 302.16 440 T
1330 (s ) 531.68 440 T
1331 (origin\051, simplifying external route management in a transit Autonomous System.) 85.54 426 T
1332 (\245) 72 406 T
1333 4 F
1334 (Four level r) 85.54 406 T
1335 (outing hierar) 145.27 406 T
1336 (chy) 212.69 406 T
1337 0 F
1338 (. OSPF has a four level routing hierarchy) 229.9 406 T
1339 (, or trust model: ) 426.32 406 T
1340 4 F
1341 (intra-) 505.94 406 T
1342 (ar) 85.54 392 T
1343 (ea) 96.64 392 T
1344 0 F
1345 (, ) 107.96 392 T
1346 4 F
1347 (inter) 113.96 392 T
1348 (-ar) 138.16 392 T
1349 (ea) 153.26 392 T
1350 0 F
1351 (, ) 164.59 392 T
1352 4 F
1353 (external type 1) 170.58 392 T
1354 0 F
1355 ( and ) 246.52 392 T
1356 4 F
1357 (external type 2) 269.84 392 T
1358 0 F
1359 ( routes. This enables multiple levels of ) 345.78 392 T
1360 (routing protection, and simpli\336es routing management in an Autonomous System.) 85.54 378 T
1361 (\245) 72 358 T
1362 4 F
1363 (V) 85.54 358 T
1364 (irtual links) 93.75 358 T
1365 0 F
1366 (. By allowing the con\336guration of virtual links, OSPF ) 150.07 358 T
1367 4 F
1368 (r) 410.94 358 T
1369 (emoves topological ) 416.05 358 T
1370 (r) 85.54 344 T
1371 (estrictions) 90.64 344 T
1372 0 F
1373 ( on area layout in an Autonomous System.) 143.27 344 T
1374 (\245) 72 324 T
1375 4 F
1376 -0.32 (Authentication of r) 85.54 324 P
1377 -0.32 (outing pr) 182.62 324 P
1378 -0.32 (otocol exchanges) 229.74 324 P
1379 0 F
1380 -0.32 (. Every time an OSPF router receives a routing ) 315.03 324 P
1381 (protocol packet, it authenticates the packet before processing it further) 85.54 310 T
1382 (.) 422.61 310 T
1383 (\245) 72 290 T
1384 4 F
1385 -0.03 (Flexible r) 85.54 290 P
1386 -0.03 (outing metric.) 134.26 290 P
1387 0 F
1388 -0.03 ( In OSPF) 206.18 290 P
1389 -0.03 (, metric are assigned to outbound router interfaces. The cost ) 249.82 290 P
1390 (of a path is then the sum of the path\325) 85.54 276 T
1391 (s component interfaces. The routing metric itself can be ) 260.42 276 T
1392 (assigned by the system administrator to indicate any combination of network characteristics ) 85.54 262 T
1393 (\050e.g., delay) 85.54 248 T
1394 (, bandwidth, dollar cost, etc.\051.) 138.04 248 T
1395 (\245) 72 228 T
1396 4 F
1397 -0.09 (Equal-cost multipath.) 85.54 228 P
1398 0 F
1399 -0.09 ( When multiple best cost routes to a destination exist, OSPF \336nds them ) 196.73 228 P
1400 (and they can be then used to load share traf) 85.54 214 T
1401 (\336c to the destination.) 292.82 214 T
1402 (\245) 72 194 T
1403 4 F
1404 (T) 85.54 194 T
1405 (OS-based r) 93.32 194 T
1406 (outing.) 150.74 194 T
1407 0 F
1408 ( Separate sets of routes can be calculated for each IP type of service. For ) 186.4 194 T
1409 (example, low delay traf) 85.54 180 T
1410 (\336c could be routed on one path, while high bandwidth traf) 198.56 180 T
1411 (\336c is routed ) 477.16 180 T
1412 -0.39 (on another) 85.54 166 P
1413 -0.39 (. This is done by \050optionally\051 assigning, to each outgoing router interface, one metric ) 135.44 166 P
1414 (for each IP T) 85.54 152 T
1415 (OS.) 148.26 152 T
1416 (\245) 72 132 T
1417 4 F
1418 (V) 85.54 132 T
1419 (ariable-length subnet support.) 93.09 132 T
1420 0 F
1421 ( OSPF includes support for variable-length subnet masks by ) 248.02 132 T
1422 (carrying a network mask with each advertised destination.) 85.54 118 T
1423 FMENDPAGE
1424 %%EndPage: "5" 6
1425 %%Page: "6" 6
1426 612 792 0 FMBEGINPAGE
1427 72 702 540 720 R
1428 7 X
1429 0 K
1430 V
1431 0 F
1432 0 X
1433 (RFC 1245) 72 712 T
1434 (OSPF protocol analysis) 249.36 712 T
1435 (July 1991) 493.02 712 T
1436 72 69.05 540 81 R
1437 7 X
1438 V
1439 0 X
1440 ([Moy]) 72 73 T
1441 ([Page 6]) 499.7 73 T
1442 72 108 540 684 R
1443 7 X
1444 V
1445 0 X
1446 (\245) 72 676 T
1447 4 F
1448 -0.08 (Stub ar) 85.54 676 P
1449 -0.08 (ea support. ) 123.56 676 P
1450 0 F
1451 -0.08 (T) 183.69 676 P
1452 -0.08 (o support routers having insuf) 190.18 676 P
1453 -0.08 (\336cient memory) 333.53 676 P
1454 -0.08 (, areas can be con\336gured as ) 405.63 676 P
1455 (stubs. External LSAs \050often making up the bulk of the Autonomous System\051 are not \337ooded ) 85.54 662 T
1456 (into/throughout stub areas. Routing to external destinations in stub areas is based solely on ) 85.54 648 T
1457 (default.) 85.54 634 T
1458 FMENDPAGE
1459 %%EndPage: "6" 7
1460 %%Page: "7" 7
1461 612 792 0 FMBEGINPAGE
1462 72 702 540 720 R
1463 7 X
1464 0 K
1465 V
1466 0 F
1467 0 X
1468 (RFC 1245) 72 712 T
1469 (OSPF protocol analysis) 249.36 712 T
1470 (July 1991) 493.02 712 T
1471 72 69.05 540 81 R
1472 7 X
1473 V
1474 0 X
1475 ([Moy]) 72 73 T
1476 ([Page 7]) 499.7 73 T
1477 72 108 540 684 R
1478 7 X
1479 V
1480 2 F
1481 0 X
1482 (3.0  Cost of the pr) 72 673.33 T
1483 (otocol) 193.4 673.33 T
1484 0 F
1485 -0.1 (This section attempts to analyze how the OSPF protocol will perform and scale in the Internet. In ) 72 646 P
1486 (this analysis, we will concentrate on the following four areas:) 72 632 T
1487 (\245) 72 612 T
1488 4 F
1489 (Link bandwidth) 85.54 612 T
1490 0 F
1491 (. In OSPF) 168.53 612 T
1492 (, a reliable \337ooding mechanism is used to ensure that router link ) 215.22 612 T
1493 (state databases are remained synchronized. Individual components of the link state databases ) 85.54 598 T
1494 -0.17 (\050the LSAs\051 are refreshed infrequently \050every 30 minutes\051, at least in the absence of topological ) 85.54 584 P
1495 (changes. Still, as the size of the database increases, the amount of link bandwidth used by the ) 85.54 570 T
1496 (\337ooding procedure also increases.) 85.54 556 T
1497 (\245) 72 536 T
1498 4 F
1499 -0.03 (Router memory) 85.54 536 P
1500 0 F
1501 -0.03 (. The size of an OSPF link state database can get quite lar) 166.32 536 P
1502 -0.03 (ge, especially in the ) 441.86 536 P
1503 (presence of many external LSAs. This imposes requirements on the amount of router memory ) 85.54 522 T
1504 (available.) 85.54 508 T
1505 (\245) 72 488 T
1506 4 F
1507 (CPU usage) 85.54 488 T
1508 0 F
1509 (. In OSPF) 141.83 488 T
1510 (, this is dominated by the length of time it takes to run the shortest path ) 188.52 488 T
1511 (calculation \050Dijkstra procedure\051. This is a function of the number of routers in the OSPF sys-) 85.54 474 T
1512 (tem.) 85.54 460 T
1513 (\245) 72 440 T
1514 4 F
1515 (Role of the Designated Router) 85.54 440 T
1516 (.) 238.32 440 T
1517 0 F
1518 ( The Designated router receives and sends more packets on a ) 241.32 440 T
1519 -0.46 (multi-access networks than the other routers connected to the network. Also, there is some time ) 85.54 426 P
1520 (involved in cutting over to a new Designated Router after the old one fails \050especially when ) 85.54 412 T
1521 (both the Backup Designated Router and the Designated Router fail at the same time\051. For this ) 85.54 398 T
1522 -0.27 (reason, it is possible that you may want to limit the number of routers connected to a single net-) 85.54 384 P
1523 (work.) 85.54 370 T
1524 (The remaining section will analyze these areas, estimating how much resources the OSPF proto-) 72 344 T
1525 -0.05 (col will consume, both now and in the future. T) 72 330 P
1526 -0.05 (o aid in this analysis, the next section will present ) 298.93 330 P
1527 (some data that have been collected in actual OSPF \336eld deployments.) 72 316 T
1528 3 F
1529 (3.1   Operational data) 72 282.67 T
1530 0 F
1531 -0.44 (The OSPF protocol has been deployed in a number of places in the Internet. For a summary of this ) 72 256 P
1532 (deployment, see [1]. Some statistics have been gathered from this operational experience, via ) 72 242 T
1533 -0.03 (local network management facilities. Some of these statistics are presented in the following table:) 72 228 P
1534 FMENDPAGE
1535 %%EndPage: "7" 8
1536 5 10 /Times-Bold FMDEFINEFONT
1537 %%Page: "8" 8
1538 612 792 0 FMBEGINPAGE
1539 72 702 540 720 R
1540 7 X
1541 0 K
1542 V
1543 0 F
1544 0 X
1545 (RFC 1245) 72 712 T
1546 (OSPF protocol analysis) 249.36 712 T
1547 (July 1991) 493.02 712 T
1548 72 69.05 540 81 R
1549 7 X
1550 V
1551 0 X
1552 ([Moy]) 72 73 T
1553 ([Page 8]) 499.7 73 T
1554 72 108 540 684 R
1555 7 X
1556 V
1557 72 666.01 540 674 C
1558 72 671.98 540 671.98 2 L
1559 0.5 H
1560 0 Z
1561 0 X
1562 0 K
1563 N
1564 0 0 612 792 C
1565 5 F
1566 0 X
1567 0 K
1568 (T) 72 677.33 T
1569 (ABLE 1. Pertinent operational statistics) 77.93 677.33 T
1570 (Statistic) 72 655.34 T
1571 (BARRNet) 216 655.34 T
1572 (NSI) 324 655.34 T
1573 (OARnet) 432 655.34 T
1574 1 F
1575 (Data gathering \050duration\051) 72 638.34 T
1576 (99 hours) 216 638.34 T
1577 (277 hours) 324 638.34 T
1578 (28 hours) 432 638.34 T
1579 (Dijkstra frequency) 72 622.34 T
1580 (50 minutes) 216 622.34 T
1581 (25 minutes) 324 622.34 T
1582 (13 minutes) 432 622.34 T
1583 (External incremental frequency) 72 606.34 T
1584 (1.2 minutes) 216 606.34 T
1585 (.98 minutes) 324 606.34 T
1586 (not gathered) 432 606.34 T
1587 (Database turnover) 72 590.34 T
1588 (29.7 minutes) 216 590.34 T
1589 (30.9 minutes) 324 590.34 T
1590 (28.2 minutes) 432 590.34 T
1591 (LSAs per packet) 72 574.34 T
1592 (3.38) 216 574.34 T
1593 (3.16) 324 574.34 T
1594 (2.99) 432 574.34 T
1595 (Flooding retransmits) 72 558.34 T
1596 (1.3%) 216 558.34 T
1597 (1.4%) 324 558.34 T
1598 (.7%) 432 558.34 T
1599 0 F
1600 (The \336rst line in the above table show the length of time that statistics were gathered on the three ) 72 533.01 T
1601 (networks. A brief description of the other statistics follows:) 72 519.01 T
1602 (\245) 72 499.01 T
1603 4 F
1604 (Dijkstra fr) 85.54 499.01 T
1605 (equency) 140.27 499.01 T
1606 (. ) 181.59 499.01 T
1607 0 F
1608 (In OSPF) 187.59 499.01 T
1609 (, the Dijkstra calculation involves only those routers and transit ) 228.28 499.01 T
1610 -0.14 (networks belonging to the AS. The Dijkstra is run only when something in the system changes ) 85.54 485.01 P
1611 (\050like a serial line between two routers goes down\051. Note that in these operational systems, the ) 85.54 471.01 T
1612 (Dijkstra process runs only infrequently \050the most frequent being every 13 minutes\051.) 85.54 457.01 T
1613 (\245) 72 437.01 T
1614 4 F
1615 (External incr) 85.54 437.01 T
1616 (emental fr) 153.61 437.01 T
1617 (equency) 206.35 437.01 T
1618 0 F
1619 (. In OSPF) 247.54 437.01 T
1620 (, when an external route changes only its entry in ) 294.23 437.01 T
1621 -0.13 (the routing table is recalculated. These are called external incremental updates. Note that these ) 85.54 423.01 P
1622 (happen much more frequently than the Dijkstra procedure. \050in other words, incremental ) 85.54 409.01 T
1623 (updates are saving quite a bit of processor time\051.) 85.54 395.01 T
1624 (\245) 72 375.01 T
1625 4 F
1626 -0.45 (Database turnover) 85.54 375.01 P
1627 -0.45 (.) 179.58 375.01 P
1628 0 F
1629 -0.45 ( In OSPF) 182.58 375.01 P
1630 -0.45 (, link state advertisements are refreshed at a minimum of every 30 ) 225.36 375.01 P
1631 (minutes. New advertisement instances are sent out more frequently when some part of the ) 85.54 361.01 T
1632 -0.2 (topology changes. The table shows that, even taking topological changes into account, on aver-) 85.54 347.01 P
1633 (age an advertisement is updated close to only every 30 minutes. This statistic will be used in ) 85.54 333.01 T
1634 (the link bandwidth calculations below) 85.54 319.01 T
1635 (. Note that NSI actually shows advertisements updated ) 267.31 319.01 T
1636 (every 30.7 \050> 30\051 minutes. This probably means that at one time earlier in the measurement ) 85.54 305.01 T
1637 (period, NSI had a smaller link state database that it did at the end.) 85.54 291.01 T
1638 (\245) 72 271.01 T
1639 4 F
1640 -0.39 (LSAs per packet.) 85.54 271.01 P
1641 0 F
1642 -0.39 ( In OSPF) 173.04 271.01 P
1643 -0.39 (, multiple LSAs can be included in either Link State Update or Link ) 215.95 271.01 P
1644 -0.35 (State Acknowledgment packets.The table shows that, on average, around 3 LSAs are carried in ) 85.54 257.01 P
1645 (a single packet. This statistic is used when calculating the header overhead in the link band-) 85.54 243.01 T
1646 (width calculation below) 85.54 229.01 T
1647 (. This statistic was derived by diving the number of LSAs \337ooded by ) 200.01 229.01 T
1648 (the number of \050non-hello\051 multicasts sent.) 85.54 215.01 T
1649 (\245) 72 195.01 T
1650 4 F
1651 (Flooding r) 85.54 195.01 T
1652 (etransmits.) 138.97 195.01 T
1653 0 F
1654 ( This counts both retransmission of LS Update packets and Link State ) 195.92 195.01 T
1655 (Acknowledgment packets, as a percentage of the original multicast \337ooded packets. The table ) 85.54 181.01 T
1656 (shows that \337ooding is working well, and that retransmits can be ignored in the link bandwidth ) 85.54 167.01 T
1657 (calculation below) 85.54 153.01 T
1658 (.) 169.69 153.01 T
1659 FMENDPAGE
1660 %%EndPage: "8" 9
1661 %%Page: "9" 9
1662 612 792 0 FMBEGINPAGE
1663 72 702 540 720 R
1664 7 X
1665 0 K
1666 V
1667 0 F
1668 0 X
1669 (RFC 1245) 72 712 T
1670 (OSPF protocol analysis) 249.36 712 T
1671 (July 1991) 493.02 712 T
1672 72 69.05 540 81 R
1673 7 X
1674 V
1675 0 X
1676 ([Moy]) 72 73 T
1677 ([Page 9]) 499.7 73 T
1678 72 108 540 684 R
1679 7 X
1680 V
1681 3 F
1682 0 X
1683 (3.2  Link bandwidth) 72 674.67 T
1684 0 F
1685 -0.02 (In this section we attempt to calculate how much link bandwidth is consumed by the OSPF \337ood-) 72 648 P
1686 (ing process. The amount of link bandwidth consumed increases linearly with the number of ) 72 634 T
1687 (advertisements present in the OSPF database.W) 72 620 T
1688 (e assume that the majority of advertisements in ) 300.88 620 T
1689 (the database will be AS external LSAs \050operationally this is true, see [1]\051.) 72 606 T
1690 (From the statistics presented in Section 3.1, any particular advertisement is \337ooded \050on average\051 ) 72 580 T
1691 (every 30 minutes. In addition, three advertisements \336t in a single packet. \050This packet could be ) 72 566 T
1692 (either a Link State Update packet or a Link State Acknowledgment packet; in this analysis we ) 72 552 T
1693 (select the Link State Update packet, which is the lar) 72 538 T
1694 (ger\051. An AS external LSA is 36 bytes long. ) 320.93 538 T
1695 (Adding one third of a packet header \050IP header plus OSPF Update packet\051 yields 52 bytes. T) 72 524 T
1696 (rans-) 515.59 524 T
1697 (mitting this amount of data every 30 minutes gives an average rate of 23/100 bits/second.) 72 510 T
1698 -0.05 (If you want to limit your routing traf) 72 484 P
1699 -0.05 (\336c to 5% of the link\325) 247.03 484 P
1700 -0.05 (s total bandwidth, you get the following ) 345.75 484 P
1701 (maximums for database size:) 72 470 T
1702 72 434.01 540 442 C
1703 72 439.98 540 439.98 2 L
1704 0.5 H
1705 0 Z
1706 0 X
1707 0 K
1708 N
1709 0 0 612 792 C
1710 5 F
1711 0 X
1712 0 K
1713 (T) 72 445.33 T
1714 (ABLE 2. Database size as a function of link speed \0505% utilization\051) 77.93 445.33 T
1715 (Speed) 180 423.34 T
1716 (# external advertisements) 288 423.34 T
1717 1 F
1718 (9.6 Kb) 180 406.34 T
1719 (2087) 288 406.34 T
1720 (56 Kb) 180 390.34 T
1721 (12,174) 288 390.34 T
1722 0 F
1723 -0.46 (Higher line speeds have not been included, because other factors will then limit database size \050like ) 72 365.01 P
1724 -0.12 (router memory\051 before line speed becomes a factor) 72 351.01 P
1725 -0.12 (. Note that in the above calculation, the size of ) 315.32 351.01 P
1726 -0.06 (the data link header was not taken into account. Also, note that while the OSPF database is likely ) 72 337.01 P
1727 (to be mostly external LSAs, other LSAs have a size also. As a ballpark estimate, router links and ) 72 323.01 T
1728 -0.01 (network links are generally three times as lar) 72 309.01 P
1729 -0.01 (ge as an AS external link, with summary link adver-) 287.18 309.01 P
1730 (tisements being the same size as external link LSAs.) 72 295.01 T
1731 (OSPF consumes considerably less link bandwidth than RIP) 72 269.01 T
1732 (. This has been shown experimentally ) 355.51 269.01 T
1733 (in the NSI network. See Jef) 72 255.01 T
1734 (frey Bur) 203.69 255.01 T
1735 (gan\325) 243.77 255.01 T
1736 (s \322NASA Sciences Internet\323 report in [3].) 264.42 255.01 T
1737 3 F
1738 (3.3  Router memory) 72 221.67 T
1739 0 F
1740 -0.1 (Memory requirements in OSPF are dominated by the size of the link state database. As in the pre-) 72 195.01 P
1741 (vious section, it is probably safe to assume that most of the advertisements in the database are ) 72 181.01 T
1742 (external LSAs. While an external LSA is 36 bytes long, it is generally stored by an OSPF imple-) 72 167.01 T
1743 -0.34 (mentation together with some support data. So a good estimate of router memory consumed by an ) 72 153.01 P
1744 (external LSA is probably 64 bytes. So a database having 10,000 external LSAs will consume ) 72 139.01 T
1745 (640K bytes of router memory) 72 125.01 T
1746 (. OSPF de\336nitely requires more memory than RIP) 213.79 125.01 T
1747 (.) 452.98 125.01 T
1748 FMENDPAGE
1749 %%EndPage: "9" 10
1750 %%Page: "10" 10
1751 612 792 0 FMBEGINPAGE
1752 72 702 540 720 R
1753 7 X
1754 0 K
1755 V
1756 0 F
1757 0 X
1758 (RFC 1245) 72 712 T
1759 (OSPF protocol analysis) 249.36 712 T
1760 (July 1991) 493.02 712 T
1761 72 69.05 540 81 R
1762 7 X
1763 V
1764 0 X
1765 ([Moy]) 72 73 T
1766 ([Page 10]) 493.7 73 T
1767 72 108 540 684 R
1768 7 X
1769 V
1770 0 X
1771 -0.35 (Using the Proteon P4200 implementation as an example, the P4200 has 2Mbytes of memory) 72 676 P
1772 -0.35 (. This ) 510.38 676 P
1773 -0.02 (is shared between instruction, data and packet buf) 72 662 P
1774 -0.02 (fer memory) 310.78 662 P
1775 -0.02 (. The P4200 has enough memory to ) 366.26 662 P
1776 (store 10, 000 external LSAs, and still have enough packet buf) 72 648 T
1777 (fer memory available to run a rea-) 367.58 648 T
1778 (sonable number of interfaces.) 72 634 T
1779 (Also, note that while the OSPF database is likely to be mostly external LSAs, other LSAs have a ) 72 608 T
1780 -0.06 (size also. As a ballpark estimate, router links and network links consume generally three times as ) 72 594 P
1781 (much memory as an AS external link, with summary link advertisements being the same size as ) 72 580 T
1782 (external link LSAs.) 72 566 T
1783 3 F
1784 (3.4  Router CPU) 72 532.67 T
1785 0 F
1786 (Assume that, as the size of the OSPF routing domain grows, the number of interfaces per router ) 72 506 T
1787 (stays bounded. Then the Dijkstra calculation is of order \050n * log \050n\051\051, where n is the number of ) 72 492 T
1788 (routers in the routing domain. \050This is the complexity of the Dijkstra algorithm in a sparse net-) 72 478 T
1789 (work\051. Of course, it is implementation speci\336c as to how expensive the Dijkstra really is.) 72 464 T
1790 (W) 72 438 T
1791 (e have no experimental numbers for the cost of the Dijkstra calculation in a real OSPF imple-) 82.36 438 T
1792 (mentation. However) 72 424 T
1793 (, Steve Deering presented results for the Dijkstra calculation in the \322MOSPF ) 169.45 424 T
1794 (meeting report\323 in [3]. Steve\325) 72 410 T
1795 (s calculation was done on a DEC 5000 \05010 mips processor\051, using ) 212.9 410 T
1796 (the Stanford internet as a model. His graphs are based on numbers of networks, not number of ) 72 396 T
1797 (routers. However) 72 382 T
1798 (, if we extrapolate that the ratio of routers to networks remains the same, the ) 154.78 382 T
1799 (time to run Dijkstra for 200 routers in Steve\325) 72 368 T
1800 (s implementation was around 15 milliseconds.) 285.87 368 T
1801 -0.46 (This seems a reasonable cost, particularly when you notice that the Dijkstra calculation is run very ) 72 342 P
1802 (infrequently in operational deployments. In the three networks presented in Section 3.1, Dijkstra ) 72 328 T
1803 -0.35 (was run on average only every 13 to 50 minutes. Since the Dijkstra is run so infrequently) 72 314 P
1804 -0.35 (, it seems ) 493.06 314 P
1805 -0.02 (likely that OSPF overall consumes less CPU than RIP \050because of RIP\325) 72 300 P
1806 -0.02 (s frequent updates, requir-) 413.95 300 P
1807 (ing routing table lookups\051.) 72 286 T
1808 (As another example, the routing algorithm in MILNET is SPF-based. MILNET\325) 72 260 T
1809 (s current size is ) 456.42 260 T
1810 -0.02 (230 nodes, and the routing calculation still consumes less than 5% of the MILNET switches\325 pro-) 72 246 P
1811 (cessor bandwidth [4]. Because the routing algorithm in the MILNET adapts to network load, it ) 72 232 T
1812 (runs the Dijkstra process quite frequently \050on the order of seconds as compared to OSPF\325) 72 218 T
1813 (s min-) 499.7 218 T
1814 (utes\051. However) 72 204 T
1815 (, it should be noted that the routing algorithm in MILNET incrementally updates ) 144.79 204 T
1816 (the SPF-tree, while OSPF rebuilds it from scratch at each Dijkstra calculation) 72 190 T
1817 (OSPF\325) 72 164 T
1818 (s Area capability provides a way to reduce Dijkstra overhead, if it becomes a burden. The ) 104 164 T
1819 -0 (routing domain can be split into areas. The extent of the Dijkstra calculation \050and its complexity\051 ) 72 150 P
1820 (is limited to a single area at a time.) 72 136 T
1821 FMENDPAGE
1822 %%EndPage: "10" 11
1823 %%Page: "11" 11
1824 612 792 0 FMBEGINPAGE
1825 72 702 540 720 R
1826 7 X
1827 0 K
1828 V
1829 0 F
1830 0 X
1831 (RFC 1245) 72 712 T
1832 (OSPF protocol analysis) 249.36 712 T
1833 (July 1991) 493.02 712 T
1834 72 69.05 540 81 R
1835 7 X
1836 V
1837 0 X
1838 ([Moy]) 72 73 T
1839 ([Page 11]) 493.7 73 T
1840 72 108 540 684 R
1841 7 X
1842 V
1843 3 F
1844 0 X
1845 (3.5  Role of Designated Router) 72 674.67 T
1846 0 F
1847 (This section explores the number of routers that can be attached to a single network. As the num-) 72 648 T
1848 -0.36 (ber of routers attached to a network grows, so does the amount of OSPF routing traf) 72 634 P
1849 -0.36 (\336c seen on the ) 469.48 634 P
1850 (network. Some of this is Hello traf) 72 620 T
1851 (\336c, which is generally multicast by each router every 10 sec-) 238.01 620 T
1852 -0.07 (onds. This burden is borne by all routers attached to the network. However) 72 606 P
1853 -0.07 (, because of its special ) 429.77 606 P
1854 -0.08 (role in the \337ooding process, the Designated router ends up sending more Link State Updates than ) 72 592 P
1855 (the other routers on the network. Also, the Designated Router receives Link State Acknowledg-) 72 578 T
1856 -0.15 (ments from all attached routers, while the other routers just receive them from the DR. \050Although ) 72 564 P
1857 (it is important to note that the rate of Link State Acknowledgments will generally be limited to ) 72 550 T
1858 (one per second from each router) 72 536 T
1859 (, because acknowledgments are generally delayed.\051) 226.38 536 T
1860 -0.22 (So, if the amount of protocol traf) 72 510 P
1861 -0.22 (\336c on the LAN becomes a limiting factor) 228.71 510 P
1862 -0.22 (, the limit is likely to be ) 424.24 510 P
1863 (detected in the Designated Router \336rst. However) 72 496 T
1864 (, such a limit is not expected to be reached in ) 305.68 496 T
1865 (practice. The amount of routing protocol traf) 72 482 T
1866 (\336c generated by OSPF has been shown to be small ) 286.62 482 T
1867 -0.11 (\050see Section 3.2\051. Also, if need be OSPF\325) 72 468 P
1868 -0.11 (s hello timers can be con\336gured to reduce the amount of ) 268.43 468 P
1869 (protocol traf) 72 454 T
1870 (\336c on the network. Note that more than 50 routers have been simulated attached to a ) 131.4 454 T
1871 (single LAN \050see [1]\051. Also, in interoperability testing 13 routers have been attached to a single ) 72 440 T
1872 (ethernet with no problems encountered.) 72 426 T
1873 -0.02 (Another factor in the number of routers attached to a single network is the cutover time when the ) 72 400 P
1874 -0.17 (Designated Router fails. OSPF has a Backup Designated Router so that the cutover does not have ) 72 386 P
1875 -0.31 (to wait for the new DR to synchronize \050the adjacency bring-up process mentioned earlier\051 with all ) 72 372 P
1876 -0.43 (the other routers on the LAN; as a Backup DR it had already synchronized. However) 72 358 P
1877 -0.43 (, in those rare ) 473.46 358 P
1878 -0.33 (cases when both DR and Backup DR crash at the same time, the new DR will have to synchronize ) 72 344 P
1879 (\050via the adjacency bring-up process\051 with all other routers before becoming functional. Field ) 72 330 T
1880 -0.44 (experience show that this synchronization process takes place in a timely fashion \050see the OARnet ) 72 316 P
1881 (report in [1]\051. However) 72 302 T
1882 (, this may be an issue in systems that have many routers attached to a sin-) 183.42 302 T
1883 (gle network.) 72 288 T
1884 -0.15 (In the unlikely event that the number of routers attached to a LAN becomes a problem, either due ) 72 262 P
1885 (to the amount of routing protocol traf) 72 248 T
1886 (\336c or the cutover time, the LAN can be split into separate ) 251 248 T
1887 (pieces \050similar to splitting up the AS into separate areas\051.) 72 234 T
1888 3 F
1889 (3.6  Summary) 72 200.67 T
1890 0 F
1891 (In summary) 72 174 T
1892 (, it seems like the most likely limitation to the size of an OSPF system is available ) 128.85 174 T
1893 -0.4 (router memory) 72 160 P
1894 -0.4 (. W) 142.43 160 P
1895 -0.4 (e have given as 10,000 as the number of external LSAs that can be supported by ) 158.39 160 P
1896 (the memory available in one con\336guration of a particular implementation \050the Proteon P4200\051. ) 72 146 T
1897 -0.09 (Other implementations may vary; nowadays routers are being built with more and more memory) 72 132 P
1898 -0.09 (. ) 534.09 132 P
1899 FMENDPAGE
1900 %%EndPage: "11" 12
1901 %%Page: "12" 12
1902 612 792 0 FMBEGINPAGE
1903 72 702 540 720 R
1904 7 X
1905 0 K
1906 V
1907 0 F
1908 0 X
1909 (RFC 1245) 72 712 T
1910 (OSPF protocol analysis) 249.36 712 T
1911 (July 1991) 493.02 712 T
1912 72 69.05 540 81 R
1913 7 X
1914 V
1915 0 X
1916 ([Moy]) 72 73 T
1917 ([Page 12]) 493.7 73 T
1918 72 108 540 684 R
1919 7 X
1920 V
1921 0 X
1922 (Note that 10,000 routes is considerably lar) 72 676 T
1923 (ger than the lar) 275.31 676 T
1924 (gest \336eld implementation \050BARRNet; ) 347.37 676 T
1925 (which at 1816 external LSAs is still very lar) 72 662 T
1926 (ge\051.) 283.65 662 T
1927 (Note that there may be ways to reduce database size in a routing domain. First, the domain can ) 72 636 T
1928 -0.19 (make use of default routing, reducing the number of external routes that need to be imported. Sec-) 72 622 P
1929 (ondly) 72 608 T
1930 (, an EGP can be used that will transport its own information through the AS instead of rely-) 98.54 608 T
1931 -0.21 (ing on the IGP \050OSPF in this case\051 to do transfer the information for it \050the EGP\051. Thirdly) 72 594 P
1932 -0.21 (, routers ) 498.11 594 P
1933 (having insuf) 72 580 T
1934 (\336cient memory may be able to be assigned to stub areas \050whose databases are drasti-) 131.41 580 T
1935 (cally smaller\051. Lastly) 72 566 T
1936 (, if the Internet went away from a \337at address space the amount of external ) 172.82 566 T
1937 (information imported into an OSPF domain could be reduced drastically) 72 552 T
1938 (.) 418.67 552 T
1939 (While not as likely) 72 526 T
1940 (, there could be other issues that would limit the size of an OSPF routing ) 162.17 526 T
1941 (domain. If there are slow lines \050like 9600 baud\051, the size of the database will be limited \050see Sec-) 72 512 T
1942 (tion 3.2\051. Dijkstra may get to be expensive when there are hundreds of routers in the OSPF ) 72 498 T
1943 (domain; although at this point the domain can be split into areas. Finally) 72 484 T
1944 (, when there are many ) 418.69 484 T
1945 (routers attached to a single network, there may be undue burden imposed upon the Designated ) 72 470 T
1946 (Router; although at that point a LAN can be split into separate LANs.) 72 456 T
1947 FMENDPAGE
1948 %%EndPage: "12" 13
1949 %%Page: "13" 13
1950 612 792 0 FMBEGINPAGE
1951 72 702 540 720 R
1952 7 X
1953 0 K
1954 V
1955 0 F
1956 0 X
1957 (RFC 1245) 72 712 T
1958 (OSPF protocol analysis) 249.36 712 T
1959 (July 1991) 493.02 712 T
1960 72 69.05 540 81 R
1961 7 X
1962 V
1963 0 X
1964 ([Moy]) 72 73 T
1965 ([Page 13]) 493.7 73 T
1966 72 108 540 684 R
1967 7 X
1968 V
1969 2 F
1970 0 X
1971 (4.0  Suitable envir) 72 673.33 T
1972 (onments) 195.21 673.33 T
1973 0 F
1974 -0.14 (Suitable environments for the OSPF protocol range from lar) 72 646 P
1975 -0.14 (ge to small. OSPF is particular suited ) 359.11 646 P
1976 (for transit Autonomous Systems for the following reasons. OSPF can accommodate a lar) 72 632 T
1977 (ge num-) 497.84 632 T
1978 (ber of external routes. In OSPF the import of external information is very \337exible, having provi-) 72 618 T
1979 -0.39 (sions for a forwarding address, two levels of external metrics, and the ability to tag external routes ) 72 604 P
1980 -0.29 (with their AS number for easy management. Also OSPF\325) 72 590 P
1981 -0.29 (s ability to do partial updates when exter-) 343.17 590 P
1982 (nal information changes is very useful on these networks.) 72 576 T
1983 (OSPF is also suited for smaller) 72 550 T
1984 (, either stand alone or stub Autonomous Systems, because of its ) 220.44 550 T
1985 (wide array of features: fast conver) 72 536 T
1986 (gence, equal-cost-multipath, T) 235.96 536 T
1987 (OS routing, areas, etc.) 382.3 536 T
1988 2 F
1989 (5.0  Unsuitable envir) 72 469.33 T
1990 (onments) 212.98 469.33 T
1991 0 F
1992 -0.22 (OSPF has a very limited ability to express policy) 72 442 P
1993 -0.22 (. Basically) 304.62 442 P
1994 -0.22 (, its only policy mechanisms are in the ) 354.25 442 P
1995 (establishment of a four level routing hierarchy: intra-area, inter) 72 428 T
1996 (-area, type 1 and type 2 external ) 374.52 428 T
1997 (routes. A system wanting more sophisticated policies would have to be split up into separate ) 72 414 T
1998 (ASes, running a policy-based EGP between them.) 72 400 T
1999 FMENDPAGE
2000 %%EndPage: "13" 14
2001 %%Page: "14" 14
2002 612 792 0 FMBEGINPAGE
2003 72 702 540 720 R
2004 7 X
2005 0 K
2006 V
2007 0 F
2008 0 X
2009 (RFC 1245) 72 712 T
2010 (OSPF protocol analysis) 249.36 712 T
2011 (July 1991) 493.02 712 T
2012 72 69.05 540 81 R
2013 7 X
2014 V
2015 0 X
2016 ([Moy]) 72 73 T
2017 ([Page 14]) 493.7 73 T
2018 72 108 540 684 R
2019 7 X
2020 V
2021 2 F
2022 0 X
2023 (6.0  Refer) 72 673.33 T
2024 (ence Documents) 137.87 673.33 T
2025 0 F
2026 (The following documents have been referenced by this report:) 72 646 T
2027 ([1]) 72 626 T
2028 (Moy) 108 626 T
2029 (, J., \322Experience with the OSPF protocol\323, RFC 1246, July 1991.) 129.88 626 T
2030 ([2]) 72 608 T
2031 (Moy) 108 608 T
2032 (, J., \322OSPF V) 129.88 608 T
2033 (ersion 2\323, RFC 1247, July 1991.) 193.85 608 T
2034 ([3]) 72 590 T
2035 (Corporation for National Research Initiatives, \322Proceedings of the Eighteenth Internet ) 108 590 T
2036 (Engineering T) 108 576 T
2037 (ask Force\323, University of British Columbia, July 30-August 3, 1990.) 176.11 576 T
2038 FMENDPAGE
2039 %%EndPage: "14" 15
2040 %%Page: "15" 15
2041 612 792 0 FMBEGINPAGE
2042 72 702 540 720 R
2043 7 X
2044 0 K
2045 V
2046 0 F
2047 0 X
2048 (RFC 1245) 72 712 T
2049 (OSPF protocol analysis) 249.36 712 T
2050 (July 1991) 493.02 712 T
2051 72 69.05 540 81 R
2052 7 X
2053 V
2054 0 X
2055 ([Moy]) 72 73 T
2056 ([Page 15]) 493.7 73 T
2057 72 108 540 684 R
2058 7 X
2059 V
2060 2 F
2061 0 X
2062 (Security Considerations) 72 673.33 T
2063 0 F
2064 (Security issues are not discussed in this memo.) 72 646 T
2065 2 F
2066 (Author) 72 617.33 T
2067 (\325) 122.04 617.33 T
2068 (s Addr) 126.77 617.33 T
2069 (ess) 173.13 617.33 T
2070 0 F
2071 (John Moy) 72 590 T
2072 (Proteon Inc.) 72 576 T
2073 (2 T) 72 562 T
2074 (echnology Drive) 87.48 562 T
2075 (W) 72 548 T
2076 (estborough, MA 01581) 82.36 548 T
2077 (Phone: \050508\051 898-2800) 72 522 T
2078 (Email: jmoy@proteon.com) 72 508 T
2079 FMENDPAGE
2080 %%EndPage: "15" 16
2081 %%Trailer
2082 %%BoundingBox: 0 0 612 792
2083 %%Pages: 15 1
2084 %%DocumentFonts: Times-Roman
2085 %%+ Times-Bold