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

[Jeremy Lakeman]

On Fri, Dec 14, 2012 at 5:57 AM, Fraser Cadger <cadge01 at googlemail.com> wrote:
> Jeremy,
>
> Thanks again for your help. I appreciate that as you said, it can be
> difficult trying to help people understand your own software. I decided to
> send my initial message because I had tried reading through the code several
> times, picking up bits and pieces, but being unsure about exactly how things
> fitted together. I genuinely found your previous comments very illuminating
> and useful, and when I compared your comments with the code a great deal of
> it made sense and I then started thinking about ways of implementing my own
> routing. In fact, I produced a short report for my supervisor based on this
> and detailing the steps I intended to take to implement our routing protocol
> on Serval. I was about to dive in with this when I realised that I did not
> really know how the update process worked and that this was a very important
> factor! So I looked at the code again and tried to work my way through,
> making notes, those notes were then used in my last post. As you said in
> your comment it is better to work with people who are making independent
> progress, so that was why I tried to explain my understanding instead of
> jumping straight in with questions. Actually, I have been meaning to check
> back with the current version of the software in repository, as I noticed a
> few functions were in different locations and you mentioned that the self
> announce had been redesigned, so this is something I'll look at.
>
> Ok, so I'll now try to explain what I intend to do with routing.
>
> Our overall aim is to develop a protocol called Geographic QoS Predictive
> Routing (GQPR) which uses geographic/location/mobility information as well
> as other context to make QoS predictions for neighbours, these predictions
> are then used as the basis for forwarding decisions. GQPR is intended to act
> as the routing element in a framework called Geographic QoS Peer-to-peer
> Streaming (GQP2PS) which will run on WiFi devices (at the moment a testbed
> of six Android phones + my own Android tablet) and facilitate the streaming
> of both live (i.e. video call) and on-demand (i.e. recorded video) between
> the devices. The intended use case is for disaster recovery scenarios, for
> instance someone with basic medical/first aid training comes across an
> injured person but is not exactly sure what course of action to take, so
> they can initiate a video call with a doctor located at base station (or
> anywhere else covered by the network) who is able to view the patient and
> perform a diagnosis and if necessary supervise the treatment. This is just
> on scenario, it could also be used for repairing infrastructure where an
> engineer supervises and guides the repair process. Indeed, the technology
> could be used for many purposes unrelated to disaster recovery, but we are
> focussing on this to give us a specific aim, although the ideas for the
> technology actually came before the idea for application.
>
> What we have at present is the building blocks of GQPR which we have called
> GPR - Geographic Predictive Routing - GPR contains some of the main elements
> of what will become GQPR but not all of the functionality. At present GPR
> uses location predictions (provided by an Artificial Neural Network) as well
> as some other factors (congestion level, radio range, a metric we'd
> developed called neighbour range (this relates to the positions of a
> neighbour's neighbours), amongst others to make forwarding decisions. I
> think explaining GPR would make the most sense if I first explained how
> basic geographic routing worked and then discussed our modifications to it.
> As the name implies, geographic routing makes forwarding decisions based on
> node's geographic locations instead of logical addresses. The most basic
> form of geographic routing is greedy geographic routing.
>
> Greedy geographic routing works as follows:
>
> A packet is received, the node inspects the packet and records the location
> of the destination
> The node then calculates the physical distance between itself and the
> destination
> All of the node's neighbours are then compared against this distance
> The one with the shortest distance to the destination is selected as the
> next hop
>
> Greedy geographic routing does not create end-to-end routes (which is why
> some people prefer the term forwarding, although the terms are used
> interchangeably in literature), instead nodes are forwarded on a per-hop
> basis using the greedy criterion. This does seem a bit similar to BATMAN,
> where packets are also forwarded on a per-hop basis, however the big
> difference is that in greedy geographic routing nodes only have knowledge
> about their directly connected neighbours (i.e. those within their radio
> range) and they do not know about destinations. So while BATMAN nodes know
> of the destination node's existence (but only know the next hop to reach it
> and not a full route), greedy geographic routing nodes know nothing about
> the destination (aside from its address and location) and simply make the
> forwarding decision based on which neighbour is closest to that destination.
> The idea being that by shortening the geographic distance at each hop we are
> finding the quickest way to reach a destination.
>
> Obviously this does not always hold true in practice, and their is a problem
> known as the local maximum where nodes are forced to drop packets if they
> cannot find a neighbour closer to the destination than themselves (to
> prevent loops, the packet cannot travel physically backwards). However,
> greedy geographic routing is relatively lightweight, and highly localised as
> nodes are only required to know their directly connected neighbours and so
> are not affected by topology changes at the other side of the network
> (although this does mean nodes will sometimes forward packets to unreachable
> destinations). There have been quite a few modifications and variants to
> standard greedy geographic routing, some of which are more similar to
> conventional routing protocols by establishing end-to-end routes (but using
> geographic information to do so), while others focus on particular problems
> (QoS, energy consumption, security, etc.) I spent a large period of my first
> year surveying different geographic routing protocols and published this as
> a paper if you're interested in finding more about geographic routing
> (shameless plug for my own paper!!!);
> http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6238283&tag=1 .
>
> Getting back to basic greedy routing, obviously nodes need a way of
> discovering their immediate neighbours as well as finding the locations of
> other nodes who they are not directly connected to. The first is achieved
> through the sending of beacon messages at set periods of time, beacons are
> just your bog standard hello-type messages except they contain the
> coordinates of the sending node. Neighbours are stored in a dedicated
> neighbour table along with their coordinates, this neighbour table is the
> only table nodes store. The second is more difficult, but typically involves
> the use of something called a location service which usually involves
> certain nodes being designated as location servers. Regular nodes
> periodically send location updates to these servers and when a node needs to
> send a packet to a destination it is not connected to it will query the
> relevant location server for that node's destination. Exactly how the
> location service works depends on the particular scheme being used.
>
> So now to talk about GPR.
>
> Structurally GPR is very similar to classical greedy geographic routing, it
> was originally implemented on top of the code developed by Karp and Kung for
> their protocol known as GPSR (Geographic Perimeter Stateless Routing). What
> we did was first implement a neural network algorithm which predicts the
> future location of a device based on two previous coordinates, and the times
> they were recorded at. Tests found that the location prediction algorithm
> was able to accurately predict the future locations of neighbouring devices
> with an error of less than 1m in most instances. At present the use of the
> location prediction algorithm is relatively simple, all we are doing is
> looking at our neighbours two previous locations (and timestamps) and using
> these to determine what position the neighbour will be in when we send the
> packet. This allows us to use greedy geographic routing, but with the
> ability to cope with changes in location. In order to avoid sending packets
> to nodes that are too far away, we always check their predicted location
> against our transmission range to ensure they are within it. So in addition
> to using the location predictions we developed a modified congestion control
> algorithm which weighs the neighbour's congestion level against the distance
> between the neighbour and other factors such as the reliability of the
> node's information. The calculation is stored as a value t, and then we
> evaluate the neighbour's neighbour range (i.e. the physical range covered by
> its own neighbours), and if that neighbour is the best it becomes the
> candidate node and the other node's values for t are compare against it, and
> so until we finish the loop and end up with the best neighbour (or none in
> which case we'll drop the packet).
>
> Another factor is that because we are using location predictions we do not
> need node updates as frequently as geographic routing normally dictates. So
> while ordinary geographic routing protocols usually send these messages over
> 0.5s we send them every 13.6s which reduces the amount of control traffic.
> This is a number based on ns-2 experimentation and it is likely that in real
> wireless network it will need to be more frequent, but we still expect it to
> be a lot less frequent than the conventional 0.5s.

The real world isn't a flat 2d plain with no obstructions. But with
ACK's, NACK's and re-transmission it shouldn't matter too much if we
try to send a payload to a node that's now out of range. It should be
possible to detect broken network paths lazily with minimal impact to
throughput and latency. Plus when the network is busy, every data
packet can act as a beacon without wasting bandwidth.

> It might not seem like a huge modification, but it performs a lot better
> than unmodified greedy geographic routing in simulations of video calling
> and streaming traffic, and compares well with AODV, DSR, and DSDV. If you
> look at the bulletin points I typed above to describe greedy geographic
> routing, it is very similar except our means of calculating the best next
> hop is slightly different.
>
> As I said earlier, I had thought about and discussed with my supervisor how
> we could go about implementing GPR in Serval. We both decided that it was
> best to implement basic greedy geographic routing first and then work from
> there. There is a possibility that the NN algorithm we used in simulations
> will be too resource-intensive for the phones we are using and will either
> need to be modified or replaced with a different approach (we have some
> backups), so our plan is to implement basic geographic routing first,
> conduct separate experiments of the NN algorithm on the phones, and if
> everything goes well combine them, build GPR, and then continue working on
> the phones and simulations to create GQPR.
>
> In terms of implementing basic greedy geographic routing, I think making the
> forwarding decisions could be quite simple. When we are in
> overlay_stuff_packet(), instead of looking at the destination's next_hop
> field we would call a function which would loop through our list of
> neighbours and find the neighbour closest to the destination and select that
> as the next hop for the packet (or drop it if we can't find a suitable next
> hop). So that part seems quite simple.

How to you communicate the current geographical location of the destination?
How does the node that creates the payload work this out?
For that matter, how are we going to communicate the device's location
to the servald daemon?
What about devices that don't have a working location service? Or they
don't currently have the available power to run one?
But don't let that stop you from experimenting.

> However, what seems a bit more complicated is implementing the beaconing
> messages. I can see two ways of doing this; keep the current Serval system
> of self announcements, self announcement acks, and node announcements and
> simply add locations to these messages. The other would be to get rid of
> node announcements, and just use self announcement and self announcement
> acks to transmit location information between directly connected nodes.

I would recommend you keep the existing messages and formats, and add
new message types that are sent at the same time, in the same packet.

Firstly, if the existing messages change, you don't need to maintain
your forked version. Secondly, network nodes that aren't implementing
your routing protocol will still be able to communicate in other ways.

Which is an important point. I want to make it easy to use servald as
a platform for future routing experiments such as this. We should aim
to build a single generic payload format and internal memory format
for tracking links to neighbours, while allowing the storage and
communication of extra protocol specific link information. It may be
useful to forward this protocol specific data even if we don't
understand it.

I think it's reasonable for the core of servald to build a map of all
2-hop neighbours, regardless of the routing approach being used. This
should allow us to limit unnecessary repetition of messages that need
to be flooded to all nodes, similar to olsr's MPR selection.

> This
> actually brings me to a question I forgot to ask; if self announce messages
> are regularly sent why do we need to ack these? If we are sending our own
> acks and receiving acks from other neighbours do we need an explicit reply?
> I.e. if we just send self announce messages, but after a period of time we
> don't get any self announce messages from neighour x, we remove them from
> our list of neighbours. Slight digression.

We can't assume all network links are symmetrical. At the physical
layer, a high powered transmission can be heard by nodes in a large
area, but that doesn't mean they can all transmit with enough power to
send a packet in the other direction. Localised interference can also
be a significant factor. The adhoc wifi standard has a number of flaws
that can prevent packets being delivered. Just because you can hear a
broadcast packet, doesn't mean you could receive a unicast one and
vice versa. And since Android doesn't support adhoc mode specifically,
it isn't tested at all by device manufacturers. And most android
devices deliberately drop all broadcast traffic when they enter power
saving modes, eg when the display powers off. The real world is a very
messy place.

> Both of the two approaches I described have their advantages; the first is
> ostensibly simpler as we don't need to stop anything being sent, while the
> second means that we are getting something closer to the 'traditional'
> beacon approach used in geographic routing as well as avoiding the
> transmission of node announcements and the recording of indirect nodes which
> we will just ignore. On the other hand, if we keep node announcements this
> could actually act as a 'surrogate' for the location service if we include
> their locations. So if for instance we have three nodes; a, b, and with b
> being connected to a and c, a only being connected to b, and c only being
> connected to c. If b advertises c to a and a to c, then a is able to know
> the location of c (and vice versa) despite not being connected and without
> the need for a location service (obviously this is a trivial example as in
> this instance a can only reach c via b, so b is not really compared against
> anyone else).
>
> I realise that Serval's implementation of BATMAN is intended to limit the
> number of nodes a particular device knows about to avoid bandwidth going out
> of control, but as we only have a testbed of six this shouldn't be a problem
> for our experiments. Although we would obviously need to rethink for future
> uses which involve larger networks. So I imagine this would really be a
> temporary way of avoiding a location service, and in the long run we would
> still try to implement an explicit location service (possibly based on
> Serval Maps which Paul pointed me in the direction of). However, I did
> discuss the idea of retaining some BATMAN elements in our implementation
> (where we have some knowledge of nodes we are not directly connected to),
> instead of going for a pure greedy geographic routing approach (where we
> only know about our one-hop neighbours) as we are by no means obliged to use
> a particular approach and our ultimate aim is performance. Therefore it is
> possible that this will lead to us developing a hybrid approach between
> GPR/GQPR and BATMAN.
>
> However, I think for now the best approach might be for us to try both
> messages of messaging and see how they perform. I'm meeting my supervisor
> tomorrow, and I'm going to discuss this with him. I've read through your
> comments fully, so I think I should be able to start planning how I will
> modify Serval announcement/advertisement messages and then try to get
> something running next week. Unfortunately I am going back home for the
> Christmas holidays, and I will only have access to an Android tablet and a
> Windows laptop (which belongs to someone else!), so I'm not sure how much
> work I'll get done until January, but if I can get Android NDK up and
> running on the laptop I might be able to get some routing work done.
>
> Hopefully, the explanation of my work makes sense (or enough sense), and as
> I indicated before I am happy to share any code I develop myself (I have
> spoken about this with Paul). So in addition to developing my routing
> protocol I intend to work on video calling, and Paul stated this was
> something the Serval team wanted to include, so if I get that working I am
> more than happy to put the code in the repo.
>
> Regards,
>
> Fraser
>

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