The cumulative ACK is used for end to end communication. It is to avoid sending an ACK for each received packet. The cumulative ACK has been adopted by TCP protocol. However, the existing TCP cannot be used directly in jmesh because the connections between mobile devices are not stable. Another reason is that the sequence number in TCP is indexed by the unit of byte but not the unit of segment (i.e., packet) in jmesh.

Top of Form

Bottom of Form

States for End-to-End Connection

We have three connection states for each end-to-end connection. These states are borrow from existing TCP, namely, slow start, collision avoidance, and fast recovery. The fast recovery is not mandatory in TCP, but we support it in jmesh to improve the performance.

Transitions Between the Three States

State Transition from Slow Start to Collision Avoidance

Each end-to-end connection (or connection for simplicity) can only have one state at a time. In the beginning, the state is slow start. To understand the state transition, we first introduce a variable named congWin to save the size of congestion window. Initially, we have congWin=1. As long as we can in the state of slow start, we increase congWin by 1 for each acknowledged packet. Note that, when the cumulative ACK is used, a received ACK can acknowledge multiple packets. For example, if the cumulative ACK acknowledges 2 packets, we need to increase congWin by 2. The slow start state transits to collision avoidance state when the value of congWin is greater than or equal to slowStartThresh which is a threshold value. The variable slowStartThresh also has an initial value. It does not matter what the initial value is as slowStartThresh will be updated later. Specifically, when a timeout event happens and the current state is slow start, we need to set slowStartThresh=congWin/2.

State Transition from either Slow Start or Collision Avoidance to Fast Recovery

When a cumulative ACK is received, it means that all the packets with sequence number smaller than the sequence number contained in the ACK have been successfully received by the destination node. The rules of sending an ACK in will be specified in details later. Now, we just need to know that, when an out-of-order packet is received by the destination, the destination will immediately transmit (or transmit again) the ACK with the sequence number of the last in-order packet received. For example, if the destination receives packets with sequence number 1,2,3, GAP, 5, then the destination transmits an ACK with sequence number 3 immediately after packet 5 is received, no matter if an ACK with sequence number 3 has ever been sent or not. Next, if packet with sequence number 6 is received again, since packet 4 has not been received, the destination node transmits an ACK with sequence number 3 to the source again. The state transition from slow start to collision avoidance happens when three ACKs with the identical sequence number have been received by the source node.

State Transition from Fast Recovery to Slow Start

When the fast recovery state is reached, a fast re-transmission will take place and new virtual timer will be started. We will introduce the rule of setting a virtual timer later. When the virtual timer is timeout but no ACK has been received with a sequence number beyond the sequence number of the re-transmitted packet, fast recovery state transmits back to slow start state.

State Transition from Fast Recovery to Collision Avoidance

When an ACK with a new (i.e., higher) sequence number is received, fast recovery state transmits back the collision avoidance state.

Author
Zehua Wang
Applied Engineering Scientist