btnut/btnode/include/cc/aodv.h File Reference


Detailed Description

Ad-hoc On Demand Vector (AODV) routing implementaion for the CC1000 radio based on [Perkins et al., Ad hoc On-Demand Distance Vector (AODV) Routing].

Author:
Florian Schuetz <fschuetz@ethz.ch>
This implementation is designed to work together with the RoutingForChipcon (RFC) layer. The implementation has been tailored towards the use with btnodes, but could easily be adaptet to Nut/OS.

Much performance can be gained, by adjusting the parameters to the task that the operating set of nodes is assigned to. For a detailed description of the parameters see [Perkins et al., Ad hoc On-Demand Distance Vector (AODV) Routing] or [Schuetz, Implementation and Testing of an Ad-hoc Routing Protocol for the Chipcon-Interface of BTnodes].

Further, in debug mode, this implementation alows to change most of the parmameter, inject packages, observe routing states and gather metrics easily. It is therefore well suited to gain insight into routing in distributed, wireless sensor networks.

Attention:
Throughout the code there are coments that say "IMPROVE". This means that at this point, AODV performance could be improved in a later version.

#include <sys/types.h>
#include <cc/ccc.h>
#include "routing.h"

Defines

#define _BT_ADOV_H_
#define ACTIVE_ROUTE_TIMEOUT   10000
#define ALLOWED_HELLO_LOSS   2
#define BLACKLIST_SIZE   10
#define BLACKLIST_TIMEOUT   4 * (RREQ_RETRIES * (long)NET_TRAVERSAL_TIME)
#define CONTROL_PACKET_QUEUE_SIZE   10
#define DELETE_PERIOD   (5 * MAX((long)ACTIVE_ROUTE_TIMEOUT, (long)HELLO_INTERVAL))
#define DISCOVERY_BUFFER_SIZE   10
#define HELLO_INTERVAL   0
#define LOCAL_ADD_TTL   2
#define MAX_REPAIR_TTL   12
#define MY_ROUTE_TIMEOUT   (2 * ACTIVE_ROUTE_TIMEOUT)
#define NET_DIAMETER   15
#define NET_TRAVERSAL_TIME   (2 * NODE_TRAVERSAL_TIME * NET_DIAMETER)
#define NEXT_HOP_WAIT   (NODE_TRAVERSAL_TIME + 10)
#define NODE_TRAVERSAL_TIME   200
#define PATH_DISCOVERY_TIME   (2 * NET_TRAVERSAL_TIME)
#define RERR_RATELIMIT   10
#define RING_TRAVERSAL_TIME   (2 * NODE_TRAVERSAL_TIME * (TTL_VALUE + TIMEOUT_BUFFER))
#define ROUTING_TABLE_SIZE   20
#define RREP_BUFFER_SIZE   20
#define RREP_RETRY   7
#define RREQ_BUFFER_SIZE   50
#define RREQ_RATELIMIT   10
#define RREQ_RETRIES   7
#define TIMEOUT_BUFFER   2
#define TTL_INCREMENT   2
#define TTL_START   1
#define TTL_THRESHOLD   7
#define TTL_VALUE   2

Functions

void aodv_enable_led (int enable_led)
u_short aodv_get_address (void)
int aodv_get_rreq_id (void)
int aodv_get_sequence_no (void)
int aodv_init (u_short address)
void aodv_print_rt (void)
void aodv_print_rt_entry (int entry)
int aodv_route_discover (u_short dst)
u_short aodv_set_address (u_short addr)

Variables

routing_interface_t aodv_interface
routing_interface_t aodv_interface
 Interface of the routing protocol.
u_short aodv_invalid_count
 Number of invalid packets targeted for this node.
u_short aodv_rerr_recv_count
 Number of RERR packets targeted for this node.
u_short aodv_rerr_send_count
 Number of RERR packets sent from this node. (including failed).
u_short aodv_rerr_send_fail_count
 Number of send failures of RERR packets.
u_short aodv_rrep_ack_recv_count
 Number of RREP-ACK packets targeted for this node.
u_short aodv_rrep_ack_send_count
 Number of RREP-ACK packets sent from this node. (including failed).
u_short aodv_rrep_ack_send_fail_count
 Number of send failures of RREP-ACK packets.
u_short aodv_rrep_recv_count
 Number of RREP packets targeted for this node.(including failed).
u_short aodv_rrep_recv_fail_count
 Number of failed RREP packets passing through this node.
u_short aodv_rrep_send_count
 Number of RREP packets sent from this node. (including failed).
u_short aodv_rrep_send_fail_count
 Number of send failures of RREP packets.
u_short aodv_rreq_ignore_count
 Number of ignored RREQs (received twice or more).
u_short aodv_rreq_recv_count
 Number of RREQ packets targeted for this node. (including failed).
u_short aodv_rreq_recv_fail_count
 Number of failed RREQ packets passing through this node.
u_short aodv_rreq_send_count
 Number of RREQ packets sent from this node. (including failed).
u_short aodv_rreq_send_fail_count
 Number of send failures of RREQ packets.


Define Documentation

#define ACTIVE_ROUTE_TIMEOUT   10000

How long a unused route is considered active (in ms, paper: 3000ms)

#define ALLOWED_HELLO_LOSS   2

Number of HELLO messages that may be lost before route is deactivated.

#define BLACKLIST_SIZE   10

Number of nodes that can be blacklisted at the same time.

#define BLACKLIST_TIMEOUT   4 * (RREQ_RETRIES * (long)NET_TRAVERSAL_TIME)

How long nodes are kept on the blacklist. (in ms ) (RREQ_RETRIES * (long)NET_TRAVERSAL_TIME)

#define CONTROL_PACKET_QUEUE_SIZE   10

Size of the queues for control packets.

#define DELETE_PERIOD   (5 * MAX((long)ACTIVE_ROUTE_TIMEOUT, (long)HELLO_INTERVAL))

Time until an inactive route is deleted. (in ms)

#define DISCOVERY_BUFFER_SIZE   10

Size of the route discovery buffer. (Limits simultanious discoveries)

#define HELLO_INTERVAL   0

Intervall between HELLO messages (if there was no other message). Set to 0 to disable HELLO messages. (in ms, paper: 1000ms)

#define LOCAL_ADD_TTL   2

Accounts for local delays. (in ms)

#define MAX_REPAIR_TTL   12

Must be 0.3 * NET_DIAMETER.

Warning:
Set by hand to avoid floating point calculations. (in ms)

#define MY_ROUTE_TIMEOUT   (2 * ACTIVE_ROUTE_TIMEOUT)

How long this specific node consideres a route acitve.

#define NET_DIAMETER   15

Number of nodes on longest path in the network.

#define NET_TRAVERSAL_TIME   (2 * NODE_TRAVERSAL_TIME * NET_DIAMETER)

How long it takes a message to traverse the longest path in the network. (in ms)

#define NEXT_HOP_WAIT   (NODE_TRAVERSAL_TIME + 10)

How long the processing overhead of the next hop is expected. (in ms)

#define NODE_TRAVERSAL_TIME   200

Time that a packet need to traverse a node. This is calculated by by the average time a packet needs to be received, processed and sent. (in ms)

#define PATH_DISCOVERY_TIME   (2 * NET_TRAVERSAL_TIME)

Worst case thime for discovering a path between two nodes. (in ms)

#define RERR_RATELIMIT   10

Maximum number of RERRs that can be emitted dring an intervall.

#define RING_TRAVERSAL_TIME   (2 * NODE_TRAVERSAL_TIME * (TTL_VALUE + TIMEOUT_BUFFER))

Time that is needed to traverse the ring during expanding ring search. (in ms)

#define ROUTING_TABLE_SIZE   20

Size of the routing table. MUST not be biger than sizeof(char) - 1. (in hops).

#define RREP_BUFFER_SIZE   20

Size of the buffer for RREPs that must be ACKed.

#define RREP_RETRY   7

Defines how many times a RREP is resent in absence of RREP-ACKs.

#define RREQ_BUFFER_SIZE   50

Size of the buffer for RREQs.

#define RREQ_RATELIMIT   10

Limits the number of RREQs a node may emit dring an interval.

#define RREQ_RETRIES   7

Number of route requests sent until destination is accepted unreachable.

#define TIMEOUT_BUFFER   2

Adds a timeout to the RREP to count for congestion. (in ms)

#define TTL_INCREMENT   2

The increment of the ttl for the expanding ring search. (in hops)

#define TTL_START   1

The start value for the expanding ring search. (in hops)

#define TTL_THRESHOLD   7

Threshold of the ttl during expanding ring search. (in hops)

#define TTL_VALUE   2

ttl field in header during expanding ring search. (in hops)


Function Documentation

void aodv_enable_led ( int  enable_led  ) 

Enables LED status reporting.

Parameters:
enable_led [in] 0 to disable LED reporting, 1 to enable.

u_short aodv_get_address ( void   ) 

Returns the configured mac address.

Returns:
configured mac address.

int aodv_get_rreq_id ( void   ) 

Get the actual RREQ id of this node.

Returns:
AODV RREQ id.

int aodv_get_sequence_no ( void   ) 

Get the actual AODV sequence number of this node.

Returns:
AODV sequence number.

int aodv_init ( u_short  address  ) 

Initialises the AODV library.

Parameters:
address [in] mac address of the node.
Returns:
0 on success, -1 otherwise.

void aodv_print_rt ( void   ) 

Prints the routing table

Attention:
This command prints the routing table as it would be interpret at the very moment. The actual routing table entries may be different (for example the active flag still set). This is because the table is lazy-evaluated. Since this command should not change the state of the programm, it only displays the results correct, but does not alter routing table entries. Those are altered when the protokoll consults the routing table next times.

void aodv_print_rt_entry ( int  entry  ) 

Prints an entry of the routing table.

Attention:
This command prints the routing table as it would be interpret at the very moment. The actual routing table entries may be different (for example the active flag still set). This is because the table is lazy-evaluated. Since this command should not change the state of the programm, it only displays the results correct, but does not alter routing table entries. Those are altered when the protokoll consults the routing table next times.
Parameters:
entry [in] Entry that should be printed.

int aodv_route_discover ( u_short  dst  ) 

Starts a route discovery.

Parameters:
dest [in] Destination to which a route shall be built.
Returns:
0 if discovery started successfully.

u_short aodv_set_address ( u_short  addr  ) 

Sets the new node address.

Warning:
Reboot the node after setting the new address, since behaviour of the MAC protocol on mac change is undefined.
Parameters:
addr [in] packet length
Returns:
-1 if error


Variable Documentation

routing_interface_t aodv_interface

Routing Interface

routing_interface_t aodv_interface

Interface of the routing protocol.

Routing-Interface


Generated on Wed Apr 29 11:12:29 2009 for BTnut System Software by doxygen 1.5.1