[Cu-wireless] HSLS protocol packet format (DRAFT 0)
David Young
dyoung at pobox.com
Thu May 6 16:43:34 CDT 2004
Here are HSLS protocol packet formats, described using pseudo-C.
This is a work in progress. Send me your feedback, please. You will
notice right off the bat that this resembles OSPF.
The backplane LSAs might throw you. They have two purposes. First,
they associate all the interface addrs with a "main" address---see the
OLSR MID message. Second, Backplane LSAs help support least-interference
routing on routers with multiple interfaces. I don't intend to program
that feature right off the bat.
I allow for one or more 32-bit metrics, which might be overkill. I am
concerned that the LSAs are heavyweight, regardless. FWIW, I don't intend
to send every LSA in every LSU packet; but only the "deltas." If an LSA
is "missing" from an LSU, that does not mean the link should be deleted
from the database; only an LSA with the DOWN flag set can indicate that.
There are Database Synchronization (DS) messages in there. On broadcast
networks, I intend for synchronization to work similarly to IS-IS,
insofar as I understand how IS-IS does it: basically, 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 it by the main address
of X, and the packet sequence number, seqno, with which X sends its DSs.
Call the tuple (X, seqno) a Synchronization Session Identifier, SSI.
X's peers respond: they ask for the link states newer than their own
that X holds. They also indicate link states that are newer than the
ones held by X. Peers 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.
During synchronization, routers re-transmit LSUs "in the usual way."
For any given Sync Session, a router MUST not summarize any LSU that
arrived after the router first received a DS in the session.
Synchronization on a point-to-multipoint net is a little more complicated,
than on a broadcast network, but I think that I have it figured out.
Regarding authentication, I have thought about doing it the OSPF way,
with an MD5 sum of (message|sequence number|shared secret), but that
does not really solve any problems on an open network.
Dave
--
David Young OJC Technologies
dyoung at ojctech.com Urbana, IL * (217) 278-3933
-------------- next part --------------
$Id: hsls-protocol 496 2004-04-28 03:17:12Z dyoung $
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 one-byte
metric indices follows the Payload. There is at least one index
in the array; the Metric Indices Count in the Header tells how
many. Packet extensions may follow the Metric Indices.
+--------+---------+----------------+-----------------+
| Header | Payload | Metric Indices | opt(Extensions) |
+--------+---------+----------------+-----------------+
There are six different payload types: they are Database Descriptions,
Hellos, Link State Requests, and Link State Updates. Payloads are
described in section HSLS Packet Payloads.
II. HSLS Packet Header
#define ONE_OR_MORE 1
#define ZERO_OR_MORE 1
struct hsls_hdr {
u_int8_t hh_version; /* version: 0. */
u_int8_t hh_type; /* payload type: Hello,
* Link State Update,
* Database Synchronization, Hello
*/
#define HSLS_PAYL_T_DSYNC 0
#define HSLS_PAYL_T_HELLO 1
#define HSLS_PAYL_T_LSUPD 2
u_int16_t hh_extlen; /* Extensions Length: length of the
* extensions in bytes.
*/
u_int16_t hh_paylen; /* Payload Length: length of the
* payload in bytes.
*/
u_int8_t hh_nmetric; /* Metric Indices Count, 0 or greater.
*/
u_int8_t hh_nfamily; /* Family Count: number of address
* families in the payload.
*/
u_int16_t hh_ifindex; /* originating interface */
u_int16_t hh_reserved0; /* must be 0 */
};
hh_version is always set to 0. If the HSLS packet format changes
in an incompatible way, packets in the new format will use a
different hh_version than 0. An implementation of HSLS Packet
Format Version 0 MUST discard HSLS packets whose hh_version is not
0.
hh_type is the payload type code. Eligible type codes are
HSLS_PAYL_T_DSYNC (0), for Database Synchronization;
HSLS_PAYL_T_HELLO (1), for Hello messages;
HSLS_PAYL_T_LSUPD (2), for Link State Updates.
hh_paylen and hh_extlen tell the length of the payload and the
packet extensions, respectively.
hh_nmetric is called the Metric Indices Count. It is 0 or greater.
It indicates the number of Metric Indices that follow the payload.
Each metric index is a byte. The order of metric indices is
significant. See section TBD, below.
III. HSLS Packet Extensions
If the Extensions End in the HSLS Header is not equal to the Header
End, then HSLS Packet Extensions are present after the last metric
index. Extensions are length-type-value tuples: an extension begins
with a 16-bit Length. A 16-bit Extension Type follows the Length.
The extension value follows the Extension Type.
The size of the extension, including Length and Extension Type
fields, is stored in Length. The Extension Types are defined
elsewhere.
IV. HSLS Packet Payload
In an HSLS Packet, the Payload begins directly after the Header.
IV.A. HSLS Database Synchronization Payload
struct hsls_bpllsa_summary {
u_int32_t bs_seqno;
u_int8_t bs_origin[ONE_OR_MORE];
};
struct hsls_extlsa_summary {
u_int32_t es_seqno;
u_int8_t es_ifaddr[ONE_OR_MORE];
u_int8_t es_dstaddr[ONE_OR_MORE];
};
struct hsls_netlsa_summary {
u_int32_t ns_seqno;
u_int16_t ns_masklen;
u_int8_t ns_ifaddr[ONE_OR_MORE];
};
struct hsls_opqlsa_summary {
u_int32_t no_seqno;
u_int32_t no_instance;
u_int16_t no_type;
};
struct hsls_rtrlsa_summary {
u_int32_t rs_seqno;
u_int8_t rs_ifaddr[ONE_OR_MORE];
u_int8_t rs_dstaddr[ONE_OR_MORE];
};
struct hsls_lsa_summary {
u_int16_t ls_type;
#define HSLS_LSA_T_BPL 0
#define HSLS_LSA_T_EXT 1
#define HSLS_LSA_T_NET 2
#define HSLS_LSA_T_OPQ 3
#define HSLS_LSA_T_RTR 4
union {
struct hsls_bpllsa_summary su_bpl;
struct hsls_extlsa_summary su_ext;
struct hsls_netlsa_summary su_net;
struct hsls_opqlsa_summary su_opq;
struct hsls_rtrlsa_summary su_rtr;
} ds_u;
#define ds_bpl ds_u.su_bpl
#define ds_ext ds_u.su_ext
#define ds_net ds_u.su_net
#define ds_opq ds_u.su_opq
#define ds_rtr ds_u.su_rtr
};
struct hsls_dsynch_hdr {
u_int32_t dh_dseqno;
u_int16_t dh_flags;
#define HSLS_DSYNCH_F_MORE 0x1 /* More DSYNCH packets that describe
* this database will follow.
*/
u_int16_t dh_nreq;
u_int16_t dh_noffer;
u_int8_t dh_family; /* address family: IPv4, ... */
u_int8_t dh_addrlen; /* address length in bytes */
/* Primary address of the router who began this database
* synchronization conversation.
*/
u_int8_t dh_originator[ONE_OR_MORE];
/* Address of the host that should answer the enclosed LSA requests. */
u_int8_t dh_reqdest[ONE_OR_MORE];
/* Requested LSAs. */
struct hsls_lsa_summary dh_reqs[ZERO_OR_MORE];
/* Offered LSAs. */
struct hsls_lsa_summary dh_offers[ZERO_OR_MORE];
};
IV.B. HSLS Hello Payload
struct hsls_af_hdr {
u_int8_t uh_family; /* address family: IPv4, IPv6, 802.3 */
u_int8_t uh_addrlen; /* address length in bytes */
u_int16_t uh_nlsa; /* number of LSAs in this family */
u_int8_t uh_origin[ONE_OR_MORE]; /* primary address of the LSU's
* originating router
*/
};
struct hsls_hello_hdr {
/* hello interval = mantissa * 2**exponent milliseconds */
int16_t hh_interval;
#define HSLS_HINTVL_EXPONENT_MASK 0xf800
#define HSLS_HINTVL_MANTISSA_MASK 0x07ff
/* number of hello intervals before the link is dead. */
u_int32_t hh_dead_intervals;
/* Number of address families in this Hello. */
u_int16_t hh_naf;
/* Header for first address family. */
struct hsls_af_hdr hh_af;
/*
* Router and Network LSAs follow each address family header.
* Opaque LSAs may also follow.
*/
};
IV.C. HSLS Link State Update Payload
struct hsls_lsu_hdr {
u_int32_t uh_mseqno; /* master sequence number */
u_int16_t uh_hopcount; /* hops made so far */
u_int16_t uh_hoplimit; /* hops remaining. if 0 or 1,
* the LSU may not be
* retransmitted
*/
struct hsls_af_hdr uh_af_hdr;
};
uh_af indicates the address family that the link addresses belong
to. IPv4, IPv6, and Link-Level families are available choices.
uh_addrlen tells how long the addresses are, in bytes.
IV.C.1. HSLS LSA Types
Link State Advertisement (LSA) types are
HSLS_LSA_T_BPL = 0, Backplane LSAs;
HSLS_LSA_T_EXT = 1, External LSAs;
HSLS_LSA_T_NET = 2, Network LSAs;
HSLS_LSA_T_OPQ = 3, Opaque LSAs; and
HSLS_LSA_T_RTR = 4, Router LSAs.
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 each of its one-hop neighbors on a non-broadcast link,
a HSLS router originates a Router LSA. For each of its
broadcast interfaces, an HSLS router originates a Router
LSA, but it does originate an LSA for each of its one-hop
neighbor.
IV.C.2. HSLS LSA Format
struct hsls_lsa_hdr {
u_int16_t ah_type; /* LSA type */
#define HSLS_LSA_T_BPL 0
#define HSLS_LSA_T_EXT 1
#define HSLS_LSA_T_NET 2
#define HSLS_LSA_T_OPQ 3
#define HSLS_LSA_T_RTR 4
u_int16_t ah_len; /* LSA length */
};
IV.C.3. Backplane LSA (ah_type == HSLS_LSA_T_BPL)
struct hsls_bpllsa_hdr {
u_int32_t bh_seqno; /* sequence number */
u_int32_t bh_flags;
u_int16_t bi_primary; /* index of primary address in
* bh_ifaces, below.
*/
u_int16_t bh_niface;
struct hsls_bpllsa_if {
u_int16_t bi_ifindex;
u_int8_t bi_ifaddr[ONE_OR_MORE];
} bh_ifaces[ONE_OR_MORE];
/* for future use */
u_int16_t bh_nlink; /* 0 for now. */
struct hsls_bpllsa_link {
u_int32_t bl_metrics[ZERO_OR_MORE];
u_int16_t bl_ifindex[2];
} bh_links[ZERO_OR_MORE];
};
IV.C.4. External LSA (ah_type == HSLS_LSA_T_EXT)
struct hsls_extlsa_hdr {
u_int32_t eh_seqno; /* sequence number */
u_int32_t eh_flags;
#define HSLS_LSA_F_UP 0x1
#define HSLS_LSA_F_BIDIR 0x2
u_int32_t eh_metrics[ZERO_OR_MORE];
u_int16_t eh_ifindex;
u_int16_t eh_masklen;
u_int8_t eh_ifaddr[ONE_OR_MORE];
u_int8_t eh_dstaddr[ONE_OR_MORE];
};
IV.C.5. Network LSA (ah_type == HSLS_LSA_T_NET)
struct hsls_netlsa_hdr {
u_int32_t nh_seqno; /* sequence number */
u_int16_t nh_nneighbor;
u_int16_t nh_masklen;
u_int16_t nh_ifindex;
u_int8_t nh_ifaddr[ONE_OR_MORE];
struct hsls_netlsa_neighbor {
u_int32_t nn_flags;
#define HSLS_LSA_F_UP 0x1
#define HSLS_LSA_F_BIDIR 0x2
u_int8_t nn_nbraddr[ONE_OR_MORE];
} nh_neighbors[ONE_OR_MORE];
};
IV.C.6. Opaque LSA (ah_type == HSLS_LSA_T_OPQ)
struct hsls_opqlsa_hdr {
u_int32_t oh_seqno; /* sequence number */
u_int32_t oh_flags;
#define HSLS_LSA_F_UP 0x1
#define HSLS_LSA_F_BIDIR 0x2
u_int16_t oh_type; /* Opaque LSA type */
u_int16_t oh_len; /* LSA length, starting at oh_flags */
u_int32_t oh_instance; /* Unique instance identifier for this
* Opaque LSA. No two LSAs of the
* same type have the same instance
* number.
*/
/* payload */
};
IV.C.7. Router LSA (ah_type == HSLS_LSA_T_RTR)
struct hsls_rtrlsa_neighbor {
u_int32_t rm_seqno;
u_int32_t rm_flags;
#define HSLS_LSA_F_UP 0x1
#define HSLS_LSA_F_BIDIR 0x2
u_int32_t rm_metrics[ZERO_OR_MORE];
u_int8_t rm_nbraddr[ONE_OR_MORE];
};
struct hsls_rtrlsa_if {
u_int16_t ri_type;
#define HSLS_NET_T_BCAST 0
#define HSLS_NET_T_PTMP 1
#define HSLS_NET_T_PTP 2
#define HSLS_NET_T_STUB 3
u_int16_t ri_nneighbor; /* 0 is permitted for
* STUB networks; 0 is
* required for BCAST
* networks. 1 or
* greater required for
* PTMP, PTP.
*/
u_int16_t ri_masklen;
u_int16_t ri_ifindex;
u_int8_t ri_ifaddr[ONE_OR_MORE];
struct hsls_rtrlsa_neighbor ri_neighbors[ONE_OR_MORE];
};
struct hsls_rtrlsa_hdr {
u_int16_t rh_nif;
struct hsls_rtrlsa_if rh_ifs[ONE_OR_MORE];
};
$Id: hsls-protocol 496 2004-04-28 03:17:12Z dyoung $
More information about the CU-Wireless
mailing list