NCA Use Cases : Nomination Algorithm  
                -------------------------------------
                             2000-05-02
                            Version: 1.1


Section D: Sender Protocol

  State Information:
    csmNominee     - The address of the current nominee receiver. Set to 0 if
                     there is no current nominee receiver.
    csmLPE         - The current loss probability estimate reported by the
                     nominee receiver.
    csmRTT         - The current round trip time to the sender reported by the
                     nominee receiver. In milliseconds.
    csmSetTime     - The time, in milliseconds, when csmLPE, csmRTT and
                     csmNominee were set.

  D.1 Initialization

  This use case begins when the sender is instantiated. The state information
is initialized as follows:

    csmNominee     = 0
    csmLPE         = -1.0
    csmRTT         = 0
    csmSetTime     = currentTime in milliseconds

This use case ends when the state information is initialized.

  D.2 Processing a Received CSM Packet

  This use case begins when a CSM packet arrives at the sender. The following
test is performed (addr, lpe and rtt are the CSM packet receiver address, loss
probability estimate and source to receiver round trip time in milliseconds.
currentTime is the current time in milliseconds. The timeout parameter is set
to some constant (e.g., 17000 milliseconds).):

    if ((csmNominee == 0) OR
        (addr == csmNominee) OR
        ((0.0 <= lpe <= 1.0) AND (csmLPE < 0.0)) OR
        ((0.0 <= lpe <= 1.0) AND (0.0 <= csmLPE <= 1.0) AND
         (g(lpe, rtt) > (1.1 * g(csmLPE, csmRTT)))) OR
        ((lpe < 0.0) AND (csmLPE < 0.0) AND (rtt > (1.1 * csmRTT))) OR
        (currentTime > (csmSetTime + 17000)))
    {
      csmNominee = addr
      csmLPE     = lpe
      csmRTT     = rtt
      csmSetTime = currentTime
      Call Updating the Nominee Receiver Address Use Case in the repair
        service algorithm passing addr
      Call Updating the Nonimee Receiver Use Case in the rate control
        algorithm passing addr and rtt
    }

The function g(lpe,rtt) is as follows:

    g(lpe,rtt) = (rtt * squareroot(lpe)), 0 <= lpe <= 1, rtt >= 0
               = 0,                       otherwise

This use case ends when either Use Case D.3 returns or the CSM packet is
ignored.

  D.3 Processing a Received NPM Packet

  This use case begins when a NPM packet arrives at the sender. The NPM packet
is ignored. This use case ends when the NPM packet is ignored.



Section E: Receiver Protocol

  State Information :
    isNomineeFlag - If true, indicates that this receiver has been nominated
                    to send congestion control signals to the sender,
                    otherwise false.
    maxNomineeSeq - The maximum data packet sequence number from the packets
                    used to update the nominee receiver information.
    npmTimestamp  - The absolute time, in milliseconds, when the last NPM
                    packet was sent.

  E.1 Initialization

  This use case begins when the receiver protocol is initialized by the upper
layers. The state information is initialized as follows:

    isNomineeFlag = false
    maxNomineeSeq = 0
    npmTimestamp  = 0

A sliding loss probability estimate (LPE) window with a fixed maximum size
(e.g., 200 packets) is created for recording the arrival of original data
packets and computing the LPE. One or more CSM packets are created with the
receiver address set to the local receiver's address, the LPE set to -1000 and
the senderRTT set to and -1. The CSM packet(s) are unicast to the receiver's
upstream repair server. The CSM Timer is started with a duration of a random
variate, uniformly distributed between 0 and 1.0, times some fixed time value
(e.g., 5000 milliseconds). This use case ends when the CSM Timer has been
started.

  E.2 Processing a Received Original Data Packet

  This use case begins when an original data packet (a data packet with the
retransmission flag set to false) is received. The sliding LPE window is
updated to record the reception of the data packet using the following rules:

    - the window may expand from being empty to the maximum size (e.g., 200)
    - the window never shrinks in size
    - once at the maximum window size, the window may be slid forward while
      the window size remains constant
    - the window may only be slid forward (never backward)

After the LPE window has been updated, Use Case E.4 is called passing the data
packet sequence number and nominee receiver address. This use case ends when
Use Case E.4 returns.

  E.3 Processing a Received SPM Packet

  This use case begins when a SPM packet is received. Use Case E.4 is called
passing the SPM packet maximum data packet sequence number and nominee
receiver address. This use case ends when Use Case E.4 returns.

  E.4 Updating the Nominee Receiver

  This use case begins when the nominee receiver must be updated. The
following processing is performed (seq and nomineeAddr are the data packet
sequence number and nominee receiver address passed into this use case.
currentTime is the current time in milliseconds.):

    if (seq < maxNomineeSeq)
    {
      End Use Case
    }
    maxNomineeSeq = seq
    if (isNomineeFlag == true)
    {
      if (nomineeAddr != receiver's IP address)
      {
        isNomineeFlag = false
        Call Disable Fast NAK Use Case in the repair service algorithm
      }
      else
      {
        if ((currentTime < npmTimestamp) OR
            (currentTime > (npmTimestamp + 10000)))
        {
          Unicast a NPM packet with the nominee address set to nomineeAddr to
            the receiver's upstream repair server
          npmTimestamp = currentTime
        }
      }
    }
    else
    {
      if (nomineeAddr == receiver's IP address)
      {
        isNomineeFlag = true
        Call Enable Fast NAK Use Case in the repair service algorithm
        Unicast a NPM packet with the nominee address set to nomineeAddr to
          the receiver's upstream repair server
        npmTimestamp = currentTime
      }
    }

This use case ends when either the Disable Fast NAK Use Case in the repair
service algorithm returns, npmTimestamp is updated, or no changes take place.

  E.5 CSM Timer Service Routine

  This use case begins when the CSM Timer expires. The following processing is
perfomed (windowSize is the current LPE window size in packets, and
capsulesReceived is the current count of received original data packets in the
LPE window):

    if (windowSize < 100)
    {
      lpe = -1000
    }
    else
    {
      lpe = (1000 * (windowSize - capsulesReceived) / windowSize)
    }
    if (receiver to sender round trip time (RTT) is unavailable)
    {
      rtt = 100
    }
    else
    {
      rtt = current receiver to sender RTT estimate in milliseconds
    }
    Unicast a CSM packet with the receiver address set to the local receiver's
      address, the LPE set to lpe and the sender RTT set to rtt to the
      receiver's upstream repair server
    Start the CSM Timer using a constant duration (e.g., 5000 milliseconds)

This use case ends when the CSM Timer is started.



Section F: Repair Server Protocol

  State Information:
    currentNominee  - The address of the current nominee. Selected by the
                      sender.
    maxNomineeSeq   - The maximum data packet sequence number from the packets
                      used to update the current nominee receiver information.
    csmNominee      - The address of the worst receiver downstream.
    csmLPE          - The current loss probability estimate reported by the
                      worst receiver downstream.
    csmRTT          - The current round trip time to the sender reported by
                      the worst receiver downstream.
    csmSetTime      - The time, in milliseconds, when csmLPE, csmRTT and
                      csmNominee were set.

  F.1 Initialization

  This use case begins when the repair server receives the first SPM packet.
The state information is initialized as follows:

    currentNominee = 0
    maxNomineeSeq  = 0
    csmNominee     = 0
    csmLPE         = -1.0
    csmRTT         = 0
    csmSetTime     = currentTime in milliseconds

The CSM Timer is started using a constant duration (e.g., 7000 milliseconds).
This use case ends when the CSM Timer has been started.

  F.2 Processing a Received CSM Packet

  This use case begins when a CSM packet arrives at the repair server. The
following test is performed (addr, lpe and rtt are the CSM packet receiver
address, loss probability estimate and sender to receiver round trip time in
milliseconds. currentTime is the current time in milliseconds. The timeout
parameter is set to some constant (e.g., 17000 milliseconds)):

    if ((csmNominee == 0) OR
        (addr == csmNominee) OR
        ((0.0 <= lpe <= 1.0) AND (csmLPE < 0.0)) OR
        ((0.0 <= lpe <= 1.0) AND (0.0 <= csmLPE <= 1.0) AND
         (g(lpe, rtt) > (1.1 * g(csmLPE, csmRTT)))) OR
        ((lpe < 0.0) AND (csmLPE < 0.0) AND (rtt > (1.1 * csmRTT))) OR
        (currentTime > (csmSetTime + 17000)))
    {
      csmNominee = addr
      csmLPE     = lpe
      csmRTT     = rtt
      csmSetTime = currentTime
      Unicast a CSM packet with the receiver address set to csmNominee, the
        LPE set to csmLPE and the sender RTT set to csmRTT to this repair
        server's repair server
      Cancel the CSM Timer
      Start the CSM Timer with a constant duration (e.g., 7000 milliseconds)
    }

The function g(lpe,rtt) is as follows:

    g(lpe,rtt) = (rtt * squareroot(lpe)), 0 <= lpe <= 1, rtt >= 0
               = 0,                       otherwise

This use case ends when either Use Case F.3 returns or the CSM packet is
ignored.

  F.3 Processing a Received Original Data Packet

  This use case begins when an original data packet (a data packet with the
retransmission flag set to false) is received. Use Case F.5 is called passing
the data packet sequence number and nominee receiver address. This use case
ends when Use Case F.5 returns.

  F.4 Processing a Received SPM Packet

  This use case begins when a SPM packet is received. Use Case F.5 is called
passing the SPM packet maximum data packet sequence number and nominee
receiver address. This use case ends when Use Case F.5 returns.

  F.5 Updating the Nominee Receiver

  This use case begins when the nominee receiver must be updated. The
following processing is performed (seq and nomineeAddr are the data packet
sequence number and nominee receiver address passed into this use case):

    if (seq >= maxNomineeSeq)
    {
      maxNomineeSeq = seq
      if (nomineeAddr != currentNominee)
      {
        currentNominee = nomineeAddr
        Call Disable Fast NAK Use Case in the repair service algorithm
      }
    }

This use case ends when either the Disable Fast NAK Use Case returns or no
changes take place.

  F.6 Processing a Received NPM Packet

  This use case begins when a NPM packet is received. The following processing
is performed (nomineeAddr is the NPM packet nominee receiver address):

    if (nomineeAddr == currentNominee)
    {
      Call Enable Fast NAK Use Case in the repair service algorithm
    }

This use case ends when either the Enable Fast NAK Use Case returns or no
changes take place.

  F.7 CSM Timer Service Routine

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

    if (currentTime in milliseconds > (csmSetTime + 17000))
    {
      csmNominee = 0
      csmLPE     = -1.0
      csmRTT     = 0
      csmSetTime = currentTime in milliseconds
    }
    if (csmNominee != 0)
    {
      Unicast a CSM packet with the receiver address set to csmNominee, the
        LPE set to csmLPE and the sender RTT set to csmRTT to this repair
        server's repair server
    }
    Start the CSM Timer with a constant duration (e.g., 7000 milliseconds)

This use case ends when the CSM Timer has been started.



Appendix A: Packet Formats

 Congestion Status Message (CSM) Packet:
   CSM packets are unicast from a receiver or repair server to its upstream
   repair server, which may be the sender. CSM packets contain:

       Receiver Address
       Loss Probability Estimate
       Sender to Receiver RTT

 Nominee Path Message (NPM) Packet:
   NAM packets are unicast from a receiver or repair server to its upstream
   repair server, which may be the sender. NPM packets contain:

       Nominee Receiver Address