1. Introduction

This paper illustrates four bandwidth problems and several solutions to them. The first deals with topology design and bandwidth allocation, the second with bandwidth management and congestion. The third is another bandwidth allocation problem, and the last considers virtual-path setup.

The topology design and bandwidth allocation problem is concerned with the ability to dynamically reconfigure a network in order to obtain best performance. In this paper, we are not concerned with the configuration of the transparent circuit-switched network, but with a packet-switched network built on top of the facility network. The aim is to exploit the flexibility of the digital cross-connect system to obtain more efficient design and operation of the packet-switched network [1–5].

Bandwidth management (BWM) protocols address congestion control. Congestion occurs when various sources compete for network resources, and these resources cannot handle the demand. This may happen when logical channels request bandwidth that cannot be supported, or when the network admits more calls than the links can handle, or at any node due to buffer shortage. BWM protocols prevent congestion essentially by accepting or refusing a new-arrival call. These protocols have five objectives: protection of shared network resources, fairness, robustness, simplicity, and flexibility. This paper illustrates several bandwidth management methods that can be used to avoid congestion based on call admission or refusal [6–23].

Broadband high-speed networks (BISDN) are expected to support a wide variety of services, so various quality-of-service (QOS) levels and bandwidths are needed. Accordingly, efficient bandwidth allocation methods must be implemented to meet the needed QOS while maintaining high utilization of the bandwidth. Several bandwidth allocation methods exist, such as simple channel strategy [24], slot assignment methods [25, 26], virtual finishing-time methods [27–30], integrated access and cross-connected systems [10, 31], resource allocation analysis programs [32–34], multilevel control methods [35, 36] and others [37–56]. Expert systems, neural networks, and fuzzy logic are also used to deal with the bandwidth allocation problem [48, 49, 57].

The virtual path is a logical direct link between two nodes; it includes a number of virtual circuits. Each virtual path has a bandwidth that defines the maximum number of virtual circuits it can carry. Virtual paths are set up to optimize performance for all users. This paper presents three methods for setting up the virtual paths [7, 52, 58, 59].

The rest of the paper is divided into five sections, each concerned with one problem, and these are divided into many subsections, each illustrating a solution. Section 2 presents topology design and bandwidth allocation; Section 3 discusses bandwidth management and congestion. Section 4 is concerned with another bandwidth allocation problem. Section 5 presents the virtual-path set-up problem. Finally, Section 6 is a summary of the paper.

2. Topology design and bandwidth allocation

In broadband high-speed networks, switches are connected with multiple digital cross-connect system (DCS) trunks. The ability to reconfigure the network dynamically is very desirable in order to benefit efficiently from network resources, especially during variable flow.

Most previous studies have been based on networks that provide circuit-switched channels of various rates between pairs of user sites. In this section we are concerned with packet-switched networks. The aim is to exploit the flexibility of DCS to obtain more efficient design and operation of the embedded network [1–5].

The backbone topology comprises a number of switches and trunks, while the embedded topology comprises a set of pipes, each having a specific capacity. The sum of the capacities of the embedded links multiplexed on the backbone must not exceed the capacity of the trunk itself [1]. Figure 1(a) shows a backbone network topology. Several embedded topologies can be derived from this topology; two examples are shown in Figure 1(b).

Figure 1

We have assumed that the backbone facility network has already been defined (number and locations of switches, fiber trunks, etc.). This facility will be partitioned among many services, public and private, operational and experimental (telephony, video distribution, private P/S nets, ISDN, BISDN, etc.).

To design the embedded-network topology, the problem is formulated as a network optimization problem in which a congestion measure based on the average packet delay is minimized subject to capacity constraints.

Assuming that the number and locations of switches and trunks in the backbone network are already defined, we address the problem of mapping the embedded topology. This mapping may have to be revised very frequently in order to overcome the traffic fluctuation.

Two types of reconfiguration procedures exist. The first one may involve a major change in embedded-network topology and may not be transparent to users (i.e., some connections may be interrupted and later resumed); this type of reconfiguration may take place with a frequency of months or weeks. The second one involves only minor perturbations in the embedded topology, and should be user-transparent; it could be carried out on an hourly basis. The proposed methodology is the same for both types.

•   Problem definition
Suppose that an initial embedded topology is defined, and the embedded link bandwidth and packet routing are chosen such that

• The average packet delay is minimized.
• The sum of the aggregate bandwidth of all pipes using the trunk does not exceed the capacity of this trunk.
• All traffic requirements are satisfied without exceeding the pipe bandwidth.

If both backbone and embedded networks are modeled using graphs, C_i is the capacity of arc i, f_i is the flow of arc i, commodity com(i, j) is the flow of packets from source i destined for j, X_i is the flow of each commodity i, and Z is the average packet delay, the problem can be formulated as follows.

Given:

• Topology and arc capacities of the links of the backbone network.
• Topology of the embedded topology. (Note that each arc in the embedded topology contains a number of pipes.)
• Offered traffic.

Objective:

• Minimize the average packet delay Z.

Variables:

• Capacities of the arcs of the embedded topology C.
• Routing on the embedded topology.

Constraints:

1.	The aggregate capacity of all arcs in the embedded topology must not exceed the capacity of the backbone topology arcs C,
	iPi C, (1) i=1 where is the number of arcs in the embedded topology and P is the arc path vector (0s or 1s).
2.	The flow of each commodity k carried on all of the pipes must be equal to the flow rk of commodity k offered to its source,
	Nk (k;n) = rk           k, (2) n=1 where N is the number of pipes and n is the pipe number.
3.	The aggregate flow on each arc in the embedded topology must be equal to the sum of all commodities flowing on all of the pipes using this arc,
	Q Nk (k;n)(k;n) = , (3) k=1 n=1 where is the number of commodities and (k; n) is the flow commodity vector (0s or 1s).
4.	The aggregate flow on each embedded arc must not exceed its capacity, . (4)
5.	(a) 0,	(5)
	(b) 0, 0. (6)

•   Algorithm
First, a random initial embedded topology is found. One choice is to include all possible M(M – 1) links (fully connected graph), and then let an optimization procedure pick the most effective ones. Another choice is to insert direct links between node pairs with the highest throughput requirements [1]. Remember that C_i is the capacity of arc i, f_i is the flow of arc i, commodity com(i, j) is the flow of packets from source i destined for j, X_i is the flow of each commodity i, and Z is the average packet delay.     The problem can be formulated as follows.

Given:

• Topology and arc capacities of the backbone topology.
• Arc vectors of the embedded topology (0 or 1).
• Traffic requirements.
• Initial feasible solution (⁰, ⁰).
• Tolerance t.

Objective:

•	Find vectors (C, f, X) that minimize the average packet delay Z (suppose M/M/1 model) [60]:
	Z = 1 m , (7) m – m m=1 where m is the value of the capacity of link m, m is the aggregate flow on link m, and is the overall flow.

Steps:

1.	Set the iteration number k to zero, and delay to (k = 0, Zold = ).
2.	Increment the iteration number k by 1 (k = k + 1). Find the vector C# satisfying constraints 1 and 5 and minimize: min Z(k-1, k–1) • . This may be done using the revised simplex method [61].     Find the vector f# satisfying constraints 2 to 6 and minimize: min Z(k-1, k–1) • . This may be done by constructing a minimum path solution (#, #) for the embedded topology where the cost of each arc u is calculated as Z(k–1, k–1)   . (8) u
3.	Find the value * that minimizes the delay Z[(#, #) + (1–)(k–1, k–1)]. (9) This optimum may be obtained by any linear search method, such as the golden section technique [62].
4.	Set (k, k) = *(#, #) + (1 - *)(k–1, k–1).
	If Z(k-1, k–1) – Z(k, k) t, then go to step 5 (a potential local minimum has been found); else go to step 2.
5.	If Zold - Z(k, k) t,
	then go to step 6; else if Zold Z(k, k), then set (*, *) = (old, old); else set (*, *) = (k, k). Stop (the local minimum has been found).
6.	Set (old, old) = (k, k) and Zold = Z(old, old).
	Using k-1, find the vector a that solves min Z =   1  ik-1    i – ik-1 m=1 such that iPi C and k–1. i=1 Set (k, k) = (a, k -1). Go to 2.

Output:
The local minimum is (*, *, *), which satisfies all of the constraints.

If R is the ratio between the delay of the embedded topology and that of the original (backbone) topology, experimental results show that R decreases with the increase in traffic, implying that using an optimized embedded topology instead of the backbone topology leads to improvement in the average delay.

3. Bandwidth management

Bandwidth management, used to prevent congestion, is essentially done by accepting or refusing a new-arrival cell. These BWM protocols must be simple, distributed, and flexible, and must have three objectives: protection of shared resources, fairness, and robustness. Many BWM protocols exist [6–23, 31], and each of the following subsections represents one.

•   Leaky-bucket method
In this method, the new traffic entering the network from each end device is monitored in real time. The algorithm uses the following steps [6–8]:

• Initialize a counter X to zero.
• If a new cell arrives,

  	decrement X; X = max(X – cT, 0),
  			where c is a specified parameter and T is the elapsed time since the last cell arrival.
  	If X M, where M is a prescribed value,
  		then		the cell is passed tagged;
  		else		the cell is passed untagged. Increment X; X = X + L, where is a specified parameter and L is the cell length in octets.

• Tagged cells are discarded whenever they encounter a moderate threshold at any cell queue along the virtual circuit.

One can select so that L = 1; then the throughput is c cells per unit time. M specifies the cell-burst size that is allowed following a substantial idle period.

This algorithm allows a sustained, untagged throughput rate of c/ octets per unit, and a burstiness that is controllable (for a given value of c and ) through selection of the value of M.

Let FVT represent the fraction of violated traffic and FPR represent the fraction of reduction in peakedness (ratio of non-violation-tagged peakedness to traffic output peakedness). is the traffic-shaping parameter (idle time between successive ATM cells), and M is the leaky-burst parameter.

Results show that both FVT and FPR decrease with an increase in M or , meaning that utilization also decreases with an increase in M or . In general, we can say that using the leaky-bucket method with good selection of M and reduces effective network utilization (for non-violated traffic), and that this traffic could be handled very easily by the network.

•   Peak-rate allocation
In this method, the user specifies both the maximum rate of cell arrival and the network virtual circuits. As shown in Figure 2, each link has a peak-rate monitor in order to guarantee that the sum of the peak rates of all virtual circuits using that link does not exceed its maximum cell rate [9, 18]. Each virtual circuit (VC_i) must have the following parameters:

• Minimum time between cells, d_i.
• Time the most recent cell was transmitted, t_i.

The following steps are taken at any new cell arrival:

When a new cell arrives for VC_i at time T:

	If T - ti < di,
		then if at the link queue the total peak rate < link rate,
			then the cell enters the network;
			else one of two decisions may be taken:
				discard the cell, or
				mark the cell (marked cell can be discarded in case of congestion);
		else wait until time reaches ti + di.

Figure 2

This method is easy for users to understand and specify, and it permits a straightforward implementation. Results prove that the peak-rate allocation method offers very strong performance in the case of uniform traffic, but in the case of burst traffic, it makes poor use of network bandwidth.

•   Bursty traffic specification and allocation
In this approach, the user specifies a peak cell rate, an expected average cell rate, and a maximum burst size. As shown in Figure 3, each link has a peak-rate monitor and a token generator. The peak-rate monitor acts as in the previous method, while the token generator generates a number of tokens to be used by the cells passing from the peak-rate monitor. The maximum number of tokens in the pool is limited by the specified maximum burst size [9, 18].

Figure 3

The algorithm is divided into two parts; the first part is the same as the peak-rate method. However, if a cell passes from the peak-rate monitor, the second part takes place:

If there are any token(s) in the pool,
then one token is consumed, and the cell enters the network;
else the cell is marked and passes. (Marked cells are
	discarded and returned to the user if the network
	encounters congestion.)

The network must be able to decide whether a given set of virtual circuits can be safely multiplexed together according to the acceptable cell loss rate.

This method is more difficult for users to understand, specify, and implement than the previous one, but it allows performance guarantees to be traded off against link efficiency and traffic burstiness. The main disadvantage of this approach is that there are currently no computationally effective ways to decide when a new virtual circuit can be safely multiplexed with other virtual circuits specified in this manner.

•   Minimum-throughput allocation
In this method, the network allocates slots in the link buffers of the virtual circuits, in proportion to the bandwidth they require from this link. Virtual circuit routing ensures that the sum of the minimum required throughputs does not exceed the link bandwidth [9, 18].

During overload periods, each virtual circuit can use only its own slots, and any excess cells are discarded. During the unloaded periods, the following steps are taken:

When a new cell for virtual circuit VCi arrives,
	if free slots exist for VCi,
		then if the queue of the link is not full,
			then store the new cell unmarked
			else discard one marked cell in the link queue
				and store the new cell unmarked;
		else if there are no free slots for VCi,
			then if the queue of the link is not full,
			then store the new cell marked (it may be discarded);
			else discard this new cell.

This method is easy to specify and implement. It can provide high efficiency in the case of uniform traffic, but uniformity is not always guaranteed, since the network cannot promise anything about throughput in excess of that requested. Users with bursty traffic streams, but needing all or almost all of their data to get through regardless of other traffic, can specify a high required throughput. However, this will lead to peak-rate allocation.

•   Fast buffer reservation
In this method, each virtual circuit has one of two states, idle or active. Any active virtual circuit is assigned a number of buffer slots according to the bandwidth it requires (as in the preceding subsection). Transition between an active and an idle state occurs upon reception of a marked cell, denoting either the start or the end of a burst. A maximum time-out period exists; after this period the virtual circuit must change from the active to the idle state. This period is determined by the delay variation in the network. The choice of this period puts a bound on the peak rate of virtual circuits [9, 18].

Suppose that three types of cells exist: start S, middle M, and end E. Traffic may be of the form SSS … SSSE, SMMM … MMME, or SMM … MSM … MSM … E.

Any virtual circuit VC_i must provide the following information:

• Number of buffer slots for VC_i when active: B_i.
• Number of buffer slots already used by VC_i: b_i (b_i B_i).
• State of virtual circuit VC_i (active or idle).

The number of unallocated buffer slots B in the queue link must also be known. This algorithm takes the following steps:

•	If a virtual circuit i (VCi) receives a start cell: if VCi is idle,
		then if B - Bi < 0,
			then discard the cell;
			else set VCi state to active,
				set timer of VCi,
				B = B - Bi,
				if bi = Bi,
					then store the cell in the buffer marked;
					else bi = bi + 1 (bi < Bi);
						store the cell in the buffer unmarked.
•	If a virtual circuit i (VCi) receives a start or middle cell: if VCi is active,
		then queue the cell;
			reset the timer of i;
			if bi = Bi,
				then store the cell in the buffer marked;
				else bi = bi + 1 (bi < Bi);
					the cell is left unmarked.
•	If a virtual circuit i (VCi) receives a middle or end cell: if VCi is idle,
		then discard the cell.
•	If a virtual circuit i (VCi) receives an end cell: if VCi is active or its timer expires,
		then set VCi state to idle;
			B = B – Bi.
•	If a virtual circuit i (VCi) receives a loner (low priority cells):
		then store the cell in the buffer marked.

Note that whenever a cell is removed from the buffer of the link, its appropriate b_i is decremented. It is clear that this method requires two bits of the ATM cell header to encode cell type (loner, start, middle, end).

The buffer reservation mechanism can be applied directly to constant-rate virtual circuits (uniform traffic), as well as to bursty virtual circuits (bursty traffic). Such virtual circuits would simply be activated initially and would remain active all the time. The software making the routing decisions must be chosen to ensure a very small probability that the instantaneous demand for buffer slots will exceed the buffer capacity.

•   Congestion control by block dropping on voice
This method considers only voice, voice-band data, and facsimile coding. It uses the concept that the loss of less significant bits in voice (compared to whole cells) causes negligible degradation of quality. This loss may reach 10% of the whole cell [10, 11].

Each voice source is sampled at 8 kHz and encoded using an embedded scheme at 32 kbps. Over 16 ms, 128 samples are collected and organized into four-block cells of equal length (note that all cells are also of equal length).

Each cell is divided into four blocks. All of the least significant bits (first quarter of the cell) from the 128 samples are contained in the first block of the cell, the next bits (next quarter) are contained in the second block, etc.

As shown in Figure 4, a header is used to incorporate a range of information about the packet (such as destination). One bit in the header may be designated to indicate whether or not a packet is “bit-droppable.” The system must distinguish a voice-band data (VBD) cell from a voice cell, and can set this bit to prevent bit dropping on a VBD cell.

Figure 4

A congestion measure is defined in terms of the number of voice and data cells currently in wait state. Four thresholds are also defined. If the congestion measure exceeds the first threshold, the first block from the cell about to enter transmission is dropped. If the measure exceeds the second threshold, the second block from the cell about to enter transmission is dropped, etc.

The cell header contains a field indicating the number of droppable blocks in the cell. In order to protect voice-band data and facsimile cells from block dropping, this field is always set to zero.

Results in [11] show that, in general, the bit-dropping method reduces the mean delay, especially with heavy loads, where threshold values have great effect on network performance. Low threshold values lead to severe degradation in the mean number of bits per sample, and also to increased packet loss probability at high load. High threshold values may result in a slight improvement in mean bits per sample or packet loss, but at the same time the mean packet delay increases.

Equation (10) offers a prudent choice of threshold values such that delay performance is optimized while performance objectives are met:

b = min		4,	1		C	– H			,	(10)
			S		Nr

where N is the number of voice sources, S is the number of voice samples per packet, H is the number of bits in the header, r is the packet arrival rate per voice source, and C is the transmission capacity.

In general, results prove that bit dropping smooths the superposition-packet voice process by speeding up the packet service rate during critical periods of congestion in the queue.

4. Bandwidth allocation methods

In this section the problem of adaptively managing the bandwidth of an integrated network is considered. Several methods exist for dealing with this problem, such as simple channel strategy [24], slot assignment methods [25, 26], virtual finishing time methods [27–30], integrated access with a cross-connected system [10, 31], resource allocation analysis programs [32–34], multilevel control methods [35, 36], network access port control methods [37], filtered input rate methods [38], statistical multiplexing methods [39], synchronous bandwidth allocation methods [40], and others [31, 41–47, 50–56]. Expert systems, neural networks, and fuzzy logic are also used to deal with the bandwidth allocation problem [48, 49, 57]. This section is divided into a number of subsections, each illustrating one method of efficiently allocating the bandwidth.

•   Simple dynamic channel strategy
In this method, each service has its own channels. If a call arrives from a service without sufficient free channels, it can use channels from another service, but only if the current number of free channels at this service exceeds a certain threshold; otherwise the call is blocked.

Sometimes it is possible, especially in the case of telephone traffic, to determine the expected number of new calls arriving in a certain period of time by using a Poisson distribution. Then it is possible to maintain a specific blocking probability by keeping a reserve of free channels based on the expected number of calls in this period. This number may also help to set the threshold [24].

Results show that dynamic channel allocation affords more efficient resource utilization for all types of services. The throughput is increased with this method over that for the case in which each service uses its own channels. This increase is small, however, when the system carries primarily traffic from a single type of service. The percentage increase in throughput decreases as the number of channels assigned for each service increases. The throughput also decreases with any decrease in block probability or mean time between call initiations.

•   Slot assignment methods
In the model shown in Figure 5, N connections are multiplexed in the source. Each source has N buffers, with a number of cells stored on each [25, 26].

Figure 5

In slot assignment algorithms, time is partitioned into cycles, each cycle is partitioned into a number of slots, and each slot is used to transmit one cell per connection. Five bandwidth allocation methods can be built using the slot assignment concept [25].

1. Static slot assignment method
In this method, both the duration of each cycle and the duration of each slot are constant, so the number of slots in each cycle is fixed. These slots are divided equally among the connections.

Figure 6 shows an example in which the cycle is divided into 24 equal slots, and the slots are divided equally among the four existing connections so that each connection has six slots to use, regardless of the number of cells it has. It is clear that this method leads to wastage of cells, since no connection can use slots other than its own, even if it has exhausted its own slots and the others have not used theirs.

Figure 6

2. Buffer-population-based dynamic slot assignment method
In this method also, both the duration of each cycle and the duration of each slot are constant, so the number of slots in each cycle is fixed. But in this method, the number of slots allocated to each connection is not constant, but is proportional to the number of cells in the buffer belonging to the connection at the time of allocation. However, there is a maximum limit on the number of cells allocated to a connection.

Due to this maximum limit, some slots may be unallocated in a cycle, leading to wastage of cells. There are two ways to overcome this disadvantage: The first is to ignore this maximum limit, and the second is to allocate these excess slots to the connection with the largest number of cells in its buffer.

3. Adaptive slot assignment method
In this method the cycle size is variable, and all connections are served in order. At its turn, any connection sends all of the cells stored in its buffer at that time, with a maximum limit m, so if the number of cells in the connection exceeds this limit, it sends only the first m cells and must wait for its next turn to send the rest (or another m cells).

4. First-come, first-served slot assignment method
In this method, no cycles exist. Each cell is transmitted on a first-come, first-served basis, regardless of the connection to which it belongs.

This method is extremely inefficient, since if a connection generates many cells because of an error, it will use a large portion of the network bandwidth, and this will slow the other connections with correct cells.

5. Rate-based dynamic slot assignment method
In this method, the size of each cycle and the number of slots allocated to a connection in a cycle are variable. With the bit rate for each connection being known, the number of slots allocated to a connection per cycle changes with this bit rate, but each connection must have at least one slot per cycle. Thus, for each period of time, the cycle size and the number of slots allocated to a connection per cycle both change. This method decreases the number of wasted slots, but some may still exist.

Results prove that Methods 2, 3, and 4 yield much lower average delay than Methods 1 and 5:

• As stated previously, the first-come first-served method has no way to prevent a connection from generating abnormally large numbers of cells and consequently using a large portion of the bandwidth.
• Methods 3 and 4 are superior, since slots are never wasted.
• In Methods 1 and 5 slots may be unused. This occurs when there is no cell from the connection to assign to these slots, while there are cells waiting from other sources.

Comparing average delay to line utilization, it has been found that

• The average delay for Method 4 is nearly equal to that for Method 3 for the entire range of line utilization.
• The average delay for Method 2 is slightly higher than that for Method 4 for low to moderate line utilization.
• The average delay for Method 2 is nearly equal to that for Method 4 for high line utilization.

•   Virtual finishing time methods
High-speed networks are capable of carrying many types of traffic (voice, graphics, video, etc.), each with a different required quality of service (QOS). In virtual finishing methods (Figure 7), each node has a number of buffers, each type of service is stored in one buffer, and these buffers are themselves FIFO (the head of each buffer is served first). Since all of the buffers share one link, a scheduling method must be used.

Figure 7

This section discusses algorithms that determine how these buffers share the link bandwidth, using the expected departure time of calls, or virtual finishing time (VFT). Several methods for calculating the VFT [27–30] allow a guaranteed rate and average delay for each service, independently of the behavior of the other services. Note that c_iⁿ is the cell i arriving at a buffer n, and VFT F_iⁿ is the expected departure time of the cell i from buffer n.

1. Packetized generalized processor sharing (PGPS)
This method distributes the idle bandwidth at any time t, in proportion to a partitioning parameter of the non-empty buffers [27–29]. Each c_iⁿ is given a VFT F_iⁿ. The cell having the least VFT is served first; if multiple cells, each at the head of a buffer, have the same VFT, they are served in arbitrary order:

VFT = Fin = max[Fni–1, V(ain)] +	1		(F0n = 0),	(11)
	n

where _n is the bandwidth-partitioning parameter of the buffer n (₁ + ₂ + ₃ + · · · + _N 1), a_iⁿ is the arrival time of c_iⁿ, and V is the virtual time function of the node.

The virtual time V(t) is defined to be zero for all times at which the link is idle. For a busy period, the beginning time is set to zero [V(0) = 0]; then V(t) evolves as follows [28]:

V(tj–1 + ) = V(tj–1) +			tj – tj–1, j = 2, 3, · · · ,	(12)
	iBji

where B_j is the set of sessions that are busy in the interval (t_j–1, t_j).

Results prove that under PGPS, the delay of a packet from service i can be bounded in terms of the service i queue size seen by that packet upon arrival, even in the absence of any rate control. This enables services to take advantage of lightly loaded network conditions.

2. Self-clocked fair queuing (SCFQ)
This method uses the same concept as the packetized generalized processor sharing method, but with different V(t). V(t) is the VFT of the last non-best-effort cell served before time t. If no such cell exists, then V(t) = 0 [27, 29]:

V(t) =		0	if no cell has been served before time t		.	(13)
		Fin	otherwise

This method puts a bound on the delay of any cell passing through a node. It leads to higher average delay than the previous method, but also provides fairness in bandwidth distribution. Also, its VFT calculation is easier than that for the PGPS method [27].

3. Non-idling virtual clock
This method uses the same concept as the packetized generalized processor sharing method, but with different VFT [27, 30]:

VFT = Fin = max (Fni–1, ain) +	1		(F0n = 0).	(14)
	n

This method produces less average packet delay than the previous two methods. Its main advantage is that the computation of the virtual time is negligible, since it is simply extracted from each packet as it goes into service.

4. Idling virtual clock
In this method, all cells at the heads of the buffers are considered for service at each departure epoch. This method uses the same concept as the PGPS and the same VFT equation as the previous method, but with different treatment of congested and best-effort cells. Buffers are considered to be congested if they exceed some threshold.

Two methods are offered; the first one favors congested cells with no regard for best-effort cells, while the second also favors congested cells, but with best-effort cells favored in the absence of congestion [27].

A. Favoring congested buffers     This method favors congested cells. At any time t, the VFT for all buffers is calculated:

•	If no buffers are congested,
		then a cell from buffer i of the smallest VFT (Fin) is served first.
•	If at least one buffer is congested,
		then find the congested buffer j with the smallest VFT (Fjm);
			find the non-empty buffer i (among all buffers) with the smallest VFT (Fin);
			if (t Fin and Fin < Fjm),
				then cin is served;
				else cjm is served.
•	Best-effort cells are served if all N buffers (congested or not) are idle.
B. Favoring congested buffers, then best-effort traffic     This method also favors congested cells, but best-effort buffer cells are favored if no congested buffers exist. At any time t, the VFT for all buffers is calculated:
•	If no buffers are congested and the best-effort buffer is empty,
		then the cell from buffer i of the smallest VFT (Fin) is served first.
•	If no buffers are congested and the best-effort buffer is not empty,
		then find the buffer i with the smallest VFT (Fin);
			if (Fin t),
				then cin is served;
				else a best-effort cell is served.
•	If at least one buffer is congested,
		then find the congested buffer j with the smallest VFT (Fjm).
			find the non-empty buffer i (among all buffers) with the smallest VFT (Fin);
			if (t Fin and Fin < Fjm),
				then cin is served;
				else cjm is served.

The idling virtual clock method handles congested cells as well as best-effort cells (in the second scheme); this leads to minimum average delay for the overall packets.

•   Integrated access and cross-connect system (IACS) multiplexing method
In this section, the T1–T2 scheme using only voice and data is considered; then a generalization of this method using all services is explained. We first classify all of the services, and then explain how they are treated.

T1–T2 scheme
In this method, only three types of cells are considered: signaling cells, voice cells (voice, voice-band data, and facsimile), and digital data cells. Each type is queued in a single buffer, and cells are served according to the T1–T2 scheme [10]:

• Waiting voice cells are served until a maximum of T₁ ms has elapsed or until the voice queue is exhausted.
• Waiting data cells are served until a maximum of T₂ ms has elapsed or until the data queue is exhausted.
• Signaling cells have high priority; they may interrupt both voice and data cells.

Figure 8 represents an example of the T1–T2 scheme. Because signaling traffic intensity is very small compared to others, we can say that the link bandwidth is allocated to voice and data with the ratio of T₁ to T₂, respectively:

Bandwidth for voice	T1	B;
	T1 + T2

Bandwidth for data	T2	B,	(13)
	T1 + T2

where B is the overall link bandwidth. Values of T₁ and T₂ can be chosen either to reserve minimum bandwidth proportions for both types, or to adjust the required delays for both cell types.

Figure 8

Dynamic time slice (DTS) scheme
This method is a generalization of the T1–T2 scheme, but with all broadband services. Cells are classified into four types; Table 1 shows the characteristics of each type and gives examples of each one [10, 31]. Figure 9 shows the traffic types and their delay bandwidth requirement.

Figure 9

Table 1   Service classification for the T1–T2 scheme.
Cell type	Characteristics	Examples
Type 1A Delay-sensitive, isochronous high- bandwidth services	Real-time services Bandwidth must be   guaranteed at call setup Isochronous: Fixed high   bandwidth is required   for duration of call	Services needing high bandwidth   with constant bit rate (CBR),   such as CBR conference video Real-time high-CBR services
Type 1B Delay-sensitive, non-isochronous high-bandwidth services	Real-time services, with high   bandwidth Non-isochronous: Each call   alternates between active and   inactive periods and   generates high-bandwidth data   stream during active periods	Variable-bit-rate video LAN-to-LAN calls
Type 2 Delay-insensitive high-bandwidth services	Non-real-time services User may specify tolerable delay Usually transported during slack   periods	Document Image Video delivery services  (non-real-time)
Type 3 Low-bandwidth statistically multiplexed services	Delay-sensitive, with   end-to-end delay ranging   from 10 s to 100 ms	Packetized voice Low-speed data Enquiry-response messages

Each type of service is assigned a separate queue. The DTS server services all of the queues by cyclically visiting each queue and allocating it a time slice. This time slice is proportional to the bandwidth required by the queue.

In any instance, if n is the number of non-empty queues in the DTS, one queue (with number 0) is added for signaling. To calculate the time slice for the n + 1 queue, the following equation must be used:

fi =	Ti			0 i n;
	n
		Ti
	i=0

n	fi 1 – f0;
i=1

n	Ti Dc,	(16)
i=1

where f_i is the fraction of the bandwidth for queue i, T_i is the time slice required for queue i, D_c is the DTS service cycle time (1 to 2 ms),

Dc = Mc,

(17)

M_c is the number of cells in a DTS service cycle, is the cell transmission time on the link, and f₀ is the bandwidth reserved for the signaling traffic on each link. Different schemes are used for each traffic type.

Servicing scheme for Type 1A     Whenever a user makes a call-set request to virtually allocate the required bandwidth, the network sends the request to all nodes en route to the destination. The user is guaranteed the allocated bandwidth for the duration of the call. A routing scheme is used to find the appropriate path from source to destination.

Servicing scheme for Type 1B     With this type, calls within each class are statistically multiplexed, but each class is assigned a guaranteed bandwidth. Each class maintains a traffic table (bandwidth versus capacity) to provide the amount of bandwidth required to multiplex a given number of calls in the class queue. A new call is admitted iff spare bandwidth is available on the link, in which case the bandwidth for this call class is increased in the table by increasing the time slice. When the call completes, the bandwidth for this call class is updated by decreasing the time slice for this class. Because of statistical fluctuations, unused bandwidth may exist; any such unused bandwidth is available to other traffic in the system. A routing scheme is used to find the appropriate path for each call.

Servicing schemes for Type 2     Three schemes exist for this type; the needs specified by the call requests determine which should be used.

1. In this scheme, the user sets up a connection with the nearest service node, which in turn accepts the bulk information and stores it in its memory. After the destination is notified, the connection with the user is terminated. During slack periods of traffic, the service node negotiates with other nodes en route to the destination to allocate the appropriate bandwidth, then transports the data. When the data is delivered, the call is cleared, and the destination sends a service-completion message to the source.
2. In this scheme, the user specifies the transaction size, delay tolerance, and bandwidth required. The network itself requests the call setup, and the information awaits transmission at the user terminal, not in the access node. During a slack period, the call is set up, but within the deadline specified by the user; then information is delivered as in the first scheme.
3. In this scheme, each link is assigned a low-priority queue with no bandwidth guarantee. It uses only spare bandwidth (idle cell slots) in each DTS cycle. If the length of this buffer exceeds a certain threshold, STOP/SEND signals are sent to neighbors to prevent congestion.

• It guarantees the desired bandwidth to connections which require a fixed wide bandwidth, and thus facilitates setting up virtual circuits.
• For each class, call admission is based on capacity versus bandwidth tables for that class. These tables are updated as technology changes.
• It is an efficient way of combining isochronous high-bandwidth services with variable-bit-rate, statistically multiplexed connections.
• Placing each call class in a separate queue facilitates serving it according to its required QOS.
• Any bandwidth unused by a call class is available to other traffic present in the multiplexor.
• The call-admission procedures are call-class-based, so the usage cost for network resources can be estimated separately for each call class, and a simple call-class billing system can be built.

The main disadvantage of the DTS scheme is that users may be penalized by buffer overflow if they exceed the contracted bandwidth, and there is no spare bandwidth on the link.

•   Resource Allocation Analysis Program (RAAP)
The Resource Allocation Analysis Program [32] is particularly useful for satellite communication. Communication by satellite requires both bandwidth and power resources. A single request is actually two subrequests, one forward and one backward, and backward subrequests may have different characteristics from forward ones. A request is not satisfied unless sufficient quantities of both power and bandwidth are available for both subrequests. Resource requests may be negotiated at the time of the request.

Each subrequest has the following information:

• Arrival time (time at which the request is received by the resource allocation process).
• Start time (time at which resources will actually begin to be used).
• Duration.
• Data rate (D).
• Modulation (M).
• Request negotiation.
• Forward error correction code rate (FEC).
• Geographical zone.

Note that M = 0.5 for QPSK (forward), and M = 1 for BPSK (backward). Requests may be immediate or booked (in advance).

From this information, bandwidth (B) for each subrequest (direction) is computed using the formula

B =	KDM	,	(18)
	FEC

where K is a bandwidth factor to provide margin for adjacent-channel interfaces, etc. (K 1.5). Two possible algorithms for allocating the resources exist:

• Complete partitioning (CP): All available resources are partitioned from the beginning among the different service classes, and each request can use only its own channel [33].
• Complete sharing (CS): All available resources are available to all classes [34].

RAAP allows the following:

• Partitioning of bandwidth into pools (each pool has a number of channels).
• Sharing among channel pools.
• Designation of a pool of raw bandwidth for common use.

Each time period, statistics are taken in order to assign bandwidth to each channel pool. For each pair of pools x and y, a table exists to specify the maximum number of channels that pool x can take from pool y (a maximum threshold may exist).

For any request, both the start time and the duration are known, so we can visualize a “request window” rectangle, with its left side at the start time and its right side at the start time + duration. Height represents the required resource, and any modification of start time or duration will change the position of the whole rectangle.

Figure 10 represents a pool with only two channels, into which four requests are made. In Figure 10(a) Request 4 is lost, since no channel is free at its arrival time, while in Figure 10(b) requests are organized such that no request is lost. Research is still needed on means for allocating the requests among channels to obtain maximum performance.

Figure 10

As shown in Figure 11, when requests arrive at the resource controller, the controller checks the resource maps and attempts to grant requests without any modification. If this is not possible, it will then try to grant requests with various combinations of modifications (start time, duration, data rate, or any combination of them). Three answers are possible for any attempt:

• Yes: The request is granted and the customer accepts any modifications.
• No: The request is not granted because the modifications cannot be satisfied.
• Abort: The request can be granted but the customer refuses the modifications.

Figure 11

Note that a request may be blocked at the outset if there are no idle modems available at the resource controller to accept the data call.

If a subrequest with modification is granted, the resource allocation sequence shown in Figure 12 will be followed. This algorithm is used for considering various levels of sharing.

Figure 12

The primary channel pool is the pool whose data rate, modulation, and FFC values match those of the subrequest itself. If this pool does not exist or has insufficient space, sharing among channel pools is attempted. If this also fails, the controller attempts to place the subrequest in the common bandwidth pool if it is defined. The satellite power constraints must also be checked.

The usefulness of the RAAP program was illustrated in [32] using two data-rate pairs. Parameters of these examples are given in Table 2.

Table 2   Results and statistics from application of the RAAP program [32].
Application	High-speed image/data transfer	Medium-speed data transfer
Data-rate pair (kb/s)   (Traffic intensity per number of channels)	768/64	256/64
Average no. of requests	35	30
Average total requests	65	65
Minimum total requests	55	55
Maximum total requests	75	75
Duration (minutes)	15 90	30 150
Start time	50%     8 a.m.–2 p.m.	All day
	25%     12–8 p.m.
	25%     2–12 p.m.
Average arrival rate   (requests per minute)	–49.44	84.58
Average holding time for a channel   (minutes)	0.04381	0.02084
Average service delay (minutes)
Booked	0.2	0.3
Immediate	0.3	0.8
Average blocking probability (%)
Initial	2.1	3.9
Ultimate	1.3	2.8

Note that an initial block occurs whenever a request is not granted with its original values (start time, duration, data), while an ultimate block occurs whenever a request does not receive service of any kind.

•   Hierarchical (multilevel) control method
This section addresses a bandwidth allocation problem in the access area to a TDM network carrying two basic traffic types, circuit-switched and packet-switched. Each user is assigned a portion of the total bandwidth (slots per frame), and this portion is dynamically allocated to the two traffic types at the user premises, using a two-layer hierarchical optimization scheme [31, 35, 36].

Consider a TDM multiplexor that carries the traffic of M user sites on a link with total capacity of C_T slots per frame. Suppose each user i has the two traffic types, circuit switching with an average call arrival rate of ₁⁽ⁱ⁾ calls per second and an average holding time of 1/µ⁽ⁱ⁾ second, and packet-switching traffic with an arrival rate of ₂⁽ⁱ⁾ packets per second, with a fixed packet length of one slot.

Using a discrete time model with frame duration of b seconds, the following formula must hold:

M	(1(i)/µ(i) + 1(i)b) < CT.	(19)
i=1

The hierarchical control has a decision-making structure (Figure 13) comprising the following:

• One central decision maker, which assigns each user i a capacity of c_tk⁽ⁱ⁾ slots per frame at decision instants t_k, k = 0, 1, · · · . This assignment lasts over the frames t_k, t_k + 1, · · · , t_k+1 – 1.
• M local decision makers, which, at the same instant, choose a parameter _tk⁽ⁱ⁾ which influences the local admission control rules that each decision maker exerts at the beginning of each frame on the incoming call requests for circuit-switched traffic.

Figure 13

At any time, if a new frame t arrives from any user i, it is either accepted (by the local decision maker) with probability B_t⁽ⁱ⁾, or blocked with probability 1 – B_t⁽ⁱ⁾. If r_t⁽ⁱ⁾ is the number of calls requiring continuation of service in the next frame, then

Bt(i) =		1 –		3(rt(i))2	–	2(rt(i))3		tk(i)	if ctk(i) > rt(i) + 1;	(20)
				(ctk(i) – 1)2		(ctk(i) – 1)3
		0							otherwise,

where t = t_k, t_k + 1, · · · , t_k+1 – 1; B_t⁽ⁱ⁾ is continuously differentiable; and 0 B_t⁽ⁱ⁾ 1.

For every c_tk⁽ⁱ⁾ > 0, _tk⁽ⁱ⁾ > 0 is the parameter to be chosen by the local decision maker at time t_k. From Equation (20), we conclude that as _tk⁽ⁱ⁾ increases, B_t⁽ⁱ⁾ increases (as _tk⁽ⁱ⁾ , B_t⁽ⁱ⁾ 1).

If each process r_t⁽ⁱ⁾, i = 1, 2, · · · , M, is a Markov chain with transition probability, then

pjk(i) = P(rt+1(i) = k|rt(i) = j) =		µ(i)bj	k = j – 1;	(21)
		1 – µ(i)bj – 1(i)bßt(i)	k = j;
		1(i)bßt(i)	k = j + 1;
		0	otherwise,

where P_tk⁽ⁱ⁾ is the transition probability matrix of r_t⁽ⁱ⁾, t (t_k, t_k+1 – 1). Hence, we can define the following parametric optimization problem.

At the beginning of each new period (t_k, t_k+1 – 1), k = 0, 1, · · · , on the basis of the knowledge of all prior information and of r_tk⁽ⁱ⁾, i = 1, 2, · · · , M, and also with the following constraints:

M	ctk(i) = CT	k = 0, 1, · · · ,	(22)
i=1

ctk(i) rtk(i)	i = 1, · · · , M,	(23)
	k = 0, 1, · · · ,

tk(i) > 0	i = 1, · · · , M,	(24)
	k = 0, 1, · · · ,

find capacity vector c_tk col[c_tk⁽¹⁾, c_tk⁽²⁾, · · · , c_tk^(M)) and parameter vector _tk col[_tk⁽¹⁾, _tk⁽²⁾, · · · , _tk^(M)), which minimize

tk(Xtk; ctk, tk) =	M	tk(i)(xtk(i); ctk(i), tk(i)),	(25)
	i=1

where

tk(i)(xtk(i); ctk(i), tk(i)) =	tk+1–1		CT	[(1 – ß(i)(s))1(i)b] • t(i)(s)
	t=tk		s=0

+ (i)

tk+1–1

max

0;

Ltk(i)

+ 2(i)b –

CT

(ctk(i) – s) • t(i)(s)

,

(26)

G

t=tk

s=0

• ⁽ⁱ⁾ is a weighting coefficient,
• L_tk⁽ⁱ⁾ is the number of packets in the packet queue of user i at time t_k,
• X_tk col[x_tk⁽¹⁾, x_tk⁽²⁾, · · · , x_tk^(M)];     x_tk⁽ⁱ⁾ col[r_tk⁽ⁱ⁾, L_tk⁽ⁱ⁾],
• ß⁽ⁱ⁾(s) ß_t⁽ⁱ⁾ for r_t⁽ⁱ⁾ = s,
• G t_k+1 – t_k (control horizon in frames),
• _t⁽ⁱ⁾(s) = Pr{r_t⁽ⁱ⁾ = s},
• _t⁽ⁱ⁾ = [_t⁽ⁱ⁾(0), _t⁽ⁱ⁾(1), · · · , _t⁽ⁱ⁾(C_T)]^T, and
• <