HSLS is the routing protocol that has been developed by CUWiN based on a technical paper from BBN. This routing protocol is specially designed to be scalable for ad-hoc mesh wireless networks. The HSLS daemon communicates with the kernel's routing tables via the Zebra daemon which provides some future portability to other operating systems.
The HSLS README explains how to invoke the HSLS daemon. On the standard CUWiNware image hslsd is started with these parameters.
CUWiNware has specified an HSLS packet format.
This protocol is intended to provide the expected transmission count (ETX) routing metric based on the work of the M.I.T. Computer Science and Artificial Intelligence Laboratory [1], and be used between routers on ad hoc wireless networks.
The Expected Transmission Count (ETX) path metric is a simple, proven routing path metric that favors high-capacity, reliable links. The ETX metric is found from the proportion of beacons sent but not received in both directions on a wireless link.
Each participant router broadcasts a beacon to its one hop neighbors at a configurable interval. Each beacon contains the protocol version, flags and a sequence number. The beacon contains a list of the router's one hop neighbors. For each neighbor a history of whether or not the beaconing router received a beacon from this neighbor is included. The history includes the last BITFIELD_LENGTH (32) of this neighbor's beacon intervals. An optional set of extensions may be included. No extensions exist at this time.
At a configurable interval, the cost of the link associated with each peer is computed based on expected probability of beacons to be transmitted and received. See Receiving Beacons and Computing Link Costs.
ETX_F_INIT - this flag MUST be set for the first BITFIELD_LENGTH transmissions made by an ETX router. It is used to distinguish sequence number wrap-around. See Sending Beacons and Receiving Beacons.
ETX_F_EXTENSIONS - indicates that a beacon contains extensions. If set, each peer block in the beacon MUST contain at least one extension block. See Extensions.
ETX_F_SUSPEND - May be set by a router to indicate that it will be out of communication for some length of time. If set, the beacon MUST contain the 32-bit time of return field. See Transmitting Beacons.
Upon receiving a beacon it is implicitly required that certain data must be available in order for the router to conform to the protocol. For example it is necessary to have accurate expectations regarding the arrival of future beacons from this neighbor.
When beacons are received from a previously unheard of neighbor, the data for the new neighbor are initialized appropriately. It is added to the neighbor list and the contents of the bit field are processed in full (dependent on the ETX_F_INIT flag).
If the beacon is from a neighbor that is already known, its sequence number is compared to the sequence number of the last beacon received from this neighbor. If the sequence number of the received beacon is less than or equal to the most recently received sequence number these statistics are recorded for MIB. If the sequence number of the received beacon is within BITFIELD_LENGTH intervals of the last heard sequence number, the previous bits of the affected bits in the bitfield are set accordingly.
The sequence number of the incoming beacon is compared to the currently expected sequence number from this neighbor. If it is less or more than expected these statistics are recorded for MIB. The bitfield is updated with the available data.
A sequentially valid beacon is processed as follows. Each sequence number that has passed since the last beacon received from this neighbor it is inferred that no beacon was received. Beacon received is set for the current beacon interval. This updated bitfield is used to recompute the probability of beacons being received from this peer. See Computing Link Costs.
Additionally, we expect that the received beacon will contain a peer block for the localhost. The bitfield from this block is used to recompute the probability of beacons being transmitted to this peer. See Computing Link Costs.
At each beacon interval, the router must assemble and broadcast a beacon to its one-hop neighbors. The sequence number MUST start at 0 and be incremented by exactly 1 with each beacon transmitted. The ETX_F_INIT flag MUST be set for the initial BITFIELD_LENGTH beacons transmitted.
For each known neighbor a valid bitfield must be determined. If a beacon was expected but not received, the bitfield must be updated accordingly (an expected and received beacon will have already been processed). If this neighbors beacon interval
is longer than the local beacon interval, the bitfield should not be updated until the neighbor beacon interval has expired. If the neighbor interval is shorter than the local interval, the extra bits of the bitfield must be evaluated (if these beacons have been received, they will already be set correctly).
Periodically, the data of known peers is used to compute the cost associated with the link to that peer. To do so, smoothed probability ratings of transmission to and reception from each peer are used. Let 'srxp_k' and 'stxp_k' represent these respective probabilities for some peer at interval 'k'.
The cost of the link with this peer is computed as
cost_k = 1 / (srxp_k * stxp_k)
The probability of receiving from this peer is computed as
Let srxp_0 = rx_0 srxp_k = h * srxp_k-1 + (1-h) * rx_k where rx_k = 1 if a beacon was received, 0 otherwise.
The values of rx_k are read from the bitfield associated with this peer. 'h' is a configurable value that specifies the influence of a single interval on the probability.
In the event that either srxp_k = 0 or stxp_k = 0, the cost is set to 1.
The probability of transmitting to this peer may be computed in the same manner, in this case the values of tx_k are read from the peer block corresponding to the localhost in the beacon received from this peer.
It is possible that no tx data is available for a number of reasons:
For efficiency it is not desirable to recompute the probabilities at every BEACON_INTERVAL. The following formula may be used to include several intervals in a single recomputation:
Let srxp_0 = rx_0 k srxp_k = h^k * rx_0 + (1-h) * Sum( h^(k-i) * rx_i ) i=1
An ETX beacon consists of a 32-bit header, containing an 8-bit version number, 8-bit flags, 16-bit beacon interval and 32-bit sequence number. In the beacon interval the highest 11 bits are interpreted as a mantissa, while the lower 5 are an exponent. The actual beacon interval is m * 2**e microseconds.
If and only if the ETX_F_GLOBAL_EXTENSIONS flag is set, the header includes a global extensions block. The format is identical to the Peer extension blocks described below. No global extensions exist at this time.
If and only if the ETX_F_SUSPEND flag is set the header includes by a 32-bit field containing the expected time to return, in multiples of the beacon interval. The value of 0 indicates unspecified time, perhaps never.
The remainder of the beacon consists of one or more ETX peer blocks. An ETX peer block consists of the 128-bit IPv6 address of the peer. IPv4 addresses are encoded as v6 addresses. The address is followed by the bitfield (32-bit) for the peer. In the bitfield, the least significant bit is always most recent. During the ETX_F_INIT stage, the most significant bits are set to zero and are not used. If and only if the ETX_F_EXTENSIONS flag is set in the beacon header, the peer block concludes with one or more ETX Extension blocks.
An ETX Extensions block consists of a 16-bit extensions-used bitmask, and a 16-bit field indicating the length, in octets, of the extension block, not counting the Bitmask and Length fields. Extension blocks are padded with zeroes to a 32-bit boundary. To allow for more than 16 extensions, the most significant bit in the extensions-used bitmask is reserved to indicate another extension block follows.
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 # | Flags | Beacon Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
( Global Extensions Bitmask | Global Extensions Length )
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
( Time expected to return, iff ETX_F_SUSPEND flag is set. )
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+- -+
+- IPV6 address (ipv4 padded to ipv6) -+
+- -+
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bitfield |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
( Extensions Used Bitmask | Length of Extensions Block )
(-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-)
( ....... )
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+- -+
+- IPV6 address (ipv4 padded to ipv6) -+
+- -+
| ....... |
Beacon Flags
0x0001 ETX_F_INIT
0x0002 ETX_F_EXTENSIONS
0x0004 ETX_F_SUSPEND
0x0008 ETX_F_SECURE
0x0010 ETX_F_GLOBAL_EXTENSIONS
Extensions Bitmask
0x8000 ETX_E_MORE_EXTENSIONS
Global Extensions Bitmask
0x8000 ETX_E_MORE_EXTENSIONS
Beacon Interval - specifies how frequently this router transmits a beacon. It is not necessary that all routers use the same interval. Valid range is [ 2^(-8), 3^7 ].
Link Compute Interval - specifies how frequently this router recomputes link costs. No range limits apply. This parameter does not affect interoperability with other routers.
Hysteresis - This value controls the impact of a single interval when computing the smoothed probabilities of transmitting to and receiving from each peer. See Computing Link Weights.
Statistics - statistics of abnormal or unexpected behaviour are available to the MIB. See Receiving Beacons.
At this time, ETX has no authentication and no confidentiality which presents certain vunerabilities. For example, a malicious or faulty router could transmit beacons that cause false link costs to be calculated. The mechanism of global extensions (see Beacon Format) may be used in future revisions to sign beacons.
[1] D. Decouto, D. Aguayo, J. Bicket, and R. Morris, "A high-throughput path metric for multi-hop wireless networks", in Proceedings of MobiCom, 2003.
Posted to the developer's mailing list on July 11th, 2005 by David Young.
I have added a "network watchdog" to the CUWiN station software. The way it works is that every time hslsd receives a Hello on the wireless interface, it runs a shell script, /usr/sbin/tickle, to "tickle" a shell "watchdog" daemon. The "tickling" is rate-limited to once every 15 seconds or more.
As long as the shell daemon, /usr/sbin/hellowdog, is getting tickled at least once every 5 minutes, it lays dormant. (I realize I'm mixing metaphors here.) If 5 minutes do elapse without a tickle, hellowdog wakes up and tries to restart hslsd. If that doesn't work (because, for example, hslsd is already running!), then it puts wdogctl to sleep. wdogctl is in charge of tickling the hardware watchdog timer. At most 32 seconds after wdogctl is put to sleep, the system will reboot.
In theory, if the wireless adapter or hslsd goes "out to lunch," the network watchdog will bring the router back onto the network in 5 minutes plus 32 seconds plus however long it takes for the node to reboot.
This document describes the IP schema we use. The main point is that the DHCP server on non-Internet connected nodes assigns numbers on the ethernets from 10.A.B/24, where A and B are made by hashing the MAC number. A != 0.
Numbers are assigned to the wireless interface in the form 10.0.A.B/16.
We will assign numbers to stations from 10.0/16. The last 16 bits are the XOR of the first two octets of the MAC number, the second two octets, and the third octets, where the bytes are taken in "reading order." That is, we produce numbers 10.0.A.B from the MAC numbers. If the MAC produces A = 0, B = 0 or A = 255, B = 255, then A and B are assigned randomly. The netmask is /16.
(We compute numbers from the MAC to begin with because in the common case, a station will boot with the same A and B every time, which is useful for diagnostic purposes.)
The host networks are assigned from 10/8. We assign to each Ethernet interface, a network 10.A.B.0, where A and B are computed as above from the Ethernet MAC number. If A = 0, we re-assign it randomly. The netmask is /24.
We run OSPF in point-to-multipoint mode on each wireless interface. The wireless and wired interfaces should be configured with 'network zzzzz/x area 0' clauses under the 'router ospf' command. All other interfaces are run in passive mode (i.e., no OSPF Hellos are sent).
We will use channel 11. The SSID is 'cuw', all lower case, without the single quotes.
Missing from this design are authentication, naming, etc.
We have not solved the BSSID partitioning problem. We will have to watch out for this (perhaps Prism-based cards such as ours are not affected).
Linux implementation for Soekris board.
CD-ROM implementation of the new network design.
As of 6 August 2006, WiFiDog has not yet been integrated into CUWiN software.
You can build your own CUWiNware images from the CUWiN sources with your local modifications included. Local modifications that you can make include setting up a default config file, changing the default root password and adding default local users, adding public key authentication for login to the nodes. You can also build against newer NetBSD sources to update the available kernel drivers and if you are a programmer you can freely modify the code as you see fit.
In order to build the software you will need a working NetBSD build environment. Once you have that you will need both the CUWiN sources and an appropriate NetBSD source snapshot.
You can get NetBSD sources either from sourceforge by downloading the cuwin-x.y.z-src-netbsd.tar.gz file or by going to NetBSD's anonymous CVS server and grabbing the CURRENT sources.
You can get the CUWiN sources via SVN from http://svn.cuwireless.net/svn/cuw/trunk/ or from anonymous CVS at sourceforge or by downloading cuwin-x.y.z-src-main.tar.gz from sourceforge. You will also need the src-extern file from sourceforge. The source forge downloads are source snapshots used to make our releases whereas the SVN and CVS repositories have the bleeding edge code.
Once you have unpacked all the sources you should have a trunk/src/boot-image directory. Parallel to the "trunk" directory you can create a "private-trunk/image-data" directory. In that directory you can put in local customization files that will be used instead of the defaults during the build process:
When the tree is configured for build as you'd like it, you can
call the mkstaboot
script to build the sources into an image. The build
script is a helper that makes calling mkstaboot
easier. The Perl script nightly-test.pl
calls build for several different targets and provides a good example for how it is called. Read over the comments in these scripts before attempting to build.
If you need help building CUWiNware please contact cu-wireless-info@cuwireless.net
Posted to the mailing list on October 1st, 2004 by Zach Miller.
Please note that anonymous CVS and SVN access are now both available.
Anonymous CVS has been available for some time but until recently updates have been broken.
Anonymous CVS is hosted by Source Forge:
Information: http://sourceforge.net/cvs/?group_id=89823
Web CVS Viewer: http://cvs.sourceforge.net/viewcvs.py/wirelessTo checkout use these commands:
cvs -d:pserver:anonymous at cvs.sourceforge.net:/cvsroot/wireless login
cvs -z3 -d:pserver:anonymous at cvs.sourceforge.net:/cvsroot/wireless co cuw-trunkDon't forget that you should use "cvs update -dP" when updating to make sure you get the right directories in your tree.
Anonymous SVN is hosted on cuwireless.net:
Browseable URL: http://svn.cuwireless.net/svn/cuw
svn checkout http://svn.cuwireless.net/svn/cuw/trunkBoth repositories are READ-ONLY. Please submit patches to this email list for discussion and eventual inclusion by the core developers.
Posted to the developer's mailing list on January 28th, 2005 by David Young.
I got fed up with waiting 10+ minutes for mkstaboot to run, even with -u -o, so I broke mkstaboot into several stages. Now I can do routine rebuilds---after I modify, say, hslsd---in just 10 seconds.
The new mkstaboot and, by extension, build{,upgrade,iso,flash}, take two new options:
% mkstaboot -h
usage: mkstaboot [ ... ] [ -L ] [ stage ]
-L List the mkstaboot stages and quit.
stage Restart mkstaboot at this build stage.Here are the build stages, in the order they will be built:
% ./buildupgrade -s ~/radix-nbsd/src/ -L
tools
toolenv
makewrapperenv
iso-kernel
flash-kernel
distrib
metalog
patch
makewrapper
mv-root-home
extras
users
modules
cuwinize-metalog
install
postinstallenv
flash
upgrade
floppy
isoFor example, if I run "./buildupgrade -s ~/radix-nbsd/src -f disk.img install", mkstaboot will restart at the 'install' stage of the build, skipping all of the preceding stages on the -L list, UNLESS
- the stage ends in an 'env' suffix
- the stage did not run to completion during the last build
- some prior stage did not run to completion
If I do not tell mkstaboot to restart at any stage, then it starts at the beginning.
A few caveats:
- I've tried hard to make stages idempotent, but at least one of them ('patch') is not.
- I do not (yet) leave out any build stage based on the options. That is, the 'iso' stage will run (although it will be a null operation) even if I don't use an '-i' option.
- It is still a good idea to use -u and, if you know what you're doing, -o, as they are indicated, to speed up your build.
Just a few bullets about the architecture of the staged builds:
- In steps.d/ are the build stages. They get "sourced" (with '.') by mkstaboot. They are derived from the old mkstaboot sources.
- steps.d/deps is a two-column list of stage dependencies: for every row, the stage on the left-hand side cannot be run until the stage on the right-hand side has completed. If you add new stages, be sure to add them to steps.d/deps !
- In $BUILDDIR/, mkstaboot touch(1)es .<STAGE-NAME>.begin when a stage begins; it touches .<STAGE-NAME>.end if and when the stage finishes successfully. Next time you run a build, if .<STAGE-NAME>.end is newer than .<STAGE-NAME>.begin, then the stage ran successfully.
- POSIX touch(1) has a time resolution of 1 second. Therefore, the shell command "touch a ; touch b ; test b -nt a && echo yes" does not necessarily yield the string "yes". Sometimes it's necessary to sleep for a second before touching .<STAGE-NAME>.end. Sleeping synchronously will slow the build by a lot. So mkstaboot sleeps in the background. Hence the "joining pid xxx" messages at the end of a build.
- step.subr contains most of the logic for deciding which build stages to run, when.