Contiki 2.6
|
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 /** @} */