16064988
Enhancing Service Location Protocol for efficiency, scalability and advanced discovery
This paper presents three new mechanisms for the Service Location Protocol (SLP): mesh enhancement, preference filters and global attributes. The mesh enhancement simplifies Service Agent (SA) registrations and improves consistency among Directory Agents (DAs) by defining an interaction scheme for DAs and supporting automatic registration distribution among peer DAs. Preference filters facilitate processing of search results (e.g., finding the best match) in SLP servers (DAs and SAs) to reduce the amount of data transferred to the client for saving network bandwidth. Global attributes allow using a single query to search services across multiple types. These mechanisms can improve SLP efficiency and scalability and support advanced discovery such as discovering multi-access-point services and multi-function devices. We expect that these techniques can also be applied to other service discovery systems.
9589474
DotSlash: A Self-Configuring and Scalable Rescue System for Handling Web Hotspots Effectively
DotSlash allows different web sites to form a mutual-aid community, and use spare capacity in the community to relieve web hotspots experienced by any individual site. As a rescue system, DotSlash intervenes when a web site becomes heavily loaded, and is phased out once the workload returns to normal. It aims to complement the existing web server infrastructure to handle short-term load spikes effectively. DotSlash is self-configuring, scalable, cost-effective, easy to use, and transparent to clients. It targets small web sites, although large web sites can also benefit from it. We have implemented a prototype of DotSlash on top of Apache. Experiments show that using DotSlash a web server can increase the request rate it supported and the data rate it delivered to clients by an order of magnitude, even if only HTTP redirect is used. Parts of this work may be applicable to other services such as Grid computational services.
45502875
DotSlash - Creating Content Distribution Networks on Demand
Traditional content distribution networks, such as Akamai, are well-suited for static web services that routinely experience large traffic volumes. They are unsuited for active content, i.e., content generated by scripts from databases, and web sites that are unlikely to receive significant number of requests. However, a few such sites will invariably experience their "fifteen minutes of fame", typically by being mentioned on a high-volume news site such as SlashDot or CNN. Such flashcrowds or "slashdot effect" will routinely cause single-server websites to collapse. We have designed and prototyped an autonomic web replication system, called DotSlash, that drafts rescue servers fully automatically, without user intervention. The system discovers suitable rescue servers via wide-area service location, either among peer servers or from a dedicated pool of rescue servers, allocates them for temporary use and redirects requests to them. The system is completely transparent to clients and does not require URL rewriting or other client modifications. We have designed two versions. The first, an Apache extension, deals only with static content, e.g., HTML pages or media objects. The second version can also replicate and execute scripts remotely. We have prototyped the system for the common LAMP (Linux, Apache, MySQL and PHP) configuration and shown that a common benchmark for bulletin boards can be replicated without code changes, yielding capacity increases bounded only by the database server. Since many such systems, including most blogs, are bottlenecked by the web server, our system can significantly increase capacity and works even for extremely rapid load increases. We are currently investigating how such systems can be further extended by increasing the database capacity of read-mostly systems with loose consistency constraints.
30153007
Selective anti-entropy
Anti-entropy [1] is an important mechanism to achieve eventual consistency among a set of replicas. We refer to traditional antientropy [2, 3] as complete anti-entropy, where two replicas reconcile all inconsistent states between them in a two-way session or two one-way sessions. Complete anti-entropy works well in full replications, but may cause a summary problem (a replica cannot summarize its received updates using a summary vector) in partial replications (where the state set is divided into subsets referred to as scopes). To avoid the summary problem, we propose to use selective anti-entropy, which is to selectively reconcile inconsistent states between two replicas in a session, i.e., a replica specifies the subsets of updates it solicits, and thus controls what it receives from another replica. In selective anti-entropy, all updates that are initially received by the same replica R= belong to the same s u b s e t / ~ . The subset of a state is determined by the last update applied to it. A selective anti-entropy session where R¢ requests new updates in -P~i, Rx2, .... R~ k from R~ is denoted as O(R~, {/:/=~, Rx2, ..., R=k }, R~). We distinguish four types of selective anti-entropy sessions (listed in Figure 1) based on the number of subsets requested and whether the session is direct or indirect. We assume that a replica R¢ does not request updates in ~ from other replicas. A session is direct if it only requests updates in R--~ from R= (e.g., O___(R~, { ~ } , R~)), otherwise the session is indirect (e.g., O(R=, {1-~u}, R~)) or mixed (e.g., O(_R=, {R~, R~}, R~)). A select-multiple or select-all session can be viewed as comprising k (k >_ 2) select-one sessions, in which at most one is select-one-direct session, and the rest are select-one-indirect sessions. A select-all session is equivalent to a complete anti-entropy session. An anti-entropy session is safe if it will not cause the summary problem. A replica can always choose safe sessions by using selective anti-entropy. Any select-one-direct anti-entropy session, such as O(R=, {R~}, R~), is safe. A select-one-indirect anti-entropy session O(R=, {R-~y}, R~) is safe if S(R=) A S(Ru) C_ S(R~), where S(R=), S(Ru) and S(Rz) denote the scopes of Re, Rv and R~, respectively. In other words, if S(R=) n S(Ru) D S(R=), O(R=, {R-~}, Rz) may cause the summary problem. In Figure 2, for example, O(Ra, {R1}, R6) is safe because S(Ra) N S(R1) = {$1, $2} = S(R6) , but O(R3, {R6}, R2) may not be safe since
1315595
An energy-efficient slack distribution technique for multimode distributed real-time embedded systems
In multimode distributed systems, active task sets are assigned to their distributed components for realizing one or more functions. Many of these systems encounter runtime task variations at the input and across the system while processing their tasks in real time. Very few efforts have been made to address energy efficient scheduling in these types of distributed systems. In this paper, we propose an analytical model for energy efficient scheduling in distributed real-time embedded systems to handle time-varying task inputs. A new slack distribution scheme is introduced and adopted during the schedule of the task sets in the system. The slack distribution is made according to the service demand at the nodes which affects the energy consumption in the system. The active component at a node periodically determines the service rate and applies voltage scaling according to the dynamic traffic condition observed at various network nodes. The proposed approach uses a comprehensive traffic description function at nodes and provides adequate information about the worst-case traffic behavior anywhere in the distributed network, thereby enhancing the system power management capabilities. We evaluate the proposed technique using several benchmarks employing an event driven simulator and demonstrate its performance for multimode applications. Experimental results indicate significant energy savings in various examples and case studies.
14103668
Static priority scheduling for ATM networks
Static priority scheduling is popular for traffic scheduling in ATM switches because it is less costly than dynamic priority scheduling while being sensitive to the delay constraints of connections. We study delay computation and priority assignment problems in an ATM network with static priority scheduling. Given an ATM network with arbitrary topology, it is possible that the traffic on it may become unstable (i.e., packet delays become unbounded) due to the potential cyclic dependency of the traffic. An unstable network is definitely unacceptable for many delay sensitive applications. We start by formally deriving a simple condition under which the network is guaranteed to be stable. We then develop a numerical method to compute worst case end to end delays in an ATM network with arbitrary topology. Convergence of the method is formally proved and a closed form for the computing error is obtained. Despite its advantages, static priority scheduling remains sensitive to proper priority assignment. We describe two simple priority assignment methods, which we show to outperform other commonly used methods.
22872614
Performance evaluation of scheduling algorithms for imprecise computer systems
Abstract We study the scheduling of tasks in computer systems which utilize imprecise (partial) computations. In our system, tasks arrive randomly during run-time. Each task has two levels of computation time requirements: the full level computation requirement and the reduced level computation requirement. The reduced level computation of a task takes less time to accomplish than the full level, but produces results which are not as precise as those of full-level computation. We assume that the imprecise results are nonetheless acceptable. The tasks are scheduled in the following way: If the total number of tasks in the system is no more than M —a system parameter—the tasks are executed at the full level. When the total number of tasks exceeds M , the tasks are executed at the reduced level. The system performance under this kind of scheduling and computation model is analyzed. Attention is devoted to development of the explicit formulas for the practically important performance metrics such as the normalized mean task waiting time, the mean task served computation time, and the fraction of tasks fully processed. The effect of variations in parameter values on the system performance is also examined in detail.
3436856
Distributed Privacy Preserving Information Sharing
In this paper, we address issues related to sharing information in a distributed system consisting of autonomous entities, each of which holds a private database. Semi-honest behavior has been widely adopted as the model for adversarial threats. However, it substantially underestimates the capability of adversaries in reality. In this paper, we consider a threat space containing more powerful adversaries that includes not only semi-honest but also those malicious adversaries. In particular, we classify malicious adversaries into two widely existing subclasses, called weakly malicious and strongly malicious adversaries, respectively. We define a measure of privacy leakage for information sharing systems and propose protocols that can effectively and efficiently protect privacy against different kinds of malicious adversaries.
9972438
New delay analysis in high speed networks
The implementation of bounded-delay services over integrated services networks relies admission control mechanisms that in turn use end-to-end delay computation algorithms. For guaranteed-rate scheduling algorithms such as fair queueing, delay computation based on Cruz's service curve model performs very well. Many currently deployed networks, be they packet-switched or ATM based, rely on non-guaranteed-rate disciplines, most prominently FIFO and static-priority disciplines. We show that for this class of disciplines the service curve model performs poorly. We propose the Integrated Approach as alternative to the service curve model to cluster servers for delay computation purposes, and show in a series of evaluations that this new approach outperforms approaches based on the service curve model as well as other currently used approaches.