6.3 IP fragment tracking algorithm

Fragment Tracking Algorithm Explanation

Overview

This algorithm tracks received IP fragments using a BitSet data structure, where each bit represents an 8-byte chunk of the final datagram. The completion check determines if all necessary fragments have been received.

Detailed Breakdown

Data Structure

private final BitSet receivedFragments;

• BitSet is used as an efficient boolean array where each bit represents an 8-byte fragment block
• For example, a 1500-byte datagram would need (1500 + 7) / 8 = 188 bits to track all fragments

Completion Check

public boolean isComplete() {
    return complete && 
           receivedFragments.cardinality() == 
           (expectedLength + 7) / 8;
}

Components:

1. complete flag:

   • Set when the last fragment is received
   • Last fragment indicates total expected datagram length

2. receivedFragments.cardinality():

   • Returns count of set bits (1s) in the BitSet
   • Each set bit represents a received 8-byte block

3. (expectedLength + 7) / 8:

   • Expected length is the total datagram size in bytes
   • Adding 7 and dividing by 8 rounds up to nearest 8-byte block
   • Gives total number of 8-byte blocks needed

Example Calculation

Consider a 1400-byte datagram:

expectedLength = 1400 bytes
blocks needed = (1400 + 7) / 8 = 176 blocks

Fragment 1: 0-799 bytes    (blocks 0-99)
Fragment 2: 800-1199 bytes (blocks 100-149)
Fragment 3: 1200-1399 bytes (blocks 150-175)

BitSet after receiving fragments:
- Fragment 1 sets bits 0-99
- Fragment 2 sets bits 100-149
- Fragment 3 sets bits 150-175

receivedFragments.cardinality() = 176 (all blocks received)
(expectedLength + 7) / 8 = 176 (expected blocks)

isComplete() returns true when:
1. complete flag is true (last fragment received)
2. 176 = 176 (all blocks accounted for)

Fragment Marking

private void markFragmentReceived(int offset, int length) {
    int startBit = offset / 8;      // Start block number
    int endBit = (offset + length + 7) / 8;  // End block number
    receivedFragments.set(startBit, endBit);  // Mark blocks as received
}

Key Points

1. 8-Byte Alignment

   • IPv4 fragments are 8-byte aligned
   • Each bit in BitSet represents one 8-byte block
   • Rounding up ensures partial blocks are tracked

2. Efficiency

   • BitSet provides efficient storage (1 bit per block)
   • Fast cardinality calculation (hardware optimized)
   • O(1) completion check

3. Completeness Check

   • Both conditions must be true:
     1. Last fragment received (complete flag)
     2. All blocks received (cardinality match)
   • Prevents premature completion

4. Memory Usage

   • For max IP size (65535 bytes):
     • Needs (65535 + 7) / 8 = 8192 bits
     • BitSet only uses 1024 bytes of memory

5. Error Handling

   • Missing fragments: cardinality will be too low
   • Duplicate fragments: doesn't affect cardinality
   • Invalid length: comparison will fail

Would you like me to explain:

1. How fragment overlap is detected using this system?
2. How the expected length is calculated from fragments?
3. How timeouts interact with this tracking mechanism?