iproutingp.nc

tinyos-2.x.rar

#endif
  }

  uint16_t getMetric(struct neigh_entry *r) {
    return (((r == NULL) || (!(IS_NEIGH_VALID(r)))) ? 
            0xffff : (r->costEstimate + getLinkCost(r)));
  }

  // Selects a potential neighbor that is not the current default route
  void chooseNewRandomDefault(bool force) {
    uint8_t i;
    uint8_t numNeigh = 0;
    uint8_t chosenNeigh;
    bool useHops = TRUE;

    dbg("IPRouting", "Looking for a new default route\n");
  retry:
    for (i = 1; i < N_NEIGH; i++) {
      if (!(IS_NEIGH_VALID(&(neigh_table[i])))) break;
      if (&neigh_table[i] == default_route) continue;
      if ((useHops && neigh_table[i].hops < neigh_table[0].hops) ||
          (!useHops && neigh_table[i].costEstimate < neigh_table[0].costEstimate)) {
        numNeigh++;
      }
    }

    // There exist other neighbors with respectable hop counts
    if (numNeigh) {
      chosenNeigh = (call Random.rand16()) % numNeigh;
      for (i = 1; i < N_NEIGH; i++) {
        if (&neigh_table[i] == default_route) continue;
        if ((useHops && neigh_table[i].hops < neigh_table[0].hops)
            || (!useHops && neigh_table[i].costEstimate < neigh_table[0].costEstimate)) {
          if (chosenNeigh) {
            chosenNeigh--;
          } else {
            default_route = &neigh_table[i];
            default_route_failures = 0;
            return;
          }
        }
      }
    }

    if (!force || !useHops) goto done;
    numNeigh = 0;
    useHops = FALSE;
  goto retry;

  done:
    dbg("IPRouting", "No random route found\n");
    default_route = &neigh_table[0];
    default_route_failures = 0;
  }
  /*
   * return: a send policy for a given attempt, including destination and one-hop neighbor.
   *        if no default route is available, returns FAIL unless the
   *        packet is destined to a link-local address, or a
   *        all-node/all-routers local multicast group.
   *
   */
  command error_t IPRouting.getNextHop(struct ip6_hdr   *hdr, 
                                       struct ip6_route *sh,
                                       ieee154_saddr_t prev_hop,
                                       send_policy_t *ret) {
    
    int i;
#ifdef CENTRALIZED_ROUTING
    struct flow_entry *r = getFlowEntry_Header(hdr);
#endif
    prev_hop = 0;
    ret->retries = BLIP_L2_RETRIES;
    ret->delay = (BLIP_L2_DELAY % (call Random.rand16())) + BLIP_L2_DELAY;
    ret->current = 0;
    ret->nchoices = 0;
 
/*     printfUART("determining next hop for message bound to: 0x%x (sh: %p)\n",  */
/*                ntohs(hdr->ip6_dst.s6_addr16[7]), sh); */

    if (sh != NULL) {
      printfUART(" type: 0x%x, next hop: 0x%x, remain: 0x%x\n",
          sh->type, ntohs(sh->hops[ROUTE_NENTRIES(sh) - sh->segs_remain]), sh->segs_remain);
    }


    // we only use the address in the source header if the record option is not used
    // otherwise, we use normal routing.
    if (sh != NULL && ((sh->type & ~IP6ROUTE_FLAG_MASK) == IP6ROUTE_TYPE_SOURCE)) {
      // if it's source routed, grab the next address out of the header.


      if (sh->segs_remain == 0) return FAIL;

      ret->dest[0] = ntohs(sh->hops[ROUTE_NENTRIES(sh) - sh->segs_remain]);
      ret->nchoices = 1;

    } else if (hdr->ip6_dst.s6_addr[0] == 0xff &&
               (hdr->ip6_dst.s6_addr[1] & 0xf) <= 0x03) {
      //hdr->dst_addr[0] == 0xff && (hdr->dst_addr[1] & 0xf) == 0x2) {
      // if it's multicast, for now, we send it to the local broadcast
      ret->dest[0] = 0xffff;
      ret->nchoices = 1;
      ret->retries = 0;
      ret->delay = 0;
      return SUCCESS;
    } else if (cmpPfx(hdr->ip6_dst.s6_addr, linklocal_prefix)) {
      ret->dest[0] = ntohs(hdr->ip6_dst.s6_addr16[7]); //  (hdr->dst_addr[14] << 8) | hdr->dst_addr[15];
      ret->nchoices = 1;
      return SUCCESS; // Currently only want one choice for broadcast
    } 

    if (getNeighEntry(ntohs(hdr->ip6_dst.s6_addr16[7])) != NULL) {
        dbg("IPRouting", "Directly adding next hop of dest: 0x%x\n", ntohs(hdr->ip6_dst.s6_addr16[7]));
        ret->dest[ret->nchoices++] = ntohs(hdr->ip6_dst.s6_addr16[7]);
    }
    
#ifdef CENTRALIZED_ROUTING
    if (r != NULL)
      updateFlowCounts(r);
     
    for (i = 0; i < N_FLOW_CHOICES; i++) {
      ieee154_saddr_t next_choice;
      if (r == NULL || 
          !IS_VALID_ENTRY(r->entries[i]) || 
          (IS_FULL_TYPE(r->entries[i]) && 
           r->entries[i].pathE->path_len > 1)) break;
      next_choice = nextHop_Flow(&(r->entries[i]));
      if (next_choice != prev_hop) {
        ret->dest[ret->nchoices++] = next_choice;
        dbg("Install", "Match: Neighbor 0x%x provided as choice 0x%x\n", 
            ret->dest[i], ret->nchoices - 1);
      }
    }
#endif

    //dbg("IPRouting", "flags: 0x%x neigh: 0x%x\n", r->flags, r->neighbor);
    if (IS_NEIGH_VALID(default_route) && prev_hop != default_route->neighbor) {
      ret->dest[ret->nchoices++] = default_route->neighbor;
    } else {
      dbg("IPRouting", "Invalid default route... quitting\n");
      /*
       * if we failed because the default route is invalid, we want to
       * trigger a routing update whenever we manage to reattach.
       */
      traffic_sent = FALSE;
      return FAIL;
    }
    i = 0;
    while (ret->nchoices < N_PARENT_CHOICES && i < N_NEIGH) {
      if (IS_NEIGH_VALID(&neigh_table[i]) &&
          &neigh_table[i] != default_route &&
          neigh_table[i].neighbor != prev_hop) {
        ret->dest[ret->nchoices++] = neigh_table[i].neighbor;
      }
      i++;
    }
    
    if (ret->nchoices == 0)
      return FAIL;
    
    dbg("IPRouting", "getNextHop: nchoices: 0x%x\n", ret->nchoices);
    
    return SUCCESS;
  }

  command uint8_t IPRouting.getHopLimit() {
    // advertise our best path to the root
    if (IS_NEIGH_VALID(&(neigh_table[0])))// && IS_MATURE(&neigh_table[0]))
      return neigh_table[0].hops + 1;
    else return 0xf0;
  }

  command uint16_t IPRouting.getQuality() {
    if (IS_NEIGH_VALID(&(neigh_table[0])))
      return getMetric(&(neigh_table[0]));
    else return 0xffff;
  }

  
  /*
   * An advertisement was received from a neighboring node
   *
   * Processing steps:
   * 1) First must check to see if the neighbor already exists in the table
   *  a) If so, we are just updating its information
   * 2) If not in table, check to make sure that the lqi passes the low-filter bar.
   *  a) If not, return
   * 3) If there is an empty space
   *  a) Insert it in the open space
   *  b) (Do we then want to move it up to where it belongs based on total path cost?)
   * 4) If there is no open space
   *  a) If the last entry doesn't meet the confidence threshold (CONF_EVICT_THRESHOLD), do nothing
   *  b) Otherwise, replace last entry if:
   *    i) Advertised Path Cost difference is greater than PATH_COST_DIFF_THRESH
   *    ii) Advertised Path Cost difference is within PATH_COST_DIFF_THRESH, 
   *         and Link estimate is lower by at least LQI_DIFF_THRESH
   * 5) Make sure to update the receptions statistic
   */ 
  command void IPRouting.reportAdvertisement(ieee154_saddr_t neigh, uint8_t hops, 
                                             uint8_t lqi, uint16_t cost) {
    //int i, place = N_NEIGH;
    //bool mustInsert = FALSE, exists = FALSE;
    //uint8_t maxCost = 0;
    //bool recount = FALSE;
    struct neigh_entry *neigh_slot =  NULL;
    dbg("IPRouting", "report adv: 0x%x 0x%x 0x%x 0x%x\n", neigh, hops, lqi, cost);
    dbg("IPRouting", "my Cost: 0x%x\n", getMetric(&(neigh_table[0])));
   
    // If neighbor does not exist in table 
    if ((neigh_slot = getNeighEntry(neigh)) == NULL) {
      dbg("IPRouting", "Advertisement from new neighbor 0x%x!\n", neigh);
      if (adjustLQI(lqi) > LQI_ADMIT_THRESH || cost == 0xffff) {
        dbg("IPRouting", "Poor Link.  Rejecting\n");
        return;
      }
      // free spots in the table.
      if(!(IS_NEIGH_VALID(&(neigh_table[N_NEIGH - 1])))) {
        
        dbg("IPRouting", "Neighbor being inserted in empty slot: 0x%x\n", N_NEIGH - 1);
        for (neigh_slot = &(neigh_table[N_NEIGH - 1]); 
             neigh_slot > &(neigh_table[0]); neigh_slot--) {
          // we might go ahead of other neighbors if we haven't heard
          // from them either and our cost is better.
          if (IS_NEIGH_VALID(neigh_slot - 1) &&
              getConfidence(neigh_slot - 1) == 0 &&
              (((struct neigh_entry *)(neigh_slot - 1))->costEstimate > cost)) {
            swapNodes((neigh_slot - 1), neigh_slot);
          } else if (IS_NEIGH_VALID(neigh_slot - 1)) {
            // if we didn't catch on the first check and the next
            // highest guy in the table is valid, we'll just go at the
            // end.  If this never catches, the loop will terminate
            // with neigh_slot == &neigh_table[0].
            break;
          }
        }
        ip_memclr((void *)neigh_slot, sizeof(struct neigh_entry));
      } else {
        // evict the bottom guy?
        dbg("IPRouting", "No empty slots...looking to replace bottom entry\n");
        //if (getConfidence(&(neigh_table[N_NEIGH - 1])) >= CONF_EVICT_THRESHOLD) {
        if (IS_MATURE(&(neigh_table[N_NEIGH - 1])) ||
            hops <= neigh_table[N_NEIGH - 1].hops) {
          dbg("IPRouting", "Bottom entry evictable\n");
          // we're a lot better,
          if ((checkThresh(neigh_table[N_NEIGH - 1].costEstimate, cost, 
                           PATH_COST_DIFF_THRESH) == BELOW_THRESH) || 
              // or we're about equal and the link estimate is better
              ((checkThresh(neigh_table[N_NEIGH - 1].costEstimate, cost, 
                            PATH_COST_DIFF_THRESH) == WITHIN_THRESH) && 
               (checkThresh(neigh_table[N_NEIGH - 1].linkEstimate, adjustLQI(lqi), 
                            LQI_DIFF_THRESH) == BELOW_THRESH))) {
            dbg("Evictions", "evict: bottom entry\n");

            // use evict to correctly handle the case when we evict
            // the default route.
            evictNeighbor(&neigh_table[N_NEIGH - 1]);
            neigh_slot = &(neigh_table[N_NEIGH - 1]);
          }
        }
      }
    } else {
      if (cost == 0xffff) {
        dbg("Evictions", "evict with cost 0xffff\n");
        evictNeighbor(neigh_slot);
        return;
      }
      // Do this to prevent double counting because of reportReception
      neigh_slot->stats[SHORT_EPOCH].receptions--; 
    }
      
    if (neigh_slot != NULL) {
      SET_NEIGH_VALID(neigh_slot);
      neigh_slot->neighbor = neigh;
      neigh_slot->hops = hops;
      neigh_slot->costEstimate = cost;
      neigh_slot->linkEstimate = adjustLQI(lqi);
      neigh_slot->stats[SHORT_EPOCH].receptions++;
      dbg("IPRouting", "currentEpoch: 0x%x, Receptions in epoch: 0x%x, Total Receptions: 0x%x\n", 
                 SHORT_EPOCH, neigh_slot->stats[SHORT_EPOCH].receptions, getReceptions(neigh_slot));
    }
    printTable();
  }

  /*
   * Reports packet reception
   *
   * Updates the link estimate, as well as the number of receptions
   */
  command void IPRouting.reportReception(ieee154_saddr_t neigh, uint8_t lqi) {
    struct neigh_entry *e = getNeighEntry(neigh);
    dbg("IPRouting", "Packet received from 0x%x lqi: %u\n", neigh, lqi);
    //if (e == NULL) e = addNeighEntry(neigh);
    if (e != NULL) {
      e->linkEstimate = adjustLQI(lqi);
      // e->stats[current_epoch].receptions++;
      //if (e == &(neigh_table[0]))
        //resetNeighLow();
      //else if (getMetric(e) < getMetric(&(neigh_table[0]))) {
        //sortFlowTable();
        //resetNeighLow();
      //}
    }
  }

  // Updates success (and failure) statistics
  // Also needs to reroute if the number of failures hits the threshold 
  event void IPExtensions.reportTransmission(uint8_t label, send_policy_t *policy) {
    int i;
    struct neigh_entry *e = NULL;
    
    // If not a broadcast address:
    //  1. If none of the provided addresses worked, then we should send out a solicitation
    //  2. All the failed nodes should have their totals increased by the max number of retries
    //  3. The successful node should update both its total and success by one
    //  4. If the successful node meets one of the following two conditions, it should be moved up one spot:
    //   a) It has a lower path cost and higher confidence than the above entry
    //   b) It has a similar path cost and confidence above a threshold (CONF_PROM_THRESHOLD)
    //  5. If we have had too many consecutive losses (MAX_CONSEC_FAILURES) toggle ReRouting
    if (policy->dest[0] != IEEE154_BROADCAST_ADDR) {
      // BLIP_STATS_INCR(stats.messages);
      dbg("IPRouting", "reportTransmission: current: 0x%x, nchoices: 0x%x, retries: 0x%x\n", 
                 policy->current, policy->nchoices, policy->actRetries); 

      // update the failed neighbor statistics
      for (i = 0; i < policy->current; i++) {
        e = getNeighEntry(policy->dest[i]);
        if (e != NULL) {
          // SDH : presumably retries == actRetries
          e->stats[SHORT_EPOCH].total += policy->retries;
          
          if (e == default_route) {
            default_route_failures++;
          }

          dbg("IPRouting", "reportTransmissions: 0x%x failed\n", e->neighbor);

          // stats.transmissions += policy->retries;
        }
      }

      if (default_route_failures > MAX_CONSEC_FAILURES) {
        dbg("IPRouting", "Too many consecutive failures!\n");
        chooseNewRandomDefault(TRUE);
      }
      
      // if we succeeded sending the packet, increment the success on that one.
      e = getNeighEntry(policy->dest[policy->current]);
      if ((policy->current < policy->nchoices) && e != NULL) {
        e->stats[SHORT_EPOCH].success += 1;
        e->stats[SHORT_EPOCH].total += policy->actRetries;

        dbg("IPRouting", "Success: 0x%x, Total: 0x%x, ETX: 0x%x (addr 0x%x)\n", 
                   getSuccess(e), getConfidence(e), getLinkCost(e), e->neighbor);
        dbg("IPRouting", "Actual attempts was 0x%x\n", policy->actRetries);

        if (e == default_route)