Subject: token bucket analysis software

From: Craig Partridge <[email-masked]>
Date: Wed, 11 Jan 95 09:04:26 -0800

Hi folks:
    
    After a hallway conversation with Mark Garrett at IETF about trying to
trace token bucket cost curves, I wrote a little program to trace out token
bucket curves and estimate the knee in the curve based on a cost function.

    I now have permission to distribute the software (subject to the
copyright notice appended to the man page).  The manual page is appended.
If you think you might find it useful, drop me a note and I'll send you
a shar file. (I don't have a convenient anonymous FTP site, and at this point,
the first users will probably have a number of improvements to suggest and
I'd like to know who is using the program).

Thanks!

Craig

TB(1)                    USER COMMANDS                      TB(1)

NAME
     tb - compute a token bucket curve from a trace

SYNOPSIS
     tb [ -vk ] tracefile

DESCRIPTION
     tb reads a trace of data traffic and examines the  range  of
     token  bucket  values  (rate  and  bucket  size) which could
     describe the data.  For a range of rates, tb  generates  the
     minimum token bucket size required to transmit each piece of
     data between the time it arrives and the time the next piece
     of  data arrives (with the exception that multiple pieces of
     data arriving at the same time are treated as one  piece  of
     data).

     By default tb prints out a range of 100  points  (rate  fol-
     lowed by token bucket size) on the curve, in a form suitable
     for input to programs like gnuplot.  Various  flags  can  be
     used  to  cause  tb  to search for a knee in the curve where
     rate and bucket size tradeoffs balance  and  to  print  some
     information about the general properties of the data such as
     mean and peak rates.

     The trace file format is a series of lines, each  containing
     two  numbers.  The first number is the time (an integer) and
     the second number is the size of the data (an integer).   tb
     simply  computes  all values in terms of data units per unit
     of time so it is up to user to determine the  time  unit  to
     use  in  tracing  the data and the data unit (e.g., bytes or
     cells) used to measure data sizes.  Note that the last entry
     in  the trace should have a zero data length and a timestamp
     greater than the next to last piece of data (to force  send-
     ing of the last true piece of data).

OPTIONS
     -v   verbose mode.   Print  out  peak  and  mean  rates  and
          minimum and maximum bucket sizes.  The peak rate is the
          maximum amount of data sent between two time increments
          in  the  trace and assumes that the data is sent evenly
          over time units.

     -k   search for a knee.  tb will print out a  point  on  the
          curve  where  the  tradeoff between the bucket size and
          rate is optimized.  The algorithm used  in  tb  assumes
          that,  within  their ranges, rate and bucket sizes have
          equal cost (e.g., a 1% increase in rate for a 2% reduc-
          tion  in bucket size is worthwhile, as is a 1% increase
          in bucket size for a 2% reduction in rate).

ALGORITHM
     tb surveys the trace by simulating the use of several  token
     buckets  with  different  rates.   For each token bucket, tb
     assumes that at the start of the trace the token  bucket  is
     full  (but  of  unknown  size but initially guessed to be of
     size 0) and the rate is fixed.  tb  then  scans  the  trace,
     examining  the  amount of data that arrives in each non-zero
     span of time.  For each amount of data, tb first reduces the
     amount  by  the rate*interval product (to reflect the amount
     of data that was transmitted at the rate) and then  compares
     the  remainder  with the number of tokens in the bucket.  If
     this remainder is smaller than the number of tokens  in  the
     bucket, the bucket size is increased by the remainder.

     This algorithm works because  of  the  assumption  that  the
     bucket  was  full at the start, and the fact that if a given
     bucket size was sufficient to  time  T  in  the  trace,  any
     increase,  I, made to the bucket size will allow I tokens to
     stay in the bucket from the start of the  trace  to  time  T
     (and thus fill the need for more tokens at time T).

LIMITATIONS
     tb is limited to traces whose time units do not  exceed  the
     maximum size of a signed integer and in which the total data
     sent does not exceed the size of  a  double  width  unsigned
     integer.

     The algorithm used to find the knee in the  curve  bears  no
     relationship to likely tariff tables.

AUTHOR
     Craig Partridge.  The algorithm  used  was  developed  in  a
     hallway conversation with Mark Garrett.

NOTICE
     Copyright(c) 1995 by BBN Systems and Technologies,  A  Divi-
     sion  of  Bolt  Beranek  and Newman Inc.  Permission to use,
     copy, modify, distribute, and sell  this  software  and  its
     documentation for any purpose is hereby granted without fee,
     provided that the above copyright notice and this permission
     appear  in  all  copies and in supporting documentation, and
     that the name of Bolt Beranek and Newman Inc.  not  be  used
     in  advertising  or  publicity pertaining to distribution of
     the software without specific, written prior permission. BBN
     makes  no  representations  about  the  suitability  of this
     software for any purposes.  It is provided "AS  IS"  without
     express or implied warranties.