============================================================================ The Link Estimation Exchange Protocol (LEEP) ============================================================================ :TEP: 124 :Group: Network Protocol Working Group :Type: Documentary :Status: Draft :TinyOS-Version: 2.x :Author: Omprakash Gnawali :Draft-Created: 05-Feb-2006 :Draft-Version: $Revision$ :Draft-Modified: $Date$ :Draft-Discuss: TinyOS Developer List .. Note:: This memo documents a part of TinyOS for the TinyOS Community, and requests discussion and suggestions for improvements. Distribution of this memo is unlimited. This memo is in full compliance with TEP 1. Abstract ============================================================================ The memo documents the Link Estimation Exchange Protocol (LEEP). Nodes use LEEP to estimate and exchange information about the quality of links to the neighbors. 1. Introduction ============================================================================ Routing protocols often require bi-directional link qualities to compute the routes. Nodes can estimate the quality of the in-bound link from a neighbor by estimating the ratio of successfully received messages and the total transmitted messages. LEEP appends in-bound packet reception rate (PRR) estimates to packets. Other nodes hearing these packets can combine the in-bound PRR values with their own in-bound values to compute bi-directional link quality. 2. Definitions ============================================================================ 2.1 Link Quality -------------------------------------------------------------------- The link quality between a directed node pair (A,B) is the probability that a packet transmitted by A will be successfully received by B. The bidirectional link quality of an undirected node pair (A,B) is the product of the link quality of (A,B) and (B,A). This definition assumes independent link losses. It also includes the case when the link quality of (A,B) and (B,A) are different; this can occur due to local interference or noise. 2.2 In-bound Link Quality -------------------------------------------------------------------- In a node pair (A,B), with B as the node of reference, in-bound link quality is a value in the range of 0 to 255 that describes the quality of the link from A to B estimated by B by counting the successfully received packets from A among all the transmitted packets or using link quality indicators such as LQI and RSSI provided by the radio on the node B, or some other methods. 2.3 Out-bound Link Quality -------------------------------------------------------------------- In a node pair (A,B), with B as the node of reference, out-bound link quality is defined as the quality of the link from B to A. B can determine the out-bound link quality if A advertises its in-bound link qualities. LEEP is the protocol that is used to exchange the in-bound link qualities. 2.4 Link Information Entry -------------------------------------------------------------------- Link Information Entry created by node k is a tuple (n,q) where q is the in-bound link quality from node n to k. 3. The Link Estimation Exchange Protocol (LEEP) ============================================================================ 3.1 Assumptions -------------------------------------------------------------------- Following are the assumptions made by LEEP: 3.1.1. The data link frame has a single-hop source field. 3.1.2. The data link layer provides a broadcast address. 3.1.3. The data link layer provides the length of the LEEP frame. 3.2 The Protocol -------------------------------------------------------------------- To compute the bi-directional link quality, in-bound link quality must be exchanged among the neighbors. LEEP maintains a sequence number that is incremented by one for each outgoing LEEP frame. The sequence number in the LEEP frame MUST be incremented by one even if the data link layer retransmits the LEEP frame. The LEEP sequence number MAY be used to count the number of missing packets to estimate the in-bound link quality from the transmitter. LEEP MUST transmit Link Information entries describing the in-bound link qualities for a subset of its neighbors. The Link Information entry on the LEEP frame allows the receiver node to find the out-bound link quality to the transmitter node identified by the data link source address. 3.3 LEEP Frame -------------------------------------------------------------------- A LEEP frame has a header, the payload, and a footer with the Link Information (LI) entries as shown in this diagram:: ------------------------------------------------------------- | LEEP | Payload | LI Entry | LI Entry | ... | LI Entry | | Header | | 1 | 2 | | n | ------------------------------------------------------------- The number of Link Information entries can be different in each outgoing LEEP frame. The number of Link Information entries MUST not increase the size of the LEEP frame beyond the maximum payload length allowed by the data link layer. A LEEP frame can have 0 Link Information entry. 3.3.1 LEEP header -------------------------------------------------------------------- The following diagram shows the LEEP header format:: 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |nentry | rsrvd | seqno | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Field definitions: * nentry - Number of Link Information entries in the footer * seqno - LEEP sequence number. * rsrvd - Reserved and must be set to 0. 3.3.2 Link Information Entry -------------------------------------------------------------------- The following diagram shows the Link Information Entry format:: 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | node id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | link quality | +-+-+-+-+-+-+-+-+ Field definitions: * node id: the link layer address of the neighbor * link quality: The in-bound link quality from the node identified by node id to the node that transmits this Link Information entry 4. Implementation ============================================================================ The following files in ``tinyos-2.x/tos/lib/net/le`` provide a reference implementation of LEEP described in this TEP. * ``LinkEstimator.h`` and ``LinkEstimatorP.nc`` The reference implementation uses the LEEP sequence number to count the number of missing packets to estimate the in-bound link quality. The implementation tries to append Link Information entry for all the neighbors in its neighbor table by sending the largest possible data link frame. If there is still not enough room to fit all the Link Information entries, it uses a round-robin policy to select the entries to be exchanged that could not fit in the previous LEEP frame. The LEEP frames are transmitted whenever the CTP [1]_ beacons, sent as a LEEP payload, are sent. 5. Author's Address ============================================================================ | Omprakash Gnawali | Ronald Tutor Hall (RTH) 418 | 3710 S. McClintock Avenue | Los Angeles, CA 90089 | | phone - +1 213 821-5627 | email - gnawali@usc.edu | 6. Citations ============================================================================ .. [1] TEP 123: The Collection Tree Protocol.