idnits 2.17.1 draft-rfced-info-cabletron-vls-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 1) being 76 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 93 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 4 instances of lines with control characters in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 544 has weird spacing: '... form adjac...' == Line 558 has weird spacing: '...sements adve...' == Line 2153 has weird spacing: '...p 4a of els...' == Line 2157 has weird spacing: '...treated sent...' == Line 2213 has weird spacing: '... remove the a...' == (3 more instances...) -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (December 1998) is 9257 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 1688 -- Looks like a reference, but probably isn't: '2' on line 1956 -- Looks like a reference, but probably isn't: '3' on line 3022 -- Looks like a reference, but probably isn't: '4' on line 3086 -- Looks like a reference, but probably isn't: '5' on line 3093 -- Looks like a reference, but probably isn't: '6' on line 3097 -- Looks like a reference, but probably isn't: '7' on line 3890 ** Obsolete normative reference: RFC 1583 (Obsoleted by RFC 2178) ** Obsolete normative reference: RFC 1700 (Obsoleted by RFC 3232) Summary: 10 errors (**), 0 flaws (~~), 9 warnings (==), 10 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 INTERNET DRAFT EXPIRES JUNE 1999 INTERNET DRAFT 2 Network Working Group L. Kane 3 Cabletron Systems Incorporated 4 Category: Informational December 1998 6 Cabletron's VLS Protocol Specification 7 9 Status of This Memo 11 This document is an Internet-Draft. Internet-Drafts are working 12 documents of the Internet Engineering Task Force (IETF), its 13 areas, and its working groups. Note that other groups may also 14 distribute working documents as Internet-Drafts. 16 Internet-Drafts are draft documents valid for a maximum of six 17 months and may be updated, replaced, or obsoleted by other 18 documents at any time. It is inappropriate to use Internet- 19 Drafts as reference material or to cite them other than as 20 "work in progress." 22 To view the entire list of current Internet-Drafts, please check 23 the "1id-abstracts.txt" listing contained in the Internet-Drafts 24 Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net 25 (Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au 26 (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu 27 (US West Coast). 29 Distribution of this document is unlimited. 31 Copyright Notice 33 Copyright (C) The Internet Society (1999). All Rights Reserved. 35 Abstract 37 The Virtual LAN Link State Protocol (VLSP) is part of the 38 InterSwitch Message Protocol (ISMP) which provides interswitch 39 communication between switches running Cabletron's SecureFast 40 VLAN (SFVLAN) product. VLSP is used to determine and maintain a 41 fully connected mesh topology graph of the switch fabric. Each 42 switch maintains an identical database describing the topology. 43 Call-originating switches use the topology database to determine 44 the path over which to route a call connection. 46 VLSP provides support for equal-cost multipath routing, and 47 recalculates routes quickly in the face of topological changes, 48 utilizing a minimum of routing protocol traffic. 50 Table of Contents 52 Status of this Memo........................................ 1 53 Copyright Notice........................................... 1 54 Abstract................................................... 1 55 1. Introduction............................................ 3 56 1.1 Acknowledgments..................................... 3 57 1.2 Data Conventions.................................... 3 58 1.3 ISMP Overview....................................... 4 59 2. VLS Protocol Overview................................... 5 60 2.1 Definitions of Commonly Used Terms.................. 5 61 2.2 Differences Between VLSP and OSPF................... 7 62 2.2.1 Operation at the Physical Layer............... 7 63 2.2.2 All Links Treated as Point-to-Point........... 8 64 2.2.3 Routing Path Information...................... 9 65 2.2.4 Configurable Parameters....................... 9 66 2.2.5 Features Not supported........................ 9 67 2.3 Functional Summary.................................. 10 69 2.4 Protocol Packets.................................... 11 70 2.5 Protocol Data Structures............................ 12 71 2.6 Basic Implementation Requirements................... 12 72 2.7 Organization of the Remainder of This Document...... 13 73 3. Interface Data Structure................................ 14 74 3.1 Interface States.................................... 16 75 3.2 Events Causing Interface State Changes.............. 19 76 3.3 Interface State Machine............................. 21 77 4. Neighbor Data Structure................................. 23 78 4.1 Neighbor States..................................... 25 79 4.2 Events Causing Neighbor State Changes............... 27 80 4.3 Neighbor State Machine.............................. 29 81 5. Area Data Structure..................................... 33 82 5.1 Adding and Deleting Link State Advertisements....... 34 83 5.2 Accessing Link State Advertisements................. 34 84 5.3 Best Path Lookup.................................... 35 85 6. Discovery Process....................................... 35 86 6.1 Neighbor Discovery.................................. 35 87 6.2 Bidirectional Communication......................... 37 88 6.3 Designated Switch................................... 37 89 6.3.1 Selecting the Designated Switch............... 38 90 6.4 Adjacencies......................................... 41 91 7. Synchronizing the Databases............................. 41 92 7.1 Link State Advertisements........................... 42 93 7.1.1 Determining Which 94 Link State Advertisement Is Newer............. 43 95 7.2 Database Exchange Process........................... 44 96 7.2.1 Database Description Packets.................. 44 97 7.2.2 Negotiating the Master/Slave Relationship..... 45 98 7.2.3 Exchanging Database Description Packets....... 46 99 7.3 Updating the Database............................... 48 100 7.4 An Example.......................................... 48 101 8. Maintaining the Databases............................... 50 102 8.1 Originating Link State Advertisements............... 51 103 8.1.1 Switch Link Advertisements.................... 51 104 8.1.2 Network Link Advertisements................... 54 105 8.2 Distributing Link State Advertisements.............. 55 106 8.2.1 Overview...................................... 56 107 8.2.2 Processing an 108 Incoming Link State Update Packet............. 57 109 8.2.3 Forwarding Link State Advertisements.......... 59 110 8.2.4 Installing Link 111 State Advertisements in the Database.......... 61 112 8.2.5 Retransmitting Link State Advertisements...... 62 113 8.2.6 Acknowledging Link State Advertisements....... 62 114 8.3 Aging the Link State Database....................... 65 115 8.3.1 Premature Aging of Advertisements............. 65 116 9. Calculating the Best Paths............................. 66 117 10. Protocol Packets....................................... 66 118 10.1 ISMP Packet Format................................ 67 119 10.1.1 Frame Header............................... 67 121 10.1.2 ISMP Packet Header......................... 68 122 10.1.3 ISMP Message Body.......................... 69 123 10.2 VLSP Packet Processing............................ 69 124 10.3 Network Layer Address Information................. 70 125 10.4 VLSP Packet Header................................ 72 126 10.5 Options Field..................................... 74 127 10.6 Packet Formats.................................... 74 128 10.6.1 Hello Packets.............................. 75 129 10.6.2 Database Description Packets............... 77 130 10.6.3 Link State Request Packets................. 79 131 10.6.4 Link State Update Packets.................. 80 132 10.6.5 Link State Acknowledgment Packets.......... 81 133 11. Link State Advertisement Formats....................... 82 134 11.1 Link State Advertisement Headers.................. 83 135 11.2 Switch Link Advertisements........................ 85 136 11.3 Network Link Advertisements....................... 87 137 12. Protocol Parameters.................................... 88 138 12.1 Architectural Constants........................... 88 139 12.2 Configurable Parameters........................... 89 140 13. Footnotes.............................................. 91 141 14. Security Considerations................................ 92 142 15. References............................................. 92 143 16. Author's Addresses..................................... 92 144 17. Full Copyright Statement............................... 93 146 1. Introduction 148 This memo is being distributed to members of the Internet 149 community in order to solicit reactions to the proposals 150 contained herein. While the specification discussed here may 151 not be directly relevant to the research problems of the 152 Internet, it may be of interest to researchers and implementers. 154 1.1 Acknowledgments 156 VLSP is derived from the OSPF link-state routing protocol 157 described in [RFC1583], written by John Moy, formerly of 158 Proteon, Inc., Westborough, Massachusetts. Much of the current 159 memo has been drawn from [RFC1583]. Therefore, this author 160 wishes to acknowledge the contribution Mr. Moy has (unknowingly) 161 made to this document. 163 1.2 Data Conventions 165 The methods used in this memo to describe and picture data 166 adhere to the standards of Internet Protocol documentation 167 [RFC1700]. In particular: 169 The convention in the documentation of Internet Protocols is 170 to express numbers in decimal and to picture data in "big- 171 endian" order. That is, fields are described left to right, 172 with the most significant octet on the left and the least 173 significant octet on the right. 174 The order of transmission of the header and data 175 described in this document is resolved to the octet 176 level. Whenever a diagram shows a group of octets, the 177 order of transmission of those octets is the normal 178 order in which they are read in English. 180 Whenever an octet represents a numeric quantity the left 181 most bit in the diagram is the high order or most 182 significant bit. That is, the bit labeled 0 is the most 183 significant bit. 185 Similarly, whenever a multi-octet field represents a 186 numeric quantity the left most bit of the whole field is 187 the most significant bit. When a multi-octet quantity 188 is transmitted the most significant octet is transmitted 189 first. 191 1.3 ISMP Overview 193 The InterSwitch Message Protocol (ISMP) provides a consistent 194 method of encapsulating and transmitting control messages 195 exchanged between switches running Cabletron's SecureFast VLAN 196 (SFVLAN) product, as described in [IDsfvlan]. ISMP provides the 197 following services: 199 o Topology services. Each switch maintains a distributed 200 topology of the switch fabric by exchanging the following 201 interswitch control messages with other switches: 203 o Interswitch Keepalive messages are sent by each switch to 204 announce its existence to its neighboring switches and to 205 establish the topology of the switch fabric. (Interswitch 206 Keepalive messages are exchanged in accordance with 207 Cabletron's VlanHello protocol, described in [IDhello].) 209 o Interswitch Spanning Tree BPDU messages and Interswitch 210 Remote Blocking messages are used to determine and maintain 211 a loop-free flood path between all network switches in the 212 fabric. This flood path is used for all undirected 213 interswitch messages -- that is, messages that are 214 (potentially) sent to all switches in the switch fabric. 216 o Interswitch Link State messages (VLS protocol) are used to 217 determine and maintain a fully connected mesh topology 218 graph of the switch fabric. Call-originating switches use 220 the topology graph to determine the path over which to 221 route a call connection. 223 o Address resolution services. Interswitch Resolve messages 224 are used to resolve a packet destination address when the 225 packet source and destination pair does not match a known 226 connection. Interswitch New User messages are used to 227 provide end-station address mobility between switches. 229 o Tag-based flooding. A tag-based broadcast method is used to 230 restrict the broadcast of unresolved packets to only those 231 ports within the fabric that belong to the same VLAN as the 232 source. 234 o Call tapping services. Interswitch Tap messages are used to 235 monitor traffic moving between two end stations. Traffic can 236 be monitored in one or both directions along the connection 237 path. 239 Note 241 This document describes the ISMP messages used by the 242 VLS protocol. Other ISMP messages are described in 243 "Cabletron's SecureFast VLAN Operational Model" 244 [IDsfvlan] and in "Cabletron's VlanHello Protocol 245 Specification" [IDhello]. 247 2. VLS Protocol Overview 249 VLSP is a dynamic routing protocol. It quickly detects 250 topological changes in the switch fabric (such as, switch 251 interface failures) and calculates new loop-free routes after a 252 period of convergence. This period of convergence is short and 253 involves a minimum of routing traffic. 255 All switches in the fabric run the same algorithm and maintain 256 identical databases describing the switch fabric topology. This 257 database contains each switch's local state, including its 258 usable interfaces and reachable neighbors. Each switch 259 distributes its local state throughout the switch fabric by 260 flooding. From the topological database, each switch constructs 261 a set of best path trees (using itself as the root) that specify 262 routes to all other switches in the fabric. 264 2.1 Definitions of Commonly Used Terms 266 This section contains a collection of definitions for terms that 267 have a specific meaning to the protocol and that are used 268 throughout the text. 270 Switch ID 272 A 10-octet value that uniquely identifies the switch within 273 the switch fabric. The value consists of the 6-octet base 274 MAC address of the switch, followed by 4 octets of zeroes. 276 Network link 278 The physical connection between two switches. A link is 279 associated with a switch interface. 281 There are two physical types of network links supported by 282 VLSP: 284 o Point-to-point links that join a single pair of switches. 285 A serial line is an example of a point-to-point network 286 link. 288 o Multi-access broadcast links that support the attachment of 289 multiple switches, along with the capability to address a 290 single message to all the attached switches. An attached 291 ethernet is an example of a multi-access broadcast network 292 link. 294 A single topology can contain both types of links. At 295 startup, all links are assumed to be point-to-point. A link 296 is determined to be multi-access when more than one 297 neighboring switch is discovered on the link. 299 Interface 301 The port over which a switch accesses one of its links. 302 Interfaces are identified by their interface ID, a 10-octet 303 value consisting of the 6-octet base MAC address of the 304 switch, followed by the 4-octet local port number of the 305 interface. 307 Neighboring switches 309 Two switches attached to a common link. 311 Adjacency 313 A relationship formed between selected neighboring switches 314 for the purpose of exchanging routing information. Not every 315 pair of neighboring switches become adjacent. 317 Link state advertisement 319 Describes the local state of a switch or a link. Each link 320 state advertisement is flooded throughout the switch fabric. 322 The collected link state advertisements of all switches and 323 links form the protocol's topological database. 325 Designated switch 327 Each multi-access network link has a designated switch. The 328 designated switch generates a link state advertisement for 329 the link and has other special responsibilities in the 330 running of the protocol. 332 The use of a designated switch permits a reduction in the 333 number of adjacencies required on multi-access links. This 334 in turn reduces the amount of routing protocol traffic and 335 the size of the topological database. 337 The designated switch is selected during the discovery 338 process. A designated switch is not selected for a point-to- 339 point network link. 341 Backup designated switch 343 Each multi-access network link has a backup designated 344 switch. The backup designated switch maintains adjacencies 345 with the same switches on the link as the designated switch. 346 This optimizes the failover time when the backup designated 347 switch must take over for the (failed) designated switch. 349 The backup designated switch is selected during the Discovery 350 process. A backup designated switch is not selected for a 351 point-to-point network link. 353 2.2 Differences Between VLSP and OSPF 355 The VLS protocol is derived from the OSPF link-state routing 356 protocol described in [RFC1583]. 358 2.2.1 Operation at the Physical Layer 360 The primary differences between the VLS and OSPF protocols stem 361 from the fact that OSPF runs over the IP layer, while VLSP runs 362 at the physical MAC layer. This difference has the following 363 repercussions: 365 o VLSP does not support features (such as fragmentation) that 366 are typically provided by network layer service providers. 368 o Due to the unrelated nature of MAC address assignments, VLSP 369 provides no summarization of the address space (such as, 370 classical IP subnet information) or level 2 routing (such as, 372 IS-IS Phase V DECnet). Thus, VLSP does not support grouping 373 switches into areas. All switches exist in a single area. 374 Since a single domain exists within any switch fabric, there 375 is no need for VLSP to provide interdomain reachability. 377 o As mentioned in Section 10.1.1, ISMP uses a single well-known 378 multicast address for all packets. However, parts of the VLS 379 protocol (as derived from OSPF) are dependent on certain 380 network layer addresses -- in particular, the AllSPFSwitches 381 and AllDSwitches multicast addresses that drive the 382 distribution of link state advertisements throughout the 383 switch fabric. In order to facilitate the implementation of 384 the protocol at the physical MAC layer, network layer address 385 information is encapsulated in the protocol packets (see 386 Section 10.3). This information is unbundled and packets are 387 then processed as if they had been sent or received on that 388 multicast address. 390 2.2.2 All Links Treated as Point-to-Point 392 When the switch first comes on line, VLSP assumes all network 393 links are point-to-point and no more than one neighboring switch 394 will be discovered on any one port. Therefore, at startup, VLSP 395 does not send its own Hello packets over its network ports, but 396 instead, relies on the VlanHello protocol [IDhello] for the 397 discovery of its neighbor switches. If a second neighbor is 398 detected on a link, the link is then deemed multi-access and the 399 interface type is changed to broadcast. At that point, VLSP 400 exchanges its own Hello packets with the switches on the link in 401 order to select a designated switch and designated backup switch 402 for the link. 404 This method eliminates unnecessary duplication of message 405 traffic and processing, thereby increasing the overall 406 efficiency of the switch fabric. 408 Note 410 Previous versions of VLSP treated all links as if they 411 were broadcast (multi-access). Thus, if VLSP determines 412 that a neighbor switch is running an older version of 413 the protocol software (see Section 6.1), it will change 414 the interface type to broadcast and begin exchanging 415 Hello packets with the single neighbor switch. 417 2.2.3 Routing Path Information 419 Instead of providing the next hop to a destination, VLSP 420 calculates and maintains complete end-to-end path information. 421 On request, a list of individual port identifiers is generated 422 describing a complete path from the source switch to the 423 destination switch. If multiple equal-cost routes exist to a 424 destination switch, up to three paths are calculated and 425 returned. 427 2.2.4 Configurable Parameters 429 OSPF supports (and requires) configurable parameters. In fact, 430 even the default OSPF configuration requires that IP address 431 assignments be specified. On the other hand, no configuration 432 information is ever required for the VLS protocol. Switches are 433 uniquely identified by their base MAC addresses and ports are 434 uniquely identified by the base MAC address of the switch and a 435 port number. 437 While a developer is free to implement configurable parameters 438 for the VLS protocol, the current version of VLSP supports 439 configurable path metrics only. Note that this has the 440 following repercussions: 442 o All switches are assigned a switch priority of 1. This 443 forces the selection of the designated switch to be based 444 solely on base MAC address. 446 o Authentication is not supported. 448 2.2.5 Features Not supported 450 In addition to those features mentioned in the previous 451 sections, the following OSPF features are not supported by the 452 current version of VLSP: 454 o Periodic refresh of link state advertisements. (This 455 optimizes performance by eliminating unnecessary traffic 456 between the switches.) 458 o Routing based on non-zero type of service (TOS). 460 o Use of external routing information for destinations outside 461 the switch fabric. 463 2.3 Functional Summary 465 There are essentially four operational stages of the VLS 466 protocol. 468 o Discovery Process 470 The discovery process involves two steps: 472 o Neighboring switches are detected by the VlanHello protocol 473 [IDhello] which then notifies VLSP of the neighbor. 475 o If more than one neighbor switch is detected on a single 476 port, the link is determined to be multi-access. VLSP then 477 sends its own Hello packets over the link in order to 478 discover the full set of neighbors on the link and select a 479 designated switch and designated backup switch for the 480 link. Note that this selection process is unnecessary on 481 point-to-point links. 483 The discovery process is described in more detail in Section 6. 485 o Synchronizing the Databases 487 Adjacencies are used to simplify and speed up the process 488 of synchronizing the topological database (also known as 489 the link state database) maintained by each switch in the 490 fabric. Each switch is only required to synchronize its 491 database with those neighbors to which it is adjacent. 492 This reduces the amount of routing protocol traffic across 493 the fabric, particularly for multi-access links with 494 multiple switches. 496 The process of synchronizing the databases is described in 497 more detail in Section 7. 499 o Maintaining the Databases 501 Each switch advertises its state (also known as its link 502 state) any time its link state changes. Link state 503 advertisements are distributed throughout the switch fabric 504 using a reliable flooding algorithm that ensures that all 505 switches in the fabric are notified of any link state 506 changes. 508 The process of maintaining the databases is described in 509 more detail in Section 8 511 o Calculating the Best Paths 513 The link state database consists of the collection of link 514 state advertisements received from each switch. Each 515 switch uses its link state database to calculate a set of 516 best paths, using itself as root, to all other switches in 517 the fabric. 519 The process of recalculating the set of best paths is 520 described in more detail in Section 9. 522 2.4 Protocol Packets 524 In addition to the frame header and the ISMP packet header 525 described in Section 10.1, all VLS protocol packets share a 526 common protocol header, described in Section 10.4. 528 The VLSP packet types are listed below in Table 1. Their 529 formats are described in Section 10.6. 531 Type Packet Name Protocol Function 533 1 Hello Select DS and Backup DS 534 2 Database Description Summarize database contents 535 3 Link State Request Database download 536 4 Link State Update Database update 537 5 Link State Ack Flooding acknowledgment 539 Table 1: VLSP Packet Types 541 The Hello packets are used to select the designated switch and 542 the backup designated switch on multi-access links. The 543 Database Description and Link State Request packets are used to 544 form adjacencies. Link State Update and Link State 545 Acknowledgment packets are used to update the topological 546 database. 548 Each Link State Update packet carries a set of link state 549 advertisements. A single Link State Update packet may contain 550 the link state advertisements of several switches. There are 551 two different types of link state advertisement, as shown below 552 in Table 2. 554 LS Advertisement Advertisement Description 555 Type Name 557 1 Switch link Originated by all switches. This 558 advertisements advertisement describes the collected 559 states of the switch's interfaces. 561 2 Network link Originated by the designated switch. 562 advertisements This advertisement contains the list 563 of switches connected to the network 564 link. 566 Table 2: VLSP Link State Advertisements 568 2.5 Protocol Data Structures 570 The VLS protocol is described in this specification in terms of 571 its operation on various protocol data structures. Table 3 572 lists the primary VLSP data structures, along with the section 573 in which they are described in detail. 575 Structure Name Description 577 Interface Data Structure Section 3 578 Neighbor Data Structure Section 4 579 Area Data Structure Section 5 581 Table 3: VLSP Data Structures 583 2.6 Basic Implementation Requirements 585 An implementation of the VLS protocol requires the following 586 pieces of system support: 588 Timers 590 Two types of timer are required. The first type, known as a 591 one-shot timer, expires once and triggers an event. The 592 second type, known as an interval timer, expires at preset 593 intervals. Interval timers are used to trigger events at 594 periodic intervals. The granularity of both types of timers 595 is one second. 597 Interval timers should be implemented in such a way as to 598 avoid drift. In some switch implementations, packet 599 processing can affect timer execution. For example, on a 600 multi-access link with multiple switches, regular broadcasts 601 can lead to undesirable synchronization of routing packets 602 unless the interval timers have been implemented to avoid 604 drift. If it is not possible to implement drift-free timers, 605 small random amounts of time should be added to or subtracted 606 from the timer interval at each firing. 608 List manipulation primitives 610 Much of the functionality of VLSP is described here in terms 611 of its operation on lists of link state advertisements. Any 612 particular advertisement may be on many such lists. 613 Implementation of VLSP must be able to manipulate these 614 lists, adding and deleting constituent advertisements as 615 necessary. 617 Tasking support 619 Certain procedures described in this specification invoke 620 other procedures. At times, these other procedures should be 621 executed in-line -- that is, before the current procedure has 622 finished. This is indicated in the text by instructions to 623 "execute" a procedure. At other times, the other procedures 624 are to be executed only when the current procedure has 625 finished. This is indicated by instructions to "schedule" a 626 task. Implementation of VLSP must provide these two types of 627 tasking support. 629 2.7 Organization of the Remainder of This Document 631 The remainder of this document is organized as follows: 633 o Section 3 through Section 5 describe the primary data 634 structures used by the protocol. Note that this specification 635 is presented in terms of these data structures in order to make 636 explanations more precise. Implementations of the protocol 637 must support the functionality described, but need not use the 638 exact data structures that appear in this specification. 640 o Section 6 through Section 9 describe the four operational 641 stages of the protocol: the discovery process, synchronizing 642 the databases, maintaining the databases, and calculating the 643 set of best paths. 645 o Section 10 describes the processing of VLSP packets and 646 presents detailed descriptions of their formats. 648 o Section 11 presents detailed descriptions of link state 649 advertisements. 651 o Section 12 summarizes the protocol parameters. 653 3. Interface Data Structure 655 The port over which a switch accesses a network link is known as 656 the link interface. Each switch maintains a separate interface 657 data structure for each network link. 659 The following data items are associated with each interface: 661 Type 663 The type of network to which the interface is attached -- 664 point-to-point or broadcast (multi-access). This data item 665 is initialized to point-to-point when the interface becomes 666 operational. If a second neighbor is detected on the link 667 after the first neighbor has been discovered, the link 668 interface type is changed to broadcast. The type remains as 669 broadcast until the interface is declared down, at which time 670 the type reverts to point-to-point. 672 Note 674 Previous versions of VLSP treated all links as if they 675 were multi-access. Thus, if VLSP determines that a 676 neighbor switch is running an older version of the 677 protocol software (see Section 6.1), it will change 678 the interface type to broadcast. 680 State 682 The functional level of the interface. The state of the 683 interface is included in all switch link advertisements 684 generated by the switch, and is also used to determine 685 whether full adjacencies are allowed on the interface. See 686 Section 3.1 for a complete description of interface states. 688 Interface identifier 690 A 10-octet value that uniquely identifies the interface. 691 This value consists of the 6-octet base MAC address of the 692 neighbor switch, followed by the 4-octet local port number of 693 the interface. 695 Area ID 697 A 4-octet value identifying the area. Since VLSP does not 698 support multiple areas, the value here is always zero. 700 HelloInterval 702 The interval, in seconds, at which the switch sends VLSP 703 Hello packets over the interface. This parameter is not used 704 on point-to-point links. 706 SwitchDeadInterval 708 The length of time, in seconds, that neighboring switches 709 will wait before declaring the local switch down once they 710 stop receiving VLSP Hello packets from the local switch. 711 This parameter is not used on point-to-point links. 713 InfTransDelay 715 The estimated number of seconds it should take to transmit a 716 Link State Update packet over this interface. Link state 717 advertisements contained in the update packet will have their 718 age incremented by this amount before transmission. This 719 value must be greater than zero and must take into account 720 transmission and propagation delays. 722 Switch priority 724 An 8-bit unsigned integer. When two switches attached to the 725 same multi-access network link contend for selection as the 726 designated switch, the switch with the highest priority takes 727 precedence. If both switches have the same priority, the 728 switch with the highest base MAC address becomes the 729 designated switch. A switch whose switch priority is set to 730 zero is ineligible to become the designated switch on the 731 attached link. This parameter is not used on point-to-point 732 links. 734 Hello timer 736 The interval timer used to regulate the transmission of VLSP 737 Hello packets over the interface. This timer expires every 738 HelloInterval seconds. This timer is not used on point-to- 739 point links. 741 Wait timer 743 The one-shot timer used to time the Waiting state. When this 744 timer expires, the interface exits the Waiting state and 745 begins selection of the designated switch on the link. The 746 length of the timer is SwitchDeadInterval seconds. This 747 timer is not used on point-to-point links. 749 Neighboring switches 751 A list of the neighboring switches attached to this network 752 link. This list is created during the discovery process. 753 Adjacencies are formed to one or more of these neighbors. 754 The set of adjacent neighbors can be determined by examining 755 the states of the neighboring switches as shown in their link 756 state advertisements. 758 Designated switch 760 The designated switch selected for the multi-access network 761 link. (A designated switch is not selected for a point-to- 762 point link.) This data item is initialized to zero when the 763 switch comes on-line, indicating that no designated switch 764 has been chosen for the link. 766 Backup designated switch 768 The backup designated switch selected for the multi-access 769 network link. (A backup designated switch is not selected 770 for a point-to-point link.) This data item is initialized to 771 zero when the switch comes on-line, indicating that no backup 772 designated switch has been chosen for the link. 774 Interface output cost(s) 776 The cost of sending a packet over the interface. The link 777 cost is expressed in the link state metric and must be 778 greater than zero. 780 RxmtInterval 782 The number of seconds between link state advertisement 783 retransmissions, for adjacencies belonging to this interface. 784 This value is also used to time the retransmission of 785 Database Description and Link State Request packets. 787 3.1 Interface States 789 This section describes the various states of a switch interface. 790 The states are listed in order of progressing functionality. 791 For example, the inoperative state is listed first, followed by 792 a list of the intermediate states through which the interface 793 passes before attaining the final, fully functional state. The 794 specification makes use of this ordering by references such as 795 "those interfaces in state greater than X". 797 Figure 1 represents the interface state machine, showing the 798 progression of interface state changes. The arrows on the graph 800 represent the events causing each state change. These events 801 are described in Section 3.2. The interface state machine is 802 described in detail in Section 3.3. 804 Down 806 This is the initial state of the interface. In this state, 807 the interface is unusable, and no protocol traffic is sent or 808 received on the interface. In this state, interface 809 parameters are set to their initial values, all interface 810 timers are disabled, and no adjacencies are associated with 811 the interface. 813 +-------+ 814 | any | Interface +----------+ Unloop Ind +----------+ 815 | state | -----------> | Down | <----------- | Loopback | 816 +-------+ Down +----------+ +----------+ 817 | ^ 818 | Interface Up | 819 +-------+ [pt-to-pt] | | 820 | Point |<------------type? Loop Ind | 821 | to | | | 822 | Point | | [broadcast] | 823 +-------+ V +-------+ 824 +-----------+ | any | 825 | Waiting | | state | 826 +-----------+ +-------+ 827 | 828 Backup Seen | 829 | Wait Timer 830 | 831 | 832 +----------+ Neighbor V Neighbor +----------+ 833 | DS | <------------> [ ] <------------> | DS Other | 834 +----------+ Change ^ Change +----------+ 835 | 836 | 837 Neighbor Change | 838 | 839 V 840 +----------+ 841 | Backup | 842 +----------+ 844 Figure 1: Interface State Machine 846 Loopback 848 In this state, the switch interface is looped back, either in 849 hardware or in software. The interface is unavailable for 850 regular data traffic. 852 Point-to-Point 854 In this state, the interface is operational and is connected 855 to a physical point-to-point link. On entering this state, 856 the switch attempts to form an adjacency with the neighboring 857 switch. 859 Waiting 861 In this state, the switch is attempting to identify the 862 backup designated switch for the link by monitoring the Hello 863 packets it receives. The switch does not attempt to select a 864 designated switch or a backup designated switch until it 865 changes out of this state, thereby preventing unnecessary 866 changes of the designated switch and its backup. 868 DS Other 870 In this state, the interface is operational and is connected 871 to a multi-access broadcast link on which other switches have 872 been selected as the designated switch and the backup 873 designated switch. On entering this state, the switch 874 attempts to form adjacencies with both the designated switch 875 and the backup designated switch. 877 Backup 879 In this state, the switch itself is the backup designated 880 switch on the attached multi-access broadcast link. It will 881 be promoted to designated switch if the current designated 882 switch fails. The switch establishes adjacencies with all 883 other switches attached to the link. (See Section 6.3 for 884 more information on the functions performed by the backup 885 designated switch.) 887 DS 889 In this state, this switch itself is the designated switch on 890 the attached multi-access broadcast link. The switch 891 establishes adjacencies with all other switches attached to 892 the link. The switch is responsible for originating network 893 link advertisements for the link, containing link information 894 for all switches attached to the link, including the designated 895 switch itself. (See Section 6.3 for more information on the 896 functions performed by the designated switch.) 898 3.2 Events Causing Interface State Changes 900 The state of an interface changes due to an interface event. 901 This section describes these events. 903 Interface events are shown as arrows in Figure 1, the graphic 904 representation of the interface state machine. For more 905 information on the interface state machine, see Section 3.3. 907 Interface Up 909 This event is generated by the VlanHello protocol [IDhello] 910 when it discovers a neighbor switch on the interface. The 911 interface is now operational. This event causes the 912 interface to change out of the Down state. The state it 913 enters is determined by the interface type. If the interface 914 type is broadcast (multi-access), this event also causes the 915 switch to begin sending periodic Hello packets out over the 916 interface. 918 Wait Timer 920 This event is generated when the one-shot Wait timer expires, 921 triggering the end of the required waiting period before the 922 switch can begin the process of selecting a designated switch 923 and a backup designated switch on a multi-access link. 925 Backup Seen 927 This event is generated when the switch has detected the 928 existence or non-existence of a backup designated switch for 929 the link, as determined in one of the following two ways: 931 o A Hello packet has been received from a neighbor that 932 claims to be the backup designated switch. 934 o A Hello packet has been received from a neighbor that 935 claims to be the designated switch. In addition, the 936 packet indicated that there is no backup. 938 In either case, the interface must have bidirectional 939 communication with its neighbor -- that is, the local switch 940 must be listed in the neighbor's Hello packet. 942 This event signals the end of the Waiting state. 944 Neighbor change 946 This event is generated when there has been one of the 947 following changes in the set of bidirectional neighbors 949 associated with the interface. (See Section 4.1 for 950 information on neighbor states.) 952 o Bidirectional communication has been established with a 953 neighbor -- the state of the neighbor has changed to 2-Way 954 or higher. 956 o Bidirectional communication with a neighbor has been lost 957 -- the state of the neighbor has changed to Init or lower. 959 o A bidirectional neighbor has just declared itself to be 960 either the designated switch or the backup designated 961 switch, as detected by examination of that neighbor's Hello 962 packets. 964 o A bidirectional neighbor is no longer declaring itself to 965 be either the designated switch or the backup designated 966 switch, as detected by examination of that neighbor's Hello 967 packets. 969 o The advertised switch priority of a bidirectional neighbor 970 has changed, as detected by examination of that neighbor's 971 Hello packets. 973 When this event occurs, the designated switch and the backup 974 designated switch must be reselected. 976 Loop Ind 978 This event is generated when an interface enters the Loopback 979 state. This event can be generated by either the network 980 management service or by the lower-level protocols. 982 Unloop Ind 984 This event is generated when an interface leaves the Loopback 985 state. This event can be generated by either the network 986 management service or by the lower-level protocols. 988 Interface Down 990 This event is generated under the following two 991 circumstances: 993 o The VlanHello [IDhello] protocol has determined that the 994 interface is no longer functional. 996 o The neighbor state machine has detected a second 997 neighboring switch on a link presumed to be of type point- 999 to-point. In addition to generating the Interface Down 1000 event, the neighbor state machine changes the interface 1001 type to broadcast. 1003 In both instances, this event forces the interface state to 1004 Down. However, when the event is generated by the neighbor 1005 state machine, it is immediately followed by an Interface Up 1006 event. (See Section 4.3.) 1008 3.3 Interface State Machine 1010 This section presents a detailed description of the interface 1011 state machine. 1013 Interface states (see Section 3.1) change as the result of 1014 various events (see Section 3.2). However, the effect of each 1015 event can vary, depending on the current state of the interface. 1016 For this reason, the state machine described in this section is 1017 organized according to the current interface state and the 1018 occurring event. For each state/event pair, the new interface 1019 state is listed, along with a description of the required 1020 processing. 1022 Note that when the state of an interface changes, it may be 1023 necessary to originate a new switch link advertisement. See 1024 Section 8.1 for more information. 1026 Some of the processing described here includes generating events 1027 for the neighbor state machine. For example, when an interface 1028 becomes inoperative, all neighbor connections associated with 1029 the interface must be destroyed. For more information on the 1030 neighbor state machine, see Section 4.3. 1032 State(s): Down 1033 Event: Interface Up 1034 New state: Depends on action routine 1035 Action: 1036 If the interface is a point-to-point link, set the interface 1037 state to Point-to-Point. Otherwise, start the Hello interval 1038 timer, enabling the periodic sending of Hello packets over 1039 the interface. If the switch is not eligible to become the 1040 designated switch, change the interface state to DS Other. 1041 Otherwise, set the interface state to Waiting and start the 1042 one-shot wait timer. Create a new neighbor data structure 1043 for the neighbor switch, initialize all neighbor parameters 1044 and set the stateof the neighbor to Down. 1046 State(s): Waiting 1047 Event: Backup Seen 1048 New state: Depends on action routine 1049 Action: 1050 Select the designated switch and backup designated switch for 1051 the attached link, as described in Section 6.3.1. As a 1052 result of this selection, set the new state of the interface 1053 to either DS Other, Backup or DS. 1055 State(s): Waiting 1056 Event: Wait Timer 1057 New state: Depends on action routine 1058 Action: 1059 Select the designated switch and backup designated switch for 1060 the attached link, as described in Section 6.3.1. As a 1061 result of this selection, set the new state of the interface 1062 to either DS Other, Backup or DS. 1064 State(s): DS Other, Backup or DS 1065 Event: Neighbor Change 1066 New state: Depends on action routine 1067 Action: 1068 Reselect the designated switch and backup designated switch 1069 for the attached link, as described in Section 6.3.1. As a 1070 result of this selection, set the new state of the interface 1071 to either DS Other, Backup or DS. 1073 State(s): Any State 1074 Event: Interface Down 1075 New state: Down 1076 Action: 1077 Reset all variables in the interface data structure and 1078 disable all timers. In addition, destroy all neighbor 1079 connections associated with the interface by generating the 1080 KillNbr event on all neighbors listed in the interface data 1081 structure. 1083 State(s): Any State 1084 Event: Loop Ind 1085 New state: Loopback 1086 Action: 1087 Reset all variables in the interface data structure and 1088 disable all timers. In addition, destroy all neighbor 1089 connections associated with the interface by generating the 1090 KillNbr event on all neighbors listed in the interface data 1091 structure. 1093 State(s): Loopback 1094 Event: Unloop Ind 1095 New state: Down 1096 Action: 1097 No action is necessary beyond changing the interface state to 1098 Down because the interface was reset on entering the Loopback 1099 state. 1101 4. Neighbor Data Structure 1103 Each switch conducts a conversation with its neighboring 1104 switches and each conversation is described by a neighbor data 1105 structure. A conversation is associated with a switch 1106 interface, and is identified by the neighboring switch ID. 1108 Note that if two switches have multiple attached links in 1109 common, multiple conversations ensue, each described by a unique 1110 neighbor data structure. Each separate conversation is treated 1111 as a separate neighbor. 1113 The neighbor data structure contains all information relevant to 1114 any adjacency formed between the two neighbors. Remember, 1115 however, that not all neighbors become adjacent. An adjacency 1116 can be thought of as a highly developed conversation between two 1117 switches. 1119 State 1121 The functional level of the neighbor conversation. See 1122 Section 4.1 for a complete description of neighbor states. 1124 Inactivity timer 1126 A one-shot timer used to determine when to declare the 1127 neighbor down if no Hello packet is received from this 1128 (multi-access) neighbor. The length of the timer is 1129 SwitchDeadInterval seconds, as contained in the neighbor's 1130 Hello packet. This timer is not used on point-to-point 1131 links. 1133 Master/slave flag 1135 A flag indicating whether the local switch is to act as the 1136 master or the slave in the database exchange process (see 1137 Section 7.2). The master/slave relationship is negotiated 1138 when the conversation changes to the ExStart state. 1140 Sequence number 1142 A 4-octet number identifying individual Database Description 1143 packets. When the neighbor state ExStart is entered and the 1144 database exchange process is started, the sequence number is 1145 set to a value not previously seen by the neighboring switch. 1146 (One possible scheme is to use the switch's time of day 1147 counter.) The sequence number is then incremented by the 1148 master with each new Database Description packet sent. See 1149 Section 7.2 for more information on the database exchange 1150 process. 1152 Neighbor ID 1154 The switch ID of the neighboring switch, as discovered by the 1155 VlanHello protocol [IDhello] or contained in the neighbor's 1156 Hello packets. 1158 Neighbor priority 1160 The switch priority of the neighboring switch, as contained 1161 in the neighbor's Hello packets. Switch priorities are used 1162 when selecting the designated switch for the attached multi- 1163 access link. Priority is not used on point-to-point links. 1165 Interface identifier 1167 A 10-octet value that uniquely identifies the interface over 1168 which this conversation is being held. This value consists 1169 of the 6-octet base MAC address of the neighbor switch, 1170 followed by the 4-octet local port number of the interface. 1172 Neighbor's designated switch 1174 The switch ID identifying the neighbor's idea of the 1175 designated switch, as contained in the neighbor's Hello 1176 packets. This value is used in the local selection of the 1177 designated switch. It is not used on point-to-point links. 1179 Neighbor's backup designated switch 1181 The switch ID identifying the neighbor's idea of the backup 1182 designated switch, as contained in the neighbor's Hello 1183 packets. This value is used in the local selection of the 1184 backup designated switch. It is not used on point-to-point 1185 links. 1187 Link state retransmission list 1189 The list of link state advertisements that have been 1190 forwarded over but not acknowledged on this adjacency. The 1192 local switch retransmits these link state advertisements at 1193 periodic intervals until they are acknowledged or until the 1194 adjacency is destroyed. (For more information on 1195 retransmitting link state advertisements, see Section 8.2.5.) 1197 Database summary list 1199 The set of link state advertisement headers that summarize 1200 the local link state database. When the conversation changes 1201 to the Exchange state, this list is sent to the neighbor via 1202 Database Description packets. (For more information on the 1203 synchronization of databases, see Section 7.) 1205 Link state request list 1207 The list of link state advertisements that must be received 1208 in order to synchronize with the neighbor switch's link state 1209 database. This list is created as Database Description 1210 packets are received, and is then sent to the neighbor in 1211 Link State Request packets. (For more information on the 1212 synchronization of databases, see Section 7.) 1214 4.1 Neighbor States 1216 This section describes the various states of a conversation with 1217 a neighbor switch. The states are listed in order of 1218 progressing functionality. For example, the inoperative state 1219 is listed first, followed by a list of the intermediate states 1220 through which the conversation passes before attaining the 1221 final, fully functional state. The specification makes use of 1222 this ordering by references such as "those neighbors/adjacencies 1223 in state greater than X". 1225 Figure 2 represents the neighbor state machine. The arrows on 1226 the graph represent the events causing each state change. These 1227 events are described in Section 4.2. The neighbor state machine 1228 is described in detail in Section 4.3. 1230 Down 1232 This is the initial state of a neighbor conversation. 1234 Init 1236 In this state, the neighbor has been discovered, but 1237 bidirectional communication has not yet been established. 1238 All neighbors in this state or higher are listed in the VLS 1239 Hello packets sent by the local switch over the associated 1240 (multi-access) interface. 1242 +----------+ KillNbr, LLDown, +-----------+ 1243 | Down | <--------------------- | any state | 1244 +----------+ or Inactivity Timer +-----------+ 1245 | 1246 Hello | 1247 Rcvd | 1248 | 1249 V 1250 +-----< [pt-to-pt?] 1251 | yes | 1252 | | no 1253 | V 1254 | +----------+ 1-Way +----------+ 1255 | | Init | <-------- | >= 2-way | 1256 | +----------+ +----------+ 1257 | | 1258 | 2-Way | 1259 | Rcvd | +-------+ AdjOK? +------------+ 1260 | +----------------> | 2-Way | <------- | >= ExStart | 1261 | | (no adjacency) +-------+ no +------------+ 1262 | | 1263 | V 1264 | +---------+ Seq Number Mismatch +-------------+ 1265 +----> | ExStart | <--------------------- | >= Exchange | 1266 +---------+ or BadLSReq +-------------+ 1267 | 1268 Negotiation | 1269 Done | 1270 V 1271 +----------+ 1272 | Exchange | 1273 +----------+ 1274 | 1275 Exchange | +--------+ 1276 Done +----------------------> | Full | 1277 | (request list empty) +--------+ 1278 | ^ 1279 V | 1280 +---------+ Loading Done | 1281 | Loading | -----------------------> 1282 +---------+ 1284 Figure 2: Neighbor State Machine 1286 2-Way 1288 In this state, communication between the two switches is 1289 bidirectional. This is the most advanced state short of 1290 beginning to establish an adjacency. On a multi-access link, 1292 the designated switch and the backup designated switch are 1293 selected from the set of neighbors in state 2-Way or greater. 1295 ExStart 1297 This state indicates that the two switches have begun to 1298 establish an adjacency by determining which switch is the 1299 master, as well as the initial sequence number for Database 1300 Descriptor packets. Neighbor conversations in this state or 1301 greater are called adjacencies. 1303 Exchange 1305 In this state, the switches are exchanging Database 1306 Description packets. (See Section 7.2 for a complete 1307 description of this process.) All adjacencies in the 1308 Exchange state or greater are used by the distribution 1309 procedure (see Section 8.2), and are capable of transmitting 1310 and receiving all types of VLSP routing packets. 1312 Loading 1314 In this state, the local switch is sending Link State Request 1315 packets to the neighbor asking for the more recent 1316 advertisements that were discovered in the Exchange state. 1318 Full 1320 In this state, the two switches are fully adjacent. These 1321 adjacencies will now appear in switch link and network link 1322 advertisements generated for the link. 1324 4.2 Events Causing Neighbor State Changes 1326 The state of a neighbor conversation changes due to neighbor 1327 events. This section describes these events. 1329 Neighbor events are shown as arrows in Figure 2, the graphic 1330 representation of the neighbor state machine. For more 1331 information on the neighbor state machine, see Section 4.3. 1333 Hello Received 1335 This event is generated when a Hello packet has been received 1336 from a neighbor. 1338 2-Way Received 1340 This event is generated when the local switch sees its own 1341 switch ID listed in the neighbor's Hello packet, indicating 1343 that bidirectional communication has been established between 1344 the two switches. 1346 Negotiation Done 1348 This event is generated when the master/slave relationship 1349 has been successfully negotiated and initial packet sequence 1350 numbers have been exchanged. This event signals the start of 1351 the database exchange process (see Section 7.2). 1353 Exchange Done 1355 This event is generated when the database exchange process is 1356 complete and both switches have successfully transmitted a 1357 full sequence of Database Description packets. (For more 1358 information on the database exchange process, see Section 7.2.) 1360 BadLSReq 1362 This event is generated when a Link State Request has been 1363 received for a link state advertisement that is not contained 1364 in the database. This event indicates an error in the 1365 synchronization process. 1367 Loading Done 1369 This event is generated when all Link State Updates have been 1370 received for all out-of-date portions of the database. (See 1371 Section 7.3.) 1373 AdjOK? 1375 This event is generated when a decision must be made as to 1376 whether an adjacency will be established or maintained with 1377 the neighbor. This event will initiate some adjacencies and 1378 destroy others. 1380 Seq Number Mismatch 1382 This event is generated when a Database Description packet 1383 has been received with any of the following conditions: 1385 o The packet contains an unexpected sequence number. 1386 o The packet (unexpectedly) has the Init bit set. 1387 o The packet has a different Options field than was 1388 previously seen. 1390 These conditions all indicate that an error has occurred 1391 during the establishment of the adjacency. 1393 1-Way 1395 This event is generated when bidirectional communication with 1396 the neighbor has been lost. That is, a Hello packet has been 1397 received from the neighbor in which the local switch is not 1398 listed. 1400 KillNbr 1402 This event is generated when further communication with the 1403 neighbor is impossible. 1405 Inactivity Timer 1407 This event is generated when the inactivity timer has 1408 expired, indicating that no Hello packets have been received 1409 from the neighbor in SwitchDeadInterval seconds. This timer 1410 is used only on broadcast (multi-access) links. 1412 LLDown 1414 This event is generated by the lower-level switch discovery 1415 protocols and indicates that the neighbor is now unreachable. 1417 4.3 Neighbor State Machine 1419 This section presents a detailed description of the neighbor 1420 state machine. 1422 Neighbor states (see Section 4.1) change as the result of 1423 various events (see Section 4.2). However, the effect of each 1424 event can vary, depending on the current state of the 1425 conversation with the neighbor. For this reason, the state 1426 machine described in this section is organized according to the 1427 current neighbor state and the occurring event. For each 1428 state/event pair, the new neighbor state is listed, along with a 1429 description of the required processing. 1431 Note that when the neighbor state changes as a result of an 1432 interface Neighbor Change event (see Section 3.2), it may be 1433 necessary to rerun the designated switch selection algorithm. 1434 In addition, if the interface associated with the neighbor 1435 conversation is in the DS state (that is, the local switch is 1436 the designated switch), changes in the neighbor state may cause 1437 a new network link advertisement to be originated (see Section 1438 8.1). 1440 When the neighbor state machine must invoke the interface state 1441 machine, it is invoked as a scheduled task. This simplifies 1443 processing, by ensuring that neither state machine executes 1444 recursively. 1446 State(s): Down 1447 Event: Hello Received 1448 New state: Depends on the interface type 1449 Action: 1450 If the interface type of the associated link is point-to- 1451 point, change the neighbor state to ExStart. Otherwise, 1452 change the neighbor state to Init and start the inactivity 1453 timer for the neighbor. If the timer expires before another 1454 Hello packet is received, the neighbor switch is declared 1455 dead. 1457 State(s): Init or greater 1458 Event: Hello Received 1459 New state: No state change 1460 Action: 1461 If the interface type of the associated link is point-to- 1462 point, determine whether this notification is for a different 1463 neighbor than the one previously seen. If so, generate an 1464 Interface Down event for the associated interface, reset the 1465 interface type to broadcast and generate an Interface Up 1466 event. 1468 Note 1470 This procedure of generating an Interface Down event 1471 and changing the interface type to broadcast is also 1472 executed if the neighbor for whom the notification was 1473 received is running an older version of the protocol 1474 software (see Section 6.1). In previous versions of 1475 the protocol, all interfaces were treated as if they 1476 were broadcast. 1478 If the interface type is broadcast, reset the inactivity 1479 timer for the neighbor. 1481 State(s): Init 1482 Event: 2-Way Received 1483 New state: Depends on action routine 1484 Action: 1485 Determine whether an adjacency will be formed with the 1486 neighbor (see Section 6.4). If no adjacency is to be formed, 1487 change the neighbor state to 2-Way. 1489 Otherwise, change the neighbor state to ExStart. Initialize 1490 the sequence number for this neighbor and declare the local 1491 switch to be master for the database exchange process. (See 1492 Section 7.2.) 1494 State(s): ExStart 1495 Event: Negotiation Done 1496 New state: Exchange 1497 Action: 1498 The Negotiation Done event signals the start of the database 1499 exchange process. See Section 7.2 for a detailed description 1500 of this process. 1502 State(s): Exchange 1503 Event: Exchange Done 1504 New state: Depends on action routine 1505 Action: 1506 If the neighbor Link state request list is empty, change the 1507 neighbor state to Full. This is the adjacency's final state. 1509 Otherwise, change the neighbor state to Loading. Begin 1510 sending Link State Request packets to the neighbor requesting 1511 the most recent link state advertisements, as discovered 1512 during the database exchange process. (See Section 7.2.) 1513 These advertisements are listed in the link state request 1514 list associated with the neighbor. 1516 State(s): Loading 1517 Event: Loading Done 1518 New state: Full 1519 Action: 1520 No action is required beyond changing the neighbor state to 1521 Full. This is the adjacency's final state. 1523 State(s): 2-Way 1524 Event: AdjOK? 1525 New state: Depends on action routine 1526 Action: 1527 If no adjacency is to be formed with the neighboring switch 1528 (see Section 6.4), retain the neighbor state at 2-Way. 1529 Otherwise, change the neighbor state to ExStart. Initialize 1530 the sequence number for this neighbor and declare the local 1531 switch to be master for the database exchange process. (See 1532 Section 7.2.) 1534 State(s): ExStart or greater 1535 Event: AdjOK? 1536 New state: Depends on action routine 1537 Action: 1538 If an adjacency should still be formed with the neighboring 1539 switch (see Section 6.4), no state change and no further 1540 action is necessary. Otherwise, tear down the (possibly 1541 partially formed) adjacency. Clear the link state 1542 retransmission list, database summary list and link state 1543 request list and change the neighbor state to 2-Way. 1545 State(s): Exchange or greater 1546 Event: Seq Number Mismatch 1547 New state: ExStart 1548 Action: 1549 Tear down the (possibly partially formed) adjacency. Clear 1550 the link state retransmission list, database summary list and 1551 link state request list. Change the neighbor state to 1552 ExStart and make another attempt to establish the adjacency. 1554 State(s): Exchange or greater 1555 Event: BadLSReq 1556 New state: ExStart 1557 Action: 1558 Tear down the (possibly partially formed) adjacency. Clear 1559 the link state retransmission list, database summary list and 1560 link state request list. Change the neighbor state to 1561 ExStart and make another attempt to establish the adjacency. 1563 State(s): Any state 1564 Event: KillNbr 1565 New state: Down 1566 Action: 1567 Terminate the neighbor conversation. Disable the inactivity 1568 timer and clear the link state retransmission list, database 1569 summary list and link state request list. 1571 State(s): Any state 1572 Event: LLDown 1573 New state: Down 1574 Action: 1575 Terminate the neighbor conversation. Disable the inactivity 1576 timer and clear the link state retransmission list, database 1577 summary list and link state request list. 1579 State(s): Any state 1580 Event: Inactivity Timer 1581 New state: Down 1582 Action: 1583 Terminate the neighbor conversation. Disable the inactivity 1584 timer and clear the link state retransmission list, database 1585 summary list and link state request list. 1587 State(s): 2-Way or greater 1588 Event: 1-Way Received 1589 New state: Init 1590 Action: 1591 Tear down the adjacency between the switches, if any. Clear 1592 the link state retransmission list, database summary list and 1593 link state request list. 1595 State(s): 2-Way or greater 1596 Event: 2-Way received 1597 New state: No state change 1598 Action: 1599 No action required. 1601 State(s): Init 1602 Event: 1-Way received 1603 New state: No state change 1604 Action: 1605 No action required. 1607 5. Area Data Structure 1609 The area data structure contains all the information needed to 1610 run the basic routing algorithm. One of its components is the 1611 link state database -- the collection of all switch link and 1612 network link advertisements generated by the switches. 1614 The area data structure contains the following items: 1616 Area ID 1618 A 4-octet value identifying the area. Since VLSP does not 1619 support multiple areas, the value here is always zero. 1621 Associated switch interfaces 1623 A list of interface IDs of the local switch interfaces 1624 connected to network links. 1626 Link state database 1628 The collection of all current link state advertisements for 1629 the switch fabric. This collection consists of the 1630 following: 1632 Switch link advertisements 1634 A list of the switch link advertisements for all switches 1635 in the fabric. Switch link advertisements describe the 1636 state of each switch's interfaces. 1638 Network link advertisements 1640 A list of the network link advertisements for all multi- 1641 access network links in the switch fabric. Network link 1642 advertisements describe the set of switches currently 1643 connected to each link. 1645 Best path(s) 1647 A set of end-to-end hop descriptions for all equal-cost best 1648 paths from the local switch to every other switch in the 1649 fabric. Each hop is specified by the interface ID of the 1650 next link in the path. Best paths are derived from the 1651 collected switch link and network link advertisements using 1652 the Dijkstra algorithm. [Perlman] 1654 5.1 Adding and Deleting Link State Advertisements 1656 The link state database within the area data structure must 1657 contain, at most, a single instance of each link state 1658 advertisement. To keep the database current, a switch adds link 1659 state advertisements to the database under the following 1660 conditions: 1662 o When a link state advertisement is received during the 1663 distribution process 1665 o When the switch itself generates a link state advertisement 1667 (See Section 8.2.4 for information on installing link state 1668 advertisements.) 1670 Likewise, a switch deletes link state advertisements from the 1671 database under the following conditions: 1673 o When a link state advertisement has been superseded by a 1674 newer instance during the flooding process 1676 o When the switch generates a newer instance of one of its 1677 self-originated advertisements 1679 Note that when an advertisement is deleted from the link state 1680 database, it must also be removed from the link state 1681 retransmission list of all neighboring switches. 1683 5.2 Accessing Link State Advertisements 1685 An implementation of the VLS protocol must provide access to 1686 individual link state advertisements, based on the 1687 advertisement's type, link state identifier, and advertising 1688 switch.[1] This lookup function is invoked during the link 1689 state distribution procedure and during calculation of the set 1690 of best paths. In addition, a switch can use the function to 1691 determine whether it has originated a particular link state 1692 advertisement, and if so, with what sequence number. 1694 5.3 Best Path Lookup 1696 An implementation of the VLS protocol must provide access to 1697 multiple equal-cost best paths, based on the base MAC addresses 1698 of the source and destination switches. This lookup function 1699 should return up to three equal-cost paths. Paths should be 1700 returned as lists of end-to-end hop information, with each hop 1701 specified as a interface ID of the next link in the path -- the 1702 6-octet base MAC address of the next switch and the 4-octet 1703 local port number of the link interface. 1705 6. Discovery Process 1707 The first operational stage of the VLS protocol is the discovery 1708 process. During this stage, each switch dynamically detects its 1709 neighboring switches and establishes a relationship with each of 1710 these neighbors. This process has the following component 1711 steps: 1713 o Neighboring switches are detected on each functioning network 1714 interface. 1716 o Bidirectional communication is established with each neighbor 1717 switch. 1719 o A designated switch and backup designated switch are selected 1720 for each multi-access network link. 1722 o An adjacent relationship is established with selected 1723 neighbors on each link. 1725 6.1 Neighbor Discovery 1727 When the switch first comes on line, VLSP assumes all network 1728 links are point-to-point and no more than one neighboring switch 1729 will be discovered on any one port. Therefore, at startup, VLSP 1730 relies on the VlanHello protocol [IDhello] for the discovery of 1731 its neighbor switches. 1733 As each neighbor is detected, VlanHello triggers a Found 1734 Neighbor event, notifying VLSP that a new neighbor has been 1735 discovered. (See [IDhello] for a description of the Found 1736 Neighbor event and the information passed.) VLSP enters the 1737 neighbor switch ID in the list of known neighbors and creates a 1738 new neighbor data structure with a neighbor status of Down. A 1739 Hello Received neighbor event is then generated, which changes 1740 the neighbor state to ExStart. 1742 There are two circumstances under which VLSP will change the 1743 type of an interface to broadcast: 1745 o If VLSP receives a subsequent notification from VlanHello, 1746 specifying a second (different) neighbor switch on the port., 1747 the interface is then known to be multi-access. VLSP 1748 generates an Interface Down event for the interface, resets 1749 the interface type to broadcast, and then generates an 1750 Interface Up event. 1752 o If the functional level of the neighbor switch is less than 1753 2, the neighbor is running a previous version of the VLSP 1754 software in which all links were treated as broadcast links. 1755 VLSP immediately changes the interface type to broadcast and 1756 generates an Interface Up event. 1758 In both cases, VLSP assumes control of communication over the 1759 interface by exchanging its own VLSP Hello packets with the 1760 neighbors on the link. 1762 Note 1764 These Hello packets are in addition to the Interswitch 1765 Keepalive messages sent by VlanHello. VlanHello still 1766 continues to monitor the condition of the interface 1767 and notifies VLSP of any change. 1769 Each Hello packet contains the following data used during the 1770 discovery process on multi-access links: 1772 o The switch ID and priority of the sending switch 1774 o Values specifying the interval timers to be used for sending 1775 Hello packets and deciding whether to declare a neighbor 1776 switch Down. 1778 o The switch ID of the designated switch and the backup 1779 designated switch for the link, as understood by the sending 1780 switch 1782 o A list of switch IDs of all neighboring switches seen so far 1783 on the link 1785 For a detailed description of the Hello packet format, see 1786 Section 10.6.1. 1788 When VLSP receives a Hello packet (on a broadcast link), it 1789 first attempts to identify the sending switch by matching its 1790 switch ID to one of the known neighbors listed in the interface 1791 data structure. If this is the first Hello packet received from 1792 the switch, the switch ID is entered in the list of known 1794 neighbors and a new neighbor data structure is created with a 1795 neighbor status of Down. 1797 At this point, the remainder of the Hello packet is examined and 1798 the appropriate interface and neighbor events are generated. In 1799 all cases, a neighbor Hello Received event is generated. Other 1800 events may also be generated, triggering further steps in the 1801 discovery process or other actions, as appropriate. 1803 For a detailed description of the interface state machine, see 1804 Section 3.3. For a detailed description of the neighbor state 1805 machine, see Section 4.3. 1807 6.2 Bidirectional Communication 1809 Before a conversation can proceed with a neighbor switch, 1810 bidirectional communication must be established with that 1811 neighbor. Bidirectional communication is detected in one of two 1812 ways: 1814 o On a point-to-point link, the VlanHello protocol sees its own 1815 switch ID listed in an Interswitch Keepalive message it has 1816 received from the neighbor. 1818 o On a multi-access link, VLSP sees its own switch ID listed in 1819 a VLSP Hello packet it has received from the neighbor. 1821 In either case, a neighbor 2-Way Received neighbor event is 1822 generated. 1824 Once bidirectional communication has been established with a 1825 neighbor, the local switch determines whether an adjacency will 1826 be formed with the neighbor. However, if the link is a multi- 1827 access link, a designated switch and a backup designated switch 1828 must first be selected for the link. The next section contains 1829 a description of the designated switch, the backup designated 1830 switch, and the selection process. 1832 6.3 Designated Switch 1834 Every multi-access network link has a designated switch. The 1835 designated switch performs the following functions for the 1836 routing protocol: 1838 o The designated switch originates a network link advertisement 1839 on behalf of the link, listing the set of switches (including 1840 the designated switch itself) currently attached to the link. 1841 For a detailed description of network link advertisements, 1842 see Section 11.3. 1844 o The designated switch becomes adjacent to all other switches 1845 on the link. Since the link state databases are synchronized 1846 across adjacencies, the designated switch plays a central 1847 part in the synchronization process. For a description of 1848 the synchronization process, see Section 7. 1850 Each multi-access network link also has a backup designated 1851 switch. The primary function of the backup designated switch is 1852 to act as a standby for the designated switch. If the current 1853 designated switch fails, the backup designated switch becomes 1854 the designated switch. 1856 To facilitate this transition, the backup designated switch 1857 forms an adjacency with every other switch on the link. Thus, 1858 when the backup designated switch must take over for the 1859 designated switch, its link state database is already 1860 synchronized with the databases of all other switches on the 1861 link. 1863 Note 1865 Point-to-point network links have neither a designated 1866 switch or a backup designated switch. 1868 6.3.1 Selecting the Designated Switch 1870 When a multi-access link interface first becomes functional, the 1871 switch sets a one-shot Wait timer (with a value of 1872 SwitchDeadInterval seconds) for the interface. The purpose of 1873 this timer is to ensure that all switches attached to the link 1874 have a chance to establish bidirectional communication before 1875 the designated switch and backup designated switch are selected 1876 for the link. 1878 When the Wait timer is set, the interface enters the Waiting 1879 state. During this state, the switch exchanges Hello packets 1880 with its neighbors attempting to establish bidirectional 1881 communication. The interface leaves the Waiting state under one 1882 of the following conditions: 1884 o The Wait timer expires. 1886 o A Hello packet is received indicating that a designated 1887 switch or a backup designated switch has already been 1888 specified for the interface. 1890 At this point, if the switch sees that a designated switch has 1891 already been selected for the link, the switch accepts that 1892 designated switch, regardless of its own switch priority and MAC 1893 address. This situation typically means the switch has come up 1895 late on a fully functioning link. Although this makes it harder 1896 to predict the identity of the designated switch on a particular 1897 link, it ensures that the designated switch does not change 1898 needlessly, necessitating a resynchronization of the databases. 1900 If no designated switch is currently specified for the link, the 1901 switch begins the actual selection process. Note that this 1902 selection algorithm operates only on a list of neighbor switches 1903 that are eligible to become the designated switch. A neighbor 1904 is eligible to be the designated switch if it has a switch 1905 priority greater than zero and its neighbor state is 2-Way or 1906 greater. The local switch includes itself on the list of 1907 eligible switches as long as it has a switch priority greater 1908 than zero. 1910 The selection process includes the following steps: 1912 1. The current values of the link's designated switch and backup 1913 designated switch are saved for use in step 6. 1915 2. The new backup designated switch is selected as follows: 1917 a) Eliminate from consideration those switches that have 1918 declared themselves to be the designated switch. 1920 b) If one or more of the remaining switches have declared 1921 themselves to be the backup designated switch, eliminate 1922 from consideration all other switches. 1924 c) From the remaining list of eligible switches, select the 1925 switch having the highest switch priority as the backup 1926 designated switch. If multiple switches have the same 1927 (highest) priority, select the switch with the highest 1928 switch ID as the backup designated switch. 1930 3. The new designated switch is selected as follows: 1932 a) If one or more of the switches have declared themselves to 1933 be the designated switch, eliminate from consideration all 1934 other switches. 1936 b) From the remaining list of eligible switches, select the 1937 switch having the highest switch priority as the designated 1938 switch. If multiple switches have the same (highest) 1939 priority, select the switch with the highest switch ID as 1940 the designated switch. 1942 4. If the local switch has been newly selected as either the 1943 designated switch or the backup designated switch, or is now 1945 no longer the designated switch or the backup designated 1946 switch, repeat steps 2 and 3, above, and then proceed to 1947 step 5. 1949 If the local switch is now the designated switch, it will 1950 eliminate itself from consideration at step 2a when the 1951 selection of the backup designated switch is repeated. 1952 Likewise, if the local switch is now the backup designated 1953 switch, it will eliminate itself from consideration at step 1954 3a when the selection of the designated switch is repeated. 1955 This ensures that no switch will select itself as both backup 1956 designated switch and designated switch.[2] 1958 5. Set the interface state to the appropriate value, as follows: 1960 o If the local switch is now the designated switch, set the 1961 interface state to DS. 1963 o If the local switch is now the backup designated switch, 1964 set the interface state to Backup. 1966 o Otherwise, set the interface state to DS Other. 1968 6. If either the designated switch or backup designated switch 1969 has now changed, the set of adjacencies associated with this 1970 link must be modified. Some adjacencies may need to be 1971 formed, while others may need to be broken. Generate the 1972 neighbor AdjOK? event for all neighbors with a state of 2-Way 1973 or higher to trigger a reexamination of adjacency 1974 eligibility. 1976 Caution 1978 If VLSP is implemented with configurable parameters, 1979 care must be exercised in specifying the switch 1980 priorities. Note that if the local switch is not 1981 itself eligible to become the designated switch (i.e., 1982 it has a switch priority of 0), it is possible that 1983 neither a backup designated switch nor a designated 1984 switch will be selected by the above procedure. Note 1985 also that if the local switch is the only attached 1986 switch that is eligible to become the designated switch, 1987 it will select itself as designated switch and there will 1988 be no backup designated switch for the link. For this 1989 reason, it is advisable to specify a default switch 1990 priority of 1 for all switches. 1992 c) If the new advertisement was received on this interface and 1993 the state of the interface is Point-to-Point, there is no 1994 need to forward the advertisement since the received 1995 advertisement was originated by the neighbor switch. 1997 d) If the new advertisement was received on this interface, 1998 and the interface state is Backup -- that is, the switch 1999 itself is the backup designated switch -- there is no need 2000 to forward the advertisement out the interface. The 2001 designated switch will distribute advertisements on the 2002 attached network link. 2004 e) Otherwise, the advertisement must be forwarded out the 2005 interface. 2007 To forward a link state advertisement, the switch first 2008 increments the advertisement's age by InfTransDelay seconds 2009 to account for the transmission time over the link. The 2010 switch then copies the advertisement into a Link State Update 2011 packet 2013 Forwarded advertisements are sent to all adjacent switches 2014 associated with the interface. If the interface state is 2015 Point-to-Point, DS, or Backup, the destination switch ID 2016 field of the network layer address information is set to the 2017 multicast switch ID AllSPFSwitches. If the interface state 2018 is DS Other, the destination switch ID field is set to the 2019 multicast switch ID AllDSwitches. 2021 8.2.4 Installing Link State Advertisements in the Database 2023 When a new link state advertisement is installed into the link 2024 state database, as the result of either originating or receiving 2025 a new instance of an advertisement, the switch must determine 2026 whether the best paths need to be recalculated. To make this 2027 determination, do the following: 2029 1. Compare the contents of the new instance with the contents of 2030 the old instance (assuming the older instance is available). 2031 Note that this comparison does not include any data from the 2032 link state header. Differences in fields within the header 2033 (such as the sequence number and checksum, which are 2034 guaranteed to be different in different instances of an 2035 advertisement) are of no consequence when deciding whether or 2036 not to recalculate the set of best paths. 2038 2. If there are no differences in the contents of the two 2039 advertisement instances, there is no need to recalculate the 2040 set of best paths. 2042 3. Otherwise, the set of best paths must be recalculated. 2044 Note also that the older instance of the advertisement must be 2045 removed from the link state database when the new advertisement 2046 is installed. The older instance must also be removed from the 2047 link state retransmission lists of all neighbors. 2049 8.2.5 Retransmitting Link State Advertisements 2051 When a switch sends a link state advertisement to an adjacent 2052 neighbor, it records the advertisement in the neighbor's link 2053 state retransmission list. To ensure the reliability of the 2054 distribution process, the switch continues to periodically 2055 retransmit the advertisements specified in the list until they 2056 are acknowledged. 2058 The interval timer used to trigger retransmission of the 2059 advertisements is set to 2060 RxmtInterval seconds, as found in the interface data structure. 2061 Note that if this value is too low, needless retransmissions 2062 will ensue. If the value is too high, the speed with which the 2063 databases synchronize across adjacencies may be affected if 2064 there are lost packets. 2066 When the interval timer expires, entries in the retransmission 2067 list are formatted into one or more Link State Update packets. 2068 (Remember that multiple advertisements can fit into a single 2069 Link State Update packet.) The age field of each advertisement 2070 is incremented by InfTransDelay, as found in the interface data 2071 structure, before the advertisement is copied into the outgoing 2072 packet. 2074 Link State Update packets containing retransmitted 2075 advertisements are always sent directly to the adjacent switch. 2076 That is, the destination field of the network layer addressing 2077 information is set to the switch ID of the neighboring switch. 2079 If the adjacent switch goes down, retransmissions will continue 2080 until the switch failure is detected and the adjacency is torn 2081 down by the VLSP discovery process. When the adjacency is torn 2082 down, the link state retransmission list is cleared. 2084 8.2.6 Acknowledging Link State Advertisements 2086 Each link state advertisement received by a switch must be 2087 acknowledged. In most cases, this is done by sending a Link 2088 State Acknowledgment packet. However, acknowledgments can also 2089 be done implicitly by sending Link State Update packets (see 2090 step 4a of Section 8.2.2). 2092 Multiple acknowledgments can be grouped together into a single 2093 Link State Acknowledgment packet. 2095 Sending an acknowledgment 2097 Link State Acknowledgment packets are sent back out the 2098 interface over which the advertisement was received. The 2099 packet can be sent immediately to the sending neighbor, or it 2100 can be delayed and sent when an interval timer expires. 2102 o Sending delayed acknowledgments facilitates the formatting 2103 of multiple acknowledgments into a single packet. This 2104 enables a single packet to send acknowledgments to several 2105 neighbors at once by using a multicast switch ID in the 2106 destination field of the network layer addressing 2107 information (see below). Delaying acknowledgments also 2108 randomizes the acknowledgment packets sent by the multiple 2109 switches attached to a multi-access network link. 2111 Note that the interval used to time delayed acknowledgments 2112 must be short (less than RxmtInterval) or needless 2113 retransmissions will ensue. 2115 Delayed acknowledgments are sent to all adjacent switches 2116 associated with the interface. If the interface state is 2117 Point-to-Point, DS, or Backup, the destination field of the 2118 network layer addressing information is set to the multicast 2119 switch ID AllSPFSwitches. If the interface state is DS 2120 Other, the destination field is set to the multicast switch 2121 ID AllDSwitches. 2123 o Immediate acknowledgments are sent directly to a specific 2124 neighbor in response to the receipt of duplicate link state 2125 advertisements. These acknowledgments are sent immediately 2126 when the duplicate is received. 2128 The method used to send a Link State Acknowledgment packet -- 2129 either delayed or immediate -- depends on the circumstances 2130 surrounding the receipt of the advertisement, as shown in Table 2131 6. Note that switches with an interface state of Backup send 2132 acknowledgments differently than other switches because they 2133 play a slightly different role in the distribution process (see 2134 Section 8.2.3). 2136 Action taken in state 2137 Circumstances Backup Other states 2139 Advertisement was No ack sent No ack sent 2140 forwarded back out 2141 receiving interface 2143 Advertisement is Delayed ack sent Delayed ack 2144 more recent than if advertisement sent 2145 database copy, but received from DS, 2146 was not forwarded else do nothing 2147 back out receiving 2148 interface 2150 Advertisement was a Delayed ack sent No ack sent 2151 duplicate treated if advertisement 2152 as an implied acknow- received from DS, 2153 ledgment (step 4a of else do nothing 2154 Section 8.2.2) 2156 Advertisement was a Immediate ack Immediate ack 2157 duplicate not treated sent sent 2158 as an implied acknow- 2159 ledgment 2161 Advertisement age Immediate ack Immediate ack 2162 equal to MaxAge and sent sent 2163 no current instance 2164 found in database 2166 Table 6: Sending Link State Acknowledgments 2168 Receiving an acknowledgment 2170 When the a Link State Acknowledgment packet is received, it is 2171 first subjected to a number of consistency checks. In 2172 particular, the packet is associated with a specific neighbor. 2173 If the state of that neighbor is less than Exchange, the entire 2174 Link State Acknowledgment packet is discarded. 2176 Each acknowledgment contained in the packet is processed as 2177 follows: 2179 o If the advertisement being acknowledged has an instance in 2180 the link state retransmission list for the sending neighbor, 2181 do the following: 2183 o If the acknowledgment is for the same instance as that 2184 specified in the list (as determined by the procedure 2186 described in Section 7.1.1), remove the instance from the 2187 retransmission list. 2189 o Otherwise, log the acknowledgment as questionable. 2191 8.3 Aging the Link State Database 2193 Each link state advertisement has an age field, containing the 2194 advertisement's age, expressed in seconds. When the 2195 advertisement is copied into a Link State Update packet for 2196 forwarding out a particular interface, the age is incremented by 2197 InfTransDelay seconds to account for the transmission time over 2198 the link. An advertisement's age is never incremented past the 2199 value MaxAge. Advertisements with an age of MaxAge are not used 2200 to calculate best paths. 2202 If a link state advertisement's age reaches MaxAge, the switch 2203 flushes the advertisement from the switch fabric by doing the 2204 following: 2206 o Originate a new instance of the advertisement with the age 2207 field set to MaxAge. The distribution process will 2208 eventually result in the advertisement being removed from the 2209 retransmission lists of all switches in the fabric. 2211 o Once the advertisement is no longer contained in the link 2212 state retransmission list of any neighbor and no neighbor is 2213 in a state of Exchange or Loading, remove the advertisement 2214 from the local link state database. 2216 8.3.1 Premature Aging of Advertisements 2218 A link state advertisement can be prematurely flushed from the 2219 switch fabric by forcing its age to MaxAge and redistributing 2220 the advertisement. 2222 A switch that was previously the designated switch for a multi- 2223 access network link but has lost that status due to a failover 2224 to the backup designated switch prematurely ages the network 2225 link advertisements it originated for the link. 2227 Premature aging also occurs when an advertisement's sequence 2228 number must wrap -- that is, when the current advertisement 2229 instance has a sequence number of 0x7fffffff. In this 2230 circumstance, the advertisement is prematurely aged so that the 2231 next instance of the advertisement can be originated with a 2232 sequence number of 0x80000001 and be recognized as the most 2233 recent instance. 2235 A switch may only prematurely age those link state advertisements 2236 for which it is the advertising switch. 2238 9. Calculating the Best Paths 2240 Once an adjacency has been formed and the two switches have 2241 synchronized their databases, each switch in the adjacency 2242 calculates the best path(s) to all other switches in the fabric, 2243 using itself as the root of each path. In this context, "best" 2244 path means that path with the lowest total cost metric across 2245 all hops. If there are multiple paths with the same (lowest) 2246 total cost metric, they are all calculated. Best paths are 2247 stored in the area data structure. 2249 Paths are calculated using the well-known Dijkstra algorithm. 2250 For a detailed description of this algorithm, the reader is 2251 referred to [Perlman], or any of a number of standard textbooks 2252 dealing with network routing. 2254 Note that whenever there is a change in an adjacency 2255 relationship, or any change that alters the topology of the 2256 switch fabric, the set of best paths must be recalculated. 2258 10. Protocol Packets 2260 This section describes VLS protocol packets and link state 2261 advertisements. 2263 There are five distinct VLSP packet types, as listed in Table 7. 2265 Type Packet Name Function Description 2267 1 Hello Select DS/Backup DS Section 10.6.1 2268 2 Database Summarize database 2269 Description contents Section 10.6.2 2270 3 LS Request Database download Section 10.6.3 2271 4 LS Update Database update Section 10.6.4 2272 5 LS Ack Flooding acknow- 2273 ledgment Section 10.6.5 2275 Table 7: VLSP Packet Types 2277 All VLSP packets are encapsulated within a standard ISMP packet, 2278 with the VLS packet carried in the ISMP message body. The ISMP 2279 packet is described in Section 10.1. 2281 Since it is important that the link state databases remain 2282 synchronized throughout the switch fabric, processing of both 2283 incoming and outgoing routing protocol packets should take 2284 priority over ordinary data packets. Section 10.2 describes 2285 packet processing. 2287 All VLSP packets begin with network layer addressing 2288 information, described in Section 10.3, followed by a standard 2289 header, described in Section 10.4. 2291 With the exception of Hello packets, all VLSP packets deal with 2292 lists of link state advertisements. The format of a link state 2293 advertisement is described in Section 11. 2295 10.1 ISMP Packet Format 2297 All VLSP packets are encapsulated within a standard ISMP packet. 2298 ISMP packets are of variable length and have the following 2299 general structure: 2301 o Frame header 2302 o ISMP packet header 2303 o ISMP message body 2305 10.1.1 Frame Header 2307 ISMP packets are encapsulated within an IEEE 802-compliant frame 2308 using a standard header as shown below: 2310 0 1 2 3 2311 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2312 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2313 00 | | 2314 + Destination address +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2315 04 | | | 2316 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Source address + 2317 08 | | 2318 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2319 12 | Type | | 2320 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 2321 16 | | 2322 + + 2323 : : 2325 Destination address 2327 This 6-octet field contains the Media Access Control (MAC) 2328 address of the multicast channel over which all switches in 2329 the fabric receive ISMP packets. The destination address of 2330 all ISMP packets contain a value of 01-00-1D-00-00-00. 2332 Source address 2334 This 6-octet field contains the physical (MAC) address of the 2335 switch originating the ISMP packet. 2337 Type 2339 This 2-octet field identifies the type of data carried within 2340 the frame. The type field of ISMP packets contains the value 2341 0x81FD. 2343 10.1.2 ISMP Packet Header 2345 The ISMP packet header consists of 6 octets, as shown below: 2347 0 1 2 3 2348 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2349 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2350 00 |///////////////////////////////////////////////////////////////| 2351 ://////// Frame header /////////////////////////////////////////: 2352 +//////// (14 octets) /////////+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2353 12 |///////////////////////////////| Version | 2354 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2355 16 | ISMP message type | Sequence number | 2356 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2357 20 | | 2358 + + 2359 : : 2361 Frame header 2363 This 14-octet field contains the frame header. 2365 Version 2367 This 2-octet field contains the version number of the 2368 InterSwitch Message Protocol to which this ISMP packet 2369 adheres. This document describes ISMP Version 2.0. 2371 ISMP message type 2373 This 2-octet field contains a value indicating which type of 2374 ISMP message is contained within the message body. Valid 2375 values are as follows: 2377 1 (reserved) 2378 2 Interswitch Keepalive messages 2379 3 Interswitch Link State messages 2380 4 Interswitch Spanning Tree BPDU messages and 2381 Interswitch Remote Blocking messages 2382 5 Interswitch Resolve and New User messages 2383 6 (reserved) 2384 7 Tag-Based Flood messages 2385 8 Interswitch Tap messages 2387 All VLS protocol messages have an ISMP message type of 3. 2389 Sequence number 2391 This 2-octet field contains an internally generated sequence 2392 number used by the various protocol handlers for internal 2393 synchronization of messages. 2395 10.1.3 ISMP Message Body 2397 The ISMP message body is a variable-length field containing the 2398 actual data of the ISMP message. The length and content of this 2399 field are determined by the value found in the message type 2400 field. VLSP packets are contained in the ISMP message body. 2402 10.2 VLSP Packet Processing 2404 Note that with the exception of Hello packets, VLSP packets are 2405 sent only between adjacent neighbors. Therefore, all packets 2406 travel a single hop. 2408 VLSP does not support fragmentation and reassembly of packets. 2409 Therefore, packets containing lists of link state advertisements 2410 or advertisement headers must be formatted such that they 2411 contain only as many advertisements or headers as will fit 2412 within the size constraints of a standard ethernet frame. 2414 When a protocol packet is received by a switch, it must first 2415 pass the following criteria before being accepted for further 2416 processing: 2418 o The checksum number must be correct. 2420 o The destination switch ID (as found in the network layer 2421 address information) must be the switch ID of the receiving 2422 switch, or one of the multicast switch IDs AllSPFSwitches or 2423 AllDSwitches. 2425 If the destination switch ID is the multicast switch ID 2426 AllDSwitches, the state of the receiving interface must be 2427 Point-to-Point, DS, or Backup. 2429 o The source switch ID (as found in the network layer address 2430 information) must not be that of the receiving switch. (That 2431 is, locally originated packets should be discarded.) 2433 At this point, if the packet is a Hello packet, it is accepted 2434 for further processing. 2436 Since all other packet types are only sent between adjacent 2437 neighbors, the packet must have been sent by one of the switch's 2438 active neighbors. If the source switch ID matches the switch ID 2439 of one of the receiving switch's active neighbors (as stored in 2440 the interface data structure associated with the inport 2441 interface), the packet is accepted for further processing. 2442 Otherwise, the packet is discarded. 2444 10.3 Network Layer Address Information 2446 As mentioned in Section 2.2.1, portions of the VLS protocol (as 2447 derived from OSPF) are dependent on certain network layer 2448 addresses -- in particular, the AllSPFSwitches and AllDSwitches 2449 multicast addresses that drive the distribution of link state 2450 advertisements throughout the switch fabric. In order to 2451 facilitate the implementation of the protocol at the physical 2452 MAC layer, network layer address information is encapsulated in 2453 the VSLP packets. This information immediately follows the ISMP 2454 frame and packet header and immediately precedes the VLSP packet 2455 header, as shown below: 2457 0 1 2 3 2458 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2459 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2460 | | 2461 : frame header / ISMP header : 2462 | | 2463 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2464 00 | | 2465 : Unused (20 octets) : 2466 | | 2467 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2468 20 | | 2469 + Source switch ID + 2470 24 | | 2471 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2472 28 | | | 2473 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 2474 32 | | 2475 + Destination switch ID + 2476 36 | | 2477 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2478 40 | | 2479 : VLSP header : 2480 | | 2481 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2483 Source switch ID 2485 This 10-octet field contains the switch ID of the sending 2486 switch. 2488 Destination switch ID 2490 This 10-octet field contains the switch ID of the packet 2491 destination. The value here is set as follows: 2493 o Hello packets are addressed to the multicast switch ID 2494 AllSPFSwitches. 2496 o The designated switch and the backup designated switch 2497 address initial Link State Update packets and Link State 2498 Acknowledgment packets to the multicast switch ID 2499 AllSPFSwitches. 2501 o All other switches address initial Link State Update 2502 packets and Link State Acknowledgment packets to the 2503 multicast switch ID AllDSwitches. 2505 o Retransmissions of Link State Update packets are always 2506 addressed directly to the nonresponding switch. 2508 o Database Description packets and Link State Request are 2509 always addressed directly to the other switch participating 2510 in the database exchange process. 2512 VLSP header 2514 This 30-octet field contains the VLSP standard header. See 2515 Section 10.4. 2517 10.4 VLSP Packet Header 2519 Every VLSP packet starts with a common 30-octet header. This 2520 header, along with the data found in the network layer address 2521 information, contains all the data necessary to determine 2522 whether the packet should be accepted for further processing. 2523 (See Section 10.1.) 2525 The format of the VLSP header is shown below. Note that the 2526 header starts at offset 36 of the ISMP message body, following 2527 the network layer address information. 2529 0 1 2 3 2530 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2531 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2532 | | 2533 : frame header / ISMP header : 2534 | | 2535 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2536 00 | | 2537 : Network layer address information : 2538 | | 2539 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2540 40 | (unused) | Type | Packet length | 2541 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2542 44 | | 2543 + Source switch ID + 2544 48 | | 2545 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2546 52 | | Area ID . . . | 2547 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2548 56 | Area ID . . . | Checksum | 2549 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2550 60 | Autype | | 2551 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Authentication + 2552 64 | | 2553 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2554 68 | | 2555 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2557 Type 2559 This 1-octet field contains the packet type. Possible values 2560 are as follows: 2562 1 Hello 2563 2 Database Description 2564 3 Link State Request 2565 4 Link State Update 2566 5 Link State Acknowledgment 2568 Packet length 2570 This 2-octet field contains the length of the protocol 2571 packet, in bytes, calculated from the start of the VLSP 2572 header, at offset 20 of the ISMP message body. If the packet 2573 length is not an integral number of 16-bit words, the packet 2574 is padded with an octet of zero (see the description of the 2575 checksum field, below). 2577 Switch ID 2579 This 10-octet field contains the switch ID of the sending 2580 switch. 2582 Area ID 2584 This 4-octet field contains the area identifier. Since VLSP 2585 does not support multiple areas, the value here is always 2586 zero. 2588 Checksum 2590 This 2-octet field contains the packet checksum value. The 2591 checksum is calculated as the 16-bit one's complement of the 2592 one's complement sum of all the 16-bit words in the packet, 2593 beginning with the VLSP header, excluding the authentication 2594 field. If the packet length is not an integral number of 16- 2595 bit words, the packet is padded with an octet of zero before 2596 calculating the checksum. 2598 AuType 2600 This 2-octet field identifies the authentication scheme to be 2601 used for the packet. Since authentication is not supported 2602 by this version of VLSP, this field contains zero. 2604 Authentication 2606 This 8-octet field is reserved for use by the authentication 2607 scheme. Since authentication is not supported by this 2609 version of VLSP, this field contains zeroes. 2611 10.5 Options Field 2613 Hello packets and Database Description packets, as well as link 2614 state advertisements, contain a 1-octet options field. Using 2615 this field, a switch can communicate its optional capabilities 2616 to other VLSP switches. The receiving switch can then choose 2617 whether or not to support those optional capabilities. Thus, 2618 switches of differing capabilities potentially can be mixed 2619 within a single VLSP routing domain. 2621 Two optional capabilities are currently defined in the options 2622 field: routing based on Type of Service (TOS) and support for 2623 external routing beyond the local switch fabric. These two 2624 capabilities are specified in the options field as shown below. 2626 +-+-+-+-+-+-+-+-+ 2627 |0|0|0|0|0|0|E|T| 2628 +-+-+-+-+-+-+-+-+ 2630 The options field 2632 T-bit 2634 The T-bit specifies the switch's Type of Service (TOS) 2635 capability. If the T-bit is set, the switch supports routing 2636 based on nonzero types of service. 2638 E-bit 2640 The E-bit specifies the switch's external routing capability. 2641 If the E-bit is set, the switch supports external routing. 2643 Note 2645 The current version of VLSP supports neither of these 2646 capabilities. Therefore, both the T-bit and the E-bit 2647 are clear and the options field contains a value of zero. 2649 10.6 Packet Formats 2651 This section contains detailed descriptions of the five VLS 2652 protocol packets. 2654 10.6.1 Hello Packets 2656 Hello packets are sent periodically over multi-access switch 2657 interfaces in order to discover and maintain neighbor 2658 relationships. 2660 Note 2662 Hello packets are not sent over point-to-point 2663 network links. For point-to-point links, the VLS 2664 protocol relies on the VlanHello protocol [IDhello] 2665 to notify it of neighboring switches. 2667 Since all switches connected to a common network link must agree 2668 on certain interface parameters, these parameters are included 2669 in each Hello packet. A switch receiving a Hello packet that 2670 contains parameters inconsistent with its own view of the 2671 interface will not establish a neighbor relationship with the 2672 sending switch. 2674 The format of a Hello packet is shown below. 2676 0 1 2 3 2677 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2678 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2679 00 | | 2680 : Network layer addressing / VLSP header : 2681 | | 2682 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2683 70 | (unused -- must be 0) | 2684 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2685 74 | HelloInt | Options | Priority | 2686 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2687 78 | DeadInt | 2688 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2689 82 | | 2690 + Designated switch ID + 2691 86 | | 2692 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2693 90 | | | 2694 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 2695 94 | | 2696 + Backup designated switch ID + 2697 98 | | 2698 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2699 102 | | 2700 + + 2701 : Neighbor list : 2702 + + 2703 | | 2704 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2706 Network layer addressing / VLSP header 2708 This 70-octet field contains the network layer addressing 2709 information and the standard VLS protocol packet header. The 2710 packet header type field contains a value of 1. 2712 HelloInt 2714 This 2-octet field contains the interval, in seconds, at 2715 which this switch sends Hello packets. 2717 Options 2719 This 1-octet field contains the optional capabilities 2720 supported by the switch, as described in Section 10.5. 2722 Priority 2724 This 1-octet field contains the switch priority used in 2725 selecting the designated switch and backup designated switch 2726 (see Section 6.3.1). If the value here is zero, the switch 2727 is ineligible to become the designated switch or the backup 2728 designated switch. 2730 DeadInt 2732 This 4-octet field contains the length of time, in seconds, 2733 that neighboring switches will wait before declaring the 2734 interface down once they stop receiving Hello packets over 2735 the interface. The value here is equal to the value of 2736 SwitchDeadInterval, as found in the interface data structure. 2738 Designated switch 2740 This 10-octet field contains the switch ID of the designated 2741 switch for this network link, as currently understood by the 2742 sending switch. This value is set to zero if the designated 2743 switch selection process has not yet begun. 2745 Backup designated switch 2747 This 10-octet field contains the switch ID of the backup 2748 designated switch for the network link, as currently understood 2749 by the sending switch. This value is set to zero if the backup 2750 designated switch selection process has not yet begun. 2752 Neighbor list 2754 This variable-length field contains a list of switch IDs of 2755 each switch from which the sending switch has received a 2756 valid Hello packet within the last SwitchDeadInterval seconds. 2758 10.6.2 Database Description Packets 2760 Database Description packets are exchanged while an adjacency is 2761 being formed between two neighboring switches and are used to 2762 describe the contents of the topological database. For a 2763 complete description of the database exchange process, see 2764 Section 7.2. 2766 The format of a Database Description packet is shown below. 2768 0 1 2 3 2769 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2770 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2771 00 | | 2772 : Network layer addressing / VLSP header : 2773 | | 2774 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2775 70 | (unused -- must be 0) | Options | Flags | 2776 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2777 74 | Sequence number | 2778 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2779 78 | | 2780 + + 2781 : Link state advertisement headers : 2782 + + 2783 | | 2784 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2786 Network layer addressing / VLSP header 2788 This 70-octet field contains the network layer addressing 2789 information and the standard VLS protocol packet header. The 2790 packet header type field contains a value of 2. 2792 Options 2794 This 1-octet field contains the optional capabilities 2795 supported by the switch, as described in Section 10.5. 2797 Flags 2799 This 1-octet field contains a set of bit flags that are used 2800 to coordinate the database exchange process. The format of 2801 this octet is as follows: 2803 +-+-+-+-+-+-+-+-+ 2804 |0|0|0|0|0|I|M|MS 2805 +-+-+-+-+-+-+-+-+ 2807 I-bit (Init) 2809 The I-bit is used to signal the start of the exchange. It 2810 is set while the two switches negotiate the master/slave 2811 relationship and the starting sequence number. 2813 M-bit (More) 2815 The M-bit is set to indicate that more Database Description 2816 packets to follow. 2818 MS-bit (Master/Slave) 2820 The MS-bit is used to indicate which switch is the master 2821 of the exchange. If the bit is set, the sending switch is 2822 the master during the database exchange process. If the 2823 bit is clear, the switch is the slave. 2825 Sequence number 2827 This 4-octet field is used to sequence the Database 2828 Description packets during the database exchange process. 2829 The two switches involved in the exchange process agree on 2830 the initial value of the sequence number during the 2831 master/slave negotiation. The number is then incremented for 2832 each Database Description packet in the exchange. 2834 To acknowledge each Database Description packet sent by the 2835 master, the slave sends a Database Description packet that 2836 echoes the sequence number of the packet being acknowledged. 2838 Link state advertisement headers 2840 This variable-length field contains a list of link state 2841 headers that describe a portion of the master's topological 2842 database. Each header uniquely identifies a link state 2843 advertisement and its current instance. (See Section 11.1 2844 for a detailed description of a link state advertisement 2845 header.) The number of headers included in the list is 2846 calculated implicitly from the length of the packet, as 2847 stored in the VLSP packet header (see Section 10.4). 2849 10.6.3 Link State Request Packets 2851 Link State Request packets are used to request those pieces of 2852 the neighbor's database that the sending switch has discovered 2853 (during the database exchange process) are more up-to-date than 2854 instances in its own database. Link State Request packets are 2855 sent as the last step in bringing up an adjacency. (See Section 2856 7.3.) 2858 The format of a Link State Request packet is shown below. 2860 0 1 2 3 2861 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2862 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2863 00 | | 2864 : Network layer addressing / VLSP header : 2865 | | 2866 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2867 70 | Link state type | 2868 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2869 74 | | 2870 + Link state ID + 2871 88 | | 2872 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2873 82 | | | 2874 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 2875 86 | | 2876 + Advertising switch ID + 2877 90 | | 2878 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2879 94 | | 2880 : . . . : 2881 | | 2882 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2884 Network layer addressing / VLSP header 2886 This 70-octet field contains the network layer addressing 2887 information and the standard VLS protocol packet header. The 2888 packet header type field contains a value of 3. 2890 Link state type 2892 This 4-octet field contains the link state type of the 2893 requested link state advertisement, as stored in the 2894 advertisement header. 2896 Link state ID 2898 This 10-octet field contains the link state ID of the 2899 requested link state advertisement, as stored in the 2900 advertisement header. 2902 Advertising switch 2904 This 10-octet field contains the switch ID of advertising 2905 switch for the requested link state advertisement, as stored 2906 in the advertisement header. 2908 Note that the last three fields uniquely identify the 2909 advertisement, but not its instance. The receiving switch will 2910 respond with its most recent instance of the specified 2911 advertisement. 2913 Multiple link state advertisements can be requested in a single 2914 Link State Request packet by repeating the link state type, ID, 2915 and advertising switch for each requested advertisement. The 2916 number of advertisements requested is calculated implicitly from 2917 the length of the packet, as stored in the VLSP packet header. 2919 10.6.4 Link State Update Packets 2921 Link State Update packets are used to respond to a Link State 2922 Request packet or to advertise a new instance of one or more 2923 link state advertisements. Link State Update packets are 2924 acknowledged with Link State Acknowledgment packets. For more 2925 information on the use of Link State Update packets, see Section 2926 7 and Section 8. 2928 The format of a Link State Update packet is shown below. 2930 0 1 2 3 2931 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2932 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2933 00 | | 2934 : Network layer addressing / VLSP header : 2935 | | 2936 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2937 70 | # advertisements | 2938 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2939 74 | | 2940 + + 2941 : Link state advertisements : 2942 + + 2943 | | 2944 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2946 6.4 Adjacencies 2948 VLSP creates adjacencies between neighboring switches for the 2949 purpose of exchanging routing information. Not every two 2950 neighboring switches will become adjacent. On a multi-access 2951 link, an adjacency is only formed between two switches if one of 2952 them is either the designated switch or the backup designated 2953 switch. 2955 Note that an adjacency is bound to the network link that the two 2956 switches have in common. Therefore, if two switches have 2957 multiple links in common, they may also have multiple 2958 adjacencies between them. 2960 The decision to form an adjacency occurs in two places in the 2961 neighbor state machine: 2963 o When bidirectional communication is initially established 2964 with the neighbor. 2966 o When the designated switch or backup designated switch on 2967 the attached link changes. 2969 The rules for establishing an adjacency between two neighboring 2970 switches are as follows: 2972 o On a point-to-point link, the two neighboring switches always 2973 establish an adjacency. 2975 o On a multi-access link, an adjacency is established with the 2976 neighboring switch under one of the following conditions: 2978 o The local switch itself is the designated switch. 2979 o The local switch itself is the backup designated switch. 2980 o The neighboring switch is the designated switch. 2981 o The neighboring switch is the backup designated switch. 2983 If no adjacency is formed between two neighboring switches, the 2984 state of the neighbor conversation remains set to 2-Way. 2986 7. Synchronizing the Databases 2988 In an SPF-based routing algorithm, it is important for the link 2989 state databases of all switches to stay synchronized. VLSP 2990 simplifies this process by requiring only adjacent switches to 2991 remain synchronized. 2993 The synchronization process begins when the switches attempt to 2994 bring up the adjacency. Each switch in the adjacency describes 2995 its database by sending a sequence of Database Description 2997 packets to its neighbor. Each Database Description packet 2998 describes a set of link state advertisements belonging to the 2999 database. When the neighbor sees a link state advertisement 3000 that is more recent than its own database copy, it makes a note 3001 to request this newer advertisement. 3003 During this exchange of Database Description packets (known as 3004 the database exchange process), the two switches form a 3005 master/slave relationship. Database Description packets sent by 3006 the master are known as polls, and each poll contains a sequence 3007 number. Polls are acknowledged by the slave by echoing the 3008 sequence number in the Database Description response packet. 3010 When all Database Description packets have been sent and 3011 acknowledged, the database exchange process is completed. At 3012 this point, each switch in the exchange has a list of link state 3013 advertisements for which its neighbor has more recent instances. 3014 These advertisements are requested using Link State Request 3015 packets. 3017 Once the database exchange process has completed and all Link 3018 State Requests have been satisfied, the databases are deemed 3019 synchronized and the neighbor states of the two switches are set 3020 to Full, indicating that the adjacency is fully functional. 3021 Fully functional adjacencies are advertised in the link state 3022 advertisements of the two switches.[3] 3024 7.1 Link State Advertisements 3026 Link state advertisements form the core of the database from 3027 which a switch calculates the set of best paths to the other 3028 switches in the fabric. 3030 Each link state advertisement begins with a standard header. 3031 This header contains three data items that uniquely identify the 3032 link state advertisement. 3034 o The link state type. Possible values are as follows: 3036 1 Switch link advertisement -- describes the collected 3037 states of the switch's interfaces. 3039 2 Network link advertisement -- describes the set of 3040 switches attached to the network link. 3042 o The link state ID, defined as follows: 3044 o For a switch link advertisement -- the switch ID of the 3045 originating switch 3047 o For a network link advertisement -- the switch ID of the 3048 designated switch for the link 3050 o The switch ID of the advertising switch -- the switch that 3051 generated the advertisement 3053 The link state advertisement header also contains three data 3054 items that are used to determine which instance of a particular 3055 link state advertisement is the most current. (See Section 3056 7.1.1 for a description of how to determine which instance of a 3057 link state advertisement is the most current.) 3059 o The link state sequence number 3061 o The link state age, stored in seconds 3063 o The link state checksum, a 16-bit unsigned value calculated 3064 for the entire contents of the link state advertisement, with 3065 the exception of the age field 3067 The remainder of each link state advertisement contains data 3068 specific to the type of the advertisement. See Section 11 for a 3069 detailed description of the link state header, as well as the 3070 format of a switch link or network link advertisement. 3072 7.1.1 Determining Which Link State Advertisement Is Newer 3074 At various times while synchronizing or updating the link state 3075 database, a switch must determine which instance of a particular 3076 link state advertisement is the most current. This decision is 3077 made as follows: 3079 o The advertisement having the greater sequence number is the 3080 most current. 3082 o If both instances have the same sequence number, then: 3084 o If the two instances have different checksum values, then 3085 the instance having the larger checksum is considered the 3086 most current.[4] 3088 o If both instances have the same sequence number and the same 3089 checksum value, then: 3091 o If one (and only one) of the instances is of age MaxAge, 3092 then the instance of age MaxAge is considered the most 3093 current.[5] 3095 o Else, if the ages of the two instances differ by more than 3096 MaxAgeDiff, the instance having the smaller (younger) age 3097 is considered the most current.[6] 3099 o Else, the two instances are considered identical. 3101 7.2 Database Exchange Process 3103 There are two stages to the database exchange process: 3105 o Negotiating the master/slave relationship 3106 o Exchanging database summary information 3108 In both these stages, the neighboring switches exchange Database 3109 Description packets. 3111 7.2.1 Database Description Packets 3113 Database Description packets are used to describe a switch's 3114 link state database during the database exchange process. Each 3115 Database Description packet contains a list of headers of the 3116 link state advertisements currently stored in the sending 3117 switch's database. (See Section 11.1 for a description of a 3118 link state advertisement header.) 3120 In addition to the link state headers, each Database Description 3121 packet contains the following data items: 3123 o A flag (the M-bit) indicating whether or not more packets are 3124 to follow. Depending on the size of the local database and 3125 the maximum size of the packet, the list of headers in any 3126 particular Database Description packet may be only a partial 3127 list of the total database. When the M-bit is set, the list 3128 of headers is only a partial list and more headers are to 3129 follow in subsequent packets. 3131 o A flag (the I-bit) indicating whether or not this is the 3132 first Database Description packet sent for this execution of 3133 the database exchange process. 3135 o A flag (the MS-bit) indicating whether the sending switch 3136 thinks it is the master or the slave in the database exchange 3137 process. If the flag is set, the switch thinks it is the 3138 master. 3140 o A 4-octet sequence number for the packet. 3142 While the switches are negotiating the master/slave 3143 relationship, they exchange "empty" Database Description 3145 packets. That is, packets that contain no link summary 3146 information. Instead, the flags and sequence number constitute 3147 the information required for the negotiation process. 3149 See Section 10.6.2 for a more detailed description of a Database 3150 Description packet. 3152 7.2.2 Negotiating the Master/Slave Relationship 3154 Before two switches can begin the actual exchange of database 3155 information, they must decide between themselves who will be the 3156 master in the exchange process and who will be the slave. They 3157 must also agree on the starting sequence number for the Database 3158 Description packets. 3160 Once a switch has decided to form an adjacency with a 3161 neighboring switch, it sets the neighbor state to ExStart and 3162 begins sending empty Database Description packets to its 3163 neighbor. These packets contain the starting sequence number 3164 the switch plans to use in the exchange process. Also, the I- 3165 bit and M-bit flags are set, as well as the MS-bit. Thus, each 3166 switch in the exchange begins by believing it will be the 3167 master. 3169 Empty Database Description packets are retransmitted every 3170 RxmtInterval seconds until the neighbor responds. 3172 When a switch receives an empty Database Description packet from 3173 its neighbor, it determines which switch will be the master by 3174 comparing the switch IDs. The switch with the highest switch ID 3175 becomes the master of the exchange. Based on this 3176 determination, the switch proceeds as follows: 3178 o If the switch is to be the slave of the database exchange 3179 process, it acknowledges that it is the slave by sending 3180 another empty Database Description packet to the master. 3181 This packet contains the master's sequence number and has the 3182 MS-bit and the I-bit cleared. 3184 o The switch then generates a neighbor event of Negotiation 3185 Done to change its neighbor state to Exchange and waits for 3186 the first non-empty Database Description packet from the 3187 master. 3189 o If the switch is to be the master of the database exchange, 3190 it waits to receive an acknowledgment from its neighbor -- 3191 that is, an empty Database Description packet with the MS-bit 3192 and I-bit cleared and containing the sequence number it (the 3193 master) previously sent. 3195 o When it receives the acknowledgment, it generates a neighbor 3196 event of Negotiation Done to change its neighbor state to 3197 Exchange and begin the actual exchange of Database 3198 Description packets. 3200 Note that during the negotiation process, the receipt of an 3201 inconsistent packet will result in a neighbor event of Seq 3202 Number Mismatch, terminating the process. See Section 4.3 for 3203 more information. 3205 7.2.3 Exchanging Database Description Packets 3207 Once the neighbor state changes to Exchange, the switches begin 3208 the exchange of Database Description packets containing link 3209 state summary data. The process proceeds as follows: 3211 1. The master sends a packet containing a list of link state 3212 headers. If the packet contains only a portion of the 3213 unexchanged database -- that is, more Database Description 3214 packets are to follow -- the packet has the M-bit set. The 3215 MS-bit is set and the I-bit is clear. 3217 If the slave does not acknowledge the packet within 3218 RxmtInterval seconds, the master retransmits the packet. 3220 2. When the slave receives a packet, it first checks the 3221 sequence number to see if the packet is a duplicate. If so, 3222 it simply acknowledges the packet by clearing the MS-bit and 3223 returning the packet to the master. (Note that the slave 3224 acknowledges all Database Description packets that it 3225 receives, even those that are duplicates.) 3227 Otherwise, the slave processes the packet by doing the 3228 following: 3230 o For each link state header listed in the packet, the slave 3231 searches its own link state database to determine whether 3232 it has an instance of the advertisement. 3234 o If the slave does not have an instance of the link state 3235 advertisement, or if the instance it does have is older 3236 than the instance listed in the packet, it creates an entry 3237 in its link state request list in the neighbor data 3238 structure. See Section 7.1.1 for a description of how to 3239 determine which instance of a link state advertisement is 3240 the newest. 3242 o When the slave has examined all headers, it acknowledges 3243 the packet by turning the MS-bit off and returning the 3244 packet to the master. 3246 3. When the master receives the first acknowledgment for a 3247 particular Database Description packet, it processes the 3248 acknowledgment as follows: 3250 o For each link state header listed in the packet, the master 3251 checks to see if the slave has indicated it has an instance 3252 of the link state advertisement that is newer than the 3253 instance the master has in its own database. If so, the 3254 master creates an entry in its link state request list in 3255 the neighbor data structure. 3257 o The master then increments the sequence number and sends 3258 another packet containing the next set of link state 3259 summary information, if any. 3261 Subsequent acknowledgments for the Database Description 3262 packet (those with the same sequence number) are discarded. 3264 When the master sends the last portion of its database 3265 summary information, it clears the M-bit in the packet to 3266 indicate that no more packets are to be sent. 3268 4. When the slave receives a Database Description packet with 3269 the M-bit clear, it processes the packet, as described above 3270 in step 2. After it has completed processing and has 3271 acknowledged the packet to the master, it generates an 3272 Exchange Done neighbor event and its neighbor state changes 3273 to Loading. 3275 The database exchange process is now complete for the slave, 3276 and it begins the process of requesting those link state 3277 advertisements for which the master has more current 3278 instances (see Section 7.3). 3280 5. When the master receives an acknowledgment for the final 3281 Database Description packet, it processes the acknowledgment 3282 as described above in step 3. Then it generates an Exchange 3283 Done neighbor event and its neighbor state changes to 3284 Loading. 3286 The database exchange process is now complete for the master, 3287 and it begins the process of requesting those link state 3288 advertisements for which the slave has more current instances 3289 (see Section 7.3). 3291 Note that during this exchange, the receipt of an inconsistent 3292 packet will result in a neighbor event of Seq Number Mismatch, 3293 terminating the process. See Section 4.3 for more information. 3295 7.3 Updating the Database 3297 When either switch completes the database exchange process and 3298 its neighbor state changes to Loading, it has a list of link 3299 state advertisements for which the neighboring switch has a more 3300 recent instance. This list is stored in the neighbor data 3301 structure as the link state request list. 3303 To complete the synchronization of its database with that of its 3304 neighbor, the switch must obtain the most current instances of 3305 those link state advertisements. 3307 The switch requests these advertisements by sending its neighbor 3308 a Link State Request packet containing the description of one or 3309 more link state advertisement, as defined by the advertisement's 3310 type, link state ID, and advertising switch. (For a detailed 3311 description of the Link State Request packet, see Section 3312 10.6.3.) The switch continues to retransmit this packet every 3313 RxmtInterval seconds until it receives a reply from the 3314 neighbor. 3316 When the neighbor switch receives the Link State Request packet, 3317 it responds with a Link State Update packet containing its most 3318 current instance of each of the requested advertisements. (Note 3319 that the neighboring switch can be in any of the Exchange, 3320 Loading or Full neighbor states when it responds to a Link State 3321 Request packet.) 3323 If the neighbor cannot locate a particular link state 3324 advertisement in its database, something has gone wrong with the 3325 synchronization process. The switch generates a BadLSReq 3326 neighbor event and the partially formed adjacency is torn down. 3327 See Section 4.3 for more information. 3329 Depending on the size of the link state request list, it may 3330 take more than one Link State Request packet to obtain all the 3331 necessary advertisements. Note, however, that there must at 3332 most one Link State Request packet outstanding at any one time. 3334 7.4 An Example 3336 Figure 3 shows an example of an adjacency being formed between 3337 two switches -- S1 and S2 -- connected to a network link. S2 is 3338 the designated switch for the link and has a higher switch ID 3339 than S1. 3341 The neighbor state changes that each switch goes through are 3342 listed on the sides of the figure. 3344 +--------+ +--------+ 3345 | Switch | | Switch | 3346 | S1 | | S2 | 3347 +--------+ +--------+ 3349 Down Down 3350 Hello (DS=0, seen=0) 3351 -------------------------------------> 3352 Init 3353 Hello (DS=S2, seen=...,S1) 3354 <------------------------------------- 3355 ExStart 3356 DB Description (Seq=x, I, M, Master) 3357 -------------------------------------> 3358 ExStart 3359 DB Description (Seq=y, I, M, Master) 3360 <------------------------------------- 3361 Exchange 3362 DB Description (Seq=y, M, Slave) 3363 -------------------------------------> 3364 Exchange 3365 DB Description (Seq=y+1, M, Master) 3366 <------------------------------------- 3367 DB Description (Seq=y+1, M, Slave) 3368 -------------------------------------> 3369 . 3370 . 3371 . 3373 DB Description (Seq=y+n, Master) 3374 <------------------------------------- 3375 DB Description (Seq=y+n, Slave) 3376 -------------------------------------> 3377 Loading Full 3378 Link State Request 3379 <------------------------------------- 3380 Link State Update 3381 -------------------------------------> 3382 . 3383 . 3384 . 3386 Link State Request 3387 <------------------------------------- 3388 Link State Update 3389 -------------------------------------> 3390 Full 3392 Figure 3: An Example of Bringing Up an Adjacency 3394 At the top of Figure 3, S1's interface to the link becomes 3395 operational, and S1 begins sending Hello packets over the 3396 interface. At this point, S1 does not yet know the identity of 3397 the designated switch or of any other neighboring switches. 3398 S2 receives the Hello packet from S1 and changes its neighbor 3399 state to Init. In its next Hello packet, S2 indicates that it 3400 is itself the designated switch and that it has received a Hello 3401 packet from S1. S1 receives the Hello packet and changes its 3402 state to ExStart, starting the process of bringing up the 3403 adjacency. 3405 S1 begins by asserting itself as the master. When it sees that 3406 S2 is indeed the master (because of S2's higher switch ID), S1 3407 changes to slave and adopts S2's sequence number. Database 3408 Description packets are then exchanged, with polls coming from 3409 the master (S2) and acknowledgments from the slave (S1). This 3410 sequence of Database Description packets ends when both the poll 3411 and associated acknowledgment have the M-bit off. 3413 In this example, it is assumed that S2 has a completely up-to- 3414 date database and immediately changes to the Full state. S1 will 3415 change to the Full state after updating its database by sending 3416 Link State Request packets and receiving Link State Update 3417 packets in response. 3419 Note that in this example, S1 has waited until all Database 3420 Description packets have been received from S2 before sending 3421 any Link State Request packets. However, this need not be the 3422 case. S1 could interleave the sending of Link State Request 3423 packets with the reception of Database Description packets. 3425 8. Maintaining the Databases 3427 Each switch advertises its state (also known as its link state) 3428 by originating switch link advertisements. In addition, the 3429 designated switch on each network link advertises the state of 3430 the link by originating network link advertisements. 3432 As described in Section 7.1, link state advertisements are 3433 uniquely identified by their type, link state ID, and 3434 advertising switch. 3436 Link state advertisements are distributed throughout the switch 3437 fabric using a reliable flooding algorithm that ensures that all 3438 switches in the fabric are notified of any link state changes. 3440 8.1 Originating Link State Advertisements 3442 A new instance of each link state advertisement is originated 3443 any time the state of the switch or link changes. When a new 3444 instance of a link state advertisement is originated, its 3445 sequence number is incremented, its age is set to zero, and its 3446 checksum is calculated. The advertisement is then installed 3447 into the local link state database and forwarded out all fully 3448 operational interfaces (that is, those interfaces with a state 3449 greater than Waiting) for distribution throughout the switch 3450 fabric. See Section 8.2.4 for a description of the installation 3451 of the advertisement into the link state database and Section 3452 8.2.5 for a description of how advertisements are forwarded. 3454 A switch originates a new instance of a link state advertisement 3455 as a result of the following events: 3457 o The state of one of the switch's interfaces changes such that 3458 the contents of the associated switch link advertisement 3459 changes. 3461 o The designated switch on any of the switch's attached network 3462 links changes. The switch originates a new switch link 3463 advertisement. Also, if the switch itself is now the 3464 designated switch, it originates a new network link 3465 advertisement for the link. 3467 o One of the switch's neighbor states changes to or from Full. 3468 If this changes the contents of the associated switch link 3469 advertisement, a new instance is generated. Also, if the 3470 switch is the designated switch for the attached network link, 3471 it originates a new network link advertisement for the link. 3473 Two instances of the same link state advertisement must not be 3474 originated within the time period MinLSInterval. Note that this 3475 may require that the generation of the second instance to be 3476 delayed up to MinLSInterval seconds. 3478 8.1.1 Switch Link Advertisements 3480 A switch link advertisement describes the collected states of 3481 all functioning links attached to the originating switch -- that 3482 is, all attached links with an interface state greater than 3483 Down. A switch originates an empty switch link advertisement 3484 when it first becomes functional. It then generates a new 3485 instance of the advertisement each time one of its interfaces 3486 reaches a fully functioning state (Point-to-Point or better). 3488 Each link in the advertisement is assigned a type, based on the 3489 state of interface, as shown in Table 4. 3491 Interface state Link type Description 3493 Point-to-Point 1 Point-to-point link 3494 DS Other* 2 Multi-access link 3495 Backup* 2 Multi-access link 3496 DS** 2 Multi-access link 3498 *If a full adjacency has been formed with the designated 3499 switch. 3501 **If a full adjacency has been formed with at least one 3502 other switch on the link. 3504 Table 4: Link Types in a Switch Link Advertisement 3506 Each link in the advertisement is also assigned a link 3507 identifier based on its link type. In general, this value 3508 identifies another switch that also originates advertisements 3509 for the link, thereby providing a key for accessing other link 3510 state advertisements for the link. The relationship between 3511 link type and ID is shown in Table 5. 3513 Type Description Link ID 3515 1 Point-to-point link Switch ID of neighbor switch 3516 2 Multi-access link Switch ID of designated switch 3518 Table 5: Link IDs in a Switch Link Advertisement 3520 In addition to a type and an identifier, the description of each 3521 link specifies the interface ID of the associated network link. 3523 Finally, each link description includes the cost of sending a 3524 packet over the link. This output cost is expressed in the link 3525 state metric and must be greater than zero. 3527 To illustrate the format of a switch link advertisement, consider 3528 the switch fabric shown in Figure 4. 3530 In this example, switch SW1 has 5 neighboring switches (shown as 3531 boxes) distributed over 3 network links (shown as lines). The 3532 base MAC address of each switch is also shown adjacent to each 3533 box. On switch SW1, ports 01 and 02 attach to point-to-point 3534 network links, while port 03 attaches to a multi-access network 3535 link with three attached switches. The interface state of each 3536 port is shown next to the line representing the corresponding 3537 link. 3539 00-00-1d-22-23-c5 3540 +-------+ 3541 | SW2 | 3542 +-------+ 3543 | 3544 | Point-to-Point 3545 | 3546 | 01 3547 +-------+ Loopback +-------+ 3548 | SW3 |----------------| SW1 | 00-00-1d-1f-05-81 3549 +-------+ 02 +-------+ 3550 00-00-1d-17-35-a4 | 03 3551 | 3552 | DS Other 3553 | 3554 +--------------------+--------------------+ 3555 | | | 3556 | DS Other | Backup | DS 3557 | | | 3558 +-------+ +-------+ +-------+ 3559 | SW4 | | SW5 | | SW6 | 3560 +-------+ +-------+ +-------+ 3561 00-00-1d-4a-26-b3 00-00-1d-4a-27-1c 00-00-1d-7e-84-2e 3563 Figure 4: Sample Switch Fabric 3565 The switch link advertisement generated by switch SW1 would 3566 contain the following data items: 3568 ; switch link advertisement for switch SW1 3570 LS age = 0 ; always true on origination 3571 Options = (T-bit|E-bit) ; options 3572 LS type = 1 ; this is a switch link advert 3574 ; SW1's switch ID 3575 Link State ID = 00-00-1d-1f-05-81-00-00-00-00 3576 Advertising switch = 00-00-1d-1f-05-81-00-00-00-00 3577 # links = 2 3579 ; link on interface port 1 3580 Link ID = 00-00-1d-22-23-c5-00-00-00-00 ; switch ID 3581 Link Data = 00-00-1d-1f-05-81-00-00-00-01 ; interface ID 3582 Type = 1 ; pt-to-pt link 3583 # other metrics = 0 ; TOS 0 only 3584 TOS 0 metric = 1 3586 ; link on interface port 2 is not fully functional 3588 ; link on interface port 3 3589 Link ID = 00-00-1d-7e-84-2e-00-00-00-00 ; switch ID of DS 3590 Link Data = 00-00-1d-1f-05-81-00-00-00-03 ; interface ID 3591 Type = 2 ; multi-access 3592 # other metrics = 0 ; TOS 0 only 3593 TOS 0 metric = 2 3595 (See Section 11.2 for a detailed description of the format of a 3596 switch link advertisement.) 3598 8.1.2 Network Link Advertisements 3600 Network link advertisements are used to describe the switches 3601 attached to each multi-access network link. 3603 Note 3605 Network link advertisements are not generated for 3606 point-to-point links. 3608 A network link advertisement is originated by the designated 3609 switch for the associated multi-access link once the switch has 3610 established a full adjacency with at least one other switch on 3611 the link. Each advertisement lists the switch IDs of those 3612 switches that are fully adjacent to the designated switch. The 3613 designated switch includes itself in this list. 3615 To illustrate the format of a network link advertisement, 3616 consider again the switch fabric shown in Figure 4. In this 3617 example, network link advertisements will be generated only by 3618 switch SW6, the designated switch of the multi-access network 3619 link between switches SW1 and switches SW4, SW5, and SW6. 3621 The network link advertisement generated by switch SW6 would 3622 contain the following data items: 3624 ; network link advertisement for switch SW6 3626 LS age = 0 ; always true on origination 3627 Options = (T-bit|E-bit) ; options 3628 LS type = 2 ; this is a network link advert 3630 ; SW6's switch ID 3631 Link State ID = 00-00-1d-73-84-2e-00-00-00-00 3632 Advertising switch = 00-00-1d-73-84-2e-00-00-00-00 3634 Attached switch = 00-00-1d-7e-84-2e-00-00-00-00 3635 Attached switch = 00-00-1d-4a-26-b3-00-00-00-00 3636 Attached switch = 00-00-1d-1f-05-81-00-00-00-00 3637 Attached switch = 00-00-1d-4a-27-1c-00-00-00-00 3639 (See Section 11.3 for a detailed description of the format of a 3640 network link advertisement.) 3642 8.2 Distributing Link State Advertisements 3644 Link state advertisements are distributed throughout the switch 3645 fabric encapsulated within Link State Update packets. A single 3646 Link State Update packet may contain several distinct 3647 advertisements. 3649 To make the distribution process reliable, each advertisement 3650 must be explicitly acknowledged in a Link State Acknowledgment 3651 packet. Note, however, that multiple acknowledgments can be 3652 grouped together into a single Link State Acknowledgment packet. 3653 A sending switch retransmits unacknowledged Link State Update 3654 packets at regular intervals until they are acknowledged. 3656 The remainder of this section is structured as follows: 3658 o Section 8.2.1 presents an overview of the distribution 3659 process. 3661 o Section 8.2.2 describes how an incoming Link State Update 3662 packet is processed. 3664 o Section 8.2.3 describes how a Link State Packet is forwarded 3665 -- both by the originating switch and an intermediate 3666 receiving switch. 3668 o Section 8.2.4 describes how advertisements are installed into 3669 the local database. 3671 o Section 8.2.5 describes the retransmission of unacknowledged 3672 advertisements. 3674 o Section 8.2.6 describes how advertisements are acknowledged. 3676 8.2.1 Overview 3678 The philosophy behind the distribution of link state 3679 advertisements is based on the concept of adjacencies -- that 3680 is, each switch is only required to remain synchronized with its 3681 adjacent neighbors. 3683 When a switch originates a new instance of a link state 3684 advertisement, it formats the advertisement into a Link State 3685 Update packet and floods the packet out each fully operational 3686 interface -- that is, each interface with a state greater than 3687 Waiting. However, only those neighbors that are adjacent to the 3688 sending switch need to process the packet. 3690 The sending switch indicates which of its neighbor switches 3691 should process the advertisement by specifying a particular 3692 multicast destination in the network layer address information 3693 (see Section 10.3). The sending switch sets the value of the 3694 network layer destination switch ID field according to the state 3695 of the interface over which the packet is sent: 3697 o If the interface state is Point-to-Point, DS, or Backup, the 3698 switch is adjacent to all other switches on the link and all 3699 neighboring switches must process the packet. Therefore, the 3700 destination field is set to the multicast switch ID 3701 AllSPFSwitches. 3703 o If the interface state is DS Other, the switch is only 3704 adjacent to the designated switch and the backup designated 3705 switch and only those two neighboring switches must process 3706 the packet. Therefore, the destination field is set to the 3707 multicast switch ID AllDSwitches. 3709 A similar logic is used when a switch receives a Link State 3710 Update packet containing a new instance of a link state 3711 advertisement. After processing and acknowledging the packet, 3712 the receiving switch forwards the Link State Update packet as 3713 follows: 3715 o On the interface over which the original Link State Update 3716 packet was received: 3718 o If the receiving switch is the designated switch for the 3719 attached network link, the packet is forwarded to all other 3720 switches on the link. (The destination field is set to 3721 AllSPFSwitches.) The originating switch will recognize 3722 that it was the advertisement originator and discard the 3723 packet. 3725 o If the receiving switch is not the designated switch for 3726 the attached network link, the packet is not sent back out 3727 the interface over which it was received. 3729 o On all other interfaces: 3731 o If the receiving switch is the designated switch for the 3732 attached network link, the packet is forwarded to all 3733 switches on the link. (The destination field is set to 3734 AllSPFSwitches.) 3736 o If the receiving switch is neither the designated switch or 3737 the backup designated switch for the attached network link, 3738 the packet is forwarded only to the designated switch and 3739 the backup designated switch. (The destination field is 3740 set to AllDSwitches.) 3742 Each Link State Update packet is forwarded and processed in this 3743 fashion until all switches in the fabric have received 3744 notification of the new instance of the link state 3745 advertisement. 3747 8.2.2 Processing an Incoming Link State Update Packet 3749 When the a Link State Update packet is received, it is first 3750 subjected to a number of consistency checks. In particular, the 3751 Link State Update packet is associated with a specific neighbor. 3752 If the state of that neighbor is less than Exchange, the entire 3753 Link State Update packet is discarded. 3755 Each link state advertisement contained in the packet is 3756 processed as follows: 3758 1. Validate the advertisement's link state checksum and type. 3759 If the checksum is invalid or the type is unknown, discard 3760 the advertisement without acknowledging it. 3762 2. If the advertisement's age is equal to MaxAge and there is 3763 currently no instance of the advertisement in the local link 3764 state database, then do the following: 3766 a) Acknowledge the advertisement by sending a Link State 3767 Acknowledgment packet to the sending neighbor (see Section 3768 8.2.6). 3770 b) Purge all outstanding requests for equal or previous 3771 instances of the advertisement from the sending neighbor's 3772 Link State Request list. 3774 c) If the neighbor is Exchange or Loading, install the 3775 advertisement in the link state database (see Section 3776 8.2.4). Otherwise, discard the advertisement. 3778 3. If the advertisement's age is equal to MaxAge and there is an 3779 instance of the advertisement in the local link state database, 3780 then do the following: 3782 a) If the advertisement is listed in the link state 3783 retransmission list of any neighbor, remove the 3784 advertisement from the retransmission list(s) and delete 3785 the database copy of the advertisement. 3787 b) Discard the received (MaxAge) advertisement without 3788 acknowledging it. 3790 4. If the advertisement's age is less than MaxAge, attempt to 3791 locate an instance of the advertisement in the local link 3792 state database. If there is no database copy of this 3793 advertisement, or the received advertisement is more recent 3794 than the database copy (see Section 7.1.1), do the following: 3796 a) If there is already a database copy, and if the database 3797 copy was installed less than MinLSInterval seconds ago, 3798 discard the new advertisement without acknowledging it. 3800 b) Otherwise, forward the new advertisement out some subset of 3801 the local interfaces (see Section 8.2.3). Note whether the 3802 advertisement was sent back out the receiving interface for 3803 later use by the acknowledgment process. 3805 c) Remove the current database copy from the Link state 3806 retransmission lists of all neighbors. 3808 d) Install the new advertisement in the link state database, 3809 replacing the current database copy. (Note that this may 3810 cause the calculation of the set of best paths to be 3811 scheduled. See Section 9.) Timestamp the new advertisement 3812 with the time that it was received to prevent installation 3813 of another instance within MinLSInterval seconds. 3815 e) Acknowledge the advertisement, if necessary, by sending a 3816 Link State Acknowledgment packet back out the receiving 3817 interface. (See Section 8.2.6.) 3819 f) If the link state advertisement was initially advertised by 3820 the local switch itself, advance the advertisement sequence 3821 number and issue a new instance of the advertisement. 3822 (Receipt of a newer instance of an advertisement means that 3823 the local copy of the advertisement is left over from 3824 before the last time the switch was restarted.) 3826 5. If the received advertisement is the same instance as the 3827 database copy (as determined by the algorithm described in 3828 Section 7.1.1), do the following: 3830 a) If the advertisement is listed in the neighbor's link state 3831 retransmission list, the local switch is expecting an 3832 acknowledgment for this advertisement. Treat the received 3833 advertisement as an implied acknowledgment, and remove the 3834 advertisement from the link state retransmission list. 3835 Note this implied acknowledgment for later use by the 3836 acknowledgment process (Section 8.2.6). 3838 b) Acknowledge the advertisement, if necessary, by sending a 3839 Link State Acknowledgment packet back out the receiving 3840 interface. (See Section 8.2.6.) 3842 6. If the database copy of the advertisement is more recent than 3843 the instance just received, do the following: 3845 a) Determine whether the instance is listed in the neighbor 3846 link state request list. If so, an error has occurred in 3847 the database exchange process. Restart the database 3848 exchange process by generating a neighbor BadLSReq event 3849 for the sending neighbor and terminate processing of the 3850 Link State Update packet. 3852 b) Otherwise, generate an unusual event to network management 3853 and discard the advertisement. 3855 8.2.3 Forwarding Link State Advertisements 3857 When a new instance of an advertisement is originated or after 3858 an incoming advertisement has been processed, the switch must 3859 decide over which interfaces and to which neighbors the 3860 advertisement will be forwarded. In some instances, the switch 3861 may decide not to forward the advertisement over a particular 3862 interface because it is able to determine that the neighbors on 3863 that attached link have or will receive the advertisement from 3864 another switch on the link. 3866 The decision of whether to forward an advertisement over each of 3867 the switch's interfaces is made as follows: 3869 1. Each neighboring switch attached to the interface is examined 3870 to determine whether it should receive and process the new 3871 advertisement. For each neighbor, the following steps are 3872 executed: 3874 a) If the neighbor state is less than Exchange, the neighbor 3875 need not receive or process the new advertisement. 3877 b) If the neighbor state is Exchange or Loading, examine the 3878 link state request list associated with the neighbor. If 3879 an instance of the new advertisement is on the list, the 3880 neighboring switch already has an instance of the 3881 advertisement. Compare the new advertisement to the 3882 neighbor's copy: 3884 o If the new advertisement is less recent, the neighbor 3885 need not receive or process the new advertisement. 3887 o If the two copies are the same instance, delete the 3888 advertisement from the link state request list. The 3889 neighbor need not receive or process the new 3890 advertisement.[7] 3892 o Otherwise, the new advertisement is more recent. Delete 3893 the advertisement from the link state request list. The 3894 neighbor may need to receive and process the new 3895 advertisement. 3897 c) If the new advertisement was received from this neighbor, 3898 the neighbor need not receive or process the advertisement. 3900 d) Add the new advertisement to the link state retransmission 3901 list for the neighbor. 3903 2. The switch must now decide whether to forward the new 3904 advertisement out the interface. 3906 a) If the link state advertisement was not added to any of the 3907 link state retransmission lists for neighbors attached to 3908 the interface, there is no need to forward the 3909 advertisement out the interface. 3911 b) If the new advertisement was received on this interface, 3912 and it was received from either the designated switch or 3913 the backup designated switch, there is no need to forward 3914 the advertisement out the interface. Chances are all 3915 neighbors on the attached network link have also received 3916 the advertisement already. 3918 Network layer addressing / VLSP header 3920 This 70-octet field contains the network layer addressing 3921 information and the standard VLS protocol packet header. The 3922 packet header type field contains a value of 4. 3924 # advertisements 3926 This 4-octet field contains the number of link state 3927 advertisements included in the packet. 3929 Link state advertisements 3931 This variable-length field contains a list of link state 3932 advertisements. For a detailed description of the different 3933 types of link state advertisements, see Section 11. 3935 10.6.5 Link State Acknowledgment Packets 3937 Link State Acknowledgment Packets are used to explicitly 3938 acknowledge one or more Link State Update packets, thereby 3939 making the distribution of link state advertisements reliable. 3940 (See Section 8.2.6.) 3942 The format of a Link State Acknowledgment packet is shown below. 3944 0 1 2 3 3945 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 3946 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3947 00 | | 3948 : Network layer addressing / VLSP header : 3949 | | 3950 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3951 70 | | 3952 + + 3953 : Link state advertisement headers : 3954 + + 3955 | | 3956 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3958 Network layer addressing / VLSP header 3960 This 70-octet field contains the network layer addressing 3961 information and the standard VLS protocol packet header. The 3962 packet header type field contains a value of 5. 3964 Link state advertisement headers 3966 This variable-length field contains a list of link state 3967 headers that are being acknowledged by this packet. Each 3968 header uniquely identifies a link state advertisement and its 3969 current instance. (See Section 11.1 for a detailed 3970 description of a link state advertisement header.) The 3971 number of headers included in the list is calculated 3972 implicitly from the length of the packet, as stored in the 3973 VLSP packet header (see Section 10.4). 3975 11. Link State Advertisement Formats 3977 Link state advertisements are used to describe various pieces of 3978 the routing topology within the switch fabric. Each switch in 3979 the fabric maintains a complete set of all link state 3980 advertisements generated throughout the fabric. (Section 8.1 3981 describes the circumstances under which a link state 3982 advertisement is originated. Section 8.2 describes how 3983 advertisements are distributed throughout the switch fabric.) 3984 This collection of advertisements, known as the link state (or 3985 topological) database, is used to calculate a set of best paths 3986 to all other switches in the fabric. 3988 There are two types of link state advertisement, as listed in 3989 Table 8. 3991 Type Name Function Description 3993 1 Switch link Lists all network Section 11.2 3994 advertisement linksattached to 3995 a switch 3997 2 Network link Lists all adjacen- Section 11.3 3998 advertisement cies on a network 3999 link 4001 Table 8: Link State Advertisement Types 4003 Each link state advertisement begins with a standard header, 4004 described in Section 11.1. 4006 11.1 Link State Advertisement Headers 4008 All link state advertisements begin with a common 32-octet 4009 header. This header contains information that uniquely 4010 identifies the advertisement -- its type, link state ID, and the 4011 switch ID of its advertising switch. Also, since multiple 4012 instances of a link state advertisement can exist concurrently 4013 in the switch fabric, the header contains information that 4014 permits a switch to determine which instance is the most recent 4015 -- the age, sequence number and checksum. 4017 The format of the link state advertisement header is shown 4018 below. 4020 0 1 2 3 4021 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 4022 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4023 00 | Age | Options | LS Type | 4024 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4025 04 | | 4026 + Link state ID + 4027 08 | | 4028 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4029 12 | | | 4030 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 4031 16 | | 4032 + Advertising switch ID + 4033 20 | | 4034 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4035 24 | Sequence number | 4036 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4037 28 | Checksum | Length | 4038 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4040 Age 4042 This 2-octet field contains the time, in seconds, since this 4043 instance of the link state advertisement was originated. 4045 Options 4047 This 1-octet field contains the optional capabilities 4048 supported by the advertising switch, as described in Section 4049 10.5. 4051 LS type 4053 This 1-octet field contains the type of the link state 4054 advertisement. Possible values are: 4056 1 Switch link advertisement 4057 2 Network link advertisement 4059 Link state ID 4061 This 10-octet field identifies the switch that originates 4062 advertisements for the link. The content of this field 4063 depends on the advertisement's type. 4065 o For a switch link advertisement, this field contains the 4066 switch ID of the originating switch 4068 o For a network link advertisement, this field contains the 4069 switch ID of the designated switch for the link 4071 Note 4073 In VLSP, the link state ID of an advertisement is 4074 always the same as the advertising switch. This level 4075 of redundancy results from the fact that OSPF uses 4076 additional types of link state advertisements for 4077 which the originating switch is not the advertising 4078 switch. 4080 Advertising switch 4082 This 10-octet field contains the switch ID of the switch that 4083 originated the link state advertisement. 4085 Sequence number 4087 This 4-octet field is used to sequence the instances of a 4088 particular link state advertisement. The number is 4089 incremented for each new instance. 4091 Checksum 4093 This 2-octet field contains the checksum of the complete 4094 contents of the link state advertisement, excluding the age 4095 field. The checksum used is commonly referred to as the 4096 Fletcher checksum and is documented in [RFC905]. Note that 4097 since this checksum is calculated for each separate 4098 advertisement, a protocol packet containing lists of 4099 advertisements or advertisement headers will contain multiple 4100 checksum values. 4102 Length 4104 This 2-octet field contains the total length, in octets, of 4105 the link state advertisement, including the header. 4107 11.2 Switch Link Advertisements 4109 A switch link advertisement is used to describe all functioning 4110 network links of a switch, including the cost of using each 4111 link. 4113 Each functioning switch in the fabric originates one, and only 4114 one, switch link advertisement -- all of the switch's links must 4115 be described in a single advertisement. A switch originates its 4116 first switch link advertisement (containing no links) when it 4117 first becomes functional. It then originates a new instance of 4118 the advertisement each time any of its neighbor states changes 4119 such that the contents of the advertisement changes. See 4120 Section 8.1 for details on originating a switch link 4121 advertisement. 4123 The format of a switch link advertisement is shown below. 4125 0 1 2 3 4126 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 4127 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4128 00 | | 4129 : Link state header : 4130 | | 4131 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4132 32 | (unused -- must be 0) | # links | 4133 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4134 36 | | 4135 + Link ID + 4136 40 | | 4137 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4138 44 | | | 4139 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 4140 48 | | 4141 + Link data + 4142 52 | | 4143 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4144 56 | Link type | # TOS | TOS 0 metric | 4145 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4146 60 | | 4147 : . . . : 4148 | | 4149 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4151 Link state header 4153 This 32-octet field contains the standard link state 4154 advertisement header. The type field contains a 1, and the 4155 link state ID field contains the switch ID of the advertising 4156 switch. 4158 # links 4160 This 2-octet field contains the number of links described by 4161 this advertisement. This value must be equal to the total 4162 number of functioning network links attached to the switch. 4164 Link ID 4166 This 10-octet field identifies the other switch that 4167 originates link state advertisements for the link, providing 4168 a key for accessing other link state advertisements for the 4169 link. The value here is based on the link type, as follows: 4171 o For point-to-point links, this field contains the switch ID 4172 of the neighbor switch connected to the other end of the 4173 link. 4175 o For multi-access links, this field contains the switch ID 4176 of the designated switch for the link. 4178 Link data 4180 This 10-octet field contains additional data necessary to 4181 calculate the set of best paths. Typically, this field 4182 contains the interface ID of the link. 4184 Link type 4186 This 1-octet field contains the type of link being described. 4187 Possible values are as follows: 4189 1 Point-to-point link 4190 2 Multi-access link 4192 # TOS 4194 This 1-octet field contains the number of nonzero type of 4195 service metrics specified for the link. Since the current 4196 version of VLSP does not support routing based on nonzero 4197 types of service, this field contains a value of zero. 4199 TOS 0 metric 4201 This 2-octet field contains the cost of using this link for 4202 the zero TOS. This value is expressed in the link state 4203 metric and must be greater than zero. 4205 Note that the last five fields are repeated for all functioning 4206 network links attached to the advertising switch. If the 4207 interface state of attached link changes, the switch must 4208 originate a new instance of the switch link advertisement. 4210 11.3 Network Link Advertisements 4212 A network link advertisement is originated by the designated 4213 switch of each multi-access network link. The advertisement 4214 describes all switches attached to the link that are currently 4215 fully adjacent to the designated switch, including the 4216 designated switch itself. See Section 8.1 for details on 4217 originating a switch link advertisement. 4219 Network link advertisements are not generated for point-to-point 4220 network links. 4222 The format of a network link advertisement is show below. 4224 0 1 2 3 4225 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 4226 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4227 00 | | 4228 : Link state header : 4229 | | 4230 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4231 32 | (unused) | 4232 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4233 36 | | 4234 + + 4235 : Switch list : 4236 + + 4237 | | 4238 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4240 Link state header 4242 This 32-octet field contains the standard link state 4243 advertisement header. The type field contains a 2, and the 4244 link state ID field contains the switch ID of the designated 4245 switch. 4247 Switch list 4249 The switch IDs of all switches attached to the network link 4250 that are currently fully adjacent to the designated switch. 4251 The designated switch includes itself in this list. 4253 12. Protocol Parameters 4255 This section contains a compendium of the parameters used in the 4256 VLS protocol. 4258 12.1 Architectural Constants 4260 Several VLS protocol parameters have fixed architectural values. 4261 The name of each architectural constant follows, together with 4262 its value and a short description of its function. 4264 AllSPFSwitches 4266 The multicast switch ID to which Hello packets and certain 4267 other protocol packets are addressed, as specified in the 4268 destination switch ID field of the network layer address 4269 information (see Section 10.3). The value of AllSPFSwitches 4270 is E0-00-00-05-00-00-00-00. 4272 AllDSwitches 4274 The multicast switch ID to which Link State Update packets 4275 and Link State Acknowledgment packets are addressed, as 4276 specified in the destination switch ID field of the network 4277 layer address information (see Section 10.3), when they are 4278 destined for the designated switch or the backup designated 4279 switch of a network link. The value of AllDSwitches is 4280 E0-00-00-06-00-00-00-00. 4282 LSRefreshTime 4284 The interval at which the set of best paths recalculated if 4285 no other state changes have forced a recalculation. The 4286 value of LSRefreshTime is set to 1800 seconds (30 minutes). 4288 MinLSInterval 4290 The minimum time between distinct originations of any 4291 particular link state advertisement. The value of 4292 MinLSInterval is set to 5 seconds. 4294 MaxAge 4296 The maximum age that a link state advertisement can attain. 4297 When an advertisement's age reaches MaxAge, it is 4298 redistributed throughout the switch fabric. When the 4299 originating switch receives an acknowledgment for the 4300 advertisement, indicating that the advertisement has been 4301 removed from all neighbor Link state retransmission lists, 4302 the advertisement is removed from the originating switch's 4303 database. Advertisements having age MaxAge are not used to 4304 calculate the set of best paths. The value of MaxAge must be 4305 greater than LSRefreshTime. The value of MaxAge is set to 4306 3600 seconds (1 hour). 4308 MaxAgeDiff 4310 The maximum time disparity in ages that can occur for a 4311 single link state instance as it is distributed throughout 4312 the switch fabric. Most of this time is accounted for by the 4313 time the advertisement sits on switch output queues (and 4314 therefore not aging) during the distribution process. The 4315 value of MaxAgeDiff is set to 900 seconds (15 minutes). 4317 LSInfinity 4319 The link state metric value indicating that the destination 4320 is unreachable. It is defined to be a binary value of all 4321 ones. 4323 12.2 Configurable Parameters 4325 Many of the switch interface parameters used by VLSP may be made 4326 configurable if the implementer so desires. These parameters 4327 are listed below. Sample default values are given for some of 4328 the parameters. 4330 Note that some of these parameters specify properties of the 4331 individual interfaces and their attached network links. These 4332 parameters must be consistent across all the switches attached 4333 to that link. 4335 Interface output cost(s) 4337 The cost of sending a packet over the interface, expressed in 4338 the link state metric. This is advertised as the link cost 4339 for this interface in the switch's switch link advertisement. 4340 The interface output cost must always be greater than zero. 4342 RxmtInterval 4344 The number of seconds between link state advertisement 4345 retransmissions for adjacencies established on this 4346 interface. This value is also used when retransmitting 4347 Database Description packets and Link State Request packets. 4348 This value must be greater than the expected round-trip delay 4349 between any two switches on the attached link. However, the 4350 value should be conservative or needless retransmissions will 4351 result. A typical value for a local area network would be 5 4352 seconds. 4354 InfTransDelay 4356 The estimated number of seconds it takes to transmit a Link 4357 State Update packet over this interface. Link state 4358 advertisements contained in the Link State Update packet must 4359 have their age incremented by this amount before 4360 transmission. This value must take into account the 4361 transmission and propagation delays for the interface and 4362 must be greater than zero. A typical value for a local area 4363 network would be 1 second. 4365 Switch priority 4367 An 8-bit unsigned integer. When two switches attached to the 4368 same network link contend for selection as the designated 4369 switch, the switch with the highest priority takes 4370 precedence. If both switches have the same priority, the 4371 switch with the highest base MAC address becomes the 4372 designated switch. A switch whose switch priority is set to 4373 zero is ineligible to become the designated switch on the 4374 attached link. 4376 HelloInterval 4378 The length of time, in seconds, between the Hello packets 4379 that the switch sends over the interface. This value is 4380 advertised in the switch's Hello packets. It must be the 4381 same for all switches attached to a common network link. The 4382 smaller this value is set, the faster topological changes 4383 will be detected. However, a smaller interval will also 4384 generate more routing traffic. A typical value for a local 4385 area network would be 10 seconds. 4387 SwitchDeadInterval 4389 The length of time, in seconds, that neighboring switches 4390 will wait before declaring the interface down once they stop 4391 receiving Hello packets over the interface. This value is 4392 advertised in the switch's Hello packets. It must be the 4394 same for all switches attached to a common network link and 4395 should be some multiple of the HelloInterval parameter. A 4396 typical value would be 4 times HelloInterval. 4398 13. Footnotes 4400 [1]During calculation of the set of best paths, a network link 4401 advertisement must be located based solely on its link state ID. 4402 Note, however, that the lookup in this case is still well 4403 defined, since no two network advertisements can have the same 4404 link state ID. 4406 [2]It is instructive to see what happens when the designated 4407 switch for a network link fails. Call the designated switch for 4408 the link S1 and the backup designated switch S2. If switch S1 4409 fails (or its interface to the link goes down), the other 4410 switches on the link will detect S1's absence within 4411 SwitchDeadInterval seconds. All switches may not detect this 4412 condition at precisely the same time. The switches that detect 4413 S1's absence before S2 does will temporarily select S2 as both 4414 designated switch and backup designated switch. When S2 detects 4415 that S1 is down, it will move itself to designated switch. At 4416 this time, the remaining switch with the highest switch priority 4417 will be selected as the backup designated switch. 4419 [3]Note that it is possible for a switch to resynchronize any of 4420 its fully established adjacencies by setting the neighbor state 4421 back to ExStart. This causes the switch on the other end of the 4422 adjacency to process a SeqNumberMismatch event and also revert 4423 to the ExStart state. 4425 [4]When two advertisements have different checksum values, they 4426 are assumed to be separate instances. This can occur when a 4427 switch restarts and loses track of its previous sequence number. 4428 In this case, since the two advertisements have the same 4429 sequence number, it is not possible to determine which 4430 advertisement is actually newer. If the wrong advertisement is 4431 accepted as newer, the originating switch will originate another 4432 instance. 4434 [5]An instance of an advertisement is originated with an age of 4435 MaxAge only when it is to be flushed from the database. This is 4436 done either when the advertisement has naturally aged to MaxAge, 4437 or (more typically) when the sequence number must wrap. 4438 Therefore, a received instance with an age of MaxAge must be 4439 processed as the most recent in order to flush it properly from 4440 the database. 4442 [6]MaxAgeDiff is an architectural constant that defines the 4443 maximum disparity in ages, in seconds, that can occur for a 4445 single link state instance as it is distributed throughout the 4446 switch fabric. If two advertisements differ by more than this 4447 amount, they are assumed to be different instances of the same 4448 advertisement. This can occur when a switch restarts and loses 4449 track of its previous sequence number. 4451 [7]This is how the link state request list is emptied, causing 4452 the neighbor state to change to Full. 4454 14. Security Considerations 4456 Security issues are not discussed in this document. 4458 15. References 4460 [Perlman] Perlman, Radia. Interconnections: Bridges and 4461 Routers. Addison-Wesley Publishing Company. 1992. 4463 [RFC905] McKenzie, A., ISO Transport Protocol specification 4464 ISO DP 8073. April 1984. 4466 [RFC1583] Moy, J. OSPF Version 2. March 1994. 4468 [RFC1700] Reynolds, S.J., Postel, J. Assigned Numbers. 4469 October 1994. 4471 [IDsfvlan] Ruffen, D., et. al. Cabletron's SecureFast VLAN 4472 Operational Model. 4474 [IDhello] Hamilton, D., et. al. Cabletron's VlanHello Protocol 4475 Specification. 4477 16. Author's Address 4479 Cabletron Systems, Inc., is located at: 4481 Post Office Box 5005 4482 Rochester, NH 03866-5005 4483 (603) 332-9400 4485 Laura Kane Email: lkane@ctron.com 4487 17. Full Copyright Statement 4489 Copyright (C) The Internet Society (1998). All Rights Reserved. 4491 This document and translations of it may be copied and furnished 4492 to others, and derivative works that comment on or otherwise 4493 explain it or assist in its implementation may be prepared, copied, 4494 published and distributed, in whole or in part, without restriction 4495 of any kind, provided that the above copyright notice and this 4496 paragraph are included on all such copies and derivative works. 4497 However, this document itself may not be modified in any way, such 4498 as by removing the copyright notice or references to the Internet 4499 Society or other Internet organizations, except as needed for the 4500 purpose of developing Internet standards in which case the 4501 procedures for copyrights defined in the Internet Standards process 4502 must be followed, or as required to translate it into languages 4503 other than English. 4505 The limited permissions granted above are perpetual and will not be 4506 revoked by the Internet Society or its successors or assigns. 4508 This document and the information contained herein is provided on an 4509 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 4510 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 4511 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 4512 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 4513 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE." 4515 INTERNET DRAFT EXPIRES JUNE 1999 INTERNET-DRAFT