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

Jeremy Lakeman jeremy at servalproject.org
Tue Nov 27 15:00:10 PST 2012


On Wed, Nov 28, 2012 at 6:30 AM, Fraser Cadger <cadge01 at googlemail.com> wrote:
> 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).

Close, next_hop always points to our immediate neighbour that we
should forward the payload to. The payloads themselves are almost
always sent in broadcast packets which may contain multiple payloads
addressed to multiple neighbours. Including payloads that should be
flooded across the entire network.

> 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?

See overlay_queue.c / overlay_stuff_packet() where we pull payloads
from our QOS queues and make a final decision about where the payload
should go next.
overlay_payload.c / overlay_frame_append_payload() is where the header
format is written into the packet.
overlay_packetformats.c / packetOkOverlay() is where those payloads
are parsed out of an incoming packet and processed or queued if they
are addressed to this node.

> 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?

That's for connected client applications to send and receive messages.
If you want to pass some extra messages between daemons, the process
is a little different.

You can schedule an alarm to periodically queue a message, or you can
hook into every outgoing packet and write your payload just before
it's sent. eg overlay_tick_interface() is called for each interface
periodically to force an outgoing packet.

You can add a case to process the message in overlay_mdp.c /
overlay_saw_mdp_frame().


> Concerning the subscriber entity, is there an actual table/list/array of
> these b as I can't seem to find one?

There's a tree in memory, built in overlay_address.c as each node is discovered.

> 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.

Yes, basically overlay_route.c is currently responsible for path
discovery. These decisions are written into the subscriber structure
so that none of the rest of the code needs to know the internal
details of how these routes were calculated.

I also have plans to implement a different routing protocol. I've been
trying to tease apart our current spaghetti code to separate the
different layers of the implementation as much as possible. This
should enable us to drop in a different path discovery process without
needing to change much of the rest of the daemon.

I've been doing some more work in that direction recently in a
currently private branch. Mainly to tweak the packet format, reducing
header overheads, so we can lock in the network byte format for
forward compatibility. I've still got a couple more changes to
implement though.

Neighbour discovery & link state detection need to be split out from
overlay_route.c and redesigned. But I'm not quite ready to start that
task yet. We don't have any bandwidth throttling yet. If you're
planning to send large volumes of data, any excessive latency added
from buffer bloat can cause havoc with route statistics. The list of
things I'd like to get done before I start replacing the routing layer
never seems to get any shorter.

You should also check out our testing framework, specifically
tests/routing. While the setup process for these tests is a little
verbose, and the file based network simulation is a bit different to
an actual adhoc mesh. It gives you a quick way to tell if you're on
the right track without needing to wander around with phones all the
time.

>
> 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.

-- 
You received this message because you are subscribed to the Google Groups "Serval Project Developers" group.
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