1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
# The following two algorithms
# Algorithm 1
# TODO: Burst and Relay/Regular differentiation
BwRate = Bandwidth Rate in Bytes Per Second
GlobalWriteBucket = 0
GlobalReadBucket = 0
Epoch = Token Fill Rate in seconds: suggest 50ms=.050
SecondCounter = 0
MinWriteBytes = Minimum amount bytes per write
Every Epoch Seconds:
UseMinWriteBytes = MinWriteBytes
WriteCnt = 0
ReadCnt = 0
BytesRead = 0
For Each Open OR Conn with pending write data:
WriteCnt++
For Each Open OR Conn:
ReadCnt++
BytesToRead = (BwRate*Epoch + GlobalReadBucket)/ReadCnt
BytesToWrite = (BwRate*Epoch + GlobalWriteBucket)/WriteCnt
if BwRate/WriteCnt < MinWriteBytes:
# If we aren't likely to accumulate enough bytes in a second to
# send a whole cell for our connections, send partials
Log(NOTICE, "Too many ORCons to write full blocks. Sending short packets.")
UseMinWriteBytes = 1
# Other option: We could switch to plan 2 here
# Service each writable ORConn. If there are any partial writes,
# return remaining bytes from this epoch to the global pool
For Each Open OR Conn with pending write data:
ORConn->write_bucket += BytesToWrite
if ORConn->write_bucket > UseMinWriteBytes:
w = write(ORConn, MIN(len(ORConn->write_data), ORConn->write_bucket))
# possible that w < ORConn->write_data here due to TCP pushback.
# We should restore the rest of the write_bucket to the global
# buffer
GlobalWriteBucket += (ORConn->write_bucket - w)
ORConn->write_bucket = 0
For Each Open OR Conn:
r = read_nonblock(ORConn, BytesToRead)
BytesRead += r
SecondCounter += Epoch
if SecondCounter < 1:
# Save unused bytes from this epoch to be used later in the second
GlobalReadBucket += (BwRate*Epoch - BytesRead)
else:
SecondCounter = 0
GlobalReadBucket = 0
GlobalWriteBucket = 0
For Each ORConn:
ORConn->write_bucket = 0
# Alternate plan for Writing fairly. Reads would still be covered
# by plan 1 as there is no additional network overhead for short reads,
# so we don't need to try to avoid them.
#
# I think this is actually pretty similar to what we do now, but
# with the addition that the bytes accumulate up to the second mark
# and we try to keep track of our position in the write list here
# (unless libevent is doing that for us already and I just don't see it)
#
# TODO: Burst and Relay/Regular differentiation
# XXX: The inability to send single cells will cause us to block
# on EXTEND cells for low-bandwidth node pairs..
BwRate = Bandwidth Rate in Bytes Per Second
WriteBytes = Bytes per write
Epoch = MAX(MIN(WriteBytes/BwRate, .333s), .050s)
SecondCounter = 0
GlobalWriteBucket = 0
# New connections are inserted at Head-1 (the 'tail' of this circular list)
# This is not 100% fifo for all node data, but it is the best we can do
# without insane amounts of additional queueing complexity.
WriteConnList = List of Open OR Conns with pending write data > WriteBytes
WriteConnHead = 0
Every Epoch Seconds:
GlobalWriteBucket += BwRate*Epoch
WriteListEnd = WriteConnHead
do
ORCONN = WriteConnList[WriteConnHead]
w = write(ORConn, WriteBytes)
GlobalWriteBucket -= w
WriteConnHead += 1
while GlobalWriteBucket > 0 and WriteConnHead != WriteListEnd
SecondCounter += Epoch
if SecondCounter >= 1:
SecondCounter = 0
GlobalWriteBucket = 0
|