Formalizing Properties

Top 5 properties we are going to look at in BATMAN:

  1. All OGMs that have entered the network will leave the network after one of the following conditions: every node has received at least one and re-broadcasting stops; they have been lost due to packet loss; their TTL value has expired.

    • This assumes that the TTL value is decremented with each hop in the network .It also assumes that all nodes broadcast an OGM at some point, and all nodes re-broadcast an OGM upon receipt. Finally, this assumes that with some probability packets are lost during the sending of routing messages.

  2. There are no redundant OGM messages from the same source.

    • This is based on the assumption that with every OGM message, the sequence number is incremented. Therefore, no OGM message should have the same sequence number from the same source (within the limits of integer overflow).

  3. If a destination is reachable from a given source, the BATMAN algorithm correctly routes to it.

    • This assumes that if the BATMAN algorithm has been run on an ad-hoc network and that each node has a routing table showing the first hop neighbor for every destination.

  4. There are no routing loops in the network.

    • This is based on the assumption that when a incoming OGM has the matching originator address, the node only further process the incoming OGM that has the equal or higher sequence number. For the OGM having the same sequence number, it only further process the OGM with equal or higher TQ (vale of goodness of a path). Otherwise such OGM is dropped.

  5. There are only bi-directional links in a route.

    • This assume that upon receiving an OGM, if the unidirectional flag is set to 1, and the last originated sequence number does not differ more than BI_LINK_TIMEOUT from the recorded sequence number, then the OGM is further process, otherwise the packet is dropped.
Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s