Existing machine learning inference-serving systems largely rely on hardware scaling by adding more devices or using more powerful accelerators to handle increasing query demands. However, hardware scaling might not be feasible for fixed-size edge clusters or private clouds due to their limited hardware resources. A viable alternate solution is accuracy scaling, which adapts the accuracy of ML models instead of hardware resources to handle varying query demands. This work studies the design of a high-throughput inference-serving system with accuracy scaling that can meet throughput requirements while maximizing accuracy. To achieve the goal, this work proposes to identify the right amount of accuracy scaling by jointly optimizing three sub-problems: how to select model variants, how to place them on heterogeneous devices, and how to assign query workloads to each device. It also proposes a new adaptive batching algorithm to handle variations in query arrival times and minimize SLO violations. Based on the proposed techniques, we build an inference-serving system called Proteus and empirically evaluate it on real-world and synthetic traces. We show that Proteus reduces accuracy drop by up to 3× and latency timeouts by 2--10× with respect to baseline schemes, while meeting throughput requirements.

Efficient GPU scheduling is the key to minimizing the execution time of the Deep Learning (DL) training workloads. DL training system schedulers typically allocate a fixed number of GPUs to each job, which inhibits high resource utilization and often extends the overall training time. The recent introduction of schedulers that can dynamically reallocate GPUs has achieved better cluster efficiency. This dynamic nature, however, introduces additional overhead by terminating and restarting jobs or requires modification to the DL training frameworks.We propose and develop an efficient, non-intrusive GPU scheduling framework that employs a combination of an adaptive GPU scheduler and an elastic GPU allocation mechanism to reduce the completion time of DL training workloads and improve resource utilization. Specifically, the adaptive GPU scheduler includes a scheduling algorithm that uses training job progress information to determine the most efficient allocation and reallocation of GPUs for incoming and running jobs at any given time. The elastic GPU allocation mechanism works in concert with the scheduler. It offers a lightweight and nonintrusive method to reallocate GPUs based on a “SideCar” process that temporarily stops and restarts the job's DL training process with a different number of GPUs. We implemented the scheduling framework as plugins in Kubernetes and conducted evaluations on two 16-GPU clusters with multiple training jobs based on TensorFlow. Results show that our proposed scheduling framework reduces the overall execution time and the average job completion time by up to 45% and 63%, respectively, compared to the Kubernetes default scheduler. Compared to a termination based scheduler, our framework reduces the overall execution time and the average job completion time by up to 20% and 37%, respectively.

Third generation (3G) wireless networks based on the CDMA2000 and UMTS standards are now increasingly being deployed throughout the world. Because of their complex signaling and relatively limited bandwidth, these 3G networks are generally more vulnerable than their wireline counterparts, thus making them fertile ground for new attacks. In this paper, we identify and study a novel denial of service (DoS) attack, called signaling attack, that exploits the unique vulnerabilities of the signaling/control plane in 3G wireless networks. Using simulations driven by real traces, we are able to demonstrate the impact of a signaling attack. Specifically, we show how a well-timed low-volume signaling attack can potentially overload the control plane and detrimentally affect the key elements in a 3G wireless infrastructure. The low-volume nature of the signaling attack allows it to avoid detection by existing intrusion detection algorithms, which are often signature or volume-based. As a counter-measure, we present and evaluate an online early detection algorithm based on the statistical CUSUM method. Through the use of extensive trace-driven simulations, we demonstrate that the algorithm is robust and can identify an attack in its inception, before significant damage is done.

Abstract — Fast spreading worms are a reality, as amply demonstrated by worms such as Slammer, which reached its peak propagation in a matter of minutes. With these kinds of fast spreading worms, the traditional approach of signature-based detection is no longer sufficient. Specifically, these worms can infect all vulnerable hosts well before a signature is available. To counter them, we must devise fast detection algorithms that can detect new worms without signatures as they first begin to appear. We present the design and evaluation of such an algorithm in this paper. The key to the algorithm is the identification of certain invariant characteristics of worm propagation. Specifically, we are able to demonstrate using real network traces how worm propagation can perturb the arrival process distribution of unsolicited packets. Our algorithm employs a novel two-step procedure that combines a first stage change point detection with a second stage growth rate inference to confirm the existence of aworm. To evaluate the algorithm, we have applied it to multi-year network traces that cover many of the major worm outbreaks in recent years, including Slammer, Witty, Nimda and Blaster. In all cases, the new algorithm is able to detect the worm within a very short time, well before significant infection has taken place. I.

The total number of hotspot users around the world is expected to grow from 9.3 million at the end of 2003 to 30 million at the end of 2004 according to researcher Gartner. Given the explosive growth in hotspot wireless usage, enhancing capacity of 802.11-based hot-spot wireless networks is an important problem. In this paper, we make two important contributions. We first present the AP-CST algorithm that dynamically adjusts the carrier sense threshold (CST) in order to allow more flows to coexist in current 802.11 architectures. We then extend the current hotspot engineering paradigm by allowing every cell and AP access to all available channels. These cells are then managed by the RNC-SC algorithm running in a centralized radio network controller. This algorithm assigns mobile stations to appropriate cells/channels and adjusts transmit power values dynamically, thereby exploiting spatial heterogeneity in distribution of users at the hotspots. Through detailed and extensive simulations, we show that the performance of 802.11-based hotspots can be improved by up to 195% per-cell and 70% overall.

An attack-resistant network is a purpose-built network to survive attacks; by construction, it should be both resilient and secure. Resiliency is the ability to provide alternative communication paths should one path become disrupted due to failures or attacks; while security is the ability to contain and limit the impact of compromises. Interestingly, these two can present conflicting demands. We provide a first formulation of a new class of problems focusing on the engineering of attack-resistant networks. Our model considers both resiliency and security, and uses a notion of blocking probability as a rigorous measure for evaluating different network constructions. We propose several efficient approximation algorithms for computing blocking probability and provide bounds for their errors. Based on these algorithms, we introduce a family of heuristics to guide the construction of optimal attack-resistant networks with minimum blocking probabilities. We also present extensive results to evaluate and demonstrate the near-optimal performance of our heuristics and approximation algorithms.

The ability to classify packets according to pre-defined rules is critical to providing many sophisticated value-added services, such as security, QoS, load balancing, traffic accounting, etc. Various approaches to packet classification have been studied in the literature with accompanying theoretical bounds. Practical studies with results applying to large number of filters (from 8K to 1 million) are rare. In this paper, we take a practical approach to the problem of packet classification. Specifically, we propose and study a novel approach to packet classification which combines a heuristic tree search with the use of filter buckets. Besides high performance and a reasonable storage requirement, our algorithm is unique in the sense that it can adapt to the input packet distribution by taking into account the relative filter usage. To evaluate our algorithms, we have developed realistic models of large scale filter tables, and used them to drive extensive experimentation. The results demonstrate the practicality of our algorithms for up to even 1 million filters.

We propose and study a new technique, which we call cache-based compaction for reducing the latency of Web browsing over a slow link. The compaction technique trades computation for bandwidth. The key observation is that an object can be coded in a highly compact form for transfer if similar objects that have been transferred earlier can be used as references. The contributions of this paper are: (1) an efficient selection algorithm for selecting similar objects as references, and (2) an encoding/decoding algorithm that reduces the size of a Web object by exploiting its similarities with the reference objects. We verify the efficacy of our proposal through detailed experimental evaluations. This compaction technique significantly generalizes previous work on optimizing Web transfer using compression or differencing, and provides a systematic foundation that ties together caching, compression and prefetching.

In this paper, we study the application of a new technique, which we call cache-based compaction for reducing the latency of email transfer over a slow link. Our compaction technique trades computation for bandwidth. The key observation is that an object can be coded in a highly compact form for transfer if similar objects that have been transferred earlier can be used as references. The compaction algorithm has two components: (1) an efficient selection algorithm for selecting similar objects as references, and (2) an encoding/decoding algorithm that reduces the transfer size of an object by exploiting its similarities with a set of reference objects. Depending on the target applications, different instances of compaction algorithms can be derived. In this paper, an instance of the compaction algorithm for optimizing email transfer is presented. Our compaction technique significantly generalizes previous framework on optimizing data transfer using caching, differencing and compression.

We present the design of a distributed authorization service which parallels existing authentication services for distributed systems. Such a service would operate on top of an authentication substrate. There are two distinct ideas underlying our design: (1) the use of a language, called generalized access control list (GACL), as a common representation of authorization requirements; and (2) the use of authenticated delegation to effect authorization offloading from an end server to an authorization server. We present the syntax and semantics of GACL, and illustrate how it can be used to specify authorization requirements that cannot be easily specified by ordinary ACL. We also describe the protocols in our design.

Wireless two-way messaging is a new wireless data service that is rapidly gaining popularity. The basic service it provides is acknowledged exchange of short messages among subscribers or network-based servers. Like cellular/PCS systems, wireless two-way messaging systems are cellular in structure, and thus share the location management problem. We study the problem of location management for wireless two-way messaging. We first highlight the unique concerns of location management for wireless two-way messaging, and lay out its differences from cellular/PCS telephony. We then provide a new cost formulation for its study. Based on this formulation, we revisit existing schemes that have been proposed for cellular/PCS telephony to evaluate how they perform under wireless two-way messaging. We then introduce new classes of algorithms, called pending replies and deferred delivery, whose designs take advantage of the unique characteristics of wireless two-way messaging, and show through simulation, that they provide improved performance.

Mobile phones are quickly becoming one of the most ubiquitous wireless consumer devices. Separately, Internet services are growing by leaps and bounds. Thus, an interesting area of research is to see if and how the two can be married together to provide wireless ubiquitous access to the ever-growing Internet services. We highlight the challenges and issues in providing Internet services to mobile phones. As an example, we describe and examine a research prototype called Wireless Data Server, which provides, among other services, wireless email service to mobile phone users.

Wireless messaging, in the form of two-way paging, is an integral part of universal Personal Communications Services (PCS). Basic wireless messaging services include providing reliable (acknowledged) message delivery, reply capabilities, and message origination from a messaging device. Many more advanced services can also be envisioned. Wireless networks and end devices impose many limitations on system design. To overcome the problems caused by such an environment, we have introduced network based proxies, called user agents, to assist simple end devices, and a novel way to define messages, called flexible messages, so that advanced messaging services may be offered. In this paper, we describe how user agents and flexible messages assist in providing messaging services in the Pigeon two-way messaging research prototype at Bell Laboratories.

Datagram services provide a simple, flexible, robust, and scalable communication abstraction; their usefulness has been well demonstrated by the success of IP, UDP, and RPC. Yet, the overwhelming majority of network security protocols that have been proposed are geared towards connection-oriented communications. The few that do cater to datagram communications tend to either rely on long term host-pair keying or impose a session-oriented (i.e., requiring connection setup) semantics.Separately, the concept of flows has received a great deal of attention recently, especially in the context of routing and QoS. A flow characterizes a sequence of datagrams sharing some pre-defined attributes. In this paper, we advocate the use of flows as a basis for structuring secure datagram communications. We support this by proposing a novel protocol for datagram security based on flows. Our protocol achieves zero-message keying, thus preserving the connectionless nature of datagram, and makes use of soft state, thus providing the per-packet processing efficiency of session-oriented schemes. We have implemented an instantiation for IP in the 4.4BSD kernel, and we provide a description of our implementation along with performance results.

Wireless messaging is an integral component of universal personal communication services (PCSs). Its growth is likely to be further fueled by the availability of new data capabilities in the new PCS air interfaces. Our research focuses on high-level issues such as new messaging functionalities, high-layer protocols, and overall system design. Pigeon is our proposal of a wireless two-way messaging system. The novelty of our system lies in: (1) the techniques used in mitigating the wireless media and end device constraints, (2) the functionalities provided, and (3) its modular architecture. Examples of (1) include the use of asymmetric protocols and the introduction of user agents. Examples of (2) include group addressing, transaction support, and flexible messages. The modularity of Pigeon allows its individual components to be adopted by specific systems, A prototype of Pigeon has been implemented, and is operational at Bell Laboratories. We describe the motivation, design, and functionality of Pigeon. We also present, as an example, a mapping of Pigeon to a standard cellular/PCS messaging system.

A new class of wireless messaging service, called two-way paging, is emerging. Current research on wireless messaging has mostly been concerned with low-level physical layer transmission issues, e.g., modulation and access. Few efforts have addressed high-level issues such as new messaging functionalities, high layer protocols, and overall system design. Most existing wireless messaging systems are built as monolithic entities in a centralized manner. We contend that the current designs lack flexibility required to meet the demand of next generation messaging needs. Pigeon is our proposal of a two-way messaging system. The novelty of our system lies in (1) the techniques used in mitigating the wireless media and end device constraints, (2) the functionalities provided, and (3) its modular architecture. Examples of (1) include the use of asymmetric protocols and the introduction of user agents. Examples of (2) include group addressing, transaction support and flexible messages. The modularity of Pigeon is especially important when it is mapped onto a specific platform, in which case the components of Pigeon, as opposed to the system as is, may be individually adopted. A prototype of Pigeon has been implemented and is operational at Bell Laboratories. We describe the design of Pigeon. We pay particular attention to motivate its service and system concepts. We also present, as an example, a mapping of Pigeon to cellular messaging.

We present an account of the entire development cycle (i.e., design, specification and verification, and implementation) of a realistic authentication protocol, which is part of a security architecture proposed by us. The protocol's design follows a stepwise refinement process, which we illustrate. Our account of its specification and verification provides a practical demonstration of a proposed formal analysis approach. For its implementation, we adopt the GSS-API standard. We describe the mapping from our protocol to GSS-API, which can serve as a reference for other protocol implementations. We believe that the global perspective presented in this paper would be of great value to protocol designers, verifiers, and implementers, and contribute toward bridging the gap between the theory and practice of authentication protocol design.>

The authors present a new approach to the analysis of authentication protocols. The approach consists of several elements: a specification language for formally specifying authentication protocols, a semantic model for characterizing protocol executions, an assertion language for stating secrecy and correspondence properties, and procedures for verifying these properties. The main emphasis of this paper is on the assertion language, its semantics, and verification procedures. In particular, the authors present a set of proof rules. An example is given to illustrate the approach.>

The authors specify authentication protocols as formal objects with precise syntax and semantics, and define a semantic model that characterizes protocol executions. They have identified two basic types of correctness properties, namely, correspondence and secrecy; that underlie the correctness concerns of authentication protocols. Assertions for specifying these properties, and a formal semantics for their satisfaction in the semantic model are defined. The Otway-Rees protocol is used to illustrate the semantic model and the basic correctness properties.>

It is argued that authorization is an independent semantic concept that must be separated from implementation mechanisms and given a precise semantics. A logical approach to representing and evaluating authorization is proposed. Specifically, a language for specifying policy bases is introduced. A policy base encodes a set of authorization requirements and is given a precise semantics based on a formal notion of authorization policy. The semantics is computable, thus providing a basis for authorization evaluation. Two composition operators for policy bases which are appropriate for modeling distributed systems with multiple administrative domains are introduced.>

An overview is given of a theory of modules and interfaces applicable to the specification and verification of systems with a layered architecture. At the heart of this theory is a module composition theorem. The theory is applied to the specification of a distributed system consisting of subjects and objects in different hosts (computers). Formal specifications of a user interface and a network interface are given. Access to objects, both local and remote, offered by the distributed system is proved to be multilevel secure.>