Opened 4 weeks ago

Closed 3 weeks ago

#2443 closed enhancement (fixed)

Make SSU compliant with RFC 6298

Reported by: zab Owned by: zzz
Priority: major Milestone: 0.9.39
Component: router/transport Version: 0.9.38
Keywords: ssu Cc:
Parent Tickets:

Description

Current SSU implementation of RTT and RTO calculation is coded against RFC 2988, but that has been obsoleted by 6298.

Few major differences from what I see in the code and what the RFC says:

Initial RTO should be 1 second, not 3 (section 2.1)
Initial RTT and RTTVAR are not set correctly (section 2.2)

The latter of these is causing the large RTTs I've observed on newly established connections.

Subtickets

Change History (4)

comment:1 Changed 4 weeks ago by zab

A patch that addresses above issues plus some others:

#
# old_revision [c89bc469fa309546ca7532cd3908a172284e5df4]
#
# patch "router/java/src/net/i2p/router/transport/udp/PeerState.java"
#  from [8da5f77c8ec62803af2f12a5efe2b18d79ada9d1]
#    to [f229219bbe0181123fb99cc74483a86c012740c9]
# 
# patch "router/java/src/net/i2p/router/transport/udp/UDPTransport.java"
#  from [571355e1913c9c64726d6c5cd7e16c771b671548]
#    to [7c32ff9fc6e6993481a2484466f8c3ea78908b12]
#
============================================================
--- router/java/src/net/i2p/router/transport/udp/PeerState.java	8da5f77c8ec62803af2f12a5efe2b18d79ada9d1
+++ router/java/src/net/i2p/router/transport/udp/PeerState.java	f229219bbe0181123fb99cc74483a86c012740c9
@@ -314,10 +314,10 @@ public class PeerState {
      */
     public static final int MAX_MTU = Math.max(LARGE_MTU, MAX_IPV6_MTU);
     
-    private static final int MIN_RTO = 100 + ACKSender.ACK_FREQUENCY;
-    private static final int INIT_RTO = 3*1000;
-    public static final int INIT_RTT = INIT_RTO / 2;
-    private static final int MAX_RTO = 15*1000;
+    private static final int MIN_RTO = 1000;
+    private static final int INIT_RTO = 1000;
+    public static final int INIT_RTT = -1;
+    private static final int MAX_RTO = 60*1000;
     private static final int CLOCK_SKEW_FUDGE = (ACKSender.ACK_FREQUENCY * 2) / 3;
     
     /**
@@ -1226,16 +1226,18 @@ public class PeerState {
      *  Caller should synch on this
      */
     private void recalculateTimeouts(long lifetime) {
-        // the rttDev calculation matches that recommended in RFC 2988 (beta = 1/4)
-        _rttDeviation = _rttDeviation + (int)(0.25d*(Math.abs(lifetime-_rtt)-_rttDeviation));
+        if (_rtt == -1) {
+	    // first measurement
+	    _rtt = (int) lifetime;
+	    _rttDeviation = (int)(lifetime / 2);
+	} else {
+            // the rttDev calculation matches that recommended in RFC 2988 (beta = 1/4)
+            _rttDeviation = (int)( 0.75*_rttDeviation + 0.25*Math.abs(lifetime-_rtt) );
         
-        float scale = RTT_DAMPENING;
-        // the faster we are going, the slower we want to reduce the rtt
-        //if (_sendBps > 0)
-        //    scale = lifetime / ((float)lifetime + (float)_sendBps);
-        //if (scale < 0.001f) scale = 0.001f;
+            float scale = RTT_DAMPENING;
         
-        _rtt = (int)(_rtt*(1.0f-scale) + (scale)*lifetime);
+            _rtt = (int)(_rtt*(1.0f-scale) + (scale)*lifetime);
+	}
         // K = 4
         _rto = Math.min(MAX_RTO, Math.max(minRTO(), _rtt + (_rttDeviation<<2)));
         //if (_log.shouldLog(Log.DEBUG))
@@ -1821,13 +1823,15 @@ public class PeerState {
                               + " remaining"
                               + " for message " + state.getMessageId() + ": " + state);
 
-                if (state.getPushCount() > 0)
+                int rto = getRTO();
+                if (state.getPushCount() > 0) {
                     _retransmitter = state;
+		    rto = Math.min(MAX_RTO, rto << state.getPushCount()); // Section 5.5 RFC 6298
+		}
 
                 if (state.push())
                     _messagesSent++;
             
-                int rto = getRTO();
                 state.setNextSendTime(now + rto);
 
                 //if (peer.getSendWindowBytesRemaining() > 0)
============================================================
--- router/java/src/net/i2p/router/transport/udp/UDPTransport.java	571355e1913c9c64726d6c5cd7e16c771b671548
+++ router/java/src/net/i2p/router/transport/udp/UDPTransport.java	7c32ff9fc6e6993481a2484466f8c3ea78908b12
@@ -2720,7 +2720,7 @@ public class UDPTransport extends Transp
         for (PeerState peer : _peersByIdent.values()) {
             if ((!includeEverybody) && now - peer.getLastReceiveTime() > 5*60*1000)
                 continue; // skip old peers
-            if (peer.getRTT() > PeerState.INIT_RTT - 250)
+            if (peer.getRTT() > 1250)
                 continue; // Big RTT makes for a poor calculation
             skews.addElement(Long.valueOf(peer.getClockSkew() / 1000));
         }
Last edited 4 weeks ago by zab (previous) (diff)

comment:2 Changed 4 weeks ago by zzz

  • Milestone changed from undecided to 0.9.39
  • Status changed from new to accepted

related: #2445 but it's a lot more complex.
This ticket parallels changes we made to streaming in 2013 see #979. Initial RTO should be set to RTT + RTT/2.
The above changes also increase the min RTO from 350 to 1000.
Testing now but this looks like a winner.

comment:3 Changed 3 weeks ago by zab

Here is an updated patch which tries to measure RTT from the establishment phase and carry it over into PeerState:

Edit: patch updated to not initialize to -1

#
# old_revision [d505721e58c3b7bbcdde170cecf9ed3f2e1843d3]
#
# patch "router/java/src/net/i2p/router/transport/udp/ACKSender.java"
#  from [7fde4315c7a18dbb4ca1fcb42a3f50088931e588]
#    to [a6a1dc4bac5263da343e650c9bf5af495489e397]
# 
# patch "router/java/src/net/i2p/router/transport/udp/EstablishmentManager.java"
#  from [7a892873d89d81ddbe1afd37a02af126e19ed7b1]
#    to [b9077993ad453bfbfa0a353a9bffb5dc183c683a]
# 
# patch "router/java/src/net/i2p/router/transport/udp/InboundEstablishState.java"
#  from [c746bfee971f5ea0f6bb944120177c0e2df7afb9]
#    to [1d55813e913298397a90adacaafbda7b35108c42]
# 
# patch "router/java/src/net/i2p/router/transport/udp/OutboundEstablishState.java"
#  from [876f0ffc4d4cf09c0a54d0c2941fea3bcc144b71]
#    to [b3d77f295db363b3a795080db8557da75dbb2cc4]
# 
# patch "router/java/src/net/i2p/router/transport/udp/PeerState.java"
#  from [8da5f77c8ec62803af2f12a5efe2b18d79ada9d1]
#    to [b38a05ce29d14485fc4fa2a7e77100620193aac7]
# 
# patch "router/java/src/net/i2p/router/transport/udp/UDPTransport.java"
#  from [67540d7a57d681086701db0defcd869fce64192e]
#    to [386ad7ce469d27c421b0807a54dcc667e8d551cc]
#
============================================================
--- router/java/src/net/i2p/router/transport/udp/ACKSender.java	7fde4315c7a18dbb4ca1fcb42a3f50088931e588
+++ router/java/src/net/i2p/router/transport/udp/ACKSender.java	a6a1dc4bac5263da343e650c9bf5af495489e397
@@ -62,7 +62,7 @@ class ACKSender implements Runnable {
     
     public synchronized void shutdown() { 
         _alive = false;
-        PeerState poison = new PeerState(_context, _transport, new byte[4], 0, null, false);
+        PeerState poison = new PeerState(_context, _transport, new byte[4], 0, null, false, 0);
         poison.setTheyRelayToUsAs(POISON_PS);
         _peersToACK.offer(poison);
         for (int i = 1; i <= 5 && !_peersToACK.isEmpty(); i++) {
============================================================
--- router/java/src/net/i2p/router/transport/udp/EstablishmentManager.java	7a892873d89d81ddbe1afd37a02af126e19ed7b1
+++ router/java/src/net/i2p/router/transport/udp/EstablishmentManager.java	b9077993ad453bfbfa0a353a9bffb5dc183c683a
@@ -694,7 +694,7 @@ class EstablishmentManager {
         
         RouterIdentity remote = state.getConfirmedIdentity();
         PeerState peer = new PeerState(_context, _transport,
-                                       state.getSentIP(), state.getSentPort(), remote.calculateHash(), true);
+                                       state.getSentIP(), state.getSentPort(), remote.calculateHash(), true, state.getRTT());
         peer.setCurrentCipherKey(state.getCipherKey());
         peer.setCurrentMACKey(state.getMACKey());
         peer.setWeRelayToThemAs(state.getSentRelayTag());
@@ -813,7 +813,7 @@ class EstablishmentManager {
             _outboundByClaimedAddress.remove(claimed, state);
         _outboundByHash.remove(remote.calculateHash(), state);
         PeerState peer = new PeerState(_context, _transport,
-                                       state.getSentIP(), state.getSentPort(), remote.calculateHash(), false);
+                                       state.getSentIP(), state.getSentPort(), remote.calculateHash(), false, state.getRTT());
         peer.setCurrentCipherKey(state.getCipherKey());
         peer.setCurrentMACKey(state.getMACKey());
         peer.setTheyRelayToUsAs(state.getReceivedRelayTag());
============================================================
--- router/java/src/net/i2p/router/transport/udp/InboundEstablishState.java	c746bfee971f5ea0f6bb944120177c0e2df7afb9
+++ router/java/src/net/i2p/router/transport/udp/InboundEstablishState.java	1d55813e913298397a90adacaafbda7b35108c42
@@ -64,6 +64,8 @@ class InboundEstablishState {
     private int _createdSentCount;
     // default true
     private boolean _introductionRequested = true;
+
+    private int _rtt;
     
     public enum InboundState {
         /** nothin known yet */
@@ -296,6 +298,8 @@ class InboundEstablishState {
      */
     public synchronized long getNextSendTime() { return _nextSend; }
 
+    synchronized int getRTT() { return _rtt; }
+
     /** RemoteHostId, uniquely identifies an attempt */
     RemoteHostId getRemoteHostId() { return _remoteHostId; }
 
@@ -356,6 +360,10 @@ class InboundEstablishState {
                 _currentState = InboundState.IB_STATE_CONFIRMED_PARTIALLY;
         }
         
+        if (_createdSentCount == 1) {
+             _rtt = (int) ( _context.clock().now() - _lastSend );
+	}	
+
         packetReceived();
     }
     
============================================================
--- router/java/src/net/i2p/router/transport/udp/OutboundEstablishState.java	876f0ffc4d4cf09c0a54d0c2941fea3bcc144b71
+++ router/java/src/net/i2p/router/transport/udp/OutboundEstablishState.java	b3d77f295db363b3a795080db8557da75dbb2cc4
@@ -74,6 +74,7 @@ class OutboundEstablishState {
     private long _confirmedSentTime;
     private long _requestSentTime;
     private long _introSentTime;
+    private int _rtt;
     
     public enum OutboundState {
         /** nothin sent yet */
@@ -179,6 +180,8 @@ class OutboundEstablishState {
      *  @since 0.9.24
      */
     public boolean needIntroduction() { return _needIntroduction; }
+
+    synchronized int getRTT() { return _rtt; }
     
     /**
      *  Queue a message to be sent after the session is established.
@@ -304,6 +307,10 @@ class OutboundEstablishState {
             _currentState == OutboundState.OB_STATE_INTRODUCED ||
             _currentState == OutboundState.OB_STATE_PENDING_INTRO)
             _currentState = OutboundState.OB_STATE_CREATED_RECEIVED;
+
+	if (_requestSentCount == 1) {
+            _rtt = (int) (_context.clock().now() - _requestSentTime);
+        }
         packetReceived();
     }
     
============================================================
--- router/java/src/net/i2p/router/transport/udp/PeerState.java	8da5f77c8ec62803af2f12a5efe2b18d79ada9d1
+++ router/java/src/net/i2p/router/transport/udp/PeerState.java	b38a05ce29d14485fc4fa2a7e77100620193aac7
@@ -314,10 +314,10 @@ public class PeerState {
      */
     public static final int MAX_MTU = Math.max(LARGE_MTU, MAX_IPV6_MTU);
     
-    private static final int MIN_RTO = 100 + ACKSender.ACK_FREQUENCY;
-    private static final int INIT_RTO = 3*1000;
-    public static final int INIT_RTT = INIT_RTO / 2;
-    private static final int MAX_RTO = 15*1000;
+    private static final int MIN_RTO = 1000;
+    private static final int INIT_RTO = 1000;
+    public static final int INIT_RTT = 0;
+    private static final int MAX_RTO = 60*1000;
     private static final int CLOCK_SKEW_FUDGE = (ACKSender.ACK_FREQUENCY * 2) / 3;
     
     /**
@@ -337,7 +337,7 @@ public class PeerState {
 
     
     public PeerState(RouterContext ctx, UDPTransport transport,
-                     byte[] remoteIP, int remotePort, Hash remotePeer, boolean isInbound) {
+                     byte[] remoteIP, int remotePort, Hash remotePeer, boolean isInbound, int rtt) {
         _context = ctx;
         _log = ctx.logManager().getLog(PeerState.class);
         _transport = transport;
@@ -366,9 +366,14 @@ public class PeerState {
         }
         //_mtuLastChecked = -1;
         _lastACKSend = -1;
+
         _rto = INIT_RTO;
         _rtt = INIT_RTT;
-        _rttDeviation = _rtt;
+	if (rtt > 0)  
+            recalculateTimeouts(rtt);
+	else
+            _rttDeviation = _rtt;
+            
         _inboundMessages = new HashMap<Long, InboundMessageState>(8);
         _outboundMessages = new CachedIteratorCollection<OutboundMessageState>();
         //_outboundQueue = new CoDelPriorityBlockingQueue(ctx, "UDP-PeerState", 32);
@@ -1226,16 +1231,18 @@ public class PeerState {
      *  Caller should synch on this
      */
     private void recalculateTimeouts(long lifetime) {
-        // the rttDev calculation matches that recommended in RFC 2988 (beta = 1/4)
-        _rttDeviation = _rttDeviation + (int)(0.25d*(Math.abs(lifetime-_rtt)-_rttDeviation));
+        if (_rtt <= 0) {
+	    // first measurement
+	    _rtt = (int) lifetime;
+	    _rttDeviation = (int)(lifetime / 2);
+	} else {
+            // the rttDev calculation matches that recommended in RFC 2988 (beta = 1/4)
+            _rttDeviation = (int)( 0.75*_rttDeviation + 0.25*Math.abs(lifetime-_rtt) );
         
-        float scale = RTT_DAMPENING;
-        // the faster we are going, the slower we want to reduce the rtt
-        //if (_sendBps > 0)
-        //    scale = lifetime / ((float)lifetime + (float)_sendBps);
-        //if (scale < 0.001f) scale = 0.001f;
+            float scale = RTT_DAMPENING;
         
-        _rtt = (int)(_rtt*(1.0f-scale) + (scale)*lifetime);
+            _rtt = (int)(_rtt*(1.0f-scale) + (scale)*lifetime);
+	}
         // K = 4
         _rto = Math.min(MAX_RTO, Math.max(minRTO(), _rtt + (_rttDeviation<<2)));
         //if (_log.shouldLog(Log.DEBUG))
@@ -1821,13 +1828,15 @@ public class PeerState {
                               + " remaining"
                               + " for message " + state.getMessageId() + ": " + state);
 
-                if (state.getPushCount() > 0)
+                int rto = getRTO();
+                if (state.getPushCount() > 0) {
                     _retransmitter = state;
+		    rto = Math.min(MAX_RTO, rto << state.getPushCount()); // Section 5.5 RFC 6298
+		}
 
                 if (state.push())
                     _messagesSent++;
             
-                int rto = getRTO();
                 state.setNextSendTime(now + rto);
 
                 //if (peer.getSendWindowBytesRemaining() > 0)
============================================================
--- router/java/src/net/i2p/router/transport/udp/UDPTransport.java	67540d7a57d681086701db0defcd869fce64192e
+++ router/java/src/net/i2p/router/transport/udp/UDPTransport.java	386ad7ce469d27c421b0807a54dcc667e8d551cc
@@ -2722,7 +2722,7 @@ public class UDPTransport extends Transp
         for (PeerState peer : _peersByIdent.values()) {
             if ((!includeEverybody) && now - peer.getLastReceiveTime() > 5*60*1000)
                 continue; // skip old peers
-            if (peer.getRTT() > PeerState.INIT_RTT - 250)
+            if (peer.getRTT() > 1250)
                 continue; // Big RTT makes for a poor calculation
             skews.addElement(Long.valueOf(peer.getClockSkew() / 1000));
Last edited 3 weeks ago by zab (previous) (diff)

comment:4 Changed 3 weeks ago by zzz

  • Resolution set to fixed
  • Status changed from accepted to closed

in d646919fa11c4387df1ed63b214e23b1c7b53d2a to be 0.9.38-11, minor additional cleanups to follow
note that this also fixes the biased clock skew numbers

Note: See TracTickets for help on using tickets.