消息的令牌桶或泄漏桶

Question

我试图将我的应用程序发送速率限制在900kbps，但问题是我使用的协议是面向消息的，并且消息的大小非常不同。我可以有从40字节一直到125000字节的消息，所有的消息都是以原子为单位发送的。

我尝试实现一个令牌桶缓冲区，但是如果我设置一个较低的桶大小，那么大包永远不会被发送，并且更大的桶将导致没有任何速率限制的大突发。

这是我用C实现的一小段代码：

typedef struct token_buffer {
  size_t capacity;
  size_t tokens;
  double rate;
  uint64_t timestamp;

} token_buffer;


static uint64_t time_now()
{
  struct timeval ts;
  gettimeofday(&ts, NULL);
  return (uint64_t)(ts.tv_sec * 1000 + ts.tv_usec/1000);
}

static int token_buffer_init(token_buffer *tbf, size_t max_burst, double rate)
{
  tbf->capacity = max_burst;
  tbf->tokens   = max_burst;
  tbf->rate = rate;
  tbf->timestamp = time_now();
}

static size_t token_buffer_consume(token_buffer *tbf, size_t bytes)
{
  // Update the tokens
  uint64_t now = time_now();
  size_t delta = (size_t)(tbf->rate * (now - tbf->timestamp));
  tbf->tokens = (tbf->capacity < tbf->tokens+delta)?tbf->capacity:tbf->tokens+delta;
  tbf->timestamp = now;

  fprintf(stdout, "TOKENS %d  bytes: %d\n", tbf->tokens, bytes);

  if(bytes <= tbf->tokens) {
    tbf->tokens -= bytes;
  } else {
    return -1;
  }

  return 0;
}

然后在main()中的某个位置：

while(1) {
  len = read_msg(&msg, file);

  // Loop until we have enough tokens.
  // if len is larger than the bucket capacity the loop never ends.
  // if the capacity is too large then no rate limit occurs.
  while(token_buffer_consume(&tbf,msg, len) != 0) {}

  send_to_net(&msg, len);
}

Answer 1

您正在通过max_burst限制您的最大消息大小(在开始时分配给tbf->容量)-由于tbf->内标识的增量永远不会超过该值，因此由于以下检查，将永远不会发送更大的消息：

if(bytes <= tbf->tokens) {
    tbf->tokens -= bytes;
  } else {
    return -1;
  }

因此，代码确实将burst的硬限制设置为max_burst -因此，如果您想要此burst大小，您应该对消息进行分段。

假设这是代码中唯一可以插入限制器的地方，如果用以下内容替换上面的内容可能会得到更好的结果：

if(tbf->tokens > 0) {
  tbf->tokens -= bytes;
} else {
  return -1;
}

语义将略有不同，但平均而言，在很长一段时间内，它应该会得到大约您正在寻找的速率。当然，如果您通过1gbps链路在一条消息中发送125K，人们很难谈论900kbps的速率-它将是完整的1gbps包突发，它们将需要在某处排队，以防存在速度较低的链路-因此，准备好在这种情况下丢失一些包。

但是，取决于您的应用程序和您正在使用的传输网络协议(TCP/UDP/SCTP/...)您可能希望将整形代码向堆栈下移-因为网络上的数据包通常只有1500字节的最大值(包括各种网络/传输协议报头)

对于测试来说，有趣的一件事是http://www.linuxfoundation.org/en/Net:Netem -如果您的目标是尝试解决较小容量的链路。或者，找几台背靠背连接着1 1mbps串行端口的老式路由器。