N-sim
Emulation and simulation of
Wireless Sensor Networks



   Home


   Project Page


   Download


   CVS



   Installation


   Configuration


   Plug-ins




 Hosted by
SourceForge.net Logo

/home/brennan/n-sim/Vaike/linux/system-addons/networking/mesh_link.c

Go to the documentation of this file.
00001 
00014 /*
00015  * Copyright 2007. Los Alamos National Security, LLC. This material
00016  * was produced under U.S. Government contract DE-AC52-06NA25396 for
00017  * Los Alamos National Laboratory (LANL), which is operated by Los
00018  * Alamos National Security, LLC, for the Department of Energy. The
00019  * U.S. Government has rights to use, reproduce, and distribute this
00020  * software. NEITHER THE GOVERNMENT NOR LOS ALAMOS NATIONAL SECURITY,
00021  * LLC, MAKES ANY WARRANTY, EXPRESS OR IMPLIED, OR ASSUMES ANY LEGAL
00022  * LIABILITY FOR THE USE OF THIS SOFTWARE. If software is modified to
00023  * produce derivative works, such modified software should be clearly
00024  * marked, so as not to confuse it with the version available from LANL.
00025  *
00026  * Additionally, this program is free software; you can redistribute
00027  * it and/or modify it under the terms of the GNU General Public
00028  * License as published by the Free Software Foundation; version 2 of
00029  * the License. Accordingly, this program is distributed in the hope
00030  * it will be useful, but WITHOUT ANY WARRANTY; without even the
00031  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
00032  * PURPOSE. See the GNU General Public License for more details.
00033  */
00034 
00035 #include <stdio.h>
00036 #include <stdlib.h>
00037 #include <string.h>
00038 #include <sys/socket.h>
00039 #include <netinet/in.h>
00040 #include <arpa/inet.h>
00041 #include <net/route.h>
00042 #include <errno.h>
00043 #include <syslog.h>
00044 #include <netdb.h>
00045 
00046 #include "mesh_link.h"
00047 #include "mesh_metrics.h"
00048 #include "sensor_self.h"
00049 
00050 
00051 
00052 unsigned int ip_to_id(char *addr)
00053 {
00054   struct in_addr ip;
00055   if (addr == NULL)
00056     return 0;
00057   if (inet_aton(addr, &ip) == 0)
00058     return 0;
00059   return ip.s_addr;
00060 }
00061 
00062 
00063 char *ip_to_dot(unsigned int addr)
00064 {
00065   struct in_addr ip;
00066   ip.s_addr = addr;
00067   return inet_ntoa(ip);
00068 }
00069 
00070 
00071 void init_link(protocol_t *proto, link_t *link)
00072 {
00073   link->rediscover = 0;
00074   inet_aton(proto->sensor->ip_addr, &link->node);
00075   link->hop_count = 0;
00076   memset(&link->metrics, 0, sizeof(unsigned int) * NUM_LINK_METRICS);
00077   inet_aton(proto->sensor->ip_addr, &link->next_hop);
00078 }
00079 
00080 
00081 void init_link_entry(protocol_t *proto, link_entry_t *entry)
00082 {
00083   entry->node_id = ip_to_id(proto->sensor->ip_addr);
00084   entry->protocol = proto;
00085 
00086   init_link(proto, &entry->link);
00087   init_metrics(&entry->metrics);
00088   entry->time_last_used = 0;
00089 
00090   entry->send_queue.root = NULL;
00091   entry->send_seq_num = 1;
00092   entry->recv_seq_num = 0;
00093 
00094   entry->routing_backlog = NULL;
00095   entry->last_packet = NULL;
00096   entry->routing_pending = 1;
00097 
00098   entry->iface = proto->sensor->interface;
00099   strcpy(entry->bcast, proto->sensor->broadcast);
00100   strcpy(entry->nmask, proto->sensor->netmask);
00101 
00102   entry->next = NULL;
00103 }
00104 
00105 
00106 link_entry_t *new_link_entry(protocol_t *proto)
00107 {
00108   link_entry_t *link = malloc(sizeof(link_entry_t));
00109   init_link_entry(proto, link);
00110   return link;
00111 }
00112 
00113 
00114 void link_to_string(link_t *link, char *string)
00115 {
00116   char node_addr[NET_ADDR_LEN+1], hop_addr[NET_ADDR_LEN+1];
00117   strncpy(node_addr, inet_ntoa(link->node), NET_ADDR_LEN);
00118   strncpy(hop_addr, inet_ntoa(link->next_hop), NET_ADDR_LEN);
00119 
00120   sprintf(string, MESH_LINK_STR_FORMAT, node_addr,
00121           link->hop_count, link->metrics[0], link->metrics[1],
00122           link->metrics[2], link->metrics[3], hop_addr);
00123 }
00124 
00125 
00126 inline size_t header_size(void) {
00127   return sizeof(int) + sizeof(int);
00128 }
00129 
00130 
00131 inline size_t database_size(unsigned int num_links)
00132 {
00133   return header_size() + (sizeof(link_t) * num_links);
00134 }
00135 
00136 
00137 database_t *new_database(protocol_t *proto, unsigned int size)
00138 {
00139   database_t *db = malloc(database_size(size));
00140   memset(db, 0, database_size(size));
00141   db->header.size = size;
00142   db->header.protocol = proto->unique_id;
00143   return db;
00144 }
00145 
00146 
00147 void pack_database(database_t *db)
00148 {
00149   unsigned int i, j, size = db->header.size;
00150 
00151   if (db == NULL)
00152     return;
00153 
00154   db->header.size = htonl(db->header.size);
00155   db->header.protocol = htons(db->header.protocol);
00156 #ifdef DEBUG_MARSHAL
00157   syslog(LOG_INFO, "packed database: (%u,%u)", db->header.protocol,
00158          db->header.size);
00159 #endif
00160 
00161   /* node and next_hop already in network byte order */
00162   for (i = 0; i < size; i++) {
00163 #ifdef DEBUG_MARSHAL
00164     char string[MESH_LINK_STRLEN];
00165 #endif
00166 
00167     db->links[i].rediscover = htons(db->links[i].rediscover);
00168     db->links[i].hop_count = htonl(db->links[i].hop_count);
00169     for (j = 0; j < NUM_LINK_METRICS; j++)
00170       db->links[i].metrics[j] = htonl(db->links[i].metrics[j]);
00171 
00172 #ifdef DEBUG_MARSHAL
00173     link_to_string(&db->links[i], string);
00174     syslog(LOG_INFO, "    link: %s", string);
00175 #endif
00176   }
00177 }
00178 
00179 void unpack_header(header_t *hdr)
00180 {
00181   if (hdr == NULL)
00182     return;
00183 
00184   hdr->size = ntohl(hdr->size);
00185   hdr->protocol = ntohs(hdr->protocol);
00186 }
00187 
00188 
00189 void unpack_database(database_t *db)
00190 {
00191   unsigned int i, j;
00192 
00193   if (db == NULL)
00194     return;
00195 
00196 #ifdef DEBUG_MARSHAL
00197   syslog(LOG_INFO, "packed database: (%u,%u)", db->header.protocol,
00198          db->header.size);
00199 #endif
00200   unpack_header(&db->header);
00201 #ifdef DEBUG_MARSHAL
00202   syslog(LOG_INFO, "                 [%u,%u]", db->header.protocol,
00203          db->header.size);
00204 #endif
00205 
00206   for (i = 0; i < db->header.size; i++) {
00207 #ifdef DEBUG_MARSHAL
00208     char string[MESH_LINK_STRLEN];
00209     link_to_string(&db->links[i], string);
00210     syslog(LOG_INFO, "    link: %s", string);
00211 #endif
00212     db->links[i].rediscover = ntohs(db->links[i].rediscover);
00213     db->links[i].hop_count = ntohl(db->links[i].hop_count);
00214     for (j = 0; j < NUM_LINK_METRICS; j++)
00215       db->links[i].metrics[j] = ntohl(db->links[i].metrics[j]);
00216   }
00217 }
00218 
00219 
00220 int add_entry(protocol_t *proto, unsigned int id, link_entry_t *entry)
00221 {
00222   if (proto == NULL || entry == NULL) {
00223     errno = EINVAL;
00224     return -1;
00225   }
00226 
00227   entry->node_id = id;
00228   return avl_insert(entry, id, &proto->network);
00229 }
00230 
00231 
00232 int remove_entry(protocol_t *proto, unsigned int id, link_entry_t *entry)
00233 {
00234   if (proto == NULL) {
00235     errno = EINVAL;
00236     return -1;
00237   }
00238   return avl_delete(entry, id, &proto->network);
00239 }
00240 
00241 
00242 link_entry_t *retrieve_entry(protocol_t *proto, unsigned int id)
00243 {
00244   return avl_retrieve(id, &proto->network);
00245 }
00246 
00247 
00248 link_entry_t *iterate_entries(protocol_t *proto)
00249 {
00250   if (proto->iterator == NULL)
00251     proto->iterator = avl_find_min(&proto->network);
00252   else
00253     proto->iterator = proto->iterator->next;
00254 
00255   if (proto->iterator == NULL)
00256     return NULL;
00257 
00258    return (link_entry_t*) proto->iterator->element;
00259 }
00260 
00261 
00262 unsigned int num_entries(protocol_t *proto)
00263 {
00264   return avl_size(&proto->network);
00265 }
00266 
00267 
00268 void empty_entries(protocol_t *proto)
00269 {
00270   link_entry_t *cur = NULL;
00271   proto->iterator = NULL;
00272 
00273   while ((cur = iterate_entries(proto)) != NULL)
00274     free(cur);
00275 
00276   destroy_avltree(proto->network.root);
00277   proto->network.root = NULL;
00278 }
00279 
00280 
00281 
00282 int add_msg(link_entry_t *link, unsigned int seq_num, msg_queue_t *msg)
00283 {
00284   u_int64_t now = get_current_time();
00285 
00286   if (link == NULL || msg == NULL) {
00287     errno = EINVAL;
00288     return -1;
00289   }
00290   msg->id = seq_num;
00291   msg->timeout = now + link->protocol->queue_timeout;
00292   return avl_insert(msg, seq_num, &link->send_queue);
00293 }
00294 
00295 
00296 int remove_msg(link_entry_t *link, unsigned int seq_num, msg_queue_t *msg)
00297 {
00298   if (link == NULL) {
00299     errno = EINVAL;
00300     return -1;
00301   }
00302   return avl_delete(msg, seq_num, &link->send_queue);
00303 }
00304 
00305 
00306 msg_queue_t *retrieve_msg(link_entry_t *link, unsigned int seq_num)
00307 {
00308   return avl_retrieve(seq_num, &link->send_queue);
00309 }
00310 
00311 
00312 void empty_msgs(link_entry_t *link)
00313 {
00314   msg_queue_t *cur = NULL;
00315   struct avlnode *iterator = avl_find_min(&link->send_queue);
00316 
00317   while (iterator != NULL) {
00318     if ((cur = (msg_queue_t*) iterator->element) != NULL)
00319       free(cur);
00320     iterator = iterator->next;
00321   }
00322 
00323   destroy_avltree(link->send_queue.root);
00324   link->send_queue.root = NULL;
00325 }
00326 
00327 
00328 
00329 #ifdef TEST_LINKS
00330 # include "sigsegv.h"
00331 
00332 int main(void)
00333 {
00334   int i, num_links = 5;
00335   database_t *db = malloc(database_size(num_links));
00336   unsigned char db_buf_out[database_marshal_size(num_links)];
00337   unsigned char db_buf_in[database_marshal_size(num_links)];
00338   self_t myself;
00339   link_entry_t *dbentry;
00340   protocol_t *proto = protocol_by_name("signal strength");
00341 
00342   setup_sigsegv();
00343 
00344   memset(db, 0, database_size(num_links));
00345   memset(db_buf_out, 0, database_marshal_size(num_links));
00346   memset(db_buf_in, 0, database_marshal_size(num_links));
00347 
00348   db->header.size = num_links;
00349   db->header.protocol = 3;
00350   fprintf(stderr, "database packing (%d links):\n", num_links);
00351   for (i = 0; i < num_links; i++) {
00352     char string[MESH_LINK_STRLEN], addr[NET_ADDR_LEN];
00353     db->links[i].rediscover = i == 0 ? 1 : 0;
00354     db->links[i].hop_count = i + 2;
00355     db->links[i].metrics[0] = (i + 1) * -1;
00356     db->links[i].metrics[1] = i + 3;
00357     db->links[i].metrics[2] = i + 5;
00358     db->links[i].metrics[3] = i + 7;
00359     sprintf(addr, "128.165.199.%d", i + 1);
00360     inet_aton(addr, &db->links[i].node);
00361     inet_aton("128.165.199.20", &db->links[i].next_hop);
00362     link_to_string(&db->links[i], string);
00363     fprintf(stderr, "    %s\n", string);
00364   }
00365 
00366   pack_database(db_buf_out, db);
00367   memset(db, 0, database_size(num_links));
00368   memcpy(db_buf_in, db_buf_out, database_size(num_links));
00369   unpack_database(db_buf_in, db);
00370 
00371   num_links = db->header.size;
00372   fprintf(stderr, "  unpacked (%u links, protocol %u):\n", num_links,
00373           db->header.protocol);
00374   for (i = 0; i < num_links; i++) {
00375     char string[MESH_LINK_STRLEN];
00376     link_to_string(&db->links[i], string);
00377     fprintf(stderr, "    %s\n", string);
00378   }
00379   fprintf(stderr, "\n");
00380 
00381   init_self(&myself);
00382   fprintf(stderr, "AVL load database: ");
00383   for (i = 0; i < num_links; i++) {
00384     link_entry_t *entry = new_link_entry(&myself, proto);
00385     memcpy(&entry->link, &db->links[i], sizeof(link_t));
00386     entry->node_id = ip_to_id(inet_ntoa(entry->link.node));
00387     add_entry(&myself, entry->node_id, entry, proto);
00388   }
00389   fprintf(stderr, " %u links loaded\n", num_entries(&myself, proto));
00390 
00391   fprintf(stderr, "AVL retrieve links:\n");
00392   while ((dbentry = iterate_entries(&myself, proto)) != NULL) {
00393     char string[MESH_LINK_STRLEN];
00394     link_to_string(&dbentry->link, string);
00395     fprintf(stderr, "   %u %s\n", dbentry->node_id, string);
00396   }
00397 
00398   fprintf(stderr, "Clearing AVL tree: ");
00399   empty_entries(&myself, proto);
00400   fprintf(stderr, "(%u left)\n", num_entries(&myself, proto));
00401 
00402   //TODO: test metrics as well
00403 
00404   return 0;
00405 }
00406 #endif  // TEST_LINKS


© 2007, Los Alamos National Security, LLC.