[SensorNetArch] grabbing a token on section 2...

[istoica at EECS.Berkeley.EDU]

Here is the modified sec 2. I removed some text
here and there, as I thought that in some places
was too much detail (e.g., in the message pool subsec).

I also added a rough draft of a discussion subsec 
(just before the implementation subsec) that tries to 
justify the functionality provided by sp. 

I think the implementation should be a separate sec.

Ion

PS. The figure looks good. We'll talk more tomorrow...


----- Original Message -----
From: Joe Polastre <joe.polastre at gmail.com>
Date: Friday, April 8, 2005 3:00 am
Subject: Re: [SensorNetArch] grabbing a token on section 2...

> I have new figures and some rewrites for section 2; let me know when
> you're done with the lock and i'll merge my changes.
> 
> First fig is attached to this message for comments/review.  it is
> intended to show how sending and message futures work.
> 
> -Joe
> 
> On Apr 7, 2005 10:38 PM, istoica at eecs.berkeley.edu
> <istoica at eecs.berkeley.edu> wrote:
> > 
> > _______________________________________________
> > SensorNetArch mailing list
> > SensorNetArch at Millennium.Berkeley.EDU
> > http://Mail.Millennium.Berkeley.EDU/mailman/listinfo/sensornetarch
> >
> 
-------------- next part --------------
\section{\sps Design}
\label{sec:sp}

Most deployed sensor networks consist of dense patches of wireless
nodes, where each patch is connected to the Internet via one or more
gateway nodes, either directly or through some form of transit
network~\cite{SMP:04habitat,HAE:ess,SOPHME:habitat-cacm,xscale}.
Unlike Internet, in sensor networks aggregate communication is
prevalent, whereas point-to-point communication is rare.  Although
each patch is often an edge network, it must address many of the
issues associated with the Internet.  Each node potentially operates
as a data source, data sink, and router.  In addition to generating
sensor data, nodes must form and maintain routes,
%translate intended destinations into hop routing decisions,
and forward traffic.  The nodes must achieve this despite noisy,
time-varying, and even intermittent connectivity.
  
These challenges have motivated a wide range of work at the physical,
data link, media access, and network layers. However, while there are
many options and possibilities at each layer, they are rarely
interchangeable. Instead, resource constraints, power management, and
application specific processing have forced many studies to make
numerous assumptions about the surrounding networking abstractions.
The variations in these assumptions prevent integrating individual
advancements into a complete solution. For example, the PSFQ routing
protocol assumes that nearby nodes can overhear
transmissions~\cite{psfq}, while TDMA based MAC protocols, such as
IEEE 802.15.4~\cite{ieee802154}, S-MAC~\cite{smac}, T-MAC~\cite{tmac},
and TRAMA~\cite{trama} can make this an invalid assumption.

The goal of \sps is to provide a unified interface to a wide range of
data link and physical protocols that allows network layer and above
protocols to operate efficiently and optimize without depending on a
particular underlying technology.  By providing a unified
interface,~\sps can offer a number of advantages over integrated
approaches. In particular, it allows multiple network protocols and
link technologies to coexist and evolve independently of each other
in the same way the IP layer allows transport protocols and link
layer technologies to evolve independently in today's Internet).
%execution efficiency can increase by operating over a set of messages
%from many protocols, multiple network protocols can coexist
%peacefully, and evolve independently of the current link technology
%(in the same way IP enables transport protocols to evolved
%independently of the link layer technologies in today's Internet).
%innovation on new network protocols can be written in
%a lasting manner, independent of the current link technology.

There is a considerable debate in the sensor network community over
which one of the network deployments (i.e., one-hop or multi-hop) will
become prevalent in the future. Since \sps is positioned under the
network layer, it is equally relevant for both deployment
scenarios. 

%Although \sps is designed as a bridge between link and network
%protocols, one hop operations must not suffer due to the abstraction.

Although we considered a variety of alternative design points, this
section describes the approach that we see as most effective in
achieving this goal.  Experience has shown that currently multihop and
single hop protocols cannot efficiently operate independently of each
other: they must share information.  The layers above and below must
be decoupled, but must also cooperate.  The principal design challenge
in \sps is defining how they achieve this cooperation in a simple but
expressive way.  This section describes a particular set of concepts
that form an \sps abstraction.  The abstraction could be implemented
in virtually any operating system, but the description would not be
complete without describing its interface for some meaningful
execution model.  We ground the \sps concepts with a concrete
implementation on the TinyOS operating system~\cite{tinyos}.

\subsection{Description}\label{sec:sp-concept}

\begin{figure}[t]
	\centering
	\includegraphics[width=0.49\textwidth]{figures/sp-concept}

	\caption{Conceptual view of \sps architecture.  Network services interact with various link protocols through \sps's shared neighbor table and message pool.}

	\label{fig:sp-concept}
\end{figure}

Figure~\ref{fig:sp-concept} shows the general \sps architecture:
network protocols reside above and data link protocols reside
below.~\sps bridges the two, providing link independent abstractions
to build efficient network protocols.  Multiple network protocols may
coexist on a node. Each network protocol is identified by a protocol
id, which is similar to a protocol type in IP, or an AM id in TinyOS.
Unlike the Internet where there is only one network protocol (i.e.,
IP),~\sps supports many network protocols which implement a variety of
%Applications typically include multiple network protocols to
%achieve a diverse set of 
functions, such as collection for data delivery, dissemination for
code updates, aggregation, and others.  The primary goal of~\sps is to
enable multiple network protocols to coexist and work efficiently.
The~\sps abstraction is implemented on a variety of link technologies,
which may utilize different physical technologies, encodings,
framings, media access mechanisms, collision avoidance protocols, and
power management mechanisms.  A node employs one or more link
technologies, depending on its hardware capabilities.
%The unified abstraction is the boundary between
%\sps and network level services.
%SP implementations
%are link dependent but expose a link independent interface to 
%network protocols.  Each network level protocol should be able to
%operate efficiently over whichever link is present via the \sps
%abstraction.

\sps performs three main operations: (1) data transmission, (2) data 
reception, and (3) neighbor management. Data transmission and
reception are message oriented, with a variable message length.
Underlying link protocols dictate a maximum data unit (MDU).  Network
protocols may query for the MDU size, fragment messages, and send the
message fragments to SP for transmission. Next, we discuss the three
operations performed by~\sps.

\vskip 0.1cm
\noindent
{\em Data Reception:} This is the simplest operation. A message
arriving on a link interface is dispatched to its associated network
protocol.  Optional message filtering may discard messages not
destined for the node's local address or for the broadcast address.
SP takes no position on higher level naming and scheduling issues
other than that nodes have an address on each interface.
\remark{need to be careful here.  Can a node have multiple
matching addresses on a link - culler}
%The protocol processes
%the packet and returns the associated storage resources.

\vskip 0.1cm
\noindent
{\em Data Transmission:} This operation is implemented using a shared
{\em message pool} data structure at the \sps layer.  Network
protocols submit messages to the pool for transmission.  Messages are
specified with control information for lower layers, such as
reliability and latency requirements. The pending messages in the pool
may be inspected by the link layer and other network protocols that
optimize their behavior based on the pool's content.  Upon
transmitting a message,~\sps provides feedback to the network
protocol. This feedback includes various information, such as
congestion status, that may help the network protocol to optimize its
behavior.
%Feedback is provided upon completion of a message transmission
%providing key information, such as channel congestion status, for
%adjusting network protocol behavior.

\vskip 0.1cm
\noindent
{\em Neighbor Management.}~\sps allows the link layer and the network
protocols to cooperatively maintain an effective summary of the useful
immediate neighbors.  This is achieved through a {\em neighbor table}
data structure, which maintains information about the link quality and
power scheduling.~\sps mediates the interactions between network
protocols and one or more specific links.  Rather than a rigid
separation of these layers,~\sps allows network and link layers to
cooperate through logically shared structures: a neighbor table and a
message pool, described below.

\vskip 0.1cm
\noindent
Below, we present the two main data structures maintained by the~\sps,
the neighbor table and the message pool, in more detail.

\subsection{Neighbor Table}

Typically, the network protocols maintain information about their
neighbors in order to make informed decisions for routing,
aggregation, and dissemination.  Similarly, the link layer maintain
information about the state of the link to particular neighbors.  The
mutual interest in neighbor-related information has often led to
monolithic designs.  For example, MintRoute~\cite{awoo-sensys} in the
TinyOS distribution combines link reliability information for its
direct neighbors with path metrics (e.g., hop count, expect path cost)
for routing to a root node.  Likewise, slotted link protocols
presented in~\cite{smac, tmac, trama} monitor neighbors to maintain
synchronization and connectivity.  Whereas MintRoute includes link
functionality and S-MAC includes network functionality,
UNPF~\cite{unpf} proposes a single unified layer must include both
link and routing information.  The UNPF proposal is not tractable nor
suitable for enabling innovation at the network layer in wireless
sensor networks.  

As sensor networks mature and multiple network protocols co-exist, it
becomes increasingly attractive to share information among various
network protocols, rather than require each of them to maintain its
own table. The~\emph{Neighbor Table} is the main repository of this
shared information. This information enables the cooperation between
network protocols and the link layer, and allows the \sps to decide
when to listen, receive, transmit, and sleep.  The insertion and the
eviction of the entries in the neighbor table are deferred to the
network protocols and the link layers to cooperatively decide which
entries belong in the table.

An entry in the neighbor table usually consists of the address of the
neighbor, link quality, and scheduling information.  For added
flexibility, the table is extensible--network services and link
protocols may add columns to it, such as routing gradients.  
%By maintaining a single network table at the \sps layer, network
%protocols no longer need to maintain their own independent tables and
%the overall resource usage may be decreased.  
Entries in the neighbor table are indexed by a combination of
destination address and network interface:~\sps assumes that all nodes
accessible through a given link interface have unique link addresses.
The format of the addresses are not specified by~\sps to allow
different link constraints and addressing modes.

\sps requires scheduling information in the neighbor table indicating 
when each neighbor is expected to be awake and asleep.  Both the
network and link layers potentially make use of this information to
determine which actions to take and when these actions should be
performed.  However, the horizon of this information within SP is
limited.  When the known communication schedule of a neighbor
expires,~\sps asks the network and the link layer to determine a new
schedule.  For example, a slotted MAC layer may respond with the next
beacon slot, regardless of the network layer, whereas a
rendezvous-based network protocol may respond with the next meeting
time, regardless of the link.

Studies have shown that in many cases the set of candidate neighbors
(i.e., nodes from which messages have been received recently) is much
larger than the set of useful neighbors (i.e., neighbors which can
provide a reasonable reliable link) and too large to retain in the
memory of most microcontrollers~\cite{awoo-sensys,zhao-sensys}.  Thus,
neighbor table management is critical.~\sps enforces as little policy
as possible; instead, it implements mechanisms that are applicable for
a wide range of uses.

When a new candidate node is detected, \sps asks each data link layer
whether the node should be added to the table.  When a neighbor's
scheduled awake period has expired, network and link protocols are
notified so that they can update the neighbor's schedule information.
When a node is evicted by a protocol, all other network protocols are
notified of the eviction.
%It is critical that the system's protocols manage the allocation of
%this critical resource.  
When multiple network protocols are present, rather than define the
resource sharing policy, \sps depends on the presence of an
optional~\emph{network service manager} to mediate resource conflicts.

\subsection{Message Pool}

The message pool allows the network protocols to request the message
transmissions to the link protocol.  The transmission interface
enables the network protocol to exert a degree of control over lower
level message processing, and provides feedback from the link layer.
%Through control parameters and feedback data, network protocols can
%cooperate with underlying data link protocols.

A key design issue of the message pool is how much information to
expose to the network protocols and link layers.  The more visibility
the link layer has on potential future transmissions, the better it
can schedule traffic to reduce energy and avoid contention.  For
example, a slotted or TDMA MAC might want to transmit messages with
different destinations into the same slot, whereas a CSMA MAC with
preamble sampling might want to batch messages to a given destination
so that a single long preamble can wake up the node for the entire
batch. In either case, the link layer potentially needs to consider
packets from multiple network protocols, and a simple shared queue is
insufficient. As evident from this discussion, the network protocols
should give the link layer enough flexibility to schedule the traffic
efficiently. Finally, the storage available for the message pool is
limited, and thus the decisions should be made in a timely fashion.
%Network protocols may benefit from visibility into the traffic
%generated by other protocols.

To address these design challenges,~\sps employs a \emph{message
pool}, instead of a simple queue. The message queue contains a set of
unordered messages.
%We introduce the concept of \emph{message futures}--by placing
%messages into the pool in an unordered fashion, future transmissions
%may be patched and scheduled by the underlying link.  
An \sps message may consists of multiple packets, specified when the
message is submitted to the pool.  Similar to lazy task creation
in~\cite{halstead-futures}, messages are only created as resources
(and the underlying medium) become available.  Storage for message
data is allocated elsewhere, for example, in the network services, or
link layer.  Each message pool entry contains a reference to the next
message to send, the number of the subsequent messages that need to be
sent, and a timeout event which signals when the next message should
be materialized.  
%This permits higher level services to have a rich
%set of options in how and when they makes the data available to the
%link layer.  The lower layers and the network protocols can inspect
%pending messages and their promised packet quantities to optimize and
%batch transfers.

%When a network protocol submits a send request to \sps, the details of
%the request are made visible to both the data link and network
%protocols.  
The message pool is used by~\sps in conjunction with the neighbor table
to schedule transmissions.  By batching messages from multiple
services, they can be transferred in bulk reducing latency and energy
costs.  Network protocols may inspect the message pool to make
informed decisions when to transmit.  Similarly, the link layer
inspects the message pool to decide how to schedule traffic and notify
\sps when messages can be sent.

%Often, network protocols may need to fragment a message into many individual
%packets and send them as part of a bulk transfer.  To efficiently account for
%future pending messages, \sps allows network protocols to specify the number
%of packet transmissions within an \sps message, referred to as 
%{\em message futures}.
%This mechanism allows network protocols to gain the
%benefits of larger transfers without requiring large buffers.  Packets may
%be realized only when needed after the previous packet transmission has
%completed.  

The message pool allows network and data link protocols to pass
message information to each other.  The send interface presents a
packet buffer to \sps along with simple indicators of latency
sensitivity and need for reliability on the transmission.~\sps
facilitates bi-directional exchange of control information through
this control and feedback information.  A network protocol can
indicate that a particular message entry is latency critical by
setting an {\em urgent} bit, which informs the link layer to treat it
as high priority or to send it soon even if extra energy is expended
to do so.  The level of effort that should be expended transferring a
message is indicated by a {\em reliability} bit, which informs the
link layer to acknowledge and retransmit a message for a predefined
number of times.  If the link layer's effort do not result in a
confirmed transfer, it communicates this failure by clearing the
reliability bit.  The control mechanism provides guidance to lower
layers which will attempt to optimize for power and channel
efficiency.

After transmission, lower layers send feedback to the network protocol
to adjust its behavior.  For instance, if a message has requested
reliable transmission,~\sps lets the network protocol know if the
desired level of reliability has been achieved.  The link layer could
inform the network protocols that the transmission rate is too high to
sustain by setting a {\em congestion} bit.  In another example,
consider a typical sensor network application that generate traffic at
regular intervals.  Even at low duty cycle, this traffic pattern can
result in high contention if sensor samples are highly correlated. One
solution to this problem is to stagger the data transmissions across
neighbor nodes.~\sps provides support for staggering data by sending
feedback indicating when such a phased shift would be beneficial and
providing a delta time recommendation for future traffic.

%Control parameters are mapped by \sps to underlying link primitives.
%Likewise, \sps aggregates data from the link protocol and presents
%abstracted feedback information to network services.  
%Sharing
%information between the network and link protocols allow policy to be
%implemented at either level, such as end-to-end congestion control or
%local cell broadcast suppression.
%
%To conserve resources but increase performance,
%\sps introduces \emph{Send Futures}.
%An \sps send request can be for more than one message.  Depending on
%the underlying data link layer, \sps may or may not be able to send
%multiple messages in quick succession to the same destination. Rather
%than force a protocol to commit every message it needs to send, the
%network protocol must only commit one when it makes a request. When
%\sps is ready to send the next message, it makes a request to the
%network protocol.
%\vspace{1ex}

%\subsubsection{\sps use}

\subsection{Discussion}

Our current design of \sps emphasizes on minimalism: \sps includes
only the set of features that we considered absolutely necessary to
develop applications in a sensor network environment. Primarily, these
features follow from the need to balance the application requirements,
on one hand, and to efficiently use the available resources, on the
other hand. Given the scarcity of resources in a sensor network,
achieving efficient resource utilization is not only desirable, but
{\em necessary}. This is the main reason for which the \sps interface
is necessarily more complex than the IP interface (i.e., the
corresponding narrow-waist in the Internet).

\sps provides three functionalities that are only partially supported, or 
not supported at all by IP: (1) allow the link layer to provide
congestion indication and schedule hints ({\em phase}) to the network
protocols, (2) allow a network protocol to associate a priority with
each message and specify how many messages it wants to send, and (3)
allow network protocols and the link layer to share the link
information.

The network protocol uses the congestion indication and schedule hints
received from the link layer to schedule its future transmissions in
order to optimize resource utilization. For example, upon receiving a
congestion indication, the network protocol can slow down to reduce
the probability of message loss, or aggregate the traffic to reduce
the number of transmissions. Note that unlike IP where the congestion
is signaled end-to-end, with \sps the congestion is signaled at every
hop. Architecturally, this design decision is justified by the fact
that, unlike an IP router whose main role is to forward packets, a
typical node in a sensor network runs also application code, which can
process data locally, if needed.

Ideally, the link layer would like to have complete information about
the future transmissions of the network protocols, and the delay
requirements of each message. This would allow the link layer to
schedule the message transmissions such that to minimize the energy
usage. \sps allows the network protocols to provide this information
by using message pools, and the priority mechanism.

Finally, allowing the network protocols and the link layer to share the
link information eliminates the need for each network protocol to
maintain its own link table. The advantage of sharing this information
is twofold: it reduces the storage requirements, and avoids redundant
measurements to estimate the link quality.

%The basic theme behind these three abstractions is defining a protocol
%independent way for network and data link layers to exchange
%information and coordinate their actions to work cooperatively.
%Additionally, some kinds of information, such as communication
%scheduling or link estimation, can be the product of both the network
%and data link layer information.  Providing a unifying abstraction
%allows implementations to remain independent of the distinction.
%%Figure~\ref{fig:sp-concept} shows the \sps decomposition and
%%abstractions. \sps sits between the multiple network protocols 
%%needed to support the application
%%and the particular data link layers provided by the hardware
%%and mediates their interactions. 
%Creating a new network protocol simply requires writing it against
%\sps, while adding a new data link protocol requires meeting the
%interfaces that \sps expects (this is commonly achieved by writing a
%small amount of \sps ``glue code'').

%\footnote{For example, protocols
%such as 802.15.4 use a TDMA MAC with CSMA channel access during each period
%to provide communication scheduling at
%the data link layer~\cite{ieee802154}, while network protocols such as
%FPS~\cite{fps} provide coarse scheduling on top of CSMA
%networks. Similarly, radios such as the Chipcon CC2420~\cite{cc2420} use
%chip error rates to provide link quality estimation in every message,
%whereas network protocols can
%estimate message loss rates with sequence numbers~\cite{awoo-sensys}.} 

\section{Implementation}
\label{sec:sp-impl}

To evaluate the feasibility of our approach and to make the proposal
concrete, we implemented the \sps abstraction in TinyOS.  We discuss
how \sps is implemented in TinyOS, including the neighbor table,
message pool, and minimal set of commands and events to build network
protocols.  The implementation is quite lean and is completely event
driven.  Three types of events trigger \sps to act: message receptions
and other link protocol events, network layer commands, and internal
timer events.

\begin{figure}[t]
\scriptsize
\begin{verbatim}
interface SPSend {
  command result_t send(sp_message_t* msg);
  event void sendDone(sp_message_t* msg, result_t success);
  event TOS_MsgPtr nextSend(sp_message_t* msg, uint8_t pos);
  command result_t changed(sp_message_t* msg);
  command result_t cancel(sp_message_t* msg);
}
\end{verbatim}
\caption{The SPSend interface.}
\label{fig:spsend}
\end{figure}

Network protocols make send requests to \sps with the {\tt SPSend} interface,
shown in Figure~\ref{fig:spsend}, which takes a single parameter, a
pointer to an {\tt sp\_message\_t}.  Figure~\ref{fig:sp-tinyos-impl} shows a
partial version of the {\tt sp\_message\_t} (it has an additional 7 bytes of
state, used for internal bookkeeping and metadata). 
The send command places a reference to the \sps 
message in the message pool
and \sps schedules it for transmission.
% by the link interface associated
%with the destination. 
A network protocol has two send control options, 
which act as hints to the underlying data
link layer: urgency and reliability.  Urgency indicates that the
message is latency critical.  It is treated as a priority mechanism --
\sps services urgent requests before others -- but also is used to
override the default power management schedule.  Extra energy may be
invested to wake up the destination in order to transfer the message
quicker.  Messages that are not marked as urgent are held in the message pool.
If the neighbor has a known wakeup period or if other traffic for that
neighbor is received, the \sps attempts to send the pending data.  Otherwise,
after message has been waiting in the pool for longer than a 
specified timeout, \sps tries to send the message more aggressively
in the same manner as urgent messages (but with less overall priority).
Reliability determines how hard \sps will try to ensure that the
message is delivered across the link.
If it is set, \sps will use acknowledgments,
retransmissions, or whatever mechanisms the underlying link provides
to ensure message delivery.  

When \sps has completed transmission of the message, it signals the
{\tt sendDone} event informing the associated network protocol.  If
\sps does not succeed in acknowledging delivery of a message marked
reliable, it resets the reliability field to false to give feedback to
the higher layer.  In addition, the data link layer provides two other
pieces of feedback to network layer: {\em phase} and {\em congestion}.
Sensor network applications tend to have highly correlated behavior,
because the same application is spread over many nodes.  For example,
the nodes may take samples at time correlated instances and then
transmit them.  Phase recommends to the network layer that if it sent
its message at a different time, it may achieve less congestion or
greater power savings.  If \sps detects excess congestion, \sps
queries the link protocol for a suitable phase shift.  The phase shift
is added to the delay incurred between submission of the message to
the pool and the actual transmission.
%In the implementation,
%the phase value is the elapsed time from when {\tt send} placed the
%message in the pool to when the link layer could accept it for
%transmission.  
The transmission delay may be a result of CSMA backoffs or TDMA slot
opportunities, depending on the underlying link.  In general, it is
important to decouple network protocol schedules
from the application's sampling schedule.
Phase feedback guides the offset for network protocols.
Congestion tells the network layer whether the data link
layer observed a congested channel when the message was sent.
Congestion allows saturation conscious
protocols (such as floods) to react accordingly or reduce their message
generation rate.
Note that the threshold for setting the congestion bit may be different
(and is higher in our implementation) than the threshold for providing a phase
offset to network protocols.

\begin{figure}[t]
	\centering
	\includegraphics[width=0.49\textwidth]{figures/sp-tinyos-impl}
	\caption{insert caption here}
	\label{fig:sp-tinyos-impl}
\end{figure}

The {\tt SPSend} interface allows the network protocol to indicate the
number of messages that are ready to follow the current one.  If this
count is non-zero, \sps can signal the {\em nextSend} event to cause
the network protocol to materialize the next message.  It may be
generated from application data, data in flash, or from a higher level
buffer.  Without imposing a large amount of RAM pressure, this allows
the link layer to burst messages when it has opportunity to do so, or
to schedule messages into upcoming slots.  The link layer, \sps layer,
and network layer are assumed to run concurrently in an event-driven
fashion.  The \sps interface allows them to schedule their activities
cooperatively.  Network protocols can modify the status of on-going
message streams using the {\tt change} and {\tt cancel}
commands. After a message is submitted, the network protocol may cancel
the outgoing message.  
After the message is submitted, activites at the network layer may cause
the contents of the message to change.  For example, a routing protocol
may receive a new route beacon that causes its parent to change.  The network
protocol may reset the destination of its pending messages and notify \sps
of the change using the {\tt change} command.
Cancel removes a message from the pending message pool.
It is particularly important for suppression
in many dissemination protocols.

\begin{figure}[t]
\scriptsize
\begin{verbatim}
interface SPNeighbor
{
  // Query and iterate through neighbors
  command sp_neighbor_t* query(uint16_t address);
  command sp_neighbor_t* get(uint8_t i);
  command uint8_t max();

  // Adding, admitting, updating and removing neighbors
  command result_t insert(sp_neighbor_t* neighbor);
  command result_t remove(sp_neighbor_t* neighbor);
  event void update(sp_neighbor_t* neighbor);
  event result_t admit(sp_neighbor_t* neighbor);

  // Expiry (update with new timing) and Eviction
  event void expired(sp_neighbor_t* neighbor);
  event void evicted(sp_neighbor_t* neighbor);

  // Adjust n's link quality based on message m
  command result_t adjust(sp_neighbor_t* n, TOS_MsgPtr m);

  // Listen to the specified neighbor on next wakeup
  command result_t listen(sp_neighbor_t* neighbor);

  // Try to find more neighbors
  command result_t find();
  command result_t findDone();
}
\end{verbatim}
\caption{The SPNeighbor interface.}
\label{fig:spneighbor}
\end{figure}

\sps provides the {\tt SPNeighbor} table interface presented
in Figure~\ref{fig:spneighbor} to allow maintainance of the neighbor table
by link and network protocols.
Next hop selections and communication scheduling are built around the
neighbor table and its associated interface.
Figure~\ref{fig:sp-tinyos-impl} shows the default TinyOS \sps
neighbor table.  It provides five pieces of information: address, time-on,
time-off, listen, and link quality for each of a limited set of
neighbors.  

Time-on and time-off indicate
when the neighbor can receive messages in terms of local node
time so that link layers can minimize idle listening.
Network protocols can incorporate link constraints 
in generating communication schedules using timing information.
For a fully active CSMA-based MAC, time on is always ``now'' and
time off is always ``never.'' 
In contrast, for a TDMA-based MAC, the
values correspond to the next time slot and its duration.
Our \sps implementation favors sleeping over listening in order to
reduce the node's duty cycle.  
If a message is pending for a neighbor, \sps will wake up and send it 
according to the neighbor's wakeup time-on in the table.  If no message is
pending, \sps will remain asleep, regardless of when that neighbor is awake.
Therefore, the time-on and time-off fields are indicators of when the
remote node is listening.  In the opposite direction, if a neighbor's
{\em listen} bit is set, \sps will explicitly wake up and receive from that
neighbor.  This allows bi-directional low power communication.
An example use of the listen bit is dissemination in a tree topology.
Nodes periodically send to their parent during their parent's active period.
Parents can broadcast data down the tree to their children during their
active period.  If the listen bit is not set, children will not wake up
and receive from their parent if they do not have any pending messages to
send to the parent.
The listen bit also permits network protocols to snoop 
on traffic from other nodes. 

\sps uses a cooperative scheme to manage neighbor table membership and
does not enforce policy on the neighbor table contents.
When a protocol requests that a neighbor be added to the table, 
it calls the {\tt insert} command.  \sps queries all other protocols with
the {\tt admit} event--if any of the protocols indicate an interest
then the neighbor is added to the table.  The {\tt admit} event allows
protocols to determine which action to take, including which entry to evict.
Since \sps generally does not have enough information to determine neighbor
schedules on its own, it signals both network and link 
protocols on neighbor expiration to attain wakeup schedules using
the {\tt expired} event.  
For example, if a TDMA MAC or a
higher level scheduling protocol knows when the neighbor will next be
awake, it can update the entry correspondingly.
To remove an entry, protocols call {\tt remove} which nullifies the entry
in the table and signals an {\tt evicted} event to link and network protocols.

Protocols may scan the neighbor table using the iteration commands found
in the {\tt SPNeighbor} interface.  Protocols {\tt get} an entry and 
query the {\tt max} number of neighbors in the table.
After receiving a message, protocols may request that the link adjust
a neighbor's link quality entry through the {\tt adjust} command
by passing the neighbor table entry and
received message.  The link uses its link estimator to update the neighbor
entry.

If the entries in the neighbor table become sparse, protocols may request
that \sps attempt to find new neighbors.  The underlying implementation of the
{\tt find} command may be implemented in numerous ways--either through
active probing, passive scanning, or enabling channel sampling.

Our implementation includes a special reserved broadcast neighbor entry.
The broadcast entry is used for the link and network protocol to inform
\sps of times where it is safe to send to the broadcast address.
The shared broadcast entries allows network wide synchronized wakeup and 
broadcast or local cell broadcast slots to be implemented with the same
framework. 

Protocols may add columns to the neighbor table to hold additional per
neighbor information. Our current
implementation achieves this through redefinition of the table entry
structure at system build time.  (We plan to use the
newly emerging nesC feature of attributes~\cite{nesc-attributes} to
simplify this process.)  
The {\tt update} event allows protocols to enter initial data into 
non-standard neighbor entries upon admission to the table or update by other
protocols.
Neighbor data is updated
through the {\tt insert} command--if the neighbor is already in the table,
its values are simply refreshed and an {\tt update} event is signalled.
% REDUNDANT
%The minimal set of neighbor columns are 
%address, time-on and time-off, listen, and link quality as shown in
%Figure~\ref{sp-tinyos-impl}.