32904961
Assignment-Based Partitioning in a Condition Monitoring System
A condition monitoring system tracks real-world variables and alerts users when a predefined condition becomes true, e.g., when enemy planes take off, or when suspicious terrorist activities and communication are detected. However, a monitoring server can easily get overwhelmed by rapid incoming data. To prevent this, we partition the condition being monitored and distribute the workload onto several independent servers. In this paper, we study the problem of how to make a partitioned system behave "equivalently" to a one-server system. We identify and formally define three desirable properties of a partitioned system, namely, orderedness, consistency, and completeness. We propose assignment-based partitioning as a solution that can handle opaque conditions and simplifies load balancing. We also look at a few typical partitioned systems, and discuss their merits using several metrics that we define. Finally, an algorithm is presented to reduce complex system configurations to simpler ones.
53245927
Cellular disco: resource management using virtual clusters on shared-memory multiprocessors
Despite the fact that large-scale shared-memory multiprocessors have been commercially available for several years, system software that fully utilizes all their features is still not available, mostly due to the complexity and cost of making the required changes to the operating system. A recently proposed approach, called Disco, substantially reduces this development cost by using a virtual machine monitor that laverages the existing operating system technology. In this paper we present a system called Cellular Disco that extends the Disco work to provide all the advantages of the hardware partitioning and scalable operating system approaches. We argue that Cellular Disco can achieve these benefits at only a small fraction of the development cost of modifying the operating system. Cellular Disco effectively turns a large-scale shared-memory multiprocessor into a virtual cluster that supports fault containment and heterogeneity, while avoiding operating system scalability bottlenecks. Yet at the same time, Cellular Disco preserves the benefits of a shared-memory multiprocessor by implementing dynamic, fine-grained resource sharing, and by allowing users to overcommit resources such as processors and memory. This hybrid approach requires a scalable resource manager that makes local decisions with limited information while still providing good global performance and fault containment. In this paper we describe our experience with a Cellular Disco prototype on a 32-processor SGI Origin 2000 system. We show that the execution time penalty for this approach is low, typically within 10% of the best available commercial operating system formost workloads, and that it can manage the CPU and memory resources of the machine significantly better than the hardware partitioning approach.
39326914
Parameterized subscriptions in publish/subscribe systems
Traditional publish/subscribe systems commonly deal with static subscriptions, whose event filtering criteria stay fixed once defined. Although systems with static subscriptions are simpler to implement, there are cases where the subscription criterion involves state that changes frequently over time. Rather than having the user re-submit his/her subscription repeatedly, we propose parameterized subscriptions as a systematic solution for adaptive subscriptions. Parameterized subscriptions depend on one or more parameters, which are state variables stored and maintained automatically by the publish/subscribe servers. In this paper, we modify traditional publish/subscribe protocols in order to deal with parameterized subscriptions. We then look at certain optimizations that improve the efficiency by controlling where and how much state is allocated in the system. Finally, we present a simple evaluation framework to illustrate the fundamental operating differences between several schemes.
3017976
Publish/Subscribe Tree Construction in Wireless Ad-Hoc Networks
Wireless ad-hoc publish/subscribe systems combine a publish/subscribe mechanism with wireless ad-hoc networking. The combination, although very attractive, has not been studied extensively in the literature. This paper addresses an important problem of such systems: how to construct an optimal publish/ subscribe tree for routing information from the source to all interested recipients. First we precisely define the optimality of a publish/subscribe tree by developing a metric to evaluate its "efficiency." The optimality metric takes into account both the goal of a publish/subscribe system (i.e., to route a set of events), and the characteristics of an ad-hoc network (for example, devices are resource limited). We propose a greedy algorithm, SHOPPARENT, which builds the publish/ subscribe tree in a fully distributed fashion. A key feature is that this algorithm can be "subscription-aware", allowing it to use publication/subscription information in order to find a better outcome. Our simulations show that SHOPPARENT's performance is within 15% of optimal under normal configurations. We also study the effect of geographically localized subscriptions.
26991946
Publish/Subscribe in a Mobile Environment
A publish/subscribe system dynamically routes and delivers events from sources to interested users, and is an extremely useful communication service when it is not clear in advance who needs what information. In this paper we discuss how a publish/subscribe system can be extended to operate in a mobile environment, where events can be generated by moving sensors or users, and subscribers can request delivery at handheld and/or mobile devices. We describe how the publish/subscribe system itself can be distributed across multiple (possibly mobile) computers to distribute load, and how the system can be replicated to cope with failures, message loss, and disconnections.
14183146
Replicated condition monitoring
A condition monitoring system tracks real-world variables and alerts users when a predefined condition becomes true, e.g., when stock price drops, or when a nuclear reactor over-heats. Replication of monitoring servers can reduce the probability that an important alert is missed. However, replicated independent servers can sometimes report “conflicting” alerts to the user, causing confusion. In this paper, we study the problem of replicated condition monitoring. We identify and formally define three desirable properties of a replicated system, namely, orderedness, consistency, and completeness. We propose new monitoring algorithms that enforce some or all of the desired properties in different scenarios.
41865724
Improved Image Coding with Classified VQ and Side-Match VQ
A new scheme for vector quantization (VQ) is proposed in this paper. We employ side-match and classified criteria for designing VQ codebooks to combat blocking effects induced from high compression rates, and then we use the proposed algorithm to improve the reconstructed image quality. Simulation results demonstrate the better image quality to compare with that produced from conventional schemes objectively and subjectively, at the cost of reasonable encoding complexity.
14512108
MCMSDA: a multi-channel multi-sector directional antenna wireless LAN
Recently there is an increasing interest in using directional antennas and multi-channel for ad-hoc wireless networks. The two techniques can also be used for infrastructure local area networks. In this paper, we present the architecture and the MAC layer design for a multi-channel multi-sector directional antenna wireless local area network (MCMSDA WLAN). This paper has three key components. First, we describe the network architecture and propose a TDMA-based MAC layer. Second, we formulate the channel time allocation problem as an optimization problem and introduce a Lagrangian relaxation based load-balancing algorithm as a solution. The simulation study shows that the algorithm obtains good sub-optimal solution very quickly. Finally, we propose two methods to accelerate the load-balancing process further
18171732
Data Placement in Intermittently Available Environments
In this paper, we address the problem of data placement in a grid based multimedia environment, where the resource providers, i.e. servers, are intermittently available. The goal is to optimize the system performance by admitting maximum number of users into the system while ensuring user Quality of Service (QoS). We define and formulate various placement strategies that determine the degree of replication necessary for video objects by using a cost-based optimization procedure based on predictions of expected requests under various time-map scenarios and QoS demands. We also devise methods for dereplication of videos based on changes in popularity and server usage patterns. Our performance results indicate the benefits obtained the judicious use of dynamic placement strategies.
14716028
New Upper Bounds for Ramsey Numbers
The Ramsey numberR(G1,G2) is the smallest integerpsuch that for any graphGonpvertices eitherGcontainsG1orGcontainsG2, whereGdenotes the complement ofG. LetR(m,n)=R(Km,Kn). Some new upper bound formulas are obtained forR(G1,G2andR(m,n), and we derive some new upper bounds for Ramsey numbers here.
6591350
Inferring Ongoing Activities of Workstation Users by Clustering Email
We are interested in automatically discovering the key ongoing activities of a workstation user, such as committees to which she belongs, writing projects in which she is involved, etc., based on the contents of her workstation. The thesis underlying our research is that this collection of user activities can be automatically inferred from the variety of data available on most users’ workstations, including their emails, files, online calendar, and history of web page accesses. Knowledge about the user's activities could be used in a variety of ways, such as cross-indexing email, calendar events, files, and web accesses according to activity, or automatically producing a 'briefing folder' for each meeting on the user's calendar. We describe here our initial research on inferring such activities by examining only the user's email. In particular, we describe a variety of unsupervised clustering methods designed for clustering emails by user activity, and the use of information extractors and pretrained classifiers to infer additional information about each discovered cluster. Experimental results are presented for emails from three users.