# Resource Management in Satellite Communication Systems: Heuristic Schemes and Algorithms

Authors: Shahaf I. Wayer; Arie Reichman
Journal: Journal of Electrical and Computer Engineering
 (2012)

---

## Abstract

The high cost of frequency bandwidth in satellite communication emphasizes the need for good algorithms to cope with the resource allocation problem. In systems using DVB-S2 links, the optimization of resource allocation may be related to the classical multi-knapsack problem. Resource management should be carried out according to the requests of subscribers, their priority levels, and assured bandwidths. A satisfaction measure is defined to estimate the allocation processes. Heuristic algorithms together with some innovative scaling schemes are presented and compared using Monte Carlo simulation based on a traffic model introduced here.


---

## Body

## 1. Introduction

### 1.1. DVB-S2 in Satellite Communication

The most popular standard today in satellite communication is DVB-S2 [1], designed for transmission of digital television broadcasting. This relatively new standard is gradually replacing the classic DVB-S [2] in new systems as well as in existing systems. It is also used in new VSAT systems in forward link as well as in reverse link, in cases when the required data rates are higher than those supplied by DVB-RCS [3]. DVB-S2 is also used in satellite modems for point-to-point applications. In this paper we focus on a system that consists of DVB-S2 links with dynamic changes in the required parameters of the links due to changes in the traffic demands.


### 1.2. Resource Management

In order to save the operational cost of the satellite communication system, transmissions that share the total available frequency band have to be fairly divided according to the requirements of the subscribers [4]. For a star-type system with a central HUB that communicates with subscriber terminals, the control is conducted by the control center in the HUB according to subscriber needs. For other type of systems, like point-to-point, the control is conducted by a dedicated communication and control system that operates in addition to point-to-point links.Regardless of the way the control is performed, a resource allocation algorithm has to be designed for optimal performances and best satisfaction.In commercial systems run by a service provider, the Service Level Agreement (SLA), which is a set of parameters that defines the capabilities and the paid rights of every terminal in the system, connects the service provider and the subscribers. The Committed Information Rate (CIR) is the rate that is guaranteed by the system. Typically it is low enough so that the system can guarantee the user of this specific rate. The Peak Information Rate (PIR), on the other hand, is the maximum rate that may be allocated. When the user asks for a rate higher than CIR and lower or equal to PIR, the system will allocate this rate if available. When a user asks for a rate higher than PIR, the system will consider it as if the request was equal to PIR. The service provider has difficulty in providing the Committed Rate with certainty. In this research, we assumed that the bandwidth of a terminal is proportional to its rate. We use the termassured bandwidth as a quantity that the system can provide most of the time but not always.The terminals have priority levels that determine their significance according to their payment to the service provider. In a situation of low resources, requests from high priority terminals may cause the system to decrease the rate of low priority terminals to their minimum.In the course of the resource allocation cycle, subscribers issue requests for bandwidth. The bandwidths they own are removed from the spectrum list. The resource allocation process follows, and the bandwidths are reconfigured over the spectrum. This whole process of removing spectrum bands and reconfiguring the spectrum with the newly allocated bands creates gaps (holes) in the spectrum, resulting in a fragmented spectrum. The task of the resource allocation algorithms is to fit the requests into those holes in the spectrum.In [5] it was shown that this task is equivalent to the multi-knapsack problem (MKP). Two heuristic algorithms were presented together with a single scaling scheme for the bandwidth requests. Scaling down the requests is necessary when their sum exceeds the available bandwidth budget, and utilizing the scaling scheme improves the algorithm results.In this paper, we review the MKP problem and suggest an extension to it. We then present our idea of combiningheuristic algorithms with scaling down schemes. Some innovative schemes are suggested to maximize a defined satisfaction measure and at the same time support the allocation of the assured bandwidth for each subscriber.In Section2, the system’s quality of service parameters is presented and performance criteria are defined.  The resource management process is presented in Section 3, including the mathematical background for the MKP problem with extension, together with a problem reformulation that may suggest a scaling down strategy as a natural way to solve the extended MKP problem.Section4 focuses on the algorithms used for the resource allocation, while Section 5 shows the significance of the scaling schemes. Several schemes are presented, based on the quality of service parameters. Then a simplified example is presented to illustrate the whole process. The techniques used to model the system dynamics are presented in Section 6, while Section 7 compares the performances obtained in simulation. Finally, we draw our conclusions in Section 8.


## 1.1. DVB-S2 in Satellite Communication

The most popular standard today in satellite communication is DVB-S2 [1], designed for transmission of digital television broadcasting. This relatively new standard is gradually replacing the classic DVB-S [2] in new systems as well as in existing systems. It is also used in new VSAT systems in forward link as well as in reverse link, in cases when the required data rates are higher than those supplied by DVB-RCS [3]. DVB-S2 is also used in satellite modems for point-to-point applications. In this paper we focus on a system that consists of DVB-S2 links with dynamic changes in the required parameters of the links due to changes in the traffic demands.


## 1.2. Resource Management

In order to save the operational cost of the satellite communication system, transmissions that share the total available frequency band have to be fairly divided according to the requirements of the subscribers [4]. For a star-type system with a central HUB that communicates with subscriber terminals, the control is conducted by the control center in the HUB according to subscriber needs. For other type of systems, like point-to-point, the control is conducted by a dedicated communication and control system that operates in addition to point-to-point links.Regardless of the way the control is performed, a resource allocation algorithm has to be designed for optimal performances and best satisfaction.In commercial systems run by a service provider, the Service Level Agreement (SLA), which is a set of parameters that defines the capabilities and the paid rights of every terminal in the system, connects the service provider and the subscribers. The Committed Information Rate (CIR) is the rate that is guaranteed by the system. Typically it is low enough so that the system can guarantee the user of this specific rate. The Peak Information Rate (PIR), on the other hand, is the maximum rate that may be allocated. When the user asks for a rate higher than CIR and lower or equal to PIR, the system will allocate this rate if available. When a user asks for a rate higher than PIR, the system will consider it as if the request was equal to PIR. The service provider has difficulty in providing the Committed Rate with certainty. In this research, we assumed that the bandwidth of a terminal is proportional to its rate. We use the termassured bandwidth as a quantity that the system can provide most of the time but not always.The terminals have priority levels that determine their significance according to their payment to the service provider. In a situation of low resources, requests from high priority terminals may cause the system to decrease the rate of low priority terminals to their minimum.In the course of the resource allocation cycle, subscribers issue requests for bandwidth. The bandwidths they own are removed from the spectrum list. The resource allocation process follows, and the bandwidths are reconfigured over the spectrum. This whole process of removing spectrum bands and reconfiguring the spectrum with the newly allocated bands creates gaps (holes) in the spectrum, resulting in a fragmented spectrum. The task of the resource allocation algorithms is to fit the requests into those holes in the spectrum.In [5] it was shown that this task is equivalent to the multi-knapsack problem (MKP). Two heuristic algorithms were presented together with a single scaling scheme for the bandwidth requests. Scaling down the requests is necessary when their sum exceeds the available bandwidth budget, and utilizing the scaling scheme improves the algorithm results.In this paper, we review the MKP problem and suggest an extension to it. We then present our idea of combiningheuristic algorithms with scaling down schemes. Some innovative schemes are suggested to maximize a defined satisfaction measure and at the same time support the allocation of the assured bandwidth for each subscriber.In Section2, the system’s quality of service parameters is presented and performance criteria are defined.  The resource management process is presented in Section 3, including the mathematical background for the MKP problem with extension, together with a problem reformulation that may suggest a scaling down strategy as a natural way to solve the extended MKP problem.Section4 focuses on the algorithms used for the resource allocation, while Section 5 shows the significance of the scaling schemes. Several schemes are presented, based on the quality of service parameters. Then a simplified example is presented to illustrate the whole process. The techniques used to model the system dynamics are presented in Section 6, while Section 7 compares the performances obtained in simulation. Finally, we draw our conclusions in Section 8.


## 2. System Parameters and Performance Criteria

### 2.1. The Quality of Service Parameters

Parameters of quality of service determine the capability of providing better service to network traffic. The system we study assumes some quality of service characteristics for each subscriber. The algorithms presented here take into consideration two such parameters.(a) Priority Level
A priority factorwk is assigned to each subscriber type, such that higher level subscribers get priority in allocation of bandwidth following user request.(b) Assured Level
Subscribers are guaranteed (with a high probability) to receive the bandwidth they request up to some assured amountΩk.  Any bandwidth above this is optional, up to a maximal value determined by PIR.These two parameters are used in the definition of thesatisfaction measure function and play an important role in algorithm design and optimization of bandwidth utilization.


### 2.2. Disconnections

The fact that the DVB-S2 links were designed for fixed center frequency and symbol rate would cause disconnections while changing them. Therefore, allocating a new bandwidth to a user causes a disconnection to the subscriber. To take into account this fact, we useeffective allocated bandwidthA related to the allocated bandwidthA0 according to:
(1)A={β⋅A0,(ifdisconnected),A0,(otherwise),
where β<1 is a constant expressing the effect of disconnection period, and the assumed dissatisfaction it causes. In this paper, we narrow ourselves to the case where users are not moved in the frequency range if they have no request for a change.


### 2.3. The Satisfaction Criterion

Resource allocation is conducted according to the requests of subscribers, their priority levels, and their assured bandwidths. For a subscriber with assured bandwidthΩ, a requested bandwidth R, and an effective allocated bandwidth A, and assuming that R≥A, we suggest the satisfaction measure S that may be calculated for a factor α<1:
(2)S(R,A,Ω)={Ω+α⋅(A-Ω)Ω+α⋅(R-Ω),(R>A≥Ω),AΩ+α⋅(R-Ω),(R>Ω≥A),AR,(Ω>R≥A).The satisfaction function ranges from 0 to 1. The maximum satisfaction valueS=1 is reached when the allocated bandwidth is equal to the requested bandwidth. Also, one can see that when A>Ω, the contribution of any increment ΔA to the function is smaller by a factor of α<1 than the contribution of the same increment ΔA when A<Ω.In order to reduce the number of variables involved in this formula, we express the satisfaction function in terms of thenormalized bandwidth variables:
(3)r=RΩ,a=AΩ,
such that the satisfaction measure may be defined as:
(4)S(r,a)={1+α⋅(a-1)1+α⋅(r-1),(r>a≥1),11+α⋅(r-1),(r>1≥a),ar,(1>r≥a).This is a concave function increasing monotonically both in ther direction and in the a direction.For a given set of users with normalized requests and allocated bandwidthsri, ai and priority factors wi, the total (weighted) satisfaction S¯ is defined as:
(5)S¯=∑iwi⋅S(ri,ai)∑iwi.The total satisfaction function gets the maximum of 1 when all requests are fulfilled. This quantitative measure may be used to compare the performance of the various algorithms and schemes.


### 2.4. The Requests Scale Down Criterion

While resource allocation algorithms fit the bandwidth requests into theholes in the spectrum, some holes may become under populated and some over-populated.The first situation (under population) happens when the sum of requests inserted into a hole does not fully cover it.The other one (over population) happens when the sum of requests assigned into a hole is greater than the capacity of the hole. In this situation the requests assigned to that hole should be scaled down to fit into the hole capacity.Let{Rj(k)} be the set of requests allocated into a holeH(k), Then the total amount δ of the requests bandwidth that is scaled down is:
(6)δ=∑kmax⁡([∑jRj(k)]-H(k),0).The amountδ is the requests scale down factor. It measures the effectiveness of the algorithms in finding a good arrangement of the requests into the gaps (holes) in spectrum. A lower value indicates better algorithm performance.


## 2.1. The Quality of Service Parameters

Parameters of quality of service determine the capability of providing better service to network traffic. The system we study assumes some quality of service characteristics for each subscriber. The algorithms presented here take into consideration two such parameters.(a) Priority Level
A priority factorwk is assigned to each subscriber type, such that higher level subscribers get priority in allocation of bandwidth following user request.(b) Assured Level
Subscribers are guaranteed (with a high probability) to receive the bandwidth they request up to some assured amountΩk.  Any bandwidth above this is optional, up to a maximal value determined by PIR.These two parameters are used in the definition of thesatisfaction measure function and play an important role in algorithm design and optimization of bandwidth utilization.


## 2.2. Disconnections

The fact that the DVB-S2 links were designed for fixed center frequency and symbol rate would cause disconnections while changing them. Therefore, allocating a new bandwidth to a user causes a disconnection to the subscriber. To take into account this fact, we useeffective allocated bandwidthA related to the allocated bandwidthA0 according to:
(1)A={β⋅A0,(ifdisconnected),A0,(otherwise),
where β<1 is a constant expressing the effect of disconnection period, and the assumed dissatisfaction it causes. In this paper, we narrow ourselves to the case where users are not moved in the frequency range if they have no request for a change.


## 2.3. The Satisfaction Criterion

Resource allocation is conducted according to the requests of subscribers, their priority levels, and their assured bandwidths. For a subscriber with assured bandwidthΩ, a requested bandwidth R, and an effective allocated bandwidth A, and assuming that R≥A, we suggest the satisfaction measure S that may be calculated for a factor α<1:
(2)S(R,A,Ω)={Ω+α⋅(A-Ω)Ω+α⋅(R-Ω),(R>A≥Ω),AΩ+α⋅(R-Ω),(R>Ω≥A),AR,(Ω>R≥A).The satisfaction function ranges from 0 to 1. The maximum satisfaction valueS=1 is reached when the allocated bandwidth is equal to the requested bandwidth. Also, one can see that when A>Ω, the contribution of any increment ΔA to the function is smaller by a factor of α<1 than the contribution of the same increment ΔA when A<Ω.In order to reduce the number of variables involved in this formula, we express the satisfaction function in terms of thenormalized bandwidth variables:
(3)r=RΩ,a=AΩ,
such that the satisfaction measure may be defined as:
(4)S(r,a)={1+α⋅(a-1)1+α⋅(r-1),(r>a≥1),11+α⋅(r-1),(r>1≥a),ar,(1>r≥a).This is a concave function increasing monotonically both in ther direction and in the a direction.For a given set of users with normalized requests and allocated bandwidthsri, ai and priority factors wi, the total (weighted) satisfaction S¯ is defined as:
(5)S¯=∑iwi⋅S(ri,ai)∑iwi.The total satisfaction function gets the maximum of 1 when all requests are fulfilled. This quantitative measure may be used to compare the performance of the various algorithms and schemes.


## 2.4. The Requests Scale Down Criterion

While resource allocation algorithms fit the bandwidth requests into theholes in the spectrum, some holes may become under populated and some over-populated.The first situation (under population) happens when the sum of requests inserted into a hole does not fully cover it.The other one (over population) happens when the sum of requests assigned into a hole is greater than the capacity of the hole. In this situation the requests assigned to that hole should be scaled down to fit into the hole capacity.Let{Rj(k)} be the set of requests allocated into a holeH(k), Then the total amount δ of the requests bandwidth that is scaled down is:
(6)δ=∑kmax⁡([∑jRj(k)]-H(k),0).The amountδ is the requests scale down factor. It measures the effectiveness of the algorithms in finding a good arrangement of the requests into the gaps (holes) in spectrum. A lower value indicates better algorithm performance.


## 3. The Resource Allocation Process

The disconnections caused while changing frequency and symbol rates pose a serious constraint in the design of optimal allocation algorithms. Therefore, links of terminals that did not require any change should stay in the same location in the spectrum, while new requests should be allocated only in the free portions (holes) of the spectrum.In this part, we will show that this problem is equivalent to the multi-knapsack problem (MKP) [6] known in computational complexity theory and then draw a scheme for a computational process to cope with it.


### 3.1. Resource Allocation as a Complexity Theory Problem

The connection between the MKP problem and satellite communication resource allocation was already reported by Birmani [7]. However, his work deals with power allocation and burst scheduling problems, which are inherently quite different in their nature than the bandwidth allocation problems in our concern.The association between resource allocation in communication and the MKP problem was already observed by Rajkumar et al. [8]. Their research was on a QoS-based Resource Allocation Model (QRAM) for satisfying multiple quality-of-service dimensions in a resource-constrained environment. Using this model, available system resources can be apportioned across multiple applications, thus maximizing the net utility that accrues to the end users of those applications. They showed that the Q-RAM problem of finding the optimal resource allocation to satisfy multiple QoS dimensions is NP hard. There is a similarity between the resources, QoS, and utility factor in their research and the bandwidth, priority level, and satisfaction function in this research. However, in our work the satisfaction function is different than their utility factor and the methods we suggest are simpler to implement.The task of the resource allocation algorithms is to find an optimal match between a set ofN requests {Ri∣0≤i<N} and a set of M holes {H(j)∣0≤j<M} in a spectrum such that all the Nj requests are inserted into those holes:
(7)∑i=0NjRKj(i)≤H(j),
where {Kj} are M disjoint subsets of indexes: the size of set Kj is Nj, such that their union covers the set {1,…,N}:
(8)⋂Kj=ϕ,⋃Kj={i∣i≤N},
where Kj(i) is the ith element in the set Kj.The algorithm theory classifies such a problem as a variation of themulti-knapsack problem. Given M containers (knapsacks) with capacities H(j) and N items with values Ri, the task is to split the set {Ri} into M disjoint subsets, such that the sum of item values in each subset will not exceed the given capacities H(j) as in (7).Although the set of inequalities in the problem definition resembles a typical linear programming formulation, it is not a linear programming problem. Instead, it belongs to a family ofsubset sum problems known as knapsack problems.The knapsack problem is part of the family of combinatorial NP-complete problems [9], meaning that it is computationally difficult to solve in general (except for a O(MN) brute force solution).  It is difficult enough to be chosen as a trapdoor cryptographic function (i.e., the Merkle-Hellman cryptosystem).Yet the resource allocation problem  does not fit the exact definition of a knapsack problem. There is one essential difference: when (7) cannot be fully satisfied, then the target of optimization should be replaced by:
(9)∑i=0NjCi(j)⋅RKj(i)≤H(j),(0<Ci(j)≤1),
such that the factors Ci(j)  are maximal.This is a “softer” version of the original problem (7). It extends the problem adding some degree of complexity (finding the factors Ci(j)). On the other hand, it eases the task somewhat, adding several degrees of freedom so that a solution can be found, even in situations where the original problem is practically insolvable.So, because this is an NP-Hard problem, we shall not try to solve it fully. Instead we may design some practical heuristic algorithms and reach suboptimal solutions [10].


### 3.2. The Resource Management Process

The resource allocation problem is too complex to be solved at once. Instead of solving (9) directly by a single algorithm, we suggest splitting it into three subproblems:(1)
find an initial approximation to theCi(j) factors;(2)
solve the main resource allocation problem;(3)
find the final values of theCi(j) factors.Following this model, the entire resource management process consists of three stages, as illustrated in Figure 1. (1)
The prescaling Step. In order for the resource allocation algorithms to operate properly, subscriber requests for bandwidthcannot exceed the available bandwidth budget. However, this situation does occur frequently. To cope with this problem, we suggest the pre-scaling process, to scale down subscriber requests according to the priority factors wi and the assured bandwidths Ωj.(2)
The resource allocation algorithm finds the best fit between the requests and theholes in the spectrum.(3)
The postscaling step is performed in one of the following situations:
(a)
if the sum of the allocated requests assigned to ahole is bigger than the size of the hole, then the requests should be downscaled;(b)
if the sum of the allocated requests assigned to a hole is smaller than the size of thehole, and the requests were downscaled (by means of pre-scaling stage), then they may be upscaled. The allocated bandwidths are scaled up such that their new value will not exceed the original requests, and in addition their sum will not exceed the size of the hole.In either case, the scaling is conducted according to the priority factors wi and the assured bandwidths Ωi in a manner very similar to the prescale stage.Figure 1
The resource allocation process flow chart.The feedback in Figure1 marks the transition to the next phase of the algorithm, when new requests are generated.


## 3.1. Resource Allocation as a Complexity Theory Problem

The connection between the MKP problem and satellite communication resource allocation was already reported by Birmani [7]. However, his work deals with power allocation and burst scheduling problems, which are inherently quite different in their nature than the bandwidth allocation problems in our concern.The association between resource allocation in communication and the MKP problem was already observed by Rajkumar et al. [8]. Their research was on a QoS-based Resource Allocation Model (QRAM) for satisfying multiple quality-of-service dimensions in a resource-constrained environment. Using this model, available system resources can be apportioned across multiple applications, thus maximizing the net utility that accrues to the end users of those applications. They showed that the Q-RAM problem of finding the optimal resource allocation to satisfy multiple QoS dimensions is NP hard. There is a similarity between the resources, QoS, and utility factor in their research and the bandwidth, priority level, and satisfaction function in this research. However, in our work the satisfaction function is different than their utility factor and the methods we suggest are simpler to implement.The task of the resource allocation algorithms is to find an optimal match between a set ofN requests {Ri∣0≤i<N} and a set of M holes {H(j)∣0≤j<M} in a spectrum such that all the Nj requests are inserted into those holes:
(7)∑i=0NjRKj(i)≤H(j),
where {Kj} are M disjoint subsets of indexes: the size of set Kj is Nj, such that their union covers the set {1,…,N}:
(8)⋂Kj=ϕ,⋃Kj={i∣i≤N},
where Kj(i) is the ith element in the set Kj.The algorithm theory classifies such a problem as a variation of themulti-knapsack problem. Given M containers (knapsacks) with capacities H(j) and N items with values Ri, the task is to split the set {Ri} into M disjoint subsets, such that the sum of item values in each subset will not exceed the given capacities H(j) as in (7).Although the set of inequalities in the problem definition resembles a typical linear programming formulation, it is not a linear programming problem. Instead, it belongs to a family ofsubset sum problems known as knapsack problems.The knapsack problem is part of the family of combinatorial NP-complete problems [9], meaning that it is computationally difficult to solve in general (except for a O(MN) brute force solution).  It is difficult enough to be chosen as a trapdoor cryptographic function (i.e., the Merkle-Hellman cryptosystem).Yet the resource allocation problem  does not fit the exact definition of a knapsack problem. There is one essential difference: when (7) cannot be fully satisfied, then the target of optimization should be replaced by:
(9)∑i=0NjCi(j)⋅RKj(i)≤H(j),(0<Ci(j)≤1),
such that the factors Ci(j)  are maximal.This is a “softer” version of the original problem (7). It extends the problem adding some degree of complexity (finding the factors Ci(j)). On the other hand, it eases the task somewhat, adding several degrees of freedom so that a solution can be found, even in situations where the original problem is practically insolvable.So, because this is an NP-Hard problem, we shall not try to solve it fully. Instead we may design some practical heuristic algorithms and reach suboptimal solutions [10].


## 3.2. The Resource Management Process

The resource allocation problem is too complex to be solved at once. Instead of solving (9) directly by a single algorithm, we suggest splitting it into three subproblems:(1)
find an initial approximation to theCi(j) factors;(2)
solve the main resource allocation problem;(3)
find the final values of theCi(j) factors.Following this model, the entire resource management process consists of three stages, as illustrated in Figure 1. (1)
The prescaling Step. In order for the resource allocation algorithms to operate properly, subscriber requests for bandwidthcannot exceed the available bandwidth budget. However, this situation does occur frequently. To cope with this problem, we suggest the pre-scaling process, to scale down subscriber requests according to the priority factors wi and the assured bandwidths Ωj.(2)
The resource allocation algorithm finds the best fit between the requests and theholes in the spectrum.(3)
The postscaling step is performed in one of the following situations:
(a)
if the sum of the allocated requests assigned to ahole is bigger than the size of the hole, then the requests should be downscaled;(b)
if the sum of the allocated requests assigned to a hole is smaller than the size of thehole, and the requests were downscaled (by means of pre-scaling stage), then they may be upscaled. The allocated bandwidths are scaled up such that their new value will not exceed the original requests, and in addition their sum will not exceed the size of the hole.In either case, the scaling is conducted according to the priority factors wi and the assured bandwidths Ωi in a manner very similar to the prescale stage.Figure 1
The resource allocation process flow chart.The feedback in Figure1 marks the transition to the next phase of the algorithm, when new requests are generated.


## 4. The Resource Allocation Algorithms

Two heuristic algorithms are presented to solve the main resource allocation problem:(i)
the Fast MKP solver;(ii)
the IBF (Insert to Best Fit) MKP solver.Both algorithms are classified asgreedy algorithms. At each stage they take the locally optimal choice rather than aiming for the global optimum. Such algorithms are widely used to solve heuristically dynamic programming problems.


### 4.1. The Fast MKP Algorithm

When allocating a request to a hole, we define the residue remainder after the allocation, that is, the size of the hole less the size of the request. TheFast MKP algorithm adopts a strategy of largest residues first, that is, it fits the largest requests to holes with the largest residue in decreasing order.In order to perform this efficiently, we maintain a binary tree ofhole items (sorted by the residue size) to enable a search and insert operation in O(log(M)) time steps [11].The algorithm consists of the following steps.(1)
Make a sorted list of requests indecreasing order (largest to smallest) and a binary tree of residues associated with the hole items.(2)
Fit thelargest request to the biggest residue hole item.(3)
Update the residue value corresponding to thehole item and insert it back into the tree according to the residue value.(4)
Discard the request from the list of requests.(5)
Repeat steps (2)–(4) until the request list is empty.This algorithm is efficient with respect to run time and memory consumption.


### 4.2. The IBF MKP Algorithm

This algorithm adopts a strategy ofbest fit residue, that is, it fits requests in decreasing order into holes with the residue that fits best (if no residue fits, it inserts to the largest one—). A best fit for any Rj over a decreasing series of residues {Zi}, is any Zi, such that Zi+1<Rj≤Zi.(1)
Start with a sorted list of requests indecreasing order (largest to smallest) and a binary tree of residues associated with the hole items.(2)
Insert the largest request into thehole item, with the smallest residue that is larger than the request.(3)
If there is no such residue, insert the request into thehole with the largest residue.(4)
Update the residue value corresponding to thehole item and insert it back into the tree according to the residue new value.(5)
Discard the request from the list of requests.(6)
Repeat steps (2)–(5) until the request list is empty.The purpose of stage (3) in the algorithm is to ensure thatall the requests are inserted into the holes, even when holes become overpopulated. This may involve temporarily assigning negative values to some residues. This is quite legitimate, because the residue values have instrumental meaning only. The postscaling stage described in next section would resolve this problem.


## 4.1. The Fast MKP Algorithm

When allocating a request to a hole, we define the residue remainder after the allocation, that is, the size of the hole less the size of the request. TheFast MKP algorithm adopts a strategy of largest residues first, that is, it fits the largest requests to holes with the largest residue in decreasing order.In order to perform this efficiently, we maintain a binary tree ofhole items (sorted by the residue size) to enable a search and insert operation in O(log(M)) time steps [11].The algorithm consists of the following steps.(1)
Make a sorted list of requests indecreasing order (largest to smallest) and a binary tree of residues associated with the hole items.(2)
Fit thelargest request to the biggest residue hole item.(3)
Update the residue value corresponding to thehole item and insert it back into the tree according to the residue value.(4)
Discard the request from the list of requests.(5)
Repeat steps (2)–(4) until the request list is empty.This algorithm is efficient with respect to run time and memory consumption.


## 4.2. The IBF MKP Algorithm

This algorithm adopts a strategy ofbest fit residue, that is, it fits requests in decreasing order into holes with the residue that fits best (if no residue fits, it inserts to the largest one—). A best fit for any Rj over a decreasing series of residues {Zi}, is any Zi, such that Zi+1<Rj≤Zi.(1)
Start with a sorted list of requests indecreasing order (largest to smallest) and a binary tree of residues associated with the hole items.(2)
Insert the largest request into thehole item, with the smallest residue that is larger than the request.(3)
If there is no such residue, insert the request into thehole with the largest residue.(4)
Update the residue value corresponding to thehole item and insert it back into the tree according to the residue new value.(5)
Discard the request from the list of requests.(6)
Repeat steps (2)–(5) until the request list is empty.The purpose of stage (3) in the algorithm is to ensure thatall the requests are inserted into the holes, even when holes become overpopulated. This may involve temporarily assigning negative values to some residues. This is quite legitimate, because the residue values have instrumental meaning only. The postscaling stage described in next section would resolve this problem.


## 5. The Scaling Schemes

The algorithms presented above perform poorly under a shortage of bandwidth resources. We suggest activating some scaling schemes when the sum of the requests is greater than the sum of the holes. In those cases, such schemes can sharefairly the available bandwidth resources, taking into consideration the quality of service parameters in order to resolve the users' diversity issues.For a set of requests{Ri} and a set of holes{H(j)} such that R=∑Ri and H=∑Hi we introduce scaling schemes to take place when R>H.Introducing scaling stages into the allocation process is crucial. It is analogous toadding filters at the entrance and outlet of an electronic system in order to adjust the signal to the dynamic range of a system. The design of scaling schemes may dramatically influence the overall performance of the allocating process just like filters that affect system’s behavior.We present first the schemes for thedownscaling performed in the prescaling step. In correspondence with the quality of service levels [12], we consider several levels of scaling schemes in accordance with the number of parameters taken into consideration:(i)
the basic scheme, which takes no parameters;(ii)
the priority-oriented scheme, which takes into consideration the priority factors wi only;(iii)
advanced schemes, taking into consideration the assured bandwidthΩi as well as the priority factors wi.


### 5.1. The Basic Scaling Scheme

In absence of any priority criteria for sharing the bandwidth, the requests are simply scaled down proportionally to their value:(10)Rk(new)=HR⋅Rk.Such a scheme corresponds to a network system that supportsbest-effort subscribers only, with no quality of service parameters.


### 5.2. The Priority-Oriented Scaling Scheme

This scheme takes into consideration only thepriority factorswi. Such a scheme is applicable for network systems that support at least the differentiated service level.The amount of bandwidth to be reduced is the difference between the sum of requests and the sum of holes:(11)D=R-H.This amount should be shared proportionally to the requestsRj (larger requests are reduced more than small ones) and inversely proportional to the priority factors wj (higher priority requests are reduced less than the lower ones). So, the request Rj should be reduced by amount dj given by: dj=C·(Rj/wj) such that D=∑jdj is the total reduction.Hence:D=C·(∑jRj/wj) where C is some proportion factor that can be written as:
(12)C=D∑kRk/wk=R-H∑kRk/wk.And finally, the requests are downscaled according to:(13)Rj(new)=(1-Cwj)⋅Rj.This scheme works unconditionally (but it does not take into consideration the assured bandwidthΩ).


### 5.3. Advanced Schemes

High-quality network systems should take into consideration the subscribers’assured bandwidthsΩi, as well as their priority factorswi. The constraint imposed by the assured bandwidth condition can be expressed as:
(14)Ri(new)≥min⁡(Ri,Ωi).This condition could be met only when:(15)∑Hi≥∑min⁡(Ri,Ωi).When this condition is satisfied, we can allocate bandwidth taking into account both the priority factors and the assured bandwidths. Otherwise, thepriority-oriented scaling scheme should be used.Our strategy is to grant all the requests below the assured bandwidth and scale downonly the others.The two schemes we present here have the same “prolog”, and differ only in the final stage.(0)
Start with a set of indexesI={1,…,N}, where N is the number of requests.(1)
SplitI into 2 subsets:
I(-)={i∣Ri≤Ωi} andI(+)={i∣Ri≤Ωi} (the complementary set).(2)
Then define(16)H(+)=H-∑i∈I(+)Ri,Ω(+)=∑i∈I(+)Ωi.(3)
Ri(new)=Ri,i∈I(-) (“grant requests less than user's assured bandwidth”).(4)
Scale the requests inI(+) using one of the schemes described next.(i) Difference-Oriented Scaling
Using thedifference(Ri-Ωi) weighted by the priority factors wi, we get:
(17)Ri(new)=Ωi+C·wi·(Ri-Ωi),i∈I(+).In similar arguments used in developing thepriority-oriented scaling scheme, we find:
(18)C=H(+)-Ω(+)∑i∈I(+)(Ri-Ωi)⋅wi.
(Note that the denominator (Ri-Ωi)·wi isalwayspositivebecause Ri>Ωi for  all i∈I(+)).(ii) Ratio-Oriented Scaling
Using theratio(Ri/Ωi) weighted by the priority factors wi, we get:
(19)Ri(new)=Ωi+C·wi·(RiΩi),i∈I(+),
where again by similar arguments we get:
(20)C=H(+)-Ω(+)∑i∈I(+)(Ri/Ωi)⋅wi.After the prescaling procedure, the algorithms in Section4 are applied. This prescaling is a necessary but not sufficient condition to be able to complete the procedure. However, the postscaling can be used to complete it.


### 5.4. The Postscaling Schemes

The postscaling stage makes the final correction to the allocated bandwidths. It may involve more downscaling to some of the requests. This happens when the allocating algorithm inserts to a hole a set of requests whose sum exceeds the hole size and assigns a negative value to the residue associated with the hole. In this case, the downscaling is performed in essentially same way as in the prescale step, except that the calculations are made separately for eachholej. Hence Hj is used instead of H and {Ri(j)}, and the set of requests allocated to Hj would replace  Ri.There are situations when the allocating algorithm assigns to a hole requests whose sum is less than thehole size. In this case, if some of the requests were over-decreased in the prescaling stage, they should be now increased back (up to the original amount) to fit the hole size.


### 5.5. Concluding Remarks

We have presented here some scaling schemes to supportfair sharing of available bandwidth resources in shortage conditions.Naturally, theadvanced  schemes are expected to perform better than the priority oriented scheme because they take into consideration the assured bandwidths as well as the priority factors.However, as we have pointed out, the other scaling schemes should not be abandoned. In some exceptional situations (heavy traffic periods for instance), when condition (15) is not satisfied, the priority oriented scheme (or the Basic one) should be used instead.


### 5.6. An Illustrative Example for the Allocation Cycle

To illustrate the whole resource allocation cycle, consider the following simplified example. Consider three requests issued to the system:(21)R1=9,R2=5,R3=4.
When there are two available “holes” in the spectrum:
(22)H1=9,H2=6.
As shown in Figure 2.Figure 2
The initial state ofholes and requests.The sum of the requests∑Rj=18 is greater than the available space in the spectrum ∑Hi=15, meaning there is deviation of 3, and a scaling phase should take place to address it.(i) Prescaling
For the sake of simplicity and in order to make it intuitive to the reader, tedious calculations involving QoS parameters considerations are dropped. Instead, we will focus on illustrating the concepts of the scaling stages.To solve the deviation problem, the prescaling phase can reduce each request by 1. For instance,(23)R={9,5,4}⟶{8,4,3}.
As shown in Figure 3.Figure 3
The state ofholes and requests after  prescaling.This way∑Rj=15, which is exactly the amount of available space.(ii) Allocation
Theresidue of Hi was denoted as Zi. Initially set: {D}={H}. Then:(1)
insertR1=8 into H1 (with Z1=9) such that the residue is updated to D1=1;(2)
insertR2=4 into H2 (with Z2=6) which makes this residue become Z2=2;(3)
finally, insertR3=3 into H2 (with Z2=2). This makes the residueZ2 receive a negative value: Z2=-1!This state of affairs is presented in Figure4. The overpopulation situation in H2 caused by the allocation algorithm is expressed by the overlappingR2 and R3 in the figure.Figure 4
The requests inserted to theholes by  the  allocation  algorithm. Notice the overlapping between R3′ and R4′.As stated in Section4.2, assigning a negative value to some residues is legitimate as an intermediate stage in calculation, and the task of the postscaling phase is to fix this situation.(iii) Postscaling
This phase fine tunes the bandwidths allocated. Recall that originally the requestR1 was 9, and then it was reduced to 8 and allocated to H1, which has a capacity of 9. Obviously the original request can be granted. Thus the final allocation for R1 should be A1=9.
R
2 and R3 were allocated to H2 which has a capacity of 6, but R2+R3=7, so they should be reduced again to: A2=3.5 and A3=2.5 such that A2+A3=6 to fit the H2=6 capacity.So the final resource allocation yields:A
1
=
9 inserted into H1=9 and {A2=3.5,A3=2.5} inserted into H2=6. (See Figure 5).Figure 5
The final stateafter the postscaling.


## 5.1. The Basic Scaling Scheme

In absence of any priority criteria for sharing the bandwidth, the requests are simply scaled down proportionally to their value:(10)Rk(new)=HR⋅Rk.Such a scheme corresponds to a network system that supportsbest-effort subscribers only, with no quality of service parameters.


## 5.2. The Priority-Oriented Scaling Scheme

This scheme takes into consideration only thepriority factorswi. Such a scheme is applicable for network systems that support at least the differentiated service level.The amount of bandwidth to be reduced is the difference between the sum of requests and the sum of holes:(11)D=R-H.This amount should be shared proportionally to the requestsRj (larger requests are reduced more than small ones) and inversely proportional to the priority factors wj (higher priority requests are reduced less than the lower ones). So, the request Rj should be reduced by amount dj given by: dj=C·(Rj/wj) such that D=∑jdj is the total reduction.Hence:D=C·(∑jRj/wj) where C is some proportion factor that can be written as:
(12)C=D∑kRk/wk=R-H∑kRk/wk.And finally, the requests are downscaled according to:(13)Rj(new)=(1-Cwj)⋅Rj.This scheme works unconditionally (but it does not take into consideration the assured bandwidthΩ).


## 5.3. Advanced Schemes

High-quality network systems should take into consideration the subscribers’assured bandwidthsΩi, as well as their priority factorswi. The constraint imposed by the assured bandwidth condition can be expressed as:
(14)Ri(new)≥min⁡(Ri,Ωi).This condition could be met only when:(15)∑Hi≥∑min⁡(Ri,Ωi).When this condition is satisfied, we can allocate bandwidth taking into account both the priority factors and the assured bandwidths. Otherwise, thepriority-oriented scaling scheme should be used.Our strategy is to grant all the requests below the assured bandwidth and scale downonly the others.The two schemes we present here have the same “prolog”, and differ only in the final stage.(0)
Start with a set of indexesI={1,…,N}, where N is the number of requests.(1)
SplitI into 2 subsets:
I(-)={i∣Ri≤Ωi} andI(+)={i∣Ri≤Ωi} (the complementary set).(2)
Then define(16)H(+)=H-∑i∈I(+)Ri,Ω(+)=∑i∈I(+)Ωi.(3)
Ri(new)=Ri,i∈I(-) (“grant requests less than user's assured bandwidth”).(4)
Scale the requests inI(+) using one of the schemes described next.(i) Difference-Oriented Scaling
Using thedifference(Ri-Ωi) weighted by the priority factors wi, we get:
(17)Ri(new)=Ωi+C·wi·(Ri-Ωi),i∈I(+).In similar arguments used in developing thepriority-oriented scaling scheme, we find:
(18)C=H(+)-Ω(+)∑i∈I(+)(Ri-Ωi)⋅wi.
(Note that the denominator (Ri-Ωi)·wi isalwayspositivebecause Ri>Ωi for  all i∈I(+)).(ii) Ratio-Oriented Scaling
Using theratio(Ri/Ωi) weighted by the priority factors wi, we get:
(19)Ri(new)=Ωi+C·wi·(RiΩi),i∈I(+),
where again by similar arguments we get:
(20)C=H(+)-Ω(+)∑i∈I(+)(Ri/Ωi)⋅wi.After the prescaling procedure, the algorithms in Section4 are applied. This prescaling is a necessary but not sufficient condition to be able to complete the procedure. However, the postscaling can be used to complete it.


## 5.4. The Postscaling Schemes

The postscaling stage makes the final correction to the allocated bandwidths. It may involve more downscaling to some of the requests. This happens when the allocating algorithm inserts to a hole a set of requests whose sum exceeds the hole size and assigns a negative value to the residue associated with the hole. In this case, the downscaling is performed in essentially same way as in the prescale step, except that the calculations are made separately for eachholej. Hence Hj is used instead of H and {Ri(j)}, and the set of requests allocated to Hj would replace  Ri.There are situations when the allocating algorithm assigns to a hole requests whose sum is less than thehole size. In this case, if some of the requests were over-decreased in the prescaling stage, they should be now increased back (up to the original amount) to fit the hole size.


## 5.5. Concluding Remarks

We have presented here some scaling schemes to supportfair sharing of available bandwidth resources in shortage conditions.Naturally, theadvanced  schemes are expected to perform better than the priority oriented scheme because they take into consideration the assured bandwidths as well as the priority factors.However, as we have pointed out, the other scaling schemes should not be abandoned. In some exceptional situations (heavy traffic periods for instance), when condition (15) is not satisfied, the priority oriented scheme (or the Basic one) should be used instead.


## 5.6. An Illustrative Example for the Allocation Cycle

To illustrate the whole resource allocation cycle, consider the following simplified example. Consider three requests issued to the system:(21)R1=9,R2=5,R3=4.
When there are two available “holes” in the spectrum:
(22)H1=9,H2=6.
As shown in Figure 2.Figure 2
The initial state ofholes and requests.The sum of the requests∑Rj=18 is greater than the available space in the spectrum ∑Hi=15, meaning there is deviation of 3, and a scaling phase should take place to address it.(i) Prescaling
For the sake of simplicity and in order to make it intuitive to the reader, tedious calculations involving QoS parameters considerations are dropped. Instead, we will focus on illustrating the concepts of the scaling stages.To solve the deviation problem, the prescaling phase can reduce each request by 1. For instance,(23)R={9,5,4}⟶{8,4,3}.
As shown in Figure 3.Figure 3
The state ofholes and requests after  prescaling.This way∑Rj=15, which is exactly the amount of available space.(ii) Allocation
Theresidue of Hi was denoted as Zi. Initially set: {D}={H}. Then:(1)
insertR1=8 into H1 (with Z1=9) such that the residue is updated to D1=1;(2)
insertR2=4 into H2 (with Z2=6) which makes this residue become Z2=2;(3)
finally, insertR3=3 into H2 (with Z2=2). This makes the residueZ2 receive a negative value: Z2=-1!This state of affairs is presented in Figure4. The overpopulation situation in H2 caused by the allocation algorithm is expressed by the overlappingR2 and R3 in the figure.Figure 4
The requests inserted to theholes by  the  allocation  algorithm. Notice the overlapping between R3′ and R4′.As stated in Section4.2, assigning a negative value to some residues is legitimate as an intermediate stage in calculation, and the task of the postscaling phase is to fix this situation.(iii) Postscaling
This phase fine tunes the bandwidths allocated. Recall that originally the requestR1 was 9, and then it was reduced to 8 and allocated to H1, which has a capacity of 9. Obviously the original request can be granted. Thus the final allocation for R1 should be A1=9.
R
2 and R3 were allocated to H2 which has a capacity of 6, but R2+R3=7, so they should be reduced again to: A2=3.5 and A3=2.5 such that A2+A3=6 to fit the H2=6 capacity.So the final resource allocation yields:A
1
=
9 inserted into H1=9 and {A2=3.5,A3=2.5} inserted into H2=6. (See Figure 5).Figure 5
The final stateafter the postscaling.


## 6. Modeling the Resource Allocation Process

In order to simulate the system dynamics under the resource allocation process described above, we derived a model to produce the network traffic and the inputs to the process. We distinguish between thedemands subscribers have and the requests they issue to the system. New demands for bandwidth emerge for each subscriber in random time steps. We assume that the demands νk of subscriber k are gamma distributed.
(24)νk~Γ(m,λk).
The gamma distribution [13] is a two-parameter family of continuous probability distributions. It has a shape parameter m, a scale parameter λk, and the average value:
(25)E[νk]=m·λk.
The traffic models based on random variables with Gamma distribution are used in applications such as video and speech [14, 15]. Such a random variable has a probability distribution with a shape similar to a Gaussian random variable but has only positive values.The parameters are chosen such that the mean demand of subscriberk,νk, is proportional to Ωk, the assured bandwidth of subscriber k, by a constant factor μ:
(26)E[νk]=μ·Ωk.So comparing (25) and (26):
(27)λk=μ⋅Ωkm.In the simulation, the values used are:μ=2.0 and m=3, as shown in Figure 6.Figure 6
Gamma distribution:Γ(3,2).We may assign a probabilityp for new demand to emerge such that in time step n we have demand νk(n):
(28)νk(n)={ν~Γ(m,λk),withprobabilityp,0,withprobability(1-p).We assume thatvery often user requests are not fully granted. In this situation, a subscriber should request the remainder Rk-Ak in the next time step, added to a new demand (if one emerges). This can be modeled by assigning a variable Qk to each subscriber k to accumulate requests Rk, subtract the allocated bandwidth Ak, and add demands νk:
(29)Qk(n+1)=Qk(n)+Rk(n)-Ak(n)+νk(n+1).Stability considerations suggest limiting the request amount a subscriberk may issue. In Section 1.1, we called this limit the Peak Information Rate (PIR). We set this limit to κ·Ωk, where κ>1 is a constant (κ=2 in our simulation):
(30)Rk(n+1)=min⁡(Qk(n+1),κ·Ωk).Finally, in order to avoid the penalty of unwanted disconnections associated with new bandwidth allocations, a restriction is superimposed on issuing new requests. Only changes exceeding some threshold can justify issuing new requests. To assure this, we set up a rule:a new request shall be issued only when:(31)|Rk(n+1)-Ak(n)|≥γ·Ak(n).In the simulation,γ=0.4 is used.


## 7. Comparison between Algorithms

Algorithms can be ranked either by their efficiency or by the quality of the results they produce. We shall examine and compare our algorithms in the following aspects:(i)
algorithm complexity (memory and time consumption);(ii)
distribution of the satisfaction measureS;(iii)
distribution of the requests scale downδ.We considered a typical system with 4 types of subscribers. Each type has its priority factorwk and assured bandwidth Ωk. The system setup is shown in a simulation snapshot presented in Figure 7.Figure 7
The system configuration in a simulation snapshot.The other simulation parameters are presented in Table1.Table 1
The simulation configuration.
Parameter
Equation
Value
Satisfaction coefficient
α
(2)
0.75
Disconnection penalty factor
β
(1)
0.9
Mean demand to assured bandwidth ratio
μ
(18)
2.0
Demand update rate
p
(21)
0.25
Threshold for new request
γ
(24)
0.40
Request bound to assured bandwidth ratio
κ
(23)
2.0


### 7.1. The Complexity of the Algorithms

Let us consider the complexity of the algorithms (without the scaling part) forN new requests and M  holes in the spectrum.The time complexity of both Fast-MKP and IBF-MKP algorithm is bounded byO(N·log(M)) integer operations, as the search and insert operation in a binary tree is O(log(M)).The memory complexity of both algorithms isO(N+M). However, we observed (experimentally) that the IBF-MKP algorithm runs slower than Fast-MKP by no more than 20% on the average. So, both algorithms are very efficient in run-time and memory consumption.


### 7.2. The Distributions of the Satisfaction Measure

The distributions for the satisfaction measure for the IBF-MKP and the Fast-MKP algorithms are presented by the histograms in Figures8 and 9, obtained by simulation without the effect of the scaling schemes. For the criterion of satisfaction, the IBF-MKP algorithm achieves better results.Figure 8
Satisfaction histogram IBF-MKP algorithm withpriority-oriented scaling scheme.Figure 9
Satisfaction histogram for Fast-MKP Algorithm with priority-oriented scaling scheme.The effect of the scaling schemes on the satisfaction measure is shown in Figures10, 11, and 12. The results are presented for the IBF-MKP algorithm only. The scaling schemes do improve results over those obtained without the scaling. The ratio-oriented scaling scheme yields better results than Difference Oriented, while the Priority Oriented scaling scheme is in third place.Figure 10
Satisfaction histogram forpriority-oriented scaling scheme.Figure 11
Satisfaction histogram fordifference-oriented scaling scheme.Figure 12
Satisfaction histogram forratio-oriented scaling scheme.


### 7.3. The Distributions of the “Requests Scale-Down”

The simulation records the amount of bandwidth scaled down in the resource allocation. Table2 compares the distribution of this variable for the two algorithms (without utilizing the scaling schemes).Table 2
Comparison of the “requests scale-down” between the algorithms.
Fast-MKP
IBF-MKP
δ
=
0
34.0%
43.2%
0
<
δ
≤
250
6.0%
9.8%
250
<
δ
≤
500
5.4%
8.8%
500
<
δ
≤
1000
11.0%
14.6%
1000
<
δ
≤
2000
19.8%
22.6%
2000
<
δ
≤
4000
23.0%
35.2%
δ
>
4000
6.0%
10.0%Clearly, the IBF-MKP algorithm achieves better results for the average amount of requests scale-down in the allocation process.The effect of scaling schemes on therequests scale-down factor δ is compared in Table 3, which presents results where again the algorithm is the IBF-MKP.Table 3
Comparison of therequests scale-down for different scaling schemes.
Priority oriented
Difference oriented
Ratio oriented
δ
=
0
32.0%
44.6%
48.2%
0
<
δ
≤
25
5.8%
8.4%
7.2%
25
<
δ
≤
50
8.2%
11.4%
6.4%
50
<
δ
≤
10
0
10.4%
20.6%
8.0%
100
<
δ
≤
200
14.4%
24.2%
12.2%
200
<
δ
≤
400
17.8%
20.4%
13.8%
δ
>
400
11.4%
15.0%
7.8%As expected, scaling schemes improve thescale-down results. The ratio-oriented gives the best results, while the difference-oriented is somewhat less effective, and the priority-oriented offers the least effectiveness.The difference is probably due to the ability to grant all requests below the assured bandwidth. This approach makes these advanced scaling schemes superior to other schemes.


## 7.1. The Complexity of the Algorithms

Let us consider the complexity of the algorithms (without the scaling part) forN new requests and M  holes in the spectrum.The time complexity of both Fast-MKP and IBF-MKP algorithm is bounded byO(N·log(M)) integer operations, as the search and insert operation in a binary tree is O(log(M)).The memory complexity of both algorithms isO(N+M). However, we observed (experimentally) that the IBF-MKP algorithm runs slower than Fast-MKP by no more than 20% on the average. So, both algorithms are very efficient in run-time and memory consumption.


## 7.2. The Distributions of the Satisfaction Measure

The distributions for the satisfaction measure for the IBF-MKP and the Fast-MKP algorithms are presented by the histograms in Figures8 and 9, obtained by simulation without the effect of the scaling schemes. For the criterion of satisfaction, the IBF-MKP algorithm achieves better results.Figure 8
Satisfaction histogram IBF-MKP algorithm withpriority-oriented scaling scheme.Figure 9
Satisfaction histogram for Fast-MKP Algorithm with priority-oriented scaling scheme.The effect of the scaling schemes on the satisfaction measure is shown in Figures10, 11, and 12. The results are presented for the IBF-MKP algorithm only. The scaling schemes do improve results over those obtained without the scaling. The ratio-oriented scaling scheme yields better results than Difference Oriented, while the Priority Oriented scaling scheme is in third place.Figure 10
Satisfaction histogram forpriority-oriented scaling scheme.Figure 11
Satisfaction histogram fordifference-oriented scaling scheme.Figure 12
Satisfaction histogram forratio-oriented scaling scheme.


## 7.3. The Distributions of the “Requests Scale-Down”

The simulation records the amount of bandwidth scaled down in the resource allocation. Table2 compares the distribution of this variable for the two algorithms (without utilizing the scaling schemes).Table 2
Comparison of the “requests scale-down” between the algorithms.
Fast-MKP
IBF-MKP
δ
=
0
34.0%
43.2%
0
<
δ
≤
250
6.0%
9.8%
250
<
δ
≤
500
5.4%
8.8%
500
<
δ
≤
1000
11.0%
14.6%
1000
<
δ
≤
2000
19.8%
22.6%
2000
<
δ
≤
4000
23.0%
35.2%
δ
>
4000
6.0%
10.0%Clearly, the IBF-MKP algorithm achieves better results for the average amount of requests scale-down in the allocation process.The effect of scaling schemes on therequests scale-down factor δ is compared in Table 3, which presents results where again the algorithm is the IBF-MKP.Table 3
Comparison of therequests scale-down for different scaling schemes.
Priority oriented
Difference oriented
Ratio oriented
δ
=
0
32.0%
44.6%
48.2%
0
<
δ
≤
25
5.8%
8.4%
7.2%
25
<
δ
≤
50
8.2%
11.4%
6.4%
50
<
δ
≤
10
0
10.4%
20.6%
8.0%
100
<
δ
≤
200
14.4%
24.2%
12.2%
200
<
δ
≤
400
17.8%
20.4%
13.8%
δ
>
400
11.4%
15.0%
7.8%As expected, scaling schemes improve thescale-down results. The ratio-oriented gives the best results, while the difference-oriented is somewhat less effective, and the priority-oriented offers the least effectiveness.The difference is probably due to the ability to grant all requests below the assured bandwidth. This approach makes these advanced scaling schemes superior to other schemes.


## 8. Conclusion

In a rapidly evolving communications market with ever-growing demand for more bandwidth, a good resource management mechanism is essential for efficient digital communication of any kind. The algorithms suggested here together with the scaling schemes successfully perform this task with reasonable computational complexity, producing a high-quality resource allocation with remarkable performance.



---

*Source: 169026-2012-07-24.xml*