Browse Prior Art Database

Bandwidth Required for a Set of Several Identical Sources

IP.com Disclosure Number: IPCOM000110634D
Original Publication Date: 1992-Dec-01
Included in the Prior Art Database: 2005-Mar-25
Document File: 3 page(s) / 114K

Publishing Venue

IBM

Related People

Roginsky, AL: AUTHOR

Abstract

Disclosed is an algorithm for computing the bandwidth that needs to be reserved for a number of connections multiplexed on a link to satisfy the loss probability quality of service requirement in a high-speed network. This algorithm is computationally simple and produces, in most practical cases, a precise value of the required bandwidth.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Bandwidth Required for a Set of Several Identical Sources

       Disclosed is an algorithm for computing the bandwidth
that needs to be reserved for a number of connections multiplexed on
a link to satisfy the loss probability quality of service requirement
in a high-speed network.  This algorithm is computationally simple
and produces, in most practical cases, a precise value of the
required bandwidth.

      Various methods for computing the amount of bandwidth required
for each individual user are described in [*].  These methods,
however, lead to a significant over-estimation of a true bandwidth.
While in some cases this overestimation can be beneficial (by
protecting a user in case of fast changes to the traffic's behavior),
in other situations it may result in an imposition of unnecessary
charges on a network user and in an under-utilization of the links.

      The disclosed five-step algorithm leads to a correct solution
when multiple identical sources are present.  It is based on an
efficient method of estimating the binomial coefficients.  While the
use of a binomial distribution in such situations is not new, it was
usually precluded by a very large number of calculations it lead to.
The algorithm described here, however, requires only a very small
number of multiplications and divisions and can be implemented in
real time.

      Assume that all sources are of the on-off type with the same on
probability p and the same maximum transmission rate of R
bits/second.  The total number of sources is N.  Consider the worst
possible case, i.e., when the link's output buffer has size 0.  The
required bandwidth is then equal to (k-1)R, where k is the smallest
integer such that
P{at least k sources are ON}, = PN + PN-1 + ... Pk<e
where
Pm =  Nm  pm(1-p)N-m                                        (1)

      Obviously, computing all of the binomial coefficients and the
powers of p  and of (1-p) in (1) is not practical since this would
involve some extremely large and some extremely small numbers.  The
disclosed algorithm takes a different approach and would require, in
most cases, a computation of only one of the Pm's.  Moreover, a
method is proposed to calculate the Pm's without dealing with very
small or very large numbers.

      The main idea is that if for some w>0 we can find such k
that Pk<e(1-w)          and                                      (2)
Pm+1/Pm<w for m>k
then
PN + PN-1+...+Pk(1+w+w2+...)<e.

      If, in addition, e(1-w)<Pk-1, then k cannot be made much
smaller, so it is very close to the target value.

      The following algorithm allows one to easily compute k as a
function...