diff options
Diffstat (limited to 'vendor/google.golang.org/grpc/transport/bdp_estimator.go')
-rw-r--r-- | vendor/google.golang.org/grpc/transport/bdp_estimator.go | 143 |
1 files changed, 143 insertions, 0 deletions
diff --git a/vendor/google.golang.org/grpc/transport/bdp_estimator.go b/vendor/google.golang.org/grpc/transport/bdp_estimator.go new file mode 100644 index 0000000..667edb8 --- /dev/null +++ b/vendor/google.golang.org/grpc/transport/bdp_estimator.go | |||
@@ -0,0 +1,143 @@ | |||
1 | /* | ||
2 | * | ||
3 | * Copyright 2017 gRPC authors. | ||
4 | * | ||
5 | * Licensed under the Apache License, Version 2.0 (the "License"); | ||
6 | * you may not use this file except in compliance with the License. | ||
7 | * You may obtain a copy of the License at | ||
8 | * | ||
9 | * http://www.apache.org/licenses/LICENSE-2.0 | ||
10 | * | ||
11 | * Unless required by applicable law or agreed to in writing, software | ||
12 | * distributed under the License is distributed on an "AS IS" BASIS, | ||
13 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | ||
14 | * See the License for the specific language governing permissions and | ||
15 | * limitations under the License. | ||
16 | * | ||
17 | */ | ||
18 | |||
19 | package transport | ||
20 | |||
21 | import ( | ||
22 | "sync" | ||
23 | "time" | ||
24 | ) | ||
25 | |||
26 | const ( | ||
27 | // bdpLimit is the maximum value the flow control windows | ||
28 | // will be increased to. | ||
29 | bdpLimit = (1 << 20) * 4 | ||
30 | // alpha is a constant factor used to keep a moving average | ||
31 | // of RTTs. | ||
32 | alpha = 0.9 | ||
33 | // If the current bdp sample is greater than or equal to | ||
34 | // our beta * our estimated bdp and the current bandwidth | ||
35 | // sample is the maximum bandwidth observed so far, we | ||
36 | // increase our bbp estimate by a factor of gamma. | ||
37 | beta = 0.66 | ||
38 | // To put our bdp to be smaller than or equal to twice the real BDP, | ||
39 | // we should multiply our current sample with 4/3, however to round things out | ||
40 | // we use 2 as the multiplication factor. | ||
41 | gamma = 2 | ||
42 | ) | ||
43 | |||
44 | var ( | ||
45 | // Adding arbitrary data to ping so that its ack can be | ||
46 | // identified. | ||
47 | // Easter-egg: what does the ping message say? | ||
48 | bdpPing = &ping{data: [8]byte{2, 4, 16, 16, 9, 14, 7, 7}} | ||
49 | ) | ||
50 | |||
51 | type bdpEstimator struct { | ||
52 | // sentAt is the time when the ping was sent. | ||
53 | sentAt time.Time | ||
54 | |||
55 | mu sync.Mutex | ||
56 | // bdp is the current bdp estimate. | ||
57 | bdp uint32 | ||
58 | // sample is the number of bytes received in one measurement cycle. | ||
59 | sample uint32 | ||
60 | // bwMax is the maximum bandwidth noted so far (bytes/sec). | ||
61 | bwMax float64 | ||
62 | // bool to keep track of the begining of a new measurement cycle. | ||
63 | isSent bool | ||
64 | // Callback to update the window sizes. | ||
65 | updateFlowControl func(n uint32) | ||
66 | // sampleCount is the number of samples taken so far. | ||
67 | sampleCount uint64 | ||
68 | // round trip time (seconds) | ||
69 | rtt float64 | ||
70 | } | ||
71 | |||
72 | // timesnap registers the time bdp ping was sent out so that | ||
73 | // network rtt can be calculated when its ack is recieved. | ||
74 | // It is called (by controller) when the bdpPing is | ||
75 | // being written on the wire. | ||
76 | func (b *bdpEstimator) timesnap(d [8]byte) { | ||
77 | if bdpPing.data != d { | ||
78 | return | ||
79 | } | ||
80 | b.sentAt = time.Now() | ||
81 | } | ||
82 | |||
83 | // add adds bytes to the current sample for calculating bdp. | ||
84 | // It returns true only if a ping must be sent. This can be used | ||
85 | // by the caller (handleData) to make decision about batching | ||
86 | // a window update with it. | ||
87 | func (b *bdpEstimator) add(n uint32) bool { | ||
88 | b.mu.Lock() | ||
89 | defer b.mu.Unlock() | ||
90 | if b.bdp == bdpLimit { | ||
91 | return false | ||
92 | } | ||
93 | if !b.isSent { | ||
94 | b.isSent = true | ||
95 | b.sample = n | ||
96 | b.sentAt = time.Time{} | ||
97 | b.sampleCount++ | ||
98 | return true | ||
99 | } | ||
100 | b.sample += n | ||
101 | return false | ||
102 | } | ||
103 | |||
104 | // calculate is called when an ack for a bdp ping is received. | ||
105 | // Here we calculate the current bdp and bandwidth sample and | ||
106 | // decide if the flow control windows should go up. | ||
107 | func (b *bdpEstimator) calculate(d [8]byte) { | ||
108 | // Check if the ping acked for was the bdp ping. | ||
109 | if bdpPing.data != d { | ||
110 | return | ||
111 | } | ||
112 | b.mu.Lock() | ||
113 | rttSample := time.Since(b.sentAt).Seconds() | ||
114 | if b.sampleCount < 10 { | ||
115 | // Bootstrap rtt with an average of first 10 rtt samples. | ||
116 | b.rtt += (rttSample - b.rtt) / float64(b.sampleCount) | ||
117 | } else { | ||
118 | // Heed to the recent past more. | ||
119 | b.rtt += (rttSample - b.rtt) * float64(alpha) | ||
120 | } | ||
121 | b.isSent = false | ||
122 | // The number of bytes accumalated so far in the sample is smaller | ||
123 | // than or equal to 1.5 times the real BDP on a saturated connection. | ||
124 | bwCurrent := float64(b.sample) / (b.rtt * float64(1.5)) | ||
125 | if bwCurrent > b.bwMax { | ||
126 | b.bwMax = bwCurrent | ||
127 | } | ||
128 | // If the current sample (which is smaller than or equal to the 1.5 times the real BDP) is | ||
129 | // greater than or equal to 2/3rd our perceived bdp AND this is the maximum bandwidth seen so far, we | ||
130 | // should update our perception of the network BDP. | ||
131 | if float64(b.sample) >= beta*float64(b.bdp) && bwCurrent == b.bwMax && b.bdp != bdpLimit { | ||
132 | sampleFloat := float64(b.sample) | ||
133 | b.bdp = uint32(gamma * sampleFloat) | ||
134 | if b.bdp > bdpLimit { | ||
135 | b.bdp = bdpLimit | ||
136 | } | ||
137 | bdp := b.bdp | ||
138 | b.mu.Unlock() | ||
139 | b.updateFlowControl(bdp) | ||
140 | return | ||
141 | } | ||
142 | b.mu.Unlock() | ||
143 | } | ||