#### DMCA

## Discriminatory Processor Sharing from Optimization Point of View

### Citations

932 | Charging and rate control for elastic traffic
- Kelly
- 1997
(Show Context)
Citation Context ...ation is Ci = wi∑N j=1 wj C. (19) Note that we also assume here that the players are price takers, that is they accept the price and the resulted allocations. This proportional allocation above is also the solution of the following optimization problem. max x N∑ i=1 wi log xi , s.t. K∑ i=1 xi = C , xi ≥ 0 (20) which is a simple rewrite of (Opt) according to our new quantities wi and Ci. The proportional allocation and the price taker characteristic have a much more fundamental property, which can be explained through the notion of competitive equilibrium between users and the resource manager [7]. In competitive equilibrium players (classes in our case) (i = 1, . . . ,K) act to maximize their payoff functions P (wi, µ) for a given price µ over wi, which payoff consists of the utility Ui( wi µ ) by obtaining wi µ resources minus the payment wi for that amount of resource to the manager, that is P (wi, µ) := Ui( wi µ )− wi. A pair (w, µ), w ≥ 0, µ > 0 is said to be a competitive equilibrium between the users and the network, if users maximize their payoff functions and the network determines the price as µ = ∑N i=1 wi C . (21) It can also be shown that if ((w, µ)) forms a competitive eq... |

94 | Time-shared systems: a theoretical treatment.
- Kleinrock
- 1967
(Show Context)
Citation Context ... It also means that the available bandwidth share calculation methods for the access rate limited DPS are also non-conventional solution methods for the extended constrained optimization problem. We also foreshadow that these results might be important steps towards obtaining efficient pricing and resource allocation mechanism when users are selfish and subject to gaming behavior when competing for communication resources. 1 Introduction Processor Sharing (PS) models have been long studied in the queueing systems literature. One of the first reports on processor sharing have been performed in [10] motivated mainly by the modeling of time-shared computer systems. In this seminal work and also in [13] not only the egalitarian sharing (equal service rates are allocated for customers), but the (multi-class) discriminatory processor sharing has also been analyzed. In DPS the division of the processing capacity C can be controlled by a set of weights (g1, g2, . . . , gK) in the following way. If there are n1, n2, . . . , nK customers from the classes in the queuing system, ⋆ This works was supported by FIRST TAMOP-4.2.2.C-11/1/KONV-2012-0001 they are served simultaneously, and the (instantan... |

66 |
Sharing a processor among many job classes.
- Fayolle, Mitrani, et al.
- 1980
(Show Context)
Citation Context ...rk and also in [13] not only the egalitarian sharing (equal service rates are allocated for customers), but the (multi-class) discriminatory processor sharing has also been analyzed. In DPS the division of the processing capacity C can be controlled by a set of weights (g1, g2, . . . , gK) in the following way. If there are n1, n2, . . . , nK customers from the classes in the queuing system, ⋆ This works was supported by FIRST TAMOP-4.2.2.C-11/1/KONV-2012-0001 they are served simultaneously, and the (instantaneous) service rate of a class−i customer is ci = gi∑K j=1 gjnj C . Fayolle et al. in [5] completed the early efforts in solving discriminatory processor sharing models. They gave the correct characterizations for the M/G/1- PS system with respect to the steady-state average response times (by integrodifferential equations), and also showed that in the special case of exponential distribution of the service time requirements, the steady-state average response times can be obtained by solving a system of linear equations. In [15] Rege and Sengupta showed how to obtain the moments of the queue length distributions as the solutions to linear equations in case of exponential service t... |

31 |
Queue length distribution for the discriminatory processorsharing queue.
- Rege, Sengupta
- 1996
(Show Context)
Citation Context ...-11/1/KONV-2012-0001 they are served simultaneously, and the (instantaneous) service rate of a class−i customer is ci = gi∑K j=1 gjnj C . Fayolle et al. in [5] completed the early efforts in solving discriminatory processor sharing models. They gave the correct characterizations for the M/G/1- PS system with respect to the steady-state average response times (by integrodifferential equations), and also showed that in the special case of exponential distribution of the service time requirements, the steady-state average response times can be obtained by solving a system of linear equations. In [15] Rege and Sengupta showed how to obtain the moments of the queue length distributions as the solutions to linear equations in case of exponential service time requirements, and they also presented a heavy-traffic limit theorem for the joint queue length distribution. These results were extended to phase type distributions by van Kessel et al. [8]. A further remarkable milestone in DPS analysis is [1] in which the authors showed that the mean queue lengths of all classes are finite under reasonable stability conditions, regardless of the higher moments of the service requirements. It was also s... |

19 | Discriminatory processor sharing revisited. In: In:
- Avrachenkov, Ayesta, et al.
- 2005
(Show Context)
Citation Context ...o showed that in the special case of exponential distribution of the service time requirements, the steady-state average response times can be obtained by solving a system of linear equations. In [15] Rege and Sengupta showed how to obtain the moments of the queue length distributions as the solutions to linear equations in case of exponential service time requirements, and they also presented a heavy-traffic limit theorem for the joint queue length distribution. These results were extended to phase type distributions by van Kessel et al. [8]. A further remarkable milestone in DPS analysis is [1] in which the authors showed that the mean queue lengths of all classes are finite under reasonable stability conditions, regardless of the higher moments of the service requirements. It was also shown that the conditional response times of the different classes are stochastically ordered according to the DPS weights. In [3] Cheung, van den Berg and Boucherie for the egalitarian PS model obtained an exact and analytically tractable decomposition. This decomposition was applied to discriminatory PS to obtain an efficient and analytically tractable approximation of the queue length distribution ... |

13 |
Asymptotic regimes and approximations for discriminatory processor sharing.
- Kessel, Nunez-Queija, et al.
- 2004
(Show Context)
Citation Context ...ponse times (by integrodifferential equations), and also showed that in the special case of exponential distribution of the service time requirements, the steady-state average response times can be obtained by solving a system of linear equations. In [15] Rege and Sengupta showed how to obtain the moments of the queue length distributions as the solutions to linear equations in case of exponential service time requirements, and they also presented a heavy-traffic limit theorem for the joint queue length distribution. These results were extended to phase type distributions by van Kessel et al. [8]. A further remarkable milestone in DPS analysis is [1] in which the authors showed that the mean queue lengths of all classes are finite under reasonable stability conditions, regardless of the higher moments of the service requirements. It was also shown that the conditional response times of the different classes are stochastically ordered according to the DPS weights. In [3] Cheung, van den Berg and Boucherie for the egalitarian PS model obtained an exact and analytically tractable decomposition. This decomposition was applied to discriminatory PS to obtain an efficient and analytically tr... |

13 |
Balancing quality of service, pricing and utilisation in multiservice networks with stream and elastic traffic. In:
- Lindberger
- 1999
(Show Context)
Citation Context ...es. In the discriminatory processor sharing models above, a common characteristics is that the users from the same class get equal share of the capacity allocated to that class, and the service capacity allocations of classes are proportional to their weights and to their number of users. The other valuable direction of further developments of processor sharing model is to introduce capacity limits by which the customers can receive service from the server. This is mainly motivated by involving access rate limitations of users (e.g. in DSL-type access systems) in to the modeling framework. In [12] Lindberger introduced and analyzed the so-called M/G/R-PS model, which is a single-class processor sharing model with access rate limit b on the users (R := C/b is the “number of servers” in this system). Several improvements of this model were studied for dimensioning purposes of IP access networks, e.g. in [16] and [4] still remaining at the single-class models. Introducing access rate limitations in multi-class discriminatory processor sharing inherently raises the question of bandwidth re-distribution. This means that if customers in a class can not fully utilize their prospective service... |

8 |
Decomposing the queue length distribution of processor-sharing models into queue lengths of permanent customer queues. Performance Evaluation 62(1-4),
- Cheung, Berg, et al.
- 2005
(Show Context)
Citation Context ...case of exponential service time requirements, and they also presented a heavy-traffic limit theorem for the joint queue length distribution. These results were extended to phase type distributions by van Kessel et al. [8]. A further remarkable milestone in DPS analysis is [1] in which the authors showed that the mean queue lengths of all classes are finite under reasonable stability conditions, regardless of the higher moments of the service requirements. It was also shown that the conditional response times of the different classes are stochastically ordered according to the DPS weights. In [3] Cheung, van den Berg and Boucherie for the egalitarian PS model obtained an exact and analytically tractable decomposition. This decomposition was applied to discriminatory PS to obtain an efficient and analytically tractable approximation of the queue length distribution and mean sojourn times. In the discriminatory processor sharing models above, a common characteristics is that the users from the same class get equal share of the capacity allocated to that class, and the service capacity allocations of classes are proportional to their weights and to their number of users. The other valuab... |

8 |
Direct solutions of M/G/1 processor-sharing models.
- O’Donovan
- 1974
(Show Context)
Citation Context ...e also non-conventional solution methods for the extended constrained optimization problem. We also foreshadow that these results might be important steps towards obtaining efficient pricing and resource allocation mechanism when users are selfish and subject to gaming behavior when competing for communication resources. 1 Introduction Processor Sharing (PS) models have been long studied in the queueing systems literature. One of the first reports on processor sharing have been performed in [10] motivated mainly by the modeling of time-shared computer systems. In this seminal work and also in [13] not only the egalitarian sharing (equal service rates are allocated for customers), but the (multi-class) discriminatory processor sharing has also been analyzed. In DPS the division of the processing capacity C can be controlled by a set of weights (g1, g2, . . . , gK) in the following way. If there are n1, n2, . . . , nK customers from the classes in the queuing system, ⋆ This works was supported by FIRST TAMOP-4.2.2.C-11/1/KONV-2012-0001 they are served simultaneously, and the (instantaneous) service rate of a class−i customer is ci = gi∑K j=1 gjnj C . Fayolle et al. in [5] completed the e... |

5 | Bandwidth-sharing networks under a diffusion scaling.
- Ayesta, Mandjes
- 2009
(Show Context)
Citation Context ...th re-distribution. This means that if customers in a class can not fully utilize their prospective service capacity share (bandwidth share) due to their access rate limit, how this unused (left) bandwidth is re-distributed among the other classes. In one of the extreme cases, there is no re-distribution at all meaning that the possible remaining unused bandwidth due to rate limits is wasted. One can also interpret this as the server capacity may not be fully utilized, even in those cases when there is “enough” customers in the system. This approach is followed for example in the papers [11], [2]. In the other extreme case of multi-class discriminatory processor sharing, all the unused bandwidth by access rate limited customers are fully utilized by the other (non-limited) customers. In this scenario even the bandwidth shares can not be easily determined for given n and g. Some of the classes will share certain amount of capacity proportional to their weights and number of users, whilst other classes’ users are saturated at their access rate limits. Efficient algorithms have been presented for computing the capacity shares in [14] and [9]. In the original DPS model, the capacity share... |

4 | A framework for multi-service IP network planning.
- Riedl, Bauschert, et al.
- 2002
(Show Context)
Citation Context ...ion of further developments of processor sharing model is to introduce capacity limits by which the customers can receive service from the server. This is mainly motivated by involving access rate limitations of users (e.g. in DSL-type access systems) in to the modeling framework. In [12] Lindberger introduced and analyzed the so-called M/G/R-PS model, which is a single-class processor sharing model with access rate limit b on the users (R := C/b is the “number of servers” in this system). Several improvements of this model were studied for dimensioning purposes of IP access networks, e.g. in [16] and [4] still remaining at the single-class models. Introducing access rate limitations in multi-class discriminatory processor sharing inherently raises the question of bandwidth re-distribution. This means that if customers in a class can not fully utilize their prospective service capacity share (bandwidth share) due to their access rate limit, how this unused (left) bandwidth is re-distributed among the other classes. In one of the extreme cases, there is no re-distribution at all meaning that the possible remaining unused bandwidth due to rate limits is wasted. One can also interpret thi... |

2 |
Differential equation models of flow-size based priorities in internet routers.
- Lakshmikantha, Srikant, et al.
- 2010
(Show Context)
Citation Context ...andwidth re-distribution. This means that if customers in a class can not fully utilize their prospective service capacity share (bandwidth share) due to their access rate limit, how this unused (left) bandwidth is re-distributed among the other classes. In one of the extreme cases, there is no re-distribution at all meaning that the possible remaining unused bandwidth due to rate limits is wasted. One can also interpret this as the server capacity may not be fully utilized, even in those cases when there is “enough” customers in the system. This approach is followed for example in the papers [11], [2]. In the other extreme case of multi-class discriminatory processor sharing, all the unused bandwidth by access rate limited customers are fully utilized by the other (non-limited) customers. In this scenario even the bandwidth shares can not be easily determined for given n and g. Some of the classes will share certain amount of capacity proportional to their weights and number of users, whilst other classes’ users are saturated at their access rate limits. Efficient algorithms have been presented for computing the capacity shares in [14] and [9]. In the original DPS model, the capacity ... |

1 |
Dimensioning Bandwidth for Elastic Traffic. NETWORKING 2002: Networking Technologies, Services, and Protocols;
- Fan
- 2006
(Show Context)
Citation Context ...rther developments of processor sharing model is to introduce capacity limits by which the customers can receive service from the server. This is mainly motivated by involving access rate limitations of users (e.g. in DSL-type access systems) in to the modeling framework. In [12] Lindberger introduced and analyzed the so-called M/G/R-PS model, which is a single-class processor sharing model with access rate limit b on the users (R := C/b is the “number of servers” in this system). Several improvements of this model were studied for dimensioning purposes of IP access networks, e.g. in [16] and [4] still remaining at the single-class models. Introducing access rate limitations in multi-class discriminatory processor sharing inherently raises the question of bandwidth re-distribution. This means that if customers in a class can not fully utilize their prospective service capacity share (bandwidth share) due to their access rate limit, how this unused (left) bandwidth is re-distributed among the other classes. In one of the extreme cases, there is no re-distribution at all meaning that the possible remaining unused bandwidth due to rate limits is wasted. One can also interpret this as the... |

1 |
Algorithmic Game Theory, chap. The Price of Anarchy and the Design of Scalable Resource Allocation Mechanisms,
- Johari
- 2007
(Show Context)
Citation Context ...e utility functions, for details see e.g. [7] An important observation here is that the proportional allocation (19) spans a bridge between the individual user payoff maximization and the social welfare maximization, that is the two maximization coincide when proportional allocation applied. This remarkable property of proportional allocation also makes possible to investigate the case when players are price anticipating, that is the players take into account that the price is set according to (21) and they maximize their payoff Ui ( wi∑N k=1 wk C ) − wi (22) with respect to their payments wi [6]. As we can have seen through Theorem 1, the allocation in case of access rate limited shares (which is partially proportional) is the solution of (OptBounds), which is a quite natural extension of (Opt) by the constraints xi ≤ bi. Based on this, we conjecture that the (appropriately modified) competitive equilibrium and the social welfare can be coupled with this allocation in case of limited access to the resource, that is Conjecture: The competitive equilibrium (w∗, µ∗) exists, in which w∗i maximizes the payoff function Pi(wi, µ ∗) = Ui ( max( wi µ∗ , nibi) ) − wi (23) where µ∗ = ∑K j=i∗+1 ... |

1 |
Characterization of peak-rate limited DPS with Pareto-efficient bandwidth sharing.
- Korosi, Szekely, et al.
- 2012
(Show Context)
Citation Context ...ch is followed for example in the papers [11], [2]. In the other extreme case of multi-class discriminatory processor sharing, all the unused bandwidth by access rate limited customers are fully utilized by the other (non-limited) customers. In this scenario even the bandwidth shares can not be easily determined for given n and g. Some of the classes will share certain amount of capacity proportional to their weights and number of users, whilst other classes’ users are saturated at their access rate limits. Efficient algorithms have been presented for computing the capacity shares in [14] and [9]. In the original DPS model, the capacity shares of users for given n and g are solutions of a constrained optimization problem (see next chapter for details). Furthermore, because this solution is a proportional bandwidth allocation (among classes), this has a bridging role between the utilitarian social welfare maximization and individual payoff maximization, when classes of users are competing for the bandwidth shares. 2 Discriminatory Processor Sharing with Access Rate Limitations Let ni denote the number of class-i (i = 1 . . .K) flows (users, jobs) in the C capacity processor sharing sys... |

1 |
S.: Characterization of peak-rate limited bandwidth efficient DPS.
- Palyi, Korosi, et al.
- 2012
(Show Context)
Citation Context ...is approach is followed for example in the papers [11], [2]. In the other extreme case of multi-class discriminatory processor sharing, all the unused bandwidth by access rate limited customers are fully utilized by the other (non-limited) customers. In this scenario even the bandwidth shares can not be easily determined for given n and g. Some of the classes will share certain amount of capacity proportional to their weights and number of users, whilst other classes’ users are saturated at their access rate limits. Efficient algorithms have been presented for computing the capacity shares in [14] and [9]. In the original DPS model, the capacity shares of users for given n and g are solutions of a constrained optimization problem (see next chapter for details). Furthermore, because this solution is a proportional bandwidth allocation (among classes), this has a bridging role between the utilitarian social welfare maximization and individual payoff maximization, when classes of users are competing for the bandwidth shares. 2 Discriminatory Processor Sharing with Access Rate Limitations Let ni denote the number of class-i (i = 1 . . .K) flows (users, jobs) in the C capacity processor sha... |