[serval-project-dev] Implementing a different routing protocol

Fraser Cadger cadge01 at googlemail.com
Tue Nov 27 12:00:59 PST 2012


 

Hi all,


 First of all, let me start by stating that I am very impressed with the 
work of the Serval Project and the Serval app. I appreciate that it is 
still under development, but having experimented on several Android phones 
I have found it really easy to use and effective.


 My name is Fraser Cadger and I am a third year PhD student at the 
University of Ulster in Northern Ireland. My project is concerned with 
developing a framework to allow the streaming of multimedia content both 
live (i.e. video call) and on-demand (recorded videos) in disaster recovery 
scenarios using a mesh network of WiFi-enabled devices (currently this 
entails a testbed of six Android phones). As I am working with Android 
devices this obviously adds a layer of difficult when trying to implement 
ad-hoc networking. After doing some searching I came across several 
different implementations of ad-hoc routing on Android, and after some 
experimentation the two I was most interested in were Serval and Commotion 
(who I believe the Serval Project collaborates with). In the end I decided 
to work with the Serval app because I felt that was the closest to what I 
was doing, and I also liked how it worked on the phones.


 Currently what I am interested in doing is implementing my own routing 
protocol (which is still under development) on the phones using Serval as a 
base. That is to say, that I want to replace the modified BATMAN code 
Serval uses for routing with the current version of my routing algorithm 
(originally written in C++ for ns-2 but re-writing in C should not be a 
huge problem). Obviously I realise this will not be a simple as copying and 
pasting my code in and that is why I am sending this message. From reading 
various comments in the code I understand that one of the main 
modifications to Serval is to restrict broadcasting to link-local nodes 
(i.e. not network-wide broadcasting), if I have understand the code 
correctly that is. The protocol I am developing is a variation of the 
greedy routing protocol GPSR 
http://www0.cs.ucl.ac.uk/staff/b.karp/gpsr/gpsr.html . Both the original 
GPSR and my own protocol use limited broadcasting as well; beacon (regular 
hello messages) are broadcast as far as one hop and nodes maintain tables 
of neighbours who can be reached directly only. There is no conventional 
collection of routes; instead each node forwards a packet to their 
neighbour who best meets the criterion/criteria (generally geographic 
location, i.e. located closest to the destination) one hop at a time. So 
packets are effectively passed from node to node without a formal route 
existing. This version of geographic routing is not perfect, and that is 
why we are working on several modifications, but for now I am content to 
have some form of working geographic routing up and running.


 I have been reading through the code and trying to determine what parts I 
need to change and where to add my code. What I am looking for is the point 
at which a node determines where to send a packet. I realise that this will 
vary depending on the packet's origin, that is to say that when a node 
generates a new packet it will usually be treated differently from when an 
intermediate node receives a packet from another node. Now, if I understand 
correctly Serval's version of BATMAN does not use an explicit routing table 
structure. I have came across a struct called subscriber defined in 
overlay_address.h, and from what I have read this seems to act as a record 
of different nodes (destinations). Within the subscriber struct there is an 
integer variable called reachable and this determines whether a node is 
reachable directly via unicast, broadcast, or must be reached indirectly. 
If a node must be reached indirectly then there is a field called next_hop 
which if I understand correctly is a pointer to another struct (the 
intermediate node between ourselves and the destination). Is this correct? 
Now, what I have noticed in the code is that sometimes next_hop contains a 
pointer to another next_hop (i.e. next_hop->next_hop). What I'm guessing 
this means is that if there are multiple intermediate nodes (i.e. to send a 
packet to node D node A needs to send it via B and C), then this is a way 
of linking them as a route. So in essence, the subscriber struct contains 
the route to a destination (by way of the next_hop attribute).


 For the actual routing, from reading the code I'm guessing that the 
'overlay_route_recalc_node_metrics' function is used to determine whether a 
destination can be reached directly or indirectly, and if indirectly it 
will then assign the appropriate intermediate nodes as next_hop's. 
Therefore, to create or change a route this function is called. Is this 
correct?


 In my case, I would like to do things slightly differently. As I am not 
doing end-to-end routing I do not need a list of destinations, instead all 
I want is a list of 1-hop neighbours who can be accessed directly. Then 
from that list I would determine which of these is the most suitable as the 
next hop (obviously in my case this will require other stuff, for instance 
adding GPS coordinates to the packet header and storing this in the 
subscriber field) and forward the packet to that node, and so on until the 
packet has been delivered (or has to be dropped). 


 The main questions I have are:


 
   - 
   
   Exactly where is a packet received and the node to which it should be 
   sent decided?
   - 
      
      i.e. if I want to decide which node to forward a packet to where 
      should I decide this?
      - 
      
      I came across a method called 'overlay_mdp_receive' in mdp_client.c, 
      is this maybe what I'm looking for?
       - 
   
   Concerning the subscriber entity, is there an actual table/list/array of 
   these b as I can't seem to find one?
   - 
      
      i.e. a list of neighbours/known nodes/destinations?
       

 I apologise if my questions and this email aren't very well-worded. 
Essentially what I'm looking for is some advice/guidance on exactly how 
routing (determining intermediate nodes for nodes which cannot be reached 
directly) and forwarding (looking at a received/originated packet and 
determining which node to send it to) is done. As I indicated earlier in 
this message, there are a few functions/structs I have stumbled across that 
I think are relevant and I have made some guesses at what they are doing, 
so I would appreciate if someone could correct/expand on my guesses.


 Any help/guidance I have would be greatly appreciated. It goes without 
saying that any code I develop myself I will happily share, and any 
issues/bugs I come across with Serval will be reported.


 Thank you for taking the time to read this message, I'm sorry it's a bit 
on the long side but hopefully I've made myself clear. 


 Regards,


 Fraser


Ps. I realise this topic has been covered before, but I think some of the 
questions I am asking in this message are new.

-- 
You received this message because you are subscribed to the Google Groups "Serval Project Developers" group.
To view this discussion on the web visit https://groups.google.com/d/msg/serval-project-developers/-/MgHT2-tr_dcJ.
To post to this group, send email to serval-project-developers at googlegroups.com.
To unsubscribe from this group, send email to serval-project-developers+unsubscribe at googlegroups.com.
For more options, visit this group at http://groups.google.com/group/serval-project-developers?hl=en.


----- End forwarded message -----
-- 
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
______________________________________________________________
ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org
8B29F6BE: 099D 78BA 2FD3 B014 B08A  7779 75B0 2443 8B29 F6BE





More information about the cypherpunks-legacy mailing list