It is estimated that over 8 million cell phones are lost or stolen each year [7]; often the loss of a cell phone means the loss of personal data, time and enormous aggravation. In this paper we present machine-learning based algorithms by which a cell phone can discern that it may be lost, and take steps to enhance its chances of being successfully recovered. We use data collected from the Reality Mining project [10] to create a suite of realistic test cases that model lost cell phone behavior. On these data sets our best algorithms can identify cases of a lost mobile device, based on its behavior over the previous 3 hours, with close to 100% accuracy. In addition, the algorithm generates false positive identifications with probability less than 3%; for individuals with relatively predictable lifestyles the False Positive Rate is substantially less. We also use the Reality Mining data to construct a set of test cases that model the behavior of a stolen phone, and show that similar algorithmic techniques give reasonable results in this setting as well.

Payload attribution can be an important element in network forensics. Given a history of packet transmissions and an excerpt of a possible packet payload, a payload attribution system (PAS) makes it feasible to identify the sources, destinations, and the times of appearance on a network of all the packets that contained the specified payload excerpt. A PAS, as one of the core components in a network forensics system, enables investigating cybercrimes on the Internet by, for example, tracing the spread of worms and viruses, identifying who has received a phishing e-mail in an enterprise, or discovering which insider allowed an unauthorized disclosure of sensitive information. Due to the increasing volume of network traffic in today's networks, it is infeasible to effectively store and query all the actual packets for extended periods of time in order to allow analysis of network events for investigative purposes; therefore, we focus on extremely compressed digests of the packet activity. We propose several new methods for payload attribution, which utilize Rabin fingerprinting, shingling, and winnowing. Our best methods allow building practical payload attribution systems, which provide data reduction ratios greater than 100:1 while supporting efficient queries with very low false positive rates. We demonstrate the properties of the proposed methods and specifically analyze their performance and practicality when used as modules of a network forensics system ForNet. Our experimental results outperform current state-of-the-art methods both in terms of false positives and data reduction ratio. Finally, these approaches directly allow the collected data to be stored and queried by an untrusted party without disclosing any payload information nor the contents of queries.

Complex distributed systems are increasingly important in modern computer science, yet many undergraduate curricula do not give students the opportunity to develop the skill sets necessary to grapple with the complexity of such systems. We have developed and integrated into an undergraduate elective course on parallel and distributed computing a teaching tool that may help students develop these skill sets. The tool uses virtualization to ease the burden of resourcing and configuring complex systems for student study, and creates varied “firefighting ” gaming scenarios in which students compete to keep the system up and running in the presence of multiple issues. Preliminary experience indicates that (1) students find the tool engaging and (2) it is a manageable way in which to give students a novel perspective on interaction with complex distributed systems.

Given a history of packet transmissions and an excerpt of a possible packet payload, the payload attribution problem requires the identification of sources, destinations and the times of appearance on a network of all the packets that contained such payload. A module to solve this problem has recently been proposed as the core component in a network forensics system. Network forensics provides useful tools for investigating cybercrimes on the Internet, by, for example, tracing the spread of worms and viruses, identifying who has received a phishing email in an enterprise, or discovering which insider allowed an unauthorized disclosure of sensitive information.

Recently there has been much progress on the design of approximation algorithms for a variety of scheduling problems in which the goal is to minimize the average weighted completion time of the jobs scheduled. Many of these approximation algorithms have been inspired by polyhedral formulations of the scheduling problems and their use in computing optimal solutions to small instances. In this paper we demonstrate that the progress in the design and analysis of approximation algorithms for these problems also yields techniques with improved computational efficacy. Specifically, we give a comprehensive experimental study of a number of these approximation algorithms for 1|rj∑wjCj, the problem of scheduling jobs with release dates on one machine so as to minimize the average weighted completion time of the jobs scheduled. We study both the quality of lower bounds given for this problem by different linear-programming relaxations and combinatorial relaxations, and the quality of upper bounds delivered by a number of approximation algorithms based on them. The best algorithms, on almost all instances, come within a few percent of the optimal average weighted completion time. Furthermore, we show that this can usually be achieved with O(n log n) computation. In addition we observe that on most kinds of synthetic data used in experimental studies a simple greedy heuristic, used in successful combinatorial branch-and-bound algorithms for the problem, outperforms (on average) all of the LP-based heuristics. We identify, however, other classes of problems on which the LP-based heuristics are superior and report on experiments that give a qualitative sense of the range of dominance of each. We consider the impact of local improvement on the solutions as well. We also consider the performance of the algorithms for the average weighted flow-time criterion, which, although equivalent to average weighted completion time at optimality, is provably much harder to approximate. Nonetheless, we demonstrate that for most instances we consider that the algorithms give very good results for this criterion as well. Finally, we extend the techniques to a rather different and more complex problem that arises from an actual manufacturing application: resource-constrained project scheduling. In this setting as well, the techniques yield algorithms with improved performance; we give the best-known solutions for a set of instances provided by BASF AG, Germany.

Streaming media on the Internet has experienced rapid growth over the last few years and will continue to increase in importance as broadband technologies and authoring tools continue to improve. As the Internet becomes an increasingly popular alternative to traditional communications media, Internet streaming will become a significant component of many content providers' communications strategies. Internet streaming, however, poses significant challenges for content providers, since it has significant distribution problems. Scalability, quality, reliability, and cost are all issues that have to be addressed in a successful streaming media offering. Streaming content delivery networks (streaming CDNs) attempt to provide solutions to the bottlenecks encountered by streaming applications on the Internet. However, only a small number of them has been deployed, and little is known about the internal organization of these systems. In this paper, we discuss the design choices made during the evolution of Akamai's CDN for streaming media. In particular, we look at the design choices made to ensure the network's scalability, quality of delivered content, and reliability while keeping costs low. Performance studies conducted on the evolving system indicate that our design scores highly on all of the above categories.

) Cynthia A. Phillips Cliff Stein y Eric Torng z Joel Wein x Abstract We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting, and scheduling to provide good response time in a number of scheduling environments. When viewed from the perspective of traditional worst-case analysis, no good on-line algorithms exist for these problems, and for some variants no good off-line algorithms exist unless P = NP. We study these problems using a relaxed notion of competitive analysis, introduced by Kalyanasundaram and Pruhs, in which the on-line algorithm is allowed more resources than the optimal off-line algorithm to which it is compared. Using this approach, we establish that several well-known on-line algorithms, that have poor performance from an absolute worst-case perspective, are optimal for the problems in question when allowed moderately more resources. For the optimization of average flow time, these are th...

We give a distributed approximation algorithm for job scheduling in a ring architecture. In contrast to many other parallel scheduling models, the model we consider captures the influence of the underlying communications network by specifying that task migration from one processor to another takes time proportional to the distance between those two processors in the network. As a result, our algorithm must balance computational load and communication time. The algorithm is simple, requires no global control, and yields schedules of length at most 4.22 times optimal. We also give a lower bound on the performance of any distributed algorithm and the results of simulation experiments which suggest better performance than does our worst-case analysis.

Scheduling a set of tasks on a set of machines so as to yield an efficient schedule is a basic problem in computer science and operations research. Most of the research on this problem incorporates the potentially unrealistic assumption that communication between the different machines is instantaneous. In this paper we remove this assumption and study the problem of network scheduling, where each job originates at some node of a network, and in order to be processed at another node must take the time to travel through the network to that node. Our main contribution is to give approximation algorithms and hardness proofs for fully general forms of the fundamental problems in network scheduling. We consider two basic scheduling objectives: minimizing the makespan and minimizing the average completion time. For the makespan, we prove small constant factor hardness-to-approximate and approximation results. For the average completion time, we give a log-squared approximation algorithm for the most general form of the problem. The techniques used in this approximation are fairly general and have several other applications. For example, we give the first nontrivial approximation algorithm to minimize the average weighted completion time of a set of jobs on related or unrelated machines, with or without a network.

We consider the problem of scheduling a parallel loop with independent iterations on a network of heterogeneous workstations, and demonstrate the effectiveness of a variant of factoring, a scheduling policy originating in the context of shared address-space homogeneous multiprocessors. In the new scheme, weighted factoring, processors are dynamically assigned decreasing size chunks of iterations in proportion to their processing speeds. Through experiments on a network of SUN Sparc workstations we show that weighted factoring significantly outperforms variants of a work-stealing load-balancing algorithm and on certain applications dramatically outperforms factoring as well. We then study weighted work assignment analytically, giving upper and lower bounds on its performance under the assumption that the processor iteration execution times can be modeled as weighted random variables. Department of Computer Science, Polytechnic University, Brooklyn, NY, 11201. Research supported by AR...

The problem of scheduling jobs on parallel machines is studied when (1) the existence of a job is not known until its unknown release date and (2) the processing requirement of a job is not known until the job is processed to completion. Two general algorithmic techniques are demonstrated for converting existing polynomial-time algorithms that require complete knowledge about the input data into algorithms that need less advance knowledge. Information-theoretic lower bounds on the length of on-line schedules are proven for several basic parallel machine models, and almost all of our algorithms construct schedules with lengths that either match or come within a constant factor of the lower bound.

We give distributed approximation algorithms for job scheduling in a ring architecture. In contrast to almost all other parallel scheduling models, the model we consider captures the influence of the underlying communications network by specifying that task migration from one processor to another takes time proportional to the distance between those two processors in the network. As a result, our algorithms must balance both computational load and communication time. The algorithms are simple, require no global control, and work in a variety of settings. All come with small constant-factor approximation guarantees; the basic algorithm yields schedules of length at most 4:22 times optimal. We also give a lower bound on the performance of any distributed algorithm and the results of simulation experiments, which give better results than our worst-case analysis. Research partially supported by NSF grant CCR-9308701, a Walter Burke Research Initiation Award and a Dartmouth College Resear...

In the job shop scheduling problem, there are m machines and n jobs. A job consists of a sequence of operations, each of which must be processed on a specified machine, and the aim is to complete all jobs as quickly as possible. This problem is strongly .$\mathcal{NP}$-hard even for very restrictive special cases. The authors give the first randomized and deterministic polynomial-time algorithms that yield polylogarithmic approximations to the optimal length schedule. These algorithms also extend to the more general case where a job is given not by a linear ordering of the machines on which it must be processed but by an arbitrary partial order. Comparable bounds can also be obtained when there are $m'$ types of machines, a specified number of machines of each type, and each operation must be processed on one of the machines of a specified type, as well as for the problem of scheduling unrelated parallel machines subject to chain precedence constraints.

The authors study the problem of scheduling jobs on parallel machines when the existence of a job is not known until an unknown release date and the processing requirement of a job is not known until the job is processed to completion. They demonstrate two general algorithmic techniques for converting existing polynomial-time algorithms that require complete knowledge about the input data into algorithms that need less advance knowledge. They prove information-theoretic lower bounds on the lengths of online schedules for several basic parallel machine models and then show that the algorithms construct schedules with lengths that either match or come within a constant factor of the lower bounds.>