 |
Claims  |
|
|
What is claimed is:
1. A packet communications network comprising
a plurality of switching nodes interconnected by a larger plurality of transmission links,
at least one source of traffic connected to one of said nodes and producing data packets having differing quality of service requirements,
a data buffer in said one of said nodes,
means for accepting data packets into said network with a first quality of service requirement only if the occupancy of said data buffer is less than a pre-defined threshold defined for said first quality of service requirement;
means for characterizing said traffic from said source by an effective bandwidth which simultaneously satisfies said quality of service requirements for all of said packets having different quality of service requirements,
means for reserving a connection through said network for said traffic having a bandwidth equal to said effective bandwidth;
means for transmitting the combined data stream from said data buffer on said connection through said network; and
means for selecting said pre-defined threshold such that the bandwidth required to meet all of said quality of service requirements is minimized.
2. The packet communications network according to claim 1 further comprising
means for minimizing said effective bandwidth.
3. The packet communications network according to claim 1 further comprising
means for generating a traffic vector including said effective bandwidth and the mean and variance of said traffic from said at least one source; and
means for utilizing said traffic vector for reserving said connection.
4. The packet communications network according to claim 3 further comprising
means for adding said traffic vector to the link traffic vector for each link in said connection when said connection is set up; and
means for subtracting said traffic vector from the link traffic vector for each link in said connection when said connection is taken down.
5. The packet communications network according to claim 2 further comprising
means for determining the effective bandwidth c.sub.1 for one of said data packets having a first quality of service requirement in accordance with the relationship ##EQU33## .lambda..sub.0 is the rate at which a second different quality of
service data packets are produced;
.lambda..sub.1 is the rate at which said first quality of service data packets are produced;
B.sub.1 is said pre-defined threshold;
.epsilon..sub.1 is the desired probability of loss of said first quality of service data packets;
.alpha. is the average amount of time said source of traffic stays off, assuming an exp(.alpha.) exponential distribution of said times;
.beta. is the average amount of time said source of traffic stays on, assuming an exp(.beta.) exponential distribution of said times;
means for determining the effective bandwidth c.sub.0 for data packets having said second quality of service requirement, where c.sub.0 is the maximum real root of the cubic equation ##EQU34## where .epsilon..sub.0 is the probability of loss of
packets with said second quality of service requirements;
B.sub.0 is the size of said data buffer; and
means for utilizing the maximum of c.sub.1 and c.sub.0 as said effective bandwidth.
6. The packet communications network according to claim 1 further comprising
binary searching means for determining the size of said pre-determined threshold, said binary search means comprising
means for initilizing the upper and lower bounds on said threshold at the size B.sub.0 of said data buffer and zero;
means for determining the average B of said upper and lower bounds on said threshold;
means for determining a temporary variable T.sub.1 according to the formula ##EQU35## .lambda..sub.0 is the rate at which a second quality of service data packets are produced;
.lambda..sub.1 is the rate at which said first quality of service data packets are produced;
.epsilon..sub.1 is the desired probability of loss of said first quality of service data packets;
.alpha. is the average amount of time said source of traffic stays off, assuming and exp(.alpha.) exponential distribution of said times;
.beta. is the average amount of time said source of traffic stays off, assuming an exp(.beta.) exponential distribution of said times;
means for determining a second temporary variable T.sub.2 according to the formula ##EQU36## .lambda..sub.0 is the rate at which said second quality of service data packets are produced;
.epsilon..sub.0 is the desired probability of loss of said second quality of service data packets;
.alpha. is the average amount of time said source of traffic stays off, assuming an exp(.alpha.) exponential distribution of said times;
.beta. is the average amount of time said source of traffic stays on, assuming an exp(.beta.) exponential distribution of said times;
means for utilizing said average value as said threshold value when the difference between said temporary variables T.sub.1 and T.sub.2 is less than a pre-selected error value;
means for setting said lower value of said threshold at said average value when said first temporary variable T.sub.1 is greater than said second temporary variable T.sub.2 and said difference is not less than said pre-selected error value;
means for setting said upper value of said threshold at said average value when said first temporary variable T.sub.1 is not greater than said second temporary variable T.sub.2 and said difference is not less than said pre-selected error value;
and
means for re-determining said average B of said upper and lower bounds, for re-comparing said first and second temporary variables T.sub.1 and T.sub.2, and for readjusting said upper or lower bounds when said difference is not less than said
pre-selected error value.
7. A method for operating a packet communications network comprising the steps of
interconnecting a plurality of switching nodes by a larger plurality of transmission links,
connecting at least one source of traffic to one of said nodes, said source producing data packets having differing quality of service requirements,
admitting data packets with a first quality of service requirement to a data buffer only if the occupancy of said data buffer is less than a pre-defined threshold defined for said given quality of service requirement;
characterizing said traffic from said source by an effective bandwidth which simultaneously satisfies said quality of service requirements for said packets having different quality of service requirements,
reserving a connection through said network for said traffic having a bandwidth equal to said effective bandwidth;
transmitting the data stream from said data buffer on said connection through said network; and
selecting said pre-defined threshold such that the bandwidths required to meet all of said quality of service requirements individually are equal to each other.
8. The method according to claim 7 further comprising the step of minimizing said effective bandwidth.
9. The method according to claim 7 further comprising the steps of
generating a traffic vector including said effective bandwidth and the mean and variance of said traffic from said at least one source; and
utilizing said traffic vector for reserving said connection.
10. The method according to claim 9 further comprising the steps of
adding said traffic vector to the link traffic vector for each link in said connection when said connection is set up; and
subtracting said traffic vector from the link traffic vector for each link in said connection when said connection is taken down.
11. The method according to claim 8 further comprising the steps of
determining the effective bandwidth c.sub.1 for one of said data sources having a first quality of service requirement in accordance with the relationship ##EQU37## .lambda..sub.0 is the rate at which a second different quality of service data
packets are produced;
.lambda..sub.1 is the rate at which said first quality of service data packets are produced;
B.sub.1 is said pre-defined threshold;
.epsilon..sub.1 is the desired probability of loss of said first quality of service data packets;
.alpha. is the average amount of time said source of traffic stays off, assuming an exp(.alpha.) exponential distribution of said times;
.beta. is the average amount of time said source of traffic stays on, assuming an exp(.beta.) exponential distribution of said times;
determining the effective bandwidth c.sub.0 for another of said data packets having a second quality of service requirement, where c.sub.0 is the maximum real root of the cubic equation ##EQU38## where .epsilon..sub.0 is the probability of loss
of packets of said second quality of service requirements;
B.sub.0 is the size of said data buffer; and
means for utilizing the maximum of c.sub.1 and c.sub.0 as said effective bandwidth.
12. The method according to claim 8 further comprising the steps of
utilizing binary searching means for said step of determining the size of said pre-determined threshold, said step of utilizing binary search means comprising the steps of
initializing the upper and lower bounds on said threshold at the size B.sub.0 of said data buffer and zero;
determining the average B of said upper and lower bounds on said threshold;
determining a temporary variable T.sub.1 according to the formula ##EQU39## .lambda..sub.0 is the rate at which a second quality of service data packets are produced;
.lambda..sub.1 is the rate at which said first quality of service data packets are produced;
.epsilon..sub.1 is the desired probability of loss of said first quality of service data packets;
.alpha. is the average amount of time said source of traffic stays off, assuming an exp(.alpha.) exponential distribution of said times;
.beta. is the average amount of time said source of traffic stays on, assuming an exp(.beta.) exponential distribution of said times;
determining a second temporary variable T.sub.2 according to the formula ##EQU40## .lambda..sub.0 is the rate at which said second quality of service data packets are produced;
.epsilon..sub.0 is the desired probability of loss of said second quality of service data packets;
.alpha. is the average amount of time said source of traffic stays off, assuming an exp(.alpha.) exponential distribution of said times;
.beta. is the average amount of time said source of traffic stays on, assuming an exp(.beta.) exponential distribution of said times;
utilizing said average value as said threshold value when the difference between said temporary variables T.sub.1 and T.sub.2 is less than a pre-selected error value;
setting said lower value of said threshold at said average value when said first temporary variable T.sub.1 is greater than said second temporary variable T.sub.2 and said difference is not less than said pre-selected error value;
setting said upper value of said threshold at said average value when said first temporary variable T.sub.1 is not greater than said second temporary variable T.sub.2 and said difference is not less than said pre-selected error value; and
re-determining said average B of said upper and lower bounds, re-comparing said first and second temporary variables T.sub.1 and T.sub.2, and readjusting said upper or lower bounds when said difference is not less than said pre-selected error
value.
13. An access node in a packet communications network comprising
means for connecting at least one source of traffic to said access nodes, said source producing data packets having differing quality of service requirements,
a data buffer,
means for combining said data packets into a single data stream by selectively introducing packets from each of said source of traffic into said data buffer,
said means for combining data packets including means for admitting data packets with a first quality of service requirement only if the occupancy of said data buffer is less than a pre-defined threshold defined for said first quality of service
requirement;
means for characterizing said traffic from said source by an effective bandwidth which simultaneously satisfies said quality of service requirements for said packets having different quality of service requirements,
means for transmitting a request for reserving a connection through said network for said traffic having a bandwidth equal to said effective bandwidth;
means for transmitting the combined data stream from said data buffer into said network; and
means for selecting said pre-defined threshold such that the bandwidth required to meet all of said quality of service requirements is minimized.
14. The access node according to claim 13 further comprising
means for minimizing said effective bandwidth.
15. The access node according to claim 13 further comprising
means for generating a traffic vector including said effective bandwidth and the mean and variance of said traffic from said at least one source; and
means for utilizing said traffic vector for reserving said connection.
16. The access node according to claim 15 further comprising
means for adding said traffic vector to the link traffic vector for each link in said connection when said connection is set up; and
means for subtracting said traffic vector from the link traffic vector for each link in said connection when said connection is taken down.
17. The access node according to claim 14 further comprising
means for determining the effective bandwidth c.sub.1 for one of said data sources having a first quality of service requirement in accordance with the relationship ##EQU41## .lambda..sub.0 is the rate at which a second different quality of
service data packets are produced;
.lambda..sub.1 is the rate at which said first quality of service data packets are produced;
B.sub.1 is said pre-defined threshold;
.epsilon..sub.1 is the desired probability of loss of said first quality of service data packets;
.alpha. is the average amount of time said source of traffic stays off, assuming an exp(.alpha.) exponential distribution of said times; and
.beta. is the average amount of time and source of traffic stays on, assuming an exp(.beta.) exponential distribution of said times;
means for determining the effective bandwidth c.sub.0 for another of said data packets having a second quality of service requirement, where c.sub.0 is the maximum real root of the cubic equation ##EQU42## where .epsilon..sub.0 is the probability
of loss of packets of said second quality of service requirements;
B.sub.0 is the size of said data buffer; and
means for utilizing the maximum of c.sub.1 and c.sub.0 as said effective bandwidth.
18. The packet communications network according to claim 13 further comprising
binary searching means for determining the size of said pre-determined threshold, said binary search means comprising
means for initializing the upper and lower bounds on said threshold at the size B.sub.0 of said data buffer and zero;
means for determining the average B of said upper and lower bounds on said threshold;
means for determining a temporary variable T.sub.1 according to the formula ##EQU43## .lambda..sub.0 is the rate at which a second quality of service data packets are produced; .lambda..sub.1 is the rate at which said first quality of service
data packets are produced;
.epsilon..sub.1 is the desired probability of loss of said first quality of service data packets;
.alpha. is the average amount of time said source of traffic stays off, assuming an exp(.alpha.) exponential distribution of said times; and
.beta. is the average amount of time said source of traffic stays on, assuming an exp(.beta.) exponential distribution of said times;
means for determining a second temporary variable T.sub.2 according to the formula ##EQU44## .lambda..sub.0 is the rate at which said second quality of service data packets are produced;
.epsilon..sub.0 is the desired probability of loss of said second quality of service data packets;
.alpha. is the average amount of time said source of traffic stays off, assuming an exp(.alpha.) exponential distribution of said times; and
.beta. is the average amount of time said source of traffic stays on, assuming an exp(.beta.) exponential distribution of said times;
means for utilizing said average value as said threshold value when the difference between said temporary variables T.sub.1 and T.sub.2 is less than a pre-selected error value;
means for setting said lower value of said threshold at said average value when said first temporary variable T.sub.1 is greater than said second temporary variable T.sub.2 and said difference is not less than said pre-selected error value;
means for setting said upper value of said threshold at said average value when said first temporary variable T.sub.1 is not greater than said second temporary variable T.sub.2 and said difference is not less than said pre-selected error value;
and
means for re-determining said average B of said upper and lower bounds, for re-comparing said first and second temporary variables T.sub.1 and T.sub.2, and for readjusting said upper or lower bounds when said difference is not less than said
pre-selected error value. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
TECHNICAL FIELD
This invention relates to packet communications networks and, more particularly, to the management of multiple priority traffic in such networks.
BACKGROUND OF THE INVENTION
Digital data to be transmitted on a packet communications network can be characterized quite accurately by a very few statistical parameters. These parameters are normally used to determine if new traffic can be added to the transmission links
of the network. These parameters, which together form a vector representation of the source traffic, could, for example, include the mean and variance of the bit rate and the effective bandwidth for the traffic. In the U.S. Pat. No. 5,289,462, issued
Feb. 22, 1994, there is disclosed a traffic control system for packet communications networks utilizing an easily constructed and readily updated traffic load vector for representing the existing traffic load on each link of the network. A
computationally efficient algorithm for updating these traffic load vectors is also disclosed which allows such updating in real time as connections are added to or removed from the network. In particular, each connection on the network is represented
by a vector. The sum of all of the individual vectors representing all of the connections on a transmission link represents the total traffic on that transmission link. Each request for a connection or a disconnection is accompanied by a connection
vector which can merely be added to or subtracted from the link load vector. New traffic is admitted to a transmission link only if sufficient capacity remains to carry that new traffic. All traffic seeking access to the network is assumed to have a
single priority class, where priority class implies a particular guaranteed level of data loss probability.
In order to ensure that the traffic offered by each input connection remains consistent with the originally assumed statistical vector for that traffic, a so-called "leaky bucket" mechanism is provided to control the access of traffic to the
network at the access point. Such a leaky bucket mechanism is transparent to the traffic so long as that traffic remains within the originally assumed statistical traffic parameters. If the incoming traffic exceeds these assumed values, the leaky
bucket mechanism controls admission of the traffic to the network so as to enforce the original assumptions (until a new set of assumptions can be negotiated). One type of leaky bucket mechanism is described in the co-pending application Ser. No.
07/943,097, filed Sep. 10, 1992, now U.S. Pat. No. 5,511,513, and assigned to applicants' assignee.
Many types of digital traffic require two or more classes of traffic priorities for proper operation. For example, K. Lindberger discusses such a system in "Analytical Methods for Traffic Problems with Statistical Multiplexing on ATM Networks,"
Proceedings of the 13th International Teletraffic Congress, 1991. Multimedia traffic, in general, has the property that a single data source produces multiple data streams having different priority classes. Real time video data, for example, requires a
much higher priority class than does the audio signal accompanying the video traffic. The traffic management system of the afore-mentioned patent application Ser. No. 07/943,097, now U.S. Pat. No. 5,311,513, unfortunately, is capable of handling only
one priority class of traffic, and hence is unsuitable for multiple priority class traffic.
SUMMARY OF THE INVENTION
In accordance with the illustrative embodiment of the present invention, the traffic management system of the above-identified patent application is modified to handle data streams including data with a plurality of traffic priority classes to be
transmitted from the same source. More particularly, if a data stream including two classes of traffic are offered to a buffer at the input access to the network, the higher priority packets are always admitted into the buffer so long as there is room
for those high priority packets. Lower priority packets, on the other hand, are admitted to the buffer only if the buffer occupancy does not exceed a threshold value. In further accord with the present invention, the threshold for admittance of the
lower priority packets is calculated so as to enforce the desired probability of loss for both priority classes and, at the same time, minimize the bandwidth requirements for the combined stream of two-priority traffic. More particularly, the buffer
size and threshold are selected so as to satisfy both quality of service loss probability requirements while simultaneously minimizing the channel bandwidth which must be reserved for carrying the multiple-priority traffic.
In accordance with one feature of the present invention, the determination of an appropriate lower priority class buffer admission threshold leads to the definition of an "effective bandwidth" for the multiple-priority data stream which comprises
a better characterization of the traffic than the directly calculated bandwidth capacity. As taught in U.S. Pat. No. 5,289,462, an effective bandwidth calculated to ensure the satisfaction of a desired level of loss probabilities provides a better
representation of the traffic which permits a more efficient utilization of the transmission facilities of the network, all as taught in the afore-mentioned patent.
A more advantage of the present invention is the ease of implementation of the multiple-priority data management algorithm since the necessary control parameters are easily calculated. In addition, the resulting management control system is a
readily implemented extension of the prior art single priority mechanism requiring few changes and very little additional computation complexity.
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 packet transmission network of the type in which the multiple-priority traffic management system of the present invention might find use;
FIG. 2 shows a graphical representation of a connection request message which might be used in the network of FIG. 1 to establish or to take down a particular connection in a multi-priority traffic management system in accordance with the present
invention;
FIG. 3 shows a more detailed block diagram of a typical decision point in the network of FIG. 1 showing the access and packet-forwarding switching facilities used in the traffic management system of the present invention;
FIG. 4 shows a detailed flow chart of the process for the handling of two-priority data from a data source by the transmission adaptors of FIG. 2 in accordance with the present invention;
FIG. 5 shows a flow chart of the process for determining an optimum effective bandwidth for a multi-priority signal source for use in reserving a connection for that traffic on the packet communications network according to FIG. 1; and
FIG. 6 shows a detailed flow chart of the process for determining an optimum acceptance threshold for a buffer storage mechanism which combines multi-priority traffic for transmission on the packet communications network of FIG. 1.
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 network 10 comprising eight network nodes 11 numbered 1 through 8. Each of the network nodes 11 is linked to others of the network nodes 11 by
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 the 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 decision points within the node. The network nodes 11 each comprise one or more decision points within the node, at which decision points 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 routes or paths between terminal nodes, providing access control to packets entering the network at that node, and providing directory services and maintenance of network topology data bases used to support route
calculations.
Each of end nodes 12 comprises either a source of digital data to be transmitted to another end nodes, a utilization device for consuming digital data received from 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 accordance with the present invention, some of the end nodes 12 are connected to
sources of two or more priority data which require transmission on the network of FIG. 1 to destinations also connected to the network of FIG. 1 at remote end nodes.
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 in this route, the route is calculated in accordance with an algorithm that insures that adequate bandwidth is available on every link for each new connection. One such algorithm is disclosed in the co-pending application, Ser. No. 07/874,917,
filed Apr. 28, 1992, now U.S. Pat. No. 5,233,604, and assigned to applicants' assignee. One 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 (or denying the new connection if sufficient bandwidth is not available). 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 pre-calculated route. The connection message of FIG. 2
comprises a routing field 20 which includes the information necessary to transmit the connection message along the pre-calculated 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 tested for statistical multiplexing with the previously existing signals on each link of the route. Typically, this connection request vector includes
the mean of the aggregate bit rate for the source, the variance of that bit rate from that source, and the equivalent bandwidth required for the new connection. The values in this connection request vector are used to test each link of the route to
determine if the new connection will actually be supported by the links, and to update, separately for each link, the link occupancy vector 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, 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 can then
be updated to reflect the removal of this connection by subtracting the vector for the removed connection.
In FIG. 3 there is shown a general block diagram of a typical packet network decision point such as is found in the network nodes 11 of FIG. 1. The decision point of FIG. 3 comprises a high speed packet switching fabric 33 onto which packets
arriving at the decision point are entered. Such packets arrive over transmission lines via transmission adapters 34, 35, . . . , 36, or originate in user applications in end nodes via application adapters 30, 31, . . . , 32. It should be noted that
one or more of the transmission adapters 34-36 can be connected to an intra-node transmission link connected to yet other packet switching fabrics similar to fabric 33, thereby expanding the switching capacity of the node. The decision point of FIG. 3
thus serves to connect the packets arriving at the decision point to a local user (for end nodes) or to a transmission link leaving the decision point (for network nodes and end nodes). The adapters 30-32 and 34-36 each include queuing circuits for
queuing packets prior to or subsequent to switching in fabric 33. In accordance with the present invention, these queuing circuits in adapters 34-36 are used to control the access of multiple priority traffic to the transmission links of FIG. 1.
A route controller 37 in the decision point of FIG. 3 is used to calculate optimum routes through the network for packets originating at one of the user application adapters 30-32 in the decision point. Network access controller 39 is used to
control the access of user data, including user multi-priority signals, to the network of FIG. 1 and to regulate the launching of packets onto the network whenever the transient bit rate of any connection exceeds the values assumed in making the original
connection. Both route controller 37 and control 39 utilize the vector representation of the new connection (field 22 of FIG. 2) in calculating new routes or for controlling access of signals on previously assigned routes. In addition, route controller
37 utilizes the link metric vectors representing current traffic on each link of the network, stored in topology data base 38, to calculate the new connection route through the network. Network topology data base 38 contains information about all of the
nodes and transmission links of the network of FIG. 1 which information is necessary for controller 37 to operate properly.
The controllers 37 and 39 of FIG. 3 may comprise discrete digital circuitry or may preferably comprise properly programmed general purpose digital computer circuits. Such a programmed computer can be used to generate and launch connection
request messages (FIG. 2) used to set up a connection and to generate headers for data packets originating at user applications in the decision point of FIG. 3 or connected directly thereto. Similarly, the computer can also be used to calculate feasible
routes for new connections and to calculate the necessary controls to regulate access to the network in order to prevent congestion. The information in data base 38 is updated when new links are activated or old links taken down, when new nodes are
added to the network or removed from the network, and when link loads change due to the addition or removal of new connections. Such information originates at the network node to which the resources are attached and is exchanged with all other nodes to
assure up-to-date topological information needed for route and access control operations. Such data can be carried throughout the network on packets very similar to the information packets exchanged between end users of the network.
The incoming transmission links to the packet decision point of FIG. 3 may comprise links from local end nodes such as end nodes 12 of FIG. 1, or links from adjacent network nodes 11 of FIG. 1. In any case, the decision point of FIG. 3 operates
in the same fashion to receive each data packet and forward it on to another local or remote decision point as dictated by the information in the packet header. The packet network of FIG. 1 thus operates to enable communication between any two end nodes
of FIG. 1 without dedicating any transmission or node facilities to that communication path except for the duration of a single packet. In this way, the utilization of the communications facilities of the packet network is optimized to carry
significantly more traffic than would be possible with dedicated transmission links for each communication path.
In FIG. 4 there is shown a flow chart of the process for admitting multi-priority traffic into transmission adaptor queues 34-36 of the decision point of FIG. 3 in accordance with the present invention. Assuming for the purposes of simplicity
that packets from a two-priority signal source, such as a multimedia signal source, arrive at one of the adapters 30-32 of FIG. 3 and are switched to one of the adapters 34-36 for entrance into the network of FIG. 1. Starting at start box 48, box 49 is
entered where the data packet or cell is received. Decision box 50 is then entered where it is determined whether or not the cell loss priority (CLP) assigned to this packet is equal to "1." That is, decision box 50 determines whether the arriving
packet is a high priority packet or a low priority packet. If the packet or cell is a high priority cell (CLP.noteq.1), decision box 51 is entered to determine whether or not the occupancy of the buffer store is greater than or equal to the size of the
buffer store (O.sub.B .gtoreq.B.sub.0), that is, there room in the buffer store for this packet. If not, box 53 is entered where the cell is discarded and then the process ended in box 54. If, on the other hand, there is room for this packet in the
packet store (O.sub.B <B.sub.0), box 56 is entered where this packet or cell is queued in the buffer store. In box 57, this cell is transmitted in the network of FIG. 1 when appropriate. The process of FIG. 4 then stops in terminal box 58.
If it is determined in decision box 50 that the packet is a low priority packet (CLP=1), decision box 55 is entered to determine whether or not the occupancy of the buffer stores exceeds a predetermined, calculated threshold B.sub.1, i.e.,
O.sub.B >B.sub.1.If the threshold is exceeded, box 53 is entered where the cell is discarded and the process terminated in box 54. If, however, the threshold is not exceeded, box 56 is entered where the cell is queued in the buffer register and, in
box 57, transmitted in the network of FIG. 1 when appropriate. The process then terminates in terminal box 58.
It can be seen that the flow chart of FIG. 4 serves to admit high priority cells (CLP=0) from a two-priority traffic source any time there is room for the high priority cell in the buffer. On the other hand, low priority cells (CLP=1) are
admitted to the buffer only if the occupancy of the buffer is below a predetermined threshold. The determination of the value of this threshold B.sub.1 will be described in detail in connection with the flow chart of FIG. 6. Note, however, that the
value of B.sub.1 is a function of the parameters of the two-parameter data stream and thus can be calculated prior to the actual transmission of the two-priority data stream and simply supplied to the circuits of FIG. 3.
The traffic from each two-priority data source must be characterized by a connection request vector to be inserted in field 22 of FIG. 2. The calculation of this vector is the subject matter of the present invention and involves the calculation
of an "effective bandwidth" which not only carries the two-priority traffic, but also ensures the satisfaction of the desired quality of service for each priority class. The calculation of a minimum value for this effective bandwidth will be described
in connection with FIG. 5. The resulting vector can be used, not only to reserve bandwidth on the links in the route to be followed by the two-priority traffic, but which can also be used, as taught in the co-pending application Ser. No. 07/943,097,
filed Sep. 10, 1992, now U.S. Pat. No. 5,311,513, and assigned to applicants' assignee, to control congestion in the network.
Before proceeding to the detailed algorithms of FIGS. 5 and 6, the mathematical basis for these algorithms will be discussed. For simplicity, two priority traffic will be considered in the preferred embodiment since ATM multimedia standards have
set aside only one bit to determine priority class. There exists a large literature on guaranteeing quality of service for a single priority traffic, including "Equivalent Capacity and its Application to Bandwidth Allocation in High Speed Networks," by
R. Guerin, H. Ahamdi and M. Naghshineh, IEEE Journal of Selected Areas in Communications, Vol. 9, pages 968-981, 1991. Typically, in single priority traffic, the quality of service is quantified by P{X=B.sub.0 }.ltoreq..epsilon., where X is the steady
state buffer content, B is the buffer size and .epsilon. is the maximum acceptable probability that a packet will be lost. The value of .epsilon. is a small positive constant (typically in the range of 10.sup.-8 to 10.sup.-10). The probability
P{X=B.sub.0 } can be interpreted as the probability that an incoming packet will be lost. The quality of service is thus measured in terms of the fraction of packets lost.
In the region where B.sub.0 is large and .epsilon. is small (the typical situation), the concept of "effective bandwidth" has been found to be a very useful traffic characterization, as taught by F. P. Kelly in "Effective Bandwidths at
Multi-Type Queues," Queuing Systems, Vol. 9, pages 5-15, 1991. Effective bandwidth is essentially a quantity that depends upon each source's characteristics and on the parameters B.sub.0 and .epsilon., and has the property that the quality of service
(as represented by B.sub.0 and .epsilon.) is guaranteed for all independent sources that are multiplexed onto a single channel if the sum of the effective bandwidths of the sources is less than the channel capacity. This result holds in the region where
B.sub.0 .fwdarw..infin. and .epsilon..fwdarw.0 in such a way that ##EQU1## approaches a constant.
For the purposes of this invention, the concept of an effective bandwidth vector for two-priority traffic is introduced, specifically that the quality of service for the two types of packets is given by:
where B.sub.0 is the buffer size, B.sub.1 is the threshold and .epsilon..sub.0 and .epsilon..sub.1 are small non-negative constants where 0<.epsilon..sub.0 <.epsilon..sub.1 <1. Again, P{X>B.sub.1 } can be interpreted as the
probability that a low priority packet is lost. Typically, .epsilon..sub.0 .congruent.10.sup.-8 to 10.sup.-10 while .epsilon..sub.1 .congruent.10.sup.-4 to 10.sup.-6. An effective bandwidth vector for a multi-priority source can then be defined which
is a vector of size k (k priorities, where k=2 for the two priority traffic of the preferred embodiment).
Assume a single Markovian on-off traffic source that stays on for an exp(.beta.) amount of time and off for an exp(.alpha.) amount of time. When the source is on, it produces two types of output: type 0 and type 1 at rates .lambda..sub.0 and
.lambda..sub.1, respectively. When the source is off, no output of any kind is produced. The outputs enter a common infinite capacity buffer that empties at a maximum rate of c. There is a single buffer threshold B.sub.1 such that outputs of both types
are accepted as long as the buffer content is less than B.sub.1 and only output of type 0 is accepted when the buffer content is greater than B.sub.1. To be precise, let X(t) be the buffer content at time t and Z(t) be the state of the source (1 if on
and 0 if off) at time t. A two-priority data source of this type can be characterized by three parameters (B.sub.0, B.sub.1, c), where c is the channel capacity in bits per second. In the following analysis, it is first assumed that B.sub.0, B.sub.1,
and c are fixed and represent the steady state of the buffer content process. An expression which ensures that this set of parameters satisfies the loss probability quality of service criterion, as represented by .epsilon..sub.0 and .epsilon..sub.1, is
developed. Assuming that (B.sub.0, B.sub.1) are held fixed, the channel capacity c is allowed to vary in order to ensure that the quality of service criteria are satisfied. This leads to an expression for an effective bandwidth vector [c.sub.0
(B.sub.0, B.sub.1), c.sub.1 (B.sub.0, B.sub.1)] such that if c.gtoreq.c.sub.i (B.sub.0, B.sub.1) for i=0,1, then the quality of service loss probabilities are satisfied. Then, if only B.sub.0 is fixed and B.sub.1 and c are allowed to vary, an expression
for an optimal B.sub.1.sup.* is obtained that minimizes the channel capacity c required to satisfy the quality of service criterion. Finally, the optimum buffer size expression and the optimal bandwidth allocation expression are solved simultaneously.
The buffer size B.sub.0 is left as a variable and a delay bound is added to the quality of service criteria. The result is an expression for optimal buffer size and effective channel capacity which meet all of the quality of service requirements.
To begin the analysis, if X(t) is the content of the buffer at time t and if Z(t) is the state of the source of two-priority signals (1 if on and 0 if off) at time t, then ##EQU2## where [x].sup.+ =max{x,0}. The steady state behavior of the
{X(t), t.gtoreq.0} process depends heavily on the value of the channel capacity c. The relevant regions are listed below:
Region 1:c.gtoreq..lambda..sub.0 +.lambda..sub.1. In this case, X(t) decreases with time and eventually reaches zero. Thus, X(t).fwdarw.0 with a probability of 1. That is, if the buffer empties faster than it can be filled, the content of the
buffer eventually goes to zero.
Region 2:.lambda..sub.0 +.lambda..sub.1 >c.gtoreq..lambda..sub.0. In this case, X(t) eventually goes below B.sub.1 and never again exceeds it. Thus the steady state distribution of X(t) is concentrated over [0,B.sub.1 ]. That is, if the if
the buffer empties faster than the arrival rate of the high priority traffic, but a lower than the arrival rate of the combined high and low priority traffic, the content of the buffer eventually goes blow the threshold and the low priority traffic is
never admitted.
Region 3: ##EQU3## Note that ##EQU4## is the mean arrival rate of type 0 output. In this case X(t) reaches a proper steady state with distribution over (0, .infin.). That is, if the buffer empties slower than the arrival rate of the high
priority traffic, but faster than the mean arrival rate of the low priority traffic, the buffer occupancy will vary over the entire possible range. This is the only region which can be exploited to serve the two-priority traffic in a practical fashion.
Region 4: ##EQU5## In this case, | | |
