Protocol implementation - npapanik/Adyton GitHub Wiki

##Introduction

Each routing protocol in Adyton consists of two files (.h, .cc) located in src/routing. The first thing when implementing a new routing protocol is to create these files. Every protocol corresponds to a class that inherits the Routing class (/src/routing/Routing.h, /src/routing/Routing.cc). The header file contains the class declaration, while the .cc file contains the source code that implements all protocol's functions.

Protocol functions are responsible for handling both incoming and outgoing packets to/from a node. The following methods are fundamental and each protocol should implement them. Most of listed methods are inherited from the Routing class and can be either virtual or not.

void NewContact(double CTime, int NID)

Called when the node comes in contact with another network node. The arguments include the current simulation time (CTime) and the ID of the node in contact (NID). In fact, this is the initialization point of each contact.

void Contact(double CTime, int NID)

Called when the node comes in contact with another node. However, it differs from NewContact() on the contact type. More specifically, in this case, the contact is not a new one in the sense that there was a previous contact between the same nodes which has not been terminated yet. This method is required as many trace files contain multiple contacts between the same pair of nodes that have time overlaps. We have tried to eliminate these overlaps during trace processing. However, some exceptions do exist. Again, the same arguments as in NewContact() are provided.

Note 1: In most protocols, NewContact() and Contact() have the same functionality. Usually, NewContact() just calls Contact() or vice versa.

Note 2: Adyton assumes that all contacts loaded from the real world trace are bidirectional. As a result, for each contact between nodes A and B in the trace file the following methods are triggered.

  1. First, NewContact() at node A
  2. Then, after ContactRemoved() is executed at node A, NewContact() is triggered at node B

Note 3: Usually, when a contact with another node is detected, the node triggers the deletion mechanism. Then, the node attempts to send all packets that are destined to the node in contact. For the latter case, already implemented methods exist inside the Routing class, e.g., SendDirectSummary() and SendDirectPackets().

void ContactRemoved(double CTime, int NID)

Called when the contact between two nodes is terminated. The simulation time (CTime) and the ID of the node in contact compose the method's arguments (NID).

void AfterDirectTransfers(double CTime, int NID)

Called after the transfer of direct packets (triggered by Contact() method) completes. In cases that Contact() never initiates the transfer of direct packets this method will never be executed. However, most protocols in Adyton implement this method.

void recv(double rTime, int pktID)

Handles the incoming packets received by the node. Packets can be of multiple types, so usually this method detects the packet type and calls the corresponding method to handle them. In the current implementation, the recv() method should also handle some specific packet types required by the deletion mechanism and transfer of direct packets. This is achieved using the following code.

void NewRoutingProtocol::recv(double rTime, int pktID)
{
	int PacketID;
	Packet *p;
	Header *h;
	// sanity check
	if((p = pktPool->GetPacket(pktID)) == NULL)
	{
		printf("Error: Packet %d doesn't exist in Packet Pool!\nAborting...\n",pktID);
		exit(1);
	}
	// get header and packet ID 
	h = p->getHeader();
	if(h->IsDuplicate() == true)
	{
		PacketID = h->GetOriginal();
	}
	else
	{
		PacketID = pktID;
	}
	// sanity check
	if(rTime < 0 || p->GetStartTime() < 0)
	{
		printf("%f: Node %d received new packet with ID %d and type %d from %d\n", rTime, this->NodeID, p->getID(), p->getType(), h->GetprevHop());
		exit(1);
	}
	
	// Identify the type of the packet
	switch(p->getType())
	{
		case DATA_PACKET:
		{
			ReceptionData(h, p, pktID, rTime, PacketID);
			break;
		}
		case DIRECT_SUMMARY_PACKET:
		{
			ReceptionDirectSummary(h,p,pktID,rTime);
			break;
		}
		case DIRECT_REQUEST_PACKET:
		{
			ReceptionDirectRequest(h,p,pktID,rTime);
			break;
		}
		case ANTIPACKET:
		{
			ReceptionAntipacket(h,p,pktID,rTime);
			break;
		}
		case ANTIPACKET_RESPONSE:
		{
			ReceptionAntipacketResponse(h,p,pktID,rTime);
			break;
		}
		default:
		{
			printf("Error: Unknown packet type! New Routing Protocol is not using this type of packet!\nAborting...\n");
			exit(1);
		}
	}
	return;
}

The code above calls a different method depending on the packet type. Most of these methods have been already implemented inside the Routing class (src/routing/Routing.cc). The only exception stands for ReceptionData() which handles the data packets and should be implemented by the new protocol.

Adyton supports a plethora of packet types defined in src/core/Packet.cc. A new protocol can directly use any subset of them as well as define new ones.

void ReceptionData(Header* hd, Packet* pkt, int PID, double CurrentTime, int RealID)

Handles the reception of data packets. In most cases, the functionality of ReceptionData() includes storing incoming data packets and updating the simulation statistics. An incoming data packet can also come from the application layer of the node meaning that it has just been created. To distinguish this kind of packets the following convention is used. The packet's source node is set to current node's ID, while the previous hop node field is set to -1.

void SendPacket(double STime, int pktID, int nHop, int RepValue)

Sends packets to other network nodes. To accomplish this task it interacts with other components of Adyton, such as Packet Pool, MAC layer etc.

##Implementing the RND Routing protocol (step-by-step example)

In the following, we present a step-by-step example displaying the implementation of a rather simple protocol, called RND Routing. According to this protocol, the meeting nodes exchange their packets based on a predefined probability as depicted in the following diagram ([pdf version].

(https://raw.githubusercontent.com/wiki/npapanik/Adyton/pdf/RND.pdf)).

Diagram was generated using js-sequence-diagrams.

Creating "RND_Routing.h"

First, the header file for the new protocol should be created containing the class declaration. Note that, the new class (RND_Routing) inherits the Routing class.

#include <stdio.h>
#include <stdlib.h>

#ifndef ROUTING_H
	#define ROUTING_H
	#include "Routing.h"
#endif


class RND_Routing:public Routing
{
public:
	RND_Routing(PacketPool* PP, MAC* mc, PacketBuffer* Bf, int NID, Statistics *St, Settings *S, God *G);
	~RND_Routing();
	virtual void ContactRemoved(double CTime, int NID);
	virtual void Contact(double CTime, int NID);
	virtual void NewContact(double CTime, int NID);
	virtual void recv(double rTime, int pktID);
protected:
	virtual void AfterDirectTransfers(double CTime,int NID);
	virtual void SendPacket(double STime,int pktID,int nHop, int RepValue);
private:
	void ReceptionData(Header *hd, Packet *pkt, int PID, double CurrentTime, int RealID);
};

You can directly download the source file here.

Creating "RND_Routing.cc"

After creating RND_Routing.cc, we add the constructor/destructor of our new class. Due to RND's simplicity, we only need to initialize the rand() function.

#ifndef RND_ROUTING_H
	#define RND_ROUTING_H
	#include "RND_Routing.h"
#endif


RND_Routing::RND_Routing(PacketPool* PP, MAC* mc, PacketBuffer* Bf, int NID, Statistics* St, Settings* S, God* G) : Routing(PP, mc, Bf, NID, St, S, G)
{
	// initialize random seed
	srand (time(NULL));
	return;
}

RND_Routing::~RND_Routing()
{
	return;
}

When detecting a new contact (either new or one with an existing node in contact) the proper methods for deletion mechanisms are called. Furthermore, the transfer of packets for direct delivery (node in contact is the destination for some packets) is scheduled. After the execution of these methods AfterDirectTransfers() will be called.

void RND_Routing::NewContact(double CTime, int NID)
{
	//just call Contact() - do not differentiate new from existing contacts 
	Contact(CTime, NID);
	return;
}

void RND_Routing::Contact(double CTime, int NID)
{
	// Apply Deletion Method operations first if needed
	int *Information=DM->GetInfo();
	if(Information != NULL)
	{
		//Create a vaccine information packet
		SendVaccine(CTime,NID,Information);
	}
	else
	{
		// If there are packets destined to node in contact try to send them 
		// Note: How this operation will be executed depends on the deletion method 
		
		//Clean buffer using Deletion method (Delivered pkts)
		DM->CleanBuffer(this->Buf);
		if(DM->ExchangeDirectSummary())
		{
			SendDirectSummary(CTime,NID);
		}
		else
		{
			SendDirectPackets(CTime,NID);
		}
	}
	return;
}

Since, the RND protocol is single-copy no deletion mechanism is needed. As a result Contact() can be simplified into the following.

void RND_Routing::Contact(double CTime, int NID)
{
	SendDirectPackets(CTime,NID);
	return;
}

No functionality is required when a contact terminates.

void RND_Routing::ContactRemoved(double CTime, int NID)
{
	return;
}

The protocol's core functionality is implemented in AfterDirectTransfers(). At this point, the deletion mechanism information has been updated successfully and the transfer of direct packets has been completed. Initially, the node gets all packets that reside in its buffer and are not destined to the node in contact. Then, each packet is probabilistically added in the scheduler for transmission. More specifically, a packet is considered for transmission with probability equal to 40%. After scheduling is applied the chosen packets are transmitted to the node in contact using SendPacket() and deleted from the buffer of the current node.

void RND_Routing::AfterDirectTransfers(double CTime, int NID)
{
	int i=0;
	int *pkts=NULL;
	double r=0.0;
	// get all packets inside my buffer that are not destined to node in contact
	pkts = Buf->getPacketsNotDestinedTo(NID);
	for(i = 1; i <= pkts[0]; i++)
	{
		//Add packets to scheduler
		r = (double) rand() / RAND_MAX;
		if (r > 0.6 && Buf->GetPrev(pkts[i]) != NID)
		{
			sch->addPacket(pkts[i],NULL);
		}
	}
	free(pkts);
	//Apply scheduling
 	int *outgoing=sch->getOutgoingPackets();
	//Send Packets
	if(outgoing)
	{
		for(int i=1;i<=outgoing[0];i++)
		{
 			//printf("node %d: Sending packet %d to node %d\n",NodeID ,outgoing[i],NID);
			SendPacket(CTime,outgoing[i],NID,1);
			// Remove the packet from the buffer
			Buf->removePkt(outgoing[i]);
		}
		free(outgoing);
	}
	return;
}

RND protocol does not use additional packet types other than data packets and basic packet types required by deletion mechanism and direct transfer. As a result, recv() is rather basic.

void RND_Routing::recv(double rTime, int pktID)
{
	int PacketID;
	Packet *p;
	Header *h;
	// sanity check
	if((p = pktPool->GetPacket(pktID)) == NULL)
	{
		printf("Error: Packet %d doesn't exist in Packet Pool!\nAborting...\n",pktID);
		exit(1);
	}
	// get header and packet ID 
	h = p->getHeader();
	if(h->IsDuplicate() == true)
	{
		PacketID = h->GetOriginal();
	}
	else
	{
		PacketID = pktID;
	}
	// sanity check
	if(rTime < 0 || p->GetStartTime() < 0)
	{
		printf("%f: Node %d received new packet with ID %d and type %d from %d\n", rTime, this->NodeID, p->getID(), p->getType(), h->GetprevHop());
		exit(1);
	}
	
	// Identify the type of the packet
	switch(p->getType())
	{
		case DATA_PACKET:
		{
			ReceptionData(h, p, pktID, rTime, PacketID);
			break;
		}
		case DIRECT_SUMMARY_PACKET:
		{
			ReceptionDirectSummary(h,p,pktID,rTime);
			break;
		}
		case DIRECT_REQUEST_PACKET:
		{
			ReceptionDirectRequest(h,p,pktID,rTime);
			break;
		}
		case ANTIPACKET:
		{
			ReceptionAntipacket(h,p,pktID,rTime);
			break;
		}
		case ANTIPACKET_RESPONSE:
		{
			ReceptionAntipacketResponse(h,p,pktID,rTime);
			break;
		}
		default:
		{
			printf("Error: Unknown packet type! RND Routing is not using this type of packet!\nAborting...\n");
			exit(1);
		}
	}
	return;
}

Data packets of the RND protocol are handled in ReceptionData(). For each incoming packet this method updates statistics, runs garbage collection and stores the packet. In case the packet comes from the application layer it is stored inside the node's buffer waiting for a forwarding opportunity to arise through future contacts with other nodes.

void RND_Routing::ReceptionData(Header* hd, Packet* pkt, int PID, double CurrentTime, int RealID)
{
	#ifdef DIRECT_DEBUG
		printf("%f: Node %d received new data packet with ID %d from %d\n", CurrentTime, this->NodeID, RealID, hd->GetprevHop());
	#endif
	// Check if I am the packet creator (packet comes from the application layer)
	if((hd->GetSource() == this->NodeID) && (hd->GetNextHop() == -1))
	{
		// Update buffer
		Buf->addPkt(RealID, hd->GetDestination(),hd->GetSource(),CurrentTime, hd->GetHops(), hd->GetprevHop(), pkt->GetStartTime());
		Stat->pktGen(RealID, hd->GetSource(), hd->GetDestination(), CurrentTime);
		return;
	}
	// Check if I am the next hop
	if(hd->GetNextHop() != this->NodeID)
	{
		// Garbage collection
		if(pkt->AccessPkt() == false)
		{
			pktPool->ErasePacket(PID);
		}

		return;
	}
	// Check if I am the destination of the packet
	if(hd->GetDestination() == this->NodeID)
	{
		// Update statistics
		Stat->pktRec(hd->GetHops(), CurrentTime - pkt->GetStartTime(), pkt, pkt->GetStartTime(), false);
		// Garbage collection
		if(pkt->AccessPkt() == false)
		{
			pktPool->ErasePacket(PID);
		}

		return;
	}
	// I am the next hop but not the destination
	if(Buf->PacketExists(RealID))
	{
		printf("[Error]: Node %d received a packet with ID %d from node %d that already exists in its buffer\n", this->NodeID, RealID, hd->GetprevHop());
		exit(EXIT_FAILURE);
	}
	else
	{
		// Update buffer
		Buf->addPkt(RealID, hd->GetDestination(), CurrentTime,hd->GetSource(),hd->GetHops(), hd->GetprevHop(), pkt->GetStartTime());
		// Update statistics
		Stat->incTimesAsRelayNode(pkt->GetStartTime());
	}
	// Garbage collection
	if(pkt->AccessPkt() == false)
	{
		pktPool->ErasePacket(PID);
	}
	return;
}

Finally, SendPacket() interacts with other components of Adyton, such as Packet Pool and MAC layer, in order to send one packet to the node in contact. Its implementation is similar to all other protocols included in Adyton. Usually, this method differentiates between single-copy and multi-copy routing protocols.

void RND_Routing::SendPacket(double STime, int pktID, int nHop, int RepValue)
{
	int CurrentN=0;
	Packet *p=NULL;
	Packet *newPkt=NULL;
	if((p = pktPool->GetPacket(pktID)) == NULL)
	{
		printf("Error: Packet %d doesn't exist in Packet Pool!\nAborting...\n", pktID);
		exit(1);
	}
	// Duplicate the packet
	newPkt = p->Duplicate(Buf->GetHops(pktID));
	newPkt->getHeader()->SetNextHop(nHop);
	newPkt->getHeader()->SetprevHop(this->NodeID);
	newPkt->getHeader()->SetRep(RepValue);
	pktPool->AddPacket(newPkt);
	// Inform the current neighbors about the new packet
	CurrentN = Mlayer->BroadcastPkt(STime, this->NodeID, newPkt->getSize(), newPkt->getID());
	// Garbage collection
	if(CurrentN > 0)
	{
		// Set access attribute to safely delete the packet later
		newPkt->SetRecipients(CurrentN);
		// Update statistics
		if(newPkt->getHeader()->GetDestination() == nHop)
		{
			Stat->incHandovers(Buf->GetPktCreationTime(pktID));
		}
		Stat->incForwards(pktID, Buf->GetPktCreationTime(pktID));
	}
	else
	{
		// Cancel broadcast and delete packet (there are no neighbors)
		pktPool->ErasePacket(newPkt->getID());
	}
	return;
}

You can directly download the source file here.

Integrating the RND protocol into Adyton

Full instructions on how to add the RND_Routing.h and RND_Routing.cc in Adyton can be found in section "Protocol integration".

After that, a simulation using RND protocol can be executed by typing the following command.

$ ./Adyton -rt RND
⚠️ **GitHub.com Fallback** ⚠️