Implementation of a Distributed Token Circulation Algorithm Under ns-2

Introduction to Token Circulation Algorithms.

These algorithms cause a token to continually circulate through all the nodes of a mobile ad hoc network. An important application of such algorithms is to ensure total order of message delivery in a group communication service. Some of the proposed algorithms are aware of, and adapt to changes in, the ad hoc network topology. When using a token circulation algorithm, a round is said to complete when every node has been visited at least once. Criteria for comparing the algorithms include the average time required to complete a round, number of bytes sent per round, and a number of nodes visited per round.

The following are the some of the examples of token circulation algorithms:

• Algorithm Local-Frequency (LF)
• Algorithm Local-Recency (LR)
• Global Algorithms
• Global Algorithms with Next and
• Algorithm Iterative Search (IS).

 

Algorithm Local-Frequency (LF)

The Local-Frequency (LF) algorithm keeps track of how many times each node has been visited and sends the token to the least frequently visited neighbor of the token-holder. To implement this algorithm, the count, for each node, as stored in the token, contains the number of past token visits to that node.

Algorithm Local-Recency (LR)

The Local-Recency (LR) algorithm is similar to LF, except that the least recently visited neighbor of the token-holder is chosen as the next recipient of the token. To implement this algorithm, the count for each node, as stored in the token, contains the “time” (as defined earlier) when the node was last visited by the token.

Global Algorithms

In these algorithms, the token is sent to the node that has been recently visited the least (in algorithm GR) or least frequently (in algorithm GF) among all the nodes in the system, not just among the token-holder’s neighbors.

Global Algorithms with Next

These algorithms first determine the node with the smallest count value from among all nodes in the network. Recall that the counts are included in the token. Then, the token is sent to the neighbor of the token-holder on the route to the node with the smallest count. These algorithms require the ability to query the network layer to determine the neighbor on the route to a given destination.

Algorithm Iterative Search (IS)

These are Iterative Search Algorithms that tries to learn from the past to improve future performance of the algorithm. Such algorithms can improve performance when the time spent by the network in a given topology increases. The algorithm tries to find a Hamiltonian path in the network if there exists one.

About this Project

The primary goal of this project is to study the existing algorithms available for token circulation in Mobile ad-hock Network and to implement a simple model for token circulation algorithm under ns2. The project work plan is given below. The proposed algorithm will be implemented using C and tcl on ns2. After the successful simulation, suitable trace files will be used for measuring various performances. The trace files will be filtered and analyzed by using suitable perl scripts or grep utility to find the performance. Finally, based on the information gathered from the trace files, various graphs will be prepared for visualizing the performance of the proposed algorithm.

The following are the performance measures that will apply to these algorithms:

• Round length. The length of a round is the number of node visits made by the token in one round. Note that, in general, a given node may be visited multiple times in a round.
• Message overhead, measured as number of bytes sent per round. This overhead measures the overhead due to all packets transmitted to complete one round. If the packet takes multiple hops to reach a destination, the bytes required to transmit the packet on each hop are counted. If any packet is lost and needs to be retransmitted, the retransmissions are counted as well. Similarly, the overhead of sending control packets in the medium access control protocol is also included in the message overhead.
• Time overhead, measured as time required to complete a round. The time required to complete a round is the duration of time from when the last node in the previous round is visited until when the last node in the current round is visited.

 

Token Passing Agent C++ Code in ns-2

static class TokenPassingAgentClass : public TclClass {
public:
 TokenPassingAgentClass() : TclClass("Agent/TokenPassing") {}
 TclObject* create(int, const char*const*) {
 return (new TokenPassingAgent());
 }
} class_message_passing_agent;

TokenPassingAgent::TokenPassingAgent() : Agent(PT_MESSAGE), seqno_(-1)
{
 bind("packetSize_", &size_);
}

TokenPassingAgent::TokenPassingAgent(packet_t type) : Agent(type)
{
 bind("packetSize_", &size_);
}

void TokenPassingAgent::sendmsg(int nbytes, AppData* data, const char* flags)
{
 Packet *p;

 if (nbytes == -1) {
 printf("Error: sendmsg() for TokenPassingAgent should not be -1\n");
 return;
 } 

 // check packet size (we don't fragment packets)
 if (nbytes > size_) {
 printf("Error: packet greater than maximum TokenPassingAgent packet size\n");
 return;
 }

 double local_time = Scheduler::instance().clock();
 p = allocpkt();
 hdr_cmn::access(p)->size() = nbytes;
 hdr_rtp* rh = hdr_rtp::access(p);
 rh->flags() = 0;
 rh->seqno() = ++seqno_;
 hdr_cmn::access(p)->timestamp() = 
 (u_int32_t)(SAMPLERATE*local_time);
 p->setdata(data);
 target_->recv(p);
 idle();
}


void TokenPassingAgent::sendto(int nbytes, AppData *data, const char* flags, ns_addr_t dst)
{
 Packet *p;

 if (nbytes == -1) {
 printf("Error: packet size for TokenPassingAgent should not be -1\n");
 return;
 } 

 // check packet size (we don't fragment packets)
 if (nbytes > size_) {
 printf("Error: packet greater than maximum TokenPassingAgent packet size\n");
 return;
 }

 double local_time = Scheduler::instance().clock();
 p = allocpkt();
 hdr_ip* iph = hdr_ip::access(p);
 iph->daddr() = dst.addr_;
 iph->dport() = dst.port_;
 hdr_cmn::access(p)->size() = nbytes;
 hdr_rtp* rh = hdr_rtp::access(p);
 rh->flags() = 0;
 rh->seqno() = ++seqno_;
 hdr_cmn::access(p)->timestamp() = 
 (u_int32_t)(SAMPLERATE*local_time);
 p->setdata(data);
 target_->recv(p);
 idle();
}

void TokenPassingAgent::FillNeighborList()
{
 Tcl& tcl = Tcl::instance();

 int TotalNodes=God::instance()->nodes();

 for(int i=0;iIsNeighbor(i , here_.addr_))
 {
 tcl.evalf("%s AddNeighborToList %d ",name(), i);
 }
 }
}

void TokenPassingAgent::sendtoAllNeighbors(int nbytes, AppData *data, int toport)
{


 if (nbytes == -1) {
 printf("Error: packet size for TokenPassingAgent should not be -1\n");
 return;
 } 

 // check packet size (we don't fragment packets)
 if (nbytes > size_) {
 printf("Error: packet greater than maximum TokenPassingAgent packet size\n");
 return;
 }

 double local_time = Scheduler::instance().clock();

 Packet *p ;
 p = allocpkt();
 hdr_ip* iph = hdr_ip::access(p);
 
 iph->dport() = toport;
 hdr_cmn::access(p)->size() = nbytes;
 hdr_rtp* rh = hdr_rtp::access(p);
 rh->flags() = 0;
 rh->seqno() = ++seqno_;
 hdr_cmn::access(p)->timestamp() = 
 (u_int32_t)(SAMPLERATE*local_time);
 p->setdata(data);
 //iph->daddr() = dst.port_;//IP_BROADCAST; //i;
 

 int TotalNodes=God::instance()->nodes();
// printf("\nTotalNodes = %d",TotalNodes);

 for(int i=0;iIsNeighbor(i , here_.addr_))
 {
// printf("\nNeighbor of %d is %d", dst.addr_,i);
 iph->daddr() = i;
 target_->recv(p->copy());
 idle();
 }
 }
Packet::free(p);
}


void TokenPassingAgent::sendtoNode(int nbytes, AppData *data, ns_addr_t dst,int ttl)
{


 if (nbytes == -1) {
 printf("Error: packet size for TokenPassingAgent should not be -1\n");
 return;
 } 

 // check packet size (we don't fragment packets)
 if (nbytes > size_) {
 printf("Error: packet greater than maximum TokenPassingAgent packet size\n");
 return;
 }
 double local_time = Scheduler::instance().clock();
 Packet *p ;
 p = allocpkt();
 hdr_ip* iph = hdr_ip::access(p);
 iph->daddr() = dst.addr_;
 iph->dport() = dst.port_;
 iph->ttl() = ttl; 
 hdr_cmn::access(p)->size() = nbytes;
 hdr_rtp* rh = hdr_rtp::access(p);
 rh->flags() = 0;
 rh->seqno() = ++seqno_;
 hdr_cmn::access(p)->timestamp() = 
 (u_int32_t)(SAMPLERATE*local_time);
 p->setdata(data);
 target_->recv(p);
 idle();
}

void TokenPassingAgent::recv(Packet* pkt, Handler*)
{
 if (app_ ) {
 // If an application is attached, pass the data to the app
 hdr_cmn* h = hdr_cmn::access(pkt);
 app_->process_data(h->size(), pkt->userdata());
 } else if (pkt->userdata() && pkt->userdata()->type() == PACKET_DATA) {
 // otherwise if it's just PacketData, pass it to Tcl

 PacketData* data = (PacketData*)pkt->userdata();

 hdr_ip* iph = hdr_ip::access(pkt);
 Tcl& tcl = Tcl::instance();
 tcl.evalf("%s recv %d %d %d {%s}", name(),
 iph->saddr(), iph->sport(),
 hdr_cmn::access(pkt)->size(), data->data());
 } else {
 // It wasn't PacketData, or userdata() was NULL
 // so pass an empty string to Tcl


 hdr_ip* iph = hdr_ip::access(pkt);
 Tcl& tcl = Tcl::instance();
 tcl.evalf("%s recv %d %d %d {}", name(),
 iph->saddr(), iph->sport(),
 hdr_cmn::access(pkt)->size());
 
 }
 Packet::free(pkt);
}


int TokenPassingAgent::command(int argc, const char*const* argv)
{
 PacketData* data;
 ns_addr_t dst;
 if (strcmp(argv[1], "set-ll") == 0) {
 if( ( ll = (NsObject*) TclObject::lookup(argv[2])) == 0) {
 fprintf(stderr, "Agent(set-ll): %s lookup of %s failed\n", argv[1], argv[2]);
 return (TCL_ERROR);
 }
 return (TCL_OK);
 }else if (argc == 2) {
 if (strcmp(argv[1], "FillNeighborList") == 0) {
 FillNeighborList();
 return TCL_OK;
 }
 }else if (argc == 4) {
 if (strcmp(argv[1], "send") == 0) {
 data = new PacketData(1 + strlen(argv[3]));
 strcpy((char*)data->data(), argv[3]);
 sendmsg(atoi(argv[2]), data);
 return TCL_OK;
 }
 } else if (argc == 5) {
 if (strcmp(argv[1], "sendmsg") == 0) {
 data = new PacketData(1 + strlen(argv[3]));
 strcpy((char*)data->data(), argv[3]);
 sendmsg(atoi(argv[2]), data, argv[4]);
 return TCL_OK;
 } else if (strcmp(argv[1], "sendto") == 0) {
 dst.addr_ = atoi(argv[3]);
 dst.port_ = atoi(argv[4]);
 if (dst.port_ == 0) dst.port_ = here_.port_;
 sendto(atoi(argv[2]), 0, dst);
 return TCL_OK;
 }else if (strcmp(argv[1], "sendtoAllNeighbors") == 0) {
 data = new PacketData(1 + strlen(argv[3]));
 strcpy((char*)data->data(), argv[3]);
 sendtoAllNeighbors(atoi(argv[2]), data, atoi(argv[4]));
 return TCL_OK;
 }
 } else if (argc == 6) {
 if (strcmp(argv[1], "sendto") == 0) {
 data = new PacketData(1 + strlen(argv[3]));
 strcpy((char*)data->data(), argv[3]);
 dst.addr_ = atoi(argv[4]);
 dst.port_ = atoi(argv[5]);
 if (dst.port_ == 0) dst.port_ = here_.port_;
 sendto(atoi(argv[2]), data, 0, dst);
 return TCL_OK;
 } else if (strcmp(argv[1], "sendmsgto") == 0) {
 dst.addr_ = atoi(argv[3]);
 dst.port_ = atoi(argv[4]);
 if (dst.port_ == 0) dst.port_ = here_.port_;
 sendto(atoi(argv[2]), argv[5], dst);
 return TCL_OK;
 } 
 } else if (argc == 7) {
 if (strcmp(argv[1], "sendmsgto") == 0) {
 data = new PacketData(1 + strlen(argv[3]));
 strcpy((char*)data->data(), argv[3]);
 dst.addr_ = atoi(argv[4]);
 dst.port_ = atoi(argv[5]);
 if (dst.port_ == 0) dst.port_ = here_.port_;
 sendto(atoi(argv[2]), argv[6], dst);
 return TCL_OK;
 }else if (strcmp(argv[1], "sendtoNode") == 0) {
 dst.addr_ = atoi(argv[4]);
 dst.port_ = atoi(argv[5]);
 int ttl = atoi(argv[6]);
 data = new PacketData(1 + strlen(argv[3]));
 strcpy((char*)data->data(), argv[3]);
 sendtoNode(atoi(argv[2]), data, dst,ttl);
 return TCL_OK;
 }
 }
 return (Agent::command(argc, argv));
}

 

 

The Important Part of  ns-2 Simulation Code

The following code segment of the main simulation script shows the way in wich the C++ TokenPass Agent code is used under tcl simulation script. 

Class Agent/TokenPassing/TokenPass -superclass Agent/TokenPassing

Agent/TokenPassing/TokenPass instproc PassToken {size token} {
$self instvar NeighborList_ node_
global ns node MESSAGE_PORT NodeDim TokenPassDelay Initiator a roundtripfd PrevTime NRound StartTime FinishTime
set NeighborList_ ""
$self FillNeighborList


set addr [$node_ set address_]
set TokenID [lindex [split $token "#"] 0 ]
set VisitedList [lindex [split $token "#"] 1 ]

if { [lsearch $VisitedList $addr] == -1 } {
 lappend VisitedList $addr
}

set NotVisitedList [lindex [split $token "#"] 2 ]

#add not visited neighbors to notvisited list
foreach x [lsort $NeighborList_] {
 if { [lsearch $VisitedList $x] == -1 } {
 if { [lsearch $NotVisitedList $x] == -1 } {
 lappend NotVisitedList $x 
 }
 }
} 

set NextHop [lindex $NotVisitedList 0]

#puts "tokenid : $TokenID"
puts "visited : $VisitedList"
puts "notvisited : $NotVisitedList"
puts "nexthop : $NextHop"


set len [llength $NotVisitedList ]
if { $len ==0 } {
 puts "finished a trip"
 set VisitedList {}
 for {set i 0} {$i < [expr $NodeDim * $NodeDim] } {incr i} {
 $node($i) color black
 }
 
 $ns at [expr [$ns now]+.1] "$self PassToken $size {$TokenID#$VisitedList#$NotVisitedList}"
 $node_ color green

 
 set Rtime [expr [$ns now] - $PrevTime] 
 set PrevTime [expr [$ns now]] 
 set NRound [expr $NRound + 1]
 if {$NRound <2} { 
 set StartTime [expr [$ns now]] 
 }
 if {$NRound >1} { #Do not record the time taken for first round
 puts $roundtripfd "$NRound $Rtime" 
 set FinishTime [expr [$ns now]] 
 }
 
} else {
$self sendtoNode size "$TokenID#$VisitedList#$NotVisitedList" $NextHop $MESSAGE_PORT 1
}
puts "node $addr Passed Token to $NextHop"
puts ""
}

Agent/TokenPassing/TokenPass instproc recv {source sport size token} {
$self instvar messages_seen NeighborList_ node_
global ns MESSAGE_PORT TokenPassDelay


$node_ color green

set addr [$node_ set address_]
puts "node $addr Recieved Token"

set TokenID [lindex [split $token "#"] 0 ]
set VisitedList [lindex [split $token "#"] 1 ]
set NotVisitedList [lindex [split $token "#"] 2 ]

#remove visited from notvisited list
set idx [lindex [lsearch $NotVisitedList $addr] 0]
set NotVisitedList [lreplace $NotVisitedList $idx $idx ]

$ns at [expr [$ns now]+ $TokenPassDelay ] "$self PassToken $size {$TokenID#$VisitedList#$NotVisitedList}"

}

Agent/TokenPassing/TokenPass instproc AddNeighborToList {nn} {
$self instvar NeighborList_ 
lappend NeighborList_ $nn
}

 

 

Name output of a 25 node Scenario

 

 

The Send and Receive Logs of nodes – Displayed in the Terminal Window

running nam...
num_nodes is set 25
channel.cc:sendUp - Calc highestAntennaZ_ and distCST_
highestAntennaZ_ = 1.5, distCST_ = 846.9

passed token
visited : 0
notvisited : 1 5
nexthop : 1

passed token
recieved token
visited : 0 1
notvisited : 5 2 6
nexthop : 5

passed token
recieved token
visited : 0 1 5
notvisited : 2 6 10
nexthop : 2

passed token
recieved token
visited : 0 1 5 2
notvisited : 6 10 3 7
nexthop : 6

passed token
recieved token
visited : 0 1 5 2 6
notvisited : 10 3 7 11
nexthop : 10

passed token
recieved token
visited : 0 1 5 2 6 10
notvisited : 3 7 11 15
nexthop : 3

passed token
recieved token
visited : 0 1 5 2 6 10 3
notvisited : 7 11 15 4 8
nexthop : 7

………………
………………
The Total Number of Nodes in the Network = 25
The Node Speed = 5 meters/second
The Tatal Time Taken for 7 Rounds = 15.62 Seconds
The Tatal Number of Rounds = 7
The Average Time Taken for a Round = 2.23 Seconds

 

Rounds vs Roundtrip Time Graph

 

 

Conclusion

In this work, a simple model for simulating a token passing algorithm under ns-2  has been presented. One can develop their own token circulation algorithms by using some of the ideas handled in this project. In this work, we derived nighbor information from GOD  of ns-2 (global object Director). But one may derive the same from AODV routing layer by enabling hello mechanism of AODV.