NCA Use Cases : Rate Control Algorithm  
                --------------------------------------
                              1999-12-08
                             Version: 1.0


Section G: Sender Protocol

  State Information:
    nominee          - The current nominee receiver address.  There is no
                       nominee if equal to 0.
    timerNominee     - The address of the nominee receiver when the CCM Timer
                       was set.
    winSize          - The current congestion window sizer. Must be greater 
                       than or equal to 1.0 at all times.
    ssThreshold      - The slow start threshold window size.
    winLowerSeq      - The sequence number of the oldest original data packet
                       that has not received a CCM packet response. Always the
                       lower end of the congestion window. Must be greater
                       than or equal to 0.
    dupLowerSeq      - The number of duplicate CCM packets received for the
                       winLowerSeq data packet.
    maxSeqSent       - The sequence number of the most recent original data
                       packet sent. This may be either in or outside of the
                       congestion window. Must be greater than or equal to 0.
    smoothedRTT      - The smoothed RTT estimate in milliseconds.
    rttVariance      - The mean deviation of the RTT estimate in milliseconds
                       (a la TCP).
    ccmTimeout       - The maximum amount of time in milliseconds to wait for
                       a CCM packet. If this time expires and no CCM packet is
                       received, then the congestion window size is dropped to
                       1.0.
    backoffFactor    - The exponential backoff factor used in case of
                       successive timeouts.
    fastRecovFlag    - A flag for recording if fast recovery is active or not.
    fastRecovSeq     - The sequence number of the last data packet in the
                       congestion window when fast recovery is activated.
                       Set to 0 when fast recovery is not active.
    maxBurstCount    - The number of original data packets sent since the last
                       CCM packet was received.

  G.1 Initialization

  This use case begins when the sender is instantiated. The constants used by
NCA are as follows:

    MAX_WINDOW      = 256
    MAX_BURST       = 4
    FR_MAX_BURST    = 2
    MIN_SS_THRESH   = 2
    MAX_BACKOFF     = 64

The state information is initialized as follows:

    nominee       = 0
    timerNominee  = 0
    winSize       = 1.0
    ssThreshold   = 64
    winLowerSeq   = initial data packet sequence number
    dupLowerSeq   = 0
    maxSeqSent    = (winLowerSeq - 1)
    smoothedRTT   = 0
    rttVariance   = 0
    ccmTimeout    = 1000
    backoffFactor = 1
    fastRecovFlag = false
    fastRecovSeq  = 0
    maxBurstCount = 0

This use case ends when the state information has been initialized.

  G.2 Processing a Received CCM Packet

  This use case begins when a CCM packet arrives at the sender. The CCM packet
is processed as follows (ccmAddr, ccmRetransFlag, seq and timestamp are the
CCM packet IP source address, retransmission flag, sequence number and time
stamp):

    if (ccmAddr == nominee)
    {
      backoffFactor = 1
      maxBurstCount = 0
      if (ccmRetransFlag == false)
      {
        Call Use Case G.3 passing timestamp
      }
      Call Use Case G.5 passing seq
      if (winLowerSeq > maxSeqSent)
      {
        Cancel CCM Timer
      }
    }

This use case ends when either Use Case G.4 returns or the CCM Timer is
canceled.

  G.3 Updating the RTT Estimate

  This use case begins when the sender receives a CCM and has to update its
RTT estimate. The CCM packet is processed as follows (timestamp is the time
stamp value of the CCM packet passed to this use case):

    newRTT = (timestamp - currentTime in milliseconds)
    if (smoothedRTT == 0)
    {
      smoothedRTT = newRTT
      ccmTimeout  = smoothedRTT
    }
    else
    {
      Call Use Case c.4 passing the value of newRTT
    }

This use case ends when either smoothedRTT and ccmTimeout are updated or Use 
Case G.4 returns.

  G.4 Updating the RTT Estimate and Variance

  This use case begins when both the RTT estimate and variance must be updated
given a new value of newRTT. The following processing is performed:

    error = (newRTT - smoothedRTT)
    smoothedRTT = (smoothedRTT + (error / 8))
    if (rttVariance == 0)
    {
      rttVariance = ABS(error)
    }
    else
    {
      rttVariance = (rttVariance + ((ABS(error) - rttVariance) / 4))
    }
    ccmTimeout = (smoothedRTT + (4 * rttVariance))

Note that ABS() is the absolute value function. This use case ends when
ccmTimeout has been updated.

  G.5 Updating the Congestion Window

  This use case begins when the congestion window needs to be updated due to
the arrival of a CCM packet. The congestion window is updated as follows (seq
is the sequence number of the CCM packet passed to this use case):

    if (seq == winLowerSeq)
    {
      dupLowerSeq = (dupLowerSeq + 1)
    }
    else
    {
      if (seq > winLowerSeq)
      {
        Call Use Case C.6
      }
      if (fastRecovFlag == true)
      {
        if (winLowerSeq > fastRecovSeq)
        {
          Call Use Case G.9
        }
        else
        {
          Call Use Case G.8
        }
      }
      else
      {
        if (dupLowerSeq >= 3)
        {
          Call Use Case G.10
        }
      }

This use case ends when the congestion window has been updated.

  G.6 Sliding the Congestion Window Forward

  This use case begins when the congestion window is ready to be slid forward.
The congestion window is updated as follows (seq is the sequence number of the
CCM packet passed to this use case):

    if (fastRecovFlag == false)
    {
      Call Use Case G.7
    }
    winLowerSeq = seq
    dupLowerSeq = 0

This use case ends when dupLowerSeq is set to 0.

  G.7 Increasing the Congestion Window Size

  This use case begins when a CCM packet is received and the congestion window
size must be increased while not in fast recovery. The congestion window is
updated as follows:

    if (winSize <= ssThreshold)
    {
      winSize = (winSize + 1.0)
    }
    else
    {
      winSize = (winSize + (1.0 / FLOOR(winSize)))
    }
    winSize = MIN(winSize, MAX_WINDOW)
    winSize = MAX(winSize, 1.0)

Note that the FLOOR() function returns the largest value that is not greater
than the argument and is equal to a mathematical integer. This use case ends
when winSize has been updated.

  G.8 Increasing the Congestion Window Size in Fast Recovery

  This use case begins when a CCM packet is received and the congestion window
size must be increased while in fast recovery. The congestion window is
updated as follows:

    winSize = (winSize + 1.0)
    winSize = MIN(winSize, MAX_WINDOW)
    winSize = MAX(winSize, 1.0)

This use case ends when winSize has been updated.

  G.9 Leaving Fast Recovery

  This use case begins when the sender must exit the fast recovery state. The
following processing is performed:

    fastRecovFlag = false
    fastRecovSeq  = 0
    winSize       = ssThreshold
    winSize       = MIN(winSize, MAX_WINDOW)
    winSize       = MAX(winSize, 1.0)

This use case ends when winSize has been updated.

  G.10 Entering Fast Recovery

  This use case begins when the sender must enter the fast recovery state.
The following processing is performed:

    fastRecovFlag = true
    fastRecovSeq  = (winLowerSeq + FLOOR(winSize) - 1)
    ssThreshold   = MAX((winSize / 2.0), MIN_SS_THRESH)
    winSize       = (ssThreshold + 3.0)
    winSize       = MIN(winSize, MAX_WINDOW)
    winSize       = MAX(winSize, 1.0)

This use case ends when winSize has been updated.

  G.11 Testing if an Original Data Packet Can Be Sent

  This use case begins when an original data packet with a sequence number of
(maxSeqSent + 1) is to be sent. The following processing is performed:

    if (maxSeqSent >= (winLowerSeq + FLOOR(winSize) - 1))
    {
      The original data packet cannot be sent at the current time
      End Use Case
    }
    if (fastRecovFlag == true)
    {
      if (maxBurstCount >= FR_MAX_BURST)
      {
        The original data packet cannot be sent at the current time
        End Use Case
      }
    }
    else
    {
      if (maxBurstCount >= MAX_BURST)
      {
        The original data packet cannot be sent at the current time
        End Use Case
      }
    }
    The original data packet can be sent at the current time

This use case ends when the determination is made to either allow or disallow
the original data packet to be sent.

  G.12 Sending an Original Data Packet

  This use case begins when an original data packet with a sequence number of
(maxSeqSent + 1) is ready to be sent and Use Case G.11 allows the packet to be
sent. The following processing is performed:

    maxSeqSent    = (maxSeqSent + 1)
    maxBurstCount = (maxBurstCount + 1)
    Cancel CCM Timer
    if (maxSeqSent >= winLowerSeq)
    {
      timerNominee = nominee
      Start the CCM Timer with a duration of (backoffFactor * ccmTimeout)
    }

This use case ends when the CCM Timer is either canceled or canceled and 
restarted.

  G.13 CCM Timer Service Routine

  This use case begins when the CCM Timer expires. The following processing is
performed:

    if (timerNominee == 0)
    {
      ssThreshold   = 64
      backoffFactor = 1
    }
    else
    {
      ssThreshold   = MAX((winSize / 2.0), MIN_SS_THRESH)
      backoffFactor = MIN((backoffFactor * 2), MAX_BACKOFF)
    }
    winSize       = 1.0
    winLowerSeq   = (maxSeqSent + 1)
    fastRecovFlag = false
    fastRecovSeq  = 0
    maxBurstCount = 0

This use case ends when winLowerSeq has been updated.

  G.14 Updating the Nonimee Receiver

  This use case begins when the nominee receiver address has changed and must
be updated. The following processing is performed (addr is the new nominee
address):

    nominee = addr
    if (nominee == 0)
    {
      ccmTimeout = the initial value (e.g., 1000 milliseconds)
    }
This use case ends when nominee has been updated.


Section H: Receiver Protocol

  State Information:
    isNomineeFlag - If true, indicates that this receiver has been nominated
                    to send congestion control signals to the sender,
                    otherwise false (from NCA Nomination Algorithm).

  H.1 Processing a Received Data Packet

  This use case begins when a data packet is received. All receivers must
maintain the lowest sequence number of all outstanding data packets at all
times. The following processing is performed:

    if ((isNomineeFlag == true) AND
        (the data packet has not been received before))
    {
      Send a CCM packet to the sender
        (seq = lowest outstanding data packet sequence number,
         timestamp = data packet timestamp,
         retrans = data packet retransmission flag)
    }

This use case ends when either a CCM packet is sent to the sender or no
processing occurs.


Appendix A: Packet Formats

 Congestion Control Message (CCM) Packet:
   Unicast from the nominated receiver to the sender.

   Fields: Version Number, Packet Type, Multicast Group Address, Port Number,
           Sequence Number, Timestamp, Retransmission Flag