$Id$ HSLS Protocol Specification I. HSLS Protocol Packets HSLS messages are IP/UDP datagrams, with UDP datagram type TBD. The HSLS Header, defined below, immediately follows the UDP header. The Payload follows the Header. A variable-length array of Metric Numbers, called the Metric Sequence, follows the Payload. There are zero or more Metric Numbers in the sequence; the Metric Sequence Length in the Header tells how many. Packet extensions may follow the Metric Sequence. 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | : Header : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | : Payload : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | : Metric Sequence : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | : Extensions : : (optional) : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ There are three different payload types: they are Database Synchronization, Hellos, and Link State Updates. Payloads are described in section HSLS Packet Payloads. II. HSLS Packet Header 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Version|Rsvd 0 | Payload Type | Payload Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Extensions Length | Originating ifIndex | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Family Count | Reserved 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Version: Always 0. If the HSLS packet format changes in an incompatible way, packets in the new format will use a different Version than 0. An implementation of HSLS Packet Format Version 0 MUST discard HSLS packets whose Version is not 0. Rsvd 0: Must be 0. Payload Type: Payload type code. Eligible type codes are 0 - Database Synchronization, 1 - Hello messages, and 2 - Link State Updates. Payload Length: length of the payload in 32-bit words. Extensions Length: length of the packet extensions in 32-bit words. Family Count: number of address families in the payload. Hellos and Link State Updates can carry routing information for one or more address families. The Family Count tells how many address families are present. See Sections V.A. and V.B. Originating ifIndex: the IfIndex (in the SNMP MIB) for the router interface that originated this routing message. Reserved 1: Must be 0. III. HSLS Packet Extensions 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Extension Length | Extension Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Extension Value ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : : : If the Extensions Length in the HSLS Header is non-zero, then HSLS Packet Extensions are present after the Metric Sequence. Extensions are length-type-value tuples: an extension begins with a Length, given in 32-bit words. An Extension Type follows the Length. The extension value follows the Extension Type. The Internet Assigned Numbers Authority will keep the Extension Types standard. The size of the extension, including Length and Extension Type fields, is stored in Length. The Extension Types are defined elsewhere. IV. HSLS LSA Types Link State Advertisement (LSA) types are - Backplane LSAs, - External LSAs, - Network LSAs, - Opaque LSAs, and - Router LSAs. The HSLS protocol allows for all LSAs but Opaque LSAs to carry one or more 32-bit metrics. Not every LSA is sent in every LSU packet; only the "deltas." If an LSA is "missing" from an LSU, that does not mean the link should be deleted from the database; only a DOWN LSA can indicate that. Backplane LSA --------- --- A router originates a Backplane Link State Advertisement (LSA) to list all of its interfaces and their addresses. A router's Backplane LSA also tells its primary interface address. (LSAs are originated using the router's address.) In the future, a Backplane LSA may be used to assign costs to paths "across the backplane" from interface to interface, to facilitate least-interference routing over multiple channels. External LSA -------- --- External LSAs indicate networks that are injected from either a different routing instance (a second HSLS program) or a different protocol (for example, OSPF). Network LSA ------- --- Network LSAs list all of the routers belonging to a broadcast network. Only the Designated Router on a broadcast network may originate the Network LSA. Opaque LSA ------ --- An HSLS router MAY originate Opaque LSAs for client protocols that want to use HSLS messages for limited dissemination of information. An HSLS router MAY notify clients of Opaque LSAs' arrival, and it MAY provide its Opaque LSA database for clients' perusal. An HSLS router MUST forward Opaque LSAs regardless of type. Router LSA ------ --- For all link types but Broadcast links, an HSLS router originates a Router LSA for each of its one-hop neighbors. For broadcast links, an HSLS router originates a Router LSA, but it does not originate an LSA for each of its one-hop neighbors. V. HSLS Packet Payload In an HSLS Packet, the Payload begins directly after the Header. V.A. HSLS Hello HSLS Hellos are payloads of Payload Type 1. An HSLS router puts all of its Router and Network LSAs into the Hello Payload. Some of its Opaque LSAs may also be advertised, depending on the preferences of the Opaque LSA originators. A Hello Payload can carry LSAs for more than one address family. Every address family's LSAs appear together, following an Address Family Header that tells the family and length of addresses to follow. The Address Family Header is described in V.C.1. The number of Address Family Headers MUST match the number of Family Count specified in the Packet Header (section II). 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |HExponent| Hello Mantissa | DR Preference | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Dead Interval | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Address Family Header | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSA | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSA | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Address Family Header | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSA | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSA | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : : : Hello Interval: The Hello Interval is equal to Hello Mantissa * 2**HExponent milliseconds. The HExponent is in 2s-complement form. The Hello Mantissa is unsigned. DR Preference: Designated Router election preference, 0 means "never." Reserved: Must be 0. Dead Interval: number of Hello Intervals before the link is dead. V.B. HSLS Link State Update Payload 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Master Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |q|r| Flags | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hop Count | Hop Limit | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Address Family Header | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSA | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSA | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Address Family Header | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSA | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSA | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : : : Master Sequence Number: a router increases this number by one after every LSA transmission. It is used to detect duplicate LSU Packets. Flags: modify the interpretation of this LSU. A router sets the Bootstrap Request bit (bit 0, labeled 'q') to indicate that it needs for its 1-hop neighbors to send their databases. A router sets the Bootstrap Response bit (bit 0, labeled 'r') to indicate that its LSU is intended as a response to a router's prior Bootstrap Request. Hop Count: hops this LSU Packet has made so far. Hop Limit: hops remaining. If 0 or 1, the LSU may not be re-transmitted. A router MUST NOT forward a packet with Hop Limit equal to 0 or 1. Before a router retransmits a message, the Hop Limit MUST be decremented by 1. A router MUST increment Hop Count by 1 before it retransmits a packet. V.C. HSLS LSU/Hello Payloads: Address Family Headers and LSAs Both Link State Updates and Hello Packets contain one or more LSAs belonging to one or more address families. An LSU/Hello Payload MUST contain precisely as many Address Family Headers as the Family Count in the HSLS Packet Header indicates. V.C.1. Address Family Header 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Family |Address Length | LSA Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : Originator Address : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ An Address Family Header tells the number and interpretation of the LSAs that follow. It also tells the address assigned to the router interface that transmitted the header. The Family field tells whether the addresses that follow, including the Originator Address, are IPv4 (0x00) or IPv6 (0x01) addresses. All other values of the Family field (0x02-0xFF) are reserved. Address Length tells how long the addresses are, in 32-bit words. Addresses are left-aligned, zero-padded to 32-bit boundaries. See Section VI, "Interface Address Format," below. LSA Count tells how many LSAs follow the header. It is 0 or greater. V.C.2. HSLS LSA Format 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSA Type | LSA Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : LSA Content : : . . . : : : LSA Type: Backplane (HSLS_LSA_T_BPL = 0), External (HSLS_LSA_T_EXT = 1), Network (HSLS_LSA_T_NET = 2), Opaque (HSLS_LSA_T_OPQ = 3), Router (HSLS_LSA_T_RTR = 4) LSA Length: LSA length in 32-bit words. LSA Content: LSA Type-dependent content. V.C.3. Backplane LSA (ah_type == HSLS_LSA_T_BPL) 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSA Type | LSA Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Flags | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Interface Count | Primary Interface Offset | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Interconnect Count | Metric Count | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Interface Record | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Interface Record | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Interconnect Record | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Interconnect Record | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : : : Sequence Number: uniquely identifies this instance of the LSA. Increases by one with changes. Flags: indicates properties of this LSA. None defined yet. Interface Count: following the header, there are this many Interface Records. Primary Interface Offset: following the header, skip forward by this many Interface Records to the record for the Primary Interface Interconnect Count: following the header, there are this many Interconnect Records. Metric Count: The Metric Count is 0 or greater. It indicates the number of Metrics in each Interconnect Record. See "Metrics," Section VII. Reserved: must be 0. V.C.3.a. Backplane LSA -- Interface Record +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | IfIndex | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : Interface Address : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ V.C.3.b. Backplane LSA -- Interconnect Record An Interconnect Record indicates connectivity on the router backplane. This will be used for least-interference routing on multiple-channel networks. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | IfIndex 1 | IfIndex 2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Metrics N-Tuple | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ V.C.4. External LSA (ah_type == HSLS_LSA_T_EXT) 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSA Type | LSA Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |u|b| Flags | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Metric Count | Reserved 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Metrics N-Tuple | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Mask Length | IfIndex | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : Interface Address : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : Destination Address : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Sequence Number: uniquely identifies this instance of the LSA. Increases by one with each change to the LSA. Flags: indicate whether the route is activated (HSLS_LSA_F_UP, bit 0, labeled 'u'), and/or bi-directional (HSLS_LSA_F_BIDIR, bit 1, labeled 'b'). Metric Count: The Metric Count is 0 or greater. It indicates the number of Metrics in this External LSA. See "Metrics," Section VII. Reserved 1: Must be 0. Mask Length: The length of the netmask on this route, if this is a network route. Set equal to Address Length if it is a host route. IfIndex: The interface where this route is attached. Destination Address: The destination of this route. V.C.5. Network LSA (ah_type == HSLS_LSA_T_NET) V.C.5.a. Network LSA Header 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSA Type | LSA Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |u|b| Flags | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Metrics N-Tuple | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Count | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Mask Length | IfIndex | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : Interface Address : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Record | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Record | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : : : Sequence Number: uniquely identifies this instance of the LSA. Increases by one with each change to the LSA. Flags: indicate whether the route is activated (HSLS_LSA_F_UP, bit 0, labeled 'u') and bi-directional (HSLS_LSA_F_BIDIR, bit 1, labeled 'b'). Neighbor Count: Indicates the number of directly-connected neighbors on this network. This many Neighbor Records follow the LSA header. Reserved: Must be 0. Mask Length: The length of the netmask on this route, if this is a network route. Set equal to Address Length if it is a host route. IfIndex: The interface where this route is attached. Interface Address: The address on the interface for this network. V.C.5.b. Network LSA -- Neighbor Record +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |u|b| Flags | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : Neighbor Address : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Flags: The neighbor is connected---HSLS_LSA_F_UP, bit 0, labeled 'u'---and the connection is bi-directional, HSLS_LSA_F_BIDIR, bit 1, labeled 'b'. Neighbor Address: Address of a directly-connected neighbor on this network. V.C.6. Opaque LSA (ah_type == HSLS_LSA_T_OPQ) 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSA Type | LSA Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |u| Flags | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Payload Type | Payload Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Instance Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : Originator Address : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Payload | : : Sequence Number: uniquely identifies this instance of the LSA. Increases by one with each change to the LSA. Flags: HSLS_LSA_F_UP, bit 0, labeled 'u': the Opaque LSA is current. Otherwise, the Opaque LSA content is not current, and the LSA is eligible to be purged from the databases of receiving routers. A router MAY omit the Payload from an Opaque LSA whose 'u' bit is not set; the Length field MUST reflect the omission. Payload Type: Opaque payload-type identifier. Used to dispatch Opaque LSAs to applications. Payload Length: Payload length in bytes, measured from the end of the Originator Address field. Instance Number: Unique instance identifier for this Opaque LSA. A router MUST distinguish two different Opaque LSAs of the same type, originated by the same router, by comparing their instance number. A router SHOULD NOT distinguish two different Opaque LSAs by their Payload. Originator Address: Address of the router that originated this Opaque LSA. Payload: Application defined payload. Zero-padded to a 32-bit boundary. The Payload Length does not include the padding. V.C.7. Router LSA (ah_type == HSLS_LSA_T_RTR) 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSA Type | LSA Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Interface Count | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Interface Record | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Interface Record | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : : : Interface Count: how many Interface Records follow the header. Reserved: must be 0. V.C.7.a. Router LSA -- Interface Record 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Flags | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Interface Type| Metric Count | Neighbor Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Mask Length | ifIndex | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : Interface Address : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Record | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Record | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : : : Flags: no flags are defined, yet. Interface Type: Broadcast (HSLS_NET_T_BCAST = 0), Point-to-Multipoint (HSLS_NET_T_PTMP = 1), Point-to-Point (HSLS_NET_T_PTP = 2), Stub (HSLS_NET_T_STUB = 3). Metric Count: The Metric Count is 0 or greater. It indicates the number of Metrics in each Neighbor Record inside of this Interface Record. See "Metrics," Section VII. Neighbor Count: 0 is permitted for STUB networks; 0 is required for BCAST networks. 1 or greater required for PTMP, PTP. Mask Length: The length of the netmask on this route, if this is a network route. Set equal to Address Length if it is a host route. ifIndex: the interface index for the advertising router's end of the link Interface Address: the interface address on the advertising router's end of the link V.C.7.b. Router LSA -- Neighbor Record +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |u|b| Flags | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Metrics N-Tuple | : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : Neighbor Address : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Sequence Number: uniquely identifies this instance of the Neighbor Record. Increases by one with each change to the Neighbor Record. Flags: The neighbor is connected---HSLS_LSA_F_UP, bit 0, labeled 'u'---and the connection is bi-directional---HSLS_LSA_F_BIDIR, bit 1, labeled 'b'. Metrics N-Tuple: Neighbor Address: V.D. HSLS Database Synchronization Payload [way out of date; use Database Bootstrap description from e-mail -dcy] HSLS routers use Database Synchronization packets to summarize their link-state databases for synchronization purposes. This functional description is a work in progress. "On broadcast networks, synchronization works similarly to IS-IS, insofar as I understand how IS-IS works: when router X joins a broadcast net, it multicasts its link-state summary in one or more DSs. Call X a Synchronization Initiator. Call the exchange of DS messages that it initiates, a Synchronization Session. Identify the session by the main address of the Initiator, and the packet sequence number, seqno, with which X sends its DS messages. Call the tuple (Initiator, Sequence Number) a Synchronization Session Identifier, SSI. The Initiator's peers respond: they ask for link states that the Initiator holds, with greater sequence numbers than their own. They also indicate to the Initiator which link states they hold, which are newer than the ones held by the Initiator. Routers listen to DS messages "promiscuously," using any DS to update their own database. Thus it takes only O(n) DS messages for n peers to synchronize on a broadcast network. Compare with O(n^2) for OSPF synchronization. "During synchronization, routers re-transmit LSUs 'in the usual way.' For any given Synchronization Session, a router MUST not summarize any LSU that arrived after the router first received a DS in the session. "A router may assume that if it receives a multicast LSU from a router that is adjacent to it on a broadcast network, then every other router on that broadcast network has received the same LSU. So it can take off its list of LSAs to multicast on that network, any LSA that it hears an adjacent router send. "Synchronization on a point-to-multipoint net is different from synchronization on a broadcast network. A router cannot blithely assume that every adjacent router has received every multicast packet that it has received. (There will be hidden nodes.) So a router cannot take off its list of LSAs to multicast on a point-to-multipoint network, the LSAs that adjacent routers have already sent. "During a Synchronization Session, a router will delay for anywhere from 0 to 2^n Delay Units (see Section IX, "HSLS MIB") from the time it hears a DS message and the time that it responds with a DS or LSU." VI. Interface Address Format Addresses are right-padded with zeroes. So a 48-bit Ethernet MAC address is loaded into a packet like this, 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | octet 0 | octet 1 | octet 2 | octet 3 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | octet 4 | octet 5 |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ For example, 00:07:5c:26:e9:9c is loaded in this way, 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 00 | 07 | 5c | 26 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | e9 | 9c |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ An IPv4 address, a.b.c.d, is loaded like this, 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | a | b | c | d | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ An IPv6 address, dead::f00d, is loaded like this, 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | de | ad | 0 | 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0 | 0 | 0 | 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0 | 0 | 0 | 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 00 | 00 | f0 | 0d | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ VII. Metrics N-Tuple In HSLS, link characteristics are given by an Metrics N-Tuple. The Metric Sequence tells the content of the Metrics N-Tuple. See "Metrics," section VII. Each Metric Number is at least one octet long. See "Metric Number Definitions," Section VIII, below. A router MAY set Metric Count to zero (0). A router MUST omit Metrics N-Tuples when Metric Count equals 0. See below. The author expects for this protocol to be used commonly on ad hoc wireless networks. A wireless link's suitability to bear traffic can be described by several metrics, which are not limited to bit-error rate, packet-error rate, delay, jitter, and hop count. It may be useful for a router to use more than one metric to select the "best" routes on a wireless network. For this reason, the protocol is designed to carry more than one metric for each link in a Metrics N-Tuple. The HSLS protocol provides 32 bits for each metric. A router indicates the length and content of its Metric N-Tuples with the Metric Count and the Metric Sequence, which are described in Section II and Section I, respectively. The Metric Sequence in a HSLS Protocol Packet tells how many metrics are in the packet's Metrics N-Tuples, the order and meanings of the metrics. Metric meanings are indicated by assigned numbers called Metric Numbers. See Section VII, "Metric Number Definitions," for tentative Metric Number assignments. This document defines two operations on Metric N-Tuples, resolution, addition, and comparison. Before two Metric N-Tuples with different length or content can be added or compared, their length and content must be reconciled. [Describe reconciliation.] After the length and content of two Metric N-Tuples are reconciled, they have the same length, and the same Metric Number names the the content at the same position in both N-Tuples. Two Metric N-Tuples, A and B, whose content is [A1, ..., An] and [B1, ..., Bn], respectively, add element-wise to produce the sum [A1 + B1, ..., An + Bn]. Two Metric N-Tuples, A = [A1, ..., An], B = [B1, ..., Bn], are compared lexicographically. The lexicographical comparison has this recursive definition, Compare([], []) -> "equal" Compare([A1] | A-remaining, [B1] | B-remaining) -> "less than" if A1 < B1, or -> "greater than" if A1 > B1, otherwise -> Compare(A-remaining, B-remaining) Metrics take values in [0, 0xFFFFFFFF]. A directed network path's Metric N-Tuple is equal to the sum of the Metric N-Tuples on all the links on the path. An HSLS router MUST choose the network path from itself to each destination that has the "least" Metric N-Tuple according to the Compare function. When a router receives an HSLS Packet with Metric Count set equal to 0, it MUST attribute to every LSA contained therein a metrics n-tuple consisting solely of the Hop Count metric set equal to 1. VIII. Metric Number Definitions Ten Metric Numbers are tentatively defined. An extension format for Metric Numbers is also tentatively defined. Metric Number Metric Name Description ------ ------ ------ ---- ----------- 0x0000 Hop Count Every link's Hop Count metric is equal to 1. A router MAY indicate the presence of the Hop Count metric in the Metric Sequence field of a HSLS Protocol Packet. A router MUST NOT reserve a slot in an Metrics N-Tuple for the Hop Count. 0x0001 External 1 External 1 through 8 are 0x0002 External 2 for routes imported from 0x0003 External 3 another HSLS instance, or 0x0004 External 4 else from another routing 0x0005 External 5 protocol, such as OSPF or 0x0006 External 6 BGP. 0x0007 External 7 0x0008 External 8 0x0009 Experimental 1 External 1 through 8 are 0x000a Experimental 2 for routes imported from 0x000b Experimental 3 another HSLS instance, or 0x000c Experimental 4 else from another routing 0x000d ETX Estimated Transmission Count: roughly, the link's ETX metric is proportional to the log-probability that the link drops a packet or its acknowledgement. An 802.11-like link is assumed. 0x000e Latency [I will let some routing wizard define this in a satisfactory way. -Ed.] 0x000f Jitter [I will let some routing wizard define this in a satisfactory way. -Ed.] 0xFF00-0xFFFF Internal Reserved for router-internal use. IX. HSLS MIB I have only just begun the HSLS MIB. Read/Write ---------- delay_units hello_interval tick_interval address-family (inet, inet6, link).ifindex (>= 1).type (bcast, ptmp, ptp, stub) .name (wi0, ath0, ...) .addr (1.2.3.4, fe80::dead:f00d) .masklen (optional) Read ---- network_diameter $Id$