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

[Fraser Cadger]

Paul,

Thank you very much for your fast reply!

Your suggestion of using Rhizome instead of the MDP overlay is interesting,
and definitely worth considering. Although I read a little about Rhizome on
the Serval website I don't think I really appreciated it's capabilities.
Also, when I installed the release version of Serval from Google Play,
selecting Rhizome didn't appear to do anything (I'm not sure if this was an
error or because the Rhizome could wasn't fully functioning then).
Therefore, when I came to read the Serval code I decided to skip the
Rhizome code to save time.

Now it would seem as though this was a mistake, and your description of
Rhizome in particular the journal concept sounds very interesting. I have
been considering implementing some for of peer-to-peer/distributed approach
for the actual streaming, due to the distribute nature of an ad-hoc/mesh
network. In the envisaged networks node mobility will be permissible and
this in addition to other dynamics calls for distributed approaches. The
journal concept could be of great use here, with some tweaking as you
mention. Using the p2p idea, I would envisage some form of peer/node
selection for participation in the streaming, and then the use of my
routing protocol to do the actual protocol. However, I have always intended
interaction between the streaming application and routing layers, and so it
is possible that the end result will lack the formal separation between
overlay and 'underlay' routing found in traditional applications.

I also like your suggestion of using Serval Maps for sharing location. In
most geographic routing protocols there is something known as a location
service which acts as a mechanism for sharing node locations so that nodes
who are not in direct contact with each other can still find their
locations. Initially, to test geographic routing, I was just planning on
running five phones in a static scenario and checking locations manually,
just to test geographic routing was possible. However, as my project is
actually concerned with mobility I will eventually need to find a way of
allowing nodes to share their locations. The visual aspect of Serval Maps
also sounds appealing for, as you say, choosing which nodes you want to see
a video. Having a graphical means of selecting nodes for streaming is
definitely something we would like.

One last question, I've had a quick look through the Serval code, and am I
right in saying all of the Rhizome code is located in the serval-dna
folder, or is there other Rhizome code elsewhere?

About contributing code, I am happy to do that via the repository.

Thanks again for your reply.

Fraser
On Nov 27, 2012 10:58 PM, "Paul Gardner-Stephen" <paul at servalproject.org>
wrote:

> Hello Fraser,
>
> Sounds like an interesting project.
>
> Jeremy has been doing the most work on the mesh routing parts of
> Serval, so I expect that he will chime in with where things are in the
> current state of the code.  Note that routing is currently under
> active development, so things are liable to change.
>
> Back to your actual goal, which is to stream multimedia content for
> disaster recovery scenarios, this is something that we have been
> thinking about from the earliest, and it is nice to hear that someone
> is looking to work on it.
>
> Thinking about the general approach you are considering around greedy
> routing, it may make more sense to use the Serval Rhizome
> store-and-forward scheme as the basis, rather than the MDP/overlay
> real-time routing.  Rhizome understands the idea of a "journal" which
> is really just a file that grows in successive versions.  Nodes
> receiving a journal can, in principle at least, pull just the new part
> of the file.  If the file has grown further in the meantime, then
> another pull will occur.    There would still be some tweaking
> required using this approach, such as making Rhizome be more selective
> about who it exchanges with so that it can be directed towards the
> destination, but I think it would give you more resilient routing. The
> tradeoff is likely to be increased latency, although I think that the
> actual useful throughput would increase, because packet loss and
> retransmission would be dealt with each hop.  You would also be able
> to use WiFi unicast packets, and thus the full WiFi bandwidth.
>
> You should also take a look at Serval Maps that provides functionality
> for nodes to share their geographic location (via Rhizome), and that
> could be used in place of adding geo tags to each packet.
>
> I guess overall I am envisaging a solution where Serval Maps provides
> the geolocation information, and also possibly the user interface for
> choosing which phone you want to see the video from.  Then the video
> or other content is pulled down via the improved Rhizome that you
> would create.  By using Rhizome, it doesn't matter if a link drops for
> a short while, as the content will be cached on intermediate nodes,
> and so it will deliver as soon as it is able.
>
> Anyway, happy to keep thinking through the options with you, and
> looking forward to seeing what you create.
>
> We would prefer that you contribute any modifications you make back to
> our repo so that everyone can benefit.  We have a standard Harmony
> Project issued contributor agreement that can facilitate that fairly
> painlessly.
>
> Paul.
>
> 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).
> >
> >
> > 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.
>
> --
> 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.
>
>

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