A method for admission control and routing by allocating network resources in network nodes

<u>Technical Field</u>

0001The invention relates to the admission control of requests for, and routing of, virtual circuits by allocating network resources.

<u>Background of the Invention</u>

0002Networks are a principal means of exchanging or transferring information <i>(e.g,</i> data, voice, text, video, etc.) among communication devices <i>(i.e.</i> devices for inputting and/or outputting information such as computer terminals, multimedia workstations, fax machines, printers, servers, telephones, videophones, etc.) connected to the networks.

0003A network typically comprises switching nodes connected to each other, and to communication devices, by links. Each link is characterized by a bandwidth or link capacity. Information input from the communication devices to the network may be of any form but is often formatted into fixed-length packets or cells. When information is to be exchanged between two communication devices, a path (comprising a set of nodes and links connecting the two communication devices) is established. This path is a so-called "virtual circuit" (VC) by which it is meant that one of the communication devices simply specifies the destination for the information, and the network delivers the information as though a dedicated circuit connected the two communication devices. Cells in transit between communication devices may temporarily be stored in buffers at nodes along the path of the virtual circuit pending sufficient available bandwidth on subsequent links along the path.

0004An important consideration in network operation is admission control and routing of virtual circuits. Admission control and routing is the process of deciding whether or not to admit requests for establishing new virtual circuits in the network and of selecting a path through the network for the requested virtual circuit. In particular, the task is to determine which VC requests the network can admit and route. The admission and routing determination may take into account various factors such as the network topology and current available network resources, such as buffer space in the nodes and capacity in the links, and any quality-of-service commitments <i>(e.g.</i> guaranteed bandwidth or maximum cell loss probability) made to users of the network.

0005The admission control and routing problems are typically addressed together. For example, when a network receives a request to establish a VC between communication devices, the network may initially select, based on a first criterion, a set of potential paths on which the requested VC may be routed. One such first criterion is to select, as the set of potential paths, all possible paths between the communication devices passing through less than a specified number of nodes. The network will then route the VC request on a path in the set of potential paths according to a second criterion <i>(e.g.</i> the VC will be routed on the path whose most heavily utilized link operates at the smallest percentage of its capacity). If no paths are in the set of potential paths or if no paths meet the second criterion, then the requested VC is not admitted.

0006The admission control/routing problem is complicated when a variable bit-rate (VBR) source or communications device seeks access to the network and requests a VC. The complication arises because the statistics which describe the variations in the information input from the VBR source to the network are often imprecise and thus it is difficult to predict what the requirements for network resources (such as requirements for buffer space in network nodes and requirements for bandwidth or capacity in network links) by the VBR source will be. For example, the bandwidth requirements of VBR sources typically vary with time, and the bandwidth variations typically are difficult to characterize. Thus, the admission/routing determination is made with information that may not accurately reflect the demands that the VBR source may place on the network thereby causing degraded network performance. More particularly, if the network resource requirements for a VBR source requesting a VC through the network are overestimated based on inaccurate characterizations of the VBR source, then the network will not run at full capacity in that a portion of the resources provided or allocated to the VBR source based on the the estimate will frequently not be used. Alternatively, if network resources are underestimated, the VBR source will input more information to the network than the network had provided for, and thus the network may become congested and cells traversing the network may be lost. <i>See, e.g.,</i> James W. Roberts, "Variable-Bit-Rate Traffic-Control in B-ISDN," <i>IEEE Comm. Mag.,</i> pp. 50-56, Sept. 1991; Anwar I. Elwalid and Debasis Mitra, "Effective Bandwidth of General Markovian Traffic Sources and Admission Control of High Speed Networks," <i>IEEE/ACM Trans. on Networking,</i> Vol. 1, No. 3, pp. 329-343, 1993. Roch Guerin et al., "Equivalent Capacity and its Application to Bandwidth Allocation in High-Speed Networks," <i>IEEE J. Sel. Areas in Comm.,</i> Vol. 9, No. 7, pp. 968-981, Sept. 1991.

0007Thus there is a need for improved methods for determining the network resources required by requests for virtual circuits and for using the resource requirements in the process of admitting and routing the VC requests.

<u>Summary of the Invention</u>

0008In accordance with the invention, requirements for network resources are allocated to a request for admission and routing of a virtual circuit from a communications device through a network, the network comprising nodes and links, where the requirements are determined based on a set of parameters used to control the flow or rate of information from the communications device into the network and onto the virtual circuit. The requirements for network resources advantageously include buffer space requirements in network nodes and bandwidth requirements in network links. The set of parameters advantageously characterize a function for controlling the flow of information from the device into the network such as the type of function performed by an access regulator. The determined network resource requirements may then be used in deciding whether to admit and how to route the requested virtual circuit in the network.

<u>Brief Description of the Drawings</u>

0009FIG. 1 illustrates a data network in which the inventive method may be practiced.

0010FIG. 2 illustrates the components of a leaky bucket regulator.

0011FIG. 3 is a flowchart illustrating the steps in the inventive method for admission control.

0012FIG. 4 illustrates an admissible region for the multiplexing of source classes for various loss probabilities.

0013FIG. 5 illustrates an admissible region for non-statistically multiplexable sources of a first class and statistically multiplexable sources of a second class.

0014FIG. 6 illustrates an admissible region in the multiplexing of a single variable bit rate sources in the presence of constant bit rate traffic.

0015FIG. 7 illustrates a periodic, on-off process of information departing from a regulator.

0016FIG. 8 is a block diagram of a virtual buffer/trunk system for a single source.

0017FIG. 9 illustrates the buffer content and utilized bandwidth for a virtual system for a single source.

0018FIG. 10 illustrates the determination of buffer space requirement and effective bandwidth.

0019FIG. 11 illustrates several possible admissible sets and statistical multiplexing gains for two traffic source classes.

<u>Detailed Description</u>

0020The following detailed description of the inventive method is divided into five sections. Section I provides an overview of the environment in which the inventive method may be practiced. Section II discusses the inventive method in a lossless multiplexing situation. Section III demonstrates how to classify sources as either statistically multiplexable or nonstatistically multiplexable. The section also describes how the inventive method can be used to allocate bandwidth and buffer for statistically multiplexable sources for a given cell loss probability. Section IV considers resource allocation for mixtures of statistically multiplexable, non-statistically multiplexable and constant bit rate sources. Section V provides a summary and conclusion.

<u>I.</u><u>Overview</u>

0021FIG. 1 illustrates a network in which the inventive method for admission control and routing of requests for virtual circuits (VCs) based on network resources required by the request may be practiced. Network 110 comprises switching nodes 130-<i>i</i> and links 140-<i>k.</i> Each communication device 105<i>-j</i> has associated with it devices, such as access regulators 120<i>-j,</i> which regulate the flow or rate of information from communication device 105<i>-j</i> into network 110 according to a function characterized by a set of (access regulator) parameters. For illustrative purposes, access regulator 120<i>-j</i> will be considered to be a leaky bucket regulator (LBR). However, other types of regulators, <i>e.g.</i> buffered leaky bucket regulators or cascaded leaky bucket regulators, may be used. Each communication device 105<i>-j</i> generates information for use by, or receives information from, other communication devices in the network. By information it is meant data, text, voice, video, etc. Information from communication device 105<i>-j</i> is characterized by a set of information parameters such as long term average transmission rate, peak rate and maximum burst size. The value of each information parameter in the set of information parameters is advantageously determined, for example, by contracting with the network for a maximum cell loss rate and for appropriate access regulator parameters <i>(i.e.</i> the rate at which information flows into the network from a device depends on the parameters of the access regulator which access regulator is advantageously a part of the network). For illustrative purposes, communication device 105-<i>j</i> includes such apparatus <i>(e.g.</i> analog-to-digital converters) so as to render the information suitable for transmission on network 110.

0022The operation of LBR 120<i>-j</i> is conceptually shown in FIG. 2. LBR 120-<i>j</i> comprises switch 222<i>-j</i> and buffer 224-<i>j</i>. LBR 120<i>-j</i> accepts information from communication device 105<i>-j.</i> The information from communication device 105<i>-j</i> is illustratively formatted into packets or cells, and information is input to LBR 120<i>-j.</i> Switch 222<i>-j</i> is closed and data is output from LBR 120<i>-j</i> only when a token is available in buffer 224<i>-j.</i> Buffer 224<i>-j</i> is capable of holding <i>B</i>_<i>Tj</i> tokens. Tokens are supplied to the buffer at rate <i>r</i>_<i>j</i><i>.</i> Information is output from LBR 120-<i>j</i> at a peak rate <i>P</i>_<i>j</i><i>.</i> Thus, LBR 120-<i>j</i> is characterized by three parameters: the token rate <i>r</i>_<i>j</i><i>,</i> which bounds the long term average rate of the information output from LBR 120<i>-j;</i> the token buffer size <i>B</i>_<i>Tj</i><i>,</i> which bounds the burst size; and a peak rate parameter <i>Pj,</i> which bounds the rate at which information may leave LBR 120<i>-j.</i>

0023In the illustrative LBR 120<i>-j</i> of FIG 2, if communication device 105<i>-j</i> inputs cells to LBR 120<i>-j</i> at a rate so great that the buffer underflows <i>(i.e.</i> so that the number of tokens in the buffer goes to zero), switch 222<i>-j</i> will open and cells will be lost. However, the LBR may be of the type in which, when no tokens are available, cells are "marked" as low priority cells; the marked cells are then routed through the network on a VC but are more likely to be dropped if congestion is encountered at nodes along the VC.

0024Returning to FIG. 1 when, for example, communication device 105-1 wishes to transmit information to communication device 105-2 via network 110, a virtual circuit (VC) is requested. A VC is a path comprising a set of nodes and set links between the LBRs associated with communication devices 105-1 and 105-2. For example in FIG. 2, one path for a VC between communication device 105-1 and 105-2 may comprise nodes 130-1, 130-2, 103-3 and links 140-1,140-3,140-5 and 140-7. Recall that each node 130-i has associated with it at least one buffer of size <i>B</i>_<i>i</i><i>,</i> and each link 140-<i>k</i> has associated with it a bandwidth capacity <i>C</i>_<i>k</i><i>.</i> Routing the requested VC on a path will require network resources, <i>e.g.</i> buffer space in the nodes along the path and bandwidth in the links along the path in transmitting information between devices 105-1 and 105-2. Moreover, before the requested VC can be routed, the network resources that are required must be determined so that a path can be selected which selected path has sufficient resources to accommodate the VC. In other words, if communications device 105-1 has a certain buffer requirement in the nodes and a certain bandwidth requirement in the links, the requested VC should be routed only on those paths comprising nodes and links with sufficient resources to meet the certain requirements.

0025FIG. 3 illustrates the steps in the inventive method for admission control and routing by determining required network resources. In order for a first communication device to transmit information to a second communication device, a VC must be requested as in step 310, and a decision is made on whether to admit the VC to the network and how to route the VC through the network <i>(i.e.</i> to select a path between the two communication devices on which the VC may be routed). In one embodiment, the information is routed through an access regulator and an effective bandwidth and an effective buffer requirement are assigned to the request for a VC where the effective bandwidth and effective buffer requirement are functions of the access regulator parameters which control the flow of information from the first communication device onto the VC as shown in step 320. Once the effective bandwidth and effective buffer requirement are determined, it can be determined which paths between the two devices are viable for routing the VC in step 330. For example, if either the effective bandwidth or effective buffer requirement for a requested VC are greater than the available capacity in a link (where the available capacity is the capacity of the link minus the bandwidth required by or allocated to other VCs routed through the link) or the available buffer space in a node, the VC cannot be routed through that link and node without exceeding the capacity. Note that once the viable paths are determined, the VC can be routed as in step 340. For example, any of the viable paths could be selected at random for routing the VC. Alternatively, the method can advantageously provide information useful in choosing on which viable path to route the requested VC as for example by routing the VC on the viable path whose most heavily utilized link operates at the smallest percentage of its capacity.

0026The request may advantageously be received by, and the decision on admission and routing may advantageously be made by, a network processor connected to every node in the network. In such a centralized system, the network processor has accurate information about the current level of congestion at each node, <i>i.e.</i> the network processor knows the content level of each node buffer and the traffic levels on links connected to each node. Alternatively, the request may be received, and decisions on routing and admission may be made, locally or in a decentralized manner at a node which node periodically receives signals which update information the node has about congestion at other nodes. Decentralized systems are more fault tolerant because no single network element makes all routing decisions. Centralized systems make decision with complete and current knowledge about congestion levels at nodes in the network rather than with information that may be dated <i>(i.e.</i> with knowledge that has not been updated).

0027The inventive method is first demonstrated in the case where the quality of service requirement is lossless performance, <i>i.e.</i> the network is operated so that no cells will be dropped due to exceeding available buffer space in a node or exceeding the available capacity in a link. If a virtual circuit is requested, and effective buffer requirement <i>b</i>₀ and effective bandwidth <i>e</i>₀ are determined. The determination is advantageously made as a function of the node and link parameters, <i>i.e.</i> the buffer size and link capacity, and of the access regulator parameters. Moreover, the ratio of the effective bandwidth <i>e</i>₀ to the capacity <i>C</i> of the link is advantageously proportional to the ratio of the effective buffer requirement <i>b</i>₀ to the size B of the node.

0028In the case where the access regulator is a leaky bucket regulator characterized by parameters, <i>B</i>_<i>T</i><i>,</i> r and P, as described above, the effective bandwidth <i>e</i>₀ and effective buffer requirement <i>b</i>₀ of a VC routed through the access regulator is:<maths id="math0001"><img file="EP0756403A2_D0001.tif" /></maths><maths id="math0002" num="(2)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">Be</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow><mrow><mtext mathvariant="italic">C</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0002.tif" /></maths> Note that if <i>e</i>₀_<i>,i</i> is the effective bandwidth of the <i>i</i>^<i>th</i> VC through a node connected to a link of capacity <i>C</i>, then the set of circuits <i>{</i>1,2,...<i>I}</i> is admissible if<maths id="math0003"><img file="EP0756403A2_D0003.tif" /></maths> The admissible set may equivalently be given by<maths id="math0004"><img file="EP0756403A2_D0004.tif" /></maths> where <i>b</i>_0,_<i>i</i> is the effective buffer requirement of the <i>i</i>^<i>th</i> VC through a node with buffer capacity B.

0029The inventive method can be expanded to the statistical multiplexing case. By statistical multiplexing it is meant that, advantageously assuming that communication devices input information to the network independently of each other, that the unutilized time varying portions of the resources allocated to VCs in the network can be used by allowing for small probabilities of loss of information. This is the lossy statistical multiplexing situation. Importantly, because the ratio of the effective bandwidth to the capacity C of the link is proportional to the ratio of the effective buffer requirement to the buffer of size <i>B</i> in the node, where the link is connected to the node (hereinafter the "node/link"), the problem of determining the effective allocation is reduced to a single resource allocation problem, <i>i.e.</i> once the effective bandwidth (buffer requirement) is known, the effective buffer requirement (bandwidth) is known. As shown more rigorously below, once a small rate of information loss is allowed, variable bit rate (VBR) traffic is found to be divisible into two classes, one for which statistical multiplexing is effective and one for which statistical multiplexing is ineffective in the sense that accepting small losses provides no advantage in terms of the number of sources that can be accommodated over requiring lossless performance. The classification of a VBR source into statistically multiplexable (SMUX) and non-statistically multiplexable (NSMUX) is likewise based on the probability of loss of information, <i>L</i>, and on the access regulator parameters. In particular, for given access regulator parameters and a specified probability of loss, a parameter <i>C</i>_<i>c</i><i>,</i> termed the "critical capacity," may be advantageously defined for a source of information:<maths id="math0005" num="(5)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">c</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> log</mtext><mfenced open="(" close=")"><mrow><mtext>1/</mtext><mtext mathvariant="italic">L</mtext></mrow></mfenced></mrow><mrow><mtext>log</mtext><mfenced open="(" close=")"><mrow><mtext>1/</mtext><mtext mathvariant="italic">w</mtext></mrow></mfenced></mrow></mfrac></mrow></math><img file="EP0756403A2_D0005.tif" /></maths> where <i>e</i>₀ is found from equation 1 above and <i>w,</i> for a leaky bucket regulator, is equal to <maths id="math0006"><math display="inline"><mrow><mfrac><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP0756403A2_D0006.tif" /></maths> . If <i>C > C</i>_<i>c</i><i>,</i> where <i>C</i> is the link capacity, the source is a statistically multiplexable source. If <i>C ≤ C</i>_<i>c</i><i>,</i> the source is non-statistically multiplexable. By the terms "statistically multiplexable" and "non-statistically multiplexable" it is meant the following: if more sources of a given type can be admitted when the maximum allowed probability of loss is increased from 0 to <i>L</i>, then the sources are statistically multiplexable. If no more sources can be admitted, then the sources are non-statistically multiplexable.

0030Consider the case in which only statistically multiplexable sources are admitted to the network. It is advantageous to group VCs from these sources by class. Let <i>J</i> denote the number of classes, where each class is associated with a particular set of access regulator parameters <i>(i.e. r, B</i>_<i>T,</i><i> P)</i> and <i>K</i>_<i>j</i> denotes the number of VCs of class <i>j</i>. To determine the effective bandwidth that a request for a VC in the <i>j</i>^<i>th</i> class should be allocated in a link of capacity <i>C</i> connected to a node with buffer size <i>B,</i> the <i>J</i>-class problem is broken down or decomposed into a series of single class problems. For a given acceptable information loss rate, <i>P</i>_<i>loss</i>, the maximum number of VCs of any one particular class, <i>K</i>_<i>max,j</i> , is the value of <i>K</i> which satisfies<maths id="math0007" num="(6)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">loss</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><mtext>exp{-</mtext><msub><mrow><mtext mathvariant="italic">F</mtext></mrow><mrow><mtext>K</mtext></mrow></msub><mfenced open="(" close=")"><mrow><mtext mathvariant="italic">s</mtext><mtext>*</mtext></mrow></mfenced><mtext>}</mtext></mrow><mrow><mtext mathvariant="italic">s</mtext><mtext>* σ</mtext><mfenced open="(" close=")"><mrow><mtext mathvariant="italic">s</mtext><mtext>*</mtext></mrow></mfenced><msqrt><mtext>2π</mtext></msqrt></mrow></mfrac><mtext></mtext><mtext mathvariant="italic">g</mtext></mrow></math><img file="EP0756403A2_D0007.tif" /></maths> where <i>g</i> is a constant (typically equal to 1) and where <i>F</i>_<i>K</i> and <i>s</i>* are functions of <i>K</i>, <i>e</i>₀_<i>,</i><i> C</i> and of the access regulator parameters associated with the class. Once <i>K</i>_<i>max,j</i> is found, an effective bandwidth <i>e</i>_<i>j</i> for a VC in the <i>j</i>^<i>th</i> class can be determined.<maths id="math0008" num="(7)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">max,j</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP0756403A2_D0008.tif" /></maths>

0031The set of values for <i>K</i>_<i>max,j</i>, <i>j=</i> 1,2,...<i>J</i>, define a linear boundary of the set of admissible VCs through a node with buffer size <i>B</i> and a link of capacity <i>C</i> as shown in FIG. 4 which illustrates the admissible region for the multiplexing of two source classes for various loss probabilities <i>L</i>. Line 410 illustrates the lossless case where the effective bandwidth for class 1 is <i>e</i>₁ and the effective bandwidth for class 2 is <i>e</i>₂<i>.</i> Lines 420 and 430 define the set of admissible VCs for cases where a small probability of loss is permitted. As above, the routing and admission problem can be solved by determining the number of VCs of each class already routed through a node/link and by determining if sufficient capacity at the node/link remains or is available. The remaining capacity can then be used for subsequently routed VCs.

0032There are alternative ways of computing the effective bandwidth <i>e</i>_<i>j</i><i>,</i> all of which typically require substantially more effort and time than the technique above. One variant also does calculations for each class separately and in isolation, but differs in the method for computing <i>K</i>_<i>max,j</i><i>.</i> Specifically, for each class a buffer distribution is computed directly, <i>i.e.,</i> without going through the intermediate step of lossless multiplexing. This multiplexing problem is solved either by a combination of mathematical and numerical techniques or by simulations. After <i>K</i>_<i>max,j</i> is calculated, <i>e</i>_<i>j</i> is obtained from (7). Another approach, which is also typically more time consuming and complex, does not consider classes in isolation and instead computes a maximal set <i>A</i> of all combinations of numbers of sources of each class such that the loss is less than <i>P</i>_<i>loss</i>. Thereafter, either <i>A</i> is stored in tabulated form or conservatively bounded by a simplex which has only a few parameters. These few parameters define the effective bandwidth which are used in real time admission control.

0033The inventive method may also be applied to combinations of statistically multiplexable (SMUX) and non-statistically multiplexable (NSMUX) sources. Let <i>K</i>₁, represent a number of sources in a single SMUX class and <i>K</i>₂ represent a number of sources in an NSMUX class. FIG. 5 illustrates how many sources of each class may be routed through a particular node/link. Note that line 510 illustrates the lossless case, where values of <i>K</i>₁ and <i>K</i>₂ must be selected such that the values define a coordinate that lies below line 510 thus ensuring lossless performance. Alternatively, line 520 is the line for lossy performance where the probability of loss is 10^-9. Note that this curve is advantageously treated as piece-wise linear with a break point <i>B</i> (the coordinates for <i>B</i> are given in equations 63<i>i</i> and 63 <i>ii</i> below). In order to determine an effective bandwidth for the lossy performance case, line 530, representing a linear approximation to line 520, can be is drawn. The linear approximation will intersect the <i>K</i>₁ axis at point <i>K</i><maths id="math0009"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext>'</mtext></mrow><mrow><mtext>1</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0009.tif" /></maths> and will intersect the <i>K</i>₂ axis at the point <i>K</i><maths id="math0010"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext>'</mtext></mrow><mrow><mtext>2</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0010.tif" /></maths>. The effective bandwidth for SMUX sources in class 1, is then<maths id="math0011"><math display="block"><mrow><mfrac><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><msubsup><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext>1</mtext></mrow><mrow><mtext>'</mtext></mrow></msubsup></mrow></mfrac><mtext> ,</mtext></mrow></math><img file="EP0756403A2_D0011.tif" /></maths> and the effective bandwidth for NSMUX sources in class 2 is then<maths id="math0012"><math display="block"><mrow><mfrac><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><msubsup><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext>2</mtext></mrow><mrow><mtext>'</mtext></mrow></msubsup></mrow></mfrac><mtext>.</mtext></mrow></math><img file="EP0756403A2_D0012.tif" /></maths> As in previous cases, the effective bandwidth can then be used for a basis for admission and routing decisions. For example, instead of linearly approximating piece-wise line 520, the end points of the curve, <i>i.e.</i> where line 520 intersects the <i>K</i>₁ and <i>K</i>₂ axis, can be used as <i>K</i><maths id="math0013"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext>'</mtext></mrow><mrow><mtext>1</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0013.tif" /></maths> and <i>K</i><maths id="math0014"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext>'</mtext></mrow><mrow><mtext>2</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0014.tif" /></maths>for purposes of determining effective bandwidth. Note that alternatively <i>K</i><maths id="math0015"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext>'</mtext></mrow><mrow><mtext>1</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0015.tif" /></maths> and <i>K</i><maths id="math0016"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext>'</mtext></mrow><mrow><mtext>2</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0016.tif" /></maths> may be selected to provide a conservative determination of the effective BW.

0034In the case where information from VBR and CBR (constant bit rate) communication devices input information into a network, it is demonstrated below that the admission of CRB sources modifies the effective bandwidth of VBR sources. FIG. 6 illustrates the admissible region in the multiplexing of a single VBR source class in the presence of CBR traffic. The portion of line 610 to the left of break point 615 is the region in which VBR sources of class 1 are nonstatistically multiplexable. To the right of break point 615 the VBR sources in the class are statistically multiplexable. Line 610 in Fig. 6 also demonstrates that if operating in the statistically multiplexable region, the effective bandwidth of the VBR sources in class 1 are <maths id="math0017"><math display="inline"><mrow><mfrac><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext>1,</mtext><mtext mathvariant="italic">max</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP0756403A2_D0017.tif" /></maths> as in the case above. However, operation in the nonstatistically multiplexable region requires an allocated bandwidth of <i>e</i>_<i>o</i> as found in equation 1. The exact location of break point 615 depends on the access regulator parameters. Thus, since break point 615 defines the boundary between SMUX and NSMUX operation with their respective allocated bandwidths, the admission of CBR sources modifies the effective bandwidth of VBR sources.

0035Use of the inventive method in each of the above situations is considered in greater detail in the sections below.

<u>II. Lossless Multiplexing</u>

0036To increase network capacity, some networks, including BISDN networks using ATM, allow multiplexing of sources on common links. It is further possible to perform statistical multiplexing of VBR sources where a gain in efficiency <i>(e.g.</i> even higher network capacity) is achieved by overallocating link capacity <i>(e.g.</i> by admitting a number of VBR sources the sum of whose peak bit rates is greater than the link capacity) at the risk of congestion in the network and consequential cell loss when too many sources transmit at the same time. The objective of admission control here is to allow such efficiency gains while guaranteeing that quality-of-service commitments are respected for admitted virtual circuits. <i>See,</i> S. E. Minzer, "Broadband ISDN and Asynchronous Transfer Mode," <i>IEEE Comm. Mag.,</i> pp. 17-24, Sept. 1989.

0037In this section the inventive method is used to determine an effective buffer requirement <i>b</i>₀ and an effective bandwidth (capacity) <i>e</i>₀ in a node/link in a network to a request for a VC as function of access regulator parameters where the quality of service requirement is lossless performance. Admission is denied if uncommitted resources at the nodes are inadequate to satisfy the allocation. Further, the set of admissible combinations of classes of VCs is characterized, where each VC class is associated with a particular set of parameters for the access regulator. Consider a network, such as the one in FIG. 1 in which all traffic offered by device 105<i>-j</i> to a node is regulated at the network edge. The regulation is illustrated by leaky bucket devices with parameters <i>(r,B</i>_<i>T,</i><i>P</i>); an ancillary burst-size parameter <i>Q</i>, indicative of the amount of information generated while a device is on and transmitting, is Q = <i>B</i>_<i>T</i><i></i><maths id="math0018"><math display="inline"><mrow><mfrac><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">P-r</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0018.tif" /></maths><i>.</i> Assume that the departure process from such a regulator is extremal, on-off and periodic with indeterminate phases which has been suggested as the worst-case in the sense of maximizing the steady-state loss probability in the node.

0038Denote by <i>Ω</i>(<i>t</i>) the rate process which is the output of the regulator, see FIG. 7. In the figure<maths id="math0019" num="(8)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">T</mtext></mrow><mrow><mtext mathvariant="italic">on</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext mathvariant="italic">T</mtext></mrow></msub></mrow><mrow><mtext mathvariant="italic">P</mtext><mtext> - </mtext><mtext mathvariant="italic">r</mtext></mrow></mfrac><mtext> , and </mtext><msub><mrow><mtext mathvariant="italic">T</mtext></mrow><mrow><mtext mathvariant="italic">off</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>T</mtext></mrow></msub></mrow><mrow><mtext mathvariant="italic">r</mtext></mrow></mfrac><mtext> .</mtext></mrow></math><img file="EP0756403A2_D0019.tif" /></maths> Let the period be denoted by <i>T</i> = <i>T</i>_<i>on</i> + <i>T</i>_<i>off</i><i> = Q/r.</i> Also, the source activity factor,<maths id="math0020" num="(9)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>Ω</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">Pr</mtext><mfenced open="(" close=")"><mrow><mtext>Ω > 0</mtext></mrow></mfenced><mtext> = </mtext><mfrac><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><mtext mathvariant="italic">P</mtext></mrow></mfrac><mtext> .</mtext></mrow></math><img file="EP0756403A2_D0020.tif" /></maths>

0039Consider the base case where the quality of service requirement is lossless performance. Each virtual circuit is allocated or has effective bandwidth <i>e</i>₀ and effective buffer requirement <i>b</i>₀ and admission is denied if uncommitted resources at the node are inadequate to satisfy the allocations. A key feature is the heterogeneity of the virtual circuits and hence the goal is to characterize the set of admissible combinations of virtual circuits with various associated regulator parameters.

0040Consider a single source in a framework which is termed its Virtual Buffer/Trunk System. A single source with periodic, on-off rate process <i>Ω</i>(<i>t</i>)<i>,</i> see FIG. 7, which supplies an infinite buffer with a trunk or link of bandwidth <i>c,</i> as shown in FIG. 8. Assume that c ≥ <i>r,</i> is the stability condition. Let <i>v(t)</i> and <i>u(t)</i> respectively denote the <i>buffer content</i> and the <i>utilized bandwidth</i> at time <i>t,</i> where the latter is an on-off process which takes values <i>c</i> and 0 depending on whether the buffer is not empty or empty, respectively. See FIG. 9.

0041The stability condition ensures that the buffer is emptied in every cycle of length <i>T</i>. Let <i>D</i>_<i>on</i> and <i>D</i>_<i>off</i> respectively denote the time in each cycle that the buffer and the trunk is utilized. Clearly, <i>D</i>_<i>on</i><i> + D</i>_<i>off</i><i> = T, and D</i>_<i>on</i> exceeds <i>T</i>_<i>on</i> by the time taken by the buffer to go from its state of maximum occupancy to empty. Let <i>b</i> denote the maximum buffer content, <i>sup </i>_<i>t>o</i><i> v</i>(<i>t</i>)<i>.</i> Then<maths id="math0021" num="(10)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">D</mtext></mrow><mrow><mtext mathvariant="italic">on</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">T</mtext></mrow><mrow><mtext mathvariant="italic">on</mtext></mrow></msub><mtext> + </mtext><mfrac><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><mtext mathvariant="italic">c</mtext></mrow></mfrac><mtext> , </mtext><msub><mrow><mtext mathvariant="italic">D</mtext></mrow><mrow><mtext mathvariant="italic">off</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">T</mtext></mrow><mrow><mtext mathvariant="italic">off</mtext></mrow></msub><mtext> - </mtext><mfrac><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><mtext mathvariant="italic">c</mtext></mrow></mfrac><mtext> .</mtext></mrow></math><img file="EP0756403A2_D0021.tif" /></maths> Hence <i>w</i>, fraction of time that the virtual buffer/trunk system is busy,<maths id="math0022" num="(11)"><math display="block"><mrow><mtext mathvariant="italic">w</mtext><mtext> = </mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">D</mtext></mrow><mrow><mtext mathvariant="italic">on</mtext></mrow></msub></mrow><mrow><msub><mrow><mtext mathvariant="italic">D</mtext></mrow><mrow><mtext mathvariant="italic">on</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">D</mtext></mrow><mrow><mtext mathvariant="italic">off</mtext></mrow></msub></mrow></mfrac><mtext> = </mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">T</mtext></mrow><mrow><mtext mathvariant="italic">on</mtext></mrow></msub></mrow><mrow><msub><mrow><mtext mathvariant="italic">T</mtext></mrow><mrow><mtext mathvariant="italic">on</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">T</mtext></mrow><mrow><mtext mathvariant="italic">off</mtext></mrow></msub></mrow></mfrac><mtext> + </mtext><mfrac><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><mtext mathvariant="italic">c</mtext></mrow></mfrac><mtext> . </mtext><mfrac><mrow><mtext mathvariant="italic">1</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">T</mtext></mrow><mrow><mtext mathvariant="italic">on</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">T</mtext></mrow><mrow><mtext mathvariant="italic">off</mtext></mrow></msub></mrow></mfrac><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>Ω</mtext></mrow></msub><mtext> + </mtext><mfrac><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><mtext mathvariant="italic">c</mtext></mrow></mfrac><mtext>.</mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><mtext mathvariant="italic">T</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0022.tif" /></maths> Importantly, <i>w</i> ≥ <i>w</i>_Ω. Also,<maths id="math0023" num="(12)"><math display="block"><mrow><mtext mathvariant="italic">b</mtext><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext mathvariant="italic">T</mtext></mrow></msub><mtext> - </mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext>T</mtext></mrow></msub><mfenced open="(" close=")"><mrow><mtext mathvariant="italic">c</mtext><mtext> - </mtext><mtext mathvariant="italic">r</mtext></mrow></mfenced></mrow><mrow><mtext mathvariant="italic">P</mtext><mtext> - r</mtext></mrow></mfrac><mtext> .</mtext></mrow></math><img file="EP0756403A2_D0023.tif" /></maths> Hence <i>b</i> ≤ <i>B</i>_<i>T</i><i>.</i> Note that <i>b</i> decreases linearly with increasing <i>c</i> for <i>r</i> ≤ <i>c</i> ≤ <i>P</i>, and that the extreme points of (<i>b,c</i>) are (<i>B</i>_<i>T</i><i>,r</i>) and (0,<i>P</i>).

0042Now the behavior of the processes of the virtual buffer/trunk system for single sources can be used to design admission control for heterogeneous sources sharing the nodal resources.

0043First, suppose there is a set of <i>I</i> virtual circuits such that the traffic source for circuit <i>i</i> (1 ≤ <i>i</i> ≤ <i>I),</i> is an on-off process Ω_<i>i</i>(<i>t</i>). The aggregate traffic Σ<maths id="math0024"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext mathvariant="italic">l</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext><mtext>=1</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0024.tif" /></maths><i>Ω</i>_<i>i</i>(<i>t</i>)<i>,</i> will be associated with buffer content <i>V(t)</i> and a utilized bandwidth <i>U</i>(<i>t</i>)<i>,</i> where the latter is an on-off process which takes values <i>C</i> and 0.

0044Consider assigning each virtual circuit a virtual buffer/trunk. Circuit <i>i</i> would be allocated bandwidth <i>c</i>_<i>i</i> (<i>r</i> ≤ <i>c</i>_<i>i</i> ≤ <i>P</i>), and also buffer <i>b</i>_<i>i</i><i>,</i> the peak buffer occupancy given in (12). Then, if<maths id="math0025"><img file="EP0756403A2_D0025.tif" /></maths> it follows that<maths id="math0026"><img file="EP0756403A2_D0026.tif" /></maths> and<maths id="math0027"><img file="EP0756403A2_D0027.tif" /></maths> Thus, the sum of the virtual buffer usages bounds the aggregate buffer usage. The sum of the virtual buffer usages, Σ<maths id="math0028"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext mathvariant="italic">I</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext><mtext>=1</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0028.tif" /></maths><i>v</i>_<i>i</i> (<i>t</i>)<i>,</i> shall conservatively be used as an estimate of the aggregate buffer usage <i>V(t).</i> Equation 15 implies that if the estimate does not exceed the available buffer <i>B,</i> then neither will the actual buffer usage.

0045In the case where all sources are identical except for phase, then<maths id="math0029"><img file="EP0756403A2_D0029.tif" /></maths> Thus, in this case the estimate accurately predicts the maximum buffer usage, and hence the boundary between lossless and lossy transmission. The estimate will be less precise when dissimilar sources are involved, or when small losses are allowed.

0046The main concern now is the selection of the parameters <i>c</i>_<i>i</i><i>,</i> which are free at this point. If all the sources are known and are heterogeneous, then determining the values <i>c</i>_<i>i</i> which produce the lowest estimated peak buffer usage without exceeding the total bandwidth constraint (13) involves a complicated optimization. A simplification results if the <i>c</i>_<i>i</i> for a particular source must be chosen independent of any knowledge of the character of other sources. Straightforward optimal resource management requires that the per-circuit allocations (<i>b</i>_<i>i</i><i>,c</i>_<i>i</i>) be such that both network resources will always be exhausted at the same time for any aggregation of circuits using the same allocation rule. This occurs when<maths id="math0030" num="(17)"><math display="block"><mrow><mfrac><mrow><msub><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub></mrow><mrow><mtext mathvariant="italic">B</mtext></mrow></mfrac><mtext></mtext><mtext mathvariant="italic">=</mtext><mtext></mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">c</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub></mrow><mrow><mtext mathvariant="italic">C</mtext></mrow></mfrac><mtext></mtext><mtext mathvariant="italic">,</mtext></mrow></math><img file="EP0756403A2_D0030.tif" /></maths><i>i.e.,</i> when the allocations are in proportion to their respective nodal capacities. Although cases will sometimes be considered where all sources are taken to be known, (17) will continue to be abided by because of the simplification it provides. Using (17) in lieu of doing a calculation invoking simultaneous knowledge of all circuits leads to admission decisions which are exact if all sources are identical, but conservative if sources are heterogeneous.

0047Observe that for given <i>B</i> and <i>C,</i> (12) and (17) determine a unique allocation denoted by (<i>b</i>₀,<i>e</i>₀). The solution is depicted in FIG. 10. The quantity <i>e</i>₀, which is of importance, is referred to as the "effective bandwidth for lossless performance". The justification for the term stems from the fact that if <i>e</i>_0,_<i>i</i> is the effective bandwidth of the <i>i</i>^<i>th</i> virtual circuit, then the set of circuits {1,2,...,<i>I</i>} is admissible if<maths id="math0031"><img file="EP0756403A2_D0031.tif" /></maths> The admissible set may equivalently be given by Σ<maths id="math0032"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext mathvariant="italic">I</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext><mtext>=1</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0032.tif" /></maths><i>b</i>_0,_<i>i</i> ≤ <i>B,</i> where <i>b</i>₀_<i>,i</i> is the "effective buffer requirement" for virtual circuit <i>i</i>; however, the former description will be used.

0048Exceptions to the above procedure arise if there is no intersection of the straight lines in FIG. 10. An intersection at (<i>b</i>₀<i>,e</i>₀) exists if and only if<maths id="math0033" num="(19b)"><math display="block"><mrow><mfrac><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">B</mtext></mrow></mfrac><mtext>> </mtext><mfrac><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext mathvariant="italic">T</mtext></mrow></msub></mrow></mfrac><mtext> .</mtext></mrow></math><img file="EP0756403A2_D0033.tif" /></maths> Sources which violate (19a) are "bandwidth-limited" and in such cases a natural choice for the allocated bandwidth is<maths id="math0034" num="(20)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">r</mtext><mtext> .</mtext></mrow></math><img file="EP0756403A2_D0034.tif" /></maths> There are the following options available in the corresponding buffer allocations: (i) <i>b</i>₀<i>= rB/C,</i> or (ii) <i>b</i>₀ = <i>B</i>_<i>T</i><i>.</i> The former allocation, which in effect inflates <i>B</i>_<i>T</i> to <i>rB/C</i> and is therefore more liberal, has the advantage that the administration of admission control and resource allocation is routine, <i>i.e.,</i> as if (19a) holds. This option is recommended if the margin of violation of (19) is small, which is more typical. On the other hand, if the margin is large and the second option is followed then it is necessary to go to the extreme length of recalculating the residual <i>B</i> and <i>C</i> available to the non-bandwidth-limited sources whenever such a bandwidth-limited virtual circuit is admitted to the network. This procedure has large consequences and is identical to one that developed for the important case of CBR traffic, which constitutes the limiting case of bandwidth-limited sources.

0049Formulas for <i>e</i>₀ and <i>w</i>, which will be useful later are:<maths id="math0035"><img file="EP0756403A2_D0035.tif" /></maths><maths id="math0036" num="(22)"><math display="block"><mrow><mtext mathvariant="italic">w</mtext><mtext> = </mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>Ω</mtext></mrow></msub><mtext mathvariant="italic">P</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow></mfrac><mtext> = </mtext><mfrac><mrow><mtext mathvariant="italic">r</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP0756403A2_D0036.tif" /></maths> Note that in the above expressions <i>e</i>₀ and <i>w</i> depend on the nodal buffer <i>B</i> and bandwidth <i>C</i> only through <i>B/C.</i> This important fact should not be surprising since the ratio of buffer and bandwidth allocated to individual sources is equal to the ratio of the buffer and bandwidth at the node.

0050The formula for <i>e</i>₀ perhaps is most easily remembered when expressed in terms of different variables:<maths id="math0037"><img file="EP0756403A2_D0037.tif" /></maths> where<maths id="math0038" num="(24)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">T</mtext></mrow><mrow><mtext mathvariant="italic">buf</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext mathvariant="italic">C</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0038.tif" /></maths> is the maximum delay time of the buffer.

<u>III. Statistical Multiplexing</u>

0051In this section additional advantages of the inventive method are realized by extracting statistical multiplexing gains both from 1) the assumption of statistical independence of communication devices, and 2) the exploitation of the unutilized time varying portions of the allocated resources to VCs while allowing for small probabilities of loss of information (<i>i.e.</i> the lossy statistical multiplexing situation). Importantly, the notion that the per-circuit allocations are such that both bandwidth and buffer network resources are exhausted at the same time, as in the previous section, is used in the lossy statistical multiplexing situation to reduce the problem of bandwidth and buffer allocation to a single resource allocation problem.

0052An overview of the method is as follows - VCs are advantageously grouped by classes. Let J denote the number of classes, where each class <i>j,j=</i> 1,2,...<i>J,</i> is associated with a particular set of access regulator parameters, and let <i>K</i>_<i>j</i> denote the number of VCs of class <i>j</i>. To determine the effective bandwidth a VC in the <i>j</i>^<i>th</i> class should be allocated at a node of capacity <i>C (i.e.</i> to determine <i>e</i><maths id="math0039"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0039.tif" /></maths> the effective bandwidth for that class), the multiclass problem is broken down into a series of single class problems. For a given acceptable information loss rate, <i>P</i>_<i>L</i><i>,</i> the maximum number of VCs of any one particular class, <i>K</i>_<i>max,j</i>, is determined using the expressions below. Then, the effective bandwidth for the <i>j</i>^<i>th</i> class is found according to: <i>e</i><maths id="math0040"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0040.tif" /></maths> = <i>C/K</i>_<i>max,j</i>. The set of values for <i>K</i>_<i>max,j</i><i> form</i> the boundary of the set of admissible VCs through the node. For each class <i>j</i>, the parameters <i>e</i>₀,_<i>j</i> and <i>b</i>_0,_<i>j</i> can be determined, as described in the previous section, and the gain <i>g</i> due to statistical multiplexing can then be defined as: <i>g</i>_<i>j</i> = <i>e</i>_0,_<i>j</i>/<i>e</i><maths id="math0041"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0041.tif" /></maths> (<i>j=</i>1,2<i>,...,J</i>).

0053Begin with the characterization of the <i>i</i>^<i>th</i> virtual circuit of class <i>j</i> by two stationary random processes <i>u</i>_<i>ji</i> (<i>t</i>) and <i>v</i>_<i>ji</i> (<i>t</i>), which respectively denote the utilized bandwidth and buffer content for the circuit's virtual buffer/trunk system. As shown in FIG. 9, these two processes are synchronized in their on-off behavior. To make their correspondence closer for ease of analysis, the process <i>v</i>_<i>ji</i>(<i>t</i>) shall be conservatively bounded shall be conservatively bounded by an on-off process, which takes the peak value for the on period. Thus <i>u</i>_<i>ji</i>(<i>t</i>) and <i>v</i>_<i>ji</i>(<i>t</i>) are viewed as two synchronized on-off processes, which respectively take values <i>e</i>_0, and <i>b</i>_<i>0,j</i> while on and 0 while off. The parameters <i>e</i>_0,_<i>j</i> and <i>b</i>₀_<i>,j</i> are calculated by the procedure in the preceding section. With this formalism in place, only one of either <i>u</i>_<i>ji</i>(<i>t</i>) or <i>v</i>_<i>ji</i>(<i>t</i>) needs to be considered, and the former is chosen.

0054On account of the assumed statistical independence of traffic sources, the processes <i>u</i>_<i>ji</i>(<i>t</i>) <i>(i</i> = 1,2,...,<i>K</i>_<i>j</i>) of the same source class have identical templates and differ only in their phase, i.e.,<maths id="math0042" num="(25)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext mathvariant="italic">ji</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">t</mtext><mtext>) = </mtext><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">t</mtext><msub><mrow><mtext> + θ</mtext></mrow><mrow><mtext mathvariant="italic">ji</mtext></mrow></msub><mtext mathvariant="italic">)</mtext><mtext> ,</mtext></mrow></math><img file="EP0756403A2_D0042.tif" /></maths> where <i>u</i>_<i>j</i>(<i>t</i>) is a deterministic, periodic on-off function with period <i>T</i>_<i>j</i><i>,</i> which takes values <i>e</i>₀_<i>,j</i> and 0 for fractions <i>w</i>_<i>j</i> and (1 - <i>w</i>_<i>j</i>), respectively; the phases θ_<i>ji</i> are independent random variables uniformly distributed in the interval <i>T</i>_<i>j</i><i>.</i>

0055The performance measure is the loss probability <i>P</i>_<i>loss</i>,<maths id="math0043" num="(26)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">loss</mtext></mrow></msub><mtext mathvariant="italic"> = Pr(U > C)</mtext><mtext> ,</mtext></mrow></math><img file="EP0756403A2_D0043.tif" /></maths> where the total instantaneous load <i>U</i> = Σ<maths id="math0044"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext mathvariant="italic">j</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext><mtext>=1</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0044.tif" /></maths> Σ<maths id="math0045"><math display="inline"><mrow><mfrac linethickness="0"><mrow><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub></mrow><mrow><mtext mathvariant="italic">i</mtext><mtext>=1</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0045.tif" /></maths><i>u</i>_<i>ji</i>. Hence <i>P</i>_<i>loss</i> is the fraction of time that the aggregated demand for bandwidth from all sources exceeds the nodal bandwidth. From the earlier discussions, time periods during which losses occur at the network node due to a full buffer are contained in periods during which <i>U</i>(<i>t</i>) > <i>C.</i> Take for our quality of service requirement,<maths id="math0046" num="(27)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">loss</mtext></mrow></msub><mtext> ≤ </mtext><mtext mathvariant="italic">L</mtext><mtext> ,</mtext></mrow></math><img file="EP0756403A2_D0046.tif" /></maths> where <i>L</i> is a small number, such as 10^-9.

0056The primary means for estimating <i>P</i>_<i>loss</i> is the Chernoff bound, which is reviewed here, and a refined large deviations approximation based on it, which is described below. The instantaneous loads <i>u</i>_<i>ji</i> are independent, nonnegative random variables with moment generating functions<maths id="math0047"><img file="EP0756403A2_D0047.tif" /></maths> where<maths id="math0048" num="(29)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">x</mtext><mtext>) = </mtext><mtext mathvariant="italic">Pr</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext mathvariant="italic">ji</mtext></mrow></msub><mtext> ≤ </mtext><mtext mathvariant="italic">x</mtext><mtext>) .</mtext></mrow></math><img file="EP0756403A2_D0048.tif" /></maths> Chernoff's bound gives,<maths id="math0049" num="(30)"><math display="block"><mrow><mtext>log </mtext><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">loss</mtext></mrow></msub><mtext> ≤ - </mtext><msub><mrow><mtext mathvariant="italic">F</mtext></mrow><mrow><mtext>K</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">s</mtext><mtext>*) ,</mtext></mrow></math><img file="EP0756403A2_D0049.tif" /></maths> where<maths id="math0050"><img file="EP0756403A2_D0050.tif" /></maths> and <i>F</i>_<b>K</b><i>(s</i>*) = <i>sup</i>_s_<i>≥</i>₀<i>F</i>_<b>K</b>(<i>s</i>)<i>.</i>

0057If <i>C</i>→∞ and <i>K</i>_<i>j</i><i>/C</i> = <i>O</i>(1)<i>,</i> then<maths id="math0051"><img file="EP0756403A2_D0051.tif" /></maths> Hence the asymptotic large deviations approximation is <i>P</i>_<i>loss</i> ∼ <i>exp</i>(<i>- F</i>_<b>K</b>(<i>s</i>*)).

0058To avoid trivialities assume the stability condition,<maths id="math0052"><img file="EP0756403A2_D0052.tif" /></maths> (the prime denotes derivative) since without the latter condition there is no loss. Also note that<maths id="math0053"><img file="EP0756403A2_D0053.tif" /></maths> It is easy to verify that <i>F</i>_<b>K</b>(<i>s</i>) is a strictly concave function with a unique maximum at <i>s</i> = <i>s</i>^*, which is the positive root of the equation <i>F'</i>_<b>K</b> (<i>s</i>) <i>=</i> 0.

0059Of particular interest here is the case of binomially distributed <i>u</i>_<i>ji</i>, where <i>w</i>_<i>j</i> = <i>Pr(u</i>_<i>ji</i> = <i>e</i>₀_<i>,j</i><i>)</i> and 1 - <i>w</i>_<i>j</i> = <i>Pr</i>(<i>u</i>_<i>ji</i> = 0). Then<maths id="math0054"><img file="EP0756403A2_D0054.tif" /></maths> and s is obtained by solving the equation<maths id="math0055"><img file="EP0756403A2_D0055.tif" /></maths> In the single-class case, i.e. <i>J</i> = 1, the resulting expressions are illuminating: for a = (<i>C/e</i>₀)<i>/K,</i><maths id="math0056"><img file="EP0756403A2_D0056.tif" /></maths><maths id="math0057"><img file="EP0756403A2_D0057.tif" /></maths>

0060The above expression may be used to obtain <i>K</i>_max, which is the value of <i>K</i> for which<maths id="math0058" num="(39)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">F</mtext></mrow><mrow><mtext mathvariant="italic">K</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">s</mtext><mtext>*) = log(1/</mtext><mtext mathvariant="italic">L</mtext><mtext>)</mtext></mrow></math><img file="EP0756403A2_D0058.tif" /></maths> In light of (27) and (30), the quality of service requirement on <i>P</i>_<i>loss</i> is satisfied for all <i>K ≤ K</i>_max. Similarly, in the case of multiple classes, of interest is the admissible set<maths id="math0059" num="(40)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext mathvariant="italic">L</mtext></mrow></msub><mtext mathvariant="italic">(B,C) = {</mtext><mtext>K : </mtext><msub><mrow><mtext mathvariant="italic">F</mtext></mrow><mrow><mtext>K</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">s*</mtext><mtext>) ≥ </mtext><mtext mathvariant="italic">log</mtext><mtext>(1/</mtext><mtext mathvariant="italic">L</mtext><mtext>)</mtext><mtext mathvariant="italic">}</mtext></mrow></math><img file="EP0756403A2_D0059.tif" /></maths> Since the complement of the admissible set is convex, the points on the boundary, which are denoted by ∂<i>A</i>_<i>L</i>, also satisfy (39) with <i>K replaced</i> by <i>J</i>-tuples (K₁,..., <i>K</i>_<i>J</i>)<i>.</i>

0061For a wide variety of conditions the boundary ∂<i>A</i>_<i>L</i> is closely approximated by an appropriately chosen linear hyperplane. (There are notable exceptions, however, even in these cases the boundary is approximately piece-wise linear and hence the following comments apply with obvious modification.) For instance, and a point <img file="EP0756403A2_D0060.tif" /> on ∂A_<i>L</i> may be picked and the tangent hyperplane to ∂<i>A</i>_<i>L</i> which touches ∂<i>A</i>_<i>L</i> at <img file="EP0756403A2_D0061.tif" /> may be obtained. Let the region constrained by this hyperplane by denoted by <img file="EP0756403A2_D0062.tif" />. Clearly, from the aforementioned concavity of <i>A</i>_<i>L</i><i>,</i><img file="EP0756403A2_D0063.tif" /> is a conservative bound to <i>A</i>_<i>L</i><i>.</i> Moreover, denoting<maths id="math0060"><img file="EP0756403A2_D0064.tif" /></maths> the parameters <i>e</i>_<i>j</i> which define <img file="EP0756403A2_D0065.tif" /> are readily obtained:<maths id="math0061"><img file="EP0756403A2_D0066.tif" /></maths> where <img file="EP0756403A2_D0067.tif" />* is where <img file="EP0756403A2_D0068.tif" /> (<i>s</i>) is maximized.

0062The quantity <i>e</i>_<i>j</i> may justifiably be called the effective bandwidth of class <i>j</i> traffic sources. The statistical multiplexing gain g compares this quantity to <i>e</i>_0,_<i>j</i>, which is the effective bandwidth for lossless performance,<maths id="math0062" num="(43)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">g</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0,</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">/e</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>  (</mtext><mtext mathvariant="italic">j</mtext><mtext> = 1,2, ..., </mtext><mtext mathvariant="italic">J</mtext><mtext>) .</mtext></mrow></math><img file="EP0756403A2_D0069.tif" /></maths>

0063In numerical investigations the end results have been found to be fairly insensitive to reasonable choices of <img file="EP0756403A2_D0070.tif" />. One selection which works well is<img file="EP0756403A2_D0071.tif" /> = <i>K</i>_<i>max</i>_,_<i>j</i>/2, where <i>K</i>_<i>max</i>_,_<i>j</i> is the maximum number of admissible sources when only class <i>j</i> sources are admitted.

0064An optimistic (upper) bound of <i>A</i>_<i>L</i><i>,</i> which follows from the aforementioned concavity of the admissible region is<maths id="math0063"><img file="EP0756403A2_D0072.tif" /></maths> where <i>e</i><maths id="math0064"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0073.tif" /></maths> = <i>C/K</i>_<i>max,j</i><i>.</i> These optimistic estimates of the effective bandwidths are considerably easier to calculate, since they are obtained by considering each source class in isolation, and in many cases are quite close to the conservative estimates in (42). Such is the case when ∂<i>A</i>_<i>L</i> is close to being linear.

0065In numerical investigations a refinement is used to the large deviations approximation (32) and bound (30). For the asymptotic scaling in which <i>K</i>_<i>j</i><i>/C</i> = <i>O</i>(1) and <i>C → ∞,</i> the refined approximation is<maths id="math0065"><img file="EP0756403A2_D0074.tif" /></maths> where <i>s</i> * is obtained by solving <i>F</i>'_<b>K</b> (<i>s</i>) <i>=</i> 0, i.e., exactly as before, and σ² (<i>s</i>) <i>=</i><maths id="math0066"><math display="inline"><mrow><mfrac><mrow><msup><mrow><mtext>∂</mtext></mrow><mrow><mtext>2</mtext></mrow></msup></mrow><mrow><msup><mrow><mtext>∂s</mtext></mrow><mrow><mtext>2</mtext></mrow></msup></mrow></mfrac></mrow></math><img file="EP0756403A2_D0075.tif" /></maths> log <i>E</i>[<i>e</i>^<i>sU</i>], where <i>U</i> is the total instantaneous load, see (26). More specifically,<maths id="math0067"><img file="EP0756403A2_D0076.tif" /></maths> In the particular case of binomially distributed random variables <i>u</i>_<i>ji</i><i>,</i> the quantities in the above expression have appeared before, except for <i>M</i><maths id="math0068"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext>''</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0077.tif" /></maths> which is given by <i>w</i>_<i>j</i><i>e</i><maths id="math0069"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext>2</mtext></mrow><mrow><mtext>0,</mtext><mtext mathvariant="italic">j</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0078.tif" /></maths><i>exp</i>(<i>se</i>_0,<i>j</i>).

0066The dominant exponential (in <i>C</i>) term is common to both the base and refined large deviations approximations. Hence, the fundamental qualitative properties are not affected. It is more convenient to conduct a qualitative investigation in terms of the simpler base approximation. In quantitative terms a rough rule of thumb is that the refinement adds about 10% to the calculated nodal capacity.

0067A qualitative theory may be developed based on the above results. The existence of solutions <b>K</b> to the equation given earlier for determining the boundary ∂<i>A</i>_<i>L</i> of the admissible set, namely,<maths id="math0070" num="(47)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">F</mtext></mrow><mrow><mtext>K</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">s*</mtext><mtext>) = </mtext><mtext mathvariant="italic">log</mtext><mtext>(1</mtext><mtext mathvariant="italic">/L)</mtext></mrow></math><img file="EP0756403A2_D0079.tif" /></maths> are examined in detail. A topic addressed here is whether the admissible set <i>A</i>₀ for lossless performance is a proper subset <i>of A</i>_<i>L</i><i>,</i> i.e., whether statistical multiplexing gains exist. Conditions under which the sets <i>A</i>₀ and <i>A</i>_L coincide either completely or partially are also determined. When only a single source class exists these results illuminate conditions under which the statistical multiplexing gain, <i>g</i> = <i>e</i>₀/<i>e</i> either exceeds or equals unity. It is shown that there exist critical values <i>C</i>_<i>c</i>, such that if <i>C</i> ≤ <i>C</i>_<i>c</i> then <i>g</i> = 1 and if <i>C</i> ≤ <i>C</i>_<i>c</i> then <i>g</i> ≥ 1. Similar critical values <i>r</i>_<i>c</i> exist for the token rate. Simple expressions for <i>C</i>_<i>c</i> and <i>r</i>_<i>c</i> are obtained. For given nodal bandwidth <i>C</i>, statistically-multiplexable and non-statistically-multiplexable VBR source classes are obtained. In the context of multiple source classes results on the constitution of the boundary of the admissible set are obtained. The results here help to explain the observations from numerical investigations, which are reported in the next section, on the almost-linearity of the boundary of the admissible in the presence of only S-VBR sources, and the qualitatively different boundary, with piece-wise linear segments, which is obtained when both S-VBR and NS-VBR sources are present.

0068From (38),<maths id="math0071"><img file="EP0756403A2_D0080.tif" /></maths> where <i>a</i> = <i>C</i>/(<i>Ke</i>₀). From the stability condition (33), <i>w</i> &lt; <i>a</i>. Hence ∂<i>F</i>_<i>K</i>(<i>s</i>*)/∂<i>K &lt;</i> 0. Also, for <i>K</i> = <i>C/e</i>₀ + 0,<i>∂F</i>_<i>k</i>(<i>s*</i>)<i>/∂K = -∞,</i> and, importantly,<maths id="math0072" num="(49)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">F</mtext></mrow><mrow><mtext mathvariant="italic">K</mtext></mrow></msub><mfenced open="(" close=")"><mrow><mtext mathvariant="italic">s</mtext><mtext>*</mtext></mrow></mfenced><mtext> = </mtext><mfrac><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow></mfrac><mtext mathvariant="italic">log</mtext><mfenced open="(" close=")"><mrow><mtext>1/</mtext><mtext mathvariant="italic">w</mtext></mrow></mfenced><mtext> .</mtext></mrow></math><img file="EP0756403A2_D0081.tif" /></maths> From the expression for <i>s</i>* in (37),<maths id="math0073"><img file="EP0756403A2_D0082.tif" /></maths> it follows that <i>s</i>^* → ∞ as <i>K → C/e</i>₀ + 0<i>,</i> and <i>s</i>* = 0 for <i>K</i> = <maths id="math0074"><math display="inline"><mrow><mfrac><mrow><mtext>1</mtext></mrow><mrow><mtext mathvariant="italic">w</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0083.tif" /></maths><maths id="math0075"><math display="inline"><mrow><mfrac><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP0756403A2_D0084.tif" /></maths> . The following summarizes the salient features of <i>F</i>_<i>K</i>(<i>s</i>*). <b>Proposition 1</b> With <i>C</i>, <i>w, e</i>₀ held fixed, and <i>K</i> in the interval<maths id="math0076"><img file="EP0756403A2_D0085.tif" /></maths><ul id="ul0001" list-style="none" compact="compact"><li>(<i>i</i>) <i>F</i>_<i>k</i>(<i>s</i>*) is monotonic, strictly decreasing with increasing <i>K.</i></li><li>(<i>ii</i>) For <i>K</i> = <i>C/e</i>₀ + 0, <i>s</i>* = ∞, <maths id="math0077"><math display="inline"><mrow><mfrac><mrow><mtext>∂</mtext></mrow><mrow><mtext>∂</mtext><mtext mathvariant="italic">K</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0086.tif" /></maths><i>F</i>_<i>K</i>(<i>s</i>*) = - ∞ and<maths id="math0078" num="■"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">F</mtext></mrow><mrow><mtext mathvariant="italic">K</mtext></mrow></msub><mfenced open="(" close=")"><mrow><mtext>s*</mtext></mrow></mfenced><mtext> = </mtext><mfrac><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow></mfrac><mtext mathvariant="italic">log</mtext><mfenced open="(" close=")"><mrow><mtext>1/</mtext><mtext mathvariant="italic">w</mtext></mrow></mfenced><mtext>.</mtext></mrow></math><img file="EP0756403A2_D0087.tif" /></maths></li></ul>

0069In particular, <maths id="math0079"><math display="inline"><mrow><mfrac><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP0756403A2_D0088.tif" /></maths><i>log</i>(1/<i>w</i>) is the maximum value of <i>F</i>_<i>K</i>(<i>s</i>*) and it is achieved at <i>K</i> = <i>C/e</i>₀.

0070Now consider the calculation of <i>K</i>_max, the largest value of <i>K</i> for which <i>P</i>_<i>loss</i> ≤ <i>L,</i> which is given by the solution <i>K</i> of <i>F</i>_<i>K</i>(<i>s</i>*) = <i>log</i>(1/<i>L</i>)<i>.</i> Observe the following dichotomy: if <i>log</i> (1/<i>L</i>) < <maths id="math0080"><math display="inline"><mrow><mfrac><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP0756403A2_D0089.tif" /></maths>(1/<i>w</i>)<i>,</i> the maximum value of <i>F</i>_<i>K</i>(<i>s</i>*), then <i>K</i>_max > <i>C/e</i>₀<i>.</i> Hence the statistical multiplexing gain <i>g</i> = <i>e</i>₀<i>/e</i> > 1, since <i>e = C/K</i>_max<i>.</i> If, on the other hand, log(1/<i>L</i>) ≥ <maths id="math0081"><math display="inline"><mrow><mfrac><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP0756403A2_D0090.tif" /></maths><i>log</i>(1/<i>w</i>) then no solution to (51) exists; however, it is known independently that for <i>K</i> = <i>C/e</i>₀<i>, P</i>_<i>loss</i> = 0 and hence <i>K</i>_max = <i>C/e</i>₀<i>.</i> In this case, <i>g</i> = 1. The above facts are now summarized.

0071<b>Definition:</b> The critical bandwidth <i>C</i>_<i>c</i> is the smallest quantity such that the statistical multiplexing gain exceeds unity for all <i>C > C</i>_<i>c</i><i>.</i>

0072Tacit to the above definition is the assumption that <i>B</i> varies with <i>C</i> in such a manner that <i>B/C is</i> held fixed.

Proposition 2

0073<maths id="math0082" num="(51) ■"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">c</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext mathvariant="italic">log</mtext><mfenced open="(" close=")"><mrow><mtext>1/</mtext><mtext mathvariant="italic">L</mtext></mrow></mfenced></mrow><mrow><mtext mathvariant="italic">log</mtext><mfenced open="(" close=")"><mrow><mtext>1/</mtext><mtext mathvariant="italic">w</mtext></mrow></mfenced></mrow></mfrac></mrow></math><img file="EP0756403A2_D0091.tif" /></maths>

0074Recall from (21) and (22) that an implication of our resource allocation procedure is that <i>e</i>₀ and <i>w</i> depend on the nodal resource capacities <i>B</i> and <i>C</i> only through <i>B/C.</i> Hence this is also true for <i>C</i>_<i>c</i>.

0075Conditions in (33) give<maths id="math0083"><img file="EP0756403A2_D0092.tif" /></maths> Also, for <i>C</i> ≥ Σ<i>K</i>_<i>j</i><i>e</i>₀_<i>,j</i> obviously <i>P</i>_<i>loss</i><i> =</i> 0. The main result is

Proposition 3

0076<ul id="ul0002" list-style="none" compact="compact"><li>(<i>i</i>) <i>F</i>_<b>K</b>(<i>s</i>*) has a maximum value <i>m</i>_<i>F</i><i>,</i> where<maths id="math0084"><img file="EP0756403A2_D0093.tif" /></maths></li><li>(<i>ii</i>) Say that the above maximum is reached at an unique <i>j</i>*. Then <i>F</i>_<b>K</b>(<i>s</i>*) reaches its maximum value at the following unique corner point <b>K</b>:<maths id="math0085"><img file="EP0756403A2_D0094.tif" /></maths></li><li><i>(iii)</i><maths id="math0086" num="(54)"><math display="block"><mrow><mtext mathvariant="italic">If log</mtext><mtext>(1/</mtext><msub><mrow><mtext mathvariant="italic">L) > m</mtext></mrow><mrow><mtext mathvariant="italic">F</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic"> then A</mtext></mrow><mrow><mtext mathvariant="italic">L</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic"> = A</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> .</mtext></mrow></math><img file="EP0756403A2_D0095.tif" /></maths><maths id="math0087"><img file="EP0756403A2_D0096.tif" /></maths> Otherwise <i>A</i>₀ ⊆<i>A</i>_<i>L,</i> i.e., the boundaries of <i>A</i>₀ and <i>A</i>_<i>L</i> coincide in part and elsewhere <i>A</i>_<i>L</i> subsumes <i>A</i>₀. Specifically, <b>K</b> on the boundary of <i>A</i>₀ such that Σ <i>K</i>_<i>j</i><i>log</i>(1/<i>w</i>_<i>j</i>) ≤ <i>log</i>(1/<i>L</i>) is also on the boundary of <i>A</i>_<i>L</i><i>,</i> and when the inequality is false <b>K</b> is contained in the proper interior <i>of A</i>_<i>L</i><i>.</i></li></ul>

0077<b>Proof:</b> Observe from (36) that as <i>s</i>* → ∞, Σ _<i>j</i><i> K</i>_<i>j</i><i>e</i>₀_<i>,j</i> → <i>C.</i> Hence, for Σ_<i>j</i><i> K</i>_<i>j</i><i>e</i>_0,_<i>j</i><i> = C,</i> from (35),<maths id="math0088"><img file="EP0756403A2_D0097.tif" /></maths>

0078Next,<maths id="math0089" num="(57)"><math display="block"><mrow><mfrac><mrow><mtext>∂</mtext></mrow><mrow><mtext>∂</mtext><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub></mrow></mfrac><msub><mrow><mtext mathvariant="italic">F</mtext></mrow><mrow><mtext>K</mtext></mrow></msub><mfenced open="(" close=")"><mrow><mtext mathvariant="italic">s</mtext><mtext>*</mtext></mrow></mfenced><mtext> = -</mtext><mtext mathvariant="italic">log</mtext><mfenced open="(" close=")"><mrow><mtext>1 - </mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub><mtext mathvariant="italic">e</mtext><msup><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">s</mtext><mtext>*</mtext><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0.</mtext><mtext mathvariant="italic">i</mtext></mrow></msub></mrow></msup></mrow></mfenced><mtext> &lt; 0.</mtext></mrow></math><img file="EP0756403A2_D0098.tif" /></maths> Similarly, by taking the derivative of both sides of (36) with <i>K</i>_<i>i</i><i>,</i> then<maths id="math0090" num="(58)"><math display="block"><mrow><mfrac><mrow><mtext>∂</mtext><mtext mathvariant="italic">s</mtext><mtext>*</mtext></mrow><mrow><mtext>∂</mtext><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow></msub></mrow></mfrac><mtext>&lt; 0 .</mtext></mrow></math><img file="EP0756403A2_D0099.tif" /></maths> At this point observe that various features of the analysis for the single class carry over naturally to the case of multiple classes, namely, on ∂<i>A</i>₀ = <i>{</i><b>K</b> : Σ <i>K</i>_<i>j</i><i>e</i>_0,_<i>j</i><i> = C}, s</i>* = ∞ and <i>F</i>_<b>K</b>(<i>s</i>*) = Σ <i>K</i>_<i>j</i>log (1/<i>w</i>_<i>j</i>), and as <b>K</b> increases in any direction away from ∂<i>A</i>₀, <i>s</i>* and <i>F</i>_<b>K</b>(<i>s</i>*) decrease.

0079Now consider the behavior of <i>F</i>_<b>K</b>(<i>s</i>*) = Σ <i>K</i>_<i>j</i><i> log</i> (1/<i>w</i>_<i>j</i>) on ∂<i>A</i>₀. Since this function is linear in <b>K</b>, its maximum on ∂<i>A</i>₀ is reached at its boundary, typically a corner point. At the <i>j</i>^<i>th</i> corner point, where <i>K</i>_<i>i</i> = <i>C/e</i>₀_<i>,j</i> if <i>i</i> = j and <i>K</i>_<i>i</i> = 0 otherwise, <i>F</i>_<b>K</b>(<i>s*</i>) <i>= (C/e</i>_0,_<i>j</i><i>) log</i>(1/<i>w</i>_<i>j</i>)<i>.</i> Hence the results in (i) and (ii) are found.

0080Next consider the multiple class version of the problem considered previously for the single class, namely, the existence of solutions <b>K</b> in (47). If <i>log</i>(1/<i>L) > m</i>_<i>F</i> then clearly no solution exists. In this case, as with a single class, the requirement <i>P</i>_<i>loss</i> < <i>L</i> can only be met by having <i>P</i>_<i>loss</i> = 0, i.e., by restricting <b>K</b> to <i>A</i>₀. Hence, in this case <i>A</i>_<i>L</i> = <i>A</i>₀. On the other and, if <i>F</i>_<i>K</i>(<i>s</i>*) > <i>log</i>(1/<i>L</i>) for all <b>K</b> on ∂<i>A</i>₀ then, from the aforementioned range and monotonicity of <i>F</i>_<b>K</b>(<i>s</i>*), solutions <b>K</b> to (47) exist in the complement of <i>A</i>₀. Hence <i>A</i>₀<i>⊂A</i>_<i>L</i><i>.</i> Finally, consider the mixed case where <i>F</i>_<b>K</b>(<i>s</i>*) < <i>log</i>(1/<i>L</i>) for some <b>K</b> on ∂<i>A</i>₀ and the inequality is reversed for other <b>K</b> on <i>∂A</i>₀<i>.</i> In this case any <b>K</b> on <i>∂A</i>₀ for which the inequality holds is such that (47) does not have a solution and hence such a K is also an element of ∂<i>A</i>_<i>L</i>. Hence, any <b>K</b> on ∂<i>A</i>₀ for which Σ <i>K</i>_<i>j</i><i>log</i>(1/<i>w</i>_<i>j</i>) <i>< log</i>(1/<i>L</i>) is also an element of ∂<i>A</i>_<i>L</i><i>.</i> Moreover, all other <b>K</b> on <i>∂A</i>₀ are contained in the proper interior of <i>A</i>_<i>L</i>.

0081This concludes the proof of Proposition 3.   ■

0082To illustrate the result for a two-class model consider three cases:<maths id="math0091" num="(59)"><math display="block"><mrow><mtext>(</mtext><mtext mathvariant="italic">i</mtext><mtext>)  </mtext><mtext mathvariant="italic">log</mtext><mtext>(1/</mtext><mtext mathvariant="italic">L</mtext><mtext>) </mtext><msub><mrow><mtext mathvariant="italic">> m</mtext></mrow><mrow><mtext mathvariant="italic">F</mtext></mrow></msub><mtext mathvariant="italic">, i.e., C < min</mtext><mtext> (</mtext><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">c,</mtext><mtext>1</mtext></mrow></msub><mtext>, </mtext><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">c,</mtext><mtext>2</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0756403A2_D0100.tif" /></maths><maths id="math0092"><img file="EP0756403A2_D0101.tif" /></maths><maths id="math0093" num="(61)"><math display="block"><mrow><mtext mathvariant="italic">(iii)</mtext><mtext>  </mtext><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">c,</mtext><mtext>1</mtext></mrow></msub><mtext> < </mtext><msub><mrow><mtext mathvariant="italic">C < C</mtext></mrow><mrow><mtext mathvariant="italic">c,</mtext><mtext>2</mtext></mrow></msub><mtext> ,</mtext></mrow></math><img file="EP0756403A2_D0102.tif" /></maths> where <i>C</i>_<i>c,j</i> is the critical bandwidth for class <i>j:</i><maths id="math0094" num="(62)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">c,j</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0,</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext mathvariant="italic">log</mtext><mtext>(1/</mtext><mtext mathvariant="italic">L</mtext><mtext>)/</mtext><mtext mathvariant="italic">log</mtext><mtext>(1/</mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext>), </mtext><mtext mathvariant="italic">j</mtext><mtext> = 1,2 .</mtext></mrow></math><img file="EP0756403A2_D0103.tif" /></maths>

0083According to Proposition (49), for case (i) <i>A</i>_<i>L</i> = <i>A</i>₀. This situation is sketched in FIG. 11(A), note that the admissible set is a simplex. The performance implication is that there is no statistical multiplexing gain in this case. For this reason both source types are NS-VBR, i.e., "bad" in the sense that the sources are too "large" with respect to the node bandwidth. For case (ii), the result states that <i>A</i>₀ is a proper subset of <i>A</i>_<i>L</i>, as sketched in FIG. 11(B), (ii). In this case the statistical multiplexing gain exists and both source types are S-VBR. The final case (iii) is sketched in FIG. 11(C), (iii). The boundary of the admissible set is <i>ABC,</i> in which the segment <i>AB</i> is linear and coincides with the boundary <i>of A</i>₀<i>,</i> namely, <i>{</i><b>K</b> : Σ<i>K</i>_<i>j</i><i>e</i>_0,_<i>j</i> = <i>C},</i> while the segment <i>BC</i> is convex. The breakpoint <i>B</i> has coordinates <b>K</b>_<i>s</i> which the result gives:<maths id="math0095" num="(63,i)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">s</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>,1</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0,1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">s</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>,2</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0,2</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">C</mtext></mrow></math><img file="EP0756403A2_D0104.tif" /></maths><maths id="math0096" num="(63,ii)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">s</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>,1</mtext></mrow></msub><mtext mathvariant="italic">log</mtext><mtext>(1/</mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>) + </mtext><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">s,</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">log(1/w</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext mathvariant="italic">) = log</mtext><mtext>(1/</mtext><mtext mathvariant="italic">L</mtext><mtext>)</mtext></mrow></math><img file="EP0756403A2_D0105.tif" /></maths> Note that for <i>K</i>₁ > <i>K</i>_<i>s,</i>₁ the boundary segment <i>BC</i> lies entirely above the linear extension <i>of AB,</i> with the difference attributable to the statistical multiplexing gain. Of course no such gain exists for <i>K</i>₁<i>< K</i>_<i>s</i>_,1<i>.</i> In this case class 1 is S-VBR and class 2 is NS-VBR for the given link bandwidth (and, implicitly, node buffer). The breakpoint <b>K</b>_<i>s</i> is clearly important for operations and design because, first, it demarcates between two different sets of effective bandwidths, and secondly, there are obvious performance benefits in operating to the right of the breakpoint since the effective bandwidth of class 1 sources is smaller.

0084In the sketch of FIG. 11, (iii) it is shown the linear segment <i>DE</i> which is tangent to <i>BC</i> at an intermediate point. As the numerical results indicate, in many cases the departure from linearity of boundary segments represented by <i>BC</i> is slight, in which case <i>DE</i> is close to <i>BC</i> throughout.

0085An important observation is the sensitivity of the statistical multiplexing gain, <i>g = e</i>₀/<i>e,</i> on the token rate <i>r.</i> Here a complementary qualitative result is presented which establishes that with all parameters except <i>r</i> held fixed, there exists a critical value of <i>r,</i> denoted by <i>r</i>_<i>c</i>, which separates token rates for which the statistical multiplexing gain exists, i.e. <i>g</i> > 1, from those for which <i>g</i> = 1. For simplicity consider the case of a single class.

0086Recall that if (<i>C/e</i>₀<i>)log</i>(<i>1/w</i>) ≤ <i>log</i>(1/<i>L</i>) then the maximum number of sources that is admissible, <i>K</i>_max = <i>C/e</i>₀ and hence <i>e</i> = <i>e</i>₀<i>.</i> On the other hand, if (<i>C/e</i>₀)<i>log</i>(1/<i>w</i>) <i>> log</i>(1<i>/L)</i> then <i>K</i>_max<i>> C/e</i>₀<i>,</i> and <i>e</i>₀ > <i>e.</i> Denote<maths id="math0097"><img file="EP0756403A2_D0106.tif" /></maths> so that <i>g</i> > 1 if and only if <i>f</i>(<i>r</i>) > <i>log</i>(1/<i>L</i>)<i>.</i> In (54) let <i>r</i> be varied, while the other parameters, <i>B, C, P,</i> and <i>B</i>_<i>T</i><i>,</i> are held fixed; note that <i>e</i>₀ and <i>w</i> depend on <i>r</i> as given in (21) and (22). Note that <i>f</i>(<i>r</i>) is a monotonic, strictly decreasing function of <i>r</i> for <i>r</i> in (0,<i>B</i>_<i>T</i><i>C/B</i>)<i>.</i> This is because both <i>e</i>₀ and <i>w</i> increase with <i>r</i>. Moreover, <i>f</i>(<i>r</i>) → ∞ as <i>r →</i> 0+ and <i>f</i>(<i>B</i>_<i>T</i><i>C</i>/<i>B</i>) = 0. For <i>r > B</i>_<i>T</i><i>C/B,</i> as discussed earlier, <i>e</i>₀ = <i>r</i> and <i>w</i> = 1, and <i>hence f</i>(<i>r</i>) = 0. Consequently, there exists an unique solution <i>r</i>_<i>c</i> to<maths id="math0098" num="(65)"><math display="block"><mrow><mtext mathvariant="italic">f</mtext><mtext>(</mtext><mtext mathvariant="italic">r</mtext><mtext>) = </mtext><mtext mathvariant="italic">log</mtext><mtext>(1/</mtext><mtext mathvariant="italic">L</mtext><mtext>),</mtext></mrow></math><img file="EP0756403A2_D0107.tif" /></maths> with the property that <i>f</i>(<i>r</i>) is greater or less than <i>log</i>(1/<i>L</i>) depending on whether <i>r</i> is less or greater than <i>r</i>_<i>c</i>. Hence:

0087<b>Proposition 4</b> Let <i>B, C</i> and the source parameters <i>P</i> and <i>B</i>_<i>T</i> be fixed. The statistical multiplexing gain <i>g</i> exceeds 1 if and only if <i>r</i> &lt; <i>r</i>_<i>c</i>. The critical token rate <i>r</i>_<i>c</i> is the unique solution <i>r</i> to the equation<maths id="math0099" num="(66)"><math display="block"><mrow><mfrac><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow></mfrac><mtext mathvariant="italic">log</mtext><mfenced open="(" close=")"><mrow><mtext>1/</mtext><mtext mathvariant="italic">w</mtext></mrow></mfenced><mtext> = </mtext><mtext mathvariant="italic">log</mtext><mfenced open="(" close=")"><mrow><mtext>1/</mtext><mtext mathvariant="italic">L</mtext></mrow></mfenced><mtext> ,</mtext></mrow></math><img file="EP0756403A2_D0108.tif" /></maths> where <i>e</i>₀ and <i>w</i> dependon <i>r</i> as given in (21) and (22).  ■

0088It is also of interest to examine the case where the mean rate <i>r</i> and period <i>T are</i> held fixed, and the source activity factor <i>w</i>_<i>Ω</i> is varied. Varying <i>w</i>_<i>Ω</i> is equivalent to varying the peak rate <i>P</i>, since <i>P</i> = <i>r/w</i>_<i>Ω</i><i>.</i> Some algebraic manipulation of (66) reveals that the critical token rate <i>r</i>_<i>c</i> may be written as<maths id="math0100"><img file="EP0756403A2_D0109.tif" /></maths> for<maths id="math0101" num="(68)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>Ω</mtext></mrow></msub><mtext> + </mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">T</mtext></mrow><mrow><mtext mathvariant="italic">buf</mtext></mrow></msub></mrow><mrow><mtext mathvariant="italic">T</mtext></mrow></mfrac><mtext> &lt; 1 .</mtext></mrow></math><img file="EP0756403A2_D0110.tif" /></maths> When (68) is violated, <i>e</i>₀ = <i>r</i> and <i>r</i>_<i>c</i> = 0.

0089The character of (67) is as follows. At <i>w</i>_Ω = 0, <i>r</i>_<i>c</i> has the value <i>r</i>_<i>c</i>_,0<i>= C/</i>[<i>e log</i>(1/<i>L</i>)]<i>.</i> As <i>w</i>_<i>Ω</i> is varied, <i>r</i>_<i>c</i> achieves a peak value <i>r</i>_<i>c,max</i><maths id="math0102"><img file="EP0756403A2_D0111.tif" /></maths> If <i>r</i>_<i>c,max</i><i> < r</i> then the multiplexing gain <i>g</i> will be 1 for all values of w_Ω. If <i>r</i> < <i>r</i>_<i>c</i>_,0 then there will be a critical value w_Ω,_<i>c</i>₂ such that <i>g</i> > 1 for w_Ω < w_Ω,_<i>c</i>₂ and <i>g</i> = 1 for <i>w</i>_Ω < <i>w</i>_Ω,_<i>c</i>₂. If <i>T</i>_<i>buf/</i>_T < <i>e</i><maths id="math0103"><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext>-1</mtext></mrow><mrow><mtext mathvariant="italic">nat</mtext></mrow></mfrac></mrow></math><img file="EP0756403A2_D0112.tif" /></maths>, then there is a third possibility, namely, that <i>r</i>_<i>c,</i>₀ < <i>r < r</i>_<i>c,max</i><i>.</i> In this case, there is an additional critical value, <i>w</i>_Ω, <i>c</i>1, such that if <i>w</i>_Ω < <i>w</i>_Ω,_<i>c</i>₁, then <i>g</i> = 1.

0090This analysis provides a possible perspective on the ways in which NS-VBR traffic can arise: statistical multiplexing can be impossible because (i) the mean rate <i>r</i> is too large; or (ii) the traffic is too smooth (<i>w</i>_Ω is large); or (iii) there is little buffering and the peak rate <i>P</i> is large (<i>w</i>_Ω is small).

<u>IV. Statistical Multiplexing of CBR and VBR Sources</u>

0091The inventive method embodies the recognition that when only a single class of statistically homogeneous traffic is present, the statistical multiplexing gain exceeds unity only if the capacity of a single resource <i>(e.g.,</i> the link bandwidth) exceed a critical value <i>C</i>_<i>c</i> which depends on the source characteristics. Thus, for a given bandwidth <i>C</i> at a node in a heterogeneous environment, there may exist source classes, termed "statistically multiplexable" classes, for which <i>C</i>_<i>c</i><i> &lt; C</i> and other classes, called "nonstatistically multiplexable," for which <i>C</i>_<i>c</i><i>≥C.</i>

0092The demand for CBR traffic is expected to constitute a significant part of customers overall demand in the initial deployment of ATM networks. As was pointed out in above, the fact that CBR traffic does not require buffers places disproportionate stress on network bandwidth. This is the source of one peculiarity associated with supporting CBR sources: the admission of CBR sources modifies the effective bandwidth of all VBR sources already in progress. Ironically, CBR sources are like NSMUX-VBR sources in that they both suppress statistical multiplexing among VBR sources. However, while NSMUX-VBR sources allow SMUX-VBR sources to share their bandwidth, CBR sources keep exclusive use of their bandwidth. (Thus, any pricing strategy should take these features into consideration.) How the presence of CBR traffic affects the resources available to VBR sources will be examined below. In particular, the admissible region for CBR and VBR sources will be derived.

0093Begin by first examining the effect of varying the channel capacity C on <i>e</i>₀ and <i>b</i>₀, the effective bandwidth and the effective buffer of regulated VBR sources for lossless multiplexing, while holding <i>B</i> and other parameters fixed. The important difference from above is that here <i>B</i> is fixed, while in the earlier treatment <i>B</i> is varied in proportion to <i>C, i.e. B/C</i> is fixed.

0094Recall <i>e</i>₀ given in equation (21). The corresponding buffer allocation for lossless multiplexing <i>b</i>₀ is given as <chemistry id="chem0001" num="0001"><img file="EP0756403A2_D0113.tif" /></chemistry> Note that increasing <i>C</i> allows the network to allocate more capacity to the user (increases <i>e</i>₀) and, in return, allocate less buffer space (decrease <i>b</i>₀). It is more appropriate here to consider <i>b</i>₀ as a measure of resource requirement rather than <i>e</i>₀ since <i>B</i> is fixed. It is interesting to note that <i>K</i>_max is a piece-wise linear function of <i>C,</i><chemistry id="chem0002" num="0002"><img file="EP0756403A2_D0114.tif" /></chemistry>

0095First consider the multiplexing of sources of a single VBR class in the presence of CBR traffic. Let <i>C</i>₀ denote the CBR rate. The capacity available to the VBR sources is therefore <i>C</i> - <i>C</i>₀<i>.</i> If <i>L</i> is the loss rate then there exists a unique solution in K, the number of VBR sources, to <chemistry id="chem0003" num="0003"><img file="EP0756403A2_D0115.tif" /></chemistry> if <chemistry id="chem0004" num="0004"><img file="EP0756403A2_D0116.tif" /></chemistry> where <i>F</i>_<i>K</i>(<i>s</i>*), <i>e</i>₀ and <i>w</i> are respectively given in (38), (21) and (11) with <i>C</i> replaced by (<i>C</i> - <i>C</i>₀). The solution to (72), denoted by <i>K</i>_max, is the maximum number of admissible VBR sources. Note that <maths id="math0104"><math display="inline"><mrow><mfrac><mrow><mtext mathvariant="italic">C</mtext><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow><mrow><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP0756403A2_D0117.tif" /></maths> and log<maths id="math0105"><img file="EP0756403A2_D0118.tif" /></maths> are increasing <i>with</i> (<i>C</i> - <i>C</i>₀) and, therefore, so is the right hand of (73).

0096<b>Proposition 5</b> With <i>B</i> and <i>C</i> held fixed, <img file="EP0756403A2_D0119.tif" /> is the smallest quantity such that the statistical multiplexing gain exceeds unity for all (<i>C</i> - <i>C</i>₀) > <img file="EP0756403A2_D0120.tif" />, and is the unique solution, in (<i>C</i> - <i>C</i>₀₎ to the equation<maths id="math0106"><img file="EP0756403A2_D0121.tif" /></maths>

0097Hence, if (<i>C</i> - <i>C</i>₀) ≤ <img file="EP0756403A2_D0122.tif" />, the multiplexing gain is unity and <i>K</i>_max is given by (71); if (<i>C</i> - <i>C</i>₀) > <img file="EP0756403A2_D0123.tif" />, <i>K</i>_max satisfies (72).

0098Now consider the admissible set of CBR and VBR sources,<maths id="math0107"><img file="EP0756403A2_D0124.tif" /></maths> It can show that the complement of the admissible set is convex. It can be shown that <maths id="math0108"><math display="inline"><mrow><mfrac><mrow><mtext mathvariant="italic">dk</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">dC</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP0756403A2_D0125.tif" /></maths> &lt; 1.

0099Consider now <i>J</i> VBR source classes and let <i>A</i>_<i>L,C</i>_{<sub2>0</sub2>} (<b>K</b>) denote the admissible set of the VBR sources given that the CBR rate is <i>C</i>₀,<maths id="math0109"><img file="EP0756403A2_D0126.tif" /></maths> where <i>F</i>_K(<i>s</i>*) is defined in (35) and (36) with <i>C</i> replaced by (<i>C</i> - <i>C</i>₀). The admissible set of CBR and VBR sources,<maths id="math0110"><img file="EP0756403A2_D0127.tif" /></maths> can be written as<maths id="math0111"><img file="EP0756403A2_D0128.tif" /></maths>

0100The results for <i>J</i> = 2 are summarized: <ul id="ul0003" list-style="none"><li><b>Case 1:</b> (<i>C - C</i>₀) <i><</i> min(<img file="EP0756403A2_D0129.tif" />),<i>A</i>_<i>L,C</i>_{<sub2>0</sub2>}(<b>k</b>) = A₀_<i>,C</i>_{<sub2>0</sub2>}(<b>k</b>)<i>,</i> i.e., there is no statistical multiplexing gain, where <i>A</i>_0,_<i>C</i>_{<sub2>0</sub2>} (<b>K</b>) = <i>{</i><b>K</b> : Σ_<i>j</i><i>k</i>_<i>j</i><i>e</i>₀,_<i>j</i> = <i>C</i> - <i>C</i>₀<i>}</i>,</li><li><b>Case 2:</b> (<i>C</i> - <i>C</i>₀) > max <img file="EP0756403A2_D0130.tif" />, <i>A</i>₀,_<i>C</i>₀ (<b>K</b>) ⊂ <i>A</i>_<i>L,C</i>_{<sub2>0</sub2>} (<b>K</b>),</li><li><b>Case 3:</b><img file="EP0756403A2_D0131.tif" /> < <i>C</i> - <i>C</i>₀ < <img file="EP0756403A2_D0132.tif" />. The boundary of the admissible set has a linear segment which coincides with the boundary of <i>A</i>_0,_<i>C</i>₀ (<b>K</b>) and a convex segment.</li></ul> The breakpoint has coordinates <b>K</b>_<i>s</i> which satisfy:<maths id="math0112"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">s</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>,1</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0,1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext mathvariant="italic">s</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>,2</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0,2</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">C</mtext><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow></math><img file="EP0756403A2_D0133.tif" /></maths><maths id="math0113"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext>s,1</mtext></mrow></msub><mtext> log(1/</mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>)+</mtext><msub><mrow><mtext mathvariant="italic">K</mtext></mrow><mrow><mtext>s,2</mtext></mrow></msub><mtext>log(1/</mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext>)=log(1/</mtext><mtext mathvariant="italic">L</mtext><mtext>).</mtext></mrow></math><img file="EP0756403A2_D0134.tif" /></maths>

<i>V. Conclusion</i>

0101The disclosure describes methods for admission control and routing by allocating network resources in network nodes. The techniques for bandwidth and buffer allocation described so far have been for a simple form of nodal buffer management. These techniques may be extended to handle more sophisticated buffer management schemes which exploit the priority levels of cells, for instance, by restricting access to the buffer by cells of low priority when the buffer content is above a certain threshold. In such schemes the objective of bandwidth and buffer allocation is to guarantee that losses sustained by the high priority cells do not exceed specified values; no guarantees are made for the performance of low priority cells. The techniques disclosed extend naturally to cover such refined forms of buffer management. Specifically, these calculations use for the buffer size <i>B</i> only the buffer space which is exclusively reserved for use by the high priority cells; the channel bandwidth <i>C</i> remains unchanged. Hence, with just this modification to <i>B</i> these techniques for the basic nodal buffer management scheme extend to the more sophisticated schemes.

0102The methods disclosed herein have been described without reference to specific hardware and software. Instead, the methods have been described in such as manner that those skilled in the art can readily adapt such hardware and software as may be available or preferable for a particular application.