Subject: Draft.

From: hai22 <[email-masked]>
Date: Thu, 16 Nov 2000 01:51:11 +1300

Respected Sir ,
Please find enclosed the copy of a draft  algorithm for your worthy
comments please .
Thanks.
Aun Haider
University of Canterbury
Christ Church
New Zealand
******************************************************************
                                                                                                                                                                                                                                                                                       Aun Haider.
Harsha Sirisena ..
November 2000.

Modified Rate Halving Algorithm for TCP Congestion control

Status of this Memo

This document is an Internet-Draft and is in full conformance with all provisions               of section 10 of RFC2026.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF ), its areas, and its working groups. .  Note that other groups may also distribute working documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. .  It is inappropriate to use Internet-Drafts as reference material or to cite them other than as  “ work in progress.”

The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/lid-abstracts.txt

The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html.

Abstract

This draft presents an improvement to the Rate Halving aAlgorithm for TCP Congestion Control. .  The Rate Halving aAlgorithm as well its modification presented in this documenthere areis largely independent of the details of the data retransmission strategy. .  Thus bothrate halving algorithm as well as its modified versions described in this document can be easily used with several standard and experimental TCP implementations such as New Reno, SACK, and ECN.
However, tThe present modified algorithm will able to capture all the feedback information of all feed back available through SACK and Duplicate SACK. .  Thus using it will ensure that spurious retransmission will avoided in large extent.

1. Introduction:

All Reno TCP implementations include TCP Fast Retransmit and Fast Recovery algorithms [RFC 2581]. .  In these implementations the Fast Retransmit relies on three duplicate acknowledgements to trigger the retransmission of of  a single lost segment. .  Once the Fast Retransmit has occurred TCP then waits for additional duplicate ACKs after receiving whichthen it will send the additional new data.

The result of this waiting is that the full new window of data is being transmitted in one half of one Round Trip Time (RTT). .  The burst of data usually causes the repeated bursts in successive RTTs following the recovery. .  ThisIt can lead to a positive contribution in theoverall burstiness of network traffic.

J.Hoe [1] suggested that during Fast Recovery the TCP data sender should space out retransmissions and send new data on alternate ACKs across the entire recovery RTT. .  This It eliminates the half RTT lull in the sending of data that which occurs in normal Reno TCP.  This is the Rate Halving algorithm.

The ideas of J.Hoe were further developed by M. Mathis, J. Semke, J.Mahdavi and Kevin Lahey in their paper available at [8].  TheyIt explains how to implement the Rate Halving Aalgorithm in under NewReno, SACK and ECN style TCP implementations.

This document proposes an improvement toin the original Rrate Hhalving algorithm in SACK environments in the particular situations where the receiver is supportsing the Duplicate SACKs describedas mentioned in RFC 2883 (July 2000). .  Consequently it will also change the FACK algorithm as described given in [4].

The FACK algorithm also uses the SACK information about the amount of out of order data queued at the receiver to avoid the unnecessary retranmissions ..It updates the snd_una variable and retran_data to calculate the awnd using SACK. The RFC 2883 is being proposed and standardised to incorporate the duplicate data enqueued at the receiver. .  Thus it is necessary to modify all the algorithms using SACK information for intelligent guessing ?? data stored in the receiver.

The Selective Acknowledgement (SACK) option defined in RFC 2018 is used by the TCP data receiver to acknowledge non-contiagiuous blocks of data not covered by the Cumulative Acknowledgement field. .  However, RFC 2018 does not specify the use of the SACK option when duplicate segments are received. The RFC 2883 specifies the use of the SACK option when acknowledging the receipt of a duplicate packet [6].

The RFC 2883 specifies that the use of D-SACK does not require athe separate negotiation between a TCP sender and receiver that have already negotiated SACK capability. .  The absence of a separate negotiation for D-SACK means that the TCP receiver could send D-SACK blocks when the TCP sender does not understand this extension to SACK. .  In this case, the TCP sender will simply discard any D-SACK blocks, and process the other SACK blocks in the SACK option field as it normally would..  However, RFC 2018 does not address the use of the SACK option when acknowledging a duplicate SACK..  The issues relating to D-SACK haves been discussed at length in RFC 2883.

2.       A  bBrief aOver view of the Rate Halving aAlgorithm:
            
The Rate Halving aAlgorithm is a four-state finite state machine. .  It is designed to reduce the congestion window following the detection of congestion in the network. .  In order to differentiate between the usage of cwnd within Rate Halving from the cwnd used by Reno and New Reno (RFC 2582) an alternate and comparable congestion window variable rhcwnd is defined.

rhcwnd is not inflated by dupacks during congestion ..  It represents the amount of data that a sender is allowed to keep. .  It is not considered as an offset to snd.una  but ratherit is count of data in flight , regardless of whether the segments contain new or retransmitted data.

The choice of which segment to send to send is completely independent of the algorithm itself thus giving us broad freedom to use the Rate Halving machinery with ECN (where no retransmissions occur) [RFC 2481], New Reno (where retransmissions are spread out one per RTT)[RFC 2582], or SACK  (where holes are filled in after detection at the receiver)[RFRC 2018].

This document does not discuss the reaction of the Rate Halvingh algorithm with ECN, Reno, and New Reno - that is left. Which might be next topic of our studies in for further study.future. This document deals specifically with SACK TCP with the Fast Recovery algorithm replaced by awith more intelligent Rate Halving algorithm with incorporating the extensions toin SACK as proposed in RFC 2883.

3. Modified Rate Halving Algorithm

       The original Rate Hhalving aAlgorithm has the following four states in it:

         1.  RH_INCR
              2.  RH_EXACT
         3.  RH_EST_REPAIR 
         4.  RH_EST

Note: In the following discussion we will refer these above states by the aboveir index sequence numbers given above. 

The transition from state RH_INCR(1) to RH_EXACT(2) occurs when we receive a new ACK carrying either a SACK or an ECN- Echo bit.

Here we requireneed the original algorithm to be modified when introducing in the light of D-SACK. The rules of carrying the D-SACK are given in RFC-2883. Specifically, iIf we receive the new ACK thatwhich carries the D-SACK then we need not to modify or update those variables are introduced to show the amount of data outstanding at the receiver in thewhich case where some sequence numbers are missing that havewhich are to be filed in by the transmitter of data by means of  retransmissions. Thus this modification will avoidsave us from many extra retransmissions therebywhich will improvinge the overall efficiency of Internet.
By using our modification in Rate Halving Algorithm, many spurious retransmissions will be avoided. Thus overall load on Internet for the transmitting of packet data will be decreased many folds. Because the retransmissions for duplicated data will be totally avoided at receiver. Only those segments will be transmitted which are really lost in path during transmission from transmitter to receiver. The duplicated or reordered segment will not be retransmitted at all.

The Modified Rate halving algorithm will not reduce its transmission rate for D-SACK. It is at this point the Modified rate halving will differ radically from the original version. The original algorithm will change its states from 1 to 2 on receiving any kindsort of SACK signal in the ACK and it will reduce the value of thevariable rhcwnd by ½ the distance fack has advanceds plus the size of any new holes.
ThisIt is incorrect.
Bbecause the original RFC2018 upon which the Rate Halving was designed does not differentiate between duplicated data at receiver and non- duplicated data at the receiver that inwhere by if both cases are out of sequence by some lost sequencegment numbers.

We are notdo no concerned here about preciselyat all that why the data is duplicated or reordered in the network which may again be our next future topic of study as well. But according tojust to mention that RFC 2581 could see duplicate packets could arise fromin on of the following four conditions (there may be other conditions as well):
a) Duplication by network itself due to intermediate routers etc.
b) Reordering. 
c) Timeouts due to ack losses.
d) Early RTO.
In the [7], Yin Zhang , Vern Paxon and Sscot Shenker haves listed some statistics about the pPacket reordering and replications ..They have used the definition of reordered packet as a –packet arriving with a sending sequence number lower than a packet that arrived previously .. They have recently found that about 0.3% of 136 million packets arrived out of order. Only 7% of measured hours have no reordering at all .. The highest sustained reordering rate was observed was to be sustained at 8.9% for one hour.
The 25 data sets had rates exceeding 5%. These statistics show that there is sufficient enough chance ofs for packet reordering to cause retransmissions triggeredrequested by a receiver.
AndAll of these reordering will cause the spurious retransmissions from a transmitter, which should be avoided for the sake ofmore efficiency.

3.1 Limitations of RFC 2883:

The RFC 2883 does not specify what action a TCP implementation should take forin the case of duplicated data (wWhatso ever its cause is) indicated by D-SACK.
This extension to the SACK option only enables the sender of data to detect these cases of duplicate data enqueued at the receiver, when there are alsowhich is also having some missing sequence numbers.

This extension to the SACK option enables the receiver to accurately report the reception of duplicate data. We should also keep in mind that, the loss of a single ACK will prevent this information from reaching the sender or transmitter of the packet data in net.  There are also certain cases in which receiver can send wrong information to the sender as mentioned in [9].  These cases merit to be further research. 

3.2 How to detect the D- SACK at sender or transmitter of data:

As per RFC 2883, in order for the sender or transmitter of packet data to check that the first D-SACK block of an acknowledgment in fact acknowledges duplicate data, the sender or transmitter should compare the sequence space in the first SACK block to the cumulative ACK which is carried in same ACK packet.  

If the SACK sequence space is less than this cumulative ACK, it is an indication that the segment indicated by the SACK block has been received more than once by the receiver.

Further more an implementation must not compare the sequence space in the SACK block to the TCP state variable snd.una (which carries the total cumulative ACK), as this may result in the wrong conclusion if ACK packets are reordered.  If the sequence space in the first SACK block is greater than the cumulative ACK, then the sender next compares the sequence space in the first SACK block with the sequence space in the second SACK block, if there exits any. This check can ensure that the first SACK block is reporting duplicate data that lies above the cumulative ACK.

3.3 Puroposed changes:

The original Rate Halving algorithm uses the variables fack and retran_data for increasing Rhcwnd and data transmission as per the following equations:

a). Upon the recipt of a new ACK in state 1 apply Congestion avoidance (CA) or slow start (SS) as per RFC 2581 only when following condition holds.
       snd.nxt – fack + retran_data + SMSS >=rhcwnd

b). While honouring all other constraints (such as receiver window), in any state transmit the data of length " len " if
       ( snd.nxt – fack + retran_data + len)<rhcwnd

If the data is retransmission then perform following update as well.

       retran_data +=len

While fack is used in these important calculations it depends upon the SACK in itself as follows [4].

At the core of the FACKfack congestion control algorithm there is a new (now rather bit old - since -1996) TCP state variable in the data sender or transmitter. .  This new variable is updated to reflect the forward most data held by the receiver. In the non-recovery states the snd.fack variable is updated from the acknowledgment number in the TCP header and is the same as snd.una.
During the recovery (while receiver holds the non-contiguous data –reported by SACK) the sender continues to update the snd.una from the acknowledgment number in the TCP header. .  But utilises the information contained in the TCP SACK option to update the snd.fack.When a SACK block is received which acknowledges data with higher number than the current value of snd.fack then it is updated to reflect the highest seq	uence number known to have been received plus one.
The sender algorithms that address the reliable transport continue to use the existing state variable snd.una
The sender algorithms that address the congestion management are altered to use the snd.fack, which provides a more accurate view of the network.
Here we again need to make this variable more accurate using D-SACK in the FACKack TCP to be used later on used in Rate Hhalving.  If there is a D-SACK then we should not advance the snd.fack.. Here we are differing from RFC 2883, which does not puropose any action for D-SACK. .  We suggest that in the case of a D-SACK treat the case as normal case without retransmissions being needed. The only remaining question is how to detect the D-SACK; this which can be done as per RFC 2883 and also as well as mentioned above.

Also the state variable awnd will be aeffected by from this change during the Recovery State. .  bBecause it is given as follows:
awnd = snd.nxt – snd.fack + retran_data
  
Thus we need to apply the D-SACK at the FACK level and then at the Rate Hhalving level.
At theIn Rate Hhalving level we need to check that whether an in coming ACK carries information about the duplicate enqueued segments at the receiver using the check given above (quoted from RFC 2883). .  WhateverWhere ever is the SACK information is used in Rate Halving, we needs to apply this check before state transitioning or transmission rate reduction.

At present we are in the process of developing, analysing and simulating some other new algorithms in this regard which will be reported soon.

4.   Conclusions:

Thus Tthe FACK and Rate Hhalving algorithms are the most intelligent algorithms already puroposed for thein current scenario of Internet which does not support much feed back signals except ACKsacks, SACKsacks and now currently D-SACKsacks for the sake of simplicity and efficiency and of the end to end congestion control. paradigm .  Our modification toin Rate Hhalving will further strengthen the capabilities of Rate Halving making it moreand will be useful forin end to end congestion control.

5.    References:

[1] J.Hoe, " Startup Dynamics of TCP's congestion Control and Avoidance Schemes"
      
      Master's thesis, Massachusetts Institute of Technology, June 1995.
        
      Available at http://ana-www.lcs.mit.edu/anaweb/ps-papers/hoe-thesis.ps"

[2] J. Hoe, " Improving the start up  Behavior of a Congestion Control scheme
      
      for TCP" , Proceedings of SIGCOMM' 96 , August 1996, Stanford, CA.
      
     Available at http://www.acm.org/sigcomm/sigcomm96/program.html

[3] V. Jacobson," Congestion Avoidance and Control ", Proceedings of 

      SIGCOMM 88, Palo Alto, CA.

[4]  M.Mathis, J.Mahdavi ,"Forward Acknowledgement: Refining TCP Congestion 

       Control ", Proceedings of SIGCOMM 96, Stanford, CA.

[5] M.Mathis, J.Mahdavi, S.Floyd and A.Romanow, "TCP Selective 

      Acknowledgement Options ", Internet Request for Comments 2018.

[6]  S.Floyd, J.Mahdavi, M.Mathis and M. Podolsky " An extension to the Selective 

       Acknowledgment (SACK) option for TCP" Interent Request for Comments 

       2883, July 2000.

      [7]  Yin Zhang, Vern Paxson and Scott  Shenker ," The Stationarity of Internet Path                     

             Properties : Routing, Loss and Throughput "  May 2000.

[8]   Matt Mathis, Jeff Semke and J.Mahdavi and  Kevin Lahey," The Rate Halving  

        Algorithm for TCP Congestion Control " available at 

        http://www.psc.edu/networking/ftp/papers/draft-ratehalving.txt

 [9] Stefan Savage, Neal Cardwell, David Wetherall, Tom Anderson ,"TCP 

       Congestion Control with a Misbehaving Receiver", ACM  Computer              

       Communications Review pp. 71-78 v. 29 N. 5 , October 1999.

       Available at  http://www.acm.org/sigcomm/ccr/archive/ccr-toc/ccr-toc-99.html

6.    Authors Addresses:

Aun Haider,
Dept of Electrical and Electronic Eng,
University of Canterbury, 
Christ Church, 
New  Zealand.
E-mail: [email-masked]

Assoc. Prof., Dr. Harsha Sirisena,
Dept of Electrical and Electronic Eng,
University of Canterbury,
Christ Church,
New Zealand.
E-mail: [email-masked]