home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Standards 1993 July / Disc.iso / inet / isoc / isocnews / issue1_3 / 030.502 < prev    next >
Encoding:
Text File  |  1993-02-08  |  6.0 KB  |  113 lines
  1.  
  2.  
  3. N-1-3-030.50.2, Gigabit Networks, by Craig Partridge*, <craig@aland.bbn.com>
  4.  
  5. As several researchers are fond of pointing out, transmitting and
  6. receiving at gigabit speeds isn't the hard problem facing us.  The
  7. really hard problem is achieving gigabit speeds while providing
  8. service guarantees.  These service guarantees include features like
  9. bounding the maximum delay or ensuring a video transmission will get
  10. enough bandwidth.
  11.  
  12. In this column, we'll look briefly at a piece of the problem of
  13. providing service guarantees: traffic shaping.  The basic idea behind
  14. traffic shaping is the following.  Assume we have a flow (or stream,
  15. or connection, or whatever is your favorite word for transmission path
  16. between two transport endpoints) which needs the network to guarantee
  17. that the end-to-end delay over the flow will be less than a certain
  18. amount, and the loss rate will not exceed a certain level.  To make
  19. those kinds of guarantees, the network needs to know something about
  20. how the flow is going to behave.  For example, if the flow is going to
  21. be sending 1 megabit packets at an average of 1 gigabit per second, a
  22. different path may be required than for a flow sending 1 Kbit packets
  23. at 56Kbit/s.  The idea behind traffic shaping is to find ways to
  24. describe how the flow will place packets into the network (size of
  25. packets, average bandwidth, etc) in such a way that the network both
  26. knows what to expect (and can punish flows which exceed the behavior
  27. promised), and can use the description of the flow to do scheduling
  28. inside the network.  (As an aside, if the network does no scheduling,
  29. it can clearly make no promises.  Exactly how much scheduling is
  30. required, however, is a hot topic of debate).
  31.  
  32. Probably the most popular way to do traffic shaping is by using of a
  33. set of schemes collectively known as "leaky bucket".  There are
  34. actually a number of variations on leaky bucket.  I'll describe three
  35. versions here.
  36.     
  37. The first and original version of leaky bucket is the simplest.  It
  38. was designed to work with Asynchronous Transfer Mode (ATM).  ATM
  39. transmits fixed-size packets called cells.  Whenever a flow wants to
  40. send a bunch of cells, it puts the cells into a fixed-size queue,
  41. called a bucket.  At some rate, R, the cells are removed, one by one,
  42. from the bottom of the bucket and sent over the network.  If the flow
  43. tries to put too many cells into the bucket, the bucket "overflows".
  44. Essentially, what simple leaky bucket does is convert a possibly
  45. bursty stream of cells from the flow into a constant bit-rate
  46. transmission pattern on the network.
  47.  
  48. The problem with simple leaky bucket is that it is too simple.  A lot
  49. of data communications traffic has the property that its average
  50. bitrate is pretty low, but there are occasional large bursts of
  51. traffic.  Simple leaky bucket will force the flow to describe itself
  52. as sending at the maximum burst rate, rather than the average rate, if
  53. the flow wants to get enough bandwidth to send its bursts quickly.
  54. But since the flow will usually not send at the burst rate, the
  55. network will likely over-allocate resources to the flow.  So traffic
  56. shaping according to simple leaky bucket is likely to lead to poor
  57. utilization of the network.  For this reason, many researchers
  58. currently prefer another version of leaky bucket, sometimes called
  59. "token bucket".
  60.  
  61. In a token bucket scheme, instead of holding data, the bucket holds
  62. tokens, where each token represents the right to send a certain amount
  63. of data (usually a byte or a cell).  The bucket fills with credits at
  64. rate R.  Whenever the bucket gets full, the extra credits overflow the
  65. bucket and are discarded.
  66.  
  67. When a flow wants to send some data (a packet or a cell), it looks in
  68. the token bucket to see if the bucket contains a number of tokens
  69. equal to the amount of data the flow wants to send.  If there are
  70. enough tokens, the data is sent, and the tokens are removed from the
  71. bucket.  If there are not enough tokens, the flow must wait until
  72. enough tokens have accumulated.
  73.  
  74. Token bucket allows a flow to be bursty (because if the bucket is
  75. full, the flow can send an amount of data equal to size of the bucket
  76. without waiting) but a flow's burstiness is limited (after the bucket
  77. has emptied, the flow has to wait for it to start to fill again).
  78. Expressed formally, the token bucket scheme says that if the bucket
  79. size is B, in any time interval T, the maximum amount of data that the
  80. flow can send is equal to B+(R*T) tokens.
  81.  
  82. There's one small problem with token bucket.  What if the bucket size
  83. is really big?  Then, in the worst case, a flow could blast a whole
  84. bucket's worth of data onto its network link without waiting.  Now
  85. what if that network link is a LAN shared among several hosts?
  86. Perhaps we don't want one flow to be able to hog the link for very
  87. long.  One way to solve this problem is use both a token bucket and a
  88. leaky bucket in sequence.  After the token bucket lets the data past,
  89. the data is thrown into the leaky bucket.  The leaky bucket rate is
  90. set very high (much higher than the token bucket rate) but still below
  91. the link bandwidth.  This way, even if the flow is blasting away, the
  92. leaky bucket ensures there is some bandwidth left for other hosts on
  93. the LAN.
  94.  
  95. That's a quick survey of leaky bucket.  By now, I expect you're
  96. beginning to wonder why you needed this much detail on leaky bucket.
  97. The answer is that early this year there was a very nice Ph.D.
  98. dissertation published by Abhay K.J. Parekh at MIT.  Parekh proved
  99. that in networks that used Fair Queueing in their gateways, if flows
  100. were described (and constrained) by the token bucket plus leaky bucket
  101. scheme described in the last paragraph, it is possible to make
  102. guarantees about worst-case delay and the minimum bandwidth a flow
  103. will receive.  In other words, we now know at least one way to provide
  104. performance guarantees to bursty traffic sources!
  105.  
  106. Parekh's dissertation, "A Generalized Processor Sharing Approach to
  107. Flow Control in Integrated Services Networks" (1991 Ph.D. -- LIDS
  108. Report 2089), is available from MIT for about $50 USD [call +1 (617)
  109. 253-5650 to order a copy].
  110.  
  111.  
  112. *Research Scientist, BBN
  113.