| 36 |
kaklik |
1 |
# Written by Bram Cohen
|
|
|
2 |
# see LICENSE.txt for license information
|
|
|
3 |
|
|
|
4 |
from traceback import print_exc
|
|
|
5 |
from binascii import b2a_hex
|
|
|
6 |
from clock import clock
|
|
|
7 |
from CurrentRateMeasure import Measure
|
|
|
8 |
from cStringIO import StringIO
|
|
|
9 |
from math import sqrt
|
|
|
10 |
|
|
|
11 |
try:
|
|
|
12 |
True
|
|
|
13 |
except:
|
|
|
14 |
True = 1
|
|
|
15 |
False = 0
|
|
|
16 |
try:
|
|
|
17 |
sum([1])
|
|
|
18 |
except:
|
|
|
19 |
sum = lambda a: reduce(lambda x,y: x+y, a, 0)
|
|
|
20 |
|
|
|
21 |
DEBUG = False
|
|
|
22 |
|
|
|
23 |
MAX_RATE_PERIOD = 20.0
|
|
|
24 |
MAX_RATE = 10e10
|
|
|
25 |
PING_BOUNDARY = 1.2
|
|
|
26 |
PING_SAMPLES = 7
|
|
|
27 |
PING_DISCARDS = 1
|
|
|
28 |
PING_THRESHHOLD = 5
|
|
|
29 |
PING_DELAY = 5 # cycles 'til first upward adjustment
|
|
|
30 |
PING_DELAY_NEXT = 2 # 'til next
|
|
|
31 |
ADJUST_UP = 1.05
|
|
|
32 |
ADJUST_DOWN = 0.95
|
|
|
33 |
UP_DELAY_FIRST = 5
|
|
|
34 |
UP_DELAY_NEXT = 2
|
|
|
35 |
SLOTS_STARTING = 6
|
|
|
36 |
SLOTS_FACTOR = 1.66/1000
|
|
|
37 |
|
|
|
38 |
class RateLimiter:
|
|
|
39 |
def __init__(self, sched, unitsize, slotsfunc = lambda x: None):
|
|
|
40 |
self.sched = sched
|
|
|
41 |
self.last = None
|
|
|
42 |
self.unitsize = unitsize
|
|
|
43 |
self.slotsfunc = slotsfunc
|
|
|
44 |
self.measure = Measure(MAX_RATE_PERIOD)
|
|
|
45 |
self.autoadjust = False
|
|
|
46 |
self.upload_rate = MAX_RATE * 1000
|
|
|
47 |
self.slots = SLOTS_STARTING # garbage if not automatic
|
|
|
48 |
|
|
|
49 |
def set_upload_rate(self, rate):
|
|
|
50 |
# rate = -1 # test automatic
|
|
|
51 |
if rate < 0:
|
|
|
52 |
if self.autoadjust:
|
|
|
53 |
return
|
|
|
54 |
self.autoadjust = True
|
|
|
55 |
self.autoadjustup = 0
|
|
|
56 |
self.pings = []
|
|
|
57 |
rate = MAX_RATE
|
|
|
58 |
self.slots = SLOTS_STARTING
|
|
|
59 |
self.slotsfunc(self.slots)
|
|
|
60 |
else:
|
|
|
61 |
self.autoadjust = False
|
|
|
62 |
if not rate:
|
|
|
63 |
rate = MAX_RATE
|
|
|
64 |
self.upload_rate = rate * 1000
|
|
|
65 |
self.lasttime = clock()
|
|
|
66 |
self.bytes_sent = 0
|
|
|
67 |
|
|
|
68 |
def queue(self, conn):
|
|
|
69 |
assert conn.next_upload is None
|
|
|
70 |
if self.last is None:
|
|
|
71 |
self.last = conn
|
|
|
72 |
conn.next_upload = conn
|
|
|
73 |
self.try_send(True)
|
|
|
74 |
else:
|
|
|
75 |
conn.next_upload = self.last.next_upload
|
|
|
76 |
self.last.next_upload = conn
|
|
|
77 |
self.last = conn
|
|
|
78 |
|
|
|
79 |
def try_send(self, check_time = False):
|
|
|
80 |
t = clock()
|
|
|
81 |
self.bytes_sent -= (t - self.lasttime) * self.upload_rate
|
|
|
82 |
self.lasttime = t
|
|
|
83 |
if check_time:
|
|
|
84 |
self.bytes_sent = max(self.bytes_sent, 0)
|
|
|
85 |
cur = self.last.next_upload
|
|
|
86 |
while self.bytes_sent <= 0:
|
|
|
87 |
bytes = cur.send_partial(self.unitsize)
|
|
|
88 |
self.bytes_sent += bytes
|
|
|
89 |
self.measure.update_rate(bytes)
|
|
|
90 |
if bytes == 0 or cur.backlogged():
|
|
|
91 |
if self.last is cur:
|
|
|
92 |
self.last = None
|
|
|
93 |
cur.next_upload = None
|
|
|
94 |
break
|
|
|
95 |
else:
|
|
|
96 |
self.last.next_upload = cur.next_upload
|
|
|
97 |
cur.next_upload = None
|
|
|
98 |
cur = self.last.next_upload
|
|
|
99 |
else:
|
|
|
100 |
self.last = cur
|
|
|
101 |
cur = cur.next_upload
|
|
|
102 |
else:
|
|
|
103 |
self.sched(self.try_send, self.bytes_sent / self.upload_rate)
|
|
|
104 |
|
|
|
105 |
def adjust_sent(self, bytes):
|
|
|
106 |
self.bytes_sent = min(self.bytes_sent+bytes, self.upload_rate*3)
|
|
|
107 |
self.measure.update_rate(bytes)
|
|
|
108 |
|
|
|
109 |
|
|
|
110 |
def ping(self, delay):
|
|
|
111 |
if DEBUG:
|
|
|
112 |
print delay
|
|
|
113 |
if not self.autoadjust:
|
|
|
114 |
return
|
|
|
115 |
self.pings.append(delay > PING_BOUNDARY)
|
|
|
116 |
if len(self.pings) < PING_SAMPLES+PING_DISCARDS:
|
|
|
117 |
return
|
|
|
118 |
if DEBUG:
|
|
|
119 |
print 'cycle'
|
|
|
120 |
pings = sum(self.pings[PING_DISCARDS:])
|
|
|
121 |
del self.pings[:]
|
|
|
122 |
if pings >= PING_THRESHHOLD: # assume flooded
|
|
|
123 |
if self.upload_rate == MAX_RATE:
|
|
|
124 |
self.upload_rate = self.measure.get_rate()*ADJUST_DOWN
|
|
|
125 |
else:
|
|
|
126 |
self.upload_rate = min(self.upload_rate,
|
|
|
127 |
self.measure.get_rate()*1.1)
|
|
|
128 |
self.upload_rate = max(int(self.upload_rate*ADJUST_DOWN),2)
|
|
|
129 |
self.slots = int(sqrt(self.upload_rate*SLOTS_FACTOR))
|
|
|
130 |
self.slotsfunc(self.slots)
|
|
|
131 |
if DEBUG:
|
|
|
132 |
print 'adjust down to '+str(self.upload_rate)
|
|
|
133 |
self.lasttime = clock()
|
|
|
134 |
self.bytes_sent = 0
|
|
|
135 |
self.autoadjustup = UP_DELAY_FIRST
|
|
|
136 |
else: # not flooded
|
|
|
137 |
if self.upload_rate == MAX_RATE:
|
|
|
138 |
return
|
|
|
139 |
self.autoadjustup -= 1
|
|
|
140 |
if self.autoadjustup:
|
|
|
141 |
return
|
|
|
142 |
self.upload_rate = int(self.upload_rate*ADJUST_UP)
|
|
|
143 |
self.slots = int(sqrt(self.upload_rate*SLOTS_FACTOR))
|
|
|
144 |
self.slotsfunc(self.slots)
|
|
|
145 |
if DEBUG:
|
|
|
146 |
print 'adjust up to '+str(self.upload_rate)
|
|
|
147 |
self.lasttime = clock()
|
|
|
148 |
self.bytes_sent = 0
|
|
|
149 |
self.autoadjustup = UP_DELAY_NEXT
|
|
|
150 |
|
|
|
151 |
|
|
|
152 |
|
|
|
153 |
|