Contiki 2.6

collect.c

Go to the documentation of this file.
00001 /**
00002  * \addtogroup rimecollect
00003  * @{
00004  */
00005 
00006 /*
00007  * Copyright (c) 2006, 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  */
00037 
00038 /**
00039  * \file
00040  *         Tree-based hop-by-hop reliable data collection
00041  * \author
00042  *         Adam Dunkels <adam@sics.se>
00043  */
00044 
00045 #include "contiki.h"
00046 #include "net/netstack.h"
00047 #include "net/rime.h"
00048 #include "net/rime/collect.h"
00049 #include "net/rime/collect-neighbor.h"
00050 #include "net/rime/collect-link-estimate.h"
00051 
00052 #include "net/packetqueue.h"
00053 
00054 #include "dev/radio-sensor.h"
00055 
00056 #include "lib/random.h"
00057 
00058 #include <string.h>
00059 #include <stdio.h>
00060 #include <stddef.h>
00061 
00062 static const struct packetbuf_attrlist attributes[] =
00063   {
00064     COLLECT_ATTRIBUTES
00065     PACKETBUF_ATTR_LAST
00066   };
00067 
00068 
00069 /* The recent_packets list holds the sequence number, the originator,
00070    and the connection for packets that have been recently
00071    forwarded. This list is maintained to avoid forwarding duplicate
00072    packets. */
00073 #define NUM_RECENT_PACKETS 16
00074 
00075 struct recent_packet {
00076   struct collect_conn *conn;
00077   rimeaddr_t originator;
00078   uint8_t eseqno;
00079 };
00080 
00081 static struct recent_packet recent_packets[NUM_RECENT_PACKETS];
00082 static uint8_t recent_packet_ptr;
00083 
00084 
00085 /* This is the header of data packets. The header comtains the routing
00086    metric of the last hop sender. This is used to avoid routing loops:
00087    if a node receives a packet with a lower routing metric than its
00088    own, it drops the packet. */
00089 struct data_msg_hdr {
00090   uint8_t flags, dummy;
00091   uint16_t rtmetric;
00092 };
00093 
00094 
00095 /* This is the header of ACK packets. It contains a flags field that
00096    indicates if the node is congested (ACK_FLAGS_CONGESTED), if the
00097    packet was dropped (ACK_FLAGS_DROPPED), if a packet was dropped due
00098    to its lifetime was exceeded (ACK_FLAGS_LIFETIME_EXCEEDED), and if
00099    an outdated rtmetric was detected
00100    (ACK_FLAGS_RTMETRIC_NEEDS_UPDATE). The flags can contain any
00101    combination of the flags. The ACK header also contains the routing
00102    metric of the node that sends tha ACK. This is used to keep an
00103    up-to-date routing state in the network. */
00104 struct ack_msg {
00105   uint8_t flags, dummy;
00106   uint16_t rtmetric;
00107 };
00108 
00109 #define ACK_FLAGS_CONGESTED             0x80
00110 #define ACK_FLAGS_DROPPED               0x40
00111 #define ACK_FLAGS_LIFETIME_EXCEEDED     0x20
00112 #define ACK_FLAGS_RTMETRIC_NEEDS_UPDATE 0x10
00113 
00114 
00115 /* These are configuration knobs that normally should not be
00116    tweaked. MAX_MAC_REXMITS defines how many times the underlying CSMA
00117    MAC layer should attempt to resend a data packet before giving
00118    up. The MAX_ACK_MAC_REXMITS defines how many times the MAC layer
00119    should resend ACK packets. The REXMIT_TIME is the lowest
00120    retransmission timeout at the network layer. It is exponentially
00121    increased for every new network layer retransmission. The
00122    FORWARD_PACKET_LIFETIME is the maximum time a packet is held in the
00123    forwarding queue before it is removed. The MAX_SENDING_QUEUE
00124    specifies the maximum length of the output queue. If the queue is
00125    full, incoming packets are dropped instead of being forwarded. */
00126 #define MAX_MAC_REXMITS            2
00127 #define MAX_ACK_MAC_REXMITS        5
00128 #define REXMIT_TIME                (CLOCK_SECOND * 32 / NETSTACK_RDC_CHANNEL_CHECK_RATE)
00129 #define FORWARD_PACKET_LIFETIME_BASE    REXMIT_TIME * 2
00130 #define MAX_SENDING_QUEUE          3 * QUEUEBUF_NUM / 4
00131 #define MIN_AVAILABLE_QUEUE_ENTRIES 4
00132 #define KEEPALIVE_REXMITS          8
00133 #define MAX_REXMITS                31
00134 
00135 MEMB(send_queue_memb, struct packetqueue_item, MAX_SENDING_QUEUE);
00136 
00137 /* These specifiy the sink's routing metric (0) and the maximum
00138    routing metric. If a node has routing metric zero, it is the
00139    sink. If a node has the maximum routing metric, it has no route to
00140    a sink. */
00141 #define RTMETRIC_SINK              0
00142 #define RTMETRIC_MAX               COLLECT_MAX_DEPTH
00143 
00144 /* Here we define what we mean with a significantly improved
00145    rtmetric. This is used to determine when a new parent should be
00146    chosen over an old parent and when to begin more rapidly advertise
00147    a new rtmetric. */
00148 #define SIGNIFICANT_RTMETRIC_PARENT_CHANGE (COLLECT_LINK_ESTIMATE_UNIT +  \
00149                                             COLLECT_LINK_ESTIMATE_UNIT / 2)
00150 
00151 /* This defines the maximum hops that a packet can take before it is
00152    dropped. */
00153 #define MAX_HOPLIM                 15
00154 
00155 
00156 /* Proactive probing: when there are no packets in the send
00157    queue, the system periodically sends a dummy packet to potential
00158    parents, i.e., neighbors with a lower rtmetric than we have but for
00159    which we do not yet have a link quality estimate. */
00160 #define PROACTIVE_PROBING_INTERVAL (random_rand() % CLOCK_SECOND * 60)
00161 #define PROACTIVE_PROBING_REXMITS  15
00162 
00163 /* The ANNOUNCEMENT_SCAN_TIME defines for how long the Collect
00164    implementation should listen for announcements from other nodes
00165    when it requires a route. */
00166 #ifdef ANNOUNCEMENT_CONF_PERIOD
00167 #define ANNOUNCEMENT_SCAN_TIME ANNOUNCEMENT_CONF_PERIOD
00168 #else /* ANNOUNCEMENT_CONF_PERIOD */
00169 #define ANNOUNCEMENT_SCAN_TIME CLOCK_SECOND
00170 #endif /* ANNOUNCEMENT_CONF_PERIOD */
00171 
00172 
00173 /* Statistics structure */
00174 struct {
00175   uint32_t foundroute;
00176   uint32_t newparent;
00177   uint32_t routelost;
00178 
00179   uint32_t acksent;
00180   uint32_t datasent;
00181 
00182   uint32_t datarecv;
00183   uint32_t ackrecv;
00184   uint32_t badack;
00185   uint32_t duprecv;
00186 
00187   uint32_t qdrop;
00188   uint32_t rtdrop;
00189   uint32_t ttldrop;
00190   uint32_t ackdrop;
00191   uint32_t timedout;
00192 } stats;
00193 
00194 /* Debug definition: draw routing tree in Cooja. */
00195 #define DRAW_TREE 0
00196 #define DEBUG 0
00197 #if DEBUG
00198 #include <stdio.h>
00199 #define PRINTF(...) printf(__VA_ARGS__)
00200 #else
00201 #define PRINTF(...)
00202 #endif
00203 
00204 /* Forward declarations. */
00205 static void send_queued_packet(struct collect_conn *c);
00206 static void retransmit_callback(void *ptr);
00207 static void retransmit_not_sent_callback(void *ptr);
00208 static void set_keepalive_timer(struct collect_conn *c);
00209 
00210 /*---------------------------------------------------------------------------*/
00211 /**
00212  * This function computes the current rtmetric by adding the last
00213  * known rtmetric from our parent with the link estimate to the
00214  * parent.
00215  *
00216  */
00217 static uint16_t
00218 rtmetric_compute(struct collect_conn *tc)
00219 {
00220   struct collect_neighbor *n;
00221   uint16_t rtmetric = RTMETRIC_MAX;
00222 
00223   /* This function computes the current rtmetric for this node. It
00224      uses the rtmetric of the parent node in the tree and adds the
00225      current link estimate from us to the parent node. */
00226 
00227   /* The collect connection structure stores the address of its
00228      current parent. We look up the neighbor identification struct in
00229      the collect-neighbor list. */
00230   n = collect_neighbor_list_find(&tc->neighbor_list, &tc->parent);
00231 
00232   /* If n is NULL, we have no best neighbor. Thus our rtmetric is
00233      then COLLECT_RTMETRIC_MAX. */
00234   if(n == NULL) {
00235     rtmetric = RTMETRIC_MAX;
00236   } else {
00237     /* Our rtmetric is the rtmetric of our parent neighbor plus
00238        the expected transmissions to reach that neighbor. */
00239     rtmetric = collect_neighbor_rtmetric_link_estimate(n);
00240   }
00241 
00242   return rtmetric;
00243 }
00244 /*---------------------------------------------------------------------------*/
00245 /**
00246  * This function is called when the route advertisements need to be
00247  * transmitted more rapidly.
00248  *
00249  */
00250 static void
00251 bump_advertisement(struct collect_conn *c)
00252 {
00253 #if !COLLECT_ANNOUNCEMENTS
00254   neighbor_discovery_start(&c->neighbor_discovery_conn, c->rtmetric);
00255 #else
00256   announcement_bump(&c->announcement);
00257 #endif /* !COLLECT_ANNOUNCEMENTS */
00258 }
00259 /*---------------------------------------------------------------------------*/
00260 /**
00261  * This function is called to update the current parent node. The
00262  * parent may change if new routing information has been found, for
00263  * example if a new node with a lower rtmetric and link estimate has
00264  * appeared.
00265  *
00266  */
00267 static void
00268 update_parent(struct collect_conn *tc)
00269 {
00270   struct collect_neighbor *current;
00271   struct collect_neighbor *best;
00272 
00273   /* We grab the collect_neighbor struct of our current parent. */
00274   current = collect_neighbor_list_find(&tc->neighbor_list, &tc->parent);
00275 
00276   /* We call the collect_neighbor module to find the current best
00277      parent. */
00278   best = collect_neighbor_list_best(&tc->neighbor_list);
00279 
00280   /* We check if we need to switch parent. Switching parent is done in
00281      the following situations:
00282 
00283      * We do not have a current parent.
00284      * The best parent is significantly better than the current parent.
00285 
00286      If we do not have a current parent, and have found a best parent,
00287      we simply use the new best parent.
00288 
00289      If we already have a current parent, but have found a new parent
00290      that is better, we employ a heuristic to avoid switching parents
00291      too often. The new parent must be significantly better than the
00292      current parent. Being "significantly better" is defined as having
00293      an rtmetric that is has a difference of at least 1.5 times the
00294      COLLECT_LINK_ESTIMATE_UNIT. This is derived from the experience
00295      by Gnawali et al (SenSys 2009). */
00296 
00297   if(best != NULL) {
00298     rimeaddr_t previous_parent;
00299 
00300     if(DRAW_TREE) {
00301       rimeaddr_copy(&previous_parent, &tc->parent);
00302     }
00303 
00304     if(current == NULL) {
00305       /* New parent. */
00306       PRINTF("update_parent: new parent %d.%d\n",
00307              best->addr.u8[0], best->addr.u8[1]);
00308       rimeaddr_copy(&tc->parent, &best->addr);
00309       stats.foundroute++;
00310       bump_advertisement(tc);
00311     } else {
00312       if(DRAW_TREE) {
00313         printf("#A e=%d\n", collect_neighbor_link_estimate(best));
00314       }
00315       if(collect_neighbor_rtmetric_link_estimate(best) +
00316          SIGNIFICANT_RTMETRIC_PARENT_CHANGE <
00317          collect_neighbor_rtmetric_link_estimate(current)) {
00318 
00319         /* We switch parent. */
00320         PRINTF("update_parent: new parent %d.%d (%d) old parent %d.%d (%d)\n",
00321                best->addr.u8[0], best->addr.u8[1],
00322                collect_neighbor_rtmetric(best),
00323                tc->parent.u8[0], tc->parent.u8[1],
00324                collect_neighbor_rtmetric(current));
00325         rimeaddr_copy(&tc->parent, &best->addr);
00326         stats.newparent++;
00327         /* Since we now have a significantly better or worse rtmetric than
00328            we had before, we let our neighbors know this quickly. */
00329         bump_advertisement(tc);
00330 
00331         if(DRAW_TREE) {
00332           printf("#A e=%d\n", collect_neighbor_link_estimate(best));
00333           /*          {
00334             int i;
00335             int etx = 0;
00336             printf("#A l=");
00337             for(i = 0; i < 8; i++) {
00338               printf("%d ", best->le.history[(best->le.historyptr - 1 - i) & 7]);
00339               etx += current->le.history[i];
00340             }
00341             printf("\n");
00342             }*/
00343         }
00344       } else {
00345         if(DRAW_TREE) {
00346           printf("#A e=%d\n", collect_neighbor_link_estimate(current));
00347           /*          {
00348             int i;
00349             int etx = 0;
00350             printf("#A l=");
00351             for(i = 0; i < 8; i++) {
00352               printf("%d ", current->le.history[(current->le.historyptr - 1 - i) & 7]);
00353               etx += current->le.history[i];
00354             }
00355             printf("\n");
00356             }*/
00357         }
00358       }
00359     }
00360     if(DRAW_TREE) {
00361       if(!rimeaddr_cmp(&previous_parent, &tc->parent)) {
00362         if(!rimeaddr_cmp(&previous_parent, &rimeaddr_null)) {
00363           printf("#L %d 0\n", previous_parent.u8[0]);
00364         }
00365         printf("#L %d 1\n", tc->parent.u8[0]);
00366       }
00367     }
00368   } else {
00369     /* No parent. */
00370     if(!rimeaddr_cmp(&tc->parent, &rimeaddr_null)) {
00371       if(DRAW_TREE) {
00372         printf("#L %d 0\n", tc->parent.u8[0]);
00373       }
00374       stats.routelost++;
00375     }
00376     rimeaddr_copy(&tc->parent, &rimeaddr_null);
00377   }
00378 }
00379 /*---------------------------------------------------------------------------*/
00380 /**
00381  * This function is called whenever there is a chance that the routing
00382  * metric has changed. The function goes through the list of neighbors
00383  * to compute the new routing metric. If the metric has changed, it
00384  * notifies neighbors.
00385  *
00386  *
00387  */
00388 static void
00389 update_rtmetric(struct collect_conn *tc)
00390 {
00391   PRINTF("update_rtmetric: tc->rtmetric %d\n", tc->rtmetric);
00392 
00393   /* We should only update the rtmetric if we are not the sink. */
00394   if(tc->rtmetric != RTMETRIC_SINK) {
00395     uint16_t old_rtmetric, new_rtmetric;
00396 
00397     /* We remember the current (old) rtmetric for later. */
00398     old_rtmetric = tc->rtmetric;
00399 
00400     /* We may need to update our parent node so we do that now. */
00401     update_parent(tc);
00402 
00403     /* We compute the new rtmetric. */
00404     new_rtmetric = rtmetric_compute(tc);
00405 
00406     /* We sanity check our new rtmetric. */
00407     if(new_rtmetric == RTMETRIC_SINK) {
00408       /* Defensive programming: if the new rtmetric somehow got to be
00409          the rtmetric of the sink, there is a bug somewhere. To avoid
00410          destroying the network, we simply will not assume this new
00411          rtmetric. Instead, we set our rtmetric to maximum, to
00412          indicate that we have no sane route. */
00413       new_rtmetric = RTMETRIC_MAX;
00414     }
00415 
00416     /* We set our new rtmetric in the collect conn structure. Then we
00417        decide how we should announce this new rtmetric. */
00418     tc->rtmetric = new_rtmetric;
00419 
00420     if(tc->is_router) {
00421       /* If we are a router, we update our advertised rtmetric. */
00422 #if COLLECT_ANNOUNCEMENTS
00423       announcement_set_value(&tc->announcement, tc->rtmetric);
00424 #else /* COLLECT_ANNOUNCEMENTS */
00425       neighbor_discovery_set_val(&tc->neighbor_discovery_conn, tc->rtmetric);
00426 #endif /* COLLECT_ANNOUNCEMENTS */
00427 
00428     }
00429     PRINTF("%d.%d: new rtmetric %d\n",
00430            rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00431            tc->rtmetric);
00432     
00433     /* We got a new, working, route we send any queued packets we may have. */
00434     if(old_rtmetric == RTMETRIC_MAX && new_rtmetric != RTMETRIC_MAX) {
00435       PRINTF("Sending queued packet because rtmetric was max\n");
00436       send_queued_packet(tc);
00437     }
00438     if(DRAW_TREE) {
00439       if(old_rtmetric != new_rtmetric) {
00440         printf("#A rt=%d,p=%d\n", tc->rtmetric, tc->parent.u8[0]);
00441       }
00442     }
00443   }
00444 }
00445 /*---------------------------------------------------------------------------*/
00446 static int
00447 enqueue_dummy_packet(struct collect_conn *c, int rexmits)
00448 {
00449   struct collect_neighbor *n;
00450   
00451   packetbuf_clear();
00452   packetbuf_set_attr(PACKETBUF_ATTR_EPACKET_ID, c->eseqno - 1);
00453   packetbuf_set_addr(PACKETBUF_ADDR_ESENDER, &rimeaddr_node_addr);
00454   packetbuf_set_attr(PACKETBUF_ATTR_HOPS, 1);
00455   packetbuf_set_attr(PACKETBUF_ATTR_TTL, 1);
00456   packetbuf_set_attr(PACKETBUF_ATTR_MAX_REXMIT, rexmits);
00457 
00458   PRINTF("%d.%d: enqueueing dummy packet %d, max_rexmits %d\n",
00459          rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00460          packetbuf_attr(PACKETBUF_ATTR_EPACKET_ID),
00461          packetbuf_attr(PACKETBUF_ATTR_MAX_REXMIT));
00462 
00463   /* Allocate space for the header. */
00464   packetbuf_hdralloc(sizeof(struct data_msg_hdr));
00465 
00466   n = collect_neighbor_list_find(&c->neighbor_list, &c->parent);
00467   if(n != NULL) {
00468     return packetqueue_enqueue_packetbuf(&c->send_queue,
00469                                          FORWARD_PACKET_LIFETIME_BASE * rexmits,
00470                                          c);
00471   }
00472   return 0;
00473 }
00474 /*---------------------------------------------------------------------------*/
00475 static void
00476 send_packet(struct collect_conn *c, struct collect_neighbor *n)
00477 {
00478   clock_time_t time;
00479 
00480   PRINTF("Sending packet to %d.%d, %d transmissions\n",
00481          n->addr.u8[0], n->addr.u8[1],
00482          c->transmissions);
00483   /* Defensive programming: if a bug in the MAC/RDC layers will cause
00484      it to not call us back, we'll set up the retransmission timer
00485      with a high timeout, so that we can cancel the transmission and
00486      send a new one. */
00487   time = 16 * REXMIT_TIME;
00488   ctimer_set(&c->retransmission_timer, time,
00489              retransmit_not_sent_callback, c);
00490   c->send_time = clock_time();
00491 
00492   unicast_send(&c->unicast_conn, &n->addr);
00493 }
00494 /*---------------------------------------------------------------------------*/
00495 static void
00496 proactive_probing_callback(void *ptr)
00497 {
00498   struct collect_conn *c = ptr;
00499   struct packetqueue_item *i;
00500 
00501   ctimer_set(&c->proactive_probing_timer, PROACTIVE_PROBING_INTERVAL,
00502              proactive_probing_callback, ptr);
00503 
00504   /* Only do proactive link probing if we are not the sink and if we
00505      have a route. */
00506   if(c->rtmetric != RTMETRIC_SINK && c->rtmetric != RTMETRIC_MAX) {
00507   /* Grab the first packet on the send queue to see if the queue is
00508      empty or not. */
00509   i = packetqueue_first(&c->send_queue);
00510   if(i == NULL) {
00511     /* If there are no packets to send, we go through the list of
00512        neighbors to find a potential parent for which we do not have a
00513        link estimate and send a dummy packet to it. This allows us to
00514        quickly gauge the link quality of neighbors that we do not
00515        currently use as parents. */
00516       struct collect_neighbor *n;
00517 
00518       /* Find the neighbor with the lowest number of estimates. */
00519       for(n = list_head(collect_neighbor_list(&c->neighbor_list));
00520           n != NULL; n = list_item_next(n)) {
00521         if(n->rtmetric + COLLECT_LINK_ESTIMATE_UNIT < c->rtmetric &&
00522            collect_link_estimate_num_estimates(&n->le) == 0) {
00523           rimeaddr_t current_parent;
00524 
00525           PRINTF("proactive_probing_callback: found neighbor with no link estimate, %d.%d\n",
00526                  n->addr.u8[RIMEADDR_SIZE - 2], n->addr.u8[RIMEADDR_SIZE - 1]);
00527 
00528           rimeaddr_copy(&current_parent, &c->parent);
00529           rimeaddr_copy(&c->parent, &n->addr);
00530           if(enqueue_dummy_packet(c, PROACTIVE_PROBING_REXMITS)) {
00531             send_queued_packet(c);
00532           }
00533           rimeaddr_copy(&c->parent, &current_parent);
00534           return;
00535         }
00536       }
00537     }
00538     PRINTF("%d.%d: nothing on queue\n",
00539            rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1]);
00540     return;
00541   }
00542 }
00543 /*---------------------------------------------------------------------------*/
00544 /**
00545  * This function is called when a queued packet should be sent
00546  * out. The function takes the first packet on the output queue, adds
00547  * the necessary packet attributes, and sends the packet to the
00548  * next-hop neighbor.
00549  *
00550  */
00551 static void
00552 send_queued_packet(struct collect_conn *c)
00553 {
00554   struct queuebuf *q;
00555   struct collect_neighbor *n;
00556   struct packetqueue_item *i;
00557   struct data_msg_hdr hdr;
00558   int max_mac_rexmits;
00559 
00560   /* If we are currently sending a packet, we do not attempt to send
00561      another one. */
00562   if(c->sending) {
00563     PRINTF("%d.%d: queue, c is sending\n",
00564            rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1]);
00565     return;
00566   }
00567 
00568 
00569   /* Grab the first packet on the send queue. */
00570   i = packetqueue_first(&c->send_queue);
00571   if(i == NULL) {
00572     PRINTF("%d.%d: nothing on queue\n",
00573            rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1]);
00574 
00575     return;
00576   }
00577 
00578   /* We should send the first packet from the queue. */
00579   q = packetqueue_queuebuf(i);
00580   if(q != NULL) {
00581     /* Place the queued packet into the packetbuf. */
00582     queuebuf_to_packetbuf(q);
00583 
00584     /* Pick the neighbor to which to send the packet. We use the
00585        parent in the n->parent. */
00586     n = collect_neighbor_list_find(&c->neighbor_list, &c->parent);
00587 
00588     if(n != NULL) {
00589 
00590       /* If the connection had a neighbor, we construct the packet
00591          buffer attributes and set the appropriate flags in the
00592          Collect connection structure and send the packet. */
00593 
00594       PRINTF("%d.%d: sending packet to %d.%d with eseqno %d\n",
00595              rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00596              n->addr.u8[0], n->addr.u8[1],
00597              packetbuf_attr(PACKETBUF_ATTR_EPACKET_ID));
00598 
00599       /* Mark that we are currently sending a packet. */
00600       c->sending = 1;
00601 
00602       /* Remember the parent that we sent this packet to. */
00603       rimeaddr_copy(&c->current_parent, &c->parent);
00604 
00605       /* This is the first time we transmit this packet, so set
00606          transmissions to zero. */
00607       c->transmissions = 0;
00608 
00609       /* Remember that maximum amount of retransmissions we should
00610          make. This is stored inside a packet attribute in the packet
00611          on the send queue. */
00612       c->max_rexmits = packetbuf_attr(PACKETBUF_ATTR_MAX_REXMIT);
00613 
00614       /* Set the packet attributes: this packet wants an ACK, so we
00615          sent the PACKETBUF_ATTR_RELIABLE flag; the MAC should retry
00616          MAX_MAC_REXMITS times; and the PACKETBUF_ATTR_PACKET_ID is
00617          set to the current sequence number on the connection. */
00618       packetbuf_set_attr(PACKETBUF_ATTR_RELIABLE, 1);
00619 
00620       max_mac_rexmits = c->max_rexmits > MAX_MAC_REXMITS?
00621         MAX_MAC_REXMITS : c->max_rexmits;
00622       packetbuf_set_attr(PACKETBUF_ATTR_MAX_MAC_TRANSMISSIONS, max_mac_rexmits);
00623       packetbuf_set_attr(PACKETBUF_ATTR_PACKET_ID, c->seqno);
00624 
00625       stats.datasent++;
00626 
00627       /* Copy our rtmetric into the packet header of the outgoing
00628          packet. */
00629       memset(&hdr, 0, sizeof(hdr));
00630       hdr.rtmetric = c->rtmetric;
00631       memcpy(packetbuf_dataptr(), &hdr, sizeof(struct data_msg_hdr));
00632 
00633       /* Send the packet. */
00634       send_packet(c, n);
00635 
00636     } else {
00637 #if COLLECT_ANNOUNCEMENTS
00638 #if COLLECT_CONF_WITH_LISTEN
00639       PRINTF("listen\n");
00640       announcement_listen(1);
00641       ctimer_set(&c->transmit_after_scan_timer, ANNOUNCEMENT_SCAN_TIME,
00642                  send_queued_packet, c);
00643 #else /* COLLECT_CONF_WITH_LISTEN */
00644       announcement_set_value(&c->announcement, RTMETRIC_MAX);
00645       announcement_bump(&c->announcement);
00646 #endif /* COLLECT_CONF_WITH_LISTEN */
00647 #endif /* COLLECT_ANNOUNCEMENTS */
00648     }
00649   }
00650 }
00651 /*---------------------------------------------------------------------------*/
00652 /**
00653  * This function is called to retransmit the first packet on the send
00654  * queue.
00655  *
00656  */
00657 static void
00658 retransmit_current_packet(struct collect_conn *c)
00659 {
00660   struct queuebuf *q;
00661   struct collect_neighbor *n;
00662   struct packetqueue_item *i;
00663   struct data_msg_hdr hdr;
00664   int max_mac_rexmits;
00665 
00666   /* Grab the first packet on the send queue, which is the one we are
00667      about to retransmit. */
00668   i = packetqueue_first(&c->send_queue);
00669   if(i == NULL) {
00670       PRINTF("%d.%d: nothing on queue\n",
00671              rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1]);
00672     /* No packet on the queue, so there is nothing for us to send. */
00673     return;
00674   }
00675 
00676   /* Get hold of the queuebuf. */
00677   q = packetqueue_queuebuf(i);
00678   if(q != NULL) {
00679 
00680     update_rtmetric(c);
00681     
00682     /* Place the queued packet into the packetbuf. */
00683     queuebuf_to_packetbuf(q);
00684 
00685     /* Pick the neighbor to which to send the packet. If we have found
00686        a better parent while we were transmitting this packet, we
00687        chose that neighbor instead. If so, we need to attribute the
00688        transmissions we made for the parent to that neighbor. */
00689     if(!rimeaddr_cmp(&c->current_parent, &c->parent)) {
00690       /*      struct collect_neighbor *current_neighbor;
00691       current_neighbor = collect_neighbor_list_find(&c->neighbor_list,
00692                                                     &c->current_parent);
00693       if(current_neighbor != NULL) {
00694         collect_neighbor_tx(current_neighbor, c->max_rexmits);
00695         }*/
00696 
00697       PRINTF("parent change from %d.%d to %d.%d after %d tx\n",
00698              c->current_parent.u8[0], c->current_parent.u8[1],
00699              c->parent.u8[0], c->parent.u8[1],
00700              c->transmissions);
00701 
00702       rimeaddr_copy(&c->current_parent, &c->parent);
00703       c->transmissions = 0;
00704     }
00705     n = collect_neighbor_list_find(&c->neighbor_list, &c->current_parent);
00706 
00707     if(n != NULL) {
00708 
00709       /* If the connection had a neighbor, we construct the packet
00710          buffer attributes and set the appropriate flags in the
00711          Collect connection structure and send the packet. */
00712 
00713       PRINTF("%d.%d: sending packet to %d.%d with eseqno %d\n",
00714              rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00715              n->addr.u8[0], n->addr.u8[1],
00716              packetbuf_attr(PACKETBUF_ATTR_EPACKET_ID));
00717 
00718       /* Mark that we are currently sending a packet. */
00719       c->sending = 1;
00720       packetbuf_set_attr(PACKETBUF_ATTR_RELIABLE, 1);
00721       max_mac_rexmits = c->max_rexmits - c->transmissions > MAX_MAC_REXMITS?
00722         MAX_MAC_REXMITS : c->max_rexmits - c->transmissions;
00723       packetbuf_set_attr(PACKETBUF_ATTR_MAX_MAC_TRANSMISSIONS, max_mac_rexmits);
00724       packetbuf_set_attr(PACKETBUF_ATTR_PACKET_ID, c->seqno);
00725 
00726       /* Copy our rtmetric into the packet header of the outgoing
00727          packet. */
00728       memset(&hdr, 0, sizeof(hdr));
00729       hdr.rtmetric = c->rtmetric;
00730       memcpy(packetbuf_dataptr(), &hdr, sizeof(struct data_msg_hdr));
00731 
00732       /* Send the packet. */
00733       send_packet(c, n);
00734     }
00735   }
00736 
00737 }
00738 /*---------------------------------------------------------------------------*/
00739 static void
00740 send_next_packet(struct collect_conn *tc)
00741 {
00742   /* Remove the first packet on the queue, the packet that was just sent. */
00743   packetqueue_dequeue(&tc->send_queue);
00744   tc->seqno = (tc->seqno + 1) % (1 << COLLECT_PACKET_ID_BITS);
00745 
00746   /* Cancel retransmission timer. */
00747   ctimer_stop(&tc->retransmission_timer);
00748   tc->sending = 0;
00749   tc->transmissions = 0;
00750 
00751   PRINTF("sending next packet, seqno %d, queue len %d\n",
00752          tc->seqno, packetqueue_len(&tc->send_queue));
00753 
00754   /* Send the next packet in the queue, if any. */
00755   send_queued_packet(tc);
00756 }
00757 /*---------------------------------------------------------------------------*/
00758 static void
00759 handle_ack(struct collect_conn *tc)
00760 {
00761   struct ack_msg msg;
00762   struct collect_neighbor *n;
00763 
00764   PRINTF("handle_ack: sender %d.%d current_parent %d.%d, id %d seqno %d\n",
00765          packetbuf_addr(PACKETBUF_ADDR_SENDER)->u8[0],
00766          packetbuf_addr(PACKETBUF_ADDR_SENDER)->u8[1],
00767          tc->current_parent.u8[0], tc->current_parent.u8[1],
00768          packetbuf_attr(PACKETBUF_ATTR_PACKET_ID), tc->seqno);
00769   if(rimeaddr_cmp(packetbuf_addr(PACKETBUF_ADDR_SENDER),
00770                   &tc->current_parent) &&
00771      packetbuf_attr(PACKETBUF_ATTR_PACKET_ID) == tc->seqno) {
00772 
00773     /*    printf("rtt %d / %d = %d.%02d\n",
00774            (int)(clock_time() - tc->send_time),
00775            (int)CLOCK_SECOND,
00776            (int)((clock_time() - tc->send_time) / CLOCK_SECOND),
00777            (int)(((100 * (clock_time() - tc->send_time)) / CLOCK_SECOND) % 100));*/
00778     
00779     stats.ackrecv++;
00780     memcpy(&msg, packetbuf_dataptr(), sizeof(struct ack_msg));
00781 
00782     /* It is possible that we receive an ACK for a packet that we
00783        think we have not yet sent: if our transmission was received by
00784        the other node, but the link-layer ACK was lost, our
00785        transmission counter may still be zero. If this is the case, we
00786        play it safe by believing that we have sent MAX_MAC_REXMITS
00787        transmissions. */
00788     if(tc->transmissions == 0) {
00789       tc->transmissions = MAX_MAC_REXMITS;
00790     }
00791     PRINTF("Updating link estimate with %d transmissions\n",
00792            tc->transmissions);
00793     n = collect_neighbor_list_find(&tc->neighbor_list,
00794                                    packetbuf_addr(PACKETBUF_ADDR_SENDER));
00795 
00796     if(n != NULL) {
00797       collect_neighbor_tx(n, tc->transmissions);
00798       collect_neighbor_update_rtmetric(n, msg.rtmetric);
00799       update_rtmetric(tc);
00800     }
00801 
00802     PRINTF("%d.%d: ACK from %d.%d after %d transmissions, flags %02x, rtmetric %d\n",
00803            rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00804            tc->current_parent.u8[0], tc->current_parent.u8[1],
00805            tc->transmissions,
00806            msg.flags,
00807            msg.rtmetric);
00808 
00809     /* The ack contains information about the state of the packet and
00810        of the node that received it. We do different things depending
00811        on whether or not the packet was dropped. First, we check if
00812        the receiving node was congested. If so, we add a maximum
00813        transmission number to its routing metric, which increases the
00814        chance that another parent will be chosen. */
00815     if(msg.flags & ACK_FLAGS_CONGESTED) {
00816       PRINTF("ACK flag indicated parent was congested.\n");
00817       collect_neighbor_set_congested(n);
00818       collect_neighbor_tx(n, tc->max_rexmits * 2);
00819       update_rtmetric(tc);
00820     }
00821     if((msg.flags & ACK_FLAGS_DROPPED) == 0) {
00822       /* If the packet was successfully received, we send the next packet. */
00823       send_next_packet(tc);
00824     } else {
00825       /* If the packet was lost due to its lifetime being exceeded,
00826          there is not much more we can do with the packet, so we send
00827          the next one instead. */
00828       if((msg.flags & ACK_FLAGS_LIFETIME_EXCEEDED)) {
00829         send_next_packet(tc);
00830       } else {
00831         /* If the packet was dropped, but without the node being
00832            congested or the packets lifetime being exceeded, we
00833            penalize the parent and try sending the packet again. */
00834         PRINTF("ACK flag indicated packet was dropped by parent.\n");
00835         collect_neighbor_tx(n, tc->max_rexmits);
00836         update_rtmetric(tc);
00837 
00838         ctimer_set(&tc->retransmission_timer,
00839                    REXMIT_TIME + (random_rand() % (REXMIT_TIME)),
00840                    retransmit_callback, tc);
00841       }
00842     }
00843 
00844     /* Our neighbor's rtmetric needs to be updated, so we bump our
00845        advertisements. */
00846     if(msg.flags & ACK_FLAGS_RTMETRIC_NEEDS_UPDATE) {
00847       bump_advertisement(tc);
00848     }
00849     set_keepalive_timer(tc);
00850   } else {
00851     stats.badack++;
00852   }
00853 }
00854 /*---------------------------------------------------------------------------*/
00855 static void
00856 send_ack(struct collect_conn *tc, const rimeaddr_t *to, int flags)
00857 {
00858   struct ack_msg *ack;
00859   uint16_t packet_seqno = packetbuf_attr(PACKETBUF_ATTR_PACKET_ID);
00860 
00861   packetbuf_clear();
00862   packetbuf_set_datalen(sizeof(struct ack_msg));
00863   ack = packetbuf_dataptr();
00864   memset(ack, 0, sizeof(struct ack_msg));
00865   ack->rtmetric = tc->rtmetric;
00866   ack->flags = flags;
00867 
00868   packetbuf_set_addr(PACKETBUF_ADDR_RECEIVER, to);
00869   packetbuf_set_attr(PACKETBUF_ATTR_PACKET_TYPE, PACKETBUF_ATTR_PACKET_TYPE_ACK);
00870   packetbuf_set_attr(PACKETBUF_ATTR_RELIABLE, 0);
00871   packetbuf_set_attr(PACKETBUF_ATTR_ERELIABLE, 0);
00872   packetbuf_set_attr(PACKETBUF_ATTR_PACKET_ID, packet_seqno);
00873   packetbuf_set_attr(PACKETBUF_ATTR_MAX_MAC_TRANSMISSIONS, MAX_ACK_MAC_REXMITS);
00874   unicast_send(&tc->unicast_conn, to);
00875 
00876   PRINTF("%d.%d: collect: Sending ACK to %d.%d for %d (epacket_id %d)\n",
00877          rimeaddr_node_addr.u8[0],rimeaddr_node_addr.u8[1],
00878          to->u8[0], to->u8[1], packet_seqno,
00879          packetbuf_attr(PACKETBUF_ATTR_EPACKET_ID));
00880 
00881   RIMESTATS_ADD(acktx);
00882   stats.acksent++;
00883 }
00884 /*---------------------------------------------------------------------------*/
00885 static void
00886 add_packet_to_recent_packets(struct collect_conn *tc)
00887 {
00888   /* Remember that we have seen this packet for later, but only if
00889      it has a length that is larger than zero. Packets with size
00890      zero are keepalive or proactive link estimate probes, so we do
00891      not record them in our history. */
00892   if(packetbuf_datalen() > sizeof(struct data_msg_hdr)) {
00893     recent_packets[recent_packet_ptr].eseqno =
00894       packetbuf_attr(PACKETBUF_ATTR_EPACKET_ID);
00895     rimeaddr_copy(&recent_packets[recent_packet_ptr].originator,
00896                   packetbuf_addr(PACKETBUF_ADDR_ESENDER));
00897     recent_packets[recent_packet_ptr].conn = tc;
00898     recent_packet_ptr = (recent_packet_ptr + 1) % NUM_RECENT_PACKETS;
00899   }
00900 }
00901 /*---------------------------------------------------------------------------*/
00902 static void
00903 node_packet_received(struct unicast_conn *c, const rimeaddr_t *from)
00904 {
00905   struct collect_conn *tc = (struct collect_conn *)
00906     ((char *)c - offsetof(struct collect_conn, unicast_conn));
00907   int i;
00908   struct data_msg_hdr hdr;
00909   uint8_t ackflags = 0;
00910   struct collect_neighbor *n;
00911 
00912   memcpy(&hdr, packetbuf_dataptr(), sizeof(struct data_msg_hdr));
00913 
00914   /* First update the neighbors rtmetric with the information in the
00915      packet header. */
00916   PRINTF("node_packet_received: from %d.%d rtmetric %d\n",
00917          from->u8[0], from->u8[1], hdr.rtmetric);
00918   n = collect_neighbor_list_find(&tc->neighbor_list,
00919                                  packetbuf_addr(PACKETBUF_ADDR_SENDER));
00920   if(n != NULL) {
00921     collect_neighbor_update_rtmetric(n, hdr.rtmetric);
00922     update_rtmetric(tc);
00923   }
00924 
00925   /* To protect against sending duplicate packets, we keep a list of
00926      recently forwarded packet seqnos. If the seqno of the current
00927      packet exists in the list, we immediately send an ACK and drop
00928      the packet. */
00929   if(packetbuf_attr(PACKETBUF_ATTR_PACKET_TYPE) ==
00930      PACKETBUF_ATTR_PACKET_TYPE_DATA) {
00931     rimeaddr_t ack_to;
00932     uint8_t packet_seqno;
00933 
00934     stats.datarecv++;
00935 
00936     /* Remember to whom we should send the ACK, since we reuse the
00937        packet buffer and its attributes when sending the ACK. */
00938     rimeaddr_copy(&ack_to, packetbuf_addr(PACKETBUF_ADDR_SENDER));
00939     packet_seqno = packetbuf_attr(PACKETBUF_ATTR_PACKET_ID);
00940 
00941     /* If the queue is more than half filled, we add the CONGESTED
00942        flag to our outgoing acks. */
00943     if(DRAW_TREE) {
00944       printf("#A s=%d\n", packetqueue_len(&tc->send_queue));
00945     }
00946     if(packetqueue_len(&tc->send_queue) >= MAX_SENDING_QUEUE / 2) {
00947       ackflags |= ACK_FLAGS_CONGESTED;
00948     }
00949 
00950     for(i = 0; i < NUM_RECENT_PACKETS; i++) {
00951       if(recent_packets[i].conn == tc &&
00952          recent_packets[i].eseqno == packetbuf_attr(PACKETBUF_ATTR_EPACKET_ID) &&
00953          rimeaddr_cmp(&recent_packets[i].originator,
00954                       packetbuf_addr(PACKETBUF_ADDR_ESENDER))) {
00955         /* This is a duplicate of a packet we recently received, so we
00956            just send an ACK. */
00957         PRINTF("%d.%d: found duplicate packet from %d.%d with seqno %d, via %d.%d\n",
00958                rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00959                recent_packets[i].originator.u8[0], recent_packets[i].originator.u8[1],
00960                packetbuf_attr(PACKETBUF_ATTR_EPACKET_ID),
00961                packetbuf_addr(PACKETBUF_ADDR_SENDER)->u8[0],
00962                packetbuf_addr(PACKETBUF_ADDR_SENDER)->u8[1]);
00963         send_ack(tc, &ack_to, ackflags);
00964         stats.duprecv++;
00965         return;
00966       }
00967     }
00968 
00969     /* If we are the sink, the packet has reached its final
00970        destination and we call the receive function. */
00971     if(tc->rtmetric == RTMETRIC_SINK) {
00972       struct queuebuf *q;
00973 
00974       add_packet_to_recent_packets(tc);
00975 
00976       /* We first send the ACK. We copy the data packet to a queuebuf
00977          first. */
00978       q = queuebuf_new_from_packetbuf();
00979       if(q != NULL) {
00980         send_ack(tc, &ack_to, 0);
00981         queuebuf_to_packetbuf(q);
00982         queuebuf_free(q);
00983       } else {
00984         PRINTF("%d.%d: collect: could not send ACK to %d.%d for %d: no queued buffers\n",
00985                rimeaddr_node_addr.u8[0],rimeaddr_node_addr.u8[1],
00986                ack_to.u8[0], ack_to.u8[1],
00987                packet_seqno);
00988         stats.ackdrop++;
00989       }
00990 
00991 
00992       PRINTF("%d.%d: sink received packet %d from %d.%d via %d.%d\n",
00993              rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
00994              packetbuf_attr(PACKETBUF_ATTR_EPACKET_ID),
00995              packetbuf_addr(PACKETBUF_ADDR_ESENDER)->u8[0],
00996              packetbuf_addr(PACKETBUF_ADDR_ESENDER)->u8[1],
00997              from->u8[0], from->u8[1]);
00998 
00999       packetbuf_hdrreduce(sizeof(struct data_msg_hdr));
01000       /* Call receive function. */
01001       if(packetbuf_datalen() > 0 && tc->cb->recv != NULL) {
01002         tc->cb->recv(packetbuf_addr(PACKETBUF_ADDR_ESENDER),
01003                      packetbuf_attr(PACKETBUF_ATTR_EPACKET_ID),
01004                      packetbuf_attr(PACKETBUF_ATTR_HOPS));
01005       }
01006       return;
01007     } else if(packetbuf_attr(PACKETBUF_ATTR_TTL) > 1 &&
01008               tc->rtmetric != RTMETRIC_MAX) {
01009       /* If we are not the sink, we forward the packet to our best
01010          neighbor. First, we make sure that the packet comes from a
01011          neighbor that has a higher rtmetric than we have. If not, we
01012          have a loop and we inform the sender that its rtmetric needs
01013          to be updated. Second, we set our rtmetric in the outgoing
01014          packet to let the next hop know what our rtmetric is. Third,
01015          we update the hop count and ttl. */
01016 
01017       if(hdr.rtmetric <= tc->rtmetric) {
01018         ackflags |= ACK_FLAGS_RTMETRIC_NEEDS_UPDATE;
01019       }
01020 
01021       packetbuf_set_attr(PACKETBUF_ATTR_HOPS,
01022                          packetbuf_attr(PACKETBUF_ATTR_HOPS) + 1);
01023       packetbuf_set_attr(PACKETBUF_ATTR_TTL,
01024                          packetbuf_attr(PACKETBUF_ATTR_TTL) - 1);
01025 
01026 
01027       PRINTF("%d.%d: packet received from %d.%d via %d.%d, sending %d, max_rexmits %d\n",
01028              rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
01029              packetbuf_addr(PACKETBUF_ADDR_ESENDER)->u8[0],
01030              packetbuf_addr(PACKETBUF_ADDR_ESENDER)->u8[1],
01031              from->u8[0], from->u8[1], tc->sending,
01032              packetbuf_attr(PACKETBUF_ATTR_MAX_REXMIT));
01033 
01034       /* We try to enqueue the packet on the outgoing packet queue. If
01035          we are able to enqueue the packet, we send a positive ACK. If
01036          we are unable to enqueue the packet, we send a negative ACK
01037          to inform the sender that the packet was dropped due to
01038          memory problems. We first check the size of our sending queue
01039          to ensure that we always have entries for packets that
01040          are originated by this node. */
01041       if(packetqueue_len(&tc->send_queue) <= MAX_SENDING_QUEUE - MIN_AVAILABLE_QUEUE_ENTRIES &&
01042          packetqueue_enqueue_packetbuf(&tc->send_queue,
01043                                        FORWARD_PACKET_LIFETIME_BASE *
01044                                        packetbuf_attr(PACKETBUF_ATTR_MAX_REXMIT),
01045                                        tc)) {
01046         add_packet_to_recent_packets(tc);
01047         send_ack(tc, &ack_to, ackflags);
01048         send_queued_packet(tc);
01049       } else {
01050         send_ack(tc, &ack_to,
01051                  ackflags | ACK_FLAGS_DROPPED | ACK_FLAGS_CONGESTED);
01052         PRINTF("%d.%d: packet dropped: no queue buffer available\n",
01053                   rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1]);
01054         stats.qdrop++;
01055       }
01056     } else if(packetbuf_attr(PACKETBUF_ATTR_TTL) <= 1) {
01057       PRINTF("%d.%d: packet dropped: ttl %d\n",
01058              rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
01059              packetbuf_attr(PACKETBUF_ATTR_TTL));
01060       send_ack(tc, &ack_to, ackflags |
01061                ACK_FLAGS_DROPPED | ACK_FLAGS_LIFETIME_EXCEEDED);
01062       stats.ttldrop++;
01063     }
01064   } else if(packetbuf_attr(PACKETBUF_ATTR_PACKET_TYPE) ==
01065             PACKETBUF_ATTR_PACKET_TYPE_ACK) {
01066     PRINTF("Collect: incoming ack %d from %d.%d (%d.%d) seqno %d (%d)\n",
01067            packetbuf_attr(PACKETBUF_ATTR_PACKET_TYPE),
01068            packetbuf_addr(PACKETBUF_ADDR_SENDER)->u8[0],
01069            packetbuf_addr(PACKETBUF_ADDR_SENDER)->u8[1],
01070            tc->current_parent.u8[0],
01071            tc->current_parent.u8[1],
01072            packetbuf_attr(PACKETBUF_ATTR_PACKET_ID),
01073            tc->seqno);
01074     handle_ack(tc);
01075     stats.ackrecv++;
01076   }
01077   return;
01078 }
01079 /*---------------------------------------------------------------------------*/
01080 static void
01081 timedout(struct collect_conn *tc)
01082 {
01083   struct collect_neighbor *n;
01084   PRINTF("%d.%d: timedout after %d retransmissions to %d.%d (max retransmissions %d): packet dropped\n",
01085          rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1], tc->transmissions,
01086          tc->current_parent.u8[0], tc->current_parent.u8[1],
01087          tc->max_rexmits);
01088   printf("%d.%d: timedout after %d retransmissions to %d.%d (max retransmissions %d): packet dropped\n",
01089          rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1], tc->transmissions,
01090          tc->current_parent.u8[0], tc->current_parent.u8[1],
01091          tc->max_rexmits);
01092 
01093   tc->sending = 0;
01094   n = collect_neighbor_list_find(&tc->neighbor_list,
01095                                  &tc->current_parent);
01096   if(n != NULL) {
01097     collect_neighbor_tx_fail(n, tc->max_rexmits);
01098   }
01099   update_rtmetric(tc);
01100   send_next_packet(tc);
01101   set_keepalive_timer(tc);
01102 }
01103 /*---------------------------------------------------------------------------*/
01104 static void
01105 node_packet_sent(struct unicast_conn *c, int status, int transmissions)
01106 {
01107   struct collect_conn *tc = (struct collect_conn *)
01108     ((char *)c - offsetof(struct collect_conn, unicast_conn));
01109 
01110   /* For data packets, we record the number of transmissions */
01111   if(packetbuf_attr(PACKETBUF_ATTR_PACKET_TYPE) ==
01112      PACKETBUF_ATTR_PACKET_TYPE_DATA) {
01113 
01114     tc->transmissions += transmissions;
01115     PRINTF("tx %d\n", tc->transmissions);    
01116     PRINTF("%d.%d: MAC sent %d transmissions to %d.%d, status %d, total transmissions %d\n",
01117            rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
01118            transmissions,
01119            tc->current_parent.u8[0], tc->current_parent.u8[1],
01120            status, tc->transmissions);
01121     if(tc->transmissions >= tc->max_rexmits) {
01122       timedout(tc);
01123       stats.timedout++;
01124     } else {
01125       clock_time_t time = REXMIT_TIME / 2 + (random_rand() % (REXMIT_TIME / 2));
01126       PRINTF("retransmission time %lu\n", time);
01127       ctimer_set(&tc->retransmission_timer, time,
01128                  retransmit_callback, tc);
01129     }
01130   }
01131 }
01132 /*---------------------------------------------------------------------------*/
01133 /**
01134  * This function is called from a ctimer that is setup when a packet
01135  * is first transmitted. If the MAC layer signals that the packet is
01136  * sent, the ctimer will be stopped before this function is called. If
01137  * this function ends up being called, we add the maximum number of
01138  * MAC layer transmissions to the transmission count, and call the
01139  * retransmit function.
01140  */
01141 static void
01142 retransmit_not_sent_callback(void *ptr)
01143 {
01144   struct collect_conn *c = ptr;
01145 
01146   PRINTF("retransmit not sent, %d transmissions\n", c->transmissions);
01147   c->transmissions += MAX_MAC_REXMITS + 1;
01148   retransmit_callback(c);
01149 }
01150 /*---------------------------------------------------------------------------*/
01151 /**
01152  * This function is called from a ctimer that is setup when a packet
01153  * is sent. The purpose of this function is to either retransmit the
01154  * current packet, or timeout the packet. The descision is made
01155  * depending on how many times the packet has been transmitted. The
01156  * ctimer is set up in the function node_packet_sent().
01157  */
01158 static void
01159 retransmit_callback(void *ptr)
01160 {
01161   struct collect_conn *c = ptr;
01162 
01163   PRINTF("retransmit, %d transmissions\n", c->transmissions);
01164   if(c->transmissions >= c->max_rexmits) {
01165     timedout(c);
01166     stats.timedout++;
01167   } else {
01168     c->sending = 0;
01169     retransmit_current_packet(c);
01170   }
01171 }
01172 /*---------------------------------------------------------------------------*/
01173 #if !COLLECT_ANNOUNCEMENTS
01174 static void
01175 adv_received(struct neighbor_discovery_conn *c, const rimeaddr_t *from,
01176              uint16_t rtmetric)
01177 {
01178   struct collect_conn *tc = (struct collect_conn *)
01179     ((char *)c - offsetof(struct collect_conn, neighbor_discovery_conn));
01180   struct collect_neighbor *n;
01181 
01182   n = collect_neighbor_list_find(&tc->neighbor_list, from);
01183 
01184   if(n == NULL) {
01185     collect_neighbor_list_add(&tc->neighbor_list, from, rtmetric);
01186     if(rtmetric == RTMETRIC_MAX) {
01187       bump_advertisement(tc);
01188     }
01189   } else {
01190     /* Check if the advertised rtmetric has changed to
01191        RTMETRIC_MAX. This may indicate that the neighbor has lost its
01192        routes or that it has rebooted. In either case, we bump our
01193        advertisement rate to allow our neighbor to receive a new
01194        rtmetric from us. If our neighbor already happens to have an
01195        rtmetric of RTMETRIC_MAX recorded, it may mean that our
01196        neighbor does not hear our advertisements. If this is the case,
01197        we should not bump our advertisement rate. */
01198     if(rtmetric == RTMETRIC_MAX &&
01199        collect_neighbor_rtmetric(n) != RTMETRIC_MAX) {
01200       bump_advertisement(tc);
01201     } 
01202     collect_neighbor_update_rtmetric(n, rtmetric);
01203     PRINTF("%d.%d: updating neighbor %d.%d, etx %d\n",
01204            rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
01205            n->addr.u8[0], n->addr.u8[1], rtmetric);
01206   }
01207 
01208   update_rtmetric(tc);
01209 }
01210 #else
01211 static void
01212 received_announcement(struct announcement *a, const rimeaddr_t *from,
01213                       uint16_t id, uint16_t value)
01214 {
01215   struct collect_conn *tc = (struct collect_conn *)
01216     ((char *)a - offsetof(struct collect_conn, announcement));
01217   struct collect_neighbor *n;
01218 
01219   n = collect_neighbor_list_find(&tc->neighbor_list, from);
01220 
01221   if(n == NULL) {
01222     /* Only add neighbors that have an rtmetric that is lower than
01223        ours. */
01224     if(value < tc->rtmetric) {
01225       collect_neighbor_list_add(&tc->neighbor_list, from, value);
01226       PRINTF("%d.%d: new neighbor %d.%d, rtmetric %d\n",
01227              rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
01228              from->u8[0], from->u8[1], value);
01229     }
01230     if(value == RTMETRIC_MAX && tc->rtmetric != RTMETRIC_MAX) {
01231       bump_advertisement(tc);
01232     }
01233   } else {
01234     /* Check if the advertised rtmetric has changed to
01235        RTMETRIC_MAX. This may indicate that the neighbor has lost its
01236        routes or that it has rebooted. In either case, we bump our
01237        advertisement rate to allow our neighbor to receive a new
01238        rtmetric from us. If our neighbor already happens to have an
01239        rtmetric of RTMETRIC_MAX recorded, it may mean that our
01240        neighbor does not hear our advertisements. If this is the case,
01241        we should not bump our advertisement rate. */
01242     if(value == RTMETRIC_MAX &&
01243        collect_neighbor_rtmetric(n) != RTMETRIC_MAX) {
01244       bump_advertisement(tc);
01245     }
01246     collect_neighbor_update_rtmetric(n, value);
01247     PRINTF("%d.%d: updating neighbor %d.%d, etx %d\n",
01248            rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
01249            n->addr.u8[0], n->addr.u8[1], value);
01250   }
01251 
01252   update_rtmetric(tc);
01253 
01254 #if ! COLLECT_CONF_WITH_LISTEN
01255   if(value == RTMETRIC_MAX &&
01256      tc->rtmetric != RTMETRIC_MAX) {
01257     announcement_bump(&tc->announcement);
01258   }
01259 #endif /* COLLECT_CONF_WITH_LISTEN */
01260 }
01261 #endif /* !COLLECT_ANNOUNCEMENTS */
01262 /*---------------------------------------------------------------------------*/
01263 static const struct unicast_callbacks unicast_callbacks = {node_packet_received,
01264                                                            node_packet_sent};
01265 #if !COLLECT_ANNOUNCEMENTS
01266 static const struct neighbor_discovery_callbacks neighbor_discovery_callbacks =
01267   { adv_received, NULL};
01268 #endif /* !COLLECT_ANNOUNCEMENTS */
01269 /*---------------------------------------------------------------------------*/
01270 void
01271 collect_open(struct collect_conn *tc, uint16_t channels,
01272              uint8_t is_router,
01273              const struct collect_callbacks *cb)
01274 {
01275   unicast_open(&tc->unicast_conn, channels + 1, &unicast_callbacks);
01276   channel_set_attributes(channels + 1, attributes);
01277   tc->rtmetric = RTMETRIC_MAX;
01278   tc->cb = cb;
01279   tc->is_router = is_router;
01280   tc->seqno = 10;
01281   tc->eseqno = 0;
01282   LIST_STRUCT_INIT(tc, send_queue_list);
01283   collect_neighbor_list_new(&tc->neighbor_list);
01284   tc->send_queue.list = &(tc->send_queue_list);
01285   tc->send_queue.memb = &send_queue_memb;
01286   collect_neighbor_init();
01287 
01288 #if !COLLECT_ANNOUNCEMENTS
01289   neighbor_discovery_open(&tc->neighbor_discovery_conn, channels,
01290                           CLOCK_SECOND * 4,
01291                           CLOCK_SECOND * 60,
01292 #ifdef COLLECT_CONF_BROADCAST_ANNOUNCEMENT_MAX_TIME
01293               COLLECT_CONF_BROADCAST_ANNOUNCEMENT_MAX_TIME,
01294 #else
01295               CLOCK_SECOND * 600UL,
01296 #endif
01297                           &neighbor_discovery_callbacks);
01298   neighbor_discovery_start(&tc->neighbor_discovery_conn, tc->rtmetric);
01299 #else /* !COLLECT_ANNOUNCEMENTS */
01300   announcement_register(&tc->announcement, channels,
01301                         received_announcement);
01302 #if ! COLLECT_CONF_WITH_LISTEN
01303   announcement_set_value(&tc->announcement, RTMETRIC_MAX);
01304 #endif /* COLLECT_CONF_WITH_LISTEN */
01305 #endif /* !COLLECT_ANNOUNCEMENTS */
01306 
01307   ctimer_set(&tc->proactive_probing_timer, PROACTIVE_PROBING_INTERVAL,
01308              proactive_probing_callback, tc);
01309 
01310 }
01311 /*---------------------------------------------------------------------------*/
01312 static void
01313 send_keepalive(void *ptr)
01314 {
01315   struct collect_conn *c = ptr;
01316 
01317   set_keepalive_timer(c);
01318 
01319   /* Send keepalive message only if there are no pending transmissions. */
01320   if(c->sending == 0 && packetqueue_len(&c->send_queue) == 0) {
01321     if(enqueue_dummy_packet(c, KEEPALIVE_REXMITS)) {
01322       PRINTF("%d.%d: sending keepalive\n",
01323              rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1]);
01324       send_queued_packet(c);
01325     }
01326   }
01327 }
01328 /*---------------------------------------------------------------------------*/
01329 static void
01330 set_keepalive_timer(struct collect_conn *c)
01331 {
01332   if(c->keepalive_period != 0) {
01333     ctimer_set(&c->keepalive_timer, (c->keepalive_period / 2) +
01334                (random_rand() % (c->keepalive_period / 2)),
01335                send_keepalive, c);
01336   } else {
01337     ctimer_stop(&c->keepalive_timer);
01338   }
01339 }
01340 /*---------------------------------------------------------------------------*/
01341 void
01342 collect_set_keepalive(struct collect_conn *c, clock_time_t period)
01343 {
01344   c->keepalive_period = period;
01345   set_keepalive_timer(c);
01346 }
01347 /*---------------------------------------------------------------------------*/
01348 void
01349 collect_close(struct collect_conn *tc)
01350 {
01351 #if COLLECT_ANNOUNCEMENTS
01352   announcement_remove(&tc->announcement);
01353 #else
01354   neighbor_discovery_close(&tc->neighbor_discovery_conn);
01355 #endif /* COLLECT_ANNOUNCEMENTS */
01356   unicast_close(&tc->unicast_conn);
01357   while(packetqueue_first(&tc->send_queue) != NULL) {
01358     packetqueue_dequeue(&tc->send_queue);
01359   }
01360 }
01361 /*---------------------------------------------------------------------------*/
01362 void
01363 collect_set_sink(struct collect_conn *tc, int should_be_sink)
01364 {
01365   if(should_be_sink) {
01366     tc->is_router = 1;
01367     tc->rtmetric = RTMETRIC_SINK;
01368     PRINTF("collect_set_sink: tc->rtmetric %d\n", tc->rtmetric);
01369     bump_advertisement(tc);
01370 
01371     /* Purge the outgoing packet queue. */
01372     while(packetqueue_len(&tc->send_queue) > 0) {
01373       packetqueue_dequeue(&tc->send_queue);
01374     }
01375 
01376     /* Stop the retransmission timer. */
01377     ctimer_stop(&tc->retransmission_timer);
01378   } else {
01379     tc->rtmetric = RTMETRIC_MAX;
01380   }
01381 #if COLLECT_ANNOUNCEMENTS
01382   announcement_set_value(&tc->announcement, tc->rtmetric);
01383 #endif /* COLLECT_ANNOUNCEMENTS */
01384   update_rtmetric(tc);
01385 
01386   bump_advertisement(tc);
01387 
01388   if(DRAW_TREE) {
01389     printf("#A rt=0,p=0\n");
01390   }
01391 }
01392 /*---------------------------------------------------------------------------*/
01393 int
01394 collect_send(struct collect_conn *tc, int rexmits)
01395 {
01396   struct collect_neighbor *n;
01397   int ret;
01398   
01399   packetbuf_set_attr(PACKETBUF_ATTR_EPACKET_ID, tc->eseqno);
01400 
01401   /* Increase the sequence number for the packet we send out. We
01402      employ a trick that allows us to see that a node has been
01403      rebooted: if the sequence number wraps to 0, we set it to half of
01404      the sequence number space. This allows us to detect reboots,
01405      since if a sequence number is less than half of the sequence
01406      number space, the data comes from a node that was recently
01407      rebooted. */
01408 
01409   tc->eseqno = (tc->eseqno + 1) % (1 << COLLECT_PACKET_ID_BITS);
01410 
01411   if(tc->eseqno == 0) {
01412     tc->eseqno = ((int)(1 << COLLECT_PACKET_ID_BITS)) / 2;
01413   }
01414   packetbuf_set_addr(PACKETBUF_ADDR_ESENDER, &rimeaddr_node_addr);
01415   packetbuf_set_attr(PACKETBUF_ATTR_HOPS, 1);
01416   packetbuf_set_attr(PACKETBUF_ATTR_TTL, MAX_HOPLIM);
01417   if(rexmits > MAX_REXMITS) {
01418     packetbuf_set_attr(PACKETBUF_ATTR_MAX_REXMIT, MAX_REXMITS);
01419   } else {
01420     packetbuf_set_attr(PACKETBUF_ATTR_MAX_REXMIT, rexmits);
01421   }
01422 
01423   PRINTF("%d.%d: originating packet %d, max_rexmits %d\n",
01424          rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
01425          packetbuf_attr(PACKETBUF_ATTR_EPACKET_ID),
01426          packetbuf_attr(PACKETBUF_ATTR_MAX_REXMIT));
01427 
01428   if(tc->rtmetric == RTMETRIC_SINK) {
01429     packetbuf_set_attr(PACKETBUF_ATTR_HOPS, 0);
01430     if(tc->cb->recv != NULL) {
01431       tc->cb->recv(packetbuf_addr(PACKETBUF_ADDR_ESENDER),
01432                    packetbuf_attr(PACKETBUF_ATTR_EPACKET_ID),
01433                    packetbuf_attr(PACKETBUF_ATTR_HOPS));
01434     }
01435     return 1;
01436   } else {
01437 
01438     /* Allocate space for the header. */
01439     packetbuf_hdralloc(sizeof(struct data_msg_hdr));
01440 
01441     if(packetqueue_enqueue_packetbuf(&tc->send_queue,
01442                                      FORWARD_PACKET_LIFETIME_BASE *
01443                                      packetbuf_attr(PACKETBUF_ATTR_MAX_REXMIT),
01444                                      tc)) {
01445       send_queued_packet(tc);
01446       ret = 1;
01447     } else {
01448       PRINTF("%d.%d: drop originated packet: no queuebuf\n",
01449              rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1]);
01450       printf("%d.%d: drop originated packet: no queuebuf\n",
01451              rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1]);
01452       ret = 0;
01453     }
01454 
01455     
01456     n = collect_neighbor_list_find(&tc->neighbor_list, &tc->parent);
01457     if(n != NULL) {
01458       PRINTF("%d.%d: sending to %d.%d\n",
01459              rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1],
01460              n->addr.u8[0], n->addr.u8[1]);
01461     } else {
01462       PRINTF("%d.%d: did not find any neighbor to send to\n",
01463              rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1]);
01464 #if COLLECT_ANNOUNCEMENTS
01465 #if COLLECT_CONF_WITH_LISTEN
01466       PRINTF("listen\n");
01467       announcement_listen(1);
01468       ctimer_set(&tc->transmit_after_scan_timer, ANNOUNCEMENT_SCAN_TIME,
01469                  send_queued_packet, tc);
01470 #else /* COLLECT_CONF_WITH_LISTEN */
01471       announcement_set_value(&tc->announcement, RTMETRIC_MAX);
01472       announcement_bump(&tc->announcement);
01473 #endif /* COLLECT_CONF_WITH_LISTEN */
01474 #endif /* COLLECT_ANNOUNCEMENTS */
01475 
01476       /*      if(packetqueue_enqueue_packetbuf(&tc->send_queue,
01477                                        FORWARD_PACKET_LIFETIME_BASE *
01478                                        packetbuf_attr(PACKETBUF_ATTR_MAX_REXMIT),
01479                                        tc)) {
01480         return 1;
01481       } else {
01482         PRINTF("%d.%d: drop originated packet: no queuebuf\n",
01483                rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1]);
01484         printf("%d.%d: drop originated packet: no queuebuf\n",
01485                rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1]);
01486                }*/
01487     }
01488   }
01489   return ret;
01490 }
01491 /*---------------------------------------------------------------------------*/
01492 int
01493 collect_depth(struct collect_conn *tc)
01494 {
01495   return tc->rtmetric;
01496 }
01497 /*---------------------------------------------------------------------------*/
01498 const rimeaddr_t *
01499 collect_parent(struct collect_conn *tc)
01500 {
01501   return &tc->current_parent;
01502 }
01503 /*---------------------------------------------------------------------------*/
01504 void
01505 collect_purge(struct collect_conn *tc)
01506 {
01507   collect_neighbor_list_purge(&tc->neighbor_list);
01508   rimeaddr_copy(&tc->parent, &rimeaddr_null);
01509   update_rtmetric(tc);
01510   if(DRAW_TREE) {
01511     printf("#L %d 0\n", tc->parent.u8[0]);
01512   }
01513   rimeaddr_copy(&tc->parent, &rimeaddr_null);
01514 }
01515 /*---------------------------------------------------------------------------*/
01516 void
01517 collect_print_stats(void)
01518 {
01519   PRINTF("collect stats foundroute %lu newparent %lu routelost %lu acksent %lu datasent %lu datarecv %lu ackrecv %lu badack %lu duprecv %lu qdrop %lu rtdrop %lu ttldrop %lu ackdrop %lu timedout %lu\n",
01520          stats.foundroute, stats.newparent, stats.routelost,
01521          stats.acksent, stats.datasent, stats.datarecv,
01522          stats.ackrecv, stats.badack, stats.duprecv,
01523          stats.qdrop, stats.rtdrop, stats.ttldrop, stats.ackdrop,
01524          stats.timedout);
01525 }
01526 /*---------------------------------------------------------------------------*/
01527 /** @} */