vendor/google.golang.org/grpc/transport/bdp_estimator.go

   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 }