 |
Description  |
|
|
TECHNICAL FIELD
This invention relates to traffic management in packet communications
networks and, more particularly, to traffic monitoring, traffic
measurement filtering, and adaptive bandwidth adjustment for such
networks.
BACKGROUND OF THE INVENTION
In order to avoid congestion and insure adequate traffic flow in packet
communication networks, it is common to control the access of packet
sources to the network on an ongoing basis. In order to successfully
control traffic access, it is necessary, first, to accurately characterize
the traffic so as to provide appropriate bandwidth for carrying that
traffic. Simple measurements which provide accurate estimates of the
bandwidth requirements of a source are taught in the copending application
Ser. No. 07/942,873, filed Sep. 10, 1992, U.S. Pat. No. 5,274,625, and
assigned to applicants' assignee. In this application, the parameters used
to characterize traffic include R, the peak bit rate of the incoming
traffic in bits per second, m, the mean bit rate of the incoming traffic
in bits per second, and b, the mean burst length of the traffic in bits.
Rather than using the actual burst length, however, a so-called
"exponential substitution" technique is used to calculate and equivalent
burst length which would produce the same packet loss probability if the
traffic were a well behaved exponentially distributed on/off process. For
traffic widely differing from such an exponential process, this equivalent
burst length produces a much more accurate characterization of the actual
traffic and therefore permits a higher density of traffic on the same
transmission facilities.
The measured parameters are used to control the access of signal sources to
the network when the actual traffic behavior departs significantly from
the initial assumptions. A leaky bucket mechanism is one technique for
controlling access to the network when the traffic exceeds the initial
assumptions, but yet permits transparent access to the network when the
traffic remains within these initial assumptions. One such leaky bucket
mechanism is shown in the copending application Ser. No. 07/943,097, filed
Sep. 10, 1992, U.S. Pat. No. 5,311,513, and assigned to applicant's
assignee. More particularly, the leaky bucket mechanism of this
application prevents saturation of the network by low priority packets by
limiting the number of low priority packets which can be transmitted in a
fixed period of time while imposing a minimum on the number of red packets
transmitted at a given time. Such leaky bucket control mechanisms optimize
the low priority throughput of the packet network. High priority traffic,
of course, is transmitted with little or no delay in the leaky bucket
mechanism.
The above-described mechanisms are suitable for controlling traffic only if
the traffic is reasonably well-behaved and remains within the general
vicinity of the initially assumed traffic parameters. The traffic
management system, however, must be structured to deal with traffic which
is not well behaved and which departs substantially from the initially
assumed traffic parameters. If such a departure persists for any
significant length of time, a new connection bandwidth must be assigned to
the connection to accommodate the new traffic parameters. Such adaptation
of the control system to radical changes in traffic behavior presents the
problems of filtering the traffic measurements to separate transient
changes of traffic behavior from longer term changes, and determining
reasonable ranges within which the initially assumed traffic parameters
can be maintained and outside of which new connection bandwidths must be
requested. A bandwidth too large for the actual traffic is wasteful of
connection resources while a bandwidth too small results in excessive
packet loss. Ancillary problems include reasonable ease in implementation
of the adaptation process and reasonable computational requirements in
realizing the implementation.
SUMMARY OF THE INVENTION
In accordance with the illustrative embodiment of the present invention,
dynamic adaptation of a traffic control system to changes in the traffic
parameters is provided by defining a region within which adaptation is not
required and outside of which a new bandwidth allocation must be
requested. In particular, the bandwidth requirement is adjusted upward if
the measurements indicate that either a desired maximum packet loss
probability will be exceeded or if the traffic on that connection will
start to unfairly interfere with other connections sharing the
transmission facilities. The bandwidth requirement can be adjusted
downward, on the other hand, if significant bandwidth savings can be
realized for both the user of the connection and for the balance of the
network, without violating any quality of service guarantees for all of
the connections. In further accord with the present invention, these
limits on the adaptation region are converted to values of effective mean
burst length and mean bit rates. The measured effective mean burst length
and mean bit rates are then filtered to insure that the filtered values
are statistically reliable, i.e., that a sufficient number of raw
measurements are involved to insure a preselected confidence level in the
results. This minimum number of raw measurements, in turn, determines the
amount of time required to collect the raw measurements, given the mean
bit rate of the traffic. This measurement time can be used to measure not
only the statistics of the incoming dam stream to the leaky bucket, but
also the effect of the leaky bucket on the incoming traffic. This latter
measurement allows a measure of how well the leaky bucket is dealing with
variances in the offered traffic and hence the packet loss probability.
When the traffic parameters fall outside of the desired adaptation region,
a new connection with a different bandwidth is requested in order to
accommodate the changes in the traffic parameters. Computations to
determine the need for adaptation can be minimized by using extrapolation
techniques between computed values marking the bounds of the adaptation
region, and confining consideration to only the upper right quadrant of
the adaptation region.
The adaptation mechanism of the present invention has the distinct
advantage of insuring a continuously reasonable traffic management
strategy by insuring dynamic adaptation when the needs of the connection
or the needs of the network call for such adaptation. Moreover,
unnecessary adaptation is avoided, reducing the overhead involved in such
adaptation.
BRIEF DESCRIPTION OF THE DRAWINGS
A complete understanding of the present invention may be gained by
considering the following detailed description in conjunction with the
accompanying drawings, in which:
FIG. 1 shows a general block diagram of a packet communications network in
which the dynamic traffic management mechanism of the present invention
might find use;
FIG. 2 shows a graphical representation of a connection request message
which might be used to set up initial connections and dynamically altered
connections in the packet communications network of FIG. 1, using the
dynamic traffic management mechanism of the present invention;
FIG. 3 shows a general block diagram of the network access subsystem for
the network of FIG. 1 in which the dynamic traffic management mechanism of
the present invention is implemented;
FIG. 4 shows a block diagram of the traffic characteristics estimation and
adaptation module forming a part of the network access subsystem of FIG.
3;
FIG. 5 shows a graphical representation, in the mean bit rate effective
burst length plane, of the adaptation region outside of which new
connection parameters are requested for an existing connection in
accordance with the present invention;
FIG. 6 shows the adaptation region of FIG. 5 replotted on the mean bit
rate, red marking probability plane to reduce the computational
requirement of determining operation outside of this adaptation region;
FIG. 7 shows a flow chart of the process for controlling the access to a
packet communications network such as that shown in FIG. 1, using the
adaptation region illustrated graphically in FIG. 6; and
FIG. 8 shows a flow chart of the process for updating a connection when
required by the procedure of the flow chart of FIG. 7.
To facilitate reader understanding, identical reference numerals are used
to designate elements common to the figures.
DETAILED DESCRIPTION
Referring more particularly to FIG. 1, there is shown a general block
diagram of a packet transmission system 10 comprising eight network nodes
11 numbered 1 through 8. Each of network nodes 11 is linked to others of
the network nodes 11by one or more communication links A through L. Each
such communication link may be either a permanent connection or a
selectively enabled (dial-up) connection. Any or all of network nodes 11
may be attached to end nodes, network node 2 being shown as attached to
end nodes 1, 2 and 3, network node 7 being shown as attached to end nodes
4, 5 and 6, and network node 8 being shown as attached to end nodes 7, 8
and 9. Network nodes 11 each comprise a data processing system which
provides data communications services to all connected nodes, network
nodes and end nodes, as well as providing decision points within the node.
The network nodes 11 each comprise one or more decision points within the
node, at which point incoming data packets are selectively routed on one
or more of the outgoing communication links terminated within that node or
at another node. Such routing decisions are made in response to
information in the header of the data packet. The network node also
provides ancillary services such as the calculation of new routes or paths
between terminal nodes, the provision of access control to packets
entering the network at that node, and the provision of directory services
and topology database maintenance at that node.
Each of end nodes 12 comprises either a source of digital data to be
transmitted to another end node, a utilization device for consuming
digital data received from another end node, or both. Users of the packet
communications network 10 of FIG. 1 utilize an end node device 12
connected to the local network node 11 for access to the packet network
10. The local network node 11 translates the user's data into packets
formatted appropriately for transmission on the packet network of FIG. 1
and generates the header which is used to route the packets through the
network 10.
In order to transmit packets on the network of FIG. 1, it is necessary to
calculate a feasible path or route through the network from the source
node to the destination node for the transmission of such packets. To
avoid overload on any of the links on this route, the route is calculated
in accordance with an algorithm that insures that adequate bandwidth is
available for the new connection. One such algorithm is disclosed in the
copending application, Ser. No. 07/874,917, filed Apr. 28, 1992, U.S. Pat.
No. 5,233,604, and assigned to applicant's assignee. Once such a route is
calculated, a connection request message is launched on the network,
following the computed route and updating the bandwidth occupancy of each
link along the route to reflect the new connection. One such connection
request message is shown in FIG. 2.
In FIG. 2 there is shown a graphical representation of a connection request
message to be launched from a source node in the network of FIG. 1 to a
destination node in the network along a precalculated route. The
connection message of FIG. 2 comprises a routing field 20 which includes
the information necessary to transmit the connection message along the
precalculated route. Also included in the connection request message of
FIG. 2 is a connection request vector 22 which characterizes the important
statistical characteristics of the new packet source and which allows this
new source to be statistically multiplexed with the previously existing
signals on each link of the route. As will be discussed in detail
hereinafter, the connection request vector includes a relatively few
parameters necessary to adequately characterize the packet source. As
described in the afore-mentioned copending application, Ser. No. 943,097
and assigned to applicant's assignee, these parameters might include the
maximum bit rate for the source, the mean of that bit rate, and the
equivalent burst length of packets from that source.
The values in the connection request vector are used to test each link of
the route to determine if the new connection can actually be supported by
that link, and to update, separately for each link, the link occupancy
metric for that link to reflect the addition of the new connection. If the
link occupancy has changed since the route was calculated, the connection
may be rejected at any node along the route, and the source node notified
of the rejection. Finally, in FIG. 2, the control fields 23 include
additional information used in establishing the connection, but which is
not pertinent to the present invention and will not be further discussed
here. Note that, when a connection is to be taken down, a connection
removal message having the same format as FIG. 2 is transmitted along the
route of the connection to be removed. The link occupancy of each link is
then updated to reflect the removal of this connection by subtracting the
metrics for the removed connection.
In FIG. 3 there is shown a general block diagram of the source bandwidth
management subsystem in accordance with the present invention comprising a
leaky bucket module 34 to which the user traffic on input line 39 is
applied. The output of leaky bucket module 34 is applied to the network 10
of FIG. 1. A subsystem similar to that shown in FIG. 3 is provided for
each source of user traffic to be applied to the network 10. These
bandwidth management subsystems are located in the endnodes 12 of FIG. 1
and one such a bandwidth management subsystem is provided for each
direction of transmission between two communicating users. Although such
bandwidth management subsystems can be realized with hard-wired circuit
components, the preferred embodiment utilizes a programmed computer since
such an implementation is more readily modified to accommodate
improvements and to reflect changes in traffic patterns.
In leaky bucket access control module 34l packets are launched into the
network on line 40 with one of at least two different priority classes,
conventionally called "red" and "green," where green is the higher
priority. Green packets are guaranteed a pre-specified grade of service
based on an acceptable level of delay and loss probability within the
network. The red packets do not have the same guarantees and are discarded
before the green packets when congestion occurs. Bandwidth-conserving
strategies for optimally marking packets in a leaky bucket mechanism is
disclosed in the copending application Ser. No. 943,097, filed Sep. 10,
1992, and assigned to applicants' assignee. In general, the function of
the leaky bucket module 34 is to "shape" the traffic before it enters
network 10 (FIG. 1), especially for user packets not conforming to the
initially provided statistical description, by marking such packets red.
If the traffic characteristics stay within the initially negotiated
values, however, the red marking mechanism is sufficiently limited to
insure the promised loss probability. If the incoming traffic
characteristics depart substantially from the negotiated values,
estimation and adaptation module 33 is invoked to take corrective action
since the leaky bucket module 34 can no longer cope with the new traffic.
As described in connection with FIG. 1, when a new connection is to be set
up through network 10, an initial estimate of the traffic characteristics
is made by the packet source. This estimate arrives at the bandwidth
management system of FIG. 3 on line 36 together with the quality of
service requirements on line 35. Such quality of service (QOS)
requirements include acceptable loss probabilities, acceptable delays,
real-time delivery requirements, and so forth. Connection agent 32 passes
these connection requirements on to path selection controller 30 which
uses these requirements, together with the up-to-date network description
in topology database 31 to calculate a connection path through network 10
(FIG. 1) which satisfies all of these requirements. One optimum connection
path selection controller is described in the copending application Ser.
No. 07/874,917, filed Apr. 28, 1992 and assigned to applicants' assignee.
Once calculated, the proposed connection path is encoded in a connection
request message such as that shown in FIG. 2 and launched as a bandwidth
request onto the network 10 over line 37 of FIG. 3.
The bandwidth request message of FIG. 2 traverses the calculated connection
path and, at each node along the route, is used to reserve, in the next
leg of the connection, the bandwidth required to satisfy the requirements
of the connection request. If sufficient bandwidth is available in each
link of the connection along the computed path, the destination endnode 12
(FIG. 1) receives the request and transmits back an acceptance of the new
connection. If, at any link along the route, insufficient bandwidth is
available due to changes in the traffic patterns, a denial of the
connection request is transmitted back to the source endnode. These
bandwidth replies, whether negative or positive, are delivered back to
connection agent 32 on line 38. If the connection is denied, the user
source is notified and another attempt at the connection can be made
later. If the connection is accepted, leaky bucket module 34 is activated
and supplied with the appropriate parameters to control the access of the
user traffic. The user then begins introducing traffic on line 39. At the
same time, estimation and adaptation module 33 begins monitoring this
incoming traffic to determine if any significant changes in the incoming
traffic characteristics have occurred during the life of the connection.
If so, module 33 notifies connection agent 32 to request a new bandwidth
allocation, supplying connection agent 32 with the new traffic parameters
required for the connection. As before, connection agent 32 launches a new
bandwidth request on line 37 requesting the adjustment of the bandwidth of
the connection. If the adjustment is accepted, the leaky bucket parameters
are updated with the new traffic characteristics and estimation and
adaptation module 33 continues to monitor the incoming traffic, but with
the new characteristics. Note that only a new bandwidth allocation is
requested, rather than a new connection. This saves the overhead involved
in taking down the old connection and setting up a new connection. If the
requested additional bandwidth is not available, the connection can be
either taken down or given a lower priority, depending on the original
negotiations with the sending party at the source node. The present
invention is an improvement in the estimation and adaptation module 33 of
FIG. 3.
In FIG. 4 there is shown a block diagram of an estimation and adaptation
module in accordance with the present invention comprising a box 41 which
uses the initial traffic parameters, supplied on line 36 of FIG. 3, to
calculate an adaptation region. For convenience, this adaptation region is
measured in units corresponding to the initially assumed mean bit rate of
the incoming user traffic and the initially calculated red marking
probability of the leaky bucket module 34 of FIG. 3. The actual input
traffic is applied to mean bit rate filter 45 to determine the actual
current mean bit rate of the incoming traffic. At the same time, the
actual red marking probability of the leaky bucket module 34 (responsive
to the actual traffic served by the leaky bucket module 34) is applied to
red probability filter 47. The function of filters 45 and 47 is to filter
out the transient changes in mean bit rate and red marking probability.
The filtered mean bit rate and the filtered red marking probability are
compared, in unit 42, to the adaptation region established in block 41. As
long as these filtered parameters remain within the adaptation region,
nothing is done. If either of the filtered parameters fall outside the
adaptation region, however, a new effective burst length is computed in
block 43 and the new effective burst length is used to request a new
connection for this user's traffic. Before proceeding to a more detailed
description of the adaptation process, the following variables will be
defined:
R The maximum bit rate, in bits per second, of the input traffic as
requested by the user source to initiate the connection.
m The mean bit rate, in bits per second, of the input traffic as requested
by the user source to initiate the connection.
b The mean burst length, in bits, of the input traffic as requested by the
user source to initiate the connection.
t The sampling period of both of filters 45 and 47. The filters 45 and 47
receive measurements and report filtered outputs to the compare unit 42
every t seconds, for a succession 1, 2, . . . n, . . . periods, at which
time compare unit 42 makes a decision.
m.sub.n The raw measurement of the mean bit rate of the input traffic for
the nth sampling period of duration t.
.xi..sub.n The raw measurement of the red marking probability being used in
the leaky bucket 34 during the nth sampling period of duration t.
m.sub.n The filtered value of the mean bit rate, as filtered by bit rate
filter 45 of FIG. 4, for the input traffic at the end of the nth sampling
period.
.xi..sub.n The filtered value of the red marking probability, as filtered
by red marking probability filter 47 of FIG. 4, for the leaky bucket at
the end of the nth sampling period.
b.sub.ef.sup.n The effective burst length of the incoming traffic at the
end of the nth sampling period, used to request a new connection.
.gamma..sup.n The green token generation rate used in the leaky bucket
module 34 of FIG. 3 during the nth sampling period. The green token rate
determines the rate at which packets marked green can be injected into the
network.
M.sub.g.sup.n The size of of the green token pool in the leaky bucket
module 34 of FIG. 3 during the nth sampling period. The size of the green
token pool determines the length of green packets injected into the
network.
Measuring the mean bit rate m.sub.n of the incoming traffic is simple. A
counter counts the number of bits received during the sampling period t
and divides this number by the length t. Similarly, the red marking
probability .xi..sub.n is equal to the number of packets marked red during
the sampling period t divided by the total number of packets transmitted
during the period t. It is these raw figures which are delivered to
filters 45 and 47, respectively, every t seconds. It will be noted that
adaptation region (established when the connection is initially set up and
once per bandwidth adjustment thereafter) is established in terms of the
units of the raw measurements m.sub.n and .xi..sub.n to avoid unnecessary
calculations. Similarly, the effective burst length b.sub.ef.sup.n is also
calculated only if the filtered m.sub.n or .xi..sub.n falls outside of the
adaptation region. As will be discussed hereinafter, an adaptation region
is established around a target red marking probability .xi..sub.T and a
target mean bit rate m.sub.T corresponding to the mean bit rate for the
sampling interval j after which the previous update was implemented and
which has been used by the network since that previous update.
As taught in the aforementioned patent application Ser. No. 942,873, the
effective burst length can be calculated by substituting for the actual
traffic stream an equivalent traffic stream having the same peak rate R,
the same mean bit rate m, and the same mean burst length b, but where the
substituted traffic stream conforms to a model having an on/off process
where the on and off periods are independent (mutually and among
themselves) and are exponentially distributed. This "exponential
substitution" process is used to calculate an effective burst length for
the actual traffic stream so that the actual traffic steam has the same
packet loss probability .epsilon. if the substituted traffic stream were
fed to the same transmission link. The packet loss probability .epsilon.
for the substituted traffic, as taught in the afore-mentioned application,
is given by
##EQU1##
where c is the speed of the transmission facility being used and X is the
buffer size of the transmission facility. Solving equations (1) and (2)
for effective burst length gives
##EQU2##
In the adaptation system of FIG. 4, the transmission facility is the leaky
bucket module 34 and hence the packet loss probability .epsilon. is the
red marking probability .xi..sub.n and the buffer size X is the size of
the green token pool M.sub.n. That is, the effective burst length is given
by
##EQU3##
where If the loss (red pack) probability falls outside of the desired
range, it is b.sub.ef.sup.n, together with R and m.sub.n, which are passed
to the connection agent 38 of FIG. 3 in order to attempt a bandwidth
update for the connection. If the bandwidth update request is accepted,
new leaky bucket parameters .gamma..sup.n+1 and M.sub.g.sup.n+l are
computed based on the new traffic parameters R, m.sub.n and
b.sub.ef.sup.n. The calculation and use of these leaky bucket parameters
is taught in detail in the aforementioned copending application Ser. No.
07/943,097.
The filters 45 and 47 report estimates of mean bit rate and red marking
probabilities, respectively, every t second. The value of t is determined
by how fast connection agent 32 can get replies to a request launched on
the network since it is useless for filters 45 and 47 to supply new
estimates which might require new connection requests faster than such
requests can be processed. Thus the sampling rate t is dependent on the
maximum round trip delay of the network 10 of FIG. 1 and thus dependent on
the network implementation. Each of filters 45 and 47 maps the current raw
measurement and all of the previous measurements into an estimate of the
filtered value. Let x.sub.1, x.sub.2, . . . x.sub.n be the raw
measurements and x.sub.1, x.sub.2, . . . , x.sub.n be the estimates (where
x is either rn or .xi.). While the mapping of filters 45 and 46 can be any
function, in the preferred embodiment of the present invention this
mapping is exponential. That is, the nth estimate x.sub.n is given by
x.sub.n =.alpha.x.sub.n-1 +(1-.alpha.)x.sub.n. (6)
where the filter parameter .alpha., lying between zero and one
(0<.alpha.<1), determines the relative reliability of the two terms in
equation (6). The value of .alpha. is determined as follows, taking up the
mean rate filter 45 of FIG. 4 first. Associated with the mean bit rate rn
is a number T.sub.m which is the amount of time required to collect the
smallest amount of information from which a "sufficiently accurate"
estimate of rn can be made. Let N.sub.m be the number of raw measurements
of m received by filter 45 in time T.sub.m, i.e., N.sub.m is the smallest
integer larger than T.sub.m /t. N.sub.m then is the smallest number of raw
measurements of m needed to determine a m.sub.N.sbsb.m which is
statistically reliable. For this reason, when it is first initialized,
filter 45 does not report any estimates to compare unit 42 until N.sub.m
measurements have been received. N.sub..xi. and T.sub..xi. can be defined
similarly to represent the minimum number and minimum collection period of
raw measurements for statistically reliable red marking probabilities in
filter 47. If all of the mean rate estimates are constant and equal to m,
the N.sub.m th estimate is given by
m.sub.N.sbsb.m =m.sub.0 +(1-.alpha..sub.m.sup.Nm)(m-m.sub.0). (7)
If, for example, it is desired to keep m.sub.N.sbsb.m within 90% of m from
the initial condition m.sub.0, then .alpha..sub.m satisfies
1-.alpha..sub.m.sup.Nm =0.9 (8)
and
.alpha..sub.m =0.1.sup.1/nm. (9)
Using confidence interval analysis, the determination of the value of
T.sub.m (and of T.sub..xi.) proceeds in the following steps:
1. Identify independent (or almost independent) identically distributed
(IIDs) "experiments" involved in measuring mean rate;
2. Determine the minimum number of experiments needed to achieve a desired
confidence interval; and
3. Determine T.sub.m as the amount of time needed to collect the minimum
number (from the previous step) of experiment results.
Assuming that the traffic can be modeled as an on/off process satisfying
the independence and exponential distribution assumptions, then the on/off
cycles are the IID experiments. Let B.sub.n and I.sub.n be the nth on and
off times, respectively, and let the mean bit rate in the nth cycle of
length B.sub.n +I.sub.n be Y.sub.n =RB.sub.n /(B.sub.n +I.sub.n). The
means of the common exponential distributions of B.sub.n and I.sub.n are
represented by .mu..sub.b.sup.-1 and .mu..sub.i.sup.-1, respectively, and
the mean of the IID random sequence {Y.sub.n, n=1, 2, . . . } is given by
m.sub..gamma. =.rho.R where .rho.=.mu..sub.i /(.mu..sub.i +.mu..sub.b)
(10a)
and its standard deviation is approximately given by
##EQU4##
Let M.sub.m be the smallest sample size in the sequence Y.sub.n such that
the sample mean m has a confidence interval (m-z.sub.m, m+z.sub.m) and a
confidence level .theta..sub.m. The let w.sub.m be obtained from the
normal distribution table to satisfy
{-w.sub.m .ltoreq.W.ltoreq.w.sub.m }=.theta..sub.m, (11)
where W is normally distributed with zero mean and unit variance. Then
M.sub.m is given by
##EQU5##
The time interval T.sub.m required for obtaining the desired confidence
level is then as the time required to obtain M.sub.m raw measurements. If
b.sub.ef is the mean burst length, then one measurement takes, on the
average, b.sub.ef /m seconds and T.sub.m is given by
##EQU6##
For the red marking probability filter 47 of FIG. 4, it is assumed that
every packet has the same probability of being marked red and that whether
or not it is marked red is independent of all of the others. Although this
is not strictly true, particularly when multiple packets arrive
back-to-back during an on period, the results used herein are not very
sensitive to the confidence level of the red marking probability .xi.
estimates. Let X.sub.i be a random variable indicating whether the ith
packet is marked red (X.sub.i =1) or green (X.sub.i =0). Then
##EQU7##
The standard deviation .sigma..sub.x of X.sub.i is
##EQU8##
Using the same steps used to compute the mean bit rate measuring period
T.sub.m, the smallest number M.sub..xi. of X observations to achieve a
confidence interval of (.xi.-z.sub..xi., .xi.+z.sub..xi.) and confidence
level .theta..sub..xi. is given by
##EQU9##
where w.sub..xi. is obtained similarly to w.sub.m. The desired measuring
period T.sub..xi. is then obtained as the time to observe the M.sub..xi.
packets. If L is the mean packet length (in bits), a packet will arrive on
the average every L/m seconds and T.sub..xi. is given by
##EQU10##
The filters 45 and 47 of FIG. 4 thus utilize the measurement periods
T.sub.m and T.sub..xi. defined in equations (13) and (17), respectively.
Filtered values m.sub.n and .xi..sub.n of the mean bit rate and the red
marking probability thus delivered to compare unit 42 once every T.sub.m
and T.sub..xi. seconds, respectively. These filtered values form a set
which can be compared in unit 42 to the acceptable sets of these values to
determine whether or not adaptation is required, i.e., a new connection
request is warranted. This comparison will be discussed in connection with
the adaptation region disclosed graphically in FIG. 5.
Before proceeding to a discussion of FIG. 5, it should generally be noted
that a new connection is requested when the mean bit rate or the
burstiness of the input traffic renders the leaky bucket mechanism 34
incapable of insuring 1) the negotiated overall packet loss probability of
that connection or 2) the packet loss probability of other connections
sharing the same links. 0n the other hand, a new connection can also be
requested when the mean bit rate or the burstiness of the input traffic
falls sufficiently low that 3) the throughput of the network can be
increased by reducing the bandwidth allocation for that connection, in the
process also reducing the user cost based on allocated bandwidth. In
accordance with the present invention, these three conditions are used to
define the bounds of the adaptation region shown in FIG. 5, as will be
shown below.
In FIG. 5 there is shown a graphical representation of the adaptation
region in accordance with the present invention for adapting the bandwidth
of a packet network connection in response to changes in the mean bit rate
and/or the burstiness of the traffic input to the network. Curve 51,
between points 50 and 52, represents the limit on the current connection's
overall packet loss probability. For the sake of simplicity, if the
overall packet loss probability .epsilon..sub.c of this connection stays
within the negotiated order of magnitude, that is, if .epsilon..sub.c
.epsilon. (0.5, 5.0).times..epsilon..sub.T, then no adaptation adjustment
is necessary. If .epsilon..sub.g and .epsilon..sub.r are the loss
probabilities, respectively, for the green and the red packets in the
network, it is assumed that the bandwidth allocation is done to equalize
these two loss probabilities and that the buffer management satisfies the
order relationship
O(.epsilon..sub.c)=.xi..sub.T
O(.epsilon..sub.r)+(1-.xi..sub.T)O(.epsilon..sub.g), (18)
where .xi..sub.T is the red marking probability, i.e., .xi..sub.T
=O(.epsilon..sub.g)/O (.xi..sub.r). When .xi. increases beyond .xi..sub.T,
the overall loss probability .epsilon..sub.c becomes unacceptable and the
bandwidth must be adjusted upward. In FIG. 5, curve 51 is the collection
of (m, b.sub.ef) points that yield .xi.=k.sub.1 .xi..sub.T where k.sub.1
is 5, the high order of magnitude limit on the target probability loss.
That is, curve 51 is the collection of sets of values of m and b.sub.ef
which satisfy
##EQU11##
Curve 53 between points 52 and 54 of FIG. 5 represents the limit on t | | |
