In the near future extremely large scale mobile adhoc networks of thousands or tens of thousands of mobile nodes will be physically feasible and desirable for a host of applications. However, routing within these networks is challenging, especially at high data rates and when node movement is highly-dynamic. In this work we present Topology Aware Geographic Routing(TAG), a position-based routing protocol that strategically uses local topology information (when available) to make better local forwarding decisions, decreasing the number of hops required to deliver a packet when compared with other geographic routing protocols. In addition, TAG is able to reliably deliver packets even in topologies that violate the often used but unrealistic unit disk graph and quasi-static assumptions. We present empirical results from a variety of simulations, illustrating how TAG outperforms GOAFR+, GFG, and OLSR in both theoretical environments and in a simulated, real-world, continental-scale airborne network.

We have developed education modules for topics in networking, security, and cloud computing. A networking instructor could use our modules to enhance the teaching of basic concepts by demonstrating these concepts with real experiments on GENI testbeds. Any systems instructor could use our security or cloud computing modules to begin teaching new topics, or enhance existing topics by adding hands-on experiments on GENI and CloudLab testbeds. Our NSF funded projects to develop these curricular modules have been successfully used by several instructors. Attendees at SIGCSE would comprise exactly the kind of audience, from varied institutions and dedicated to enhancing their curriculum, for whom we've built these modules. Our modules are freely available, and we are committed to helping instructors use our modules in their courses. The underlying testbeds, GENI and CloudLab, are also NSF-funded and thus freely available for instructors to use. Attendees will be provided a handout that contains relevant information, including contact for help, as they go back and begin using our education modules in their curriculum.

Civilian Airborne Networks capable of providing network connectivity to users onboard aircraft and users on the ground may soon be viable. We propose a novel airborne network architecture consisting of commercial aircraft and ground station gateways inter-connected with Free-Space Optical Communications (FSOC) links to form a high-bandwidth mesh network. The use of directional FSOC links necessitates explicit topology control, where a protocol must manage which links will point at one another to form connections. The algorithm used by the topology control protocol to form topologies must have low computation time, and must compute topologies that are robust, inclusive, and contain short paths between nodes. We use FAA flight path data for the aircraft en route within the continental United States during a 24-hour period to analyze the properties of airborne mesh networks, and compare candidate topology algorithms. In our simulation an airborne network with ground stations was able to continuously connect over 98% of the air-craft into a mesh network using FSOC links. We propose two new topology algorithms (DCTRT and DCKruskal+Long) which are extensions to existing algorithms. DCKruskal+Long appears to perform best for the metrics measured.

Over the last decade web content has evolved from relatively static pages often delivered by one or two servers, to websites rich with interactive media content served from numerous servers. This content change has affected the associated network traffic. Quantifying and analyzing these changes can lead to updated traffic models and more accurate web traffic simulations for testing new protocols and devices. In this work we analyze the TCP/IP headers in packet traces collected at various times over 13 years on the link that connects the University of North Carolina at Chapel Hill (UNC) to its ISP. We show that while the decade-old methodology for inferring web activity from these packet traces is still viable, it is no longer possible to infer all page boundaries given only the TCP and IP headers. We propose a novel method for segmenting web traffic into Activity Sections, in order to obtain comparable higher level statistics. Using these methods to analyze our data set, we describe trends in the HTTP request and response sizes, and a trend towards longer connection durations. We also show that the number of servers supporting web activity has increased, and present empirical evidence that suggests the number of unused connections has risen, likely due to new speculative TCP preconnect features of popular browsers.

Networking research would be well served by the adoption of a set of traffic benchmarks to model network applications for empirical evaluations; such benchmarks are common in many other areas of computing. While it has long been known that certain aspects of modeling traffic, such as round trip time, can dramatically affect application and network performance, there is still no agreement as to how such components should be controlled within an experiment. In this paper we advance the discussion of standards for empirical networking research by demonstrating how certain components of network traffic, such as the structure of application data exchanges within a TCP connection, can have a larger impact on the results obtained through experimentation than other dimensions of traffic such as round-trip time. Such findings point to the pressing need for traffic benchmarks in networking research. Through testbed experiments performed with synthetically generated network traffic from two very different traffic sources, and using several models of TCP connection structure, we demonstrate the strong effects of connection structure in traffic workload modeling on performance measures such as queue length at routers, number of active connections in the network, user response times, and connection durations.

In this tutorial, we will introduce the SIGMETRICS/Performance community to the vast testbeds, tools and resources openly available through the GENI (Global Environment for Network Innovations) project. We will present details about the distributed computing resources available on GENI for researchers interested in simulation as well as measurement-based performance evaluation experiments. We will demonstrate simple experiments on GENI, and leave them with information on how to run experiments for research and education using GENI resources.

In order to perform valid experiments, traffic generators used in network simulators and testbeds require contemporary models of traffic as it exists on real network links. Ideally one would like a model of the workload created by the full range of applications running on the Internet today. Unfortunately, at best, all that is available to the research community are a small number of models for single applications or application classes such as the web or peer-to-peer. We present a method for creating a model of the full TCP application workload that generates the traffic flowing on a network link. From this model, synthetic workload traffic can be generated in a simulation that is statistically similar to the traffic observed on the real link. The model is generated automatically using only a simple packet-header trace and requires no knowledge of the actual identity or mix of TCP applications on the network. We present the modeling method and a traffic generator that will enable researchers to conduct network experiments with realistic, easy-to-update TCP application workloads. An extensive validation study is performed using Abilene and university traces. The method is validated by comparing traces of synthetically generated traffic to the original traces for a set of important measures of realism. We also show how workload models can be re-sampled to generate statistically valid randomized and rescaled variations.

By scheduling the non real-time tasks earlier while still meeting deadlines for the real-time tasks, the overall system performance can be improved. In particular, we believe that the variability in the execution time requirements of real-time tasks can be effectively leveraged to reduce response times of non real-time tasks. We propose a novel processor sharing algorithm where the processor share of RT jobs increases with their progress based on the empirical probability distribution of execution times of real-time tasks, to adaptively schedule variable requirement real-time to maximize the minimum expected service rate to non real-time tasks at any instant.

Active queue management (AQM) in routers has been proposed as a solution to some of the scalability issues associated with TCP’s pure end-to-end approach to congestion control. However, beyond congestion control, controlling queues in routers is important because unstable router queues can cause poor application performance. Existing AQM schemes explicitly try to control router queues by probabilistically dropping (or marking) packets. We argue that while controlling router queues is important, this control needs to be tempered by a consideration of the overall lossrate at the router. Solely attempting to control queue length can induce loss-rates that have as negative an effect on application and network performance as the large queues that existing AQM schemes were trying to avoid. Thus controlling queue length without regard to loss-rate can be counterproductive. In this work we demonstrate that by jointly controlling queue length and loss-rate, both network and application performance are improved. We present a novel AQM design that attempts to simultaneously optimize queue length and loss-rate. Our algorithm, called loss and queuing delay control (LQD), is a control theoretic scheme that explicitly treats loss-rate as a control parameter. LQD is shown to provide stable control analytically and is evaluated empirically by comparing its performance against other control theoretic AQM designs (PI and REM). The results of evaluation in a laboratory testbed under realistic traffic mixes and loads show that LQD results in lower overall loss rates and that applications see lower average queue lengths than with PI or REM.

We describe a new methodology for understanding how applications use TCP to exchange data. The method is useful for characterizing TCP workloads and synthetic traffic generation. Given a packet header trace, the method automatically constructs a source-level model of the applications using TCP in a network without any a priori knowledge of which applications are actually present in a network. From this source-level model, statistical feature vectors can be defined for each TCP connection in the trace. Hierarchical cluster analysis can then be performed to identify connections that are statistically homogeneous and that are likely exerting similar demands on a network. We apply the methods to packet header traces taken from the UNC and Abilene networks and show how classes of similar connections can be automatically detected and modeled.

Active queue management (AQM) in routers has been proposed as a solution to some of the scalability issues associated with TCP's pure end-to-end approach to congestion control. A recent study of AQM demonstrated its effectiveness in reducing the response times of Web request/response exchanges as well as increasing link throughput and reducing loss rates [L. Le et al., 2003]. However, use of the ECN (explicit congestion notification) signaling protocol was required to outperform drop-tail queuing. Since ECN is not currently widely deployed on end-systems, we investigate an alternative to ECN, namely applying AQM differentially to flows based on a heuristic classification of the flow's transmission rate. Our approach, called differential congestion notification (DCN), distinguishes between "small" flows and "large" high-bandwidth flows and only provides congestion notification to large high-bandwidth flows. We compare DCN to other prominent AQM schemes and demonstrate that for Web and general TCP traffic, DCN outperforms all the other AQM designs, including those previously designed to differentiate between flows based on their size and rate.

New source-level models for aggregated HTTP traffic and a design for their integration with the TCP transport layer are built and validated using two large-scale collections of TCP/IP packet header traces. An implementation of the models and the design in the ns network simulator can be used to generate web traffic in network simulations

We measured and analyzed the variability in round trip times (RTTs) within TCP connections using passive measurement techniques. We collected eight hours of bidirectional traces containing over 22 million TCP connections between end-points at a large university campus and almost $1$ million remote locations. Of these, we used over 1 million TCP connections that yield 10 or more valid RTT samples, to examine RTT variability within a TCP connection. Our results indicate that contrary to observations in several previous studies, RTT values within a connection vary widely. Our results have implications for designing better simulation models, and understanding how round trip times affect the dynamic behavior and throughput of TCP connections.

We present an empirical study of the effects of active queue management (AQM) on the distribution of response times experienced by a population of web users. Three prominent AQM schemes are considered: the Proportional Integrator (PI) controller, the Random Exponential Marking (REM) controller, and Adaptive Random Early Detection (ARED). The effects of these AQM schemes were studied alone and in combination with Explicit Congestion Notification (ECN). Our major results are:

Real-time signal-processing applications for high assurance systems are commonly designed using a processing-graph software architecture. Here we demonstrate the management of latency and buffer requirements in such an architecture—the US Navy's processing graph method (PGM). By applying recent results in real-time scheduling theory to the subset of PGM employed by the US DARPA rapid prototyping of application-specific signal processors (RASSP) synthetic aperture radar (SAR) benchmark application, we identify inherent real-time properties of nodes in a PGM graph, and demonstrate how these properties can be exploited to perform useful and important system-level analyses such as schedulability analysis, end-to-end latency analysis, and memory requirements analysis. More importantly, we develop relationships between properties such as latency and buffer bounds and show how one may be traded off for the other.

We study the effects of RED on the performance of Web browsing with a novel aspect of our work being the use of a user-centric measure of performance: response time for HTTP request-response pairs. We empirically evaluate RED across a range of parameter settings and offered loads. Our results show that: (1) contrary to expectations, compared to an FIFO queue, RED has a minimal effect on HTTP response times for offered loads up to 90% of link capacity; (2) response times at loads in this range are not substantially affected by RED parameters; (3) between 90% and 100% load, RED can be carefully tuned to yield performance somewhat superior to FIFO, however, response times are quite sensitive to the actual RED parameter values selected; and (4) in such heavily congested networks, RED parameters that provide the best link utilization produce poorer response times. We conclude that for links carrying only Web traffic, RED queue management appears to provide no clear advantage over tail-drop FIFO for end-user response times.

We study the effects of RED on the performance of Web browsing with a novel aspect of our work being the use of a user-centric measure of performance - response time for HTTP request-response pairs. We empirically evaluate RED across a range of parameter settings and offered loads. Our results show that: (1) contrary to expectations, compared to a FIFO queue, RED has a minimal effect on HTTP response times for offered loads up to 90% of link ca?pacity, (2) response times at loads in this range are not substantially effected by RED pa?rameters, (3) between 90% and 100% load, RED can be carefully tuned to yield performance somewhat superior to FIFO, however, response times are quite sensitive to the actual RED pa?rameter values selected, and (4) in such heavily congested networks, RED parameters that provide the best link utilization produce poorer response times. We conclude that for links carrying only web traf?fic, RED queue management appears to provide no clear advantage over tail-drop FIFO for end-user response times.

Packet switching in connection-oriented networks that may have multiple parallel links between pairs of switches is considered. An efficient packet scheduling algorithm that guarantees a deterministic quality of service to connections with real time constraints is proposed; this algorithm is a generalization of some recent multiprocessor scheduling algorithms, and offers real time performance guarantees similar to those offered by earlier fair scheduling strategies, such as Weighted Fair Queueing and proportional share schemes.

We present a task model for the real-time execution of event-driven tasks in which no a priori characterization of the actual arrival rates of events is known; only the expected arrival rates of events is known. The model, called rate-bared execution (RBE), is a generalization of Mok's sporadic task model. The RBE model is motivated naturally by distributed multimedia and digital signal processing applications. We derive necessary and sufficient conditions for determining the feasibility of an RBE task set and demonstrate that earliest deadline first (EDF) scheduling is an optimal scheduling algorithm for both preemptive and nonpreemptive execution environments, as well as hybrid environments wherein RBE tasks access shared resources. Our analysis of RBE tasks demonstrates a fundamental distinction between deadline based scheduling methods and static priority based methods. We show that for deadline-based scheduling methods, feasibility is solely a function of the distribution of task deadlines in time. This is contrasted with static priority schedulers where feasibility is a function of the actual arrival rates of work for tasks. Thus whereas the feasibility of static priority schedulers is a function of the periodicity of tasks, the feasibility of deadline schedulers is independent of task arrival processes and hence deadline schedulers are more suitable for use in distributed, event-driven, real-time systems.

We consider the problem of implementing shared objects in uniprocessor and multiprocessor real-time systems in which tasks are executed using a scheduling quantum. In most quantum-based systems, the size of the quantum is quite large in comparison to the length of an object call. As a result, most object calls can be expected to execute without preemption. A good object-sharing scheme should optimize for this expected case, while achieving low overhead when preemptions do occur. In this paper, we present several new shared-object algorithms for uniprocessors and multiprocessors that were designed based upon this principle. We also present scheduling analysis results that can be used in conjunction with these algorithms.

While there is currently great interest in the problem of providing real time services in general purpose operating systems, the issue of real time scheduling of internal operating system activities has received relatively little attention. Without such real time scheduling, the system is susceptible to conditions such as receive livelock-a situation in which an operating system spends all its time processing arriving network packets, and application processes, even if scheduled with a real time scheduler, are starved. We investigate the problem of scheduling operating system activities such as network protocol processing in a proportional share manner. We describe a proportional share implementation of the FreeBSD operating system and demonstrate that it solves the receive livelock problem. Packets are processed within the operating system only at the cumulative rate at which the destination applications are prepared to receive them. If packets arrive at a faster rate then they are discarded after consuming minimal system resources. In this manner the performance of "well behaved" applications is unaffected by "misbehaving" applications. We demonstrate this effect by running a set of multimedia applications under a variety of network conditions on a set of increasingly sophisticated proportional share implementations of FreeBSD and comparing their performance. This work contributes to our knowledge of the engineering of proportional share real time systems.

The Processing Graph Method (PGM)-a dataflow model widely used in the design and analysis of embedded signal-processing applications-is studied from a real-time scheduling perspective. It is shown that the problem of deciding if instances of the general model are feasible on a single processor is intractable (co-NP-complete in the strong sense); however, a useful special case is sometimes more tractable. An efficient feasibility test and an optimal preemptive scheduling algorithm are derived for this special case, and a procedure is presented which permits system architects to make efficient use of computational resources and memory requirements for buffers while constructing real-time dataflow applications that offer hard service guarantees.

This article considers the use of lock-free shared objects within hard real-time systems. As the name suggests,lock-freeshared objects are distinguished by the fact that they are accessed without locking. As such, they do not give rise to priority inversions, a key advantage over conventional, lock-based object-sharing approaches. Despite this advantage, it is not immediately apparent that lock-free shared objects can be employed if tasks must adhere to strict timing constraints. In particular, lock-free object implementations permit concurrent operations to interfere with each other, and repeated interferences can cause a given operation to take an arbitrarily long time to complete. The main contribution of this article is to show that such interferences can be bounded by judicious scheduling. This work pertains to periodic, hard real-time tasks that share lock-free objects on a uniprocessor. In the first part of the article, scheduling conditions are derived for such tasks, for both static and dynamic priority schemes. Based on these conditions, it is formally shown that lock-free shared objects often incur less overhead than object implementations based on wait-free algorithms or lock-based schemes. In the last part of the article, this conclusion is validated experimentally through work involving a real-time desktop videoconferencing system.

One of the major problems experienced with LAN-based videoconferencing systems is the degradation of conference latency and fidelity due to network congestion. In this paper, we present a comprehensive transmission control framework describing the relationship of latency and fidelity to properties of human perception and network congestion. We discuss how network factors such as physical link capacity and size of maximum transmission units may exacerbate the effects of congestion on the conference and how the impact of congestion can be ameliorated through judicious adaptation of the media streams' bit and message rates. Finally, we demonstrate the ability of an adaptive transmission control algorithm based upon the framework to produce low-latency, high-fidelity conferences over congested internetworks.

We propose and analyze a proportional share resource allocation algorithm for realizing real-time performance in time-shared operating systems. Processes are assigned a weight which determines a share (percentage) of the resource they are to receive. The resource is then allocated in discrete-sized time quanta in such a manner that each process makes progress at a precise, uniform rate. Proportional share allocation algorithms are of interest because: they provide a natural means of seamlessly integrating real and non-real-time processing; they are easy to implement; they provide a simple and effective means of precisely controlling the real-time performance of a process; and they provide a natural means of policing so that processes that use more of a resource than they request have no ill-effect on well-behaved processes. We analyze our algorithm in the context of an idealized system in which a resource is assumed to be granted in arbitrarily small intervals of time and show that our algorithm guarantees that the difference between the service time that a process should receive and the service time it actually receives is optimally bounded by the size of a time quantum. In addition, the algorithm provides support for dynamic operations, such as processes joining or leaving the competition, and for both fractional and non-uniform time quanta. As a proof of concept we have implemented a prototype of a CPU scheduler under FreeBSD. The experimental results shows that our implementation performs within the theoretical bounds and hence supports real-time execution in a general purpose operating system.

Summary form only given, as follows. Static models are not appropriate for next-generation distributed real-time applications that are likely to be adaptive in nature, (for example, to provide a high degree of fault tolerance). During the last few years, the real-time systems community has started to counter this criticism by extending traditional work to cover newer application domains, The central problem remains, however, that the concept of adaptivity is often domain-specific and sometimes ill-defined in the context of bringing distributed real-time systems concept into better focus. Accordingly, be it resolved that future distributed embedded and real-time applications will be adaptive and that meanings, challenges and research paradigms await discovery. The charge to the panel is to defend (or to dismiss as fluff) the above resolution.

This paper considers the use of lock-free shared objects within hard real-time systems. As the name suggests, lock-free shared objects are distinguished by the fact that they are not locked. As such, they do not give rise to priority inversions, a key advantage over conventional, lock-based object-sharing approaches. Despite this advantage, it is not immediately apparent that lock-free shared objects can be employed if tasks must adhere to strict timing constraints. In particular, lock-free object implementations permit concurrent operations to interfere with each other, and repeated interferences can cause a given operation to take an arbitrarily long time to complete. The main contribution of this paper is to show that such interferences can be bounded by judicious scheduling. This work pertains to periodic, hard real-time tasks that share lock-free objects on a uniprocessor. In the first part of the paper, scheduling conditions are derived for such tasks, for both static and dynamic priority schemes. Based on these conditions, it is formally shown that lock-free object-sharing approaches can be expected to incur much less overhead than approaches based on wait-free objects or lock-based schemes. In the last part of the paper, this conclusion is validated experimentally through work involving a real time desktop videoconferencing system.

One of the major obstacles facing designers of video conferencing systems is the problem of ameliorating the effects of congestion on interconnected packet-switched networks that do not support real-time communication. We present a framework for transmission control that describes the current network environment as a set of sustainable bit and packet transmission-rate combinations and show that adaptively scaling both the bit and packet-rate of the audio and video streams can reduce the impact of congestion. We empirically demonstrate the validity of adapting both packet and bit-rate using a simple feedback mechanism and simple adaptation heuristics to deliver audio and video streams suitable for low-latency, high-fidelity playout.

In order to apply the results of formal studies of real-time task models, a practitioner must account for the effects of phenomena present in the implementation but not present in the formal model. We study the feasibility and schedulability problems for periodic tasks that must compete for the processor with interrupt handlers - tasks that are assumed to always have priority over application tasks. The emphasis in the analysis is on deadline driven scheduling methods. We develop conditions that solve the feasibility and schedulability problems and demonstrate that our solutions are computationally feasible. Lastly, we compare our analysis with others developed for static priority task systems.>

ABSTRACT The UNC Collaboratory project is concerned with both the process of collaboration and with computer systems to support that process. Here, we describe a component of the Artifact-Based Collaboration (ABC) system, called the Matrix, that provides an infrastructure in which existing single-user applications can be incorporated with few, if any, changes and used collaboratively. We take the position that what is needed is not new tools but better infrastructure for using familiar single-user tools collectively. The paper discusses the Matrix architecture, a Virtual Screen component, and generic functions that provide conferencing, hyperlinking, and recording of users' actions for all applications.

The problem of scheduling a set of sporadic tasks that share a set of serially reusable, single unit software resources on a single processor is considered. The correctness conditions are that: each invocation of each task completes execution at or before a well-defined deadline; and a resource is never accessed by more than one task simultaneously. An optimal online algorithm for scheduling a set of sporadic tasks is presented. The algorithm results from the integration of a synchronization scheme for access to shared resources with the earliest deadline first algorithm. A set of relations on task parameters that are necessary and sufficient for a set of tasks to be schedulable is also derived. The proposed model for the analysis of processor scheduling policies is novel in that it incorporates minimum as well as maximum processing time requirements of tasks. The scheduling algorithm and the sporadic tasking model have been incorporated into an operating system kernel and used to implement several real-time systems.>

A fundamental problem in the theory of real-time scheduling is examined: scheduling a set of periodic or sporadic tasks on a uniprocessor without preemption and without inserted idle time. The authors give a necessary and sufficient set of conditions C for a set of periodic or sporadic tasks to be schedulable for arbitrary release times of the tasks. They show that any set of periodic or sporadic tasks that satisfies C can be scheduled with an earliest-deadline-first (EDF) scheduling algorithm. The authors present the scheduling model, briefly review the literature in real-time scheduling, prove that the non-preemptive EDF algorithm is universal for sets of tasks, whether periodic or sporadic, and demonstrate the absence of a universal algorithm for periodic tasks with specified release times. It is proved that the problem of deciding schedulability of a set of concrete periodic tasks is intractable.>

An examination is made of the problem of guaranteeing, on a uniprocessor, response times to sporadic tasks with preemption constraints. The preemption constraints arise from the fact that tasks require exclusive access to shared software resources during portions of their computations. The primary objective is to determine conditions under which it is possible to guarantee a response time to each task which is less than or equal to the task's minimum interexecution request time. An analysis is made of three different characterizations of a task's resource requirements. It is shown that for restricted patterns of resource usage, there exist synchronization and scheduling disciplines which are optimal for executing these tasks.>