Contiki 2.6
|
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(¤t_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, ¤t_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 /** @} */