[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: [tor-bugs] #23816 [Core Tor/Tor]: Use exponetial backoff with jitter and/or tune its parameters (was: Use expontial backoff with jitter and/or tune its parameters)

#23816: Use exponetial backoff with jitter and/or tune its parameters
-----------------------------+------------------------------------
 Reporter:  nickm            |          Owner:  nickm
     Type:  defect           |         Status:  needs_review
 Priority:  Medium           |      Milestone:  Tor: 0.3.2.x-final
Component:  Core Tor/Tor     |        Version:
 Severity:  Normal           |     Resolution:
 Keywords:  review-group-24  |  Actual Points:
Parent ID:                   |         Points:
 Reviewer:  catalyst         |        Sponsor:  SponsorV
-----------------------------+------------------------------------

Comment (by catalyst):

 I'm going to start by summarizing my comparison of the algorithms.

 The existing algorithm is a weird hybrid of decorrelated jitter and equal
 jitter.  Each delay is at least the size of the preceding one, plus a
 random value capped at a fixed multiple of the preceding delay.  This
 means in the worst case, d,,i+1,, = d,,i,, + d,,i,, * 3 + 1 = d,,i,, * 4 +
 1, or approximately, d,,i,, = 4^i^.

 For full jitter, the worst case is d,,i,, = base * m^i^.

 For decorrelated jitter, the worst case is also d,,i,, = base *m^i^ but
 any small variation in an early delay step magnifies in later steps.

 The examples in the blog show m=2 for full jitter and m=3 for decorrelated
 jitter.  I'm not sure why they chose that variation.

 The existing algorithm has some of the drawbacks of equal jitter, such as
 missing some possible time slots because it tries to always include a
 fixed delay component that's longer than the previous, so either
 decorrelated jitter or full jitter would be an improvement.

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/23816#comment:7>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online

_______________________________________________
tor-bugs mailing list
tor-bugs@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs