Markov decision processes and regular events

Desirable properties of the infinite histories of a finite-state Markov decision process are specified in terms of a finite number of events represented as ω-regular sets. An infinite history of the process produces a reward which depends on the properties it satisfies. The authors investigate the existence of optimal policies and provide algorithms for the construction of such policies     

Minimum and maximum delay problems in real-time systems

We consider a finite-state system with a finite number of clocks, where the transitions may depend on the values of the clocks, and may reset some of the clocks. We address the complexity and provide algorithms for the following problems. Suppose that the system starts from a given current state with a given assignment of values to the clocks. Can a given target state ever appear in the history of the system? What is the earliest time it can appear? What is the latest time it can appear?     

Pricing Differentiated Services in the GPRS Environment

The General Packet Radio Service extends the existing GSM mobile communications technology by providing packet switching and higher data rates in order to efficiently access IP-based services in the Internet. We adapt the Differentiated Services Quality-of-Service support framework and apply it over the GPRS air interface in order to provide various levels of service differentiation. We also focus on applying a charging technique so as to publish a unit price for each service class. These prices are designed to lead to the maximization of social welfare and the users' net benefit.     

Incentives for large peer-to-peer systems

We consider problems of provisioning an excludable public good amongst n potential members of a peer-to-peer system who are able to communicate information about their private preferences for the good. The cost of provisioning the good in quantity Q depends on Q, and may also depend on n, or on the final number of participating peers m. Our aim is to maximize the expected social welfare in a way that is incentive compatible, rational and budget-balanced. Although it is unfortunately almost never possible to calculate or implement a truely optimal mechanism design, we show that as the number of participants becomes large the expected social welfare that can be obtained by the optimal design is at most a factor 1+O(1/n) or 1+O(1//spl radic/n) greater than that which can be obtained with a very simple scheme that requires only payment of a fixed contribution from any agent who joins the system as a participating peer. Our first application is to a model of file sharing, in which the public good is content availability; the second concerns a problem of peering wireless local area networks, in which the public good is the availability of connectivity for roaming peers. In both problems, we can cope with the requirement that the payments be made in kind, rather than in cash.     

Memory-efficient algorithms for the verification of temporal properties

This article addresses the problem of designing memory-efficient algorithms for the verification of temporal properties of finite-state programs. Both the programs and their desired temporal properties are modeled as automata on infinite words (Büchi automata). Verification is then reduced to checking the emptiness of the automaton resulting from the product of the program and the property. This problem is usually solved by computing the strongly connected components of the graph representing the product automaton. Here, we present algorithms that solve the emptiness problem without explicitly constructing the strongly connected components of the product graph. By allowing the algorithms to err with some probability, we can implement them with a randomly accessed memory of size O(n) bits, where n is the number of states of the graph, instead of O(n log n) bits that the presently known algorithms require.     

Serving process with least thinking time maximizes resource utilization

A fixed number of processes (users) share a common resource. Each process is described by a Markov chain with a "thinking" state and a "request" for service state. A policy is a preemptive scheme that assigns the resource to one of the simultaneously requesting processes. The policy that maximizes resource utilization assigns the resource to the process with least thinking time.     

Application of the many sources asymptotic and effective bandwidths to traffic engineering

Accurate yet simple methods for traffic engineering are important for efficient management of resources in broadband networks. The goal of this paper is to apply and evaluate large deviation techniques for traffic engineering. In particular, we employ the recently developed theory of effective bandwidths, where the effective bandwidth depends not only on the statistical characteristics of the traffic stream, but also on a link’s operating point through two parameters, the space and time parameters, which can be computed using the many sources asymptotic. We show that this effective bandwidth definition can accurately quantify resource usage. Furthermore, we estimate and interpret values of the space and time parameters for various mixes of real traffic demonstrating how these values can be used to clarify the effects on the link performance of the time scales of traffic burstiness, of the link resources (capacity and buffer), and of traffic control mechanisms such as traffic shaping. Our experiments involve a large set of MPEG‐1 compressed video and Internet Wide Area Network (WAN) traces, as well as modeled voice traffic. This revised version was published online in June 2006 with corrections to the Cover Date.     

A game-theoretic view of two processes using a single resource

Two processes are served on a first-come, first-serve basis by a single resource (server). The thinking and resource holding times of both processes are exponential with different parameters. It is proved that, under a scaling condition, no cooperation of the processes can improve both of their resource utilizations.     

A marketplace and its market mechanism for trading commoditized computing resources

This paper presents the design and implementation of the GridEcon Marketplace. In addition to supporting a market mechanism for trading computing resources on a pay-per-use basis, this marketplace also provides an environment for integrating value-added support services. These value-added services help consumers to use the utility computing market more efficiently. The GridEcon Market Mechanism for virtual machines specifies in detail the unit-of-trade, the bids and asks, as well as the matching algorithm. The marketplace and market mechanism are validated by using the GridEcon Platform, which is a service-oriented platform for composing market scenarios. Our validation results show that the GridEcon Marketplace fulfills all functional requirements and that the GridEcon Market Mechanism is computationally and economically efficient.