Home › Implementated Protocols

Implementated Protocols

des-aodv

This is our Ad hoc On-Demand Distance Vector Routing (AODV) protocol implementation as a variant for underlay routing. The protocol has been modified to optimize the route discovery in scenarios with unidirectional links.

Deviations from the RFC:

  • All links are monitored for bidirectionality independent of whether the link is used for a route. RREQ are forwarded only when they are received over a bidirectional link. Thus routes are always bidirectional which is not the case in AODV as defined in the RFC.

  • RERR_RATELIMIT, section 6.11, page 23. Router error messages are limited to RERR_RATELIMIT per second. Additional messages are not queued but dropped to avoid blocking.

Optional features of the RFC:

  • Local route repair, section 6.12., page 25. The node detecting a local link break will always send a RERR message. The RFC additionally allows for local link repair which in our opinion might lead to suboptimal routes.

  • Route Error (RERR) Messages, section 6.11, page 23. The RFC allow RERRs to be sent as unicast, broadcast, or iterative unicast. In des-aodv they are always sent as broadcast.

des-ara

This is our Ant Routing Algorithm (ARA) protocol implementation as a variant for underlay routing. ARA uses a two-way flooding (source to destination and backwards) to leave pheromone trails on the routers in the network. Data packets are forwarded along these trails depending on the intensity of the pheromone. The pheromones diminish over time but are intensified by any packet that is forwarded thus unused or suboptimal paths dissappear while good paths are preferred. ARA is a reactive multipath routing protocol.

Features:

  • Currently, either the best next hop is selected to forward packets or alternatively a random next hop considering a weighting function.

Description:

The following figure shows node A and node B that are connected over a network which is represented by the gray paths with routers at the intersections. When node A has to send a packet to B and no next hop is yet know, it floods a forward ant packet (FANT) over the network. The ant(-s) leave(-s) a pheromone trail which is marked by the red dots in the figure. Once a FANT reaches node B, a so called a backwards ant packet (BANT) is flooded from B to A leaving the blue pheromone trails. When a BANT is received by A, it knows that there should exist a path and thus forwards the data over the router which forwarded the BANT. As there can exist many routes in the nextwork, each node determines the next hop based on the pheromone level. Data packets increase the pheromone level which leads to a selection of the best path(-s) over time as it is assumed that they will consist of links with a high PDR and deliver the most packets per time unit. Underused paths vanish over time as the pheromone "evaporates".

ARA Example

des-batman

This is our Better Approach To Mobile Ad-hoc Networking (B.A.T.M.A.N.) protocol implementation as a variant for underlay routing.

Deviations from the Internet-Draft:

  • Host Network Announcement (HMA), section 3.1., page 5 and section 3.3., page 8 and section 5.1., page 12. The des-batman implementation currently provides no gateways to other networks as it is out of our focus.
  • Precursor List Mode is an option where OGMs are evaluated even when the sequence number of a received OGM is equal to the sequence number in the routing table. This modification was necessary to optimize the protocol for multiple-transceiver devices.
  • Packet ID is an modification to avoid looping data packets as only OGMs have normally a sequence number. In some first experiments we noticed that while the loop detection of OGMs works, data packets began to loop at some point.

Optional features of the Internet-Draft:

  • none yet

des-dsr

This is our Dynamic Source Routing (DSR) protocol implementation as a variant for underlay routing. Currently there are several variants that also enable multi-path routing.

DSR  variants:

(Description will be added soon)

  • des-dsr is the unicast variant of DSR as defined in RFC 4728
  • des-dsr-linkcache extends des-dsr by a linkcache
  • des-dsr-etx uses the ETX metric instead of shortest path routing
  • des-dsr-etx-backup
  • des-dsr-etx-lb
  • des-dsr-linkcache-etx supports uses a linkcache as well as the ETX metric
  • des-dsr-mdsr is based on MDSR (Protocol 1) by Nasipuri and Das
  • des-dsr-smr is based on SMR by Lee and Gerla
  • des-dsr-backuppath1 is based on BackupPath (Scheme 1) by Lim, Xu, and Gerla
  • des-dsr-backuppath2 is based on BackupPath (Scheme 2) by Lim, Xu, and Gerla

des-example

This is just a minimal DES-SERT skeleton daemon which is used as a starting point by developers. Additionally we use the separately available debian/ files to ease the Debian packaging process.

des-gossip

Gossip routing or probabilistic flooding is a very simple approach to send data over a network. Every router receiving a packet, for which it is not the destination, chooses a random number. If this number is below a specific threshold, the packet is forwarded by broadcast, otherwise it is dropped. Depending on the value of the threshold, a packet send by a source via broadcast may be received by only some or even all nodes in the network.

The implementation is very simple and uses no TLL field or loop detection. Thus packets may loop around the network for a very long time. The des-gossip package serves as a simple example how to send and receive packets.

des-gossip-adv

The deficiencies of des-gossip are resolved by this more advanced implementation. The daemon can be configured on demand over the command line interface thus enabling different forwarding strategies. We started with 4 variants based on the works of Haas et al. and implemented several others.

Gossip routing variants:

Most variants are extensions of others. Thus parameters are only explained once.

  • gossip0(p): Forward packets when random(0,1) <= threshold p; otherwise drop the packet.
  • gossip1(p,k): For the first k hops forward with p=1.0 (flooding)
  • gossip2(p,k,p2,n): If the node has less than n neighbors, use p2 to determine the packet forwarding.
  • gossip3(p,k,m): If a packet is not forwarded due to chance, store the packet. If fewer than m duplicates are received in some specifc time, send the stored packet; otherwise drop it finally.
  • gossip4(p,k,k'): Each node has a zone of k' hops. If a packet is received that is destined to a node within this zone, than the packet is sent as unicast over a route found by some proactive unicast routing protocol. This variant is inspired by the Zone Routing Protocol (ZRP).
  • gossip5(p,k): Same behavior as gossip3 but if fewer than the number of neighbors minus 1 duplicates are received, then the stored packet is sent.
  • gossip6: is based on the gossip3 modification of Zhongmin Shi and Hong Shen 
  • gossip7: is based on the work of Mohammed et al.
  • gossip8: is based on the work of Hanashi et al.
  • gossip9: is based on the work of Abdulai et al.

The first batch of graphs based on our experiments is available here.

des-namtab

This is a variant of the Better Approach To Mobile Ad-hoc Networking (B.A.T.M.A.N.) protocol implementation which resolves many of the issues we found within the original B.A.T.M.A.N. specification. Most notably we had to modify the protocol to find better routes in networks with multiple transceiver routers and unidirectional links.

Features:

  • Inverted routing table in addition to normal routing table that stores the next hop in forward direction
  • Optional usage of unidirectional links
  • Inverted link quality measurement. The next hop to A to is not determined based on the OGMs received from A but on the OGMs sent by B to A.

des-olsr

This is our Optimized Link State Routing (OLSR) protocol implementation as a variant for underlay routing. Our implementation is somehow a hybrid of version 1 and the draft version of OLSRv2. The latter one basically only modifies the first version by introducing a new message format (RFC 5444) and the Neighborhood Discovery Protocol (NHDP). The extension mechanism is similar to the format in RFC 5444.

Deviations from the RFC:

  • MPR selection algorithm, section 8.3., page 37. The original MPR selection is based on an algorithm that has a complexity O(n3) where n is the number of neighbor. Our algorithm has a complexity of O(n2) and prefers neighbors to be included in the MPR set that have a lower willingness but more neighbors.

  • Gateways, section 12.2., page 51 and section 12.6., page 53 and section 20.3., page 68. The des-olsr implementation currently provides no gateways to other networks as it is out of our focus.

Optional features of the RFC:

  • While OLSRv1 specifies hop count as metric, many implementation also provide ETX. Currently, there is a discussion on the IETF MANET mailing list about the metric for version 2. The consensus will probably be that a separate RFC will be written which discusses different metrics that can be used, e.g., in OLSRv2. You can choose between a hop count and packet loss ratio metric in the configuration file of des-olsr.