WiSense MAC – Duplicate packet detection
In this post, I am going to explain how WiSense MAC (Medium access control) layer handles duplicate packets.
Assume you have two WiSense nodes, node A and node B. Suppose node A sends a packet (say Px) to node B and the “ack_required” bit in the packet’s MAC header is set to 1. When “B” receives this packet ‘Px’ , it will send an acknowledgment frame to A. If A receives this acknowledgment frame, A will be satisfied that the packet ‘Px’ has made it to B. If A does not receive this acknowledgment frame from B, A will retransmit ‘Px’ to B. Note that when B receives ‘Px’, it will send the corresponding ACK frame (to A) immediately without performing CSMA/CA (carrier sense multiple access with collision avoidance). A will retransmit ‘Px’ at most 3 times. If A still does not receive acknowledgment from ‘B’, ‘A’ will give up and delete the packet ‘A’.
If ‘A’ does not get acknowledgment from ‘B’, there are two possibilities –
- B did not receive ‘Px’ sent by A
- B received ‘Px’ from A but A did not receive the acknowledgment sent by B.
In the second case, A will resend ‘Px’ to B. If this re-transmission also makes it to B, B will receive ‘Px’ again (a duplicate). In the worst case, B will receive 4 copies of the same frame ‘Px’. It is very important that B drop the duplicates.
The MAC layer includes a mechanism to detect (and drop) duplicate frames received over a link. The MAC header has a 2 byte frame sequence number. Each WiSense node maintains a 16 bit frame sequence number (FSN) in the MAC layer.
- 1 <= FSN <= 65535.
- 0 is not a valid FSN.
- When FSN reaches 65535, it will start back again from 1.
Whenever a node transmits a MAC frame (other than an ACK frame), it will copy the current value of the FSN into the MAC header. It will then increment this FSN. This means every frame sent out will have a different frame sequence number. Note that re-transmissions of a frame have the same sequence number. Let us take the two node example above. Suppose A sends sequence number 389 in the frame ‘Px’ sent to B. When B receives ‘Px’, B will make a note that it has received a frame with sequence number 389 from node A. Suppose A does not receive the acknowledgment sent by B and A resends ‘Px’ (containing the same sequence number 389). B will receive ‘Px’ again but it will drop this duplicate frame since the duplicate frame has the same sequence number (389) which B has already noted down from the first ‘Px’ frame received from A.
Note that a node may have multiple (N) neighbors which are sending packets to it. It has to do duplicate detection on packets received from all of these ‘N’ nodes. Each node maintains its FSN independent of other nodes which means a node can receive frames (from different nodes) with the same sequence number. So it is not enough to just store the frame sequence number from the last received frame. The MAC needs to store both the source address and the last sequence number received from that source address.
WiSense MAC maintains a table (on each non RFD) of received frames. Each entry in this table has three fields.
- Field 1 – The 16 bit MAC address of the node which sent the frame
- Field 2 – The 16 bit frame sequence number from the frame’s MAC header
- Field 3 – Time to expiry (in seconds) of this entry (8 bit value).
Currently this table can have max 32 entries.
Whenever a node receives a (non acknowledgment) frame, it will look up this table to check if the received frame is a duplicate or not. If the frame is a duplicate, it will be dropped but an acknowledgment will still be sent to the source if the received frame has the acknowledgment required bit set in the MAC header. If the received frame is not a duplicate, the corresponding entry (16 bit MAC address of the sender) in the table is updated with the new frame sequence number from the received frame. Every time an entry is updated or created, it’s time-to-expiry field is set to 8 seconds. This field is decremented every second. When this field becomes zero, the corresponding entry is deleted.
Another point which is relevant to this discussion is the short address allocated to nodes. If a node rejoins the network it will get a new short address.
Finally let us look at duplicate frame detection on RFDs (reduced function devices). A WiSense RFD only communicates with/via its parent. This means it only has to worry about duplicate packets received from its parent node. RFDs, therefore, do not need to maintain a table. They just need to maintain the frame sequence number in the last frame received from the parent. RFD MAC resets this sequence number to 0 (the invalid sequence number) every time the RFD wakes up from deep sleep.