Introduction to the geographic greedy forwarding

What is the geographic greedy forwarding?

There are several types of ad hoc routing protocols, such as proactive, reactive, geographic stateless routing, and so on. I believe geographic stateless routing is the simplest routing protocol to be implemented in ns2. Why it is the simplest? It is because the property of stateless indicates that no node in a network does not maintain any routing table. Note that we will still keep neighbors list at the routing component, but such information is available at logical link layer.

The purpose of this series is to learn how to implement a new routing protocol, thus we consider static networks where nodes are not move. The assumptions we hold for implementation include; 1) all nodes have its own geographic location (2-dimensional coordinates); 2) each node knows its neighbors location; and 3) a source node knows the ID and the location of the corresponding destination.

The geographic greedy forwarding protocol that we are going to implement works as follow.

  1. On receiving a packet from upper layer, the source node adds a header including the destination ID and location.
  2. The source node sends out the packet to the neighbor closest to the destination.
  3. On receiving a packet from a neighbor, a node forwards the packet if there exists a neighbor closer to the destination than itself.
  4. If there is no neighbor closer than itself, so called local minimum, it simply drops the packet.
  5. When the packet arrives at the destination, routing is done.

Source codes

In this project, we will write new codes (greedy_pkt.h, greedy.h, greedy.cc, greedy_nbr.h greedy_nbr.cc, greedy_flow.h, and greedy_flow.cc), new script codes (greedy.tcl (the scenario file) and nbr.tcl), and modify existing source codes (common/packet.h, queue/priqueue.cc, tcl/lib/ns-lib.tcl, tcl/lib/ns-packet.tcl, and tcl/lib/ns-mobilenode.tcl).

The source code of this project is greedy.tar.gz.

Packet format

In a packet, we need to define the source node ID, the destination node ID, and the location of the destination. The following is the part of greedy/greedy_pkt.h.

Neighbor list and flow information

Since we assume that each node has its neighbors list including their location and the destination location, the routing module will need to have those information. Hence, we create two classes as follow.

 

Routing Module

The routing module is the most important part of this project, because we are implementing a routing protocol. First, we need to make packet class to bind TCL and C++ as follow. You can consider this is a template, and when you implement another protocol, you just change the name of the class.

Second, we need to bind the routing module in C++ and TCL so that you can create a routing agent from a scenario file. Again, you can consider this is a template. You will always need to do this when you implement a new routing protocol.

Thrid, we need to override Agent::command(arg ....) so that we can access this class in C+ from a TCL file. For example, when you want to set up neighbor list from a TCL file, you can wirte "$node_($i) set-nbr $nbr_id $nbr_x $nbr_y". Note that the number of arguments is at least two, the first one is node instance, $node_($i), and the second one is the command such as "start", "set-location", and so forth. Then, the parameters that you want to pass to C++ code follow.

Fourth, we need to override Agent::recv(args ...). This is called when upper layer or lower layer pass a packet to the routing module. For example, when a CBR agent sends a packet, a routing agent receive the packet by this function. Also, when a node receive a packet from another node, the routing agent receive the packet from a link layer agent by this function.

In the first "if" statement, the agent checks if the source IP address is its own address. If so, the packet is either one that loops or one from the upper layer. If the number of forwarding in hdr_cmn (it stands for common header) is equal to 0, the packet is from upper layer, and thus the routing module set greedy_pkt header to be the corresponding destination information.

If the first "if" statement is is not true, the packet is definitely an incoming packet from another node. So, the routing module checks what kinds of packet it is. The type of a packet is stored at "hdr_cmn ch->ptype", which could be an application packet e.g., PT_CBR, a control packet i.e., PT_GREEDY, and so on. But, be careful. Greedy forwarding is stateless and therefore it does not introduce any control packet in the routing layer. So, the packet type could not be PT_GREEDY. If the packet is one generate by an application such as CBR, the routing agent forward the packet to the destination.

Fifth, we define forwardData(Packet* p) to handle packet forwarding. It checks if the destination is this node. If so, it will be forwarded to the upper layer by "port_dumux->recv(p, 0)". Otherwise, it will be forwarded to the lower layer by "send(p, 0)". Note that we define "getNextNode(Packet* p)" function that returns the closer neighbor to the destination. If the packet reaches the local minimum, the function returns -1 and then the packet is dropped.

Although there are several local functions we need to write in the routing module, we already talk about the important parts in the routing module.

Modifying Existing C++ codes

To combine your original protocol with ns2, we have to modify packet/packet.cc as follow.



In addition, we need to modify queue/priqueue.cc as follow.

Modifying Tcl/Tk code

To bind C++ and Tcl/TK, we need to modify some existing tcl codes. Since the new routing protocol defines its original packet type, we need to modify tcl/lib/ns-packet.tcl as follow.

We need to modify tcl/lib/ns-lib.tcl so that we can create routing module instance from TCL code as follow. wwe first add a few line to call a function "create-greedy-agent $node", and then we define the function to create routing module instance.



When we want to access to C++ code from TCL, we need to add some function to tcl/lib/ns-mobilenode.tcl as follow. To be specific, we will add functions to access routing agent from your scenario file, to set up neighbors for a node, and to set up CBR flow information (this is for a source node to get a destination location).

Compile

Before we compile, we have to modify Makefile.in. Otherwise, the source codes we have just written will not be compiled. We need to add .cc file to "OBJ_CC =" in Makefile.in as follow.