With the ever increasing popularity of smart phones, mobile services have been evolving rapidly to allow users to enjoy localized and personalized experiences. Users can discover local information and keep connected with family and friends on the go, and ultimately to experience the convergence of cyber space and physical world where digital technologies are interwoven into the day-to-day life. A pivotal component of such a cyber-physical convergence is the contextual intelligence. The extraction and dissemination of contextual information around users is the key for the cyber capabilities to be applied to physical activities and for the cyber world to better reflect the physical reality. In this talk, we shall address some issues arising from context-based mobile services. In particular, we discuss how mobility impacts contextual relevancy and personalization in mobile services. The relevancy and timeliness of contextual information not only are essential for these services to deliver great user experiences, but also put significant computation pressure on service infrastructure that processes continuous data streams in real time and disseminate relevant data to a large amount of mobile users. This talk will explore the challenges and opportunities for high-performance computing in mobile services. Based on key findings from large-scale mobile measurement data, the talk will analyze the tradeoff of different computing architectures, present case studies of scalable system design and implementation for personalized mobile services, and conclude with open challenges for the broad research community in performance measurement and modeling.

Stream processing is widely used by today's applications such as financial data analysis and disaster response. In distributed stream processing systems, machine fail-stop events are handled by either active standby or passive standby. However, existing high availability (HA) schemes have not sufficiently addressed the situation when a machine becomes temporarily unavailable due to data rate spikes, intensive analysis or job sharing, which happens frequently but lasts for short time. It is not clear how well active and passive standby fare against such transient unavailability. In this paper, we first critically examine the suitability of active and passive standby against transient unavailability in a real testbed environment. We find that both approaches have advantages and drawbacks, but neither is ideal to provide fast recovery at low overhead as required to handle transient unavailability. Based on the insights gained, we propose a novel hybrid HA method that switches between active and passive standby modes depending on the occurrence of failure events. It presents a desirable tradeoff that is different from existing HA approaches: low overhead during normal conditions and fast recovery upon transient or permanent failure events. We have implemented our hybrid method and compared it with existing HA designs with comprehensive evaluation. The results show that our hybrid method can reduce two-thirds of the recovery time compared to passive standby and 80% message overhead compared to active standby, allowing applications to enjoy uninterrupted processing without paying a high premium.

Many emerging information processing applications require applying various fork and join type operations such as correlation, aggregation, and encoding/decoding to data streams in real-time. Each operation will require one or more simultaneous input data streams and produce one or more output streams, where the processing may shrink or expand the data rates upon completion. Multiple tasks can be co-located on the same server and compete for limited resources. Effective in-network processing and resource management in a distributed heterogeneous environment is critical to achieving better scalability and provision of quality of service. In this paper, we study the distributed resource allocation problem for a synchronous fork and join processing network, with the goal of achieving the maximum total utility of output streams. Using primal and dual based optimization techniques, we propose several decentralized iterative algorithms to solve the problem, and design protocols that implement these algorithms. These algorithms have different strengths in practical implementation and can be tailored to take full advantage of the computing capabilities of individual servers. We show that our algorithms guarantee optimality and demonstrate through simulation that they can adapt quickly to dynamically changing environments.

This paper addresses the problem of distributed resource allocation in general fork and join processing networks. The problem is motivated by the complicated processing requirements arising from distributed data intensive computing. In such applications, the underlying data processing software consists of a rich set of semantics that include synchronous and asynchronous data fork and data join. The different types of semantics and processing requirements introduce complex interdependence between various data flows within the network.

Multipath streaming protocols have recently attracted much attention because they provide an effective means to provide high-quality streaming over the Internet. However, many existing schemes require a long start-up delay and thus are not suitable for interactive applications such as video conferencing and tele-presence. In this paper, we focus on real-time live streaming applications with stringent end-to-end latency requirement, say several hundreds of milliseconds. To address these challenges, we take a joint multipath and FEC approach that intelligently splits the FEC-encoded stream among multiple available paths. We develop an analytical model and use asymptotic analysis to derive closed-form, optimal load splitting solutions, which are surprisingly simple yet insightful. To our best knowledge, this is the first work that provides such closed-form optimal solutions. Based on the analytical insights, we have designed and implemented a novel encoded multipath streaming (EMS) scheme for real-time live streaming. EMS strives to continuously satisfy the application's QoS requirements by dynamically adjusting the load splitting decisions and the FEC settings. Our simulation results have shown that EMS can not only outperform the existing multipath streaming schemes, but also adapt to the dynamic loss and delay characteristics of the network with minimal overhead.

Federated systems have recently attracted much attention because they allow loosely coupled organizations to share resources for common benefits. However, discovering resources across administrative boundaries is challenging. Despite their willingness to share resources, many organizations prefer not to export their internal resource description to unfamiliar parties. While it is highly desirable to facilitate such voluntary sharing, the system also needs to resolve resource queries in an efficient manner. Unfortunately, none of the existing resource discovery designs, either hierarchical or DHT-based, can address these two challenges in the same time.In this paper, we present the design and evaluation of ROADS, a Replication Overlay Assisted resource Discovery Service for federated systems. In ROADS, the resource owners only export summaries, which are condensed representations of their resource records. These summaries are aggregated along a hierarchy and used to direct queries to appropriate resource owners. To improve its efficiency and resiliency, ROADS replicates the summaries using server overlays that enable "shortcuts'' in query forwarding. We have implemented ROADS and evaluated its performance through extensive analysis and experiments. The results show that ROADS outperforms a DHT-based design with 1-2 orders of magnitude less overhead in update messages and 50% less query forwarding time.

The Web services research community has proposed a number of approaches for service composition, ranging from manual to semi-automatic to completely automatic. However, it is often difficult to take independently developed services and compose them, since they may not work together correctly. For service composition to occur, the services in question must be designed and developed in a manner that facilitates their composition. In this paper, we propose a novel approach for service design and composition that combines top-down and bottom-up elements. Our approach is driven by faceted, tag-based functional requirements provided by end-users. These requirements describe, at a high-level, the families of compositions that end-users desire. The requirements kick off a top-down service development lifecycle, where enterprise architects and service developers design, develop and test workflows and services, possibly reusing existing flows and services in the process. At runtime, end-users can specify goals, which are satisfied through a bottom-up composition of flows from the available services. The composed flows include those explicitly designed by the architects as well as new ones that are assembled in a serendipitous manner from the available services. With examples from a case study in the financial services domain, we demonstrate our approach for designing and developing services that can be composed into myriad workflows based on end-user goals.

As mobile nodes roam in a wireless network, they continuously associate with different access points and perform handoff operations. However, frequent handoffs can potentially incur unacceptable delays and even interruptions for interactive applications. To alleviate these negative impacts, we present novel association control algorithms that can minimize the frequency of handoffs occurred to mobile devices. Specifically, we show that a greedy LookAhead algorithm is optimal in the offline setting, where the user's future mobility is known. Inspired by such optimality, we further propose two online algorithms, namely LookBack and Track, that operate without any future mobility information. Instead, they seek to predict the lifetime of an association using randomization and statistical approaches, respectively. We evaluate the performance of these algorithms using both analysis and trace-driven simulations. The results show that the simple LookBack algorithm has surprisingly a competitive ratio .of (log k + 2), where k is the maximum number of APs that a user can hear at any time, and the Track algorithm can achieve near-optimal performance in practical scenarios.

Recent advances in computer technology and wireless communications have enabled the emergence of stream-based sensor networks. In such sensor networks, real-time data are generated by a large number of distributed sources. Queries are made that may require sophisticated processing and filtering of the data. A query is represented by a query graph. In order to reduce the data transmission and to better utilize resources, it is desirable to place operators of the query graph inside the network, and thus to perform in-network processing. Moreover, given that various queries occur with different frequencies and that only a subset of sensor data may actually be queried, caching intermediate data objects inside the network can help improve query efficiency. In this paper, we consider the problem of placing both operators and intermediate data objects inside the network for a set of queries so as to minimize the total cost of storage, computation, and data transmission. We propose distributed algorithms that achieve optimal solutions for tree-structured query graph topologies and general network topologies. The algorithms converge in Lmax(.HQ+ 1) iterations, where Lmaxis the order of the diameter of the sensor network, and Hq represents the depth of the query graph, defined as the maximum number of operations needed for a raw data to become a final data. For a regular grid network and complete binary tree query graph, the complexity is 0(radic(N)log2M), where N is the number of nodes in the sensor network and M is the number of data objects in a query graph. The most attractive features of these algorithms are that they require only information exchanges between neighbors, can be executed asynchronously, are adaptive to cost change and topology change, and are resilient to node or link failures.

In the realm of component-based software systems, pursuers of the holy grail of automated application composition face many significant challenges. In this paper we argue that, while the general problem of automated composition in response to high-level goal statements is indeed very difficult to solve, we can realize composition in a restricted context, supporting varying degrees of manual to automated assembly for specific types of applications. We propose a novel paradigm for composition in flow-based information processing systems, where application design and component development are facilitated by the pervasive use of faceted, tag-based descriptions of processing goals, of component capabilities, and of structural patterns of families of application. The facets and tags represent different dimensions of both data and processing, where each facet is modeled as a finite set of tags that are defined in a controlled folksonomy. All data flowing through the system, as well as the functional capabilities of components are described using tags. A customized AI planner is used to automatically build an application, in the form of a flow of components, given a high-level goal specification in the form of a set of tags. End-users use an automatically populated faceted search and navigation mechanism to construct these high-level goals. We also propose a novel software engineering methodology to design and develop a set of reusable, well-described components that can be assembled into a variety of applications. With examples from a case study in the Financial Services domain, we demonstrate that composition using a faceted, tag-based application design is not only possible, but also extremely useful in helping end-users create situational applications from a wide variety of available components.

We consider a fundamental flow maximization problem that arises during the evaluation of multiple overlapping queries defined on a data stream, in a heterogenous parallel environment. Each query is a conjunction of boolean filters, and each filter could be shared across multiple queries. We are required to design an evaluation plan that evaluates filters against stream items in order to determine the set of queries satisfied by each item. The evaluation plan specifies for each item: (i) the subset of filters evaluated for this item and the order of their evaluations, and (ii) the processor on which each filter evaluation occurs. Our goal is to design an evaluation plan which maximizes the total throughput (flow) of the stream handled by the plan, without violating the processor capacities.

We consider the problem of evaluating multiple overlapping queries defined on data streams, where each query is a conjunction of multiple filters and each filter may be shared across multiple queries. Efficient support for overlapping queries is a critical issue in the emerging data stream systems, and this is particularly the case when filters are expensive in terms of their computational complexity and processing time. This problem generalizes other well-known problems such as pipelined filter ordering and set cover, and is not only NP-Hard but also hard to approximate within a factor of o(log n) from the optimum, where n is the number of queries. In this paper, we present two near-optimal approximation lgorithms with provably-good performance guarantees for the evaluation of overlapping queries. We present an edge-coverage based Greedy algorithm which achieves an approximation ratio of (1 + log(n) + log(α)), where n is the number of queries and α is the average number of filters in a query. We also present a randomized, fast and easily parallelizable Harmonic algorithm which achieves an approximation ratio of 2β, where β is the maximum number of filters in a query. We have implemented these algorithms in a prototype system, and evaluated their performance using extensive experiments in the context of multimedia stream analysis. The results show that our Greedy algorithm consistently outperforms other known algorithms under various settings and scales well as the numbers of queries and filters increase.

With the emergence of Yahoo Pipes and several similar services, data mashup tools have started to gain interest of business users. Making these tools simple and accessible ton users with no or little programming experience has become a pressing issue. In this paper we introduce MARIO (Mashup Automation with Runtime Orchestration and Invocation), a new tool that radically simplifies data mashup composition. We have developed an intelligent automatic composition engine in MARIO together with a simple user interface using an intuitive "wishful search" abstraction. It thus allows users to explore the space of potentially composable data mashups and preview composition results as they iteratively refine their "wishes", i.e. mashup composition goals. It also lets users discover and make use of system capabilities without having to understand the capabilities of individual components, and instantly reflects changes made to the components by presenting an aggregate view of changed capabilities of the entire system. We describe our experience with using MARIO to compose flows of Yahoo Pipes components.

We present a failure recovery framework for System S, a large-scale stream data analysis environment. It is intended to support multiple sites, which have their own local administration and goals. However, it is beneficial for these sites to cooperate with each other, especially in the presence of various failures. Our ultimate goal is to support automatic, timely failure recovery through cooperation among sites. We identify the unique challenges in the context of System S and present our initial design work. In particular, we consider a backup selection problem, specifying where to recover failed jobs, which we formulate as an optimization problem. We present an approximation algorithm together with empirical results obtained through simulations. Our numerical evaluations show that the proposed approximation algorithm is very efficient and effective compared to the optimal solutions. It exhibits a promising empirical performance ratio that is close to the theoretical limit of polynomial approximations of such a problem

Disclosing any information contained within an information system that stores personal data can be associated with risk. Nevertheless, the risk of privacy violation is often considered acceptable, since otherwise the most routine business operations can become impossible. Traditional privacy protection methods limit this risk indirectly by using access control policies for the protection of private information, authorizing the release of information only when the purpose of access justifies doing so. While simple and robust, these policies are binary, and therefore they can be too rigid in practice. A data access operation that is only slightly more risky than usual will be denied, and treated no differently than disclosing all possible data contained in the system. If the risk was justified, the access control policy will be modified later to allow it, but the original declined operation will not be performed in time. In this paper we build upon existing research in disclosure risk assessment, and propose a new flexible privacy protection approach based on soft constraints, as opposed to the hard constraints of traditional systems. The proposed model uses identifiability risk computation to estimate the risk of data access, and allows those requesting data access to decide whether the risk is justified. To prevent abuse of the system, each granted access will be recorded, and those taking high risks will need to justify their decisions later. However, the system will not decline access at the time when the request is made, unless, of course, the risk is unjustifiably high. We believe that this novel approach will help achieve the perfect balance between privacy protection and business efficiency. We illustrate our approach using data published by the U. S. Census Bureau.

False data injection is a severe attack that compromised sensor nodes ("moles"1) can launch. These moles inject large amount of bogus traffic that can lead to application failures and exhausted network resources. Existing sensor network security proposals only passively mitigate the damage by filtering injected packets; they do not provide active means for fight back. This paper studies how to locate such moles within the framework of packet marking, when forwarding moles collude with source moles to manipulate the marks. Existing Internet traceback mechanisms do not assume compromised forwarding nodes and are easily defeated by manipulated marks. We propose a probabilistic nested marking (PNM) scheme that is secure against such colluding attacks. No matter how colluding moles manipulate the marks, PNM can always locate them one by one. We prove that nested marking is both sufficient and necessary to resist colluding attacks. PNM also has fast-traceback: within about 50 packets, it can track down a mole up to 20 hops away from the sink. This virtually prevents any effective data injection attack: moles will be caught before they have injected any meaningful amount of bogus traffic.

In this paper, we propose a novel way of modeling Web services using semantic graph transformations. Each operation supported by a Web service is associated with a semantic annotation that describes the input and output messages using RDF graph patterns. The terms used in these patterns are defined in OWL ontologies that describe the application domain. A key difference between our model and existing semantic Web service models like OWLS is that it describes the inputs and outputs in terms of instance-based graph patterns, rather than in terms of concepts. This allows associating a rich set of constraints on the input and output data in terms of relations between instances. We also propose a composition model for Web service operations, that describes the conditions for composing services into workflows. The composition model includes the notion of semantic propagation, i.e. the semantic description of the output message of an operation depends on the semantics of the input message. We have developed a planner that uses this model to compose services, automatically. The planner uses DLP reasoning to aid plan search. We present performance results for the planner.

A large number of potential applications of sensor and actuator networks (SANETs) have emerged recently, for example in the areas of energy production and distribution and health care and telemedicine. SANETs integrate the tasks of sensing and actuation, the process of controlling the operation of a physical system by setting values for parameters of interest. Of particular importance in SANETs is the ability to set actuator parameters, typically depending on values observed by the sensors, so as to achieve a system-wide objective. However, SANETs with large number of nodes or covering wide geographical areas present scalability challenges that necessitate the use of summarization techniques resulting in sub-optimal actuation values. There is therefore a clear trade-off between the level of summarization and the quality of the computed actuation parameters. This paper focuses on two interdependent problems. The first is the issue of efficient aggregation and summarization of the measurements. The second is the distributed computation of optimal actuation parameters to achieve a system-wide objective. We first consider the problem under the assumption of semi-static sensed values and then extend our model to cover the general case where sensor state changes, triggering update events. We develop algorithms for efficient summarization of these events and demonstrate that they minimally impact optimal actuation. Our work is motivated by the domain of energy distribution networks and, in particular, intelligent electrical grids.

In this paper, an almost peer-to-peer (AP2P) clock synchronization protocol is proposed. AP2P is almost peer-to-peer in the sense that it provides the desirable features of a purely hierarchical (client/server) clock synchronization protocol while avoiding the undesirable consequences of a purely peer-to-peer one. In AP2P, a unique node is elected as a leader in a distributed manner. Each non-leader node adjusts its clock rate based on message exchanges with its neighbors, taking into consideration that neighbors that are closer to the leader have more effect on the adjustment than the neighbors that are further away from the leader. We compare the performance of AP2P with that of the server time protocol (STP), which is a purely hierarchical clock synchronization protocol. Simulation results, which have been conducted on several network topologies, have shown that AP2P can provide a clock synchronization accuracy that is indistinguishable from that of STP. Furthermore, AP2P is more fault-tolerant because it can recover from certain types of failures that STP cannot recover from.

We study a joint scheduling and coding problem for collecting multi-snapshots spatial data in a resource constrained sensor network. Motivated by a distributed coding scheme for single snapshot data collection [7], we generalize the scenario to include multi-snapshots and general coding schemes. Associating a utility function with the recovered data, we aim to maximize the expected utility gain through joint coding and scheduling.

This paper investigates how the through put of a general fork-join queueing network with blocking behaves as the number of nodes increases to infinity while the processing speed and buffer space of each node stay unchanged. The problem is motivated by applications arising from distributed systems and computer networks. One example is large-scale distributed stream processing systems where TCP is used as the transport protocol for data transfer in between processing components. Other examples include reliable multicast in overlay networks, and reliable data transfer in ad hoc networks. Using an analytical approach, the paper establishes bounds on the asymptotic throughput of such a network. For a subclass of networks which are balanced, we obtain sufficient conditions under which the network stays scalable in the sense that the throughput is lower bounded by a positive constant as the network size increases. Necessary conditions of throughput scalability are derived for general networks. The special class of series-parallel networks is then studied in greater detail, where the asymptotic behavior of the throughput is characterized.

Intelligence Transportation Systems are critical to improve the efficiency of modern transportation. A system that is flexible and powerful enough to handle diverse demands from a large user base, is still elusive. Studies have shown that developing and integrating the various components constitute a significant portion of the capital cost and complexity of such systems. In this paper, we present a stream processing infrastructure we call System S. System S enables the deployment of large scale applications. It supports a mechanism for sharing data sources, software components, and even intermediate results allowing a reduction in the cost of software integration, and ownership. We experiment the stream processing infrastructure with a Fleet Management Center, and demonstrate how the infrastructure can be used to address unique issues in traffic management.

Relational databases are widely used today as a mechanism for providing access to structured data. They, however, are not suitable for typical information finding tasks of end users. There is often a semantic gap between the queries users want to express and the queries that can be answered by the database. In this paper, we propose a system that bridges this semantic gap using domain knowledge contained in ontologies. Our system extends relational databases with the ability to answer semantic queries that are represented in SPARQL, an emerging Semantic Web query language. Users express their queries in SPARQL, based on a semantic model of the data, and they get back semantically relevant results. We define different categories of results that are semantically relevant to the users' query and show how our system retrieves these results. We evaluate the performance of our system on sample relational databases, using a combination of standard and custom ontologies.

Value-added content resiliency services help to migrate the burden of resiliency provisioning and maintenance from service users, especially home users and small/medium organizations, who have difficulty in handling correlated failures that impact large areas. For service providers to achieve business success, however, the cost-effectiveness of their resiliency strategies is critical: while the content resiliency requirements specified by the end users have to be satisfied, excessive preventive operation costs caused by the over-reaction to potential risks should be avoided. In this paper, we study the problem of cost-effective configuration in content resiliency service networks under both independent and geographically correlated failures. We propose a new approach to modeling correlated failures in a representable, quantifiable and consistent way, which allows for both quantified availability guarantees and aggressive prevention cost optimization. We then formulate the costeffective configuration problem in content resiliency services and develop both real optimal and heuristic-based algorithms for solving the problem. Our experiments show that with the help of good models for correlated failures, the operation cost of the services can be significantly reduced without impairing the user-specified content resiliency.

We study the problem of the reconstruction of a Gaussian field defined in [0,1] using N sensors deployed at regular intervals. The goal is to quantify the total data rate required for the reconstruction of the field with a given mean square distortion. We consider a class of two-stage mechanisms which (a) send information to allow the reconstruction of the sensor's samples within sufficient accuracy, and then (b) use these reconstructions to estimate the entire field. To implement the first stage, the heavy correlation between the sensor samples suggests the use of distributed coding schemes to reduce the total rate. Our main contribution is to demonstrate the existence of a distributed block coding scheme that achieves, for a given fidelity criterion for the sensor's measurements, a total information rate that is within a constant, independent of N, of the minimum information rate required by an encoder that has access to all the sensor measurements simultaneously. The constant in general depends on the autocorrelation function of the field and the desired distortion criterion for the sensor samples.

Performance of overlay networks is dependent on last-mile connections, since they require that data traverse these last-mile bottlenecks at each forwarding step. This requires several times more upstream bandwidth than downstream, further exaggerating the asymmetry between down-stream and upstream bandwidth in last-mile technologies. This imbalance can cause packet queuing at the outgoing network interface of forwarding nodes, increasing latency and causing packet losses. We describe a model of a last-mile constrained overlay network and formulate and use it to solve a simplified latency- and bandwidth-bounded overlay construction problem. We observe that queueing delay may be a significant component of the end-to-end delay and approaches ignoring this may potentially result in an overlay network violating the delay and/or loss bounds. We observe that allowing a small amount of loss, it is possible to support a significantly large number of nodes. For a given end to end delay and loss bound we identify feasible degree (fan out) of each nodes. Our study sheds insights which provide engineering guidelines for designing overlays accounting for last mile problem in the Internet.

We consider reliable multicast in overlay networks where nodes have finite-size buffers and are subject to failures. We address issues of end-to-end reliability and throughput scalability in this framework. We propose a simple architecture which consists of using distinct point-to-point TCP connections between adjacent pairs of end-systems, together with a back-pressure control mechanism regulating the transfers of adjacent TCP connections, as well as a back-up buffering system handling node failures. This architecture, that we call the one-to-many TCP overlay, is a natural extension of TCP to the one-to-many case, in that it adapts the rate of the group communication to local congestion in a decentralized way via the window back-pressure mechanism. Using theoretical investigations, experimentations in the Internet, and large network simulations, we show that this architecture provides end-to-end reliability and can tolerate multiple simultaneous node failures, provided the backup buffers are sized appropriately. We also show that under random perturbations caused by cross traffic described in the paper, the throughput of this reliable group communication is always larger than a positive constant, that does not depend on the group size. This scalability result contrasts with known results about the non-scalability of IP-supported multicast for reliable group communication.

A number of mobility models have been proposed for the purpose of either analyzing or simulating the movement of users in a mobile wireless network. Two of the more popular are the random waypoint and the random direction models. The random waypoint model is physically appealing but difficult to understand. Although the random direction model is less appealing physically, it is much easier to understand. User speeds are easily calculated, unlike for the waypoint model, and, as we observe, user positions and directions are uniformly distributed. The contribution of this paper is to establish this last property for a rich class of random direction models that allow future movements to depend on past movements. To this end, we consider finite oneand two-dimensional spaces. We consider two variations, the random direction model with wrap around and with reflection. We establish a simple relationship between these two models and, for both, show that positions and directions are uniformly distributed for a class of Markov movement models regardless of initial position. In addition, we establish a sample path property for both models, namely that any piecewise linear movement applied to a user preserves the uniform distribution of position and direction provided that users were initially uniformly throughout the space with equal likelihood of being pointed in any direction.

We pose the question of how to encourage the resource sharing in a distributed, multi-provider environment, where each node, or provider, has local work but is able to accept additional work from other nodes/providers if there is available capacity. An instance of such an environment is found in content delivery, where. numerous, competing providers can work together if enough benefit is to be gained from doing so. We model individual provider behavior as essentially selfish, and then propose pricing schemes to exploit the selfishness to achieve system wide performance gains. We employ a game theoretic framework to analyze the problem, and come up with a time-dependent, noncooperative network equilibrium model. To influence the system towards the positive end of resource sharing, we suggest the creation of a monetary unit, tokens, whose exchange encourages a more efficient use of system-wide capacity, and whose effect is regulated by the pricing scheme in place. The impact of the different node behavior, model parameters, and pricing schemes in influencing the system performance is investigated through simulation. This framework can be combined with distance and round trip time to calibrate redirection behavior of distributed server environments.

Overlay trees typically use directed trees as efficient structures for disseminating information, but their single-path structure means that just one node failure results in the disconnection of all descendants, possibly a significant portion of the graph. The addition of extra "backup" links to a directed tree can provide alternate data paths that significantly reduce the number of nodes disconnected when some set of nodes are removed from the graph. We investigate several deterministic and randomized algorithms for adding such backup links to a directed tree and analyze the connectedness of the resulting graphs when nodes in the network fail with some random probability. We present closed-form approximations and simulation measurements for the connectivity of these augmented trees in networks ranging from hundreds to hundreds of thousands of nodes. We also identify and measure the costs of adding backup links, using simulations and real-world measurements from overlays constructed using PlanetLab latency data. We find that, with node failure rates up to 10%, deterministic backup link selection policies offer comparable resiliency to random backup links with significantly lower overhead and resource usage.

Overlay multicast (or application-level multicast) has become an increasingly popular alternative to IP-supported multicast. End nodes participating in overlay multicast can form a directed tree rooted at the source using existing unicast links. For each receiving node there is always only one incoming link. Very often, nodes can support no more than a fixed number of outgoing links due to bandwidth constraints. Here, we describe an algorithm for constructing a multicast tree with the objective of minimizing the maximum communication delay (i.e. the longest path in the tree), while satisfying degree constraints at nodes. We show that the algorithm is a constant-factor approximation algorithm. We further prove that the algorithm is asymptotically optimal if the communicating nodes can be mapped into Euclidean space such that the nodes are uniformly distributed in a convex region. We evaluate the performance of the algorithm using randomly generated configurations of up to 5,000,000 nodes.

This study provides some new insights into the scalability of reliable group communication mechanisms using overlays. These mechanisms use individual TCP connections for packet transfers between end-systems. End-systems store incoming packets and forward them to downstream nodes using different unicast TCP connections. In this paper we assume that buffers in end-systems are large enough for the transfers. It is shown that the throughput of the reliable overlay group communication scales in the sense that for all multicast tree sizes and topologies, the group throughput is strictly positive under natural conditions. This is in contrast with the IP supported multicast paradigm where reliable protocols have vanishing throughput when the group size tends to infinity. The scalability of packet delay and buffer occupancy is then investigated. In the absence of additional control, the occupancy of the buffer and the latency in the end-systems explodes with time. It is then shown that proactive rate throttle mechanism implemented at the source leads to finite packet latency and buffer occupancy in any end-system of the network provided certain moment conditions are satisfied by cross traffic in the routers.

We consider the steady state distribution of the end-to-end delay of a tagged flow in queueing networks where the queues have self-similar cross traffic. We assume that such cross traffic at each queue, say queue I, is modeled by fractional Brownian motion (FBM) with Hurst parameter H/sub i/ /spl isin/ (1/2,1), and is independent of other queues. The arrival process of the tagged flow is renewal. Two types of queueing networks are considered. We show that the end-to-end delay of the tagged flow in a tandem queueing network, and more generally in a tree network, is completely dominated by one of the queues. The dominant queue is the one with the maximal Hurst parameter. If several queues have the same maximal Hurst parameter, then we have to compare the ratio (1-/spl rho/)/sup H///spl sigma/ to determine the dominant queue, where /spl rho/ is the load of the queue and /spl sigma/ is the coefficient of variation of the cross traffic at the queue. In the case that the tagged flow is controlled through a window based congestion control mechanism, the end-to-end delay is still asymptotically Weibullian with the same shape parameter. We provide upper and lower bounds on the constant that determines the scale parameter of the corresponding Weibull distribution.

The overwhelming success of the Web as a mechanism for facilitating information retrieval and for conducting business transactions has ledto an increase in the deployment of complex enterprise applications. These applications typically run on Web Application Servers, which assume the burden of managing many tasks, such as concurrency, memory management, database access, etc., required by these applications. The performance of an Application Server depends heavily on appropriate configuration. Configuration is a difficult and error-prone task dueto the large number of configuration parameters and complex interactions between them. We formulate the problem of finding an optimal configuration for a given application as a black-box optimization problem. We propose a smart hill-climbing algorithm using ideas of importance sampling and Latin Hypercube Sampling (LHS). The algorithm is efficient in both searching and random sampling. It consists of estimating a local function, and then, hill-climbing in the steepest descent direction. The algorithm also learns from past searches and restarts in a smart and selective fashion using the idea of importance sampling. We have carried out extensive experiments with an on-line brokerage application running in a WebSphere environment. Empirical results demonstrate that our algorithm is more efficient than and superior to traditional heuristic methods.

This paper introduces new algorithms specifically designed for content-based publication-subscription systems. These algorithms can be used to determine multicast groups with as much commonality as possible, based on the totality of subscribers' interests. The algorithms are based oil concepts borrowed from the literature on spatial databases and clustering. These algorithms perform well in the context of highly heterogeneous subscriptions, and they also scale well. Based on concepts borrowed from the spatial database literature, we develop an algorithm to match publications to subscribers in real-time. We also investigate the benefits of dynamically determining whether to unicast, multicast or broadcast information about the events over the network to the matched subscribers. We call this the distribution method problem. Some of these same concepts can be applied to match publications to subscribers in real-time, and also to determine dynamically whether to unicast, multicast or broadcast information about the events over the network to the matched subscribers. We demonstrate the quality of our algorithms via a number of realistic simulation experiments.

This paper involves the study of the throughput capacity of hybrid wireless networks. A hybrid network is formed by placing a sparse network of base stations in an ad hoc network. These base stations are assumed to be connected by a high-bandwidth wired network and act as relays for wireless nodes. They are not data sources nor data receivers. Hybrid networks present a tradeoff between traditional cellular networks and pure ad hoc networks in that data may be forwarded in a multihop fashion or through the infrastructure. It has been shown that the capacity of a random ad hoc network does not scale well with the number of nodes in the system. In this work, we consider two different routing strategies and study the scaling behavior of the throughput capacity of a hybrid network. Analytical expressions of the throughput capacity are obtained. For a hybrid network of n nodes and m base stations, the results show that if m grows asymptotically slower than √n, the benefit of adding base stations on capacity is insignificant. However, if m grows faster than √n, the throughput capacity increases linearly with the number of base stations, providing an effective improvement over a pure ad hoc network. Therefore, in order to achieve nonnegligible capacity gain, the investment in the wired infrastructure should be high enough.

Design of e-commerce services that are competitive in a quickly responding market requires the analyses of prices and price structures. We develop a general model of an e-commerce market that allows us to analyze optimal price structures, both flat and usage-based. Based on the price structure of a major web hosting provider, we consider single-tier and two-tier (burst-rate) pricing, and our result suggests that the more complex two-tier structure may not be worth the marketing effort, as the firm's equilibrium profits will not increase through the use of this structure. An essential feature of our approach is that we model explicitly the spread of price-QoS tradeoffs across the end-user population.

We analyze the asymptotic tail distribution of stationary waiting times and stationary virtual waiting times in a single-server queue with long-range dependent arrival process and subexponential service times. We investigate the joint impact of the long range dependency of the arrival process and of the tail distribution of the service times. We consider two traffic models that have been widely used to characterize the long-range dependence structure, namely, the M/G/8 input model and the Fractional Gaussian Noise (FGN) model. We focus on the response times of the customers in a First-Come First-Serve (FCFS) queueing system, although the results carry through to the backlog distribution of the system with any arbitrary queueing discipline. When the arrival process is driven by an M/G/8 input model we show that if the residual service time tail distribution Fe is lighter than the residual session duration Ge, then the stationary waiting time is dominated by the long-range dependence structure, which is determined by the residual session duration Ge. If the residual service time distribution Fe is heavier than the residual session duration Ge, then the tail distribution of the stationary waiting time is dominated by that of the residual service time. When the arrival process is modeled by an FGN, we show that the waiting time tail distribution is asymptotically equal to the tail distribution of the residual service time if the latter is asymptotically heavier than Weibull distribution with shape parameter 2-2H, where H is the Hurst parameter of the FGN. If, however, this residual service time is asymptotically lighter than Weibull distribution with shape parameter 2-2H, then the waiting time tail distribution is dominated by the dependence structure of the arrival process so that it is asymptotically equal to Weibull distribution with shape parameter 2-2H.

With the growing popularity of Web applications, there is a considerable increase in the importance of managing Web sites to deliver high levels of performance and scalability to accommodate future growth and evolution. One of the key issues in this regard concerns a better understanding of the traffic patterns at multiple levels, such as the levels of requests, pages and sessions. This paper presents a detailed analysis of measurement data from various sources pertaining to a specific multi-tiered, geographically distributed architecture that has been used to host the Web sites for a number of recent, popular sporting events. Our analysis of the request-level and page-level patterns demonstrate differences among the Web sites depending upon the type of event and the breadth of interests of the user community. Some of these patterns are consistent with commercial Web sites, while others are significantly different These results further illustrate geographical differences in the request-level and page-level patterns. Our analysis also investigates in detail session-level characteristics. This includes an analysis of the session durations, the think time distributions, the dependence structure of the session arrival process, and the page views comprising each session.

We present an approach to analyzing the performance characteristics of TCP sessions in the presence of network routers which deploy the random early detection (RED) mechanism with two in-and-out drop probability functions (RIO). We consider the case with a large number of TCP sessions which use token buckets for marking in and out packets at the entrance of the network. Under some simplifying assumptions, we derive a set of equations that govern the evolution of these TCP sessions and the routers under consideration. The equations are solved numerically using a fixed point method. Our analysis can capture characteristics of both RED and tail drop (TD) mechanisms in the RIO router. Our model is validated through simulations which show that less than 5% error is achieved in most cases. Various performance analyses are carried out using this approach to study the impact of the RIO parameters on the performance characteristics of TCP sessions. The results show that the loss probability threshold of out packets has a significant effect on the TCP throughput and on the average queue length. Setting this parameter consists of trading off between network utilization and fairness among TCP connections. The results also show that the tail drop mechanism is particularly suitable for use in packets to satisfy various QoS constraints.

We consider efficient communication schemes based on both network-supported and application-level multicast techniques for content-based publication-subscription systems. We show that the communication costs depend heavily on the network configurations, distribution of publications and subscriptions. We devise new algorithms and adapt existing partitional data clustering algorithms. These algorithms can be used to determine multicast groups with as much commonality as possible, based on the totality of subscribers' interests. They perform well in the context of highly heterogeneous subscriptions, and they also scale well. An efficiency of 60% to 80% with respect to the ideal solution can be achieved with a small number of multicast groups (less than 100 in our experiments). Some of these same concepts can be applied to match publications to subscribers in real-time, and also to determine dynamically whether to unicast, multicast or broadcast information about the events over the network to the matched subscribers. We demonstrate the quality of our algorithms via simulation experiments.

Packet delay traces are important measurements for analyzing end-to-end performance and for designing traffic control algorithms in computer networks. Due to the fact that the clocks at the end systems are usually not synchronized and running at different speeds, these measurements can be quite inaccurate. We propose several algorithms to estimate and remove the relative clock skews from delay measurements based on the computation of convex hulls. Compared with existing techniques, such as linear regression and linear programming, the convex-hull approach provides better insight and allows us to handle more error metrics. We obtain algorithms which are linear in the number of measurement points for the case with no clock resets. For the more challenging case with clock resets, i.e., the clocks are reset to some reference times during the measurement period, we develop linear algorithms to identity the clock resets, and derive the best clock skew lines. We extend this analysis to environments in which at least one of the clocks is controlled by NTP (network time protocol). These algorithms can greatly improve the accuracy of the measurements, and can be used both online and offline. They can also be extended for active clock synchronization, to replace or further improve NTP. Numerical experiments are presented to demonstrate the robustness of the algorithms.

We present a methodology for maximizing profits in a general class of e-commerce environments. The cost model is based on revenues that are generated when Quality-of-Service (QoS) guarantees are satisfied and on penalties that are incurred otherwise. The corresponding QoS criteria are derived from multiclass Service-Level-Agreements (SLAs) between service providers and their clients, which include the tail distributions of the per-class delays in addition to more standard QoS metrics such as throughput and mean delays. Our approach consists of formulating the optimization problem as a network flow model with a separable set of concave objective functions based on queueing-theoretic formulas, where the SLA classes are taken into account in both the constraints and the objective function. This problem is then solved via a fixed-point iteration. Numerous experiments illustrate the benefits of our approach.

We show how the analysis of Markov modulated rate processes can be used to address the problem of computing the distribution of W, the stationary workload in the MMPP/GI/1 queue. Using the results of papers by Anick et al. (1982); Mitra (1988); and Elwalid et al. (1991), we present the decomposition properties of the Laplace transform of W and efficient computational algorithms for computing its distribution. The techniques are also applied to compute the bounds on the distribution of W developed by Liu et al. (see JACM, vol.44, no.2, p.366-94, 1997). Numerical results illustrating the usefulness of the methods are given for the case of the superposition of independent, nonidentical sources.

Stochastic timed Petri nets are a useful tool in the performance analysis of concurrent systems such as parallel computers, communication networks and flexible manufacturing systems. In general, performance measures of stochastic timed Petri nets are difficult to obtain for practical problems due to their sizes. In this paper, we provide a method to efficiently compute upper and lower bounds for the throughputs and mean token numbers for a large class of stochastic timed Petri nets. Our approach is based on uniformization technique and linear programming.

In this paper, we develop a framework for computing upper and lower bounds of an exponential form for a large class of single resource systems with Markov additive inputs. Specifically, the bounds are on quantities such as backlog, queue length, and response time. Explicit or computable expressions for our bounds are given in the context of queuing theory and numerical comparisons with other bounds and exact results are presented. The paper concludes with two applications to admission control in multimedia systems.

In this paper, we consider the stochastic profile scheduling problem of a partially ordered set of tasks on uniform processors. The set of available processors varies in time. The running times of the tasks are independent random variables with exponential distributions. We obtain a sufficient condition under which a list policy stochastically minimizes the makespan within the class of preemptive policies. This result allows us to obtain a simple optimal policy when the partial order is an interval order, an in-forest, or an out-forest.

International audience

There exists a substantial body of work on the problem of providing guaranteed quality of service (QoS) to different service classes in B-ISDNs. We consider a discrete time, single server system in which packets arrive from a finite population of sources. Under the assumption that arrivals from each source are modulated by a Markov process, we examine the following metrics (i) the fraction of an interval during which the queue length exceeds a certain value, and (ii) the fraction of a group of packets from a single source that arrive to find the queue length above a certain value. For both metrics we derive upper and lower bounds on the probabilities that they exceed a threshold. These are important measures because they reflect more accurately the behavior perceived by applications such as networked audio and video. An application of these results to call admission is also given.

Considers rate-based flow control throttles feeding a sequence of single server infinite capacity queues. Specifically, the authors consider two types of throttles, the token bank and the leaky bucket. They show that the cell waiting times at the downstream queues are increasing functions of the token buffer capacity. These results are established when the rate-based throttles have finite capacity data buffers as well as infinite capacity buffers. In the case that the data buffer has finite capacity, they require that the sum of the capacities of the data buffer and token buffer be a constant. Last, they establish similar results for the process of number of losses at the last downstream queue in the case that the waiting buffer has finite capacity.>

In this paper, we study quantitative as well as qualitative properties of Fork-Join Queuing Networks with Blocking (FJQN/Bs). Specifically, we prove results regarding the equivalence of the behavior of a FJQN/B and that of its duals and a strongly connected marked graph. In addition, we obtain general conditions that must be satisfied by the service times to guarantee the existence of a long-term throughput and its independence on the initial configuration. We also establish conditions under which the reverse of a FJQN/B has the same throughput as the original network. By combining the equivalence result for duals and the reversibility result, we establish a symmetry property for the throughput of a FJQN/B. Last, we establish that the throughput is a concave function of the buffer sizes and the initial marking, provided that the service times are mutually independent random variables belonging to the class of PERT distributions that includes the Erlang distributions. This last result coupled with the symmetry property can be used to identify the initial configuration that maximizes the long-term throughput in closed series-parallel networks.

Parallel execution of an arrival stream of jobs with and without real-time constraints on a (possibly heterogeneous) multiprocessor system IS considered.A job consists of a set of tasks and a partial order specifying the precedence constraints between the tasks.The real-time constraints are specified by due times, also called so~t real time deadlines.It is assumed that there is a predefine mapping from the set of tasks onto the set of machines that is identical for all jobs.Associated with each task is a service time that may depend on the machine that it is allocated to.The problem of scheduling tasks into execution at each machine is the subject of this paper.Dynamic nonpreemptive scheduling policies that do not use service-time information is examined and a class of Local Order Preserving (LOP) policies that contains the class of nonidling First Come Fust Serve (FCFS) policies is defined.It is shown that policies from this last class, along with the classes of LOP Shortest Due Time First (S DTF), LOP Largest Due Time First (LDTF), and LOP Last Come First Serve (LCFS) policies stochastically minimize the number of jobs in the system and maximize the job throughput.The class of FCFS policies is further shown to minimize the vector of transient response times in the increasing Schur convex sense.Last, we consider the job lateness, the difference between the due time and the completion time of the job, and prove that within the class of LOP policies, the SDTF and LDTF policies bound, respectively, from below and from above the transient vector of the job latenesses, in the Schur convex sense.The paper concludes with extensions to the steady state performance metrics, to the class of preemptive-resume policies, and to jobs having random task graphs.All of the results, except those concerned with preemptive policies, assume that task service times form mutually independent sequences of independent and identically distributed random variables.In the latter case, service times are further assumed to be exponential random variables.

The problem of optimal routing in an interconnection network, called the de Bruijn network, where the sites are linked in the form of a de Bruijn graph, is considered. The distance functions for both the undirected and directed de Bruijn graphs are provided. The optimal routing problem is then reduced to that of pattern matching. Morris and Pratt's (1970) failure function and Weiner's (1973) prefix tree are used to develop algorithms that find the shortest paths in the unidirectional and bidirectional de Bruijn networks, respectively. These algorithms are linear in time and space (in the diameter of the graph). When approximately implemented, these linear algorithms have constant factors low enough to make them of practical use.>

The server visits N queues in an arbitrary manner. Each queue is visited for a random period of time whose duration is sampled in advance. At the end of a visit period, either all customers of the attended queue leave the system (variant I) or only customers that were present in the queue upon the arrival of the server leave the system (variant II). A scheduling policy is a rule that selects the next queue to be visited by the server. When the controller has no information on the state of the system, it is shown, under homogeneous arrival assumptions, that a cyclic policy minimizes the expected number of customers in the system. When the controller knows the number of customers in each queue, it is shown that the so-called most-customers-first (MCF) policy minimizes, in the sense of strong stochastic ordering, the vector of the number of customers in each queue whose components are arranged in decreasing order. These results hold for variants I and II and are obtained under fairly weak statistical assumptions. This model has potential applications in videotex and time-division multiple-access systems.>

The new class of queuing models, calledSynchronized Queuing Networks, is proposed for evaluating the performance of multiprogrammed and multitasked multiprocessor systems, where workloads consists of parallel programs of similar structure and where the scheduling discipline is first-come-first-serve. Pathwise evolution equations are established for these networks that capture the effects of competition for processors and the precedence constraints governing tasks executions. A general expression is deduced for the stability condition of such queuing networks under general statistical assumptions (basically the stationarity and the ergodicity of input sequences), which yields the maximum program throughput of the multiprocessor system, or equivalently, the maximum rate at which programs can be executed or submitted. The proof is based on the ergodic theory of queues. Basic integral equations are also derived for the stationary distribution of important performance criteria such as the workload of the queues and program response times. An iterative numerical schema that converges to this solution is proposed and various upper and lower bounds on moments are derived using stochastic ordering techniques.