16820775
Nonconvexity issues for Internet rate control with multiclass services: stability and optimality
In this paper, we investigate the problem of distributively allocating transmission rates to users on the Internet. We allow users to have concave as well as sigmoidal utility functions that are natural in the context of various applications. In the literature, for simplicity, most works have dealt only with the concave case. However, we show that when applying rate control algorithms developed for concave utility functions in a more realistic setting (with both concave and sigmoidal types of utility functions), they could lead to instability and high network congestion. We show that a pricing based mechanism that solves the dual formulation can be developed based on the theory of subdifferentials with the property that the prices "self-regulate" the users to access the resource based on the net utility. We discuss convergence issues and show that an algorithm can be developed that is efficient in the sense of achieving the global optimum when there are many users.
32342128
Performance Analysis of an Input Queueing ATM Switch with Two Priority Classes
Abstract In this paper, we study an input queueing asynchronous transfer mode (ATM) switch with the preemptive priority scheme. Up to now, many researchers have studied this switch, but their models do not yield accurate results. Therefore, we propose another model and analyze the performance of the switch for two different arrival processes, that is, the independent priority arrival process (IPAP) and the dependent priority arrival process (DPAP). In this paper, we model a virtual head of line (HOL) queue like the previous works, and analyze it using a three-dimensional Markov chain. As for each input queue, we model it as a two-class Geomx/Geom/1 queue with preemptive priority. By using this model, we obtain the mean queueing delay of the low priority class and the maximum throughput of the switch. In case of the IPAP, we compare our result with simulation and those of the previous works to show that our model yields more accurate results. In addition, we compare the performances of those two arrival processes to illustrate their difference.
11623554
Downlink power allocation for multi-class CDMA wireless networks
We use a utility based power allocation framework in the downlink to treat multi-class CDMA wireless services in a unified way. Our goal is to obtain a power allocation which maximizes the total system utility. Natural utility functions for each mobile are non-concave. Hence we cannot use existing techniques on convex optimization problems to derive a social optimal solution. We propose a simple distributed algorithm to obtain an approximation to the social optimal power allocation. The algorithm is based on dynamic pricing and allows partial cooperation between mobiles and the base station. The algorithm consists of two stages. At the first stage, the base station selects mobiles to which power is allocated, considering their partial-cooperative nature. This is called partial-cooperative optimal selection, since in a partial-cooperative setting and pricing scheme, this selection is optimal and satisfies system feasibility. At the next stage, the base station allocates power to the selected mobiles. This power allocation is a social optimal power allocation among mobiles in the partial-cooperative optimal selection, thus, we call it a partial-cooperative optimal power allocation. We compare the partial-cooperative optimal power allocation with the social optimal power allocation for the single class case. From these results, we infer that the system utility obtained by partial-cooperative optimal power allocation is quite close to the system utility obtained by social optimal allocation.
12603358
Resource Volume Management for Shared File System in SAN Environment
In this paper, a volume management scheme that supports multi-host environments is designed and implemented. The proposed scheme provides various features for enterprise internet services such as online resizing, online migration and an enhanced configuration scheme considering workload access patterns and disk geometry. The SANfs is a shared file system in which multiple hosts can share multiple disks via a storage area network (SAN). SANfs is designed to provide high storage I/O performance and reliability to support the internet web server, but various features of SANfs are limited by traditional storage management technology; therefore, a volume management scheme for SANfs is required. The designed volume manager in this paper, called SANfsVM, can maximize the performance of SANfs and provide SANfs with high storage volume scalability and availability. It can provide SANfs with maximum system uptime and unlimited storage capacity using online resizing management. SANfs-VM can also provide the opportunity to use the disk characteristics and access patterns of system workloads by utilizing an enhanced configuration scheme.
1712871
Quasi-interpolants Based Multilevel B-Spline Surface Reconstruction from Scattered Data
This paper presents a new fast and local method of 3D surface reconstruction for scattered data. The algorithm makes use of quasi-interpolants to compute the control points from a coarse to fine hierarchy to generate a sequence of bicubic B-spline functions whose sum approaches to the desired interpolation function. Quasi-interpolants gives a procedure for deriving local spline approximation methods where a B-spline coefficient only depends on data points taken from the neighborhood of the support corresponding B-spline. Experimental results demonstrate that high-fidelity reconstruction is possible from a selected set of irregular samples.
14116288
A Practitioner's Approach to Normalizing XQuery Expressions
XQuery becomes a standard of the XML query language. Just like in SQL, XQuery allows nested expressions. To optimize XQuery processing, a lot of research has been done on normalization, i.e., transforming nested expressions to equivalent unnested ones. Previous normalization rules are classified into two categories – source-level and algebra-level – depending on whether a construct is specified by using a query language or an algebraic expression. In implementation point of view, we contend that the source-level rule is preferable to the algebra-level rule because algebras used for normalization are hard to be directly exploited in a typical DBMS. However, a complete set of source-level rules is yet to be developed. In this paper, we propose source-level rules for normalizing XQuery expressions and present an implementation mechanism. We show that our rules are correct and complete according to the nesting types classified by Kim. Our mechanism is easily implementable since it adapts the well-known Query Graph Model (QGM) representation. We have successfully implemented this mechanism into our XML DBMS named Odysseus/XML.
948007
A Microeconomic Approach to Intelligent Resource Sharing in Multiagent Systems
Abstract : We have analyzed characteristics of sharable resources and developed techniques for intelligently sharing resources specifically, communication channels among agents in multiagent systems. Our techniques allow agents to nearly optimize their communication behavior in a self-organizing and distributed fashion, involving the use of a microeconomic pricing system based on economic laws of supply and demand and trading among agents in real-time. Our analyses are based on three measures of performance: fairness of resource allocation, waiting time for resources, and utilization of resources. Our initial analysis indicates that fairness and utilization are conflicting, in that the best utilization with a fair allocation is equivalent to the worst utilization with an unfair resource allocation, assuming the allocation policy is statically defined. To strike a balance in performance, we have developed mechanisms that establish an artificial economy, where agents can dynamically reallocate goods (resource access) using a competitive market pricing mechanism. However, unlike more common market-oriented methods, our approach does not demand convergence to equilibrium, but permits more rapid, heuristic trading, leading to near optimal performance where both buyers and sellers of resources can benefit. Our studies show that agents employing our mechanisms can dramatically improve utilization while still providing fair access to the resources.
13264531
An efficient scattered data approximation using multilevel B-splines based on quasi-interpolants
In this paper, we propose an efficient approximation algorithm using multilevel B-splines based on quasi-interpolants. Multilevel technique uses a coarse to fine hierarchy to generate a sequence of bicubic B-spline functions whose sum approaches the desired interpolation function. To compute a set of control points, quasi-interpolants gives a procedure for deriving local spline approximation methods where a B-spline coefficient only depends on data points taken from the neighborhood of the support corresponding the B-spline. Experimental results show that the smooth surface reconstruction with high accuracy can be obtained from a selected set of scattered or dense irregular samples.