Contiki 2.6

rudolph2.c

Go to the documentation of this file.
00001 /* XXX todo: add timeout so that hops_from_sink is reset to MAX
00002    after a while. */
00003 
00004 /* XXX todo: use a ctimer to drive peridodic transmission: the current
00005    way does not work if a queuebuf cannot be allocated. */
00006 
00007 /**
00008  * \addtogroup rudolph2
00009  * @{
00010  */
00011 
00012 /*
00013  * Copyright (c) 2007, Swedish Institute of Computer Science.
00014  * All rights reserved.
00015  *
00016  * Redistribution and use in source and binary forms, with or without
00017  * modification, are permitted provided that the following conditions
00018  * are met:
00019  * 1. Redistributions of source code must retain the above copyright
00020  *    notice, this list of conditions and the following disclaimer.
00021  * 2. Redistributions in binary form must reproduce the above copyright
00022  *    notice, this list of conditions and the following disclaimer in the
00023  *    documentation and/or other materials provided with the distribution.
00024  * 3. Neither the name of the Institute nor the names of its contributors
00025  *    may be used to endorse or promote products derived from this software
00026  *    without specific prior written permission.
00027  *
00028  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
00029  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00030  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00031  * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
00032  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00033  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00034  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00035  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00036  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00037  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00038  * SUCH DAMAGE.
00039  *
00040  * This file is part of the Contiki operating system.
00041  *
00042  * $Id: rudolph2.c,v 1.7 2009/03/12 21:58:21 adamdunkels Exp $
00043  */
00044 
00045 /**
00046  * \file
00047  *         Rudolph2: a simple block data flooding protocol
00048  * \author
00049  *         Adam Dunkels <adam@sics.se>
00050  */
00051 
00052 #include <stdio.h>
00053 #include <stddef.h> /* for offsetof */
00054 
00055 #include "net/rime.h"
00056 #include "net/rime/polite.h"
00057 #include "net/rime/rudolph2.h"
00058 #include "cfs/cfs.h"
00059 
00060 #define SEND_INTERVAL CLOCK_SECOND / 2
00061 #define STEADY_INTERVAL CLOCK_SECOND * 16
00062 #define RESEND_INTERVAL SEND_INTERVAL * 4
00063 #define NACK_TIMEOUT CLOCK_SECOND / 4
00064 
00065 struct rudolph2_hdr {
00066   uint8_t type;
00067   uint8_t hops_from_base;
00068   uint16_t version;
00069   uint16_t chunk;
00070 };
00071 
00072 #define POLITE_HEADER 1
00073 
00074 #define HOPS_MAX 64
00075 
00076 enum {
00077   TYPE_DATA,
00078   TYPE_NACK,
00079 };
00080 
00081 #define FLAG_LAST_SENT     0x01
00082 #define FLAG_LAST_RECEIVED 0x02
00083 #define FLAG_IS_STOPPED    0x04
00084 
00085 #define DEBUG 0
00086 #if DEBUG
00087 #include <stdio.h>
00088 #define PRINTF(...) printf(__VA_ARGS__)
00089 #else
00090 #define PRINTF(...)
00091 #endif
00092 
00093 #define LT(a, b) ((signed short)((a) - (b)) < 0)
00094 
00095 /*---------------------------------------------------------------------------*/
00096 static int
00097 read_data(struct rudolph2_conn *c, uint8_t *dataptr, int chunk)
00098 {
00099   int len = 0;
00100 
00101   if(c->cb->read_chunk) {
00102     len = c->cb->read_chunk(c, chunk * RUDOLPH2_DATASIZE,
00103                             dataptr, RUDOLPH2_DATASIZE);
00104   }
00105   return len;
00106 }
00107 /*---------------------------------------------------------------------------*/
00108 static int
00109 format_data(struct rudolph2_conn *c, int chunk)
00110 {
00111   struct rudolph2_hdr *hdr;
00112   int len;
00113   
00114   packetbuf_clear();
00115   hdr = packetbuf_dataptr();
00116   hdr->type = TYPE_DATA;
00117   hdr->hops_from_base = c->hops_from_base;
00118   hdr->version = c->version;
00119   hdr->chunk = chunk;
00120   len = read_data(c, (uint8_t *)hdr + sizeof(struct rudolph2_hdr), chunk);
00121   packetbuf_set_datalen(sizeof(struct rudolph2_hdr) + len);
00122 
00123   return len;
00124 }
00125 /*---------------------------------------------------------------------------*/
00126 static void
00127 write_data(struct rudolph2_conn *c, int chunk, uint8_t *data, int datalen)
00128 {
00129   /* xxx Don't write any data if the application has been stopped. */
00130   if(c->flags & FLAG_IS_STOPPED) {
00131     return;
00132   }
00133   
00134   if(chunk == 0) {
00135     c->cb->write_chunk(c, 0, RUDOLPH2_FLAG_NEWFILE, data, 0);
00136   }
00137   
00138   PRINTF("%d.%d: get %d bytes\n",
00139          rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00140          datalen);
00141 
00142   
00143   if(datalen < RUDOLPH2_DATASIZE) {
00144     PRINTF("%d.%d: get %d bytes, file complete\n",
00145            rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00146            datalen);
00147     c->cb->write_chunk(c, chunk * RUDOLPH2_DATASIZE,
00148                        RUDOLPH2_FLAG_LASTCHUNK, data, datalen);
00149   } else {
00150     c->cb->write_chunk(c, chunk * RUDOLPH2_DATASIZE,
00151                        RUDOLPH2_FLAG_NONE, data, datalen);
00152   }
00153 }
00154 /*---------------------------------------------------------------------------*/
00155 static int
00156 send_data(struct rudolph2_conn *c, clock_time_t interval)
00157 {
00158   int len;
00159 
00160   len = format_data(c, c->snd_nxt);
00161   polite_send(&c->c, interval, POLITE_HEADER);
00162   PRINTF("%d.%d: send_data chunk %d, rcv_nxt %d\n",
00163          rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00164          c->snd_nxt, c->rcv_nxt);
00165 
00166   return len;
00167 }
00168 /*---------------------------------------------------------------------------*/
00169 static void
00170 send_nack(struct rudolph2_conn *c)
00171 {
00172   struct rudolph2_hdr *hdr;
00173   packetbuf_clear();
00174   packetbuf_hdralloc(sizeof(struct rudolph2_hdr));
00175   hdr = packetbuf_hdrptr();
00176 
00177   hdr->hops_from_base = c->hops_from_base;
00178   hdr->type = TYPE_NACK;
00179   hdr->version = c->version;
00180   hdr->chunk = c->rcv_nxt;
00181 
00182   PRINTF("%d.%d: Sending nack for %d\n",
00183          rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00184          hdr->chunk);
00185   polite_send(&c->c, NACK_TIMEOUT, POLITE_HEADER);
00186 }
00187 /*---------------------------------------------------------------------------*/
00188 #if 0 /* Function below not currently used in the code */
00189 static void
00190 send_next(struct rudolph2_conn *c)
00191 {
00192   int len;
00193   clock_time_t interval;
00194 
00195   if(c->flags & FLAG_LAST_SENT) {
00196     interval = STEADY_INTERVAL;
00197   } else {
00198     interval = SEND_INTERVAL;
00199   }
00200   
00201   len = send_data(c, interval);
00202 
00203   if(len < RUDOLPH2_DATASIZE) {
00204     c->flags |= FLAG_LAST_SENT;
00205   } else {
00206     c->flags &= ~FLAG_LAST_SENT;
00207   }
00208   
00209   if(c->nacks == 0 &&
00210      len == RUDOLPH2_DATASIZE &&
00211      c->snd_nxt + 1 < c->rcv_nxt) {
00212     c->snd_nxt++;
00213   }
00214   c->nacks = 0;
00215 }
00216 #endif /* 0 */
00217 /*---------------------------------------------------------------------------*/
00218 static void
00219 sent(struct polite_conn *polite)
00220 {
00221   /*  struct rudolph2_conn *c = (struct rudolph2_conn *)polite;
00222 
00223   if((c->flags & FLAG_IS_STOPPED) == 0 &&
00224      (c->flags & FLAG_LAST_RECEIVED)) {
00225     if(c->snd_nxt < c->rcv_nxt) {
00226       send_next(c);
00227     } else {
00228       send_data(c, STEADY_INTERVAL);
00229     }
00230     }*/
00231   
00232 }
00233 /*---------------------------------------------------------------------------*/
00234 static void
00235 dropped(struct polite_conn *polite)
00236 {
00237   /*  struct rudolph2_conn *c = (struct rudolph2_conn *)polite;
00238   if((c->flags & FLAG_IS_STOPPED) == 0 &&
00239      (c->flags & FLAG_LAST_RECEIVED)) {
00240     if(c->snd_nxt + 1 < c->rcv_nxt) {
00241       send_data(c, SEND_INTERVAL);
00242     } else {
00243       send_data(c, STEADY_INTERVAL);
00244     }
00245     }*/
00246 }
00247 /*---------------------------------------------------------------------------*/
00248 static void
00249 timed_send(void *ptr)
00250 {
00251   struct rudolph2_conn *c = (struct rudolph2_conn *)ptr;
00252   clock_time_t interval;
00253   int len;
00254   
00255   if((c->flags & FLAG_IS_STOPPED) == 0 &&
00256      (c->flags & FLAG_LAST_RECEIVED)) {
00257     /*    if(c->snd_nxt + 1 < c->rcv_nxt) {
00258       interval = SEND_INTERVAL;
00259     } else {
00260       interval = STEADY_INTERVAL;
00261       }*/
00262     /*    send_data(c, interval);*/
00263 
00264     if(c->flags & FLAG_LAST_SENT) {
00265       interval = STEADY_INTERVAL;
00266     } else {
00267       interval = SEND_INTERVAL;
00268     }
00269   
00270 
00271     len = send_data(c, interval);
00272     
00273     if(len < RUDOLPH2_DATASIZE) {
00274       c->flags |= FLAG_LAST_SENT;
00275     } else {
00276       c->flags &= ~FLAG_LAST_SENT;
00277     }
00278     
00279     if(c->nacks == 0 &&
00280        len == RUDOLPH2_DATASIZE &&
00281      c->snd_nxt + 1 < c->rcv_nxt) {
00282       c->snd_nxt++;
00283     }
00284     c->nacks = 0;
00285     ctimer_set(&c->t, interval, timed_send, c);
00286   }
00287 }
00288 /*---------------------------------------------------------------------------*/
00289 static void
00290 recv(struct polite_conn *polite)
00291 {
00292   struct rudolph2_conn *c = (struct rudolph2_conn *)polite;
00293   struct rudolph2_hdr *hdr = packetbuf_dataptr();
00294 
00295   /* Only accept NACKs from nodes that are farther away from the base
00296      than us. */
00297 
00298   if(hdr->type == TYPE_NACK && hdr->hops_from_base > c->hops_from_base) {
00299     c->nacks++;
00300     PRINTF("%d.%d: Got NACK for %d:%d (%d:%d)\n",
00301            rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00302            hdr->version, hdr->chunk,
00303            c->version, c->rcv_nxt);
00304     if(hdr->version == c->version) {
00305       if(hdr->chunk < c->rcv_nxt) {
00306         c->snd_nxt = hdr->chunk;
00307         send_data(c, SEND_INTERVAL);
00308       }
00309     } else if(LT(hdr->version, c->version)) {
00310       c->snd_nxt = 0;
00311       send_data(c, SEND_INTERVAL);
00312     }
00313   } else if(hdr->type == TYPE_DATA) {
00314     if(hdr->hops_from_base < c->hops_from_base) {
00315       /* Only accept data from nodes that are closer to the base than
00316          us. */
00317       c->hops_from_base = hdr->hops_from_base + 1;
00318       if(LT(c->version, hdr->version)) {
00319         PRINTF("%d.%d: rudolph2 new version %d, chunk %d\n",
00320                rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00321                hdr->version, hdr->chunk);
00322         c->version = hdr->version;
00323         c->snd_nxt = c->rcv_nxt = 0;
00324         c->flags &= ~FLAG_LAST_RECEIVED;
00325         c->flags &= ~FLAG_LAST_SENT;
00326         if(hdr->chunk != 0) {
00327           send_nack(c);
00328         } else {
00329           packetbuf_hdrreduce(sizeof(struct rudolph2_hdr));
00330           write_data(c, 0, packetbuf_dataptr(), packetbuf_totlen());
00331         }
00332       } else if(hdr->version == c->version) {
00333         PRINTF("%d.%d: got chunk %d snd_nxt %d rcv_nxt %d\n",
00334                rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00335                hdr->chunk, c->snd_nxt, c->rcv_nxt);
00336         
00337         if(hdr->chunk == c->rcv_nxt) {
00338           int len;
00339           packetbuf_hdrreduce(sizeof(struct rudolph2_hdr));
00340           PRINTF("%d.%d: received chunk %d len %d\n",
00341                  rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00342                  hdr->chunk, packetbuf_totlen());
00343           len = packetbuf_totlen();
00344           write_data(c, hdr->chunk, packetbuf_dataptr(), packetbuf_totlen());
00345           c->rcv_nxt++;
00346           if(len < RUDOLPH2_DATASIZE) {
00347             c->flags |= FLAG_LAST_RECEIVED;
00348             send_data(c, RESEND_INTERVAL);
00349             ctimer_set(&c->t, RESEND_INTERVAL, timed_send, c);
00350           }
00351         } else if(hdr->chunk > c->rcv_nxt) {
00352           PRINTF("%d.%d: received chunk %d > %d, sending NACK\n",
00353                  rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00354                  hdr->chunk, c->rcv_nxt);
00355           send_nack(c);
00356         } else if(hdr->chunk < c->rcv_nxt) {
00357           /* Ignore packets with a lower chunk number */
00358         }
00359       }
00360     }
00361   }
00362 }
00363 /*---------------------------------------------------------------------------*/
00364 static const struct polite_callbacks polite = { recv, sent, dropped };
00365 /*---------------------------------------------------------------------------*/
00366 void
00367 rudolph2_open(struct rudolph2_conn *c, uint16_t channel,
00368               const struct rudolph2_callbacks *cb)
00369 {
00370   polite_open(&c->c, channel, &polite);
00371   c->cb = cb;
00372   c->version = 0;
00373   c->hops_from_base = HOPS_MAX;
00374 }
00375 /*---------------------------------------------------------------------------*/
00376 void
00377 rudolph2_close(struct rudolph2_conn *c)
00378 {
00379   polite_close(&c->c);
00380 }
00381 /*---------------------------------------------------------------------------*/
00382 void
00383 rudolph2_send(struct rudolph2_conn *c, clock_time_t send_interval)
00384 {
00385   int len;
00386 
00387   c->hops_from_base = 0;
00388   c->version++;
00389   c->snd_nxt = 0;
00390   len = RUDOLPH2_DATASIZE;
00391   packetbuf_clear();
00392   for(c->rcv_nxt = 0; len == RUDOLPH2_DATASIZE; c->rcv_nxt++) {
00393     len = read_data(c, packetbuf_dataptr(), c->rcv_nxt);
00394   }
00395   c->flags = FLAG_LAST_RECEIVED;
00396   /*  printf("Highest chunk %d\n", c->rcv_nxt);*/
00397   send_data(c, SEND_INTERVAL);
00398   ctimer_set(&c->t, SEND_INTERVAL, timed_send, c);
00399 }
00400 /*---------------------------------------------------------------------------*/
00401 void
00402 rudolph2_stop(struct rudolph2_conn *c)
00403 {
00404   polite_cancel(&c->c);
00405   c->flags |= FLAG_IS_STOPPED;
00406 }
00407 /*---------------------------------------------------------------------------*/
00408 /** @} */