Load balancing in processor sharing systems

We investigate optimal load balancing strategies for a multi-class multi-server processor-sharing system with a Poisson input stream, heterogeneous service rates, and a server-dependent holding cost per unit time. Specifically, we study (i) the centralized setting in which a dispatcher routes incoming jobs based on their service time requirements so as to minimize the weighted mean sojourn time in the system; and (ii) the decentralized, distributed non-cooperative setting in which each job, aware of its service time, selects a server with the objective of minimizing its weighted mean sojourn time in the system. For the decentralized setting we show the existence of a potential function, which allows us to transform the non-cooperative game into a standard convex optimization problem. For the two aforementioned settings, we characterize the set of optimal routing policies and obtain a closed form expression for the load on each server under any such policy. Furthermore, we show the existence of an optimal policy that routes a job independently of its service time requirement. We also show that the set of servers used in the decentralized setting is a subset of set of servers used in the centralized setting. Finally, we compare the performance perceived by jobs in the two settings by studying the so-called Price of Anarchy (PoA), that is, the ratio between the decentralized and the optimal centralized solutions. When the holding cost per unit time is the same for all servers, it is known that the PoA is upper bounded by the number of servers in the system. Interestingly, we show that the PoA for our system can be unbounded. In particular this indicates that in our system, the performance of selfish routing can be extremely inefficient.     

Call admission control schemes under generalized processor sharing scheduling

Provision of Quality‐of‐Service (QoS) guarantees is an important and challenging issue in the design of integrated‐services packet networks. Call admission control is an integral part of the challenge and is closely related to other aspects of networks such as service models, scheduling disciplines, traffic characterization and QoS specification. In this paper we provide a theoretical framework within which call admission control schemes with multiple statistical QoS guarantees can be constructed for the Generalized Processor Sharing (GPS) scheduling discipline. Using this framework, we present several admission control schemes for both session‐based and class‐based service models. The theoretical framework is based on recent results in the statistical analysis of the GPS scheduling discipline and the theory of effective bandwidths. Both optimal schemes and suboptimal schemes requiring less computational effort are studied under these service models. The QoS metric considered is loss probability. This revised version was published online in June 2006 with corrections to the Cover Date.     

Analytical modelling and evaluation of generalized processor sharing systems with heterogeneous traffic

Generalized processor sharing (GPS) has been widely studied as an important scheme for providing differentiated quality of service. Realistic traffic in multi‐service networks exhibits heterogeneous properties and can be categorized into two classes, namely, long range dependent (LRD) and short range dependent (SRD) traffic. Performance modelling and analysis of GPS systems subject to heterogeneous network traffic is an open and challenging problem. This paper develops an analytical performance model for GPS systems under heterogeneous LRD and SRD traffic. To this end, we propose a cost‐efficient modelling method for GPS and further develop the analytical upper and lower bounds of the queue length distributions for individual traffic flows. Numerical examples and extensive simulation results are presented to validate the accuracy and merits of the analytical model. Copyright © 2007 John Wiley & Sons, Ltd.     

Performance modelling of generalized processor sharing systems with multiple self-similar traffic flows

The Generalized Processor Sharing (GPS) is an important service differentiation scheme in telecommunication systems and has attracted great research interests due to the desirable properties of fairness, traffic isolation, and work conservation. The major limitation of the existing analytical performance models of GPS systems subject to self-similar traffic is that these models have been restricted to a simplified scenario with only two traffic flows. To overcome such a limitation, this study proposes a new flow-decomposition approach to modelling GPS systems subject to multiple self-similar traffic flows. We present and prove the existence of a feasible ordering of GPS systems based on the required and guaranteed service rates of traffic flows. With the aid of the feasible ordering, we decompose the GPS system into a group of single-queue systems and then derive the queue length distributions and loss probabilities of individual self-similar traffic flows in the original GPS system. Extensive simulation experiments are conducted to validate the accuracy of the developed analytical model.     

Strongly ideal secret sharing schemes

We define strongly ideal secret sharing schemes to be ideal secret sharing schemes in which certain natural requirements are placed on the decoder. We prove an information-theoretic characterization of perfect schemes, and use it to determine which access structures can be encoded by strongly ideal schemes. We also discuss a hierarchy of secret sharing schemes that are more powerful than strongly ideal schemes.     

Graph decompositions and secret sharing schemes

In this paper we continue a study of secret sharing schemes for-access structures based on graphs. Given a graph G, we require that a subset of participants can compute a secret key if they contain an edge of G; otherwise, they can obtain no information regarding the key. We study the information rate of such schemes, which measures how much information in being distributed as shares compared with the size of the secret key, and the average information rate, which is the ratio between the secret size and the arithmetic mean of the size of the shares. We give both upper and lower bounds on the optimal information rate and average information rate that can be obtained. Upper bounds arise by applying entropy arguments due to Capocelli et al. [15]. Lower bounds come from constructions that are based on graph decompositions. Application of these constructions requires solving a particular linear programming problem. We prove some general results concerning the information rate and average information rate for paths, cycles, and trees. Also, we study the 30 (connected) graphs on at most five vertices, obtaining exact values for the optimal information rate in 26 of the 30 cases, and for the optimal average information rate in 28 of the 30 cases.The research of C. Blundo, A. De Santis, and U. Vaccaro was partially supported by the Italian Ministry of University and Research (M.U.R.S.T.) and by the National Council for Research (C.N.R.) under Grant 91.02326.CT12. The research of D. R. Stinson was supported by NSF Grant CCR-9121051.     

Credit-based processor sharing for decoupled delay and bandwidthallocation

We propose a credit-based processor sharing (CPS) approach for decoupled allocation of delay and bandwidth. For bandwidth guarantees, a CPS system serves traffic flows in proportion to their service weights. For delay guarantees, on the other hand, a CPS system allows real-time flows to temporarily borrow bandwidth from nonreal-time flows using service credits. This borrowing mechanism boosts the delay performance of real-time flows without increasing their long-term bandwidth requirements. By systematically regulating service credits of real-time flows, nonreal-time flows are protected for their aggregate long-term bandwidth share     

Generalized processor sharing with light-tailed and heavy-tailed input

We consider a queue fed by a mixture of light-tailed and heavy-tailed traffic. The two traffic flows are served in accordance with the generalized processor sharing (GPS) discipline. GPS-based scheduling algorithms, such as weighted fair queueing, have emerged as an important mechanism for achieving service differentiation in integrated networks. We derive the asymptotic workload behavior of the light-tailed traffic flow under the assumption that its GPS weight is larger than its traffic intensity. The GPS mechanism ensures that the workload is bounded above by that in an isolated system with the light-tailed flow served in isolation at a constant rate equal to its GPS weight. We show that the workload distribution is in fact asymptotically equivalent to that in the isolated system, multiplied with a certain pre-factor, which accounts for the interaction with the heavy-tailed flow. Specifically, the pre-factor represents the probability that the heavy-tailed flow is backlogged long enough for the light-tailed flow to reach overflow. The results provide crucial qualitative insight in the typical overflow scenario.     

Fluid simulation for self-similar traffic in generalized processor sharing servers

We propose a fluid simulation algorithm for generalized processor sharing (GPS) servers. We analyze the complexity of the proposed algorithm and show the advantage of fluid simulation, compared to packet-level simulation. Numerical results show that the simulation time can be much reduced by admitting some performance errors as the load is heavier and the self-similarity is higher.     

Ideal secret sharing schemes with multiple secrets

We consider secret sharing schemes which, through an initial issuing of shares to a group of participants, permit a number of different secrets to be protected. Each secret is associated with a (potentially different) access structure and a particular secret can be reconstructed by any group of participants from its associated access structure without the need for further broadcast information. We consider ideal secret sharing schemes in this more general environment. In particular, we classify the collections of access structures that can be combined in such an ideal secret sharing scheme and we provide a general method of construction for such schemes. We also explore the extent to which the results that connect ideal secret sharing schemes to matroids can be appropriately generalized.The work of the second and third authors was supported by the Australian Research Council.     

Secret sharing schemes with bipartite access structure

We study the information rate of secret sharing schemes whose access structure is bipartite. In a bipartite access structure there are two classes of participants and all participants in the same class play an equivalent role in the structure. We characterize completely the bipartite access structures that can be realized by an ideal secret sharing scheme. Both upper and lower bounds on the optimal information rate of bipartite access structures are given. These results are applied to the particular case of weighted threshold access structure with two weights     

Performance analysis of switch‐based multiuser scheduling schemes with adaptive modulation in spectrum sharing systems

This paper focuses on the development of multiuser access schemes for spectrum sharing systems whereby secondary users are allowed to share the spectrum with primary users under the condition that the interference observed at the primary receiver is below a predetermined threshold. In particular, two scheduling schemes are proposed for selecting a user among those that satisfy the interference constraint and achieve an acceptable signal‐to‐noise ratio level. The first scheme focuses on optimizing the average spectral efficiency by selecting the user that reports the best channel quality. In order to alleviate the relatively high feedback required by the first scheme, a second scheme based on the concept of switched diversity is proposed, where the base station (BS) scans the secondary users in a sequential manner until a user whose channel quality is above an acceptable predetermined threshold is found. We develop expressions for the statistics of the signal‐to‐interference and noise ratio as well as the average spectral efficiency, average feedback load, and the delay at the secondary BS. We then present numerical results for the effect of the number of users and the interference constraint on the optimal switching threshold and the system performance and show that our analysis results are in perfect agreement with the numerical results. Copyright © 2014 John Wiley & Sons, Ltd.     

基于单向函数的广义秘密共享方案

提出了广义秘密共享方案的概念，并给出了两个基于单向函数的广义秘密共享方案，这两个方案只需每个成员保存一个子秘密，而且每个成员的子秘密可以重复使用，并且在更新成员时无需更改每个成员的子秘密。     

On the classification of ideal secret sharing schemes

In a secret sharing scheme a dealer has a secret key. There is a finite set P of participants and a set of subsets of P. A secret sharing scheme with as the access structure is a method which the dealer can use to distribute shares to each participant so that a subset of participants can determine the key if and only if that subset is in . The share of a participant is the information sent by the dealer in private to the participant. A secret sharing scheme is ideal if any subset of participants who can use their shares to determine any information about the key can in fact actually determine the key, and if the set of possible shares is the same as the set of possible keys. In this paper we show a relationship between ideal secret sharing schemes and matroids.This work was performed at the Sandia National Laboratories and was supported by the U.S. Department of Energy under Contract No. DE-AC04-76DP00789.     

Optimal spectrum utilisation in cognitive radio networks based on processor sharing techniques

Cognitive radio networks have achieved higher efficiency in terms of spectrum usage; however they do not readily solve any competition for access among secondary users. Optimisation is applied to an underlay network to obtain the optimal solution for at least two secondary users operating simultaneously on the same channel. Performance measures are used as the target for optimisation. However, the objective function is difficult to obtain in closed form. For the performance measures, queueing theory, particularly weighted processor sharing techniques are employed to model the system dynamics and behaviour. Transmission power and the interference temperature limit are used to allocate weights to the secondary users. Queue length and waiting time functions obtained from the queuing models are used for optimisation. After establishing that the objective function can be considered to be pseudo‐convex, convex programming is then deployed to obtain the optimised solution. The results suggest that there is indeed an improvement in network performance after optimisation. The immediate benefits of such a system are firstly improved spectrum utilisation through adding multiple secondary users and secondly, through optimisation, higher performance that can be achieved by the secondary users.     

On secret sharing systems

A "secret sharing system" permits a secret to be shared amongntrustees in such a way that anykof them can recover the secret, but anyk-1have complete uncertainty about it. A linear coding scheme for secret sharing is exhibited which subsumes the polynomial interpolation method proposed by Shamir and can also be viewed as a deterministic version of Blakley's probabilistic method. Bounds on the maximum value ofnfor a givenkand secret size are derived for any system, linear or nonlinear. The proposed scheme achieves the lower bound which, for practical purposes, differs insignificantly from the upper bound. The scheme may be extended to protect several secrets. Methods to protect against deliberate tampering by any of the trustees are also presented.     

On the size of shares for secret sharing schemes

A secret sharing scheme permits a secret to be shared among participants in such a way that only qualified subsets of participants can recover the secret, but any nonqualified subset has absolutely no information on the secret. The set of all qualified subsets defines the access structure to the secret. Sharing schemes are useful in the management of cryptographic keys and in multiparty secure protocols.We analyze the relationships among the entropies of the sample spaces from which the shares and the secret are chosen. We show that there are access structures with four participants for which any secret sharing scheme must give to a participant a share at least 50% greater than the secret size. This is the first proof that there exist access structures for which the best achievable information rate (i.e., the ratio between the size of the secret and that of the largest share) is bounded away from 1. The bound is the best possible, as we construct a secret sharing scheme for the above access structures that meets the bound with equality.This work was partially supported by Algoritmi, Modelli di Calcolo e Sistemi Informativi of M.U.R.S.T. and by Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo of C.N.R. under Grant Number 91.00939.PF69.     

适用于任意接入结构的可验证多秘密分享方案

对一般接入结构上的可验证多秘密分享进行了研究，给出了可适用于任意接入结构的一类可验证多秘密分享方案的构造方法。用这种方法构造的可验证多秘密分享方案具有以下性质：可在一组分享者中同时分享多个秘密；分发者发送给每一分享者的秘密份额都是可公开验证的；关于每一秘密的公开信息也是可公开验证的；恢复秘密时可防止分享者提供假的份额。分析表明，用此方法构造的可验证多秘密分享方案不仅是安全的，而且是高效的。     

Secret sharing schemes from three classes of linear codes

Secret sharing has been a subject of study for over 20 years, and has had a number of real-world applications. There are several approaches to the construction of secret sharing schemes. One of them is based on coding theory. In principle, every linear code can be used to construct secret sharing schemes. But determining the access structure is very hard as this requires the complete characterization of the minimal codewords of the underlying linear code, which is a difficult problem in general. In this paper, a sufficient condition for all nonzero codewords of a linear code to be minimal is derived from exponential sums. Some linear codes whose covering structure can be determined are constructed, and then used to construct secret sharing schemes with nice access structures.     

Sequential diagnosis of processor array systems

We examine the diagnosis of processor array systems formed as two-dimensional arrays, with boundaries, and either four or eight neighbors for each interior processor. We employ a parallel test schedule. Neighboring processors test each other, and report the results. Our diagnostic objective is to find a fault-free processor or set of processors. The system may then be sequentially diagnosed by repairing those processors tested faulty according to the identified fault-free set, or a job may be run on the identified fault-free processors. We establish an upper bound on the maximum number of faults which can be sustained without invalidating the test results under worst case conditions. We give test schedules and diagnostic algorithms which meet the upper bound as far as the highest order term. We compare these near optimal diagnostic algorithms to alternative algorithms, both new and already in the literature, and against an upper bound ideal case algorithm, which is not necessarily practically realizable. For eight-way array systems with N processors, an ideal algorithm has diagnosability 3N/sup 2/3/-2N/sup 1/2/ plus lower-order terms. No algorithm exists which can exceed this. We give an algorithm which starts with tests on diagonally connected processors, and which achieves approximately this diagnosability. So the given algorithm is optimal to within the two most significant terms of the maximum diagnosability. Similarly, for four-way array systems with N processors, no algorithm can have diagnosability exceeding 3N/sup 2/3//2/sup 1/3/-2N/sup 1/2/ plus lower-order terms. And we give an algorithm which begins with tests arranged in a zigzag pattern, one consisting of pairing nodes for tests in two different directions in two consecutive test stages; this algorithm achieves diagnosability (3/2)(5/2)/sup 1/3/N/sup 2/3/-(5/4)N/sup 1/2/ plus lower-order terms, which is about 0.85 of the upper bound due to an ideal algorithm.