Federated geographically-distributed computing platforms such as PlanetLab [1] and the Grid [2, 3] have recently become popular for evaluating and deploying network services and scientific computations. As the size, reach, and user population of such infrastructures grow, resource discovery and resource selection become increasingly important. Although a number of resource discovery and allocation services have been built, there is little data on the utilization of the distributed computing platforms they target. Yet the design and efficacy of such services depends on the characteristics of the target platform.

We are developing a distributed query processor called PIER, which is designed to run on the scale of the entire Internet. PIER utilizes a Distributed Hash Table (DHT) as its communication substrate in order to achieve scalability, reliability, decentralized control, and load balancing. PIER enhances DHTs with declarative and algebraic query interfaces, and underneath those interfaces implements multihop, in-network versions of joins, aggregation, recursion, and query/result dissemination. PIER is currently being used for diverse applications, including network monitoring, keyword-based filesharing search, and network topology mapping. We will demonstrate PIER's functionality by showing system monitoring queries running on PlanetLab, a testbed of over 300 machines distributed across the globe.

This paper presents Sharp, a framework for secure distributed resource management in an Internet-scale computing infrastructure. The cornerstone of Sharp is a construct to represent cryptographically protected resource claims ---promises or rights to control resources for designated time intervals---together with secure mechanisms to subdivide and delegate claims across a network of resource managers. These mechanisms enable flexible resource peering : sites may trade their resources with peering partners or contribute them to a federation according to local policies. A separation of claims into tickets and leases allows coordinated resource management across the system while preserving site autonomy and local control over resources. Sharp also introduces mechanisms for controlled, accountable oversubscription of resource claims as a fundamental tool for dependable, efficient resource management. We present experimental results from a Sharp prototype for PlanetLab, and illustrate its use with a decentralized barter economy for global PlanetLab resources. The results demonstrate the power and practicality of the architecture, and the effectiveness of oversubscription for protecting resource availability in the presence of failures.

This paper presents a performance analysis of market-based batch schedulers for clusters of workstations. In contrast to previous work, we use user-centric performance metrics as the basis for system evaluation. Each user is modeled as having a utility function for each job which measures value delivered to the user as function of execution time. Summing over all utility functions in the workload, we use aggregate utility as a measure of overall value delivered to users. With aggregate utility as the performance metric, simulations are used to quantify the performance of both market-based and traditional batch scheduling algorithms under a variety of synthetic work-loads. Results show that an auction-based batch scheduling algorithm improves performance by a factor of up to 2-5x for sequential workloads and up to 14x for highly parallel workloads compared to traditional scheduling algorithms.

This paper presents a network mapping algorithm and proves its correctness assuming a traffic-free network.Respecting well-defined parameters, the algorithm produces a graph isomorphic to N -F, where N is the network of switches and hosts and F is the set of switches connected by a switch-bridge to the set of hosts I-I.We show its performance on a Myrinet system-area network with a fat-tree-like topology.It can map 36 nodes, 13 switches and 64 links in 248 ms and 100 nodes, 40 switches, and 193 linksin981 rns.From such maps, the system computes mutually deadlock-free routes and distributes them to all network interfaces.Switched, multi-gigabyte per second, system area networks are the enabling building-blocks for networks of workstations.Because of their core role, these networks should be dynamically recontigurable, automatically adapting to the addition or removal of hosts, switches and links. IntroductionSystem area networks [1] move switched, low-latency, high-speed networks away from the backplanes and cabinets of massively parallel processors into the traditional territory of local area networks.These networks commonly use source-based message routing through anonymous switches.In this regime, their topologies may no longer be the static, well-defined, and well-understood [2] graphs such as hypercubes, meshes.etc., and instead may be arbitrary graphs that change over time.Therefore, systems must periodically discover their topologies rather than assuming one a priori.Lacking an out-of-band mechanism for directly querying switches for their identities, systems must use in-band messaging to disambiguate switch identities when discovering the network topology.From the resulting maps, systems can compute mutually deadlock-free routes without relying upon properties of traditional multicomputer networks, e.g., static topologies, that may now be transient.