Changes between Version 16 and Version 17 of petconpaper


Ignore:
Timestamp:
Mar 1, 2009 1:50:13 AM (10 years ago)
Author:
anonymous
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • petconpaper

    v16 v17  
    22#!html
    33
    4 <h1>Peer Profiling and Selection in I2P</h1>
     4<h1>Peer Profiling and Selection in the I2P Anonymous Network</h1>
    55
    66PET-CON 2009.1
    77<br>
    8 DRAFT 2009-03-01 01:00 UTC
     8DRAFT 2009-03-01 03:00 UTC
    99<br>
    1010zzz@i2pmail.org
     
    3333</ul>
    3434
    35 
     35<b>NOTE TO ECHELON: I did some editing/cleanup in your sections too.</b>
    3636
    3737<h2>I2P Overview</h2>
     
    7373The current bandwith used by all peers is roughly 11 MByte/sec with peaks at 16
    7474MByte/sec (pic) and the peers builds ~40,000 tunnels (pic) producing this load.
    75 In the last 6 month the net grew from 400 up to 800 peers (pic), from 5 to 10 MByte/sec
     75In the last 6 months the net grew from 400 up to 800 peers (pic), from 5 to 10 MByte/sec
    7676and from ~20,000 to ~40,000 tunnels, which shows the vital stats of the net
    7777doubled in half a year. We predict continued stable growth for the network.
     
    128128tunnel in I2P has a fixed lifetime of 10 minutes and will be discarded after
    129129this time. A new tunnel will be created before the existing one will timeout.
    130 Until the old tunnel times out, data will be sent on all existent tunnels (
    131 associated to the specific destination).
    132 <p>
    133 Peers can reject or drop tunnel build requests send by other peers due to a lot
     130Data will be sent on one or more of the tunnels
     131associated with the specific destination.
     132<p>
     133Peers can reject or drop tunnel build requests sent by other peers for a number
    134134of reasons (overload, shutdown in progress, limit reached, out of sync).
    135 Even within lifetime of a tunnel these can be discarded due to overload or
     135Even within the lifetime of a tunnel these can be discarded due to overload or
    136136unexpected shutdown of one of the peers in the tunnel. To prevent a breakage
    137 of the destination, each tunnel is tested on a periodic base for funtion. This
    138 creates more or less 1 kbyte/minute traffic, which is considered low bandwith.
     137of the destination, each tunnel is tested on a periodic basis. This
     138creates about 1 Kbyte/minute of traffic, which is very low bandwith.
    139139<p>
    140140The client tunnels on a peer are sorted into different classes:
    141 <li>- application tunnels: the tunnel starts or ends in this peer, binded to a
     141<li>- application tunnels: the tunnel starts or ends in this peer, bound to a
    142142  server or client on the peer
    143143<li>- participating tunnels: this peer is a member in one of the in/outgoing tunnels
    144   and the participating tunnels reach in from a peer and is reached through to
     144  and the participating tunnels come in from a peer and continue through to
    145145  another peer.
    146   Three cases can be devided: endpoint of outgoing tunnel, inpoint of incoming
    147   tunnel, and pure participating tunnel
     146  Three cases are possible: endpoint or "outbound gateway" of an outgoing tunnel, entrance or "inbound gateway" of an incoming  tunnel, and a middle peer of a participating tunnel.
    148147   
    149148<p>
     
    332331
    333332<p>Client tunnels are used for all user client and server traffic, including accessing internal I2P network destinations or "hidden services" such as "eepsites", connection to external gateways ("inproxies" and "outproxies") and other uses.
    334 
    335 <p> The Not Failing tier is everybody, including the following two tiers.
    336 
    337 <p>The High-Capacity tier includes peers with above-average rating for accepting tunnel build requests, and the following tier.
    338 
    339 <p>The Fast tier includes peers from the High-Capacity tier with above-average rating for bandwidth-per-tunnel.
    340 
    341 <p>So here's how it works. Client tunnels are build from peers in the Fast tier. the end.
    342 
    343 
    344         <p> Exploratory tunnels are build from peers either in the Not Failing tier or the High Capacity tier. The tier selected is chosen on a per-build basis, using a weighted random function. This function uses data on the exploratory tunnel build success vs. the client tunnel build success to adjust the weighting.
     333<ul>
     334<li> The Not Failing tier is everybody, including the following two tiers.
     335
     336<li>The High-Capacity tier includes peers with above-average rating for accepting tunnel build requests, and the following tier.
     337
     338<li>The Fast tier includes peers from the High-Capacity tier whose speed rating (i.e.  peak bandwidth per tunnel) is above-average for all peers in the Not Failing tier.
     339</ul>
     340
     341<p>Candidate peers for tunnel builds are selected as follows. Client tunnels are built from peers in the Fast tier. Exploratory tunnels are built from peers either in the Not Failing tier or the High Capacity tier. The tier selected is chosen on a per-build basis, using a weighted random function. This function uses data on the exploratory tunnel build success vs. the client tunnel build success to adjust the weighting.
    345342As exploratory build success declines, the router builds more tunnels from the high capacity tier, to limit the amount of effort spent on the expensive tunnel build request operation.
    346343Therefore the selection maintains the balance between tunnel build requests and the need to explore peers.
    347344
    348 It may seem curious to use the Not Failing tier (generally the lowest-bandwidth, lowest-capacity peers) for exploratory tunnels, since these tunnels are required to function for a router to build client tunnels. However failing exploratory tunnels are recognized quickly and so this works out ok FIXME.
     345It may seem curious to use the Not Failing tier (generally the lowest-bandwidth, lowest-capacity peers) for exploratory tunnels, since these tunnels are required to function for a router to build client tunnels. However failing exploratory tunnels are recognized quickly and so in practice this well.
    349346 And the benefit, of course, is opportunistic bandwidth and capacity measurement.
    350347
    351         <p> Peers are selected with Equal weight within each tier
     348        <p> Peers are selected with Equal weight within each tier. If sufficient peers for a tunnel are not found within a given tier, the peer selection moves on to the next-lower tier.
    352349
    353350
     
    390387If peers are punished too lightly, routers will be slow to react to overloaded peers, and maintain the same high capacity peers for too long. In other words, a router will accept poor performance from a peer even when better peers may be available.
    391388
    392         <p> Start simple, get more complex if necessary, you will probably have to simplify again later
    393           (for example, our speed calc used to be pages and pages of code, now a one-liner)
    394 
    395         <p> As the tune-up paper says, active bandwidth probing (i.e.  generating large amounts of special-purpose data for testing is not practical. Nore is it necessary.
    396           Our exploratory tunnels average only 100KB in 10m (~150Bps)...
    397           Our unused client tunnels average only 10KB in 10m from tunnel tests (~15Bps)...
    398            but this is sufficient.
    399           When you are low bw, you don't care how accurately you sort into tiers.
    400           When you push a lot of data, your tiering will be better.
    401           Even very-low-bw routers tend to accurately find fast peers and thus are
     389        <p> We recommend that those wishing to implement a profiling and selection system start with relatively simple algorithms.  It is always possible to add complexity later if necessary. In practice, you will probably have to simplify again later.
     390          For example, I2P's speed calculation  used to be pages and pages of code, now it is a one-liner.
     391
     392       
     393<h2>Summary</h2>
     394<p>
     395          I2P's exploratory tunnels average only 100KB in 10m (~150Bps).
     396          Idle  client tunnels average only 10KB in 10m from tunnel tests (~15Bps).
     397           Surprisingly, this is sufficient to find sufficiently fast, high-capacity peers.
     398          When a router requires little bandwidth, it doesn't care how accurately its peers are sorted into tiers.
     399          When the router does require more bandwidth, the tiering will be correspondingly better.
     400          Even very-low-bandwidth routers tend to accurately find fast peers and thus are
    402401          well-prepared when higher bw is demanded.
    403 </ul>
     402
     403
     404 <p> To use the terms of the "Tune-up for Tor" paper [SB08], I2P's peer profiling and selection system is an opportunistic bandwidth measurement algorithm that is sensitive to network load and client demand. It does not use self-reported values. However it does not provide a "tunable" mechanism for users to trade off anonymity and performance. Nor do we think such a mechanism is necessary. Not only is active bandwidth probing (i.e.  generating large amounts of special-purpose data for testing is not practical, as [SB08] states, it is not necessary. In addition to the bandwidth measurements proposed in [SB08], I2P measures tunnel build acceptance rate, with adjustments for various bad behavior by peers. I2P's profiling and selection system has been in continuous use for approximately five years.
     405
     406<p>While the base system works well, several adjustments (some described above) are possible. The authors will continue to research and tune I2P's peer profiling and selection system in the coming months. We hope that the information in this paper will prove valuable to the developers of Tor and other anonymous networks.
     407
    404408
    405409<h2>References                   </h2><ul>
    406410<li>This paper includes material adapted from http://www.i2p2.de/ written by jrandom and others.
    407 <li><i>TOR http://www.torproject.org/</i>
     411<li><i>Tor http://www.torproject.org/</i>
    408412<li><i>IIP http://invisibleip.sourceforge.net/iip/ and http://en.wikipedia.org/wiki/Invisible_IRC_Project</i>
    409413<li><i>Licenses http://www.i2p2.de/licenses.html</i>
    410414<li><i>Pics should be taken from stats.i2p<i>
    411415
    412 <li><i>A Tune-up for Tor: Improving Security and Performance in the Tor Network</i>
     416<li><i>[SB08] A Tune-up for Tor: Improving Security and Performance in the Tor Network</i>
    413417Robin Snader and Nikita Borisov @ UIUC
    414 <li>I2P Development Meeting 68, December 9, 2003 http://www.i2p2.de/meeting68 (profiling described)
    415 <li>I2P Development Meeting 82, March 23, 2004 http://www.i2p2.de/meeting82 (profiling released in 0.3)
     418<li>[Jr03] I2P Development Meeting 68, December 9, 2003 http://www.i2p2.de/meeting68 (profiling described)
     419<li>[Jr04] I2P Development Meeting 82, March 23, 2004 http://www.i2p2.de/meeting82 (profiling released in 0.3)
    416420
    417421<li>Predecessor attack papers