We find `strict' Pareto inefficiency of Nash equilibria (NE) in prisoners' dilemma and Braess paradox, wherein the utilities of `all' players degrade in NE. The strict Pareto inefficiency is a narrower concept than (usually mentioned) Pareto inefficiency. In this paper, we present a measure that shows the magnitude of strict Pareto inefficiency, abbreviated as MoS. MoS distinguishes strict Pareto inefficiency of a state (an allocation/a strategy profile), say, a Nash equilibrium (NE). We present examples wherein the widely-used measure of ineffectiveness based on the social optimality, like price of anarchy (PoA), does not always distinguish strict Pareto inefficiency whereas MoS does. Furthermore, we show that, if there exists a Pareto optimum that is proportional to a state, MoS of the state is obtained as the constant of proportionality between the Pareto optimum and the state. Then, if the Pareto optimum is socially optimal, PoA of the state is identical to MoS of the state. We show that the magnitude of strict Pareto inefficiency, MoS, of NE can increase without bounds in a networking game, even though the network has a finite amount of resources and a small number of noncooperative players.

In this paper, we study the secure routing for cluster-based sensor networks where clusters are formed dynamically and periodically. We point out the deficiency in the secure routing protocols with symmetric key pairing. Along with the investigation of ID-based cryptography for security in WSNs, we propose a new secure routing protocol with ID-based signature scheme for cluster-based WSNs, in which the security relies on the hardness of the Diffie-Hellman problem in the random oracle model. Because of the communication overhead for security, we provide analysis and simulation results in details to illustrate how various parameters act between security and energy efficiency.

We study in this paper a noncooperative approach for sharing resources of a common pool among users, wherein each user strives to maximize its own utility. The optimality notion is then a Nash equilibrium. First, we present a general framework of systems wherein a Nash equilibrium is Pareto inefficient, which are similar to the 'tragedy of the commons' in economics. As examples that fit in the above framework, we consider noncooperative flow-control problems in communication networks where each user decides its throughput to optimize its own utility. As such a utility, we first consider the power which is defined as the throughput divided by the expected end-to-end packet delay, and then consider another utility of additive costs. For both utilities, we establish the non-efficiency of the Nash equilibria.

This paper addresses the dynamic location management for personal communication service (PCS) networks with consideration of mobility patterns. The popular hexagonal cellular architecture is considered. In this paper, we first introduce a coordinate system for the hexagonal cellular architectures. Then, we develop an all-direction mobility model based on the coordinate system for the hexagonal cellular architecture to cope with the mobility patterns of mobile terminals (MTs). The shape and size of the local area (LA) in the dynamic location management scheme is determined by minimizing the total location management cost with bounding the paging cost The optimization problem is transferred to maximize expected number of cells traversed by the MT in the LA with a given size of the LA. The analytic model of calculating the probabilities of any MT's moving is established. An algorithm is proposed to solve the optimization problem efficiently.

A mobile ad hoc network (MANET) is the cooperative engagement of a collection of wireless mobile nodes without aid of any established infrastructure or centralized administration. The conventional security solutions to provide key management through accessing trusted authorities or centralized servers are infeasible for this new environment since mobile ad hoc networks are characterized by the absence of any infrastructure, frequent mobility, and wireless links. In this paper, we propose an on-demand, fully localized, and hop-by-hop public key management scheme for MANETs. It can be performed by generating public/private key pairs by nodes themselves, issuing certificates to neighboring nodes, holding these certificates in their certificate repositories, and providing an authentication service quickly adaptive to the dynamic topology of the network without relying on any servers. Also, our scheme can be performed successfully as long as there is a physical communication line between two nodes, and it is accustomed well to the on-demand routing of MANETs.

Consider networks in Wardrop equilibria, i.e., situations where each user in a network strives to optimize its own cost noncooperatively but has only an infinitesimal impact on other users. In computer networking, some shortest-path routing protocols that reflect link queueing delays may bring about situations close to Wardrop equilibria. The Braess (1968) paradox is a famous example of paradoxical cases where adding capacity to a network degrades the costs for all users. This paper investigates, in particular, networks generalized from what were studied by Cohen (1990, 1997), Kelly (1990), and Jeffries (1997) in comparison with the networks of the same topology as the original Braess network. The measure of cost degradation considered is the ratio of the cost for each user of a network after adding capacity (a link) to that before adding capacity. It has been shown that a value of the measure is less than 2 for every general Braess network. The results of this paper show that the measure of paradoxical cost degradation is also less than 2 for all of the networks considered in this paper.

In completely symmetric systems that have homogeneous nodes (hosts, computers, or processors) with identical arrival processes, an optimal static load balancing scheme does not involve the forwarding of jobs among nodes. Using an appropriate analytic model of a distributed computer system, we examine the following three decision schemes for load balancing: completely distributed, intermediately distributed, and completely centralized. We show that there is no forwarding of jobs in the completely centralized and completely distributed schemes, but that in an intermediately distributed decision scheme, mutual forwarding of jobs among nodes is possible, leading to degradation in system performance for every decision maker. This result appears paradoxical, because by adding communication capacity to the system for the sharing of jobs between nodes, the overall system performance is degraded. We characterize conditions under which such paradoxical behavior occurs, and we give examples in which the degradation of performance may increase without bound. We show that the degradation reduces and finally disappears in the limit as the intermediately distributed decision scheme tends to a completely distributed one.

The performance of parallel transaction processing systems can be degraded significantly due to data skew, a phenomenon of unbalanced data distribution over the nodes of a system. Rebalancing the data load of a system with data skew by redistributing its data is known to be an effective approach to cope with data skew. Unfortunately, for most of the existing approaches, the data being redistributed is unavailable (off-line). Numerous applications, such as those for reservations, finance, process control, hospitals, police and the armed forces, however, cannot afford off-line data for any significant amount of time. These applications call for the ability of balancing data load online. In this paper, a new online data redistribution approach is proposed. A prototype of the approach has been implemented, and experiments have been conducted. Experimental results confirm the substantial performance gains of the approach.

We study a dynamic mobility management scheme: the movement-based location update scheme. An analytical model is applied to formulate the costs of location update and paging in the movement-based location update scheme. The problem of minimizing the total cost is formulated as an optimization problem that finds the optimal threshold in the movement-based location update scheme. We prove that the total cost function is a convex function of the threshold. Based on the structure of the optimal solution, an efficient algorithm is proposed to find the optimal threshold directly. Furthermore, the proposed algorithm is applied to study the effects of changing important parameters of mobility and calling patterns numerically.

The movement based dynamic location update scheme is studied. An analytical model is applied to formulate the costs of location update and paging in the movement based location update scheme. The problem of minimizing the total cost is formulated as an optimization problem that finds the optimal threshold in the movement based location update scheme. We prove that the total cost function is a convex function of the threshold. Based on the structure of the optimal solution, an efficient algorithm is proposed to find the optimal threshold directly. Furthermore, the proposed algorithm is applied to study the effects of changing important parameters of mobility and calling patterns numerically.

Load balancing problems for multiclass jobs in distributed/parallel computer systems with general network configurations are considered. We construct a general model of such a distributed/parallel computer system. The system consists of heterogeneous host computers/processors (nodes) which are interconnected by a generally configured communication/interconnection network wherein there are several classes of jobs, each of which has its distinct delay function at each host and each communication link. This model is used to formulate the multiclass job load balancing problem as a nonlinear optimization problem in which the goal is to minimize the mean response time of a job. A number of simple and intuitive theoretical results on the solution of the optimization problem are derived. On the basis of these results, we propose an effective load balancing algorithm for balancing the load over an entire distributed/parallel system. The proposed algorithm has two attractive features. One is that the algorithm can be implemented in a decentralized fashion. Another feature is simple and straightforward structure. Models of nodes, communication networks, and a numerical example are illustrated. The proposed algorithm is compared with a well-known standard steepest-descent algorithm, the FD algorithm. By using numerical experiments, we show that the proposed algorithm has much faster convergence in terms of computational time than the FD algorithm.

We present an analytic model to study the reliability of some important disk array organizations that have been proposed by others in the literature. These organizations are based on the combination of two options for the data layout, regular RAID-5 and block designs, and three alternatives for sparing: hot sparing, distributed sparing and parity sparing. Uncorrectable bit errors have big effects on reliability but are ignored in traditional reliability analysis of disk arrays. We consider both disk failures and uncorrectable bit errors in the model. The reliability of disk arrays is measured in terms of MTTDL (Mean Time To Data Loss). A unified formula of MTTDL has been derived for these disk array organizations. The MTTDLs of these disk array organizations are also compared using the analytic model.

We study the static load balancing problem in a distributed computer system with the tree hierarchy configuration. It is formulated as a nonlinear optimization problem. After studying the conditions that the solution to the optimization problem of the tree hierarchy network satisfies, we demonstrate that the special structure of the optimization problem leads to an interesting decomposition technique. A new effective decomposition algorithm to solve the optimization problem is presented. The proposed algorithm Is compared with two other well known algorithms: the Flow Deviation (FD) algorithm and the Dafermos-Sparrow (D-S) algorithm. It is shown that the amounts of the storage required for the proposed algorithm and the FD algorithm are O(n) for load balancing of an n-node system. However, the amount of the storage required for the D-S algorithm is O(n log(n)). By using numerical experiments, we show that both the proposed algorithm and the D-S algorithm have much faster convergence in terms of central processing unit (CPU) time than the FD algorithm.>

This model is an extension of the Tantawi and Towsley (1985) single-job-class model as applied to a multiple-job-class model. Some properties of the optimal solution are shown. On the basis of these properties, a straightforward and efficient algorithm for optimal load balancing of multiclass jobs is derived. The performance of this algorithm is compared with that of two other well-known algorithms for multiclass jobs, the flow deviation (FD) algorithm and the Dafermos algorithm. The authors' algorithm and the FD algorithm both require a comparable amount of storage that is far less than that required by the Dafermos algorithm. Numerical experiments show that for obtaining the optimal solution the authors' algorithm and the Dafermos algorithm require comparable computation times that are far less than that of the FD algorithm.>

The scheduling of jobs for multiprogramming systems includes the selection of jobs to be loaded into memory (job loading policy or memory schedule) and the scheduling for CPU processing (CPU schedule). There has been a successful empirical claim for the optimal CPU schedule; its optimality has been proved in a Markovian model of job-stream processing that uses the first-come-first-loaded (FCFL) job loading policy. We extend this model to gain insight into the effects of job loading policies. The model studied consists of an input stream of jobs of two classes and a multiple-resource system (the model of a multiprogramming system) with a stack for waiting jobs. The system consists of a finite amount of memory and a cyclic queue of a single (CPU) server station and a multiple (I/O) server station. The values of parameters describing each class of jobs are distinct except the mean I/O service time and the amount of memory required. The estimate of the maximum processing capacity (throughput bound) of the system is obtained and is shown to be achieved by the combination of the empirically claimed optimal CPU schedule and a job loading policy whereby the set of jobs in memory is kept to be (nearly) balanced with respect to the job stream. Furthermore, we show that the job loading policies independent of the system status have no improvement over the FCFL policy. Our investigation, supported by numerical calculations, suggests that much more care may be needed in implementing the job loading policy that aims at the optimal processing capacity than in implementing the optimal CPU schedule. This agrees with what has been conjectured on the basis of empirical studies.

The effects of providing communication channels among computer systems located at different sites are studied. It is shown that the maximum utility at every site with computer communication can be greater (or at least not less) than that without communication. This can be achieved in such a way that, with communication, each computer system is more specialized in processing transactions of the types in which the system has comparative advantage and mutually exchanges the processed transactions through communication channels; the utility here is assumed to depend on performance. It is shown, however, that growth in computing resources at a site toward a higher degree of specialization may sometimes lead to a decrease in the maximum utility at the site.

It has been claimed on the basis of empirical studies that a CPU scheduling policy, whereby I/Obound jobs are given preemptive priority over CPU-bound jobs, produces the highest overall CPU utilization of multiprogrammed computer systems.However, a theoretical result has shown that the CPU utilization is independent of CPU scheduling in a finite-source queuing model of multiprogrammed systems.This paper aims at resolving this seeming conflict and gaining some insight into CPU scheduling by analyzing a Markovian model of job-stream processing.The model studied consists of an infinite backlog of jobs of two classes (a job stream} and a multiple-resource system (the model of a multiprogrammed system which processes the job stream}; the system consists of a cyclic queue of two nodes--a single (CPU) server and an infinite (I/O) server.The system contains a fixed number of jobs concurrently; the values of parameters describing each job class are distinct except for the mean I/O service time.The following result is obtained under the near-complete decomposability of the model: The maximum overall CPU server utilization (and the maximum throughput) is achieved by scheduling policy whereby jobs of the class having a shorter mean CPU service time are given preemptive priority over others at the CPU server, although the CPU server utilization is independent of CPU scheduling so long as the set of jobs in the system remains fixed.

A property of the normalization constants for closed single-class product-form queueing networks is derived under the condition that the service rate at each service center is not decreasing with the increase of the number of jobs staying at the center. The result implies that the throughput at each service center is monotonically increasing with the increase of the total number of jobs contained in the queueing network considered.

~STRACT A finite-source queuing model (sometimes called the finite-population, machine-interference, or machine-repairman model), which has often been used in analyzing time-sharing systems and multiprogrammed computer systems, is invesugated.The model studied here has two service staUons, a processor (single server) and peripherals (infinite server), and a finite number of customers (or jobs) that have a distract service rate at the processor.The model is in eqmhbnum.It is shown that the utilization factor of the processor can be obtained in an analyuc form and ts independent of various scheduling disciphnes employed at the processor, such as FCFS, generahzed processor sharing, preempUve (resume) and nonpreemptwe priority disciphnes, under some condiaon.Other relevant propemes of this model are also shown.The range within which these properties hold is discussed, and some examples are given.Examples of appficatlon to multiprogrammmg and tune-sharing systems are given; in particular, It Is shown that the often used dynamic dispatching pohcy (which gwes the higher preempuve priority to the more I/O oriented job) is optimal within the framework of this multiprogramming model.