Contiki 2.6

route-discovery.c

Go to the documentation of this file.
00001 /**
00002  * \addtogroup routediscovery
00003  * @{
00004  */
00005 
00006 /*
00007  * Copyright (c) 2007, Swedish Institute of Computer Science.
00008  * All rights reserved.
00009  *
00010  * Redistribution and use in source and binary forms, with or without
00011  * modification, are permitted provided that the following conditions
00012  * are met:
00013  * 1. Redistributions of source code must retain the above copyright
00014  *    notice, this list of conditions and the following disclaimer.
00015  * 2. Redistributions in binary form must reproduce the above copyright
00016  *    notice, this list of conditions and the following disclaimer in the
00017  *    documentation and/or other materials provided with the distribution.
00018  * 3. Neither the name of the Institute nor the names of its contributors
00019  *    may be used to endorse or promote products derived from this software
00020  *    without specific prior written permission.
00021  *
00022  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
00023  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00024  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00025  * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
00026  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00027  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00028  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00029  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00030  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00031  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00032  * SUCH DAMAGE.
00033  *
00034  * This file is part of the Contiki operating system.
00035  *
00036  * $Id: route-discovery.c,v 1.20 2010/01/27 08:12:56 adamdunkels Exp $
00037  */
00038 
00039 /**
00040  * \file
00041  *         Route discovery protocol
00042  * \author
00043  *         Adam Dunkels <adam@sics.se>
00044  */
00045 
00046 #include "contiki.h"
00047 #include "net/rime.h"
00048 #include "net/rime/route.h"
00049 #include "net/rime/route-discovery.h"
00050 
00051 #include <stddef.h> /* For offsetof */
00052 #include <stdio.h>
00053 
00054 struct route_msg {
00055   rimeaddr_t dest;
00056   uint8_t rreq_id;
00057   uint8_t pad;
00058 };
00059 
00060 struct rrep_hdr {
00061   uint8_t rreq_id;
00062   uint8_t hops;
00063   rimeaddr_t dest;
00064   rimeaddr_t originator;
00065 };
00066 
00067 #if CONTIKI_TARGET_NETSIM
00068 #include "ether.h"
00069 #endif
00070 
00071 
00072 #define DEBUG 0
00073 #if DEBUG
00074 #include <stdio.h>
00075 #define PRINTF(...) printf(__VA_ARGS__)
00076 #else
00077 #define PRINTF(...)
00078 #endif
00079 
00080 /*---------------------------------------------------------------------------*/
00081 static char rrep_pending;               /* A reply for a request is pending. */
00082 /*---------------------------------------------------------------------------*/
00083 static void
00084 send_rreq(struct route_discovery_conn *c, const rimeaddr_t *dest)
00085 {
00086   rimeaddr_t dest_copy;
00087   struct route_msg *msg;
00088 
00089   rimeaddr_copy(&dest_copy, dest);
00090   dest = &dest_copy;
00091 
00092   packetbuf_clear();
00093   msg = packetbuf_dataptr();
00094   packetbuf_set_datalen(sizeof(struct route_msg));
00095 
00096   msg->pad = 0;
00097   msg->rreq_id = c->rreq_id;
00098   rimeaddr_copy(&msg->dest, dest);
00099 
00100   netflood_send(&c->rreqconn, c->rreq_id);
00101   c->rreq_id++;
00102 }
00103 /*---------------------------------------------------------------------------*/
00104 static void
00105 send_rrep(struct route_discovery_conn *c, const rimeaddr_t *dest)
00106 {
00107   struct rrep_hdr *rrepmsg;
00108   struct route_entry *rt;
00109   rimeaddr_t saved_dest;
00110   
00111   rimeaddr_copy(&saved_dest, dest);
00112 
00113   packetbuf_clear();
00114   dest = &saved_dest;
00115   rrepmsg = packetbuf_dataptr();
00116   packetbuf_set_datalen(sizeof(struct rrep_hdr));
00117   rrepmsg->hops = 0;
00118   rimeaddr_copy(&rrepmsg->dest, dest);
00119   rimeaddr_copy(&rrepmsg->originator, &rimeaddr_node_addr);
00120   rt = route_lookup(dest);
00121   if(rt != NULL) {
00122     PRINTF("%d.%d: send_rrep to %d.%d via %d.%d\n",
00123            rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00124            dest->u8[0],dest->u8[1],
00125            rt->nexthop.u8[0],rt->nexthop.u8[1]);
00126     unicast_send(&c->rrepconn, &rt->nexthop);
00127   } else {
00128     PRINTF("%d.%d: no route for rrep to %d.%d\n",
00129            rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00130            dest->u8[0],dest->u8[1]);
00131   }
00132 }
00133 /*---------------------------------------------------------------------------*/
00134 static void
00135 insert_route(const rimeaddr_t *originator, const rimeaddr_t *last_hop,
00136              uint8_t hops)
00137 {
00138   PRINTF("%d.%d: Inserting %d.%d into routing table, next hop %d.%d, hop count %d\n",
00139          rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00140          originator->u8[0], originator->u8[1],
00141          last_hop->u8[0], last_hop->u8[1],
00142          hops);
00143   
00144   route_add(originator, last_hop, hops, 0);
00145   /*
00146     struct route_entry *rt;
00147   
00148   rt = route_lookup(originator);
00149   if(rt == NULL || hops < rt->hop_count) {
00150     PRINTF("%d.%d: Inserting %d.%d into routing table, next hop %d.%d, hop count %d\n",
00151            rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00152            originator->u8[0], originator->u8[1],
00153            last_hop->u8[0], last_hop->u8[1],
00154            hops);
00155     route_add(originator, last_hop, hops, 0);
00156 #if CONTIKI_TARGET_NETSIM
00157     ether_set_line(last_hop->u8[0], last_hop->u8[1]);
00158 #endif
00159 
00160 }*/
00161 }
00162 /*---------------------------------------------------------------------------*/
00163 static void
00164 rrep_packet_received(struct unicast_conn *uc, const rimeaddr_t *from)
00165 {
00166   struct rrep_hdr *msg = packetbuf_dataptr();
00167   struct route_entry *rt;
00168   rimeaddr_t dest;
00169   struct route_discovery_conn *c = (struct route_discovery_conn *)
00170     ((char *)uc - offsetof(struct route_discovery_conn, rrepconn));
00171 
00172   PRINTF("%d.%d: rrep_packet_received from %d.%d towards %d.%d len %d\n",
00173          rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00174          from->u8[0],from->u8[1],
00175          msg->dest.u8[0],msg->dest.u8[1],
00176          packetbuf_datalen());
00177 
00178   PRINTF("from %d.%d hops %d rssi %d lqi %d\n",
00179          from->u8[0], from->u8[1],
00180          msg->hops,
00181          packetbuf_attr(PACKETBUF_ATTR_RSSI),
00182          packetbuf_attr(PACKETBUF_ATTR_LINK_QUALITY));
00183 
00184   insert_route(&msg->originator, from, msg->hops);
00185 
00186   if(rimeaddr_cmp(&msg->dest, &rimeaddr_node_addr)) {
00187     PRINTF("rrep for us!\n");
00188     rrep_pending = 0;
00189     ctimer_stop(&c->t);
00190     if(c->cb->new_route) {
00191       rimeaddr_t originator;
00192 
00193       /* If the callback modifies the packet, the originator address
00194          will be lost. Therefore, we need to copy it into a local
00195          variable before calling the callback. */
00196       rimeaddr_copy(&originator, &msg->originator);
00197       c->cb->new_route(c, &originator);
00198     }
00199 
00200   } else {
00201     rimeaddr_copy(&dest, &msg->dest);
00202 
00203     rt = route_lookup(&msg->dest);
00204     if(rt != NULL) {
00205       PRINTF("forwarding to %d.%d\n", rt->nexthop.u8[0], rt->nexthop.u8[1]);
00206       msg->hops++;
00207       unicast_send(&c->rrepconn, &rt->nexthop);
00208     } else {
00209       PRINTF("%d.%d: no route to %d.%d\n", rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1], msg->dest.u8[0], msg->dest.u8[1]);
00210     }
00211   }
00212 }
00213 /*---------------------------------------------------------------------------*/
00214 static int
00215 rreq_packet_received(struct netflood_conn *nf, const rimeaddr_t *from,
00216                      const rimeaddr_t *originator, uint8_t seqno, uint8_t hops)
00217 {
00218   struct route_msg *msg = packetbuf_dataptr();
00219   struct route_discovery_conn *c = (struct route_discovery_conn *)
00220     ((char *)nf - offsetof(struct route_discovery_conn, rreqconn));
00221 
00222   PRINTF("%d.%d: rreq_packet_received from %d.%d hops %d rreq_id %d last %d.%d/%d\n",
00223          rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00224          from->u8[0], from->u8[1],
00225          hops, msg->rreq_id,
00226      c->last_rreq_originator.u8[0],
00227      c->last_rreq_originator.u8[1],
00228          c->last_rreq_id);
00229 
00230   if(!(rimeaddr_cmp(&c->last_rreq_originator, originator) &&
00231        c->last_rreq_id == msg->rreq_id)) {
00232 
00233     PRINTF("%d.%d: rreq_packet_received: request for %d.%d originator %d.%d / %d\n",
00234            rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00235            msg->dest.u8[0], msg->dest.u8[1],
00236            originator->u8[0], originator->u8[1],
00237            msg->rreq_id);
00238 
00239     rimeaddr_copy(&c->last_rreq_originator, originator);
00240     c->last_rreq_id = msg->rreq_id;
00241 
00242     if(rimeaddr_cmp(&msg->dest, &rimeaddr_node_addr)) {
00243       PRINTF("%d.%d: route_packet_received: route request for our address\n",
00244              rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1]);
00245       PRINTF("from %d.%d hops %d rssi %d lqi %d\n",
00246              from->u8[0], from->u8[1],
00247              hops,
00248              packetbuf_attr(PACKETBUF_ATTR_RSSI),
00249              packetbuf_attr(PACKETBUF_ATTR_LINK_QUALITY));
00250 
00251       insert_route(originator, from, hops);
00252       
00253       /* Send route reply back to source. */
00254       send_rrep(c, originator);
00255       return 0; /* Don't continue to flood the rreq packet. */
00256     } else {
00257       /*      PRINTF("route request for %d\n", msg->dest_id);*/
00258       PRINTF("from %d.%d hops %d rssi %d lqi %d\n",
00259              from->u8[0], from->u8[1],
00260              hops,
00261              packetbuf_attr(PACKETBUF_ATTR_RSSI),
00262              packetbuf_attr(PACKETBUF_ATTR_LINK_QUALITY));
00263       insert_route(originator, from, hops);
00264     }
00265     
00266     return 1;
00267   }
00268   return 0; /* Don't forward packet. */
00269 }
00270 /*---------------------------------------------------------------------------*/
00271 static const struct unicast_callbacks rrep_callbacks = {rrep_packet_received};
00272 static const struct netflood_callbacks rreq_callbacks = {rreq_packet_received, NULL, NULL};
00273 /*---------------------------------------------------------------------------*/
00274 void
00275 route_discovery_open(struct route_discovery_conn *c,
00276                      clock_time_t time,
00277                      uint16_t channels,
00278                      const struct route_discovery_callbacks *callbacks)
00279 {
00280   netflood_open(&c->rreqconn, time, channels + 0, &rreq_callbacks);
00281   unicast_open(&c->rrepconn, channels + 1, &rrep_callbacks);
00282   c->cb = callbacks;
00283 }
00284 /*---------------------------------------------------------------------------*/
00285 void
00286 route_discovery_close(struct route_discovery_conn *c)
00287 {
00288   unicast_close(&c->rrepconn);
00289   netflood_close(&c->rreqconn);
00290   ctimer_stop(&c->t);
00291 }
00292 /*---------------------------------------------------------------------------*/
00293 static void
00294 timeout_handler(void *ptr)
00295 {
00296   struct route_discovery_conn *c = ptr;
00297   PRINTF("route_discovery: timeout, timed out\n");
00298   rrep_pending = 0;
00299   if(c->cb->timedout) {
00300     c->cb->timedout(c);
00301   }
00302 }
00303 /*---------------------------------------------------------------------------*/
00304 int
00305 route_discovery_discover(struct route_discovery_conn *c, const rimeaddr_t *addr,
00306                          clock_time_t timeout)
00307 {
00308   if(rrep_pending) {
00309     PRINTF("route_discovery_send: ignoring request because of pending response\n");
00310     return 0;
00311   }
00312 
00313   PRINTF("route_discovery_send: sending route request\n");
00314   ctimer_set(&c->t, timeout, timeout_handler, c);
00315   rrep_pending = 1;
00316   send_rreq(c, addr);
00317   return 1;
00318 }
00319 /*---------------------------------------------------------------------------*/
00320 /** @} */