Network/Data Layer Messaging Protocol for Stand-Alone, Free-Field Communications Systems
Reproduced with permission. Copyright ARRL, 2007 all rights reserved.
This material originally appeared in QEX: Forum for Communication Experimenters (www.arrl.org/qex)
 
Citation: Robertson L J (2007). Network/Data Layer Messaging Protocol for Stand-Alone, Free-Field Communications Systems. QEX. 242 pp33-38


Network/Data Layer Messaging Protocol for Stand-Alone, Free-Field Communications Systems

The author proposes protocols and data formats for a self-organizing network of stations to pass messages.
Lindsay J Robertson, ZL2LJR
Lindsay@tech-vantage.com

Abstract


Protocols and data formats are proposed that will allow a completely self-organizing network of peer stations using free-field physical-layer communications, to pass message packets from an originating station, to a designated destination station at arbitrary distance, needing no other equipment or systems. The proposed system is presented in enough detail to allow implementation, but most importantly the paper establishes some general principles, that can be extended and developed as required. Briefly, a datagram header format that contains geographical location and a local identifier of the destination station is proposed: peer stations build up internal lists of ID’s and locations of other peer stations that they can “hear” — and hence each station that progresses a datagram is able to automatically select an optimum station to which the transient datagram may be passed. Simple protocols are proposed for authenticating and verifying datagram transfer, for rerouting datagrams to ensure a high probability of delivery, and for purging of datagrams that are successfully passed towards their final destinations. An “open” approach that encourages user control and further optimization is proposed. This is different from present Mobile Ad-hoc Network (MANET) protocols, and it also differs in several aspects from current geographic routing proposals and current radio packet transfer systems.

Need for Robust, Free-Field Network Layer System

Life without instant, reliable communication is just about inconceivable — we simply assume reliable communication via the Internet, cellular and “landline” phone services. Yet a review of existing systems shows that only the long-range point-to-point HF radio system is both independent of a “wired backbone” and capable of long-range messaging. Although workable, the point-to-point HF radio system has limited reliability. (It depends upon ionospheric conditions between two stations, and is a highly inefficient use of bandwidth.) Reliance upon wired communication backbones represents a significant vulnerability. To appreciate the issue, one only has to consider how useless a cell-phone handset is, without the cell-phone nodes and inter-node routing systems. A news item “The Backhoe: A Real Cyberthreat” describes this issue eloquently.1

The existing systems therefore do not adequately address any of the following situations:

Existing Systems

Classification of Existing Systems

Before considering any proposed “new” system, it is essential to review systems already in existence. Classifications of network systems have been published before, however these have generally been limited to relatively narrow fields. For the purposes of this paper, a very broad approach is taken, and the following categories are proposed:
“Wired” Systems. For these systems, all nodes are hard-wired, and for each route segment, a router selects the next destination node and switches the packet to that node.4 (See the referenced text, starting on page 405.) Examples include the Internet, and landline telephones. These offer efficient, high-speed communication, but are totally dependent upon the “wired” connection, and vulnerable to either physical disruption of wired “backbone” (see Note 1), and electronic disruptions (see Notes 2 and 3).
Wireless Neighborhood Networks. These are dense local collections of wireless (commonly short range) nodes. Examples include the Zigbee system, various “household control” nets, and “Motes” (“smart dust”).5, 6 The protocols used in these systems include (but are not limited to) Ad hoc on-demand distance vector (AODV), Multi-Radio Link-Quality Source Routing (MR-LQSR), and Destination-Sequenced Distance Vector Protocol (DSDV).7 These systems offer good levels of network resilience, but they are generally designed for short-range meshes in which nodes are aware of each other. See also Notes 8, 9 and 10.
Wireless Access Systems. These systems are characterized by the use of a single wireless point-to-point hop, from a mobile station to a wired network. Examples include cellular telephone and WiFi (802.11) internet access systems.
Wireless End-to-End. These are the systems that allow true point-to-point communication between peer (radio) stations. These systems rely on a single-hop path, with every connected node having a unique identifier — (MAC or call sign). Examples include commercial or amateur HF transceivers. Although autonomous, these systems make very inefficient use of bandwidth, and are totally dependent upon long wireless transmission paths.

There are a great number of variations within these categories: Ethernet rings are perhaps closest to the semi-wired category, and VHF radio repeaters, the “digipeater” facilities, AX.25 protocols and ROSE switches offer a limited multi-hop capability.11 Although some systems (satellite phone) do not fit this taxonomy exactly, the above list is largely complete, and is sufficient to illustrate the points raised in this paper.

Control Data Flow in Existing Systems

As well as user data flows, data communication systems usually require control data communicated between nodes of the network, to configure and reconfigure the network. In wired systems, network data is communicated either automatically (routers sharing dynamic routing tables) or manually (the Network Operator edits static router tables). In a typical neighborhood system, nodes undertake a complex request/response protocol, at the end of which each node has established a route to each destination node. See Note 11. The semi-wired and “wireless access” systems introduce one further level of complexity; the wired nodes must exchange information about the unwired devices that are currently connected to each node. In other words, they must dynamically associate the user addressing information (my cell-phone number, and the cell-phone number of the person I am calling) with the node interconnection information.
Control data may also include user address translation, such as DNS lookup data to translate user addressing data into datagram information that can be used by routers to select a next destination.
Although less easy to define, all network systems also incorporate various levels of “assumed knowledge” — whether this is acknowledged or not.

Basis for Proposed System

Design Objectives

The subject of this paper is the specification of a system able to address the deficiencies of existing systems. The proposed objectives are:

Principles

The proposed system assumes that each station/node comprises at least one free-field physical-layer communication channel (radio transceiver with antenna, or similar equipment), plus basic computing capabilities and some data memory. This is not an onerous requirement — a single-channel VHF transceiver, and a simple, single-board computer would be quite adequate. We can note that effective radio path distances of a few km are quite practical with the RF power levels readily available from handheld apparatus.
Three principles are essential:
a) Broadcast “Offer of service” and create local router table. Each station periodically broadcasts, on each physical-layer channel available to it, an “offer of service” (OOS) packet. These broadcasts advise other stations within reception range of its existence/identification, its location (geographical coordinates) and its available communication modes. Any “send” by a node/station is also treated by its listeners as an offer of service, on that channel. By scanning across its own receive channels, and storing data from the received “offer of service” packets, each station builds up its own file/record (analogous to a router table), of the identity, location and available physical-layer modes of stations that it can “hear”.
b) Process, or pass-on datagram. When a station receives a packet (the packet has the receiving station’s ID as either its final or immediate destination), it determines whether it is the final destination of the message, and if not it forwards the message. To forward a packet towards a distant destination station (whose exact ID, and approximate geographic location is contained in the message header), a users’ station searches the list of stations that it has recently heard, and uses the listed station locations to calculate the one farthest in the desired direction (calculation of shortest route across the surface of a sphere). The users’ station then places that (intermediate) station’s ID into the packet header, and retransmits the message.
c) Acknowledge/purge datagram. Having received a packet, an intermediate or destination station confirms the integrity of the packet using the message digest, then sends an that identifies itself, and identifies the packet by its message digest (CRC).12 On receipt of this ACK, the (intermediate) source station deletes the packet from its memory. Data packets carry the identity and the geographical coordinates of the packet’s final destination, and progressively acquire a list of each station passed on its journey.

Some Theoretical Considerations:

Node-to-Node Datagram Transfer

The proposed approach includes a “digest” in the datagram header (CRC or hash) of the data portion of the datagram. The essential property of a message digest is that it is highly unlikely that another set of data can have the same digest — hence the digest can, for practical purposes, be assumed to uniquely identify the data portion of the packet. This “digest” can therefore be used to prove the integrity of data transfer between two peer stations (nodes). A true message-digest algorithm should be such that it is computationally impossible for two different datasets to generate the same “digest” — but such algorithms produce large outputs (the MD5 algorithm produces a 128-bit output).13 This level of rigor is not required here; a shorter digest or hash function (possibly even such a simple functions as CCITT should be satisfactory.14

Origin-to-Destination Datagram Transfer

The proposed design allows the identity and location of each peer station that the datagram “passes,” to be recorded in the datagram header. When a station receives a datagram, it identifies the “best” next hop destination — but if that station is listed in the datagram’s header as having already been “passed,” then clearly the route is a dead-end, and a “next-best” destination must be selected. Since the “worst” packet forwarding option (returning the packet to the previous station) is always available, this approach is effectively a depth-first search algorithm, which will ultimately find a path between source and destination if such exists.

Assumptions

A small number of assumptions/restrictions are inherent in the proposed design:
1) Assume that each user (station/node) has an ID (call sign) that is at least unique within its geographical area.
2) Assume that a destination user’s approximate location is known or is predictable.
3) Assume that sufficient stations/nodes are implemented, so that at least one continuous corridor of transmission paths exists between source and destination.

Provided these assumptions/restrictions are accepted, then a long-distance, ad-hoc and extensible free-field messaging protocol is possible and practical.
Although one can postulate situations in which one or another of these criteria pose problems, it is respectfully suggested that for a very large proportion of practical situations, these are quite acceptable limitations, and furthermore that acceptable approaches are possible to mitigate these difficulties. I would argue that these are acceptable assumptions/restrictions.
The availability of higher ISO layers to handle the disassembly/reassembly of datagrams into files, can be assumed.15
The availability of encryption, to secure the contents of the message, can also be assumed. Although not covered in this paper, combinations of public/private key cryptography systems, and challenge/response identification systems could certainly be devised to prevent packet-spoofing problems. Since the datagram header is simply prepended to the message data, recovery and extraction of the message data is simple.

Proposed Implementation

Datagram Header Tags

In the field of data communications, data packet headers are commonly defined with fixed field lengths and without field delimiters. In a case where all fields must be used on all occasions, this approach has the advantage of incurring no bandwidth overheads for delimiting of fields. The approach does, however, have significant disadvantages. If all fields are not used all the time, there is wasted space, and conversely if insufficient (number or size) fields are defined, massive redesign is needed at a latter stage — this situation is the fundamental reason behind the move from IPv4 to IPv6.16 The system proposed in this paper places a high value on an “open” design approach, and for this and the above reasons, it is proposed to use an Extensible Markup Language (XML) format for the packet header.17 The limited number of “tags” required allows single-letter tag names, reducing the size of the transmission overhead. The markup language approach offers an excellent combination of flexibility and extensibility.
The proposed data packet header is simply prepended to the data portion of the packet. See Table 1.

Tag, name Description, Options,example
Header Format < SND001 T=Type >
Type options: "S" for Service, "A" for ACK, "D" for data.
Example
Station ID (list) Format < S Stn_type, Stn_ID, loc; Stn_type, Stn_ID, loc; etc >
Stn_type = “FR” From, “TO” To, “PS” Passed, “NE” Next.
Stn_ID = unique ID (e.g. callsign)
Loc = ccmmddhhmmss,lo,la,ht – datestamp, latitude, longitude, height
Example < S FR:ZL2LJR,123,123,123; PS: ZL1BOO,234,234,234; TO:ZL1ASD,123,123,123 >
Channel (list) Format: < C=”Mode”, “Frequency” >
Example < C=FM,144.3; FM, 144.35; USB;3.600 >
Validation Format: < V Val_type,str LN=Length >
Val_type options: CCITT32
Example < V CCITT32=a9f4R; LN=120 >
Table 1: Packet header tag formats and descriptions


Datagram Formats

Three types of datagram (or packet) formats are required, as shown in Table 2. It may appear that the use of a markup approach to defining header information imposes a significant transmission overhead. Closer inspection shows that because some information that would normally be supplied by higher ISO layers is already incorporated into the header of the SND datagram, the net overhead increase is small. For example, in the case of an e-mail message, the data portion of the IP packet will contain the “TO,” “FROM” and other fields in ASCII text — information that is already contained within the “overhead” of an SND datagram. By restricting the size and number of tags in the proposed SND system, the real overhead is not excessive for moderate-sized messages.
A priority design principle is that of “openness” — in other words the accessibility of the system parameters and data by the user. This approach is somewhat at odds with the philosophy that requires equipment to be completely autonomous and able to cope with any eventuality. There is obviously a trade-off between user control and simplicity, but this issue can be easily managed by providing default settings.
Functions that should be accessible by the user include editing/updating of the router table, and editing/updating of station parameters.

Datagram_type Format
OOS <SND001 T=O>
<S FR=ZL2LJR,123,123,123 />
<C F=114.600,M=FM; F=115.00,M=FM />
</SND001>
MSG <SND001 T=D>
<S FR:ZL2LJR,123,123,123;; PS=ZL1AAA,123,123,123; TO=ZL1ABC,123,123,123 />
<V CRC=asdasd L=123 />
</SND001>
.. Datagram content…
(Note, the header is simply pre-pended to the message content)
ACK <SND001 T=A>
<S FR=ZL1AAA,123,123,123 />
</SND001>
Table 2: Datagram formats

Each station’s router table is local and is prefiltered so only accessible modes are listed — when reduced to minimal level we have a station whose only purpose is to act as a single-mode relay station. Since each peer station is functionally identical (acting as both an end-use station and a relay facility), the user located at the end of a long valley could provide a corridor of coverage by locating a series of minimal SND units strategically along the valley. The proposed protocol requires that the approximate geographical location of the originating and destination stations must be known. The station ID tag links to each station ID, a datestamp (ccmmddhhmmss), and the station’s latitude, longitude and height. With the assumption that individual sets have a range of a small number of km, this is not an onerous requirement for very many cases. The earth’s circumference is about 40,000 km, so a 4-byte hex representation of longitude or latitude (for example, a3b4) allows a resolution of 600 meters — a practical option. The station’s “router” table should be a simple file containing repeating tuples with XML elements corresponding to Station_ID, latitude, longitude, height, time, frequency and mode. The use of the XML approach means that additional fields for permissions to access commercial stations, public keys, and so on, can be added in future.

Basic Protocols

Broadcast Offer of Service, Update Router Table:

The specification requires that each station periodically broadcast an “offer of service” packet, containing information that receiving stations can use to build up their internal router table. These are proposed to be uniquely identified packet types, broadcast regularly on each physical-level channel available to the station. (See Note 15.) A station can also supply, in the body of each “offer of service” packet, more than one channel/mode data pair; hence provided that a station receives one “offer of service” packet from a peer, it can add all the possible channel/mode pairs available, without having to listen on multiple channels. The data contained in the offer of service packet is the identity and location of the broadcasting station, and a set of data pairs identifying channel and mode combinations that are available The data format is extensible (potentially to place limits on the duration of the offer of service), but provision for including authorization information, and the station’s public key is anticipated.18 On receiving a broadcast “offer of service” message/packet, the receiving station uses the information in the broadcast packet to update its router table. The ranking of stations within a router table, and further optimizations are easily envisaged, but not essential to the basic proposal of this paper.

Receive Datagram (Scan Channels), and ACK

:
In its default operational state, a station regularly scans each channel/frequency/mode available to it (that can be accessed by its physical-layer systems), listening for incoming data. Offer of service packets are not acknowledged. If a broadcast offer of service packet or a data packet is received, then the “Update Router Table” function is invoked for that station on that channel. There is an important principle here; if a station can be “heard,” its details are able to be added to other stations’ router tables — for a user, the default option is that if the system is used, then the User’s station is available to be bused by the system also! If a received packet is not complete, or its CRC is incorrect, it is ignored. If the receiving station does not (for whatever reason) bbhave the capacity to process the message, the message is ignored! If either the intermediate or final destination name of the incoming packet is the same as the receiving station, and if the receiving station decides not to ignore the packet, then the message is stored and processed.

Send and process ACK:

When a station receives a datagram addressed to it (for example, the receiving station’s ID is found against a Stn_type=“TO” or Stn_type=“NE” in the message header), the CRC is checked. If the CRC is valid, then an datagram (containing the CRC of the received packet) is broadcast, and the receiving station’s type is changed from “NE” to “PS” in the message header. When a Station receives a broadcast packet, the station scans its memory for a message with the same CRC. If a corresponding CRC is found, the Station concludes that this message has been successfully received by the (intermediate) destination station, and purges/archives the message from its memory.
User Control: If there is insufficient memory to store the incoming packet, then it is ignored. Each station’s user-defined options control whether relay service is available — if not, then packets for which that station is not the final destination, are not ’d — in other words, are effectively ignored.

Process/Pass on Datagram:

When a station receives a packet in which its ID is listed as the intermediate destination or as the final destination, the packet is processed. Then an corresponding to that message is broadcast. If the receiving station is designated as an intermediate station in the message, then the “Send-Onwards Datagram” function is invoked, and the attribute corresponding to the current station’s ID is changed from “NE” to “PS” in the datagram header. If the receiving station is the final destination of the data packet, then the “Accept Message” function is invoked.
Send-Onwards: The receiving station parses the coordinates of the final destination station (contained in the datagram). The receiving station then searches its “router” table. If the identification of the destination station is found in the router table (if the datagram’s final destination is accessible), then the packet is broadcast. If the destination station’s ID is not in the router table, the station uses the coordinates of the packet’s final destination, and computes from the coordinates of the stations in the router table, which of the stations is farthest along the path towards the final station’s destination. If this proposed next station is already listed in the station ID tag, this indicates that the message has already passed that station, and found the route to be a dead-end; the station must therefore search the router table again for the next-best intermediate destination station. Having identified the next intermediate-hop station, that station’s ID is inserted into the Station ID tag of the message’s header, with the “NE” attribute. The station then checks whether the frequency/mode for the next intermediate-hop station is free — if so the datagram is broadcast, otherwise the station waits and retries after a random delay — if channel is still in use, then the station reprocesses the router table, looks for another channel/mode that is equidistant or next-farthest towards the destination, loads that station’s ID into the station ID field, then rebroadcasts. The protocols automatically allow the use of any physical mode (medium, frequency, mode, speed and so on) for any particular hop, allowing good bandwidth utilization. Packets that have been broadcast are retained in memory pending receipt of an from the (final or intermediate) station to which they were addressed.
Following the broadcast of the packet, the sending station waits for an : If an is not received, the station retries (the number and frequency of retries is set by user-definable options), then reprocesses its router table, selects the next-farthest station from the router table, loads that station’s ID into the packet’s intermediate-station ID field, and rebroadcasts the datagram. It is important to note that this procedure will eventually lead to the packet being sent back to the originating station, if no better destination is found: an important consideration in ensuring system robustness. Note also that, by using the Stn_type=“PS” attribute, the identify of each peer station that passes on a datagram, is recorded in the datagram header. While this approach potentially results in a large header, the absence of such a list would allow messages to be “trapped” in a dead-end coverage corridor — and by contrast, the presence of such a list allows a rigorous “depth-first” search for possible coverage routes to be conducted. The combination of the routing and protocols, create a robust system; a node that does not a message — for any reason — is automatically bypassed. A message that cannot be moved towards its destination is automatically returned to the previous node, allowing selection of an alternative route segment. This process is illustrated in Figure 1.


Figure 1: Message route from AA to GG

User Interface, Create Initial Datagram:

To initiate the sending of a datagram, the user (application layer) needs to specify the location of the destination station. For practicality, a lookup table of locations/coordinates would be trivially easy to implement and would insulate the user from a possibly unacceptable level of detail. Deal with Datagram Successfully Received at Final Destination:If a datagram whose final station ID is that of the current station is received, (so, the datagram has reached its final destination) then the datagram is passed on to the next highest protocol layer (possibly the user interface).

Conclusion

This paper has highlighted a serious vulnerability that is inherent in all “wired” communication systems. Having articulated the vulnerability, the paper described the functional necessities (specifications) of a highly decentralized, fully automated, peer-station network communication system. Core protocols and data formats, that meet the specified need, have been defined: these core protocols and data formats are simple, robust and readily able to be both extended and optimized. The assumptions required to permit the proposed system to work have been examined, and it is suggested that these are acceptable and feasible for the vast majority of cases. The technology elements required to implement the core protocols and data structures are readily available (basic transceiver, and basic computing capability — indeed, the core components are also present in cell-phone handsets)

1 Notes appear on following page.


Notes
1 The Backhoe: A Real Cyberthreat, available online at www.wired.com/news/technology/0,70040-0.html.

2 Anon, “The Day the Internet Died — Courtesy of the Florida Internet Exchange,” 18 Aug 2003, available online at flix.flirble.org/.

3 Cnet Staff Reporter “Router glitch cuts Net access,” last modified 25 Apr 1997, 7:00 PM PDT. Available online at news.com.com/2100-1033-279235.html?legacy=cnet. “‘There are probably a hundred guys in back rooms keeping this stuff together, just barely,’ Ricard said of the Internet.”

4 Telecommunications: A Beginner’s Guide, Hill Associates, Inc, Pub 2002, McGraw-Hill/Osborne, Berkley,CA. USA.

5 ZigBee is a published specification set of high level communication protocols designed to use small, low-power digital radios based on the IEEE 802.15.4 standard for wireless personal area networks (WPANs). The specifications are available online at en.wikipedia.org/wiki/ZigBee. See also www.merl.com/projects/zigbeestack/.

6 “Dust Networks,” DustNetworks Ltd, available online at www.dustnetworks.com/technology/overview.shtml. Also see A. M. Agogino, MEMS “SMART DUST MOTES” FOR DESIGNING, MONITORING AND ENABLING EFFICIENT LIGHTING(2003), Department of Mechanical Engineering, University of California, Berkeley, CA, 94720. The Project Report 2002-03 for MICRO Project 02-001 is available online at www.ucop.edu/research/micro/02_03/02_001.pdf.

7 C. E. Perkins, E. M. Royer, and S. R. Das, AODV (Ad-hoc On-demand Distance Vector), routing.draft-ietf-manet-aodv-06.txt, July 2000. See also www.usenix.org/events/osdi02/tech/full_papers/musuvathi/musuvathi_html/node12.html.

8 L. E. Miller, Multihop Connectivity of Arbitrary Networks, Wireless Communication Technologies Group NIST “Multihop connectiviry,” 29 March 2001, ConCalc.pdf.

9 Richard Draves Jitendra Padhye Brian Zill, Microsoft Research, {richdr, padhye, bzill}@microsoft.com, Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks, available online at research.microsoft.com/mesh/papers/multiradio.pdf.

10 Ali N. Zadeh and Bijan Jabbari, George Mason University, Raymond Pickholtz and Branimir Vojcic, George Washington University, Self-Organizing Packet Radio Ad Hoc Networks with Overlay (SOPRANO).

11 Greg Jones, WD5IVD, Introduction to Packet Radio, available online at www.tapr.org/pr_intro.html. See also L. Ehud, H. Eli, E. Amir, and D. Koren D, X.25 Packets and Protocols(2004). Available online at www2.rad.com/networks/1996/x25/x25.htm. See also Packet Radio: What? Why? How? / Articles and Information on General Packet Radio Topics, TAPR, Publication #95-1. 1995. 130 pages. Particularly see the section about ROSE switches. Available online at www.tapr.org/pr_intro.html and www.nzart.org.nz/nzart/digital/digital.html. Particularly, see the “Digipeater” section.

12 R. N. Williams, A Painless Guide to CRC Error Detection Algorithms (1996). Available online at www.ross.net/crc/crcpaper.html.

13 Akadia AG, MD5 — Message Digest (fingerprint, checksum) (2000), available online at www.akadia.com/services/md5.html. See particularly the section on the MD5 algorithm.

14 J. Geluso, CRC16-CCITT, (2004), available online at www.joegeluso.com/software/articles/ccitt.htm.

15 G. C. Kessler, An Overview of TCP/IP Protocols and the Internet (2003). Available online at www.garykessler.net/library/tcpip.html. See also Anon, OSI Layer Definitions (2005). Available online at www.webopedia.com/TERM/O/OSI.html. See also F. Halsall, Data Communications, Computer Networks and OSI, Second Ed, Addison-Wesley Publishing Co, Inc, 1988.

16 Ipv6 Task Force, Mobile wireless working group report, available online at www.ec.ipv6tf.org/PublicDocuments/IPv6TF-Mobilewireless.pdf. See also RFC 3794, available online: rfc.net/rfc3794.html.

17 W3C, Recommendation 10-February-1998 Extensible Markup Language (XML) 1.0, available online at www.xml.com/axml/testaxml.htm.

18 B. Schneier, Applied Cryptography, Second Edition. John Wiley & Sons, 1996, ISBN 0-471-11709-9. See also Department of Commerce, National Institute of Standards and Technology, RIN 0693-AA86, A Proposed Federal Information Processing Standard for Digital Signature Standard (DSS), available online at www.epic.org/crypto/dss/dss_fr_notice_1991.html. See also W. Stallings, Cryptography and Network Security, Third Edition(2005), available online at williamstallings.com/Crypto3e/Crypto3e-student.html


I'd appreciate your feedback