contiki-os/contiki — pull request #288 by simonduq (2013-06-28 23:19:26+00:00)
Title: New neighbor tables

This pull requests implements a new centralized neighbor table for Contiki, in core/net/neighbor-table.[ch], meant for use in Contiki modules such as rpl, ND, routes, and phase.

The goal is to make all these modules maintain information on a consistent set of neighbors, and avoid e.g. to have a RPL preferred parent but no link metric for it. The new single configuration parameter that defines how many neighbors are in the system is NEIGHBOR_CONF_MAX_NEIGHBORS. Inspired by TinyOS’s 4-bit link estimator, this neighbor tables offer the possibility to lock a neighbor, so that all information about it will never get deleted. Upon inserting a new neighbor on a full table, an old neighbor will be possibly replaced. The replacement policy is the following: remove neighbor that is (1) not locked (2) used by fewest tables (3) oldest. This results in improved consistency in comparison with having independent tables in every module, with different capacity and having each their own replacement policy.

IPv6 ND address mapping has been moved from uip-ds6 to a new uip-ds6-neighbor, which provides a convenient interface for looping on neighbors and getting global IPv6 <-> link-local IPv6 <-> MAC mappings.

The routing module (uip-ds6-route) also uses neighbor-table. Instead of storing a single list with (destination, nexthop) pairs, we now have, for every neighbor in the system, a list of reachable destinations.

The rpl-dag module stores RPL information using neighbor-table, and constantly keeps RPL preferred parent(s) locked, guaranteeing that connectivity to the border router will never be lost, and the the path to it will remain efficient (e.g., when using ContikiMAC, the phase lock to this neighbor is never dropped).

The neighbor-info module, which was only used by RPL for ETX calculation, is removed. Instead, ETX is calculated by rpl-of-etx.c, and stored directly in the RPL data structures, avoiding conversions between different fixed point representations, and saving space and complexity.

A side benefit of this new module is substantial RAM savings: link-layer addresses are stored only once rather than in every module that keeps information about neighbors. IPv6 addresses are shared among ds6-neighbor, ds6-route, rpl-dag. On msp430, the RAM consumption per neighbor goes from 128 to 81. The RAM per route entry goes from 48 to 31. There is no significant impact on ROM consumption (increase in the range [0-14] bytes for rpl-border-router, udp-sink, udp-sender).

The pull request includes a large number of modified files, due to a change in the API to access routes and ND information, which affects many platforms, examples and apps.