jist.swans.route
Class RouteAodv

java.lang.Object
  jist.swans.route.RouteAodv

All Implemented Interfaces:

JistAPI.Proxiable, JistAPI.Timeless, Protocol, NetInterface.NetHandler, RouteInterface, RouteInterface.Aodv

public class RouteAodv
extends java.lang.Object
implements RouteInterface.Aodv

Ad-hoc On-demand Distance Vector (AODV) Routing Protocol Implementation.

Since:

SWANS1.0

Version:

$Id: RouteAodv.java,v 1.46 2004/04/06 16:07:50 barr Exp $

Author:

Clifton Lin, Rimon Barr <barr+jist@cs.cornell.edu>

Nested Class Summary

static class	RouteAodv.AodvPacketStats Packet stats.
static class	RouteAodv.AodvStats Data structure to collect AODV statistics.
private static class	RouteAodv.HelloMessage Represents a HELLO message.
private static class	RouteAodv.MessageQueue A MessageQueue object temporarily stores transport-layer messages while routes are being determined.
private static class	RouteAodv.OutgoingInfo Information for each node in the outgoing node set.
private static class	RouteAodv.OutgoingSet Represents the set of neighboring nodes through which this node routes messages.
private static class	RouteAodv.PrecursorInfo Information stored for each precursor node.
private static class	RouteAodv.PrecursorSet Represents the set of neighboring nodes which (likely) route through this node.
private static class	RouteAodv.RouteErrorMessage Represents a Route Error (RERR) message class.
private static class	RouteAodv.RouteReplyMessage Represents a Route Reply (RREP) message.
private static class	RouteAodv.RouteRequest Represents a request for a route by a node.
private static class	RouteAodv.RouteRequestMessage Represents a Route Request (RREQ) message.
private static class	RouteAodv.RouteTable A routing table contains a hash map, consisting of NetAddress->RouteTableEntry mappings.
private static class	RouteAodv.RouteTableEntry Information to be stored for each destination in routing table.
private static class	RouteAodv.RreqBuffer Buffer for keeping track of recently sent RREQ messages (so they are not resent).
private static class	RouteAodv.RreqBufferEntry A single entry of the RREQ Buffer.

Nested classes/interfaces inherited from interface jist.swans.route.RouteInterface

RouteInterface.Aodv, RouteInterface.Dsr, RouteInterface.Zrp

Field Summary

static long	AODV_TIMEOUT Period of time after which the AODV timeout event gets called.
static boolean	DEBUG_MODE debug mode.
static long	HELLO_ALLOWED_LOSS Number of timeout periods that must pass before this node can determine an outgoing link unreachable.
static long	HELLO_INTERVAL Duration of inactivity after which a HELLO message should be sent to a precursor.
static boolean	HELLO_MESSAGES_ON Hello Messages setting.
static int	MAX_RREQ_BUFFER_SIZE The maximum number of entries allowed in the RREQ buffer.
private RouteAodv.MessageQueue	msgQueue buffer for storing messages that need routes.
private NetAddress	netAddr local network address.
private NetInterface	netEntity Network entity.
private RouteAodv.OutgoingSet	outgoingSet set of nodes that this node routes through.
private RouteAodv.PrecursorSet	precursorSet set of nodes that route through this node.
private RouteAodv.RouteTable	routeTable routing table.
static long	RREQ_BUFFER_EXPIRE_TIME The maximum duration of time a RREQ buffer entry can remain in the RREQ buffer.
static int	RREQ_ID_SEQUENCE_NUMBER_START Starting value for RREQ ID sequence numbers.
static long	RREQ_TIMEOUT_BASE Constant term of the RREQ Timeout duration.
static long	RREQ_TIMEOUT_PER_TTL Variable term of the RREQ Timeout duration, dependant on the RREQ's TTL.
private RouteAodv.RreqBuffer	rreqBuffer buffer for storing info about previously sent RREQ messages.
private int	rreqIdSeqNum sequence number for RREQ id's.
private java.util.LinkedList	rreqList list of pending route requests (originated by this node).
private RouteInterface.Aodv	self Self-referencing proxy entity.
private int	seqNum node sequence number.
static int	SEQUENCE_NUMBER_START Starting value for node sequence numbers.
private RouteAodv.AodvStats	stats statistics accumulator.
static long	TRANSMISSION_JITTER The maximum amount of jitter before sending a packet.
static byte	TTL_INCREMENT The amount added to current TTL upon successive broadcasts of a RREQ message.
static byte	TTL_START The initial TTL value for any Route Request instance.
static byte	TTL_THRESHOLD The maximum TTL for any RREQ message.

Constructor Summary

RouteAodv(NetAddress addr)
Constructs new RouteAodv instance.

Method Summary

private long	computeRREQTimeout(byte ttl) Computes the RREQ Timeout period, given a TTL value.
private void	forwardRouteRequestMessage(RouteAodv.RouteRequestMessage rreqMsg, byte newTtl, RouteAodv.RouteTableEntry destRouteEntry) Forwards a RREQ message to all neighbors.
private void	generateRouteReplyMessage(RouteAodv.RouteRequestMessage rreqMsg, boolean isDest, RouteAodv.RouteTableEntry destRouteEntry) Generates and sends a RREP message.
NetAddress	getLocalAddr() Gets node's local address.
RouteInterface.Aodv	getProxy() Returns self-referencing proxy entity.
private void	helloSendEvent() Send hello messages to any precursors to which we have not sent a message in the past HELLO_INTERVAL time.
private void	helloWaitEvent() Increments the HELLO_wait counter for each outgoing node.
void	peek(NetMessage msg, MacAddress lastHop) Called by the network layer for every incoming packet.
private static void	printDebug_plain(java.lang.String s) Print given string only if debug mode on.
private void	printDebug(java.lang.String s) Print given string with JiST time and local net address, if debug mode on.
private static void	printDebug(java.lang.String s, NetAddress addr) Print given string with JiST time and given net address, if debug mode on.
private static void	printlnDebug_plain(java.lang.String s) Println given string only if debug mode on.
private void	printlnDebug(java.lang.String s) Println given string with JiST time and local net address, if debug mode on.
private static void	printlnDebug(java.lang.String s, NetAddress addr) Println given string with JiST time and given net address, if debug mode on.
void	printOutgoing() Prints the node's outgoing set.
void	printPrecursors() Prints the node's precusor set.
private static void	randomSleep(long time) Sleep for a random time.
void	receive(Message msg, NetAddress src, MacAddress lastHop, byte macId, NetAddress dst, byte priority, byte ttl) Receive a message from network layer.
private void	receiveHelloMessage(RouteAodv.HelloMessage helloMsg) Process an incoming HELLO message.
private void	receiveRouteErrorMessage(RouteAodv.RouteErrorMessage rerrMsg, MacAddress lastHop, byte ttl) Process an incoming RERR message.
private void	receiveRouteReplyMessage(RouteAodv.RouteReplyMessage rrepMsg, NetAddress src, MacAddress lastHop, NetAddress dst, byte priority, byte ttl) Process an incoming RREP message.
private void	receiveRouteRequestMessage(RouteAodv.RouteRequestMessage rreqMsg, NetAddress src, MacAddress lastHop, NetAddress dst, byte priority, byte ttl) Process an incoming RREQ message.
void	RREQtimeout(java.lang.Object rreqObj) This event is called periodically after a route request is originated, until a route has been found.
void	send(NetMessage msg) Called by the network layer to request transmission of a packet that requires routing.
void	sendIpMsg(NetMessage.Ip ipMsg, MacAddress destMacAddr) Sends IP message after transmission delay, and renews precursor list entry.
void	setNetEntity(NetInterface netEntity) Sets network entity.
void	setStats(RouteAodv.AodvStats stats) Sets aodv statistics object.
private boolean	shouldUpdateRouteToOrigin(RouteAodv.RouteRequestMessage rreqMsg, RouteAodv.RouteTableEntry origRouteEntry) Decides whether a node receiving a RREQ message should update its route to the RREQ originator.
void	start() Start running protocol.
void	timeout() AODV Timeout event, which gets called periodically at fixed intervals.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DEBUG_MODE

public static final boolean DEBUG_MODE

debug mode.

See Also:

Constant Field Values

HELLO_MESSAGES_ON

public static final boolean HELLO_MESSAGES_ON

Hello Messages setting. Should always be true, except possibly for debugging purposes.

See Also:

Constant Field Values

SEQUENCE_NUMBER_START

public static final int SEQUENCE_NUMBER_START

Starting value for node sequence numbers.

See Also:

Constant Field Values

RREQ_ID_SEQUENCE_NUMBER_START

public static final int RREQ_ID_SEQUENCE_NUMBER_START

Starting value for RREQ ID sequence numbers.

See Also:

Constant Field Values

RREQ_BUFFER_EXPIRE_TIME

public static final long RREQ_BUFFER_EXPIRE_TIME

The maximum duration of time a RREQ buffer entry can remain in the RREQ buffer.

See Also:

Constant Field Values

MAX_RREQ_BUFFER_SIZE

public static final int MAX_RREQ_BUFFER_SIZE

The maximum number of entries allowed in the RREQ buffer.

See Also:

Constant Field Values

AODV_TIMEOUT

public static final long AODV_TIMEOUT

Period of time after which the AODV timeout event gets called.

See Also:

Constant Field Values

HELLO_INTERVAL

public static final long HELLO_INTERVAL

Duration of inactivity after which a HELLO message should be sent to a precursor.

See Also:

Constant Field Values

HELLO_ALLOWED_LOSS

public static final long HELLO_ALLOWED_LOSS

Number of timeout periods that must pass before this node can determine an outgoing link unreachable.

See Also:

Constant Field Values

TTL_START

public static final byte TTL_START

The initial TTL value for any Route Request instance.

See Also:

Constant Field Values

TTL_INCREMENT

public static final byte TTL_INCREMENT

The amount added to current TTL upon successive broadcasts of a RREQ message.

See Also:

Constant Field Values

TTL_THRESHOLD

public static final byte TTL_THRESHOLD

The maximum TTL for any RREQ message.

See Also:

Constant Field Values

RREQ_TIMEOUT_BASE

public static final long RREQ_TIMEOUT_BASE

Constant term of the RREQ Timeout duration.

See Also:

Constant Field Values

RREQ_TIMEOUT_PER_TTL

public static final long RREQ_TIMEOUT_PER_TTL

Variable term of the RREQ Timeout duration, dependant on the RREQ's TTL.

See Also:

Constant Field Values

TRANSMISSION_JITTER

public static final long TRANSMISSION_JITTER

The maximum amount of jitter before sending a packet.

See Also:

Constant Field Values

netEntity

private NetInterface netEntity

Network entity.

self

private RouteInterface.Aodv self

Self-referencing proxy entity.

netAddr

private NetAddress netAddr

local network address.

seqNum

private int seqNum

node sequence number.

rreqIdSeqNum

private int rreqIdSeqNum

sequence number for RREQ id's.

routeTable

private RouteAodv.RouteTable routeTable

routing table.

rreqList

private java.util.LinkedList rreqList

list of pending route requests (originated by this node).

rreqBuffer

private RouteAodv.RreqBuffer rreqBuffer

buffer for storing info about previously sent RREQ messages.

msgQueue

private RouteAodv.MessageQueue msgQueue

buffer for storing messages that need routes.

precursorSet

private RouteAodv.PrecursorSet precursorSet

set of nodes that route through this node.

outgoingSet

private RouteAodv.OutgoingSet outgoingSet

set of nodes that this node routes through.

stats

private RouteAodv.AodvStats stats

statistics accumulator.

Constructor Detail

RouteAodv

public RouteAodv(NetAddress addr)

Constructs new RouteAodv instance.

Parameters:

addr - node's network address

Method Detail

RREQtimeout

public void RREQtimeout(java.lang.Object rreqObj)

This event is called periodically after a route request is originated, until a route has been found. Each time it is called, it rebroadcasts the route request message with a new rreq id and incremented TTL.

Specified by:

RREQtimeout in interface RouteInterface.Aodv

Parameters:

rreqObj - RouteRequest object

timeout

public void timeout()

AODV Timeout event, which gets called periodically at fixed intervals. Clears expired RREQ buffer entries. Sends hello messages. Updates wait counters, and checks for idle outgoing-nodes

Specified by:

timeout in interface RouteInterface.Aodv

helloSendEvent

private void helloSendEvent()

Send hello messages to any precursors to which we have not sent a message in the past HELLO_INTERVAL time.

helloWaitEvent

private void helloWaitEvent()

Increments the HELLO_wait counter for each outgoing node. If this event gets called more than HELLO_ALLOWED_LOSS times without us having heard a message from some outgoing node, then we can assume that outgoing node is no longer reachable, and we update our data structures accordingly, and send out RERR messages to our precursors.

sendIpMsg

public void sendIpMsg(NetMessage.Ip ipMsg,
                      MacAddress destMacAddr)

Sends IP message after transmission delay, and renews precursor list entry.

Specified by:

sendIpMsg in interface RouteInterface.Aodv

Parameters:

ipMsg - IP message to send

destMacAddr - next hop mac address

start

public void start()

Start running protocol.

Specified by:

start in interface Protocol

peek

public void peek(NetMessage msg,
                 MacAddress lastHop)

Called by the network layer for every incoming packet. A routing implementation may wish to look at these packets for informational purposes, but should not change their contents.

Specified by:

peek in interface RouteInterface

Parameters:

msg - incoming packet

lastHop - last link-level hop of incoming packet

send

public void send(NetMessage msg)

Called by the network layer to request transmission of a packet that requires routing. It is the responsibility of the routing layer to provide a best-effort transmission of this packet to an appropriate next hop by calling the network slayer sending routines once this routing information becomes available.

Specified by:

send in interface RouteInterface

Parameters:

msg - outgoing packet

receive

public void receive(Message msg,
                    NetAddress src,
                    MacAddress lastHop,
                    byte macId,
                    NetAddress dst,
                    byte priority,
                    byte ttl)

Receive a message from network layer.

Specified by:

receive in interface NetInterface.NetHandler

Parameters:

msg - message received

src - source network address

lastHop - source link address

macId - mac identifier

dst - destination network address

priority - packet priority

ttl - packet time-to-live

receiveRouteRequestMessage

private void receiveRouteRequestMessage(RouteAodv.RouteRequestMessage rreqMsg,
                                        NetAddress src,
                                        MacAddress lastHop,
                                        NetAddress dst,
                                        byte priority,
                                        byte ttl)

Process an incoming RREQ message.

Parameters:

rreqMsg - incoming route request message

src - source of message

lastHop - last hop of message

dst - destination of message

priority - message priority

ttl - message TTL

receiveRouteReplyMessage

private void receiveRouteReplyMessage(RouteAodv.RouteReplyMessage rrepMsg,
                                      NetAddress src,
                                      MacAddress lastHop,
                                      NetAddress dst,
                                      byte priority,
                                      byte ttl)

Process an incoming RREP message.

Parameters:

rrepMsg - incoming route reply message

src - source of message

lastHop - last hop of message

dst - destination of message

priority - message priority

ttl - message TTL value

receiveRouteErrorMessage

private void receiveRouteErrorMessage(RouteAodv.RouteErrorMessage rerrMsg,
                                      MacAddress lastHop,
                                      byte ttl)

Process an incoming RERR message.

Parameters:

rerrMsg - incoming route error message

lastHop - last hop of message

ttl - message TTL value

receiveHelloMessage

private void receiveHelloMessage(RouteAodv.HelloMessage helloMsg)

Process an incoming HELLO message.

Parameters:

helloMsg - incoming hello message

forwardRouteRequestMessage

private void forwardRouteRequestMessage(RouteAodv.RouteRequestMessage rreqMsg,
                                        byte newTtl,
                                        RouteAodv.RouteTableEntry destRouteEntry)

Forwards a RREQ message to all neighbors.

Parameters:

rreqMsg - incoming route request message

newTtl - TTL value for the (new) RREQ message to be forwarded

destRouteEntry - route table entry for destination node

generateRouteReplyMessage

private void generateRouteReplyMessage(RouteAodv.RouteRequestMessage rreqMsg,
                                       boolean isDest,
                                       RouteAodv.RouteTableEntry destRouteEntry)

Generates and sends a RREP message.

Parameters:

rreqMsg - RREQ message that this RREP message is responding to

isDest - true if this node is the destination of the RREQ message

destRouteEntry - route table entry for the destination node, if this is not dest. (otherwise, null)

shouldUpdateRouteToOrigin

private boolean shouldUpdateRouteToOrigin(RouteAodv.RouteRequestMessage rreqMsg,
                                          RouteAodv.RouteTableEntry origRouteEntry)

Decides whether a node receiving a RREQ message should update its route to the RREQ originator.

Parameters:

rreqMsg - incoming route request message

origRouteEntry - existing routing table entry for the RREQ-originating node

Returns:

true, if node should update its routing table entry to RREQ-originating node

computeRREQTimeout

private long computeRREQTimeout(byte ttl)

Computes the RREQ Timeout period, given a TTL value.

Parameters:

ttl - TTL value

Returns:

timeout period

randomSleep

private static void randomSleep(long time)

Sleep for a random time.

Parameters:

time - max sleep time

setStats

public void setStats(RouteAodv.AodvStats stats)

Sets aodv statistics object.

Parameters:

stats - aodv statistics object

getLocalAddr

public NetAddress getLocalAddr()

Gets node's local address.

Returns:

local address

getProxy

public RouteInterface.Aodv getProxy()

Returns self-referencing proxy entity.

Returns:

self-referencing proxy entity

setNetEntity

public void setNetEntity(NetInterface netEntity)

Sets network entity.

Parameters:

netEntity - network entity

printlnDebug

private void printlnDebug(java.lang.String s)

Println given string with JiST time and local net address, if debug mode on.

Parameters:

s - string to print

printDebug

private void printDebug(java.lang.String s)

Print given string with JiST time and local net address, if debug mode on.

Parameters:

s - string to print

printlnDebug

private static void printlnDebug(java.lang.String s,
                                 NetAddress addr)

Println given string with JiST time and given net address, if debug mode on.

Parameters:

s - string to print

addr - node address

printDebug

private static void printDebug(java.lang.String s,
                               NetAddress addr)

Print given string with JiST time and given net address, if debug mode on.

Parameters:

s - string to print

addr - node address

printlnDebug_plain

private static void printlnDebug_plain(java.lang.String s)

Println given string only if debug mode on.

Parameters:

s - string to print

printDebug_plain

private static void printDebug_plain(java.lang.String s)

Print given string only if debug mode on.

Parameters:

s - string to print

printPrecursors

public void printPrecursors()

Prints the node's precusor set.

printOutgoing

public void printOutgoing()

Prints the node's outgoing set.