============================================================================== The Source Routing Protocol (SRP) ============================================================================== :TEP: 139 :Group: Network Working Group :Type: Documentary :Status: Draft :TinyOS-Version: > 2.1 :Author: Chieh-Jan Mike Liang, Eric Decker, Doug Carlson, and Omprakash Gnawali :Draft-Created: 18-Jun-2010 :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 ============================================================================== This memo documents the Source Routing Protocol (SRP), which provides best-effort point-to-point datagram communication in a network. 1. Introduction ============================================================================== A source routing protocol delivers packets from the origin node to the destination node. Specifically, source routing allows the origin node to specify the route the packet should take in the network. In this respect, source routing is considered as one implementation of the forwarding engine in network protocols. The Source Routing Protocol (SRP) is a reference implementation of source routing in TinyOS 2.x. SRP is a network-level protocol built on top of the TinyOS Active Message (AM) Layer which provides unreliable delivery over multi-link routes. Users interact with SRP through the source routing interfaces described in TEP 138 [1]_. In this TEP, after a brief discussion of source routing and SRP, we specify the packet format used by SRP, and how fields in the packet are used to deliver packets in the network. There are no control frames in SRP; all information necessary for source routing is carried in the data frame. All fields in this specification are in network byte order. 2. Source routing and SRP ============================================================================== Source routing relies on the origin node to specify the list of nodes that a packet should traverse to reach the destination node. Mechanisms for path determination are beyond the scope of this specification. Source routing is useful in many cases. First, source routing may be used by protocols that compute routes centrally on more capable nodes. Such protocols might first collect link state information from the network, and then compute the routes to destination nodes of pending packets. Second, during experiments, applications can use source routing to fix the route that data packets traverse in the network. When the user of SRP provides the source route, or the list of nodes on the path, SRP stores this information in the data packet header. SRP looks up the next hop in the source route in the data packet header and forwards the data packet to the next hop. Once the data packet reaches the destination, it is considered as being successfully delivered. SRP is a best-effort protocol. During packet forwarding, if the underlying MAC layer indicates a failure in delivering packets to the next hop (i.e., the MAC layer fails to receive the packet acknowledgement), SRP drops the packet and does not need to notify the origin node. 3. Packet Format ============================================================================== SRP does not have control packets. All the information necessary for routing is contained in the data packet header. The SRP data frame consists of the header, the source routing entries (SR Entry), and the payload as shown below:: ------------------------------------------------------------- | SRP | SR Entry | SR Entry | ... | SR Entry | Payload | | Header | 0 | 1 | | n-1 | | ------------------------------------------------------------- SR Entry 0 corresponds to the origin node, and SR Entry 1 corresponds to the first-hop node on the path. Similarly, SR Entry n-1 corresponds to the destination of the packet. The number of source route entries is equal to the number of nodes on the path. SR Entries SHOULD NOT repeat as this can cause unwanted loops. 3.1 SRP header -------------------------------------------------------------------- 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | sr_len | hops_left | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | seqno | payload_id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Field definitions are as follows: * sr_len: (n) The length of the path in hops. This is equal to the number of source route entries following the SRC header. * hops_left: The remaining distance (in hops) towards the destination. Each node MUST decrement this field when it forwards the packet. It is 0 at the destination. Must be less than sr_len (0..n-1). * seqno: The value of the sequence number counter maintained by the origin node. The origin node sets this field, and a node forwarding a data frame MUST NOT modify it. The origin node SHOULD use increasing sequence numbers with wraparound. * payload_id: Higher-level protocol identifier. The origin sets this field, and a node forwarding a data frame MUST NOT modify it. 3.2 Source Routing Entry -------------------------------------------------------------------- The following diagram shows the format of the Source Routing Entry:: 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | node_id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Field definition: * node_id: the link layer address of a node on the path to the destination. 4. Implementation ============================================================================== An implementation of SRP can be found in the ``tos/lib/net/srp`` directory of TinyOS 2.x source tree. 5. Authors ==================================================================== | Chieh-Jan Mike Liang | 213 NEB, 3400 N Charles St | Johns Hopkins University | Baltimore, MD 21211 | | email - cliang4@cs.jhu.edu | | Eric B. Decker | Autonomous Systems Lab | University of California, Santa Cruz | | email - cire831@gmail.com | | Doug Carlson | 213 NEB, 3400 N Charles St | Johns Hopkins University | Baltimore, MD 21211 | | email - carlson@cs.jhu.edu | | Omprakash Gnawali | S255 Clark Center, 318 Campus Drive | Stanford University | Stanford, CA 94305 | | phone - +1 650 725 6086 | email - gnawali@cs.stanford.edu 6. Citations ==================================================================== .. [1] TEP 138: Source Routing