# Two-Dimensional Convolution Algorithm for Modelling Multiservice Networks with Overflow Traffic

Authors: Mariusz Głąbowski; Adam Kaliszan; Maciej Stasiak
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

The present paper proposes a new method for analytical modelling multiservice networks with implemented traffic overflow mechanisms. The basis for the proposed method is a special two-dimensional convolution algorithm that enables determination of the occupancy distribution and the blocking probability in network systems in which traffic streams of individual classes can be serviced by both primary and alternative resources. The algorithm worked out by the authors makes it possible to model systems with any type of traffic offered to primary resources. In order to estimate the accuracy of the proposed method, the analytical results of blocking probabilities in selected networks with traffic overflow have been compared with simulation data.


---

## Body

## 1. Introduction

The basic structure of telecommunications networks is the hierarchical topology (a.k.a. tree topology). The application of the hierarchical topology is followed by a reduction in financial outlays in constructing networks and makes the effective management of their resources possible. Initially, networks with hierarchical structures were public switched telephone networks (PSTN) [1], based on the application of the circuit switching technology. In the 1950s, the hierarchical structure applied to the PSTN network made it possible to introduce a strategy for diverting traffic via alternative routes [2–5]. To achieve that, the following types of resources were distinguished in the hierarchical structure of a network (defined in systems with circuit switching as link groups): (i)
direct group: a group of links defined directly between end nodes, that is, ingress and egress nodes,(ii)
transit group: a group of links between the end node and a transit node or between transit nodes,(iii)
basic group: a transit group that connects any switching node with its superordinate or subordinate node, or one that leads between nodes of the highest hierarchy.The assumption was at the time that both direct groups and transit groups could be high-usage groups or groups with minimal loss. Basic groups constitute the network backbone of a PSTN telecommunications network—the so-called core network. The use of these groups decreases the overall cost of the network and enables operators to extend their transmission capabilities without a simultaneous increase in the capacities of nodes and with the assumed traffic loss factor retained. Basic groups are generally groups with relatively minimal losses, whereas direct groups are in the main high-usage groups. According to the traffic management strategy for alternative routes, calls arriving at the nodes of telecommunications networks free resources in direct groups, that are primary groups, are searched. Some part of this traffic, the so-called overflow traffic, that cannot be serviced by a primary group due to its occupancy, is offered to alternative groups. Traffic that is not carried by this group is rejected traffic.The above-discussed method for traffic management via alternative routes was then applied to wireless networks: 2G (e.g., GSM—Global System for Mobile Communications), 3G (e.g. UMTS—Universal Mobile Telecommunication System) and 4G networks (e.g., LTE—Long Term Evolution LTE). Overflow traffic in wireless networks was applied within the framework of the same technology and between networks operating in different technologies (e.g. GSM, UMTS, and LTE) [6–8].In present-day market place, the growing variety of different access technologies—both wireless and wired networks—is accompanied by a concurrent unification with regard to network layer protocols: the standard for the network layer is the IP protocol (v4, v6). At the same time, the increasing number of network service has eventually led to a necessity to ensure predefined quality of service (QoS) parameters demanded by traffic sources in a network. Defined quality of service parameters in networks with packet switching is guaranteed following creation of virtual channels (with dedicated or shared resources) that transmit packet streams related to a given class (or classes) of service, which leads to a connection-oriented packet-switching architecture communications. The allocation of packet streams to given classes of services is executed (in edge routers) as a result of an appropriate determination of the field of the type (class) of service in the IP header. This identification field can then be used as a DSCP (Differentiated Services Code Point) code point in packet marking in the case of the DiffServ (Differentiated Services) architecture. In the case of the MPLS technology (MultiProtocol Label Switching), the most widely used by operators in backbone networks, the field determining the type of class is mapped into a value of a corresponding label that unequivocally determines the path in the network and/or the EXP (experimental) parameter used for distinguishing quality parameters for packet streams transmitted over the same path. The parameters that can be used for a classification of packet streams are, for example, the interface of the edge router (ingress router), the address of the destination network, and the relationship of the source of traffic stream with a given VPN network (virtual private networks) of the second or the third layer [9–11].From the traffic engineering perspective, the resources (virtual channels, MPLS paths) that are used to service individual packet streams (traffic) can be treated as theprimary resources. At the same time, in order to optimize the resources of a network and to secure the demanded quality of service, prevent the network from being overloaded, as well as for network survivability, additional resources (such as additional MPLS paths, additional resources within MPLS path) can be introduced to the connection-oriented packet networks in which packets lost as a result of the service in dedicated primary resources would be transmitted. Such an additional resource (virtual channel, MPLS path) that services blocked traffic in the primary resources can be treated as the alternative resources that service overflow traffic.The major difficulty that occurs during an analysis of systems with traffic overflow is to determine the demanded volume of alternative resources (with low losses). If we assume that a given distribution of time between calls (a call in packet networks can be interpreted as a session, e.g., TCP or UDP session) is offered to the primary resources (e.g., exponential distribution), then traffic that overflows from these resources will be of a different nature [12], because calls from an overflow stream can appear only during the total occupancy of the primary resources. This means that an overflow stream is more “concentrated/dense” within certain time intervals, that is, having a dynamic and “peak” nature as compared to traffic offered to primary resources. If we assume identical value of offered traffic and identical value of the blocking probability, then to execute service for overflow traffic, a greater number of resources is required than that for the service of traffic offered to the primary resources.In traffic engineering, in works devoted to modelling of systems with traffic overflow, it has been usually assumed that the call stream offered to primary resources is consistent with the Poisson distribution or with binomial distribution [8, 12–19]. The variety of network services to be observed in modern-day networks results, however, in a situation where the previously adopted assumptions do not describe call streams generated in packet networks precisely enough. To make an analytical modelling of the network with any distribution of call streams offered to primary resources possible, this paper proposes a new method for modelling multiservice packet networks with implemented traffic overflow mechanisms. The basis of the proposed method is a special two dimensional convolution algorithm. The worked-out method allows researchers to determine the occupancy distribution and the blocking/loss probability in networks with both primary and alternative resources.The further part of the paper is organized as follows. Section2 presents an overview of research studies in modelling multiservice networks with traffic overflow. Section 3 proposes a new model of the overflow system with multirate traffic. In Section 4, the results of the analytical calculations are compared with the results of the simulation. Section 5 sums up the paper’s main conclusions.


## 2. Related Works

In traffic theory both single-service systems [12, 14, 16] and multiservice systems [17, 20] have been considered. In the case of single-service systems, all calls that are serviced by a telecommunications system always demand the same amount of resources. In the case of multiservice systems, in which multirate models are used for modelling, offered traffic is a mixture of different classes of calls, each demanding an integer multiplicity of a certain unit of the resources, called basic bandwidth unit (BBU) [21–28]. In the case of constant bit rate sources, resources are expressed in bit rates of original traffic streams. In the case of variable bit rate sources prior the BBU determination, the so-called equivalent bandwidth [27] for particular traffic packet streams is calculated (Methods for determination of equivalent bandwidth depend on such parameters such as admissible packet loss rate, admissible latency, link capacity, the average and the maximum value of bit rate, the nature of packet streams (e.g., self-similar streams), and the type of the network. Algorithms for determination of the equivalent bandwidth for defined types of the network and services are proposed, for example, in [27, 29–36].)For single-rate traffic, two basic methods for determination of blocking probabilities in alternative groups (groups to which traffic overflows from other groups) have been worked-out: the equivalent random technique (ERT) method [12, 14] and the Fredericks-Hayward method [16]. The latter method has become the basis for a generalization for multirate overflow traffic [17]. In this method [17], probabilities of subsequent states were determined in a recurrent way using the generalization of Kaufman-Roberts formula [37, 38].A different technique for modelling networks with traffic overflow is proposed in [39]. The basis for the method proposed in [39] is the Erlang’s Ideal Grading model with multirate traffic [40, 41]. The objective of the proposed method is to simplify the process of the determination of the occupancy distribution in systems with traffic overflow as it does not require calculations for the parameters of overflow traffic. Its accuracy is comparable to the accuracy of the method [17]. The basic limitation of this method is that only one class of calls is offered to each of the primary resources.In calculations of multiservice systems with traffic overflow, the so-called convolution algorithms [20, 22, 42, 43] can also be used. The advantage of these algorithms is that they offer a possibility to model systems with any streams of offered traffic. References [22, 42, 43] propose convolution models of systems with reservation. In [44], the authors of the paper describe, for the first time, the problem of modelling systems with overflow traffic with the application of the convolution mechanism. The presented method is characterized by high accuracy, though the scope of its application is limited to systems in which each of the primary resources services directly calls of only one traffic class. This paper proposes, using the concept idea presented in [44], a new, generalized method that makes it possible to determine characteristics of multiservice systems with traffic overflow in which each primary group is offered a number of traffic streams. To improve the order of computational complexity of the new method, the simultaneous convolution operation (proposed in [44]) has been replaced by a two-dimensional convolution operation worked-out for the purposes of this paper (Section 3).


## 3. Modelling of Multiservice Systems with Traffic Overflow

### 3.1. Basic Assumptions

In order to present the basic assumptions of the proposed method for modelling systems with overflow traffic, let us consider an overflow system that consists ofk primary groups that belong to the set K and one alternative group (Figure 1). Each primary group j (j∈K) is offered traffic classes m1(j),m2(j),…,mmj(j) from the set M{j} with cardinality m{j}. Traffic of class mi(j), the calls of which demand ti(j) BBUs, is offered to the primary group j. Let M denote a set of all offered classes:
(1)M={M{1},M{2},…,M{k}}={m1(1),m2(1),…,mm{1}(1),m1(2),…,mm(2)(2),…,m1(k),…,mm{k}(k)}.
A primary group with the capacity Vj services traffic streams with the intensity A1(j),A2(j),…,Am{j}(j). Discarded traffic that is not serviced in these groups forms an overflow traffic stream. This traffic is then offered to the alternative group with the capacity V0. Hence, calls of classes of the set M{j} can occupy at the maximum d{j} BBUs in the system:
(2)d{j}=V0+Vj.
The calls of class mi(j) can occupy at the maximum di{j} BBUs in the system:
(3)di{j}=⌊Vjti(j)⌋ti(j)+⌊V0ti(j)⌋ti(j).
The total capacity of the system is
(4)V=V0+∑j=1k‍Vj.Figure 1
Structure of an overflow system.


### 3.2.  Occupancy Distribution

Firstly, let us consider the occupancy distribution[P]d{j}M{j}={[P0]d{j}M{j},[P1]d{j}M{j},…,[Pn]d{j}M{j},…,[Pd{j}]d{j}M{j}} in the basic subsystem of the considered overflow system presented in Figure 1, that is, a system with one primary group j and one alternative group for calls of classes of the set M{j}. A single nth element of the distribution [P]d{j}M{j}, that is, [Pn]d{j}M{j}, denotes the probability of n busy BBUs. The maximum number of BBUs that can be occupied in such a system is d{j} (equation (2)).By expanding our analysis of the system into a subsystem that is composed of two primary groups “j” and “j+1”, we can determine the occupancy distribution for two sets of service classes M{j} and M{j+1}. The single element [Pn]d{j,j+1}M{j,j+1} of the occupancy distribution in the system with two primary groups j and j+1 can be obtained by a convolution operation of distributions [P]d{j}M{j} and [P]d{j+1}M{j+1}:
(5)[Pn]d{j,j+1}M{j,j+1}=k·∑l=0n‍[Pl]d{j}M{j}[Pn-l]d{j+1}M{j+1},
where d{j} and d{j+1} are determined by (2), in which d{j,j+1} determines a new length of the distribution equal to
(6)d{j,j+1}=Vj+Vj+1+V0.
The parameter k in (5) is the normalization coefficient. Notice that according to the convolution operation defined by (5), the distribution [P]d{j,j+1}M{j,j+1} is shortened to the length d{j,j+1} that is lower than d{j}+d{j+1}. After shortening of the distribution, it is necessary then to normalize it. The normalization coefficient k ensures the sum of all elements of the distribution to be equal to one:
(7)k=1∑n=0d{j,j+1}∑l=0n[Pl]d{j}M{j}[Pn-l]d{j+1}M{j+1}.Let us notice that the expression (5) does not precisely reflect the operation of the overflow system since the convolution operation does not take into consideration states that appear as a result of the termination of a service of certain calls. States that occur directly after the termination of the service of a call in the primary group, in instances where all BBUs of the primary group and some (or all) BBUs of the alternative group were busy before the termination of this service, are not taken into consideration properly. To present this phenomenon, let us consider a simple example of an overflow system that is composed of three primary groups 1, 2, and 3 with the capacities V1=4, V2=4, and V3=4 BBUs. Each group is offered one traffic class with demands equal to 1 BBU. Traffic coming from the three groups overflows to alternative group with the capacity V0=4 BBUs. The total capacity of this system is then equal to 16 BBUs. Let us consider now the combination (4,8,0). The adopted notation is such that calls of the first class, offered to the first group, occupy 4 BBUs and calls of the second class, offered to the second group, occupy 8 BBUs, whereas no call that was offered to the third group is currently being serviced. The combination (4,8,0) is feasible because calls of the first class m1(1) occupy the entire primary group 1 (4 BBUs). Then, calls of class m2(2) can occupy 8 BBUs (entire primary group 2 (4 BBUs) and the whole alternative group (4 BBUs)) because calls of class m3(3) are not serviced at all. The considered combination is shown in Figure 2(a).Occupancy of resources in the overflow system with calls’ transfer.
(a)
combination(4,8,0)
(b)
combination(4,7,0) before the transfer of the call
(c)
combination(4,7,0) after the transfer of the callNote that the method for determination of the occupancy distribution in the system with traffic overflow presented in [44] assumes that after termination of each of the calls serviced in the primary group, calls are transferred from the alternative group to the appropriate primary group provided that the latter has free resources. This means that after a disconnection of a call of class 2 in the primary group 2 in the considered state (4,8,0), the system transits to state (4,7,0) (Figure 2(b)) in which immediately a transfer of the serviced connection of class 2 in the alternative group to the primary group is executed (Figure 2(c)). Consequently, the combination (4,7,0) means the occupancy of 4 BBUs by calls of class 1 in the primary group 1 and 7 BBUs by calls of class 2; while all 4 BBUs are busy in the primary group, 2 and 3 BBUs are busy in the alternative group. Hence, the convolution (5) determines the occupancy distribution in the overflow system that includes a transfer of connections from alternative group to primary group.Subsequently, let us try to determine, for the considered exemplary system, the aggregated distribution for the case when the system simultaneously services calls that are offered to all of the three primary groups. This distribution cannot be determined in a direct way since not all of the combinations included and taken into consideration in the distribution (5) are allowable. Consider an exemplary combination (2,8,5) in which calls offered to primary group 1 occupy 2 BBUs, calls offered to primary group 2 occupy 8 BBUs, and calls offered to primary group 3 occupy 5 BBUs. In total, there are 15 BBUs occupied for such a combination, less than the total capacity of the system V=16. Note, however, that according to the combination under consideration calls offered initially to primary group 2 occupy 4 BBUs in the alternative group, whereas calls offered initially to primary group 3 occupy 1 BBU. This means that calls offered initially to primary group 2 and 3 “occupy” more resources of the alternative group than the number of resources available in the group. Therefore, while determining probabilities for each of the states, it is necessary to omit those combinations that lead to an occupancy state in the alternative group higher than its capacity.The method that assumes call transfers between the alternative and the primary group and eliminates all forbidden states in which the number of busy BBUs in the alternative group exceeds the capacity of this group, the so-called simultaneous convolution operation of many distributions, is proposed in [44]. The method is characterized by high accuracy, while its limitation involves the assumption of only one call class that is offered to each of the primary groups. In Section 3.3, a new method will be proposed. The method is based on the so-called two-dimensional convolution operation that, due to a lower order of complexity, can make it possible to model more effectively systems with overflow traffic in which the primary group services single classes of calls. This will be followed by a presentation of two generalized methods (continuous method—Section 3.5.1—and discrete method—Section 3.5.2) that enable modelling systems in which each primary group can be offered many classes of calls.


### 3.3.  Two-Dimensional Distribution

Let state(y,n) denote a state in which there are y  occupied resources of the alternative group, with the total occupancy of the system equal to n. The two-dimensional occupancy distribution in this system will be denoted by the symbol [R]V0,V. In this distribution a single element [Ry,n]V0,V determines the state probability (y,n).According to the adopted notation in the paper, the first dimension determines the occupancy state of the alternative group, whereas the second dimension determines the occupancy state of the whole system. To justify such an approach let us consider an exemplary relation between the one-dimensional distribution[P]VM{j} and the two-dimensional distribution [R]V0,VM{j}. Both distributions describe state probabilities for the system with traffic overflow that is composed of the primary group j with the capacity Vj and the alternative group with the capacity V0. The primary group j is offered calls from the set M{j}. The relations between the elements of both distributions can be written in the following way:
(8)[Pn]VM{j}=∑y=0V0‍[Ry,n]V0,VM{j}.
Figure 3 shows the interpretation of (8) for the system composed of the primary group with the number 1, with the capacity V1=4 and the alternative group with the capacity V0=4. The primary group is offered calls from the set M{1}. The figure shows only those states—(y,n)—of the distribution [R]V0,VM{1} that are permitted by the system. Thus, the states in which a larger amount of resources of the alternative group than the capacity of this group would be occupied (y>V0), as well as the states in which more resources of the alternative group than the total amount of occupied resources would be occupied (y>n), are omitted.Figure 3
The relation between the one-dimensional and the two-dimensional distribution for a system with traffic overflow.


### 3.4. Modelling of Systems in Which the Primary Group Is Offered a Single Class of Calls

Let us recall that the method proposed in [44] is limited to the instances of modelling of systems in which the primary group is offered only one class of calls. The method [44] can be optimized effectively with the application of the two-dimensional distribution presented in the further part of this subsection. The input data that enable the determination of the two-dimensional distribution are then the occupancy distributions of the so-called subsystems. A subsystem is composed of a set of a certain number of primary groups and an alternative group. In this paper, the basic subsystem j will be a system that is composed of the primary group j and an alternative group. In our further considerations, the assumption that the system with traffic overflow is approximated by a system with calls transfer still holds good.


#### 3.4.1. Determination of the Two-Dimensional Occupancy Distribution of the Basic Subsystem

Using the two-dimensional distribution[R]V0,d{j}M{j}, it is possible to describe the characteristics of the occupancy for the basic subsystem j. A single element [Ry,n]V0,d{j}M{j} of this distribution determines the occupancy probability of y BBUs in the alternative group and n BBUs in the whole system by calls of the classes from the set M{j}. In the case of the basic subsystem j the set M{j} is a one-element set. To improve the readability of the notation, we adopt that the symbols [p] and [r] will always denote occupancy distributions for one class of calls exclusively.In the basic subsystemj, which is offered one call of class i, the distribution [r]V0,d{j}{mi(j)} is the equivalent of the distribution [R]V0,d{j}M{j}. In a similar way, the distribution [p]d{j}{mi(j)} is the equivalent of the distribution [P]d{j}M{j}. A single element [ry,n]V0,d{j}{mi(j)} of the two-dimensional distribution can be determined on the basis of a single element of the one-dimensional distribution [p]d{j}{mi(j)} for the group with the capacity d{j}. For this purpose, we adopt that for the occupancy states n>Vj, where n denotes the total number of busy (occupied) resources, the relation y=n-⌊Vj/ti(j)⌋ti(j) is fulfilled. The parameter y denotes the number of busy resources of the alternative group. The adopted assumption is fulfilled for the systems with calls’ transfer and allows for the occurrence of a state in which the resources of the alternative group are busy, while part of the resources of the primary group has not been entirely used. Unused resources of the primary group result from the necessity of servicing a single call requiring ti(j) within one group.Thus according to adopted assumptions, the relation between the expressions of both distributions (one-dimensional and two-dimensional) can then be written in the following way:(9)[ry,n]V0,d{j}{mi(j)}={[pn]d{j}{mi(j)}for(y=0)∧(n⩽⌊Vjti(j)⌋ti(j)),[pn]d{j}{mi(j)}for(y=n-⌊Vjti(j)⌋ti(j))∧(⌊Vjti(j)⌋ti(j)<n⩽d{j}),0inremainingcases.Following the assumption for transferring the calls, it is possible to determine in an easy way the two-dimensional distribution[R]V0,d{j}{Mi{j}} of the occupancy in the basic system to which one class of calls is offered. The following subsection will present a description of the method for a determination of the two-dimensional occupancy distribution for multiservice systems with traffic overflow. The method (Section 3.4.2) is universal and does not depend on the number of traffic classes offered to basic subsystems. The distributions determined in the following subsection will provide a starting point for the algorithms for modelling systems in which many classes of calls are offered to the primary group.


#### 3.4.2.  Two-Dimensional Convolution Operation

Consider now a method for a determination of the two-dimensional occupancy distribution[R]V0,VM for a multiservice system with traffic overflow. Each expression [Ry,n]V0,VM of this distribution determines the occupancy probability y BBU of the alternative group and n BBU of all groups (including the alternative group). The two-dimensional convolution operation makes it possible to effectively determine the distribution [R]V0,VM for the whole system with traffic overflow on the basis of the occupancy distributions [R]V0,d{j}M{j} of basic subsystems j with traffic overflow. The distribution [R]V0,d{j}M{j} can be a distribution for a subsystem in which the group j is offered one class of calls (its determination is described in Section 3.4.1) or a subsystem in which the primary group is offered a number of call classes (two different methods for a determination of these distributions are presented in Section 3.5.1 and Section 3.5.2, resp.).In order to determine the occupancy distribution for a system composed of primary groups that belong to the setK, all distributions [R]V0,d{j}M{j} (j∈K) are to be aggregated. The distribution [Ry,n]V0,d{1,…,j}M{1,…,j}, which determines state probabilities for a subsystem composed of primary groups 1,…,j and the alternative group, is determined on the basis of the convolution operation formulated as follows:
(10)[Ry,n]V0,d{1,…,j}M{1,…,j}=k∑ly=0y‍∑ln=0n‍[Rly,ln]V0,d{1,…,j-1}M{1,…,j-1}[Ry-ly,n-ln]V0,d{j}M{j},
for y⩽V0 and y⩽n. The symbol k in formula (10) is the normalization coefficient that is determined as follows:
(11)k∑y=0V0‍∑n=0V‍∑ly=0y‍∑ln=0n‍[Rly,ln]V0,d{1,…,j-1}M{1,…,j-1}[Ry-ly,n-ln]V0,d{j}M{j}=1.Let us interpret (10) with the example of a system that is composed of 3 primary groups with the capacity 4 BBUs each and an alternative group with the capacity 4 BBU. We will be considering combinations (y,n) of an overflow system composed of three primary groups and one alternative group with the following capacities: V1=V2=V3=V0=4. Let us consider then a combination ((0,2);(4,8);(1,5)) for the respective 3 subsystems. The considered combination describes a state in which calls of the classes from the set M{1} occupy 2 BBUs in a primary group and do not occupy resources in the alternative group of the subsystem. Calls of the classes from the set M{2} occupy 4 BBUs in the primary group and 4 BBUs in the alternative group of the subsystem, whereas calls of the classes from the set M{3} occupy 4 BBUs in the primary group and 1 BBU in the alternative group of the subsystem. Thus, the total number of busy BBUs in the alternative group is equal to 5, which means that this combination is not applicable. Let us analyse now a method for determination of the probability of an occurrence of such a combination using the two-dimensional convolution operation.Note that after the classes from the setM{1} and the classes from the set M{2} are aggregated, the probabilities of the occurrence of the state combination ((0,2);(4,8)) will be added up to the probability of the permitted state [R4,10]d{1,2}M{1,2}. While proceeding with further aggregation of the distribution of the classes from the set M{1,2} with the distribution of the classes from the set M{3}, the probability of occurrence of the state combination ((4,10);(1,5)) should be added to the state probability [R5,15]d{1,2,3}M{1,2,3}. This state, however, is not a permitted state in view of the convolution operation determined in (10), which allows us to eliminate properly nonpermitted states in the process of the determination of the two-dimensional distribution for the system with traffic overflow.Note that the convolution operation increases the length of the distribution in the dimension that determines the total number of busy BBUs, while the dimension that defines the capacity of the alternative group remains without any changes.The introduced notation, in which one dimension determines the occupancy of the alternative group while the other determines the occupancy of primary groups and the alternative group, makes it possible to directly convolute two-dimensional distributions. The order of complexity of a single convolution operation of two-dimensional distributions is equal toΘ(V02V2), whereas the order of computational complexity of the algorithm for k primary groups is Θ(kV02V2), which is a major advantage over the method discussed in [44], where the order of complexity is Θ(Vk).


#### 3.4.3.  Blocking Probability

On the basis of the convolution operation (10) it is possible to determine the aggregated occupancy distributions [R]M∖{M{j}} for all groups except the group j:
(12)[R]V0,V-VjM∖M{j}=[R]d{1}M{1}*⋯*[R]d{j-1}M{j-1}*[R]d{j+1}M{j+1}*⋯*[R]d{k}M{k}.
Distribution (12) will allow us to work out a method for determination of the blocking probability for calls of traffic classes offered to group j, when the alternative group is offered overflow traffic from all primary groups.For this purpose, let us consider now the feasible combinations of the distributions[R]V0,V-VjM∖{M{j}} and [R]V0,d{j}{M{j}}. Let the set Ψ(j) be a set of all permitted occupancy combinations for the basic subsystem j with a subsystem that is composed of primary groups that belong to the set {1,2,…,j-1,j+1,…,k}. Let us define the possible combinations ((n-ln,y-ly);(n,y)) of the occupancy of the basic subsystem j with the subsystem that is composed of the remaining primary groups and the alternative group:
(13)Ψ(j)={(ln⩽min(n,d{j}))∧(ly⩽min(y,ln))∧(ln⩽min(n,d{j}))∧(ly⩽min(y,ln))(n,y,ln,ly):(n⩽V)∧(y⩽min(n,V0))∧(ln⩽min(n,d{j}))∧(ly⩽min(y,ln))}.
The condition n⩽V is self-explanatory since the total number of BBUs serviced in the system cannot exceed the capacity of the system. The condition y⩽min(n,V0) in formula (13) means that the number of all busy BBUs in the alternative group will always be equal to V0 or n at the maximum, if n<V0. The condition ln⩽min(n,d{j}) means that the total number of busy BBUs occupied by calls offered to the group j cannot be higher than the availability d{j} of the basic subsystem j or than the total number of n busy BBUs in the system (if n<d{j}). The condition ly⩽min(y,ln), in turn, expresses the fact the number of busy BBUs in the alternative group occupied by calls that overflow from the group j will never be higher than the total number ln of the resources that occupy calls offered to the group j or than the total number y of occupied resources of the alternative group, if y<ln.In the same way we will define the setΨi(j) that is a subset of the set Ψ(j) and that determines the blocking state for the class mi(j). The basis for the determination of this set is the lack of ti(j) free BBUs in both the alternative and the primary group j. Therefore we get
(14)Ψi(j)={∧(ln-ly>Vj-ti(j))(n,y,ln,ly)∈Ψ(j):(y>V0-ti(j))∧(ln-ly>Vj-ti(j))}.The probabilityP(n,y,ln,ly) of the combination from the set Ψ(j), in which calls of all classes occupy n BBUs in the primary groups and in the alternative group, while calls of the classes from the set M{j} occupy ln BBUs in the primary group j and the alternative group (ly BBUs in the alternative group), can be determined on the basis of the distributions [R]V0,V-VjM∖{M{j}} and [R]d{j}M{j}:
(15)P(n,y,ln,ly)=k[Rly,ln]V0,d{j}M{j}[Ry-ly,n-ln]V0,V-VjM∖M{j},
where k is the normalization coefficient equal to
(16)k=1∑Ψ(j)[Rly,ln]V0,d{j}M{j}[Ry-ly,n-ln]V0,V-VjM∖M{j}.
The blocking probability Ei(j) for the class mi(j) can be determined on the basis of the sum of the probabilities P(n,y,ln,ly) of blocking combinations from the set Ψi(j):
(17)Ei(j)=∑Ψi(j)‍P(n,y,ln,ly).


#### 3.4.4. Algorithm for Modelling Systems with Overflow for Primary Groups with Single Classes of Calls

The algorithm that allows us to determine the blocking probability in networks with traffic overflow in which each primary group is offered a single class of calls can be written in the form of the following four stages:(1)
determination of the one-dimensional distribution[p]d{j}{mi(j)} for a single class mi(j) offered to the primary group j on the basis of models worked-out for single-service systems,(2)
determination of two-dimensional distributions[r]V0,d{j}mi(j) for all primary groups on the basis of one-dimensional distributions [p]d{j}mi(j) (formula (9)),(3)
determination, for every primary groupj, of aggregated distributions [R]V0,V-VjM∖M{j} of all primary groups except group j (formula (12)),(4)
determination of the blocking probability (formula (17)) for each traffic class mi(j) offered to each primary group j.


### 3.5.  Modelling of Systems in Which the Primary Group Is Offered a Number of Call Classes

#### 3.5.1.  Continuous Method

Consider now an overflow system in which primary groups are offered many classes of calls (multiple classes of calls). According to the adopted notation, the primary groupj is offered call classes from the set M{j}. In the first proposed method, that is, the continuous method, we adopt the assumption that a single call can be serviced simultaneously by the resources of the primary as well as the alternative group. The occupancy distribution in the considered basic subsystem is determined on the basis of a modified convolution operation of two-dimensional distributions.Consider a system in which the primary groupj has the capacity Vj. Traffic from this group overflows to the alternative group with the capacity V0. Assume that the sets A and B are separable subsets of the set M{j}. The primary group j is offered mixtures of call classes that belong to the sets A and B for which the distributions [R]V0,d{j}A and [R]V0,d{j}B have been determined.For any groupj in the overflow system with the assumed calls’ transfer, the two-dimensional convolution operation makes it possible to determine the elements [Ry,n]V0,d{j}A∪B of the distribution [R]V0,d{j}A∪B on the basis of the summation of probabilities (combinations) of states ((yA,nA);(yB,nB)) that satisfy the following condition:
(18)nA-yA+nB-yB⩽Vj.
Condition (18) determines all combinations for states ((yA,nA);(yB,nB)) whose probabilities can be added up to the probability of the aggregated state (y,n). For the states that satisfy the condition (18), the following relations then ensue:
(19)n=nA+nB,(20)y=yA+yB.Let us determine now for the state(y,n) a set αBA(y,n) of all state combinations ((yA,nA);(yB,nB)) for which the condition (18) is fulfilled, that is, for which the value of deficit z (described in the next paragraph) is equal to 0:
(21)αBA(y,n)={((yA,nA);(yB,nB)):(n=nA+nB)∧(y=yA+yB)∧(nA-yA+nB-yB⩽Vj)∧(y⩽V0)}.The system also offers such combinations of states((yA,nA);(yB,nB)) that do not satisfy the condition (18). These combinations will be permitted in the system when part of the serviced calls is transferred to the alternative group. Then, the relation (19) that determines the total occupancy in the system is still retained, while the relation (20) is not satisfied because the occupancy of the alternative group changes. The failure of the relation (20) results from the so-called deficit z in the resources of the primary group. This deficit can be determined in the following way:
(22)z=nA-yA+nB-yB-Vj.
The interpretation of the deficit of the primary resources is shown in Figure 4. Figure 4(a) presents the combination ((yA,nA);(yB,nB)), when the resources of the primary and the alternative groups are occupied only by calls from the set A and when the resources are occupied only by calls from the set B. Figure 4(b) shows the attempt to aggregate both combinations. It is clear to see the deficit in the resources that is to be “transferred” to the resources of the alternative group (Figure 4(c)). Note that the amount of all resources of the alternative group after the transfer of the deficit resources taken into consideration is equal to
(23)y=nA+nB-Vj.
Taking into account (19), which is always true (for z=0 and for z≠0), we can express (23) in the following form:
(24)y=n-Vj.
Now, we are in a position to define the set βBA(y,n) of all permitted combinations ((yA,nA); (yB,nB)) for which the deficit value z is higher than zero (the condition (18) has not been fulfilled):
(25)βBA(y,n)={∧(nA-yA+nB-yB>Vj)∧(y⩽V0)((yA,nA);(yB,nB)):(n=nA+nB)∧(y=yA+yB+z)∧(nA-yA+nB-yB>Vj)∧(y⩽V0)}.
Taking into account (22), the set (25) can be rewritten as follows:
(26)βBA(y,n)={∧(nA-yA+nB-yB>Vj)∧(y⩽V0)((yA,nA);(yB,nB)):(n=nA+nB)∧(y=nA+nB-Vj)∧(nA-yA+nB-yB>Vj)∧(y⩽V0)}.Interpretation of the parameterz defining the deficit of resources in the primary group.
(a)
Combination of occupancy states
(b)
Deficit in the resources in the primary group
(c)
Transferred deficit of resources of the alternative groupOn the basis of the setsαBA(y,n) and βBA(y,n) it is possible to determine the sum of the probabilities of all combinations for the state (y,n), that is, the probability [Ry,n]V0,d{j}A∪B for this state:
(27)[Ry,n]V0,d{j}A∪B=k∑αBA(y,n)∪βBA(y,n)‍[RyA,nA]V0,d{j}A[RyB,nB]V0,d{j}B.Equation (27) can be rewritten in the following way:
(28)[Ry,n]V0,d{j}A∪B=k{∑nA=0n‍∑yA=0y‍[RyA,nA]V0,d{j}A[Ry-yB,nB]V0,d{j}Bfory>n-Vj,∑nA=0n‍∑z=0n-Vj‍∑yA=0y-z‍[RyA,nA]V0,d{j}A[Ry-yA-z,nB]V0,d{j}Bfory=n-Vj,0fory<n-Vj.
The transformation of (27) into (28) is presented in Appendix A. Using (28) we are in a position to aggregate subsequent distributions in the primary group. It is thus a convenient notation for a construction of the computational algorithm.


#### 3.5.2.  Discrete Method

The method for determination of the occupancy distribution in the basic subsystem with multiple call classes, that is, a system that is composed of the primary group and the alternative group presented in Section3.5.1, adopts the assumption that the transfer of calls results in a total exploitation of the primary group. Such an approach assumes a possibility of simultaneous occupation of the resources of the primary and the alternative group by one call in the stage of the aggregation of classes within the basic subsystem and, in consequence, leads to inaccurate and imprecise determination of the deficit in resources.Let us consider now a modified method for determination of the two-dimensional occupancy distribution[R]V0,d{j}A∪B for the basic subsystem on the basis of the occupancy distributions [R]V0,d{j}A and [R]V0,d{j}B in which a possibility of a simultaneous servicing of calls by the resources of the primary and the alternative groups is excluded. Note that, on the basis of the given combination ((yA,nA);(yB,nB)), it is not possible to unequivocally determine the history of call acceptance and call service. It is not possible then to determine the amount s of resources of the primary group that cannot be used due to the lack of the possibility of a division of the serviced call between the primary group and the alternative group. The value of the parameter s depends not only on the combination itself but also on the history of call acceptance and call service.As previously mentioned, let us assume that the basic subsystemj is offered mixtures of call classes that belong to the set A and B. The sets A and B are separate subsets of the set M{j} traffic classes.The number of occupied resourcesy in the alternative group can be determined in the same way as in Section 3.5.1 but with the number s of unused resources in the primary group taken additionally into account. If the total number of occupied resources is lower than or equal to the capacity of the primary group, then there is no deficit in resources and all resources of the primary group can be used. In this situation, the condition (18) is also fulfilled. If the number of occupied resources exceeds the capacity of the primary group and the condition (18) is at the same time fulfilled, then there is no deficit in the primary group. When this is the case, the number of busy resources of the alternative group is higher by the number of unused resources of the primary group s. In the case when the condition (18) is not fulfilled, the number y of busy resources of the primary group is increased by the parameters z and s. We can thus write
(29)y={yA+yBforn⩽Vj,yA+yB+sfor(nA-yA+nB-yB⩽Vj),yA+yB+s+zfor(nA-yA+nB-yB>Vj).Consider now the way the parameters that determines the number of unused resources of the primary group is estimated. Assuming that there is a possibility of calls’ transfer, there can be at the maximum tmax(A)-1 unused BBU or tmax(B)-1 unused BBU in the primary group, depending on which call class has been admitted for service as the last one. The upper boundary for the value of the parameter s is (V-n) BBU, that is, the number of free resources in both groups (primary and alternative). Let smaxA(n) denote the maximum number of unused resources in the primary group, on condition that a call that belongs to the set A has been accepted as the last one:
(30)smaxA(n)={min(tmax(A)-1,V-n)forn>Vj,0forn⩽Vj.LetPn(s∣A) denote the probability of s BBU unused in the primary group in state n, on condition that the last accepted call was a call of the class that belongs to the set A. A determination of this probability is fairly complex. Let us assume then that the distributions P(s∣A) and P(s∣B) are approximated by the uniform distribution:
(31)Pn(s∣A)={1smaxA(n)for0⩽s⩽smaxA(n),0inothercases,Pn(s∣B)={1smaxB(n)for0⩽s⩽smaxB(n),0inothercases.LetPn(A) denote the probability that the state n has been reached when the last accepted call was a call of the class that belonged to the set A, and Pn(B) denotes the probability that the state n has been reached when the last accepted call was a call of the class that belonged to the set B. The proposed method makes the assumption that these probabilities are directly proportional to the number of resources that are occupied by calls that belong to the sets A and B:
(32)Pn(A)=nAn,Pn(B)=nBn.Let us define the convolution of the distributions[R]V0,d{j}A and [R]V0,d{j}B. To determine the state probability (y,n), let us consider the three intervals defined in (29). The first interval includes the states (y,n) for n⩽Vj. The second and the third intervals include states in which the total number of occupied resources n is higher than the capacity of the primary group Vj. Each interval includes the combinations of states denoted as ((yA,nA);(yB,nB)).Let us consider the method for determination of the probability of occurrence of the states(y,n) for n⩽Vj as the first. The probability of the occurrence of the state (y,n) is equal to the sum of the probability of occurrence for all combinations for this particular state, defined in (19) and (29):
(33)∀n⩽Vj[Ry,n]V0,d{j}A∪B=k∑nA=0n‍∑yA=0y‍[RyA,nA]V0,d{j}A[Ry-yA,n-nA]V0,d{j}B.
For the remaining two intervals defined in (29), to determine the state probability (y,n), for n>Vj, it is necessary to take into consideration additional parameters such as Pn(s∣A), Pn(s∣B) (formula (31)) and Pn(A) and Pn(B) (formula (32)). In addition, it is necessary to define the set γ of all possible combinations (yA,nA);(yB,nB) for the second interval of (29) and the set φ of all possible combinations for the third interval.Definitions of the setsγ and φ depend on the last admitted call. If the last admitted call is a call of the classes from the set A, then for the state (y,n) we denote these sets as γBA(y,n) and φBA(y,n). Similarly, if the last admitted call was a call of the class that belonged to the set B, then the sets will be denoted as γAB(y,n) and φAB(y,n). The sets γBA(y,n), φBA(y,n), γAB(y,n) and φAB(y,n) define all the possible combinations ((yA,nA);(yB,nB)) as well as the number of unused resources s for the state (y,n). In addition, the sets φBA(y,n) and φAB(y,n) define the deficit z of the resources of the primary group. As a consequence of our considerations we can write
(34)γBA(y,n)={∧(y=n-Vj+s)((yA,nA);(yB,nB),s):(n=nA+nB)∧(y=yA+yB+s)∧(0⩽s⩽smaxA(n))∧(y=n-Vj+s)},γAB(y,n)={∧(y=n-Vj+s)((yA,nA);(yB,nB),s):(n=nA+nB)∧(y=yA+yB+s)∧(0⩽s⩽smaxB(n))∧(y=n-Vj+s)},φBA(y,n)={∧(1⩽z⩽n-Vj)∧(y=n-Vj+s)((yA,nA);(yB,nB),s,z):(n=nA+nB)∧(y=yA+yB+z+s)∧(0⩽s⩽smaxA(n))∧(1⩽z⩽n-Vj)∧(y=n-Vj+s)},φAB(y,n)={∧1(⩽z⩽n-Vj)∧(y=n-Vj+s)((yA,nA);(yB,nB),s,z):(n=nA+nB)∧(y=yA+yB+z+s)∧(0⩽s⩽smaxB(n))∧(1⩽z⩽n-Vj)∧(y=n-Vj+s)}.In line with the adopted notation, the state probability(y,n) (for n>Vj) can be written as follows:
(35)∀n>Vj[Ry,n]V0,d{j}A∪B=kP(A)∑γBA(y,n)∪φBA(y,n)‍Pn(s∣A)×[RyA,nA]V0,d{j}A[RyB,nB]V0,d{j}B+kP(B)∑γAB(y,n)∪φAB(y,n)‍Pn(s∣B)×[RyA,nA]V0,d{j}A[RyB,nB]V0,d{j}B.
Equations (33) and (35) can be combined and eventually rewritten in the following form:
(36)[Ry,n]V0,d{j}A∪B=k×{∑nA=0n‍∑yA=0y‍[RyA,nA]V0,d{j}A[Ry-yA,n-nB]V0,d{j}Bforn⩽Vj,∑nA=0n‍nAPn(y+Vj-n∣A)+nBPn(y+Vj-n∣B)n×∑z=0n-Vj‍∑yA=0n-Vj‍R[yA,nA]V0,d{j}A×R[n-Vj-yA-z,n-nA]V0,d{j}Bforn>Vj.
The way (33) is transformed to the form (36) is described in Appendix B.


## 3.1. Basic Assumptions

In order to present the basic assumptions of the proposed method for modelling systems with overflow traffic, let us consider an overflow system that consists ofk primary groups that belong to the set K and one alternative group (Figure 1). Each primary group j (j∈K) is offered traffic classes m1(j),m2(j),…,mmj(j) from the set M{j} with cardinality m{j}. Traffic of class mi(j), the calls of which demand ti(j) BBUs, is offered to the primary group j. Let M denote a set of all offered classes:
(1)M={M{1},M{2},…,M{k}}={m1(1),m2(1),…,mm{1}(1),m1(2),…,mm(2)(2),…,m1(k),…,mm{k}(k)}.
A primary group with the capacity Vj services traffic streams with the intensity A1(j),A2(j),…,Am{j}(j). Discarded traffic that is not serviced in these groups forms an overflow traffic stream. This traffic is then offered to the alternative group with the capacity V0. Hence, calls of classes of the set M{j} can occupy at the maximum d{j} BBUs in the system:
(2)d{j}=V0+Vj.
The calls of class mi(j) can occupy at the maximum di{j} BBUs in the system:
(3)di{j}=⌊Vjti(j)⌋ti(j)+⌊V0ti(j)⌋ti(j).
The total capacity of the system is
(4)V=V0+∑j=1k‍Vj.Figure 1
Structure of an overflow system.


## 3.2.  Occupancy Distribution

Firstly, let us consider the occupancy distribution[P]d{j}M{j}={[P0]d{j}M{j},[P1]d{j}M{j},…,[Pn]d{j}M{j},…,[Pd{j}]d{j}M{j}} in the basic subsystem of the considered overflow system presented in Figure 1, that is, a system with one primary group j and one alternative group for calls of classes of the set M{j}. A single nth element of the distribution [P]d{j}M{j}, that is, [Pn]d{j}M{j}, denotes the probability of n busy BBUs. The maximum number of BBUs that can be occupied in such a system is d{j} (equation (2)).By expanding our analysis of the system into a subsystem that is composed of two primary groups “j” and “j+1”, we can determine the occupancy distribution for two sets of service classes M{j} and M{j+1}. The single element [Pn]d{j,j+1}M{j,j+1} of the occupancy distribution in the system with two primary groups j and j+1 can be obtained by a convolution operation of distributions [P]d{j}M{j} and [P]d{j+1}M{j+1}:
(5)[Pn]d{j,j+1}M{j,j+1}=k·∑l=0n‍[Pl]d{j}M{j}[Pn-l]d{j+1}M{j+1},
where d{j} and d{j+1} are determined by (2), in which d{j,j+1} determines a new length of the distribution equal to
(6)d{j,j+1}=Vj+Vj+1+V0.
The parameter k in (5) is the normalization coefficient. Notice that according to the convolution operation defined by (5), the distribution [P]d{j,j+1}M{j,j+1} is shortened to the length d{j,j+1} that is lower than d{j}+d{j+1}. After shortening of the distribution, it is necessary then to normalize it. The normalization coefficient k ensures the sum of all elements of the distribution to be equal to one:
(7)k=1∑n=0d{j,j+1}∑l=0n[Pl]d{j}M{j}[Pn-l]d{j+1}M{j+1}.Let us notice that the expression (5) does not precisely reflect the operation of the overflow system since the convolution operation does not take into consideration states that appear as a result of the termination of a service of certain calls. States that occur directly after the termination of the service of a call in the primary group, in instances where all BBUs of the primary group and some (or all) BBUs of the alternative group were busy before the termination of this service, are not taken into consideration properly. To present this phenomenon, let us consider a simple example of an overflow system that is composed of three primary groups 1, 2, and 3 with the capacities V1=4, V2=4, and V3=4 BBUs. Each group is offered one traffic class with demands equal to 1 BBU. Traffic coming from the three groups overflows to alternative group with the capacity V0=4 BBUs. The total capacity of this system is then equal to 16 BBUs. Let us consider now the combination (4,8,0). The adopted notation is such that calls of the first class, offered to the first group, occupy 4 BBUs and calls of the second class, offered to the second group, occupy 8 BBUs, whereas no call that was offered to the third group is currently being serviced. The combination (4,8,0) is feasible because calls of the first class m1(1) occupy the entire primary group 1 (4 BBUs). Then, calls of class m2(2) can occupy 8 BBUs (entire primary group 2 (4 BBUs) and the whole alternative group (4 BBUs)) because calls of class m3(3) are not serviced at all. The considered combination is shown in Figure 2(a).Occupancy of resources in the overflow system with calls’ transfer.
(a)
combination(4,8,0)
(b)
combination(4,7,0) before the transfer of the call
(c)
combination(4,7,0) after the transfer of the callNote that the method for determination of the occupancy distribution in the system with traffic overflow presented in [44] assumes that after termination of each of the calls serviced in the primary group, calls are transferred from the alternative group to the appropriate primary group provided that the latter has free resources. This means that after a disconnection of a call of class 2 in the primary group 2 in the considered state (4,8,0), the system transits to state (4,7,0) (Figure 2(b)) in which immediately a transfer of the serviced connection of class 2 in the alternative group to the primary group is executed (Figure 2(c)). Consequently, the combination (4,7,0) means the occupancy of 4 BBUs by calls of class 1 in the primary group 1 and 7 BBUs by calls of class 2; while all 4 BBUs are busy in the primary group, 2 and 3 BBUs are busy in the alternative group. Hence, the convolution (5) determines the occupancy distribution in the overflow system that includes a transfer of connections from alternative group to primary group.Subsequently, let us try to determine, for the considered exemplary system, the aggregated distribution for the case when the system simultaneously services calls that are offered to all of the three primary groups. This distribution cannot be determined in a direct way since not all of the combinations included and taken into consideration in the distribution (5) are allowable. Consider an exemplary combination (2,8,5) in which calls offered to primary group 1 occupy 2 BBUs, calls offered to primary group 2 occupy 8 BBUs, and calls offered to primary group 3 occupy 5 BBUs. In total, there are 15 BBUs occupied for such a combination, less than the total capacity of the system V=16. Note, however, that according to the combination under consideration calls offered initially to primary group 2 occupy 4 BBUs in the alternative group, whereas calls offered initially to primary group 3 occupy 1 BBU. This means that calls offered initially to primary group 2 and 3 “occupy” more resources of the alternative group than the number of resources available in the group. Therefore, while determining probabilities for each of the states, it is necessary to omit those combinations that lead to an occupancy state in the alternative group higher than its capacity.The method that assumes call transfers between the alternative and the primary group and eliminates all forbidden states in which the number of busy BBUs in the alternative group exceeds the capacity of this group, the so-called simultaneous convolution operation of many distributions, is proposed in [44]. The method is characterized by high accuracy, while its limitation involves the assumption of only one call class that is offered to each of the primary groups. In Section 3.3, a new method will be proposed. The method is based on the so-called two-dimensional convolution operation that, due to a lower order of complexity, can make it possible to model more effectively systems with overflow traffic in which the primary group services single classes of calls. This will be followed by a presentation of two generalized methods (continuous method—Section 3.5.1—and discrete method—Section 3.5.2) that enable modelling systems in which each primary group can be offered many classes of calls.


## 3.3.  Two-Dimensional Distribution

Let state(y,n) denote a state in which there are y  occupied resources of the alternative group, with the total occupancy of the system equal to n. The two-dimensional occupancy distribution in this system will be denoted by the symbol [R]V0,V. In this distribution a single element [Ry,n]V0,V determines the state probability (y,n).According to the adopted notation in the paper, the first dimension determines the occupancy state of the alternative group, whereas the second dimension determines the occupancy state of the whole system. To justify such an approach let us consider an exemplary relation between the one-dimensional distribution[P]VM{j} and the two-dimensional distribution [R]V0,VM{j}. Both distributions describe state probabilities for the system with traffic overflow that is composed of the primary group j with the capacity Vj and the alternative group with the capacity V0. The primary group j is offered calls from the set M{j}. The relations between the elements of both distributions can be written in the following way:
(8)[Pn]VM{j}=∑y=0V0‍[Ry,n]V0,VM{j}.
Figure 3 shows the interpretation of (8) for the system composed of the primary group with the number 1, with the capacity V1=4 and the alternative group with the capacity V0=4. The primary group is offered calls from the set M{1}. The figure shows only those states—(y,n)—of the distribution [R]V0,VM{1} that are permitted by the system. Thus, the states in which a larger amount of resources of the alternative group than the capacity of this group would be occupied (y>V0), as well as the states in which more resources of the alternative group than the total amount of occupied resources would be occupied (y>n), are omitted.Figure 3
The relation between the one-dimensional and the two-dimensional distribution for a system with traffic overflow.


## 3.4. Modelling of Systems in Which the Primary Group Is Offered a Single Class of Calls

Let us recall that the method proposed in [44] is limited to the instances of modelling of systems in which the primary group is offered only one class of calls. The method [44] can be optimized effectively with the application of the two-dimensional distribution presented in the further part of this subsection. The input data that enable the determination of the two-dimensional distribution are then the occupancy distributions of the so-called subsystems. A subsystem is composed of a set of a certain number of primary groups and an alternative group. In this paper, the basic subsystem j will be a system that is composed of the primary group j and an alternative group. In our further considerations, the assumption that the system with traffic overflow is approximated by a system with calls transfer still holds good.


### 3.4.1. Determination of the Two-Dimensional Occupancy Distribution of the Basic Subsystem

Using the two-dimensional distribution[R]V0,d{j}M{j}, it is possible to describe the characteristics of the occupancy for the basic subsystem j. A single element [Ry,n]V0,d{j}M{j} of this distribution determines the occupancy probability of y BBUs in the alternative group and n BBUs in the whole system by calls of the classes from the set M{j}. In the case of the basic subsystem j the set M{j} is a one-element set. To improve the readability of the notation, we adopt that the symbols [p] and [r] will always denote occupancy distributions for one class of calls exclusively.In the basic subsystemj, which is offered one call of class i, the distribution [r]V0,d{j}{mi(j)} is the equivalent of the distribution [R]V0,d{j}M{j}. In a similar way, the distribution [p]d{j}{mi(j)} is the equivalent of the distribution [P]d{j}M{j}. A single element [ry,n]V0,d{j}{mi(j)} of the two-dimensional distribution can be determined on the basis of a single element of the one-dimensional distribution [p]d{j}{mi(j)} for the group with the capacity d{j}. For this purpose, we adopt that for the occupancy states n>Vj, where n denotes the total number of busy (occupied) resources, the relation y=n-⌊Vj/ti(j)⌋ti(j) is fulfilled. The parameter y denotes the number of busy resources of the alternative group. The adopted assumption is fulfilled for the systems with calls’ transfer and allows for the occurrence of a state in which the resources of the alternative group are busy, while part of the resources of the primary group has not been entirely used. Unused resources of the primary group result from the necessity of servicing a single call requiring ti(j) within one group.Thus according to adopted assumptions, the relation between the expressions of both distributions (one-dimensional and two-dimensional) can then be written in the following way:(9)[ry,n]V0,d{j}{mi(j)}={[pn]d{j}{mi(j)}for(y=0)∧(n⩽⌊Vjti(j)⌋ti(j)),[pn]d{j}{mi(j)}for(y=n-⌊Vjti(j)⌋ti(j))∧(⌊Vjti(j)⌋ti(j)<n⩽d{j}),0inremainingcases.Following the assumption for transferring the calls, it is possible to determine in an easy way the two-dimensional distribution[R]V0,d{j}{Mi{j}} of the occupancy in the basic system to which one class of calls is offered. The following subsection will present a description of the method for a determination of the two-dimensional occupancy distribution for multiservice systems with traffic overflow. The method (Section 3.4.2) is universal and does not depend on the number of traffic classes offered to basic subsystems. The distributions determined in the following subsection will provide a starting point for the algorithms for modelling systems in which many classes of calls are offered to the primary group.


### 3.4.2.  Two-Dimensional Convolution Operation

Consider now a method for a determination of the two-dimensional occupancy distribution[R]V0,VM for a multiservice system with traffic overflow. Each expression [Ry,n]V0,VM of this distribution determines the occupancy probability y BBU of the alternative group and n BBU of all groups (including the alternative group). The two-dimensional convolution operation makes it possible to effectively determine the distribution [R]V0,VM for the whole system with traffic overflow on the basis of the occupancy distributions [R]V0,d{j}M{j} of basic subsystems j with traffic overflow. The distribution [R]V0,d{j}M{j} can be a distribution for a subsystem in which the group j is offered one class of calls (its determination is described in Section 3.4.1) or a subsystem in which the primary group is offered a number of call classes (two different methods for a determination of these distributions are presented in Section 3.5.1 and Section 3.5.2, resp.).In order to determine the occupancy distribution for a system composed of primary groups that belong to the setK, all distributions [R]V0,d{j}M{j} (j∈K) are to be aggregated. The distribution [Ry,n]V0,d{1,…,j}M{1,…,j}, which determines state probabilities for a subsystem composed of primary groups 1,…,j and the alternative group, is determined on the basis of the convolution operation formulated as follows:
(10)[Ry,n]V0,d{1,…,j}M{1,…,j}=k∑ly=0y‍∑ln=0n‍[Rly,ln]V0,d{1,…,j-1}M{1,…,j-1}[Ry-ly,n-ln]V0,d{j}M{j},
for y⩽V0 and y⩽n. The symbol k in formula (10) is the normalization coefficient that is determined as follows:
(11)k∑y=0V0‍∑n=0V‍∑ly=0y‍∑ln=0n‍[Rly,ln]V0,d{1,…,j-1}M{1,…,j-1}[Ry-ly,n-ln]V0,d{j}M{j}=1.Let us interpret (10) with the example of a system that is composed of 3 primary groups with the capacity 4 BBUs each and an alternative group with the capacity 4 BBU. We will be considering combinations (y,n) of an overflow system composed of three primary groups and one alternative group with the following capacities: V1=V2=V3=V0=4. Let us consider then a combination ((0,2);(4,8);(1,5)) for the respective 3 subsystems. The considered combination describes a state in which calls of the classes from the set M{1} occupy 2 BBUs in a primary group and do not occupy resources in the alternative group of the subsystem. Calls of the classes from the set M{2} occupy 4 BBUs in the primary group and 4 BBUs in the alternative group of the subsystem, whereas calls of the classes from the set M{3} occupy 4 BBUs in the primary group and 1 BBU in the alternative group of the subsystem. Thus, the total number of busy BBUs in the alternative group is equal to 5, which means that this combination is not applicable. Let us analyse now a method for determination of the probability of an occurrence of such a combination using the two-dimensional convolution operation.Note that after the classes from the setM{1} and the classes from the set M{2} are aggregated, the probabilities of the occurrence of the state combination ((0,2);(4,8)) will be added up to the probability of the permitted state [R4,10]d{1,2}M{1,2}. While proceeding with further aggregation of the distribution of the classes from the set M{1,2} with the distribution of the classes from the set M{3}, the probability of occurrence of the state combination ((4,10);(1,5)) should be added to the state probability [R5,15]d{1,2,3}M{1,2,3}. This state, however, is not a permitted state in view of the convolution operation determined in (10), which allows us to eliminate properly nonpermitted states in the process of the determination of the two-dimensional distribution for the system with traffic overflow.Note that the convolution operation increases the length of the distribution in the dimension that determines the total number of busy BBUs, while the dimension that defines the capacity of the alternative group remains without any changes.The introduced notation, in which one dimension determines the occupancy of the alternative group while the other determines the occupancy of primary groups and the alternative group, makes it possible to directly convolute two-dimensional distributions. The order of complexity of a single convolution operation of two-dimensional distributions is equal toΘ(V02V2), whereas the order of computational complexity of the algorithm for k primary groups is Θ(kV02V2), which is a major advantage over the method discussed in [44], where the order of complexity is Θ(Vk).


### 3.4.3.  Blocking Probability

On the basis of the convolution operation (10) it is possible to determine the aggregated occupancy distributions [R]M∖{M{j}} for all groups except the group j:
(12)[R]V0,V-VjM∖M{j}=[R]d{1}M{1}*⋯*[R]d{j-1}M{j-1}*[R]d{j+1}M{j+1}*⋯*[R]d{k}M{k}.
Distribution (12) will allow us to work out a method for determination of the blocking probability for calls of traffic classes offered to group j, when the alternative group is offered overflow traffic from all primary groups.For this purpose, let us consider now the feasible combinations of the distributions[R]V0,V-VjM∖{M{j}} and [R]V0,d{j}{M{j}}. Let the set Ψ(j) be a set of all permitted occupancy combinations for the basic subsystem j with a subsystem that is composed of primary groups that belong to the set {1,2,…,j-1,j+1,…,k}. Let us define the possible combinations ((n-ln,y-ly);(n,y)) of the occupancy of the basic subsystem j with the subsystem that is composed of the remaining primary groups and the alternative group:
(13)Ψ(j)={(ln⩽min(n,d{j}))∧(ly⩽min(y,ln))∧(ln⩽min(n,d{j}))∧(ly⩽min(y,ln))(n,y,ln,ly):(n⩽V)∧(y⩽min(n,V0))∧(ln⩽min(n,d{j}))∧(ly⩽min(y,ln))}.
The condition n⩽V is self-explanatory since the total number of BBUs serviced in the system cannot exceed the capacity of the system. The condition y⩽min(n,V0) in formula (13) means that the number of all busy BBUs in the alternative group will always be equal to V0 or n at the maximum, if n<V0. The condition ln⩽min(n,d{j}) means that the total number of busy BBUs occupied by calls offered to the group j cannot be higher than the availability d{j} of the basic subsystem j or than the total number of n busy BBUs in the system (if n<d{j}). The condition ly⩽min(y,ln), in turn, expresses the fact the number of busy BBUs in the alternative group occupied by calls that overflow from the group j will never be higher than the total number ln of the resources that occupy calls offered to the group j or than the total number y of occupied resources of the alternative group, if y<ln.In the same way we will define the setΨi(j) that is a subset of the set Ψ(j) and that determines the blocking state for the class mi(j). The basis for the determination of this set is the lack of ti(j) free BBUs in both the alternative and the primary group j. Therefore we get
(14)Ψi(j)={∧(ln-ly>Vj-ti(j))(n,y,ln,ly)∈Ψ(j):(y>V0-ti(j))∧(ln-ly>Vj-ti(j))}.The probabilityP(n,y,ln,ly) of the combination from the set Ψ(j), in which calls of all classes occupy n BBUs in the primary groups and in the alternative group, while calls of the classes from the set M{j} occupy ln BBUs in the primary group j and the alternative group (ly BBUs in the alternative group), can be determined on the basis of the distributions [R]V0,V-VjM∖{M{j}} and [R]d{j}M{j}:
(15)P(n,y,ln,ly)=k[Rly,ln]V0,d{j}M{j}[Ry-ly,n-ln]V0,V-VjM∖M{j},
where k is the normalization coefficient equal to
(16)k=1∑Ψ(j)[Rly,ln]V0,d{j}M{j}[Ry-ly,n-ln]V0,V-VjM∖M{j}.
The blocking probability Ei(j) for the class mi(j) can be determined on the basis of the sum of the probabilities P(n,y,ln,ly) of blocking combinations from the set Ψi(j):
(17)Ei(j)=∑Ψi(j)‍P(n,y,ln,ly).


### 3.4.4. Algorithm for Modelling Systems with Overflow for Primary Groups with Single Classes of Calls

The algorithm that allows us to determine the blocking probability in networks with traffic overflow in which each primary group is offered a single class of calls can be written in the form of the following four stages:(1)
determination of the one-dimensional distribution[p]d{j}{mi(j)} for a single class mi(j) offered to the primary group j on the basis of models worked-out for single-service systems,(2)
determination of two-dimensional distributions[r]V0,d{j}mi(j) for all primary groups on the basis of one-dimensional distributions [p]d{j}mi(j) (formula (9)),(3)
determination, for every primary groupj, of aggregated distributions [R]V0,V-VjM∖M{j} of all primary groups except group j (formula (12)),(4)
determination of the blocking probability (formula (17)) for each traffic class mi(j) offered to each primary group j.


## 3.4.1. Determination of the Two-Dimensional Occupancy Distribution of the Basic Subsystem

Using the two-dimensional distribution[R]V0,d{j}M{j}, it is possible to describe the characteristics of the occupancy for the basic subsystem j. A single element [Ry,n]V0,d{j}M{j} of this distribution determines the occupancy probability of y BBUs in the alternative group and n BBUs in the whole system by calls of the classes from the set M{j}. In the case of the basic subsystem j the set M{j} is a one-element set. To improve the readability of the notation, we adopt that the symbols [p] and [r] will always denote occupancy distributions for one class of calls exclusively.In the basic subsystemj, which is offered one call of class i, the distribution [r]V0,d{j}{mi(j)} is the equivalent of the distribution [R]V0,d{j}M{j}. In a similar way, the distribution [p]d{j}{mi(j)} is the equivalent of the distribution [P]d{j}M{j}. A single element [ry,n]V0,d{j}{mi(j)} of the two-dimensional distribution can be determined on the basis of a single element of the one-dimensional distribution [p]d{j}{mi(j)} for the group with the capacity d{j}. For this purpose, we adopt that for the occupancy states n>Vj, where n denotes the total number of busy (occupied) resources, the relation y=n-⌊Vj/ti(j)⌋ti(j) is fulfilled. The parameter y denotes the number of busy resources of the alternative group. The adopted assumption is fulfilled for the systems with calls’ transfer and allows for the occurrence of a state in which the resources of the alternative group are busy, while part of the resources of the primary group has not been entirely used. Unused resources of the primary group result from the necessity of servicing a single call requiring ti(j) within one group.Thus according to adopted assumptions, the relation between the expressions of both distributions (one-dimensional and two-dimensional) can then be written in the following way:(9)[ry,n]V0,d{j}{mi(j)}={[pn]d{j}{mi(j)}for(y=0)∧(n⩽⌊Vjti(j)⌋ti(j)),[pn]d{j}{mi(j)}for(y=n-⌊Vjti(j)⌋ti(j))∧(⌊Vjti(j)⌋ti(j)<n⩽d{j}),0inremainingcases.Following the assumption for transferring the calls, it is possible to determine in an easy way the two-dimensional distribution[R]V0,d{j}{Mi{j}} of the occupancy in the basic system to which one class of calls is offered. The following subsection will present a description of the method for a determination of the two-dimensional occupancy distribution for multiservice systems with traffic overflow. The method (Section 3.4.2) is universal and does not depend on the number of traffic classes offered to basic subsystems. The distributions determined in the following subsection will provide a starting point for the algorithms for modelling systems in which many classes of calls are offered to the primary group.


## 3.4.2.  Two-Dimensional Convolution Operation

Consider now a method for a determination of the two-dimensional occupancy distribution[R]V0,VM for a multiservice system with traffic overflow. Each expression [Ry,n]V0,VM of this distribution determines the occupancy probability y BBU of the alternative group and n BBU of all groups (including the alternative group). The two-dimensional convolution operation makes it possible to effectively determine the distribution [R]V0,VM for the whole system with traffic overflow on the basis of the occupancy distributions [R]V0,d{j}M{j} of basic subsystems j with traffic overflow. The distribution [R]V0,d{j}M{j} can be a distribution for a subsystem in which the group j is offered one class of calls (its determination is described in Section 3.4.1) or a subsystem in which the primary group is offered a number of call classes (two different methods for a determination of these distributions are presented in Section 3.5.1 and Section 3.5.2, resp.).In order to determine the occupancy distribution for a system composed of primary groups that belong to the setK, all distributions [R]V0,d{j}M{j} (j∈K) are to be aggregated. The distribution [Ry,n]V0,d{1,…,j}M{1,…,j}, which determines state probabilities for a subsystem composed of primary groups 1,…,j and the alternative group, is determined on the basis of the convolution operation formulated as follows:
(10)[Ry,n]V0,d{1,…,j}M{1,…,j}=k∑ly=0y‍∑ln=0n‍[Rly,ln]V0,d{1,…,j-1}M{1,…,j-1}[Ry-ly,n-ln]V0,d{j}M{j},
for y⩽V0 and y⩽n. The symbol k in formula (10) is the normalization coefficient that is determined as follows:
(11)k∑y=0V0‍∑n=0V‍∑ly=0y‍∑ln=0n‍[Rly,ln]V0,d{1,…,j-1}M{1,…,j-1}[Ry-ly,n-ln]V0,d{j}M{j}=1.Let us interpret (10) with the example of a system that is composed of 3 primary groups with the capacity 4 BBUs each and an alternative group with the capacity 4 BBU. We will be considering combinations (y,n) of an overflow system composed of three primary groups and one alternative group with the following capacities: V1=V2=V3=V0=4. Let us consider then a combination ((0,2);(4,8);(1,5)) for the respective 3 subsystems. The considered combination describes a state in which calls of the classes from the set M{1} occupy 2 BBUs in a primary group and do not occupy resources in the alternative group of the subsystem. Calls of the classes from the set M{2} occupy 4 BBUs in the primary group and 4 BBUs in the alternative group of the subsystem, whereas calls of the classes from the set M{3} occupy 4 BBUs in the primary group and 1 BBU in the alternative group of the subsystem. Thus, the total number of busy BBUs in the alternative group is equal to 5, which means that this combination is not applicable. Let us analyse now a method for determination of the probability of an occurrence of such a combination using the two-dimensional convolution operation.Note that after the classes from the setM{1} and the classes from the set M{2} are aggregated, the probabilities of the occurrence of the state combination ((0,2);(4,8)) will be added up to the probability of the permitted state [R4,10]d{1,2}M{1,2}. While proceeding with further aggregation of the distribution of the classes from the set M{1,2} with the distribution of the classes from the set M{3}, the probability of occurrence of the state combination ((4,10);(1,5)) should be added to the state probability [R5,15]d{1,2,3}M{1,2,3}. This state, however, is not a permitted state in view of the convolution operation determined in (10), which allows us to eliminate properly nonpermitted states in the process of the determination of the two-dimensional distribution for the system with traffic overflow.Note that the convolution operation increases the length of the distribution in the dimension that determines the total number of busy BBUs, while the dimension that defines the capacity of the alternative group remains without any changes.The introduced notation, in which one dimension determines the occupancy of the alternative group while the other determines the occupancy of primary groups and the alternative group, makes it possible to directly convolute two-dimensional distributions. The order of complexity of a single convolution operation of two-dimensional distributions is equal toΘ(V02V2), whereas the order of computational complexity of the algorithm for k primary groups is Θ(kV02V2), which is a major advantage over the method discussed in [44], where the order of complexity is Θ(Vk).


## 3.4.3.  Blocking Probability

On the basis of the convolution operation (10) it is possible to determine the aggregated occupancy distributions [R]M∖{M{j}} for all groups except the group j:
(12)[R]V0,V-VjM∖M{j}=[R]d{1}M{1}*⋯*[R]d{j-1}M{j-1}*[R]d{j+1}M{j+1}*⋯*[R]d{k}M{k}.
Distribution (12) will allow us to work out a method for determination of the blocking probability for calls of traffic classes offered to group j, when the alternative group is offered overflow traffic from all primary groups.For this purpose, let us consider now the feasible combinations of the distributions[R]V0,V-VjM∖{M{j}} and [R]V0,d{j}{M{j}}. Let the set Ψ(j) be a set of all permitted occupancy combinations for the basic subsystem j with a subsystem that is composed of primary groups that belong to the set {1,2,…,j-1,j+1,…,k}. Let us define the possible combinations ((n-ln,y-ly);(n,y)) of the occupancy of the basic subsystem j with the subsystem that is composed of the remaining primary groups and the alternative group:
(13)Ψ(j)={(ln⩽min(n,d{j}))∧(ly⩽min(y,ln))∧(ln⩽min(n,d{j}))∧(ly⩽min(y,ln))(n,y,ln,ly):(n⩽V)∧(y⩽min(n,V0))∧(ln⩽min(n,d{j}))∧(ly⩽min(y,ln))}.
The condition n⩽V is self-explanatory since the total number of BBUs serviced in the system cannot exceed the capacity of the system. The condition y⩽min(n,V0) in formula (13) means that the number of all busy BBUs in the alternative group will always be equal to V0 or n at the maximum, if n<V0. The condition ln⩽min(n,d{j}) means that the total number of busy BBUs occupied by calls offered to the group j cannot be higher than the availability d{j} of the basic subsystem j or than the total number of n busy BBUs in the system (if n<d{j}). The condition ly⩽min(y,ln), in turn, expresses the fact the number of busy BBUs in the alternative group occupied by calls that overflow from the group j will never be higher than the total number ln of the resources that occupy calls offered to the group j or than the total number y of occupied resources of the alternative group, if y<ln.In the same way we will define the setΨi(j) that is a subset of the set Ψ(j) and that determines the blocking state for the class mi(j). The basis for the determination of this set is the lack of ti(j) free BBUs in both the alternative and the primary group j. Therefore we get
(14)Ψi(j)={∧(ln-ly>Vj-ti(j))(n,y,ln,ly)∈Ψ(j):(y>V0-ti(j))∧(ln-ly>Vj-ti(j))}.The probabilityP(n,y,ln,ly) of the combination from the set Ψ(j), in which calls of all classes occupy n BBUs in the primary groups and in the alternative group, while calls of the classes from the set M{j} occupy ln BBUs in the primary group j and the alternative group (ly BBUs in the alternative group), can be determined on the basis of the distributions [R]V0,V-VjM∖{M{j}} and [R]d{j}M{j}:
(15)P(n,y,ln,ly)=k[Rly,ln]V0,d{j}M{j}[Ry-ly,n-ln]V0,V-VjM∖M{j},
where k is the normalization coefficient equal to
(16)k=1∑Ψ(j)[Rly,ln]V0,d{j}M{j}[Ry-ly,n-ln]V0,V-VjM∖M{j}.
The blocking probability Ei(j) for the class mi(j) can be determined on the basis of the sum of the probabilities P(n,y,ln,ly) of blocking combinations from the set Ψi(j):
(17)Ei(j)=∑Ψi(j)‍P(n,y,ln,ly).


## 3.4.4. Algorithm for Modelling Systems with Overflow for Primary Groups with Single Classes of Calls

The algorithm that allows us to determine the blocking probability in networks with traffic overflow in which each primary group is offered a single class of calls can be written in the form of the following four stages:(1)
determination of the one-dimensional distribution[p]d{j}{mi(j)} for a single class mi(j) offered to the primary group j on the basis of models worked-out for single-service systems,(2)
determination of two-dimensional distributions[r]V0,d{j}mi(j) for all primary groups on the basis of one-dimensional distributions [p]d{j}mi(j) (formula (9)),(3)
determination, for every primary groupj, of aggregated distributions [R]V0,V-VjM∖M{j} of all primary groups except group j (formula (12)),(4)
determination of the blocking probability (formula (17)) for each traffic class mi(j) offered to each primary group j.


## 3.5.  Modelling of Systems in Which the Primary Group Is Offered a Number of Call Classes

### 3.5.1.  Continuous Method

Consider now an overflow system in which primary groups are offered many classes of calls (multiple classes of calls). According to the adopted notation, the primary groupj is offered call classes from the set M{j}. In the first proposed method, that is, the continuous method, we adopt the assumption that a single call can be serviced simultaneously by the resources of the primary as well as the alternative group. The occupancy distribution in the considered basic subsystem is determined on the basis of a modified convolution operation of two-dimensional distributions.Consider a system in which the primary groupj has the capacity Vj. Traffic from this group overflows to the alternative group with the capacity V0. Assume that the sets A and B are separable subsets of the set M{j}. The primary group j is offered mixtures of call classes that belong to the sets A and B for which the distributions [R]V0,d{j}A and [R]V0,d{j}B have been determined.For any groupj in the overflow system with the assumed calls’ transfer, the two-dimensional convolution operation makes it possible to determine the elements [Ry,n]V0,d{j}A∪B of the distribution [R]V0,d{j}A∪B on the basis of the summation of probabilities (combinations) of states ((yA,nA);(yB,nB)) that satisfy the following condition:
(18)nA-yA+nB-yB⩽Vj.
Condition (18) determines all combinations for states ((yA,nA);(yB,nB)) whose probabilities can be added up to the probability of the aggregated state (y,n). For the states that satisfy the condition (18), the following relations then ensue:
(19)n=nA+nB,(20)y=yA+yB.Let us determine now for the state(y,n) a set αBA(y,n) of all state combinations ((yA,nA);(yB,nB)) for which the condition (18) is fulfilled, that is, for which the value of deficit z (described in the next paragraph) is equal to 0:
(21)αBA(y,n)={((yA,nA);(yB,nB)):(n=nA+nB)∧(y=yA+yB)∧(nA-yA+nB-yB⩽Vj)∧(y⩽V0)}.The system also offers such combinations of states((yA,nA);(yB,nB)) that do not satisfy the condition (18). These combinations will be permitted in the system when part of the serviced calls is transferred to the alternative group. Then, the relation (19) that determines the total occupancy in the system is still retained, while the relation (20) is not satisfied because the occupancy of the alternative group changes. The failure of the relation (20) results from the so-called deficit z in the resources of the primary group. This deficit can be determined in the following way:
(22)z=nA-yA+nB-yB-Vj.
The interpretation of the deficit of the primary resources is shown in Figure 4. Figure 4(a) presents the combination ((yA,nA);(yB,nB)), when the resources of the primary and the alternative groups are occupied only by calls from the set A and when the resources are occupied only by calls from the set B. Figure 4(b) shows the attempt to aggregate both combinations. It is clear to see the deficit in the resources that is to be “transferred” to the resources of the alternative group (Figure 4(c)). Note that the amount of all resources of the alternative group after the transfer of the deficit resources taken into consideration is equal to
(23)y=nA+nB-Vj.
Taking into account (19), which is always true (for z=0 and for z≠0), we can express (23) in the following form:
(24)y=n-Vj.
Now, we are in a position to define the set βBA(y,n) of all permitted combinations ((yA,nA); (yB,nB)) for which the deficit value z is higher than zero (the condition (18) has not been fulfilled):
(25)βBA(y,n)={∧(nA-yA+nB-yB>Vj)∧(y⩽V0)((yA,nA);(yB,nB)):(n=nA+nB)∧(y=yA+yB+z)∧(nA-yA+nB-yB>Vj)∧(y⩽V0)}.
Taking into account (22), the set (25) can be rewritten as follows:
(26)βBA(y,n)={∧(nA-yA+nB-yB>Vj)∧(y⩽V0)((yA,nA);(yB,nB)):(n=nA+nB)∧(y=nA+nB-Vj)∧(nA-yA+nB-yB>Vj)∧(y⩽V0)}.Interpretation of the parameterz defining the deficit of resources in the primary group.
(a)
Combination of occupancy states
(b)
Deficit in the resources in the primary group
(c)
Transferred deficit of resources of the alternative groupOn the basis of the setsαBA(y,n) and βBA(y,n) it is possible to determine the sum of the probabilities of all combinations for the state (y,n), that is, the probability [Ry,n]V0,d{j}A∪B for this state:
(27)[Ry,n]V0,d{j}A∪B=k∑αBA(y,n)∪βBA(y,n)‍[RyA,nA]V0,d{j}A[RyB,nB]V0,d{j}B.Equation (27) can be rewritten in the following way:
(28)[Ry,n]V0,d{j}A∪B=k{∑nA=0n‍∑yA=0y‍[RyA,nA]V0,d{j}A[Ry-yB,nB]V0,d{j}Bfory>n-Vj,∑nA=0n‍∑z=0n-Vj‍∑yA=0y-z‍[RyA,nA]V0,d{j}A[Ry-yA-z,nB]V0,d{j}Bfory=n-Vj,0fory<n-Vj.
The transformation of (27) into (28) is presented in Appendix A. Using (28) we are in a position to aggregate subsequent distributions in the primary group. It is thus a convenient notation for a construction of the computational algorithm.


### 3.5.2.  Discrete Method

The method for determination of the occupancy distribution in the basic subsystem with multiple call classes, that is, a system that is composed of the primary group and the alternative group presented in Section3.5.1, adopts the assumption that the transfer of calls results in a total exploitation of the primary group. Such an approach assumes a possibility of simultaneous occupation of the resources of the primary and the alternative group by one call in the stage of the aggregation of classes within the basic subsystem and, in consequence, leads to inaccurate and imprecise determination of the deficit in resources.Let us consider now a modified method for determination of the two-dimensional occupancy distribution[R]V0,d{j}A∪B for the basic subsystem on the basis of the occupancy distributions [R]V0,d{j}A and [R]V0,d{j}B in which a possibility of a simultaneous servicing of calls by the resources of the primary and the alternative groups is excluded. Note that, on the basis of the given combination ((yA,nA);(yB,nB)), it is not possible to unequivocally determine the history of call acceptance and call service. It is not possible then to determine the amount s of resources of the primary group that cannot be used due to the lack of the possibility of a division of the serviced call between the primary group and the alternative group. The value of the parameter s depends not only on the combination itself but also on the history of call acceptance and call service.As previously mentioned, let us assume that the basic subsystemj is offered mixtures of call classes that belong to the set A and B. The sets A and B are separate subsets of the set M{j} traffic classes.The number of occupied resourcesy in the alternative group can be determined in the same way as in Section 3.5.1 but with the number s of unused resources in the primary group taken additionally into account. If the total number of occupied resources is lower than or equal to the capacity of the primary group, then there is no deficit in resources and all resources of the primary group can be used. In this situation, the condition (18) is also fulfilled. If the number of occupied resources exceeds the capacity of the primary group and the condition (18) is at the same time fulfilled, then there is no deficit in the primary group. When this is the case, the number of busy resources of the alternative group is higher by the number of unused resources of the primary group s. In the case when the condition (18) is not fulfilled, the number y of busy resources of the primary group is increased by the parameters z and s. We can thus write
(29)y={yA+yBforn⩽Vj,yA+yB+sfor(nA-yA+nB-yB⩽Vj),yA+yB+s+zfor(nA-yA+nB-yB>Vj).Consider now the way the parameters that determines the number of unused resources of the primary group is estimated. Assuming that there is a possibility of calls’ transfer, there can be at the maximum tmax(A)-1 unused BBU or tmax(B)-1 unused BBU in the primary group, depending on which call class has been admitted for service as the last one. The upper boundary for the value of the parameter s is (V-n) BBU, that is, the number of free resources in both groups (primary and alternative). Let smaxA(n) denote the maximum number of unused resources in the primary group, on condition that a call that belongs to the set A has been accepted as the last one:
(30)smaxA(n)={min(tmax(A)-1,V-n)forn>Vj,0forn⩽Vj.LetPn(s∣A) denote the probability of s BBU unused in the primary group in state n, on condition that the last accepted call was a call of the class that belongs to the set A. A determination of this probability is fairly complex. Let us assume then that the distributions P(s∣A) and P(s∣B) are approximated by the uniform distribution:
(31)Pn(s∣A)={1smaxA(n)for0⩽s⩽smaxA(n),0inothercases,Pn(s∣B)={1smaxB(n)for0⩽s⩽smaxB(n),0inothercases.LetPn(A) denote the probability that the state n has been reached when the last accepted call was a call of the class that belonged to the set A, and Pn(B) denotes the probability that the state n has been reached when the last accepted call was a call of the class that belonged to the set B. The proposed method makes the assumption that these probabilities are directly proportional to the number of resources that are occupied by calls that belong to the sets A and B:
(32)Pn(A)=nAn,Pn(B)=nBn.Let us define the convolution of the distributions[R]V0,d{j}A and [R]V0,d{j}B. To determine the state probability (y,n), let us consider the three intervals defined in (29). The first interval includes the states (y,n) for n⩽Vj. The second and the third intervals include states in which the total number of occupied resources n is higher than the capacity of the primary group Vj. Each interval includes the combinations of states denoted as ((yA,nA);(yB,nB)).Let us consider the method for determination of the probability of occurrence of the states(y,n) for n⩽Vj as the first. The probability of the occurrence of the state (y,n) is equal to the sum of the probability of occurrence for all combinations for this particular state, defined in (19) and (29):
(33)∀n⩽Vj[Ry,n]V0,d{j}A∪B=k∑nA=0n‍∑yA=0y‍[RyA,nA]V0,d{j}A[Ry-yA,n-nA]V0,d{j}B.
For the remaining two intervals defined in (29), to determine the state probability (y,n), for n>Vj, it is necessary to take into consideration additional parameters such as Pn(s∣A), Pn(s∣B) (formula (31)) and Pn(A) and Pn(B) (formula (32)). In addition, it is necessary to define the set γ of all possible combinations (yA,nA);(yB,nB) for the second interval of (29) and the set φ of all possible combinations for the third interval.Definitions of the setsγ and φ depend on the last admitted call. If the last admitted call is a call of the classes from the set A, then for the state (y,n) we denote these sets as γBA(y,n) and φBA(y,n). Similarly, if the last admitted call was a call of the class that belonged to the set B, then the sets will be denoted as γAB(y,n) and φAB(y,n). The sets γBA(y,n), φBA(y,n), γAB(y,n) and φAB(y,n) define all the possible combinations ((yA,nA);(yB,nB)) as well as the number of unused resources s for the state (y,n). In addition, the sets φBA(y,n) and φAB(y,n) define the deficit z of the resources of the primary group. As a consequence of our considerations we can write
(34)γBA(y,n)={∧(y=n-Vj+s)((yA,nA);(yB,nB),s):(n=nA+nB)∧(y=yA+yB+s)∧(0⩽s⩽smaxA(n))∧(y=n-Vj+s)},γAB(y,n)={∧(y=n-Vj+s)((yA,nA);(yB,nB),s):(n=nA+nB)∧(y=yA+yB+s)∧(0⩽s⩽smaxB(n))∧(y=n-Vj+s)},φBA(y,n)={∧(1⩽z⩽n-Vj)∧(y=n-Vj+s)((yA,nA);(yB,nB),s,z):(n=nA+nB)∧(y=yA+yB+z+s)∧(0⩽s⩽smaxA(n))∧(1⩽z⩽n-Vj)∧(y=n-Vj+s)},φAB(y,n)={∧1(⩽z⩽n-Vj)∧(y=n-Vj+s)((yA,nA);(yB,nB),s,z):(n=nA+nB)∧(y=yA+yB+z+s)∧(0⩽s⩽smaxB(n))∧(1⩽z⩽n-Vj)∧(y=n-Vj+s)}.In line with the adopted notation, the state probability(y,n) (for n>Vj) can be written as follows:
(35)∀n>Vj[Ry,n]V0,d{j}A∪B=kP(A)∑γBA(y,n)∪φBA(y,n)‍Pn(s∣A)×[RyA,nA]V0,d{j}A[RyB,nB]V0,d{j}B+kP(B)∑γAB(y,n)∪φAB(y,n)‍Pn(s∣B)×[RyA,nA]V0,d{j}A[RyB,nB]V0,d{j}B.
Equations (33) and (35) can be combined and eventually rewritten in the following form:
(36)[Ry,n]V0,d{j}A∪B=k×{∑nA=0n‍∑yA=0y‍[RyA,nA]V0,d{j}A[Ry-yA,n-nB]V0,d{j}Bforn⩽Vj,∑nA=0n‍nAPn(y+Vj-n∣A)+nBPn(y+Vj-n∣B)n×∑z=0n-Vj‍∑yA=0n-Vj‍R[yA,nA]V0,d{j}A×R[n-Vj-yA-z,n-nA]V0,d{j}Bforn>Vj.
The way (33) is transformed to the form (36) is described in Appendix B.


## 3.5.1.  Continuous Method

Consider now an overflow system in which primary groups are offered many classes of calls (multiple classes of calls). According to the adopted notation, the primary groupj is offered call classes from the set M{j}. In the first proposed method, that is, the continuous method, we adopt the assumption that a single call can be serviced simultaneously by the resources of the primary as well as the alternative group. The occupancy distribution in the considered basic subsystem is determined on the basis of a modified convolution operation of two-dimensional distributions.Consider a system in which the primary groupj has the capacity Vj. Traffic from this group overflows to the alternative group with the capacity V0. Assume that the sets A and B are separable subsets of the set M{j}. The primary group j is offered mixtures of call classes that belong to the sets A and B for which the distributions [R]V0,d{j}A and [R]V0,d{j}B have been determined.For any groupj in the overflow system with the assumed calls’ transfer, the two-dimensional convolution operation makes it possible to determine the elements [Ry,n]V0,d{j}A∪B of the distribution [R]V0,d{j}A∪B on the basis of the summation of probabilities (combinations) of states ((yA,nA);(yB,nB)) that satisfy the following condition:
(18)nA-yA+nB-yB⩽Vj.
Condition (18) determines all combinations for states ((yA,nA);(yB,nB)) whose probabilities can be added up to the probability of the aggregated state (y,n). For the states that satisfy the condition (18), the following relations then ensue:
(19)n=nA+nB,(20)y=yA+yB.Let us determine now for the state(y,n) a set αBA(y,n) of all state combinations ((yA,nA);(yB,nB)) for which the condition (18) is fulfilled, that is, for which the value of deficit z (described in the next paragraph) is equal to 0:
(21)αBA(y,n)={((yA,nA);(yB,nB)):(n=nA+nB)∧(y=yA+yB)∧(nA-yA+nB-yB⩽Vj)∧(y⩽V0)}.The system also offers such combinations of states((yA,nA);(yB,nB)) that do not satisfy the condition (18). These combinations will be permitted in the system when part of the serviced calls is transferred to the alternative group. Then, the relation (19) that determines the total occupancy in the system is still retained, while the relation (20) is not satisfied because the occupancy of the alternative group changes. The failure of the relation (20) results from the so-called deficit z in the resources of the primary group. This deficit can be determined in the following way:
(22)z=nA-yA+nB-yB-Vj.
The interpretation of the deficit of the primary resources is shown in Figure 4. Figure 4(a) presents the combination ((yA,nA);(yB,nB)), when the resources of the primary and the alternative groups are occupied only by calls from the set A and when the resources are occupied only by calls from the set B. Figure 4(b) shows the attempt to aggregate both combinations. It is clear to see the deficit in the resources that is to be “transferred” to the resources of the alternative group (Figure 4(c)). Note that the amount of all resources of the alternative group after the transfer of the deficit resources taken into consideration is equal to
(23)y=nA+nB-Vj.
Taking into account (19), which is always true (for z=0 and for z≠0), we can express (23) in the following form:
(24)y=n-Vj.
Now, we are in a position to define the set βBA(y,n) of all permitted combinations ((yA,nA); (yB,nB)) for which the deficit value z is higher than zero (the condition (18) has not been fulfilled):
(25)βBA(y,n)={∧(nA-yA+nB-yB>Vj)∧(y⩽V0)((yA,nA);(yB,nB)):(n=nA+nB)∧(y=yA+yB+z)∧(nA-yA+nB-yB>Vj)∧(y⩽V0)}.
Taking into account (22), the set (25) can be rewritten as follows:
(26)βBA(y,n)={∧(nA-yA+nB-yB>Vj)∧(y⩽V0)((yA,nA);(yB,nB)):(n=nA+nB)∧(y=nA+nB-Vj)∧(nA-yA+nB-yB>Vj)∧(y⩽V0)}.Interpretation of the parameterz defining the deficit of resources in the primary group.
(a)
Combination of occupancy states
(b)
Deficit in the resources in the primary group
(c)
Transferred deficit of resources of the alternative groupOn the basis of the setsαBA(y,n) and βBA(y,n) it is possible to determine the sum of the probabilities of all combinations for the state (y,n), that is, the probability [Ry,n]V0,d{j}A∪B for this state:
(27)[Ry,n]V0,d{j}A∪B=k∑αBA(y,n)∪βBA(y,n)‍[RyA,nA]V0,d{j}A[RyB,nB]V0,d{j}B.Equation (27) can be rewritten in the following way:
(28)[Ry,n]V0,d{j}A∪B=k{∑nA=0n‍∑yA=0y‍[RyA,nA]V0,d{j}A[Ry-yB,nB]V0,d{j}Bfory>n-Vj,∑nA=0n‍∑z=0n-Vj‍∑yA=0y-z‍[RyA,nA]V0,d{j}A[Ry-yA-z,nB]V0,d{j}Bfory=n-Vj,0fory<n-Vj.
The transformation of (27) into (28) is presented in Appendix A. Using (28) we are in a position to aggregate subsequent distributions in the primary group. It is thus a convenient notation for a construction of the computational algorithm.


## 3.5.2.  Discrete Method

The method for determination of the occupancy distribution in the basic subsystem with multiple call classes, that is, a system that is composed of the primary group and the alternative group presented in Section3.5.1, adopts the assumption that the transfer of calls results in a total exploitation of the primary group. Such an approach assumes a possibility of simultaneous occupation of the resources of the primary and the alternative group by one call in the stage of the aggregation of classes within the basic subsystem and, in consequence, leads to inaccurate and imprecise determination of the deficit in resources.Let us consider now a modified method for determination of the two-dimensional occupancy distribution[R]V0,d{j}A∪B for the basic subsystem on the basis of the occupancy distributions [R]V0,d{j}A and [R]V0,d{j}B in which a possibility of a simultaneous servicing of calls by the resources of the primary and the alternative groups is excluded. Note that, on the basis of the given combination ((yA,nA);(yB,nB)), it is not possible to unequivocally determine the history of call acceptance and call service. It is not possible then to determine the amount s of resources of the primary group that cannot be used due to the lack of the possibility of a division of the serviced call between the primary group and the alternative group. The value of the parameter s depends not only on the combination itself but also on the history of call acceptance and call service.As previously mentioned, let us assume that the basic subsystemj is offered mixtures of call classes that belong to the set A and B. The sets A and B are separate subsets of the set M{j} traffic classes.The number of occupied resourcesy in the alternative group can be determined in the same way as in Section 3.5.1 but with the number s of unused resources in the primary group taken additionally into account. If the total number of occupied resources is lower than or equal to the capacity of the primary group, then there is no deficit in resources and all resources of the primary group can be used. In this situation, the condition (18) is also fulfilled. If the number of occupied resources exceeds the capacity of the primary group and the condition (18) is at the same time fulfilled, then there is no deficit in the primary group. When this is the case, the number of busy resources of the alternative group is higher by the number of unused resources of the primary group s. In the case when the condition (18) is not fulfilled, the number y of busy resources of the primary group is increased by the parameters z and s. We can thus write
(29)y={yA+yBforn⩽Vj,yA+yB+sfor(nA-yA+nB-yB⩽Vj),yA+yB+s+zfor(nA-yA+nB-yB>Vj).Consider now the way the parameters that determines the number of unused resources of the primary group is estimated. Assuming that there is a possibility of calls’ transfer, there can be at the maximum tmax(A)-1 unused BBU or tmax(B)-1 unused BBU in the primary group, depending on which call class has been admitted for service as the last one. The upper boundary for the value of the parameter s is (V-n) BBU, that is, the number of free resources in both groups (primary and alternative). Let smaxA(n) denote the maximum number of unused resources in the primary group, on condition that a call that belongs to the set A has been accepted as the last one:
(30)smaxA(n)={min(tmax(A)-1,V-n)forn>Vj,0forn⩽Vj.LetPn(s∣A) denote the probability of s BBU unused in the primary group in state n, on condition that the last accepted call was a call of the class that belongs to the set A. A determination of this probability is fairly complex. Let us assume then that the distributions P(s∣A) and P(s∣B) are approximated by the uniform distribution:
(31)Pn(s∣A)={1smaxA(n)for0⩽s⩽smaxA(n),0inothercases,Pn(s∣B)={1smaxB(n)for0⩽s⩽smaxB(n),0inothercases.LetPn(A) denote the probability that the state n has been reached when the last accepted call was a call of the class that belonged to the set A, and Pn(B) denotes the probability that the state n has been reached when the last accepted call was a call of the class that belonged to the set B. The proposed method makes the assumption that these probabilities are directly proportional to the number of resources that are occupied by calls that belong to the sets A and B:
(32)Pn(A)=nAn,Pn(B)=nBn.Let us define the convolution of the distributions[R]V0,d{j}A and [R]V0,d{j}B. To determine the state probability (y,n), let us consider the three intervals defined in (29). The first interval includes the states (y,n) for n⩽Vj. The second and the third intervals include states in which the total number of occupied resources n is higher than the capacity of the primary group Vj. Each interval includes the combinations of states denoted as ((yA,nA);(yB,nB)).Let us consider the method for determination of the probability of occurrence of the states(y,n) for n⩽Vj as the first. The probability of the occurrence of the state (y,n) is equal to the sum of the probability of occurrence for all combinations for this particular state, defined in (19) and (29):
(33)∀n⩽Vj[Ry,n]V0,d{j}A∪B=k∑nA=0n‍∑yA=0y‍[RyA,nA]V0,d{j}A[Ry-yA,n-nA]V0,d{j}B.
For the remaining two intervals defined in (29), to determine the state probability (y,n), for n>Vj, it is necessary to take into consideration additional parameters such as Pn(s∣A), Pn(s∣B) (formula (31)) and Pn(A) and Pn(B) (formula (32)). In addition, it is necessary to define the set γ of all possible combinations (yA,nA);(yB,nB) for the second interval of (29) and the set φ of all possible combinations for the third interval.Definitions of the setsγ and φ depend on the last admitted call. If the last admitted call is a call of the classes from the set A, then for the state (y,n) we denote these sets as γBA(y,n) and φBA(y,n). Similarly, if the last admitted call was a call of the class that belonged to the set B, then the sets will be denoted as γAB(y,n) and φAB(y,n). The sets γBA(y,n), φBA(y,n), γAB(y,n) and φAB(y,n) define all the possible combinations ((yA,nA);(yB,nB)) as well as the number of unused resources s for the state (y,n). In addition, the sets φBA(y,n) and φAB(y,n) define the deficit z of the resources of the primary group. As a consequence of our considerations we can write
(34)γBA(y,n)={∧(y=n-Vj+s)((yA,nA);(yB,nB),s):(n=nA+nB)∧(y=yA+yB+s)∧(0⩽s⩽smaxA(n))∧(y=n-Vj+s)},γAB(y,n)={∧(y=n-Vj+s)((yA,nA);(yB,nB),s):(n=nA+nB)∧(y=yA+yB+s)∧(0⩽s⩽smaxB(n))∧(y=n-Vj+s)},φBA(y,n)={∧(1⩽z⩽n-Vj)∧(y=n-Vj+s)((yA,nA);(yB,nB),s,z):(n=nA+nB)∧(y=yA+yB+z+s)∧(0⩽s⩽smaxA(n))∧(1⩽z⩽n-Vj)∧(y=n-Vj+s)},φAB(y,n)={∧1(⩽z⩽n-Vj)∧(y=n-Vj+s)((yA,nA);(yB,nB),s,z):(n=nA+nB)∧(y=yA+yB+z+s)∧(0⩽s⩽smaxB(n))∧(1⩽z⩽n-Vj)∧(y=n-Vj+s)}.In line with the adopted notation, the state probability(y,n) (for n>Vj) can be written as follows:
(35)∀n>Vj[Ry,n]V0,d{j}A∪B=kP(A)∑γBA(y,n)∪φBA(y,n)‍Pn(s∣A)×[RyA,nA]V0,d{j}A[RyB,nB]V0,d{j}B+kP(B)∑γAB(y,n)∪φAB(y,n)‍Pn(s∣B)×[RyA,nA]V0,d{j}A[RyB,nB]V0,d{j}B.
Equations (33) and (35) can be combined and eventually rewritten in the following form:
(36)[Ry,n]V0,d{j}A∪B=k×{∑nA=0n‍∑yA=0y‍[RyA,nA]V0,d{j}A[Ry-yA,n-nB]V0,d{j}Bforn⩽Vj,∑nA=0n‍nAPn(y+Vj-n∣A)+nBPn(y+Vj-n∣B)n×∑z=0n-Vj‍∑yA=0n-Vj‍R[yA,nA]V0,d{j}A×R[n-Vj-yA-z,n-nA]V0,d{j}Bforn>Vj.
The way (33) is transformed to the form (36) is described in Appendix B.


## 4. Numerical Results

To confirm the accuracy and effectiveness of the proposed convolution method, the results of the blocking probability in the overflow systems obtained on the basis of the analytical calculations, both for the continuous method (Section3.5.1), and the discrete method (Section 3.5.2), were compared with the results of the simulation experiments. Additionally, in the case of call streams generated by infinite number of traffic sources, the results obtained on the basis of a modified Hayward method [17] are presented. The characteristics presented in the graphs show the dependence between the blocking probability of each of the offered classes in the whole system and offered traffic a, offered to a single BBU of the primary group:
(37)∀j∈Ka=∑mi{j}∈Mj‍Ai(j)ti(j)Vj.The event-oriented discrete simulation method was used for simulation [45, 46]. Each simulation experiment consisted of 10 series. The length of each series was determined by the number of lost calls (at least 200000 lost calls for each traffic class). The 99% confidence intervals were calculated according to the Student-Fisher distribution.The study was carried out for the telecommunications systems defined in Table1. The systems are offered three types of Erlang (Poisson call streams), Engset (binomial call streams), and Pascal (negative binomial call streams) traffic streams [20, 47]. The selected types of traffic cover three different types of the dependence between the mean arrival rates of calls and the occupancy state of the system: (1) the mean arrival rate of new calls does not depend on the occupancy state of the system (Erlang traffic), (2) the mean arrival rate of new calls decreases with the increase in the occupancy state of the system (Engset traffic), and (3) the mean arrival rate of new calls increases with the increase in the occupancy state of the system (Pascal traffic).Table 1
Parameters of the considered systems.
No.
V
0
V
1
t
1
(
1
)
Sources type
t
2
(
1
)
Sources type
V
2
t
1
(
2
)
Sources type
t
2
(
2
)
Sources type
1
20
15
1
Poisson
2
Poisson
15
3
Poisson
4
Poisson
2
20
15
1
Binomial
2
Binomial
15
3
Binomial
4
Binomial
3
20
15
1
Negative binomial
2
Negative binomial
15
3
Negative binomial
4
Negative binomial
4
20
15
1
Poisson
2
Poisson
15
3
Binomial
4
Binomial
5
20
15
1
Poisson
2
Poisson
15
3
Negative binomial
4
Negative binomialThe graphs presented in Figures5, 6, 7, 8, and 9 showing the blocking probability, determined on the basis of the two-dimensional convolution algorithm, both continuous and discrete, as well as the results of the simulation experiments, are presented for each of the systems under consideration. In addition, for the systems 1 and 2, the results obtained on the basis of the generalized Hayward method are included. The confidential interval in the graphs is too small to be visible due to the length and the number of series in the simulation.Blocking probability in system no. 1 with overflow traffic (V1=15, V2=15, t1(1)=1 (Poisson); t2(1)=2 (Poisson); t1(2)=3 (Poisson); t2(2)=4 (Poisson); V0=20).
(a)
Two-dimensional continuous convolution algorithm
(b)
Two-dimensional discrete convolution algorithm
(c)
Generalized Hayward methodBlocking probability in system no. 2 with overflow traffic (V1=15, V2=15; t1(1)=1, S11=60 (binomial); t2(1)=2, S21=30 (binomial); t1(2)=3, S12=20 (binomial); t2(2)=4, S22=15 (binomial); V0=20).
(a)
Two-dimensional continuous convolution algorithm
(b)
Two-dimensional discrete convolution algorithmBlocking probability in system no. 3 with overflow traffic (V1=15, V2=15, t1(1)=1, N11=60 (negative binomial); t2(1)=2, N21=30 (negative binomial); t1(2)=3, N12=20 (negative binomial); t2(2)=4, N22=15 (negative binomial); V0=20).
(a)
Two-dimensional continuous convolution algorithm
(b)
Two-dimensional discrete convolution algorithmBlocking probability in system no. 4 with overflow traffic (V1=15, V2=15, t1(1)=1 (Poisson); t2(1)=2 (Poisson); t1(2)=3, S12=20 (binomial); t2(2)=4, S22=15 (binomial); V0=20).
(a)
Two-dimensional continuous convolution algorithm
(b)
Two-dimensional discrete convolution algorithmBlocking probability in system no. 5 with overflow traffic (V1=15, V2=15, t1(1)=1 (Poisson); t2(1)=2 (Poisson); N12=20 (negative binomial), t1(2)=3; t2(2)=4, N22=15 (negative binomial); V0=20).
(a)
Two-dimensional continuous convolution algorithm
(b)
Two-dimensional discrete convolution algorithmWe can notice that both convolution algorithms, continuous and discrete, ensure higher accuracy than the modified Hayward method. Additionally, we can observe, that the continuous algorithm lowers probabilities of states that belong to the blocking area for classes that demand the highest number of BBUs in relation to the remaining classes. This phenomenon can be justified in the following way. The continuous method assumes a possibility of servicing a single call by the primary and the alternative group. In this way, the model assumes a better use of resources than it is actually the case in a real system. As a consequence of the adoption of this assumption, states in which some resources of primary groups would not be busy do not occur. This leads to an increase in the number of free resources of the alternative group and, in consequence, to an increase in the number of serviced calls that require a higher number of BBUs. At the same time, elimination of states in which the primary group would have free resources leads to an increase in the blocking state for calls that demand a lower number of resources. As a result, the probabilities determined for classes that demand a higher number of BBUs are lower than those obtained in real systems, while blocking probabilities for classes that demand a low number of BBUs are overestimated. The highest accuracy of calculation process is ensured by the discrete algorithm.


## 5. Conclusions

The paper proposes new methods for modelling of network systems with traffic overflow. The methods are based on the proposed two-dimensional convolution algorithm and can be applied to determine the parameters of the overflow system exclusively on the basis of the knowledge of the parameters of offered traffic and the volume of the resources. Additionally, the method makes it possible to determine the blocking probability in systems that are offered traffic streams of any type, which is an important advantage of the proposed method. The proposed methods differ considerably in the way two-dimensional distributions[R]V0,djmj that describe the occupancy of the primary group j and the alternative group are determined.The first method for determination of the two-dimensional convolution, the so-called continuous method, gives the same results as the simultaneous convolution method [44]. The proposed algorithm offers, however, a lower order of computational complexity and can be used for modelling systems in which the primary group is offered multiple call classes. The other method, the so-called discrete method for determination of the two-dimensional convolution, gives more accurate results with the same order of computational complexity retained.It should be emphasized that the methods for modelling multirate systems with traffic overflow developed in [17] aimed at determining the blocking probability only in alternative resources (groups). Moreover, all hitherto known methods for modelling systems with both single-service overflow traffic (ERT method and Hayward method), and with multiservice overflow traffic [17], require the overflow traffic parameters to be first determined in the process of a determination of losses in the overflow system. Consequently, these methods are limited to modelling only systems with Erlang and Engset traffic streams, whereas the method proposed in the present article makes it possible to model systems with multiservice overflow traffic generated by sources of any type.



---

*Source: 852082-2013-06-10.xml*