INTERNET-DRAFT Christian F. Tschudin Mobile Ad Hoc Networking Working Group University of Basel Expires: Sep 11, 2004 March 11, 2004 Lightweight Underlay Network Ad hoc Routing (LUNAR) Protocol Status of This Memo This document is an Internet-Draft and is subject to all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html Abstract The Lightweight Underlay Network Ad hoc Routing (LUNAR) Protocol is intended for use by mobile nodes in small size wireless ad hoc networks. LUNAR operates at layer 2.5. It emulates a single-hop IP subnet with unicast as well as broadcast communication primitives. DHCP and ARP messages are intercepted and serve as hooks for self- configuration of IP addresses as well as the mapping of IP addresses to the underlying layer 2.5 multihop routes. Table of Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2 Tschudin Expires Sep 11, 2004 [Page 1] Internet-Draft: LUNAR Protocol March 11, 2004 2 Protocol Overview . . . . . . . . . . . . . . . . . . . . . . . 3 3 The SelNet Virtual Link Layer . . . . . . . . . . . . . . . . . 4 3.1 SelNet over Ethernet . . . . . . . . . . . . . . . . . . . 5 3.2 SelNet Packet Format . . . . . . . . . . . . . . . . . . . 5 3.3 Selector Format and Values . . . . . . . . . . . . . . . . 5 3.4 Network Pointers . . . . . . . . . . . . . . . . . . . . . 7 3.5 Forwarding Information Base (FIB) . . . . . . . . . . . . 7 4 LUNAR Protocol Logic . . . . . . . . . . . . . . . . . . . . . 8 4.1 LUNAR Unicast Routes . . . . . . . . . . . . . . . . . . . 8 4.2 LUNAR Broadcast Trees . . . . . . . . . . . . . . . . . . 12 5 The eXtensible Resolution Protocol (XRP) . . . . . . . . . . . 12 5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . 13 5.2 Commands . . . . . . . . . . . . . . . . . . . . . . . . . 13 5.3 Command Parameters . . . . . . . . . . . . . . . . . . . . 13 5.4 LUNAR Specific XRP Definitions . . . . . . . . . . . . . . 14 5.5 Encoding Example . . . . . . . . . . . . . . . . . . . . . 15 6 IP Adaption and Steering Layer . . . . . . . . . . . . . . . . 15 6.1 IPv4 Subnet for LUNAR . . . . . . . . . . . . . . . . . . 15 6.2 DHCP Interception for IPv4 Address Allocation . . . . . . 16 6.3 ARP Interception and Route Discovery Steering . . . . . . 16 6.4 IP Datagram Transmission . . . . . . . . . . . . . . . . . 17 6.5 Forced Rediscovery of Routes . . . . . . . . . . . . . . . 17 7 LUNAR Profiles and Configuration Parameters . . . . . . . . . . 18 7.1 LUNAR Profiles . . . . . . . . . . . . . . . . . . . . . . 18 7.2 Summary of Configuration Parameters . . . . . . . . . . . 19 8 Security Considerations . . . . . . . . . . . . . . . . . . . . 19 9 Numbering Considerations . . . . . . . . . . . . . . . . . . . 20 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 20 References . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1 Introduction This document describes the second incarnation of the LUNAR protocol. The first version, published in January 2001, adhered to the same protocol but used an active networking implementation style. The cur- rent and second version is expressed as a classic protocol where the complete protocol logic resides in the nodes and where packets are mere parameter collections. Tschudin Expires Sep 11, 2004 [Page 2] Internet-Draft: LUNAR Protocol March 11, 2004 LUNAR is a routing protocol based on ARP [RFC826] forwarding. A source node which desires to send an IP packet to a destination in the same LUNAR network emits internally a standard ARP request. The LUNAR routing layer intercepts this ARP request and maps it to a LUNAR Route Request (RREQ) message that is broadcasted and forwarded inside the network. Once the destination node receives this RREQ mes- sage, it will send back a Route Reply (RREP) and build two indepen- dently managed unicast routes (one for each direction) between the source and the destination nodes. When the source receives the RREP message, it maps it back to an ARP reply message, permitting the source's IP stack to send IP datagrams to the destination node. Thus, none of the involved IP stacks is aware of the potential multi- hop nature of the underlying LUNAR network. LUNAR routes have a limited life time and need to be re-established at regular intervals. The corresponding LUNAR system parameter has been set to 3 seconds i.e., a data route is in use for 3 seconds before it is replaced by another newly constructed one. The routing and forwarding strategy of LUNAR is simpler than other MANET routing protocols: LUNAR does not feature route repair, route caching nor packet salvation. Nevertheless, simulations reveiled that LUNAR scales without problems to networks of 40 nodes and 10 hops. Despite these observations, this document conservatively recommends LUNAR operations for networks with less than 15 nodes and even imposes a network diameter of 3 hops. Factors like TCP unfairness over IEEE 802.11 (WiFi) become so dominant at this range that the best thing the LUNAR protocol can do is to impose an artificial 3-hop zone in order to let users operate with parameters yielding accept- able network performance. 2 Protocol Overview LUNAR has four building blocks: a) IP adaption and steering layer (ASL) b) LUNAR protocol engine c) eXtensible Resolution Protocol (XRP) d) SelNet virtual link layer The IP adaption and steering layer (ASL) is responsible for translat- ing events at the border to the IP stack into LUNAR specific actions and vice versa. Among others, this includes the intercepting of ARP and DHCP requests and mapping them to the corresponding LUNAR Tschudin Expires Sep 11, 2004 [Page 3] Internet-Draft: LUNAR Protocol March 11, 2004 primitives. This layer also takes care of the forced rediscovery of routes every 3 seconds. The LUNAR protocol engine implements the core routing algorithm. It handles the generation of LUNAR RREQ and RREP messages and their pro- cessing at intermediate and destination nodes. As a result, data routes will be created. The eXtensible Resolution Protocol (XRP) is the request/reply proto- col and data format through which the LUNAR protocol engines interact with each other. The Selector Network (SelNet) is a forwarding layer which supports the creation of data routes composed of network pointers [NETPTR]. It is independent of IP addresses and the IP routing layer and works directly on top of the link layer. The following figure shows how these four building blocks relate to each other and to the standard IP networking environment: +-------------+ +-------------+ L7 | IP apps | | IP apps | +-------------+ +-------------+ L3-6 | IP stack | | IP stack | +-------------+ +-------------+ | --- IP subnet emulation --- | +-------------+ +-------------+ | adapt+steer | | adapt+steer | +-------------+ +-------------+ +-------------+ L2.5 | LUNAR| XRP | | LUNAR| XRP | | LUNAR| XRP | +-------------+ +-------------+ +-------------+ | SelNet | | SelNet | | SelNet | +-------------+ +-------------+ +-------------+ | | | +-------------+ +-------------+ +-------------+ L1-2 | e.g. WiFi |.....| e.g. WiFi |.....| e.g. WiFi | +-------------+ +-------------+ +-------------+ source intermediate destination In the following four sections we define the functionality for each of the four LUNAR building blocks. We start with the lowest LUNAR layer, SelNet, before continuing with XRP and the LUNAR protocol engine and finally presenting the IP adaption and steering layer. 3 The SelNet Virtual Link Layer Tschudin Expires Sep 11, 2004 [Page 4] Internet-Draft: LUNAR Protocol March 11, 2004 The Selector Network (SelNet) layer is a shim whose main task is to provide unreliable routes for datagrams. 3.1 SelNet over Ethernet In case of LUNAR, the SelNet operates on top a WiFi network. Future versions of LUNAR might also use other link layer technologies. The Ethernet Protocol ID of 0x4242 has been chosen for identifying SelNet packets. A SelNet-over-Ethernet frame has the following format (without preamble and trailer): 48 bits 48 bits 16 bits +-------+-------+-------+------------------ - - ---+ | dst | src |0x4242 | SelNet packet | +-------+-------+-------+------------------ - - ---+ SelNet-over-Ethernet packet 3.2 SelNet Packet Format SelNet packets follow the "Simple Active Packet Format" [SAPF] which has a two-field layout as shown in the following figure: +---------------------+-------------------- - - - ---+ | selector (64 bits) | payload | +---------------------+-------------------- - - - ---+ SelNet packet The first field is a fixed length 64-bit header that contains a per- hop "selector". The second field is a variable length payload. The total packet's length must be provided by the underlying datagram link layer or by an additional framing protocol. The payload's length is computed by subtracting 8 Bytes from the packet length. 3.3 Selector Format and Values The selector field of a SelNet packet permits to demultiplex received packets to the appropriate packet handler via a Forwarding Informa- tion Base (FIB, see section 3.5). A typical packet handler would be a forwarding procedure that forwards the received packet to one or more neighbors (as encoded in the handler) after having replaced the selector field with a value that is useful for the downstream node(s). Another packet handler could take the received packet, Tschudin Expires Sep 11, 2004 [Page 5] Internet-Draft: LUNAR Protocol March 11, 2004 remove the selector header and deliver the payload to the IP stack. A third handler, for example, could deliver the payload to LUNAR's XRP block. Packets for which no handlers are installed are silently discarded. A 64-bit selector has the following fine structure: 13 bits 3 bits 48 bits +----------+---+-----------------------------------------+ | reserved |CTX| handler identifier (handID) | +----------+---+-----------------------------------------+ Selector fine structure The handler identifier (handID) values, and consequently also the corresponding selector values, exist for three different contexts: a) statically assigned handler IDs b) receiver chosen handler IDs c) sender chosen handler IDs The context (CTX) is encoded inside the selector at the bit positions 48 to 50, where the context value is: 0 static 1 receiver chosen 2 sender chosen 3-7 reserved Static HIDs are "well known", their unique values are assigned on a global basis. The following value has been allocated for LUNAR: SELNET_LUNAR_XRP 0x8000000000000002ULL Receiver chosen handIDs are dynamically allocated by a node which plans to receive in the future correspondingly labeled SelNet pack- ets. A typical usage are reply handlers where a node installs a han- dler that shall by used by other nodes to report back a result. The request to neighbors thus has to carry such a selector with a dynami- cally generated handID as a "reply-to address". Because the receiver can access the local demultiplexing table, it can find and allocate unique, i.e. unused handID values. Sender chosen handIDs are also dynamically allocated but there is no way of knowing whether their values will be unique on the receiving side. Typically, selectors in this context are chosen randomly in Tschudin Expires Sep 11, 2004 [Page 6] Internet-Draft: LUNAR Protocol March 11, 2004 order to minimize the danger of collision. Note: that the Simple Active Packet Format [SAPF] uses the "reserved" bits of a selector to add redundancy information, permitting to recover up to two bit errors in the selector value. This feature is not used in LUNAR, therefore the sender should set the corresponding bits to 0 except for the top bit (position 63). The receiver must discard the reserved bits and only use the 51 least significant bits of a received selector value. 3.4 Network Pointers In order to create multihop forwarding routes in SelNet, LUNAR will install "network pointers" [NETPTR] on intermediate nodes. Packets sent to such a pointer shall be forwarded to the next network pointer until they are received at the end of the SelNet route. The Ethernet destination as well as the selector value of a packet will be rewrit- ten on each leg of the forwarding route: .--------------. .-----------------. | S -> S' @ E' | | S' -> S'' @ E'' | `--------------' `-----------------' SelNet E ^ | E' ^ | packet | | | | to "S @ E" | | pkt to "S' @ E'" | | >--------------' `------->-----------' `---------> Ethernet addr and selector rewriting during forwarding A network pointer instance is a rewriting rule which contain the Eth- ernet address E' of its downstream node and a selector S' which iden- tifies either another network pointer or the final delivery routine. SelNet's forwarding of data packets and the use of network pointers is very similar to the label swapping of MPLS [RFC3031]. Unlike MPLS, there is no label distribution protocol other than the one imple- mented by LUNAR or any other routing algorithm. SelNet envisages the presence of more general packet processing functions (packet han- dlers) which offer a richer functionality than plain forwarding but which are also addressed by selectors (labels). 3.5 Forwarding Information Base (FIB) Network pointer (instances) are implemented through packet handlers. The table which contains the bindings between selector values and the associated packet handlers is called the Forwarding Information Base. Tschudin Expires Sep 11, 2004 [Page 7] Internet-Draft: LUNAR Protocol March 11, 2004 Entries in the FIB are either permanent (e.g., LUNAR's packet handler for the SELNET_LUNAR_XRP selector) or transient. Transient entries are removed by the system (garbage collected) after 6 seconds latest. This also erases all state associated with this entry or packet han- dler. LUNAR implementations may reduce the life time of transient entries further based on the number of packets or bytes they have processed. FIB entries have an activity flag which is set each time the entry has been traversed by a SelNet packet. The activity flag can be queried and is reset at the same occasion. 4 LUNAR Protocol Logic The LUNAR protocol logic is responsible for creating unicast SelNet routes and SelNet broadcast delivery trees. By using appropriate con- trol messages, the LUNAR protocol will create "multihop forwarding circuits" for SelNet data packets. 4.1 LUNAR Unicast Routes Given a target IP address, LUNAR attempts to create a SelNet route from the source to the target. In the successful case the algorithm returns a local selector value D identifying the first network pointer of the found forwarding route. The unsuccessful case is rec- ognized by a timeout (see section 6.3) LUNAR discovers routes by a flooding algorithm. The source nodes broadcasts a LUNAR route request (RREQ) message with the following fields (optional fields are marked with an asterix; additional fields may also be carried in RREQ messages): Field Name Data Type Comment RREQ_TTL int remaining permitted hops RREQ_SERIES selector identifies the RREQ RREQ_TARGET IPv4 or IPv6 identifies the target RREQ_REPLYTO sel/eth pair where to send back replies RREQ_BACKPTR* sel/eth pair ptr of return data route RREQ_SRC* IPv4 or IPv6 identifies the source RREQ_SOURCEHID* 128 bits source host id RREQ_TARGETHID* 128 bits target host id Route Reply (RREP) messages have the following fields (optional fields are marked with an asterix, other fields may also be carried Tschudin Expires Sep 11, 2004 [Page 8] Internet-Draft: LUNAR Protocol March 11, 2004 in RREP messages): Field Name Data Type Comment RREP_HOPS int distance to target RREP_FWDPTR sel/eth pair where to send data to RREP_TARGETHID* 128 bits target host id The route discovery algorithm of LUNAR works as follows: 0) This is the initialization step at the node that wishes to discover a route: 0.a) Allocate an unused "receiver chosen" selector S and bind it to a transient "source RREP packet handler". The logic of this handler is defined at step 4). 0.b) Allocate a random "sender chosen" selector Q and add an entry to the FIB which binds Q to a null packet handler. 0.c) Create a RREQ message with the mandatory fields assigned as follows: Field Name Value RREQ_TTL (LUNAR_MIN_RING - 1) or (LUNAR_MAX_RING - 1), see section 6.3 RREQ_SERIES selector Q RREQ_TARGET IPv4 or IPv6 addr of target RREQ_REPLYTO pair of S and own Ethernet addr E 0.d) The optional RREQ_BACKPTR and RREQ_SRC fields should be used if the source node knows or guesses that the target node will need a route back to the source. These fields permit to estab- lish a parallel data forwarding route from the target to the source node in the same discovery process. To this end, the source allocates a "receiver chosen" selector B and binds it to a transient "IP delivery packet handler" (the logic of this handler is defined at step 5). The RREQ under construction has to be extended to also contain the two fields: Field Name Value RREQ_BACKPTR pair of B and own Ethernet addr E RREQ_SRC IPv4 or IPv6 addr of source Tschudin Expires Sep 11, 2004 [Page 9] Internet-Draft: LUNAR Protocol March 11, 2004 0.e) If the source node has a globally unique host identifier (e.g., a hash value of a cryptographically certified name or a good random number generated at boot time), it should fill in the same bits into the RREQ_SOURCEHID field for each discovery request. 0.f) If the source node knows for the target given in RREQ_TARGET its unique host identifier, it should add it in the RREQ_TAR- GETHID field in all route discovery requests for this target. 0.g) This RREQ message becomes the payload of a SelNet packet with selector SELNET_LUNAR_XRP. It is sent to the Ethernet broad- cast address "ff:ff:ff:ff:ff:ff". 1) The permanent "RREQ packet handler" defined in the following steps is responsible for processing RREQ packets: 1.a) On reception of a RREQ message, search the FIB for an entry for the selector in the RREQ_SERIES field. If an entry exists, discard the packet and exit. 1.b) Add an entry to the FIB for the selector in the RREQ_SERIES field (and let it point to a null packet handler). 1.c) Compare the RREQ_TARGET field with own IP address. If it does not match then proceed with step 1.d). If there is no RREQ_TARGETHID field then proceed with step 2). If the RREQ_TARGETHID matches this node's host identifier then also proceed with step 2). 1.d) If the RREQ_TTL field is zero, discard the packet and exit. 1.e) Allocate an unused "receiver chosen" selector S and bind it to a transient "Intermediate RREP packet handler" instantiated with the value of the RREQ_REPLYTO field. The logic of this handler is defined at step 3). If the RREQ contains a RREQ_BACKPTR then generate a "receiver chosen" selector B' and pass RREQ_BACKPTR and B' also to the handler instance. 1.f) Create a new RREQ packet by copying all fields of the incoming RREQ except for the following fields which obtain new values: Field Name Content RREQ_TTL incoming RREQ_TTL decremented by 1 RREQ_REPLYTO pair of S and own Ethernet address E' Tschudin Expires Sep 11, 2004 [Page 10] Internet-Draft: LUNAR Protocol March 11, 2004 If the incoming RREQ had a RREQ_BACKPTR and a RREQ_SRC field, also replace in the outgoing RREQ the field RREQ_BACKPTR pair of B' and own Ethernet address E' 1.g) Broadcast this new RREQ (using the same selector SEL- NET_LUNAR_XRP and Ethernet address "ff:ff:ff:ff:ff:ff" as before) and exit. 2) Target found branch: 2.a) If the RREQ message has a RREQ_BACKPTR and a RREQ_SRC field, allocate a "receiver chosen" selector A and bind it to a tran- sient network pointer as specified by RREQ_BACKPTR. Inform the IP adaption and steering layer about the new SelNet route for host RREQ_SRC available at selector A. The IP adaption and steering layer must treat this new entry as if it was already LUNAR_REVERSE_ROUTE_RRET_OFFSET milliseconds old (see Section 6.5) 2.b) Allocate a "receiver chosen" selector T and bind it to a tran- sient "IP delivery packet handler" (the logic of this handler is defined at step 5). 2.c) Create a RREP packet with the following field values: Field Name Value RREP_HOPS 0 RREP_FWDPTR pair of T and own Ethernet address E' 2.d) If the target node has a globally unique host identifier, it should fill in the the same bits into the RREP_TARGETHID field for each RREP message. 2.e) Send this RREP packet to the network pointer given in the RREQ_REPLYTO field and exit. 3) "Intermediate RREP packet handler" for the processing of one RREP message: 3.a) If this handler was initiated with a RREQ_BACKPTR value, cre- ate a network pointer with the RREQ_BACKPTR value and bind it to the selector B' that was generated in step 1.e). Tschudin Expires Sep 11, 2004 [Page 11] Internet-Draft: LUNAR Protocol March 11, 2004 3.b) Allocate a "receiver chosen" selector F and bind it to a net- work pointer pointing to RREP_FWDPTR. 3.c) Create a new RREP packet by copying all fields of the incoming RREP except for the following fields which obtain new values: Name Content RREQ_HOPS incoming RREP_HOPS incremented by 1 RREP_FWDPTR pair of F and own Ethernet address E'' 3.d) Send this RREP message to the network pointer obtained from the field RREQ_REPLYTO in step 1.e). 3.e) Remove this "Intermediate RREP packet handler" instance and exit. 4) "Source RREP packet handler": 4.a) Allocate a "receiver chosen" selector D and bind it to a net- work pointer pointing to RREP_FWDPTR. 4.b) Remove this handler instance and inform the IP adaption and steering layer about the result of the LUNAR route setup algo- rithm: A new SelNet route to the given target is now available at selector D. Exit. 5) "IP delivery packet handler": 5.a) Remove the selector field from the received SelNet packet and deliver the payload to the IP stack. This ends the description of the LUNAR discovery algorithm for uni- cast routes. 4.2 LUNAR Broadcast Trees This section needs to be written ... consult the source. 5 The eXtensible Resolution Protocol (XRP) The eXtensible Resolution Protocol defines a presentation format for LUNAR's RREQ and RREP messages. It permits to specify a variable and extensible number of parameter fields. The parameter format resembles Tschudin Expires Sep 11, 2004 [Page 12] Internet-Draft: LUNAR Protocol March 11, 2004 the encoding of RSVP "objects" [RFC2205, Sect 3.1.2]. 5.1 Overview An XRP message is a sequence of XRP commands. Each command is intro- duced by a 32-bit command header: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1| XRP command | ttl | reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ followed by zero or more command parameters. Command parameters have the format: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0| length (in bytes) | class | class-type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... contents ... | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ and are always padded to a 32-bit boundary. Several XRP commands with their parameters may be put back to back in the same XRP message. The XRP message is terminated by an end-of-mes- sage pseudo command of the form: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1| 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5.2 Commands The XRP end-of-message pseudo command is defined as XRP_CMD_EOM 0x0000 LUNAR defines two XRP commands: XRP_CMD_LUNAR_RREQ 0x0001 XRP_CMD_LUNAR_RREP 0x0002 5.3 Command Parameters XRP command parameters are of variable length: The parameter's length Tschudin Expires Sep 11, 2004 [Page 13] Internet-Draft: LUNAR Protocol March 11, 2004 field indicates the real length of the parameter data, including the 4 bytes of the parameter header. Parameters are zero-padded to the next 32-bit boundary. Parameters can appear inside the parameter block at arbitrary places, thus are not bound to a specific position. Their semantics is given by the "class" field, which names the parameter. The "class-type" field defines the parameter's data type. As an example, in a RREQ command, the parameter with the class RREQ_TARGET can have one of two class-types: IPv4 or IPv6. 5.4 LUNAR Specific XRP Definitions The following parameter class constants are defined for XRP and the LUNAR commands: XRP_CLASS_LUNAR_RREQ_SERIES 1 XRP_CLASS_LUNAR_RREQ_REPLYTO 2 XRP_CLASS_LUNAR_RREQ_TARGET 3 XRP_CLASS_LUNAR_RREQ_BACKPTR 4 XRP_CLASS_LUNAR_RREQ_SRC 5 XRP_CLASS_LUNAR_RREQ_SOURCEHID 6 XRP_CLASS_LUNAR_RREQ_TARGETHID 7 XRP_CLASS_LUNAR_RREP_FWDPTR 8 XRP_CLASS_LUNAR_RREP_TARGETHID 9 Note that the parameter RREQ_TTL is carried in the RREQ command's TTL field, while the RREP_HOPS parameter is carried in the RREP command's TTL field. The following class-types are used for LUNAR: XRP_CTYPE_SELECTOR 1 XRP_CTYPE_IPv4 2 XRP_CTYPE_IPv6 3 XRP_CTYPE_SEL_ETH 4 XRP_CTYPE_SEL_IPv4_UDP 5 XRP_CTYPE_HID128 6 All values are encoded in network byte order. Simple type values (selector, IPv4, IPv6 or 128-bit host identifier) are placed directly behind the four bytes of the parameter header. A two-tuple value of a XRP_CTYPE_SEL_ETH parameter is encoded in the order: 8 selector bytes followed by 6 Ethernet address bytes followed by 2 padding bytes (not accounted for in the parameter's length Tschudin Expires Sep 11, 2004 [Page 14] Internet-Draft: LUNAR Protocol March 11, 2004 field). A two-tuple value of a XRP_CTYPE_SEL_IPv4_UDP parameter is encoded in the order: 8 selector bytes followed by 4 IPv4 address bytes followed by 2 UDP port bytes followed by 2 padding bytes (not accounted for in the parameter's length field). 5.5 Encoding Example A LUNAR RREQ message sent by host 192.168.42.15 with Ethernet address 00:E0:00:89:BA:FA for discovering host 192.168.42.64 is encoded as an XRP message as follows: 0x80 0x01 0x03 0x00 ; LUNAR_RREQ command, ttl=3 0x00 0x0c 0x01 0x01 ; RREQ_SERIES parameter 0x80 0x02 0x56 0x5a 0x33 0x62 0xa8 0xc7 0x00 0x08 0x03 0x02 ; RREQ_TARGET parameter 0xc0 0xa8 0x2a 0x40 0x00 0x08 0x05 0x02 ; RREQ_SRC parameter 0xc0 0xa8 0x2a 0x0f 0x00 0x12 0x02 0x04 ; RREQ_REPLYTO parameter 0x80 0x01 0xfa 0x22 0xac 0x43 0x44 0xae 0x00 0xe0 0x00 0x89 0xba 0xfa 0x00 0x00 0x00 0x12 0x04 0x04 ; RREQ_BACKPTR parameter 0x80 0x01 0x6a 0xdd 0xad 0x23 0xa8 0xfa 0x00 0xe0 0x00 0x89 0xba 0xfa 0x00 0x00 0x80 0x00 ; end-of-msg 6 IP Adaption and Steering Layer LUNAR's IP Adaption and Steering Layer (ASL) is an emulation layer that creates an IP subnet illusion using the LUNAR services. It is responsible for steering LUNAR's operation by starting the route dis- covery, for refreshing routes and for providing IP address allocation support. 6.1 IPv4 Subnet for LUNAR Typically, the IP adaption and steering layer of LUNAR will present its emulation services to the IP stack as a low level Ethernet Tschudin Expires Sep 11, 2004 [Page 15] Internet-Draft: LUNAR Protocol March 11, 2004 device; In fact, LUNAR could also be implemented on the WiFi inter- face card itself. From an operating point of view, this permits to treat a LUNAR cloud as an Ethernet LAN where a single subnet entry in the IP route table suffices. Hence, all mobile nodes of a LUNAR network have to belong to the same IP subnet. The standard LUNAR profile defines 192.168.42.0/24 as the default IPv4 prefix (see also Section 7.1) 6.2 DHCP Interception for IPv4 Address Allocation The standard way for an IP stack to obtain a dynamic IPv4 address is to use the DHCP protocol [RFC2131]. The IP Adaption and Steering Layer (ASL) intercepts a node's DHCP queries and answers them directly, thus implements a rudimentary and fake DHCP server. If the DHCP_DISCOVER query requests the allocation of a specific address outside the LUNAR prefix, a DHCP_NAK message is returned. If the requested address is inside the LUNAR prefix, the ASL retains it for testing. In case of a DHCP_DISCOVER message without IP number request, a random host id (not including the subnet broadcast addresses) within the LUNAR IPv4 prefix is chosen for testing. The ASL tests for address collisions by trying to create a LUNAR route for the given address. This will be attempted up to LUNAR_IPADDR_PROBE_MAX times, with a wait interval of LUNAR_IPADDR_PROBE_WAIT milliseconds between each try and using a diameter of LUNAR_MAX_RING. If all attempts fail, a DHCP_ACK message is returned if the address was explicitly requested, or a DHCP_OFFER otherwise. If that address already exists in the LUNAR network (i.e., the LUNAR algorithm succeeds) and the IP stack had requested a spe- cific IP address, a DHCP_NAK message is returned. Otherwise, a new random address is chosen as above and the collision test repeated. Up to LUNAR_IPADDR_MAX_RETRIES random addresses will be tested before giving up. 6.3 ARP Interception and Route Discovery Steering In each node, the IP Adaption and Steering Layer maintains an IP-to- Selector table where IP destination addresses are mapped to selec- tors. These selectors identify local entries in the FIB pointing to the first network pointer of a SelNet route. This table can also be used to store host identifiers as received in the RREP_TARGETHID and sent in the RREQ_TARGETHID field of LUNAR control messages (see steps 2.d and 0.f, respectively, in section 4.1). Tschudin Expires Sep 11, 2004 [Page 16] Internet-Draft: LUNAR Protocol March 11, 2004 When the IPv4 stack has to send an IP datagram to a host in the LUNAR network for the first time, it will issue an ARP request for mapping the destination IP number to an Ethernet address. The IP Adaption and Steering Layer intercepts this ARP request. If the host to be looked up in the ARP request is in the IP-to-Selec- tor table, an ARP reply is sent back to the IP stack, giving the low 48 bits of the associated selector as the target's Ethernet address. Alternatively, the node's ARP table is manipulated directly and the IP stack informed about the change. If the address is not in the IP-to-Selector table, the ASL will trig- ger the LUNAR route discovery algorithm with a search limit of LUNAR_MIN_RING hops. If this limited LUNAR discovery succeeds (thus returns selector D), a corresponding entry is added to the IP-to- selector table and an ARP reply is sent back as described above. If the limited LUNAR discovery does not succeed within (LUNAR_TIME- OUT_PER_RING * LUNAR_MIN_RING) milliseconds, more discovery attempts will be made, now with the LUNAR_MAX_RING diameter. The ASL will wait (LUNAR_TIMEOUT_PER_RING * LUNAR_MAX_RING) milliseconds before attempting a next route discovery. As soon as a route is discovered, an ARP reply is sent back as described above and the discovery stops. After a total of (1 + LUNAR_MAX_RETRIES) unsuccessful discovery attempts, including the limited initial limited discovery, the ASL will give up and the ARP request is silently dropped. Alternatively, the failure of the pend- ing ARP request is directly reflected in the operating system's ARP table and the IP stack informed about the change. ARP requests that are intercepted while another ARP request for the same destination is currently being processed, are silently dropped. 6.4 IP Datagram Transmission For each IP datagram sent by the IP stack to the ASL, the destination Ethernet address is extracted. The six Ethernet bytes become the lower six bytes of a "receiver chosen" selector. This selector and the IP datagram are used to form a SelNet packet that is handed over to the local SelNet layer. There, it is demultiplexed to the SelNet route, if it exists, or dropped otherwise. 6.5 Forced Rediscovery of Routes The ASL keeps a timer for each entry in the IP-to-Selector table. Tschudin Expires Sep 11, 2004 [Page 17] Internet-Draft: LUNAR Protocol March 11, 2004 This timer is reset each time the LUNAR algorithm successfully estab- lished a SelNet route to an IP destination. a) Let T be (LUNAR_FORCED_RRET + random(-LUNAR_RRET_JITTER ... +LUNAR_RRET_JITTER)). When the timer of an entry times out after T milliseconds, the ASL examines whether the correspond- ing SelNet route has been used during the last T milliseconds (see note on the activity flag in section 3.5). If not, pro- ceed with step d). b) The ASL will launch a new LUNAR discovery for the entry's IP number. During this time, the entry in the IP-to-Selector ta- ble is not changed and any old SelNet route will continue to function. c) After successful discovery, the IP-to-selector table is updated so that all subsequent IP datagrams will use the new SelNet route. At the same time an ARP packet is generated and sent to the IP stack with the new Ethernet number (extracted from the result selector D) that is now associated with the IP address. Alternatively, the node's ARP table is manipulated directly and the IP stack informed about the change. d) If the re-discovery fails or the SelNet route was inactive for more than T milliseconds, the entry in the IP-to-Selector is removed. If technically possible, the corresponding entry in the operating system's ARP table is directly removed and the IP stack informed about the change. Nothing needs to be done with the old routes' selectors: old routes will be automatically garbage collected by the SelNet mechanism. Note that the reverse SelNet route from the destination to the source node is managed by the destination and needs no attention from the source node. 7 LUNAR Profiles and Configuration Parameters This section defines the LUNAR configuration profiles which comprises all algorithm independent settings required for interoperability. This section also recapitulates LUNAR's timing and other algorithm constants. 7.1 LUNAR Profiles Tschudin Expires Sep 11, 2004 [Page 18] Internet-Draft: LUNAR Protocol March 11, 2004 LUNAR profiles are configuration sets which can easily be switched by out-of-band coordination. For example, instead of the default "red profile", participants in a convention hall can agree to use LUNAR's "blue profile" which uses another WiFi channel and bandwidth not shared by the "red profile". The default LUNAR profile, called the "red profile", is defined as: Phys+Link Layer: WiFi (IEEE 802.11b) WiFi mode: ad-hoc WiFi ESSID: LUNAR WiFi channel: 3 IP subnet: 192.168.42.0/24 The LUNAR profile called the "blue profile", is defined as: Phys+Link Layer: WiFi (IEEE 802.11b) WiFi mode: ad-hoc WiFi ESSID: LUNAR WiFi channel: 6 IP subnet: 192.168.43.0/24 7.2 Summary of Configuration Parameters LUNAR_MIN_RING 1 diameter of first discovery wave LUNAR_MAX_RING 3 max network diameter LUNAR_TIMEOUT_PER_RING 25 ms: RTT per ring LUNAR_MAX_RETRIES (LUNAR_MAX_RING+3) giveup count LUNAR_FORCED_RRET 3000 ms: Route Re-Esta- blishment Time LUNAR_RRET_JITTER 100 ms LUNAR_REVERSE_ROUTE_RRET_OFFSET 1500 ms LUNAR_IPADDR_PROBE_MAX 3 unused addr count LUNAR_IPADDR_PROBE_WAIT 500 ms: delay between probes LUNAR_IPADDR_MAX_RETRIES 50 giveup count LUNAR_BRCAST_DELAY 30 ms: delay before blasting 8 Security Considerations This document does not address security, although it raises security concerns: Like most ad hoc routing protocols, LUNAR is vulnerable to all attacks known in the field [MOLVA]. However, LUNAR provides be a good platform for building a secure version of this ad hoc routing protocol because (a) XRP messages can easily be extended to carry authentication data or other cryptographic tokens, (b) there is no Tschudin Expires Sep 11, 2004 [Page 19] Internet-Draft: LUNAR Protocol March 11, 2004 sharing of routing state built into the LUNAR algorithm so trust domains are separated. Hence, (c) the end-to-end RREQ/RREP protocol could be modified to work on cryptographic host identifiers and to include a challenge/response scheme. 9 Numbering Considerations LUNAR shares or introduces numbering ranges which need global coordi- nation. a) SelNet Ethertype -- because of the difficulties to obtain an Ethernet Protocol ID for SelNet from IEEE, we have picked the value 0x4242. More widespread use of SelNet will require a rectification of this situation. b) SelNet "static" selector values need to be globally unique. A new registry is to be created for these selectors and the value SELNET_LUNAR_XRP 0x8000000000000002ULL be assigned for LUNAR. The XRP command values, class and class-type numbers in this document are defined inside the SELNET_LUNAR_XRP context and hence need no global coordi- nation. c) A static IP number is allocated to each LUNAR profile. Acknowledgements We wish to acknowledge the comments and improvements suggested by Henrik Lundgren, Erik Nordstrom and Evgeny Osipov. References [MOLVA] Molva R. and Michiardi, P., "Security in Ad Hoc Networks", Proc PWC'2003, LNCS 2775, Sep 2003. [NETPTR] Tschudin, C. and Gold, R., "Network Pointers", First Workshop on Hot Topics in Networks (HotNets-I), Oct 2002. Tschudin Expires Sep 11, 2004 [Page 20] Internet-Draft: LUNAR Protocol March 11, 2004 [RFC826] Plummer, D., "An Ethernet Address Resolution Protocol -or- Convert- ing Network Addresses to 48-bit Ethernet Address for Transmission on Ethernet Hardware", STD 37, RFC 826, Nov 1982. [RFC2131] Droms, R., "Dynamic Host Configuration Protocol (DHCP)", RFC 2131, Mar 1997. [RFC2205] Braden, R. (Ed.), Zhang, L., Berson, S., Herzog, S. and Jamin, S., "Resource ReserVation Protocol (RSVP) -- Version 1 Functional Spec- ification", RFC 2205, Sep 1997. [RFC3031] Rosen, E., Viswanathan, A. and Callon, R., "Multiprotocol Label Switching Architecture", RFC 3031, Jan 2001. [SAPF] Decasper, D. and Tschudin C., "Simple Active Packet Format", work in progress, Aug 1998. References [RFC826], [RFC2131], [RFC2205] and [RFC3031] are norma- tive; all others are informative. Additional Information Additional information (especially on the implementations and mailing lists) is available at http://cn.cs.unibas.ch/projects/lunar/ Comments should be sent to christian.tschudin@unibas.ch or the MANET Mailing List http://www.ietf.org/html.charters/manet-charter.html Author's Address Christian F. Tschudin CS Departement, University of Basel Bernoullistrasse 16 CH - 4053 Basel, Switzerland Phone: +41 61 267-0557 Fax: +41 61 267-0559 EMail: christian.tschudin@unibas.ch Tschudin Expires Sep 11, 2004 [Page 21]