Draft of our Model

The following is a draft for our SPIN model focuses on the 5 properties we are going to check. (The list is only the first draft that is continuously under modification).

OGM’s fields we need to keep track:

  • TTL, with type byte. Initially set to a value in the proposed range, [2, 255]
  • Seq_No, with type short. Initially set to a value in the proposed range, [0, 65535] (take the modulo 2^16 when exceeds the range).
  • Is-Direct-Link_Flag, with type bool. Indication of a direct neighbor or not, initially set to 0.
  • Unidirectional_Flag, with type bool. Indication of the neighboring node is bidirectional or not, initially set to 0.
  • Originator_Address, with type int, set to the IPv4 address interface on which behalf the OGM has been generated.

Information a Node keeps:

  • Routing_Table
  • incoming new OGMs
  • Originator_List, with each of type typedef

Fields that an Originator maintains:

  • Originator_Address, with type int
  • Last_Aware_Time
  • Bi-direct_Link_Seq_No,with type short. The last accepted self-initiated OGM received from a direct link neighbor
  • Current_Seq_No, with type short.
  • The newest OGM seq_no accepted from the given Originator.
  • Neighbor_Information_List, with type typedef

Fields that each Direct Link to each Neighbor (Neighbor Information) maintains:

  • Sliding_Window, with type byte (proposed Sliding Window_Size = 128)

    • In-Window_Seq_No: Current Seq_No from this Originator and the (Window_Size -1) Seq_No below it.

    • Out-Of-Range_Seq_No: All other seq_no that are not in In-Window range, (rew, next expected seq_no)

  • Packet_Count, with type byte.
  • The amount of seq_no recorded in the sliding window.
  • Last Valid Time, timestamp when the last valid OGM received via such neighbor
  • Last_TTL, last OGM’s TTL received via such neighbor

5 Steps of Flooding Mechanise

  1. Generate and Broadcast OGMs

  2. Reception and Evaluation of OGMs
  3. Update and Useage of Bidirectional Link Check

  4. Neighbor Ranking and Best Link Detection

  5. Rebroadcast Mechanism

Step 1: Generate and Broadcast OGMs

  • Periodically generate and broadcast every ORIGINATOR_INTERVAL (maybe we can use a counter instead, and a new OGM is generated and broadcast when the counter mod some number == 0)

  • Initialize all OGM as describe in the “OGM’s fields we need to keep track”

Step 2: Reception and Evaluation of OGMs

  • MUST drop if OGM’s Originator_Address ==  this node’s Originator_Address

  • MUST drop if the sender address of the OGM is a broadcast address of an own B.A.T.M.A.N. interface the message MUST be silently dropped

  • If the Originator Address of the OGM is identical with any of the Nodes’ own B.A.T.M.A.N. Interfaces then the OGM has been originated by the Node itself.  The processing of the OGM MUST continue as described in Step 3 and afterwards silently dropped.

  • MUST drop if Unidirectional_Flag == 1

  • MUST be processed as Step 4 if Step 3 Check Succeeds AND Seq_No is Out-Of-Range_Seq_No

  • MUST be recroadcasted as Step 5 if sender address == Originator_Address

  • MUST be recroadcasted as Step 5 if Step 3 Check Succeeds AND (Seq_No is Out-Of-Range_Seq_No OR TTL == Last_TTL)

Step 3: Update and Useage of Bidirectional Link Check

  • Record the seq_no of each self-originated OGM (re-broadcasted by a direct link neighbor) for each Interface as Bi-direct_Link_Seq_No If
  • the self-originated OGM has been received via the Interface for which the OGM has been generated

  • Is-Direct-Link_Flag == 1

  • Seq_No == the Seq_No of last OGM broadcasted for that Interface

  • Check Succeeds if (last originated Seq_No – recorded Seq_No) < BI_LINK_TIMEOUT
  • I can’t find a proposed value for BI_LINK_TIMEOUT

Step 4: Neighbor Ranking and Best Link Detection

Upon reception of an OGM from another node, the following must be performed:

  • MUST update Packet_Count
  • If OGMs Seq_No > Current_Seq_No then,
  • Current_Seq_No = Seq_No

  • MUST update Last_TTL

  • The Sliding Windows of all known links to the Originator of the OGM must be updated (purged) to reflect the new upper and lower boundaries of the Ranking Range.  The Sequence Number of the received OGM must be added to the Sliding Window representing the link via which the OGM has been received.

  • MUST update Best Link to this link if the Sliding_Window, of the link via which the OGMs has been received contains the most (In-Window_Seq_No) then this link.

Step 5: Rebroadcast Mechanism

When an OGM is to be re-broadcasted, the following MUST be performed,

  • TTL -= 1

  • MUST Is-Direct-Link_Flag = 1 if OGM has been received from Directed Link Neighbor AND is re-broadcasted via the link which it has been received

  • MUST Unidirectional_Flag = 1 if OGM is to re-broadcasted that has been received via an unidirectional link

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