route.c

Go to the documentation of this file.
00001 /**
00002  * \addtogroup rimeroute
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.c,v 1.18 2010/06/15 19:22:25 adamdunkels Exp $
00037  */
00038 
00039 /**
00040  * \file
00041  *         Rime route table
00042  * \author
00043  *         Adam Dunkels <adam@sics.se>
00044  */
00045 
00046 #include <stdio.h>
00047 
00048 #include "lib/list.h"
00049 #include "lib/memb.h"
00050 #include "sys/ctimer.h"
00051 #include "net/rime/route.h"
00052 #include "contiki-conf.h"
00053 
00054 #ifdef ROUTE_CONF_ENTRIES
00055 #define NUM_RT_ENTRIES ROUTE_CONF_ENTRIES
00056 #else /* ROUTE_CONF_ENTRIES */
00057 #define NUM_RT_ENTRIES 8
00058 #endif /* ROUTE_CONF_ENTRIES */
00059 
00060 #ifdef ROUTE_CONF_DECAY_THRESHOLD
00061 #define DECAY_THRESHOLD ROUTE_CONF_DECAY_THRESHOLD
00062 #else /* ROUTE_CONF_DECAY_THRESHOLD */
00063 #define DECAY_THRESHOLD 8
00064 #endif /* ROUTE_CONF_DECAY_THRESHOLD */
00065 
00066 #ifdef ROUTE_CONF_DEFAULT_LIFETIME
00067 #define DEFAULT_LIFETIME ROUTE_CONF_DEFAULT_LIFETIME
00068 #else /* ROUTE_CONF_DEFAULT_LIFETIME */
00069 #define DEFAULT_LIFETIME 60
00070 #endif /* ROUTE_CONF_DEFAULT_LIFETIME */
00071 
00072 /*
00073  * List of route entries.
00074  */
00075 LIST(route_table);
00076 MEMB(route_mem, struct route_entry, NUM_RT_ENTRIES);
00077 
00078 static struct ctimer t;
00079 
00080 static int max_time = DEFAULT_LIFETIME;
00081 
00082 #define DEBUG 0
00083 #if DEBUG
00084 #include <stdio.h>
00085 #define PRINTF(...) printf(__VA_ARGS__)
00086 #else
00087 #define PRINTF(...)
00088 #endif
00089 
00090 
00091 /*---------------------------------------------------------------------------*/
00092 static void
00093 periodic(void *ptr)
00094 {
00095   struct route_entry *e;
00096 
00097   for(e = list_head(route_table); e != NULL; e = list_item_next(e)) {
00098     e->time++;
00099     if(e->time >= max_time) {
00100       PRINTF("route periodic: removing entry to %d.%d with nexthop %d.%d and cost %d\n",
00101              e->dest.u8[0], e->dest.u8[1],
00102              e->nexthop.u8[0], e->nexthop.u8[1],
00103              e->cost);
00104       list_remove(route_table, e);
00105       memb_free(&route_mem, e);
00106     }
00107   }
00108 
00109   ctimer_set(&t, CLOCK_SECOND, periodic, NULL);
00110 }
00111 /*---------------------------------------------------------------------------*/
00112 void
00113 route_init(void)
00114 {
00115   list_init(route_table);
00116   memb_init(&route_mem);
00117 
00118   ctimer_set(&t, CLOCK_SECOND, periodic, NULL);
00119 }
00120 /*---------------------------------------------------------------------------*/
00121 int
00122 route_add(const rimeaddr_t *dest, const rimeaddr_t *nexthop,
00123           uint8_t cost, uint8_t seqno)
00124 {
00125   struct route_entry *e;
00126 
00127   /* Avoid inserting duplicate entries. */
00128   e = route_lookup(dest);
00129   if(e != NULL && rimeaddr_cmp(&e->nexthop, nexthop)) {
00130     list_remove(route_table, e);
00131   } else {
00132     /* Allocate a new entry or reuse the oldest entry with highest cost. */
00133     e = memb_alloc(&route_mem);
00134     if(e == NULL) {
00135       /* Remove oldest entry.  XXX */
00136       e = list_chop(route_table);
00137       PRINTF("route_add: removing entry to %d.%d with nexthop %d.%d and cost %d\n",
00138              e->dest.u8[0], e->dest.u8[1],
00139              e->nexthop.u8[0], e->nexthop.u8[1],
00140              e->cost);
00141     }
00142   }
00143 
00144   rimeaddr_copy(&e->dest, dest);
00145   rimeaddr_copy(&e->nexthop, nexthop);
00146   e->cost = cost;
00147   e->seqno = seqno;
00148   e->time = 0;
00149   e->decay = 0;
00150 
00151   /* New entry goes first. */
00152   list_push(route_table, e);
00153 
00154   PRINTF("route_add: new entry to %d.%d with nexthop %d.%d and cost %d\n",
00155          e->dest.u8[0], e->dest.u8[1],
00156          e->nexthop.u8[0], e->nexthop.u8[1],
00157          e->cost);
00158   
00159   return 0;
00160 }
00161 /*---------------------------------------------------------------------------*/
00162 struct route_entry *
00163 route_lookup(const rimeaddr_t *dest)
00164 {
00165   struct route_entry *e;
00166   uint8_t lowest_cost;
00167   struct route_entry *best_entry;
00168 
00169   lowest_cost = -1;
00170   best_entry = NULL;
00171   
00172   /* Find the route with the lowest cost. */
00173   for(e = list_head(route_table); e != NULL; e = list_item_next(e)) {
00174     /*    printf("route_lookup: comparing %d.%d.%d.%d with %d.%d.%d.%d\n",
00175            uip_ipaddr_to_quad(dest), uip_ipaddr_to_quad(&e->dest));*/
00176 
00177     if(rimeaddr_cmp(dest, &e->dest)) {
00178       if(e->cost < lowest_cost) {
00179         best_entry = e;
00180         lowest_cost = e->cost;
00181       }
00182     }
00183   }
00184   return best_entry;
00185 }
00186 /*---------------------------------------------------------------------------*/
00187 void
00188 route_refresh(struct route_entry *e)
00189 {
00190   if(e != NULL) {
00191     /* Refresh age of route so that used routes do not get thrown
00192        out. */
00193     e->time = 0;
00194     e->decay = 0;
00195     
00196     PRINTF("route_refresh: time %d last %d decay %d for entry to %d.%d with nexthop %d.%d and cost %d\n",
00197            e->time, e->time_last_decay, e->decay,
00198            e->dest.u8[0], e->dest.u8[1],
00199            e->nexthop.u8[0], e->nexthop.u8[1],
00200            e->cost);
00201 
00202   }
00203 }
00204 /*---------------------------------------------------------------------------*/
00205 void
00206 route_decay(struct route_entry *e)
00207 {
00208   /* If routes are not refreshed, they decay over time. This function
00209      is called to decay a route. The route can only be decayed once
00210      per second. */
00211   PRINTF("route_decay: time %d last %d decay %d for entry to %d.%d with nexthop %d.%d and cost %d\n",
00212          e->time, e->time_last_decay, e->decay,
00213          e->dest.u8[0], e->dest.u8[1],
00214          e->nexthop.u8[0], e->nexthop.u8[1],
00215          e->cost);
00216   
00217   if(e->time != e->time_last_decay) {
00218     /* Do not decay a route too often - not more than once per second. */
00219     e->time_last_decay = e->time;
00220     e->decay++;
00221 
00222     if(e->decay >= DECAY_THRESHOLD) {
00223       PRINTF("route_decay: removing entry to %d.%d with nexthop %d.%d and cost %d\n",
00224              e->dest.u8[0], e->dest.u8[1],
00225              e->nexthop.u8[0], e->nexthop.u8[1],
00226              e->cost);
00227       route_remove(e);
00228     }
00229   }
00230 }
00231 /*---------------------------------------------------------------------------*/
00232 void
00233 route_remove(struct route_entry *e)
00234 {
00235   list_remove(route_table, e);
00236   memb_free(&route_mem, e);
00237 }
00238 /*---------------------------------------------------------------------------*/
00239 void
00240 route_flush_all(void)
00241 {
00242   struct route_entry *e;
00243 
00244   while(1) {
00245     e = list_pop(route_table);
00246     if(e != NULL) {
00247       memb_free(&route_mem, e);
00248     } else {
00249       break;
00250     }
00251   }
00252 }
00253 /*---------------------------------------------------------------------------*/
00254 void
00255 route_set_lifetime(int seconds)
00256 {
00257   max_time = seconds;
00258 }
00259 /*---------------------------------------------------------------------------*/
00260 int
00261 route_num(void)
00262 {
00263   struct route_entry *e;
00264   int i = 0;
00265 
00266   for(e = list_head(route_table); e != NULL; e = list_item_next(e)) {
00267     i++;
00268   }
00269   return i;
00270 }
00271 /*---------------------------------------------------------------------------*/
00272 struct route_entry *
00273 route_get(int num)
00274 {
00275   struct route_entry *e;
00276   int i = 0;
00277 
00278   for(e = list_head(route_table); e != NULL; e = list_item_next(e)) {
00279     if(i == num) {
00280       return e;
00281     }
00282     i++;
00283   }
00284   return NULL;
00285 }
00286 /*---------------------------------------------------------------------------*/
00287 /** @} */

Generated on Mon Apr 11 14:23:31 2011 for Contiki 2.5 by  doxygen 1.6.1