hsls_report

HSLS Routing Design and Implementation Update

David Young 28 Jun 2004

Our HSLS wireless routing implementation stands now at 10,000 lines of portable code in the C programming language. It implements the Adaptive HSLS (A-HSLS) protocol that is documented in [1]. We have a draft HSLS protocol specification, which we update as our design and programming progresses [3]. This protocol specification, when complete, will be submitted to the Internet Engineering Task Force for standardization.

Operational Overview

We have chosen to implement Adaptive HSLS (A-HSLS), as described in [1], p. 27. A-HSLS is superior technology for routing in large and growing wireless networks where link conditions are dynamic. Following the implementation notes in [1], our routers send periodic Hellos that tell the status of links in the 1-hop neighborhood; routers flood using the limited dissemination techniques described in [1], and routers adapt to the size and rate of change of the network. Current OSPF implementations use flooding to communicate node paths and can support no more than 50 nodes. In contrast, A-HSLS has the potential to support thousands of nodes using the superior limited dissemination method.

Protocol Packet Format

Address-family agnostic and IPv6-ready: We designed support for arbitrary network address formats (IPv4, IPv6, Ethernet) into the HSLS protocol packet format, in anticipation of world-wide IPv6 connectivity and universal operating-system support for IPv6. Many free operating systems (FreeBSD, Linux, NetBSD, OpenBSD) and commercial(MacOS X, Windows 2000) already support IPv6 networking, and adoption of IPv6 networking is picking up in some parts of the world. Because of IPv4-number scarcity outside of the U.S., the developing world may adopt IPv6 faster than the U.S.

Layer-2 routing is also possible with the packet protocol we have designed. On networks built with links made on the same media (WiFi-only, say, or Ethernet-only), there may be advantages to "pushing down" the routing from IP ("layer 3" in the OSI model) to layer 2.

Multiple metrics: Following a suggestion from Dr. Gregory Troxel at BBN Technologies, we designed support for an arbitrary number of "wide" (32-bit) path costs/metrics. A dynamic wireless networking environment may be best described by several path metrics, including ETX (which we are implementing), packet-delivery ratio, bandwidth, latency, and jitter.

Uncomplicated: Our HSLS protocol defines just two packet types, Hellos and Link-State Updates (LSUs). Of the five LSA types, only two are necessary in typical wireless deployments, the Router LSA (for path-finding on the rooftop network) and the Opaque LSA (for propagating Internet gateway advertisements, and possibly for name service).

Suitable for standardization: Our HSLS implementation will be eligible for "draft" standardization. Full standardization will be possible when a second, interoperable implementation is finished, using our documentation.

Extensible: HSLS is extended by adding Packet Payload Extensions or by adding Opaque LSAs. There is an API defined [5] for programs to provide Extensions and Opaque LSAs. We have implemented the Extensions API, and the ETX path metric module uses it to carry beacons.

Libraries

In the course of development, we have re-used some existing libraries, and programmed some libraries from scratch. The following libraries support our HSLS code.

libpack: HSLS and ETX both use our original Packet-Packing Library, libpack, to fill buffers with protocol packet fields prior to tranmission, and also to disassemble protocol packets.

libssrv: libssrv is our original Socket Server Library (SSL) that helps set up the multicast sockets that our HSLS daemon uses to send and receive HSLS protocol packets. It also aids in constructing, processing, and printing IPv4 and IPv6 addresses (sockaddrs). We were also able to re-use Niels Provos' event(3) library for timers and socket event indications, which is available on several platforms, and helps us to meet our portability goals.

liblog: The HSLS daemon and the ETX module both use liblog to print to either the standard error output or system logs messages indicating program progress, exceptional events and conditions.

---

[1] Ramanathan, Ram, and Cesar A. Santivanez. "Hazy Sighted Link State (HSLS) Routing: A Scalable Link State Algorithm." BBN Technical Memorandum No. 1301. August 31, 2001. (Revised March 2003.)

[2] Moy, John T. OSPF: Anatomy of an Internet Routing Protocol. Addison-Wesley: Reading, MA. 1998.

[3] HSLS Protocol Specification,
http://cvs.sourceforge.net/viewcvs.py/wireless/cuw-trunk/doc/local/hsls-protocol.

[4] Miller, Zachary. Personal communication. 25 June 2004.

[5] "HSLS Transponder & LSU Extensions API." Comments in the C header file,
http://cvs.sourceforge.net/viewcvs.py/wireless/cuw-trunk/src/hsls/hsls_client_api.h.