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:
- incoming new OGMs
- Originator_List, with each of type typedef
Fields that an Originator maintains:
- Originator_Address, with type int
- 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
Generate and Broadcast OGMs
- Reception and Evaluation of OGMs
Update and Useage of Bidirectional Link Check
Neighbor Ranking and Best Link Detection
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