Changeset 43f2695


Ignore:
Timestamp:
Feb 10, 2008 6:29:21 PM (13 years ago)
Author:
zzz <zzz@…>
Branches:
master
Children:
d2f3a26, f7b0e81
Parents:
ea0d4ff
Message:
  • Add new tunnel build algorithm (preliminary)
  • Change NTCP backlogged message from error to warning
  • Checklist updates
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • checklist.txt

    rea0d4ff r43f2695  
    44Sync with mtn.i2p2.i2p
    55Start with a clean checkout mtn -d i2p.mtn co --branch=i2p.i2p
     6Double-check trust list
    67
    78Change revision in:
     
    1516        ant dist
    1617        mtn ci
    17         mtn tag i2p-0.6.1.xx
     18        mtn tag i2p-0.6.1.xx h:
    1819        Sync with mtn.i2p2.i2p
    1920
     
    2829Make the source tarball:
    2930        Start with a clean checkout mtn -d i2p.mtn co --branch=i2p.i2p i2p-0.6.1.xx
    30         tar tjf i2p-0.6.1.xx.tar.bz2 --exclude i2p-0.6.1.xx/_MTN i2p-0.6.1.xx   
     31        Double-check trust list
     32        tar cjf i2psource-0.6.1.xx.tar.bz2 --exclude i2p-0.6.1.xx/_MTN i2p-0.6.1.xx     
    3133        mv i2p-0.6.1.xx.tar.bz2 i2p.i2p
    3234
    3335More signatures:
    34         sha1sum i2pinstall.exe i2p.tar.bz2 i2p-0.6.1.xx.tar.bz2 i2pupdate.zip
     36        sha1sum i2pinstall.exe i2p.tar.bz2 i2psource-0.6.1.xx.tar.bz2 i2pupdate.zip
    3537        gpg -b i2pinstall.exe
    3638        gpg -b i2p.tar.bz2
  • history.txt

    rea0d4ff r43f2695  
     12008-02-10 zzz
     2    * Add new tunnel build algorithm (preliminary)
     3    * Change NTCP backlogged message from error to warning
     4    * Checklist updates
     5
    16* 2008-02-10  0.6.1.31 released
    27
  • router/java/src/net/i2p/router/RouterVersion.java

    rea0d4ff r43f2695  
    1818    public final static String ID = "$Revision: 1.548 $ $Date: 2008-02-10 15:00:00 $";
    1919    public final static String VERSION = "0.6.1.31";
    20     public final static long BUILD = 0;
     20    public final static long BUILD = 1;
    2121    public static void main(String args[]) {
    2222        System.out.println("I2P Router version: " + VERSION + "-" + BUILD);
  • router/java/src/net/i2p/router/transport/ntcp/NTCPConnection.java

    rea0d4ff r43f2695  
    269269                int blocks = 0;
    270270                synchronized (_writeBufs) { blocks = _writeBufs.size(); }
    271                 if (_log.shouldLog(Log.ERROR))
    272                     _log.error("Too backlogged for too long (" + _consecutiveBacklog + " messages for " + DataHelper.formatDuration(queueTime()) + ", sched? " + wantsWrite + ", blocks: " + blocks + ") sending to " + _remotePeer.calculateHash().toBase64());
     271                if (_log.shouldLog(Log.WARN))
     272                    _log.warn("Too backlogged for too long (" + _consecutiveBacklog + " messages for " + DataHelper.formatDuration(queueTime()) + ", sched? " + wantsWrite + ", blocks: " + blocks + ") sending to " + _remotePeer.calculateHash().toBase64());
    273273                _context.statManager().addRateData("ntcp.closeOnBacklog", getUptime(), getUptime());
    274274                close();
  • router/java/src/net/i2p/router/tunnel/pool/ExpireJob.java

    rea0d4ff r43f2695  
    2020        // up through the full lifetime of the tunnel, plus a clock skew, since
    2121        // others may be sending to the published lease expirations
     22        // Also skew the inbound away from the outbound
    2223        long expire = cfg.getExpiration();
    2324        _dropAfter = expire + Router.CLOCK_FUDGE_FACTOR;
    24         expire -= ctx.random().nextLong(5*60*1000);
     25        expire -= ctx.random().nextLong(60*1000);
     26        if (_pool.getSettings().isInbound())
     27            expire -= ctx.random().nextLong(15*1000);
    2528        cfg.setExpiration(expire);
    2629        getTiming().setStartAfter(expire);
  • router/java/src/net/i2p/router/tunnel/pool/TunnelPool.java

    rea0d4ff r43f2695  
    11package net.i2p.router.tunnel.pool;
    22
     3import java.util.Arrays;
    34import java.util.ArrayList;
    45import java.util.Collections;
     
    1718import net.i2p.router.TunnelInfo;
    1819import net.i2p.router.tunnel.HopConfig;
     20import net.i2p.stat.Rate;
     21import net.i2p.stat.RateStat;
    1922import net.i2p.util.Log;
    2023
     
    3740    private long _lastRateUpdate;
    3841    private long _lastLifetimeProcessed;
    39     private String _rateName;
     42    private final String _rateName;
     43    private final String _buildStatName;
     44    private static final int TUNNEL_LIFETIME = 10*60*1000;
    4045   
    4146    public TunnelPool(RouterContext ctx, TunnelPoolManager mgr, TunnelPoolSettings settings, TunnelPeerSelector sel) {
     
    5762                    (_settings.isExploratory() ? "exploratory" : _settings.getDestinationNickname()) +
    5863                    (_settings.isInbound() ? ".in" : ".out");
     64        _buildStatName = "tunnel.build." +
     65                    (_settings.isExploratory() ? "exploratory" : _settings.getDestinationNickname()) +
     66                    (_settings.isInbound() ? ".in" : ".out");
    5967        refreshSettings();
    6068    }
     
    8088                               "Tunnel Bandwidth", "Tunnels",
    8189                               new long[] { 5*60*1000l });
     90        _context.statManager().createRateStat(_buildStatName,
     91                               "Tunnel Build Frequency", "Tunnels",
     92                               new long[] { TUNNEL_LIFETIME });
    8293    }
    8394   
     
    149160                // if there are nonzero hop tunnels and the zero hop tunnels are fallbacks,
    150161                // avoid the zero hop tunnels
     162                TunnelInfo backloggedTunnel = null;
    151163                if (avoidZeroHop) {
    152164                    for (int i = 0; i < _tunnels.size(); i++) {
    153165                        TunnelInfo info = (TunnelInfo)_tunnels.get(i);
    154166                        if ( (info.getLength() > 1) && (info.getExpiration() > _context.clock().now()) ) {
    155                             _lastSelected = info;
    156                             return info;
     167                            // avoid outbound tunnels where the 1st hop is backlogged
     168                            if (_settings.isInbound() || !_context.commSystem().isBacklogged(info.getPeer(1))) {
     169                                _lastSelected = info;
     170                                return info;
     171                            } else {
     172                                backloggedTunnel = info;
     173                            }
    157174                        }
    158175                    }
     176                    // return a random backlogged tunnel
     177                    if (backloggedTunnel != null)
     178                        return backloggedTunnel;
    159179                }
    160180                // ok, either we are ok using zero hop tunnels, or only fallback tunnels remain.  pick 'em
     
    163183                    TunnelInfo info = (TunnelInfo)_tunnels.get(i);
    164184                    if (info.getExpiration() > _context.clock().now()) {
    165                         //_log.debug("Selecting tunnel: " + info + " - " + _tunnels);
    166                         _lastSelected = info;
    167                         return info;
     185                        // avoid outbound tunnels where the 1st hop is backlogged
     186                        if (_settings.isInbound() || info.getLength() <= 1 ||
     187                            !_context.commSystem().isBacklogged(info.getPeer(1))) {
     188                            //_log.debug("Selecting tunnel: " + info + " - " + _tunnels);
     189                            _lastSelected = info;
     190                            return info;
     191                        } else {
     192                            backloggedTunnel = info;
     193                        }
    168194                    }
    169195                }
     196                // return a random backlogged tunnel
     197                if (backloggedTunnel != null)
     198                    return backloggedTunnel;
    170199                if (_log.shouldLog(Log.WARN))
    171200                    _log.warn(toString() + ": after " + _tunnels.size() + " tries, no unexpired ones were found: " + _tunnels);
     
    446475        boolean allowZeroHop = ((getSettings().getLength() + getSettings().getLengthVariance()) <= 0);
    447476         
     477        /**
     478         * This algorithm builds based on the previous average length of time it takes
     479         * to build a tunnel. This average is kept in the _buildRateName stat.
     480         * It is a separate stat for each pool, since in and out building use different methods,
     481         * and each pool can have separate length and length variance settings.
     482         * We add one minute to the stat for safety.
     483         *
     484         * We linearly increase the number of builds per expiring tunnel from
     485         * 1 to PANIC_FACTOR as the time-to-expire gets shorter.
     486         *
     487         * The stat will be 0 for first 10m of uptime so we will use the conservative algorithm
     488         * further below instead. It will take about 30m of uptime to settle down.
     489         * Or, if we are building more than 33% of the time something is seriously wrong,
     490         * we also use the conservative algorithm instead
     491         *
     492         **/
     493
     494        int avg = 0;
     495        RateStat rs = _context.statManager().getRate(_buildStatName);
     496        if (rs != null) {
     497            Rate r = rs.getRate(TUNNEL_LIFETIME);
     498            if (r != null)
     499                avg = (int) ( TUNNEL_LIFETIME * r.getAverageValue() / wanted);
     500        }
     501
     502        if (avg > 0 && avg < TUNNEL_LIFETIME / 3) {
     503            final int PANIC_FACTOR = 4;  // how many builds to kick off when time gets short
     504            avg += 60*1000;   // one minute safety factor
     505            if (_settings.isExploratory())
     506                avg += 60*1000;   // two minute safety factor
     507            long now = _context.clock().now();
     508
     509            int expireSoon = 0;
     510            int expireLater = 0;
     511            int expireTime[];
     512            int fallback = 0;
     513            synchronized (_tunnels) {
     514                expireTime = new int[_tunnels.size()];
     515                for (int i = 0; i < _tunnels.size(); i++) {
     516                    TunnelInfo info = (TunnelInfo)_tunnels.get(i);
     517                    if (allowZeroHop || (info.getLength() > 1)) {
     518                        int timeToExpire = (int) (info.getExpiration() - now);
     519                        if (timeToExpire > 0 && timeToExpire < avg) {
     520                            expireTime[expireSoon++] = timeToExpire;
     521                        } else {
     522                            expireLater++;
     523                        }
     524                    } else if (info.getExpiration() - now > avg) {
     525                        fallback++;
     526                    }
     527                }
     528            }
     529
     530            int inProgress;
     531            synchronized (_inProgress) {
     532                inProgress = _inProgress.size();
     533            }
     534            int remainingWanted = (wanted - expireLater) - inProgress;
     535            if (allowZeroHop)
     536                remainingWanted -= fallback;
     537
     538            int rv = 0;
     539            int latesttime = 0;
     540            if (remainingWanted > 0) {
     541                if (remainingWanted > expireSoon) {
     542                    rv = PANIC_FACTOR * (remainingWanted - expireSoon);  // for tunnels completely missing
     543                    remainingWanted = expireSoon;
     544                }
     545                // add from 1 to PANIC_FACTOR builds, depending on how late it is
     546                // only use the expire times of the latest-expiring tunnels,
     547                // the other ones are extras
     548                for (int i = 0; i < remainingWanted; i++) {
     549                    int latestidx = 0;
     550                    // given the small size of the array this is efficient enough
     551                    for (int j = 0; j < expireSoon; j++) {
     552                        if (expireTime[j] > latesttime) {
     553                            latesttime = expireTime[j];
     554                            latestidx = j;
     555                        }
     556                    }
     557                    expireTime[latestidx] = 0;
     558                    if (latesttime > avg / 2)
     559                        rv += 1;
     560                    else
     561                        rv += 2 + ((PANIC_FACTOR - 2) * (((avg / 2) - latesttime) / (avg / 2)));
     562                }
     563            }
     564
     565            if (rv > 0 && _log.shouldLog(Log.DEBUG))
     566                _log.debug("New Count: rv: " + rv + " allow? " + allowZeroHop
     567                       + " avg " + avg + " latesttime " + latesttime
     568                       + " soon " + expireSoon + " later " + expireLater
     569                       + " std " + wanted + " inProgress " + inProgress + " fallback " + fallback
     570                       + " for " + toString());
     571            _context.statManager().addRateData(_buildStatName, rv + inProgress, 0);
     572            return rv;
     573        }
     574
     575        // fixed, conservative algorithm - starts building 3 1/2 - 6m before expiration
     576        // (210 or 270s) + (0..90s random)
    448577        long expireAfter = _context.clock().now() + _expireSkew; // + _settings.getRebuildPeriod() + _expireSkew;
    449578        int expire30s = 0;
     
    492621        }
    493622       
    494         return countHowManyToBuild(allowZeroHop, expire30s, expire90s, expire150s, expire210s, expire270s,
     623        int rv = countHowManyToBuild(allowZeroHop, expire30s, expire90s, expire150s, expire210s, expire270s,
    495624                                   expireLater, wanted, inProgress, fallback);
     625        _context.statManager().addRateData(_buildStatName, (rv > 0 || inProgress > 0) ? 1 : 0, 0);
     626        return rv;
     627
    496628    }
    497629   
     
    591723                rv = standardAmount - inProgress - fallback;
    592724       
    593         if (_log.shouldLog(Log.DEBUG))
     725        if (rv > 0 && _log.shouldLog(Log.DEBUG))
    594726            _log.debug("Count: rv: " + rv + " allow? " + allowZeroHop
    595727                       + " 30s " + expire30s + " 90s " + expire90s + " 150s " + expire150s + " 210s " + expire210s
Note: See TracChangeset for help on using the changeset viewer.