Mixed reality (MR) telepresence provides a shared common 3D space for networked users to enjoy real-time immersive experiences with natural interactivity and movement. Due to its high hardware and compute demands, a large-scale cloud-edge MR solution is necessary for achieving critical mass adoption, where users engage in the MR environment using low-cost cameras at the edge and complex 3D world processing is offloaded to the cloud servers. However, cloud-edge MR solutions have distinct challenges such as concurrent multiple camera support, unpredictable compute demands, and CPU/GPU contention. In this paper, we present PointPresence, an edge-compute framework for large-scale MR applications. PointPresence is deployed at an edge node, such as an O-RAN RIC or a local enterprise server, and provides low-latency MR experiences to a large number of users by incorporating intelligent camera selection for compute reduction, reactive pipeline design for adaptation to compute demand changes, and context-aware GPU sharing. Our comprehensive evaluation on an MR testbed shows that PointPresence reduces end-to-end latency by up to 3.5× and improves end user perceived visual quality by 30%.

Remote Direct Memory Access (RDMA) has been widely adopted in modern data centers thanks to its high-throughput, low-latency data transfer capability and reduced CPU overhead. However, traditional network-flow-based monitoring is poor at interpreting RDMA communication and hence inadequate for gaining insights. In this paper, we present INSERT, an end-to-end RDMA telemetry system that enables seamless visibility into RDMA communication from the network layer all the way to the application layer. To this end, INSERT combines (i) eBPF-based transparent RDMA tracing on end-hosts and (ii) stateful RDMA network telemetry on programmable data plane. We implement RDMA network telemetry on programmable SmartNICs, where we address practical challenges for maintaining fine-grained state on massively-parallel packet processing pipelines. We demonstrate that INSERT can perform reasonably accurate telemetry at line-rate for different types of RDMA traffic even in the presence of out-of-order packets, and finally showcase two practical use cases that can benefit from it.

While the fast adoption of RDMA in data centers has been primarily driven by its performance benefits, more and more attention is being paid to its security implication, especially with mounting security risks associated with lateral communication within data centers. However, since RDMA is implemented as NIC’s fixed function, it is challenging to incorporate any new security feature in RDMA. In this paper, we propose Zeta, a zero-trust security addon for RoCEv2, which enables network-independent, fine-grained zero-trust security control for RDMA. It does not require any change in RDMA’s ASIC implementation or application-level interfaces. To this end, Zeta leverages modern SmartNIC’s versatility to perform zero-trust policy control on RDMA packets within a SmartNIC in a cryptographically secure fashion. From its prototype implementation and evaluation based on real-word applications, we show that, while cryptographic verification of Zeta introduces 1.5 ms session startup latency, the overhead of end-to-end application performance is marginal (e.g., less than 1% throughput and 5% latency penalty).

In the new industrial Internet, a wide variety of industrial applications are expected to rely on high-performance data communication between a multitude of sensors and actuators that are deployed on a large scale. Publish-subscribe-based communication model is well-suited to handle such large-scale data gathering and dissemination among data sources and sinks. To support publish-subscribe-based data delivery, the newly standardized Segmented Routing over IPv6 (SRv6) can provide non-disruptive network programming primitives for building and maintaining network-efficient, shareable data distribution trees within the network. We study optimal algorithms for setting up different types of multicasting in the SRv6-capable network. In particular, we show, both theoretically and experimentally, that splitting multicast streams into multiple sub-streams, as well as using end-to-end application-layer coding without any network participation can provide significant benefits in terms of multicast throughput compared to traditional single stream multicasting.

It is commonly assumed that the end-to-end networking performance of edge offloading is purely dictated by that of the network connectivity between end devices and edge computing facilities, where ongoing innovation in 5G/6G networking can help. However, with the growing complexity of edge-offloaded computation and dynamic load balancing requirements, an offloaded task often goes through a multi-stage pipeline that spans across multiple compute nodes and proxies interconnected via a dedicated network fabric within a given edge computing facility. As the latest hardware-accelerated transport technologies such as RDMA and GPUDirect RDMA are adopted to build such network fabric, there is a need for good understanding of the full potential of these technologies in the context of computation offload and the effect of different factors such as GPU scheduling and characteristics of computation on the net performance gain achievable by these technologies. This paper unveils detailed insights into the latency overhead in typical machine learning (ML)-based computation pipelines and analyzes the potential benefits of adopting hardware-accelerated communication. To this end, we build a model-serving framework that supports various communication mechanisms. Using the framework, we identify performance bottlenecks in state-of-the-art model-serving pipelines and show how hardware-accelerated communication can alleviate them. For example, we show that GPUDirect RDMA can save 15-50% of model-serving latency, which amounts to 70–160 ms.

State-disaggregated Network Function Virtualization (NFV) architectures decouple NF states from packet processing logic to achieve elasticity and resilience in stateful NFs. However, the existing state disaggregation approaches suffer from either poor NF performance due to frequent remote state access or potential inconsistencies in state updates when multiple NF instances concurrently access shared states. Moreover, they do not properly support state rejuvenation/expiration which is required for resource scalability of stateful NF operations. This paper presents a new state-disaggregated NFV system called RESCue that addresses these problems. RESCue handles remote state access differently for shared and private states. For efficient and consistent access of shared states, it leverages a lightweight custom control message protocol between NFs and a centralized state server. For private state access, it adopts a remote-paging-based interface to avoid introducing expensive blocking remote access within the critical path of NF packet processing. Finally, it utilizes non-blocking operations for state rejuvenation/expiration handling to minimize its performance overhead. Our evaluation of a RESCue prototype shows that it can handle NF scaling and failure recovery well, while supporting consistent state updates and state rejuvenation/expiration without compromising performance.

Modern data centers are witnessing fast-growing east-west traffic on their network infrastructure due to the highly distributed data center applications. Motivated by the heterogeneity of such application workloads, we propose in this article an extensible network management architecture calledMAGNetwhich enables application-aware intra-data center networking. The crux ofMAGNetis the smart endpoint residing within end-hosts, which is empowered by machine learning combined with lightweight workload tracing to detect workload identities and enable workload-dependent packet tagging. The centralized management plane interface ofMAGNetallows network functions to interpret packet tags and perform application-aware packet processing. We demonstrate the feasibility of the architecture via prototype implementation and extensive use case evaluation. Our experiments show that the smart endpoint can fingerprint many real-world applications with 99 percent accuracy only at 1–2 percent additional CPU, and that application-aware data plane can potentially bring substantial benefits in terms of security (e.g., via identity-based microsegmentation), CPU usage (e.g., for intrusion detection) and network latency (e.g., via TCP stack customization).

Multiplexing resources is the core savings principle upon which the economic model of the Cloud is built. Cloud customers can flexibly purchase additional resources when needed, and trim these down when the need has past, while Cloud providers can direct resources when and where customers might require. One aspect which poses a challenge to this capability is the allocation process itself, which can be costly in terms of time and energy. Indeed, both provider and customer would prefer if resource allocation would be continuous, fast and with low energy overhead. Since this is not the case, there is an inherent tension between limiting the number of allocation events and efficient resource utilization.This paper considers this tension using several different models, and proposes a history-based dynamic allocation scheme that minimizes the number of resource allocation transition points for both average and adversarial use cases. We prove performance bounds and use extensive simulation to study the performance of our scheme.

Performance troubleshooting is notoriously difficult for distributed microservices-based applications. A typical root-cause diagnosis for performance anomaly by an analyst starts by narrowing down the scope of slow services, investigates into high-level performance metrics or available logs in the slow components, and finally drills down to an actual cause. This process can be long, tedious, and sometimes aimless due to the lack of domain knowledge and the sheer number of possible culprits. This paper introduces a new machine-learning-driven performance analysis system called LongTale that automates the troubleshooting process for latency-related performance anomalies to facilitate the root cause diagnosis and explanation. LongTale builds on existing application-layer tracing in two significant aspects. First, it stitches application-layer traces with corresponding system stack traces, which enables more informative root-cause analysis. Second, it utilizes a novel machine-learning-driven analysis that feeds on the combined data to automatically uncover the most likely contributing factor(s) for given performance slowdown. We demonstrate how LongTale can be utilized in different scenarios, including abnormal long-tail latency explanation and performance interference analysis.

Having an efficient onboarding process is a pivotal step to utilize and provision the IoT devices for accessing the network infrastructure. However, the current process to onboard IoT devices is time-consuming and labor-intensive, which makes the process vulnerable to human errors and security risks. In order to have a streamlined onboarding process, we need a mechanism to reliably associate each digital identity with each physical device. We design an onboarding mechanism called MAIDE to fill this technical gap. MAIDE is an Augmented Reality (AR)-facilitated app that systematically selects multiple measurement locations, calculates measurement time for each location and guides the user through the measurement process. The app also uses an optimized voting-based algorithm to derive the device-to-ID mapping based on measurement data. This method does not require any modification to existing IoT devices or the infrastructure and can be applied to all major wireless protocols such as BLE, and WiFi. Our extensive experiments show that MAIDE achieves high device-to-ID mapping accuracy. For example, to distinguish two devices on a ceiling in a typical enterprise environment, MAIDE achieves ~95% accuracy by measuring 5 seconds of Received Signal Strength (RSS) data for each measurement location when the devices are 4 feet apart.

The onset of the 6G era in telecommunications, touted to launch in 2030, is hoped to serve many masters and deliver an unparalleled improvement in capabilities, applications, intelligence, and indeed liberate human potential. The vision of 6G incorporates new radio frequencies and technologies, the integration of sensing, cognitive methods defining both network functions and their management, and new networking approaches for a broader scope of applications and distribution. The challenges for inventors lies in both physical devices and a substantive improvement in the development of functions implemented by, and managed, with software. The algorithms (including dynamic solutions based on Artificial Intelligence and Machine Learning), protocols, and architecture evolutions will bring together the most advanced software systems ever imagined for telecommunications. Yet, the business of companies building and operating these next generation platforms requires a huge investment, and 6G will exceed all others with its breadth and complexity. This paper outlines one possible timeline of technological impact based on the pace of invention, investment, global context, and the broad goals of 6G. From this, follows a vision of the critical methods in automation, security and networking that we believe will be central to bringing the dream of 6G to a reality.

Since the outbreak of the COVID-19 pandemic, videoconferencing has become the default mode of communication in our daily lives at homes, workplaces and schools, and it is likely to remain an important part of our lives in the post-pandemic world. Despite its significance, there has not been any systematic study characterizing the user-perceived performance of existing videoconferencing systems other than anecdotal reports. In this paper, we present a detailed measurement study that compares three major videoconferencing systems: Zoom, Webex and Google Meet. Our study is based on 62 hours’ worth of more than 1.1K videoconferencing sessions, which were created with a mix of emulated videoconferencing clients deployed in the cloud, as well as real mobile devices running from a residential network over two separate periods with nine months apart. We find that the existing videoconferencing systems vary in terms of geographic scope and resource provisioning strategies, which in turns determine streaming lag experienced by users. We also observe that streaming rate can change under different conditions (e.g., available bandwidth, number of users in a session, mobile device status), which affects user-perceived streaming quality. Beyond these findings, our measurement methodology enables reproducible benchmark analysis for any types of comparative or longitudinal study on available videoconferencing systems.

Since the outbreak of the COVID-19 pandemic, videoconferencing has become the default mode of communication in our daily lives at homes, workplaces and schools, and it is likely to remain an important part of our lives in the post-pandemic world. Despite its significance, there has not been any systematic study characterizing the user-perceived performance of existing videoconferencing systems other than anecdotal reports. In this paper, we present a detailed measurement study that compares three major videoconferencing systems: Zoom, Webex and Google Meet. Our study is based on 48 hours' worth of more than 700 videoconferencing sessions, which were created with a mix of emulated videoconferencing clients deployed in the cloud, as well as real mobile devices running from a residential network. We find that the existing videoconferencing systems vary in terms of geographic scope, which in turns determines streaming lag experienced by users. We also observe that streaming rate can change under different conditions (e.g., number of users in a session, mobile device status, etc), which affects user-perceived streaming quality. Beyond these findings, our measurement methodology can enable reproducible benchmark analysis for any types of comparative or longitudinal study on available videoconferencing systems.

Dynamic resource allocation to satisfy varying, concurrent and unpredictable demands from multiple applications is a key need in cloud systems. A fundamental challenge is the need to find the right balance between over-allocation, which satisfies each application’s varying needs without requiring frequent allocation changes, and system efficiency which requires that the allocation exactly matches the application needs. However, allocating resources close to current needs will result in frequent allocation changes. This can be detrimental to applications since there may be fixed costs (state replication, policy reconfiguration, etc.) that need to be incurred by applications for each allocation change. In this paper, we develop an MDP-based dynamic allocation scheme that uses reinforcement learning to satisfy unpredictable application demands. It minimizes the overall resource allocation needed to satisfy varying application demands while meeting application constraints on the rate of allocation changes. We prove convergence bounds and use real-world traces to study the performance.

Mobile Augmented Reality (MAR) is going to play an important role in industrial automation. In order to tag a physical object in the MAR world, a smart phone running MAR-based applications must know the precise location of an object in the real world. Tracking and localizing a large number of objects in an industrial environment can become a huge burden for the smart phone due to compute and battery requirements. In this paper we propose GLAMAR, a novel framework that leverages externally provided geo-location of the objects and IMU sensor information (both of which can be noisy) from the objects to 10-cate them precisely in the MAR world. GLAMAR offloads heavy-duty computation to the edge and supports building MAR-based applications using commercial development packages. We develop a regenerative particle filter and a continuously improving transformation matrix computation methodology to dramatically improve the positional accuracy of objects in the real and the AR world. Our prototype implementation on Android platform using ARCore shows the practicality of GLAMAR in developing MAR-based applications with high precision, efficiency, and more realistic experience. GLAMAR is able to achieve less then 10cm error compared to the ground truth for both stationary and moving objects and reduces the CPU overhead by 83% and battery consumption by 80% for mobile devices.

In order to create services using IoT devices, the underlying network infrastructure must support large number of such devices with different underlying protocols, and diverse requirements from the service applications (privacy, reliability and QoS guarantee, etc.). Many of these requirements can be realized by implementing an in-network packet forwarding policy in the infrastructure supporting direct device-to-device communications. However, with large number of devices deployed in the IoT network, the number of rules required for policy enforcement grows very rapidly, and it becomes an infrastructural challenge to installing and managing the rules in switches/routers. We argue that attaching service and role-based labels to address IoT devices can significantly reduce the number of rules by using wild-cards. We formulate a scheme that can produce the optimum length labels for representing the service attributes of the communicating IoT devices. Due to non-convex nature of the optimization, we develop two heuristic solutions for the label generating scheme. Through evaluation using a simulated but practical IoT network environment with large number of devices, we demonstrate the benefits of the scheme that can reduce the number of rules by several orders of multitude.

Application aware data centers promise various benefits for data center management, in terms of resource provisioning, power estimation, network management, security protection, etc. However, the emerging microservices make it challenging for data center operators to accurately identify what applications are deployed by tenants, due to their highly dynamic and heterogeneous nature. In this paper, we address the problem of fingerprinting microservices in a unified, efficient, accurate and non-intrusive fashion. To this end, we characterize the runtime behaviors of microservices using eBPF-based lightweight system call tracing. To accurately fingerprint a diverse set of microservices based on their system call activities, we utilize the machine learning approach which combines Bayesian learning and LSTM autoencoders. We demonstrate that our approach can fingerprint many real-world microservices with 99% accuracy, using 1-2% additional CPU resource, and can detect the presence of previously unseen microservices with near perfect accuracy.

Mobility tracking of IoT devices in smart city infrastructures such as smart buildings, hospitals, shopping centers, warehouses, smart streets, and outdoor spaces has many applications. Since Bluetooth Low Energy (BLE) is available in almost every IoT device in the market nowadays, a key to localizing and tracking IoT devices is to develop an accurate ranging technique for BLE-enabled IoT devices. This is, however, a challenging feat as billions of these devices are already in use, and for pragmatic reasons, we cannot propose to modify the IoT device (a BLE peripheral) itself. Furthermore, unlike WiFi ranging - where the channel state information (CSI) is readily available and the bandwidth can be increased by stitching 2.4GHz and 5GHz bands together to achieve a high-precision ranging, an unmodified BLE peripheral provides us with only the RSSI information over a very limited bandwidth. Accurately ranging a BLE device is therefore far more challenging than other wireless standards. In this paper, we exploit characteristics of BLE protocol (e.g. frequency hopping and empty control packet transmissions) and propose a technique to directly estimate the range of a BLE peripheral from a BLE access point by multipath profiling. We discuss the theoretical foundation and conduct experiments to show that the technique achieves a 2.44m absolute range estimation error on average.

This paper proposes Muppet, an edge-based multi-protocol architecture for large-scale Internet of Things (IoT) deployment and service automation. The crux of Muppet is a P4-based switch that inserts itself in between communicating IoT devices that can use different protocols. The switches are networked over IP to support wide area deployment and managed using centralized SDN control for scalability. Muppet provides many of the benefits of both native peer-to-peer and widely used cloud-centric approaches while avoiding their drawbacks. For example, Muppet offers low-latency and low-energy benefits of the peer-to-peer approach, while enabling wide-area, cross-protocol automation similar to the cloud-based solutions. We describe the P4 design and prototype realization of the switch using two very popular, but widely disparate, IoT protocols, namely, Bluetooth low energy and Zigbee. Through experiments, we show that Muppet is as efficient as peer-to-peer in terms of delay and energy usage, and scalable and programmable as cloud-based solutions. We illustrate its utility through practical use cases.

Increasingly, smart Network Interface Cards (sNICs) are being used in data centers to offload networking functions (NFs) from host processors thereby making these processors available for tenant applications. Modern sNICs have fully programmable, energy-efficient multi-core processors on which many packet processing functions, including a full-blown programmable switch, can run. However, having multiple switch instances deployed across the host hypervisor and the attached sNICs makes controlling them difficult and data plane operations more complex.

Stream processing pipelines operated by current big data streaming frameworks present two problems. First, the pipelines are not flexible, controllable, and programmable enough to accommodate dynamic streaming application needs. Second, the application-level data routing over the pipelines do not exhibit optimal performance for increasingly common one-to-many communication. To address these problems, we propose an SDN-based real-time big data streaming framework called Typhoon, that tightly integrates SDN functionality into a real-time stream framework. By partially offloading application-layer data routing and control to the network layer via SDN interfaces and protocols, Typhoon provides on-the-fly programmability of both the application and network layers, and achieve high-performance data routing. In addition, Typhoon SDN controller exposes cross-layer information, from both the application and the network, to SDN control plane applications to extend the framework's functionality. We introduce several SDN control plane applications to illustrate these benefits.

Bluetooth Low Energy (BLE) is a personal area wireless network technology that is of increasing importance for emerging Internet of Things (IoT) deployments. By design, BLE supports short-range, single-hop communication between a pair of BLE devices. As such, native BLE does not allow network-based policy control or in-network functions for service enhancement. These limitations are impediments to any large-scale BLE based IoT deployment (e.g., in hospital environments), where such sophisticated network-based visibility and control may be required. Relying on cloud-based solutions to meet these requirements has many known shortcomings. This paper proposes an SDN-based architecture for enabling wide area IoT deployments using BLE devices at the edge. We introduce a programmable BLE service switch (BLESS) that is transparently inserted between two communicating BLE devices. BLESS can be programmed at the service layer by a central controller to enable flexible, policy-based switching, as well as various in-network operations in BLE networks. We describe the design of BLESS, its implementation using P4 and OVS, and illustrate its utility through practical use cases.

Software Defined Networking (SDN) can benefit a Network Function Virtualization solution by chaining a set of network functions (NF) to create a network service. Currently, control on NFs is isolated from the SDN, which creates routing inflexibility, flow imbalance and choke points in the network as the controller remains oblivious to the number, capacity and placement of NFs. Moreover, a NF may modify packets in the middle, which makes flow identification at a SDN switch challenging. In this paper, we postulate native NFs within the SDN data plane, where the same logical controller controls both network services and routing. This is enabled by extending SDN to support stateful flow handling based on higher layers in the packet beyond layers 2-4. As a result, NF instances can be chained on demand, directly on the data plane. We present an implementation of this architecture based on Open vSwitch, and show that it enables popular NFs effectively using detailed evaluation and comparison with other alternative solutions.

One of the primary functions of a cloud service provider is to allocate cloud resources to users upon request. Requests arrive in real-time and resource placement decisions must be made as and when a request arrives, without any prior knowledge of future arrivals. In addition, when a cloud service provider operates a geographically diversified cloud that consists of a large number of small data centers, the resource allocation problem becomes even more complex. This is due to the fact that resource request can have additional constraints on data center location, service delay guarantee, and so on, which is especially true for the emerging network function virtualization application. In this paper, we propose a generalized resource placement methodology that can work across different cloud architectures, resource request constraints, with real-time request arrivals and departures. The proposed algorithms are online in the sense that allocations are made without any knowledge of resource requests that arrive in the future, and the current resource allocations are made in such a manner as to permit the acceptance of as many future arrivals as possible. We derive worst case competitive ratio for the algorithms. We show through experiments and case studies the superior performance of the algorithms in practice.

Multipath TCP (MPTCP) is a promising technique for boosting application throughput while using well-known and versatile network socket interfaces. Recently, many interesting applications of MPTCP in various environments such as wireless networks and data centers have been proposed, but little work has been done to investigate the impact of this protocol on conventional network devices. For example, MPTCP throughput advantage can be better achieved if all MPTCP subflows are routed on disjoint paths, but this is currently not feasible since routers are not designed to recognize the membership of MPTCP subflows. In this paper, we take a first step to address this issue by proposing SAMPO, an online algorithm to detect and associate MPTCP subflows in network. The main challenge is that sampling techniques and network dynamics may cause a network device to only obtain partial flow records. SAMPO takes advantage of both protocol information and statistical characteristics of MPTCP data sequence number to overcome the challenge in network. Through analysis and experimentation, we show that SAMPO is able to detect and associate MPTCP subflows with high accuracy even when a small portion of the entire flow records are available.

Software Defined Networking (SDN) has become a popular paradigm for centralized control in many modern networking scenarios such as data centers and cloud. For large data centers hosting many hundreds of thousands of servers, there are few thousands of switches that need to be managed in a centralized fashion, which cannot be done using a single controller node. Previous works have proposed distributed controller architectures to address scalability issues. A key limitation of these works, however, is that the mapping between a switch and a controller is statically configured, which may result in uneven load distribution among the controllers as traffic conditions change dynamically. To address this problem, we propose ElastiCon, an elastic distributed controller architecture in which the controller pool is dynamically grown or shrunk according to traffic conditions. To address the load imbalance caused due to spatial and temporal variations in the traffic conditions, ElastiCon automatically balances the load across controllers thus ensuring good performance at all times irrespective of the traffic dynamics. We propose a novel switch migration protocol for enabling such load shifting, which conforms with the Openflow standard. We further design the algorithms for controller load balancing and elasticity. We also build a prototype of ElastiCon and evaluate it extensively to demonstrate the efficacy of our design.

One of the primary functions of a cloud service provider is to allocate cloud resources to users upon request. Requests arrive in real-time and resource placement decisions must be made as and when a request arrives, without any prior knowledge of future arrivals. In addition, when a cloud service provider operates a geographically diversified cloud that consists of large number of small data centers, the resource allocation problem becomes even more complex. This is due to the fact that resource request can have additional constraints on data center location, service delay guarantee, etc. In this paper, we propose a generalized resource placement methodology that can work across different cloud architectures, resource request constraints, with real-time request arrivals and departures. The proposed algorithms are online in the sense that allocations are made without any knowledge of resource requests that arrive in the future, and the current resource allocations are made in such a manner as to permit the acceptance of as many future arrivals as possible. We derive worst case competitive ratio for the algorithms. We show through experiments and case studies the superior performance of the algorithms in practice.

The articles in this special section focus on new applications that are supported by cloud computing.

In an ad targeting system, an advertiser specifies the profiles of the users to whom it is interested in showing an ad. The underlying ad distribution system would like to use profiles of users, if available, to match advertisers to users in an optimal manner. Availability of the needed profile information very much depends on whether users opt-in to have their profile information revealed. When some set of users opt-out of having their profile information revealed, possibly for privacy reasons, an ad distribution system needs methods to match advertisers to the right users despite the system itself not having full knowledge of the users' profiles. In this paper, we propose solutions to this problem thereby expanding the universe of users to whom ad targeting becomes feasible. Ads can be targeted to opt-in users, whose profiles are therefore known to the ad targeting system, using now known approaches. Our solution enables targeting of ads to users who have chosen to not opt-in to reveal their profiles. Such users keep their true interest profiles to themselves (locally on their equipment). Ads to be displayed are selected locally and ad scheduling is done using a guaranteed approximation online algorithm that uses only statistically falsified profile information and not the true profiles. Despite the use of statistically falsified information, accurate targeting can be done. We show both analytically and experimentally that the performance of the ad scheduler is quite close to optimal.

Large-scale data processing needs of enterprises today are primarily met with distributed and parallel computing in data centers. MapReduce has emerged as an important programming model for these environments. Since today's data centers run many MapReduce jobs in parallel, it is important to find a good scheduling algorithm that can optimize the completion times of these jobs. While several recent papers focused on optimizing the scheduler, there exists very little theoretical understanding of the scheduling problem in the context of MapReduce. In this paper, we seek to address this problem by first presenting a simplified abstraction of the MapReduce scheduling problem, and then formulate the scheduling problem as an optimization problem.We devise various online and offline algorithms to arrive at a good ordering of jobs to minimize the overall job completion times. Since optimal solutions are hard to compute (NP-hard), we propose approximation algorithms that work within a factor of 3 of the optimal. Using simulations, we also compare our online algorithm with standard scheduling strategies such as FIFO, Shortest Job First and show that our algorithm consistently outperforms these across different job distributions.

Behavioral targeting of content to users is a huge and lucrative business, valued as a $20 billion industry that is growing rapidly. So far, the dominant players in this field like Google and Yahoo! examine the user requests coming to their servers and place appropriate ads based on the user's search keywords. Triple-play service providers have access to all the traffic generated by the users and can generate more comprehensive profiles of users based on their TV, broadband, and mobile usage. Using such multisource profile information, they can generate new revenue streams by smart targeting of ads to their users over multiple screens (computer, TV, and mobile handset). This paper proposes methods to place targeted ads to a TV based on user's interests. It proposes an ad auction model that can leverage multisource profile and can handle dynamic profile-based targeting like Google's AdWords vis-à-vis static demography-based targeting of legacy TV. We then present a 0.502-competitive revenue maximizing scheduling algorithm that chooses a set of ads in each time slot and assigns users to one of these selected ads.

Behavioral targeting of content to users is a huge and lucrative business, valued as a $20 billion industry that is growing rapidly. So far dominant players in this field like Google and Yahoo examine the user requests coming to their servers and place appropriate ads based on the user's search keywords. Triple play service providers have access to all the traffic generated by the users and can generate more comprehensive profiles of users based on their TV, broadband and mobile usage. Using such multi-source profile information they can generate new revenue streams by smart targeting of ads to their users over multiple screens (computer, TV and mobile handset). This paper proposes methods to place targeted ads to a TV based on user's interests. It proposes an ad auction model that can leverage multi-source profile and can handle dynamic profile-based targeting like Google's AdWords vis-a-vis static demography-based targeting of legacy TV. We then propose a 0.502-competitive revenue maximizing scheduling algorithm that chooses a set of ads in each time slot and assigns users to one of these selected ads.

In current CDMA2000 standard, a packet data serving node (PDSN) acts as an IP gateway to the Internet. Mobile nodes (MN) connect to a PDSN using a point-to-point (PPP) session and IP packets are tunneled over the PPP session from the client to the PDSN which then routes the packets onto a packet network. A CDMA2000 network is a hierarchical network where packets from an MN to the PDSN are transported over a radio-access network (RAN). An MN could move from one RAN to another and still be anchored under the same PDSN; it is also possible that when an MN moves from one RAN to another, the anchor PDSN itself becomes different. In the latter case, there are two ways to handle mobility: (i) tear down the PPP session from the MN to the old PDSN and establish a new PPP session from the MN to the new PDSN, and (ii) use the fast-handoff mechanism as specified in the CDMA2000 standard where a P-P (PDSN to PDSN) tunnel is established to tunnel PPP frames from the old PDSN to the new PDSN and then to the MN. In this paper, we present a better approach to handling mobility than either of the above two techniques. The method is to migrate the PPP state from the old PDSN to the new PDSN transparent to the MN; once the PPP state migration is completed, the new PDSN will serve as the IP gateway to the MN. We have implemented the PPP migration technique and through experimental measurements show its benefits.

Multicast delivery is an efficient approach to the provision of a video-on-demand (VoD) service. Interacting with the video stream is a desirable feature for users. However, it is a challenging task to provide the functionality in the multicast environment because a lot of users share multicast delivery channels. In this paper, we propose an active buffer management technique to provide interactive functions in broadcast VoD systems. In our scheme, the client can selectively prefetch segments from broadcast channels based on the observation of the play point in its local buffer. The content of the buffer is adjusted in such a way that the relative position of the play point is kept in the middle part of the buffer. Our simulations show that the active buffer management scheme can implement interactive actions through buffering with a high probability in a wide range of user interaction levels.

A virtual private network (VPN) is an overlay network that uses the public network to carry data traffic between corporate sites and users, maintaining privacy through the use of tunnelling protocols and security procedures. In the network-based model, VPN-aware network elements are placed within the network to set up concatenated tunnels between the user/site and enterprise resources to offer intranet VPN and remote access VPN. This paper identifies the important differences between a traditional VPN and the mobile VPN and proposes a hierarchical network architecture to efficiently realize network-based mobile VPNs. We address the problem of optimally provisioning VPN-aware devices, called IP service gateways (IPSGs), in the hierarchical network architecture for mobile VPNs, while taking into account of (1) the cost of links over which VPN tunnels are established, (2) the cost of provisioning a VPN customer on an IPSG, and (3) redundancy in IPSG provisioning for fault tolerance. We develop generic yet powerful problem formulations for different scenarios described above while considering practical requirements of the network elements and business requirements of the VPN service provider. The formulation becomes a set of integer programming problems. We solve several instances of the problem for a few practical cases and discuss their applications in the overall network design.

In a CDMA2000 network, a mobile node (MN) gets packet data service by establishing a PPP session with a packet data serving node (PDSN). The PDSN acts as the muter for the IP packets transported over the PPP session. A packet control function (PCF) sits between the radio access network and the packet network, selects the PDSN for the MN during session setup, and relays the PPP frames between the MN and the PDSN during the session. The PCF selects a PDSN based on the MN's device identity. Due to this, the data services that a mobile user subscribes become tightly coupled with the device that the user registers with the service provider. Because the PCF selects a PDSN based only on mobile device identity, it is unable to select the "best" PDSN to support the services subscribed by a specific user. This work presents the design and implementation of an entity called radio-packet session redirector (RPSR) that works within the current standard and alleviates this shortcoming. The RPSR intercepts a PPP session, parses the user identity, selects a PDSN based on the user identity, creates a PPP session with the selected PDSN and splices the sessions together so that PPP frames can be seamlessly forwarded between the MN and the PDSN with very little overhead. We identify a number of services that RPSR enables in the network. We describe a prototype stand-alone device implementation of the RPSR in the Linux kernel and present performance results.

With the popularity of services like push-to-talk, the need for "always on" services is becoming important for service providers. The paper addresses the problem of supporting always on services in existing and new network architectures. It defines the requirements of always on service, identifies the problems in supporting such a service, and proposes an overlay network based solution to make always on service a reality. Some results from initial prototyping and experimentation are also presented to demonstrate the feasibility of deploying such services.

Recent observations through experiments that we have performed in current third generation wireless networks have revealed that the achieved throughput over wireless links varies widely depending on the application. In particular, the throughput achieved by file transfer application (FTP) and web browsing application (HTTP) are quite different. The throughput achieved over a HTTP session is much lower than that achieved over an FTP session. The reason for the lower HTTP throughput is that the HTTP protocol is affected by the large Round-Trip Time (RTT) across Wireless links. HTTP transfers require multiple TCP connections and DNS lookups before a HTTP page can be displayed. Each TCP connection requires several RTTs to fully open the TCP send window and each DNS lookup requires several RTTs before resolving the domain name to IP mapping. These TCP/DNS RTTs significantly degrade the performance of HTTP over wireless links. To overcome these problems, we have developed session level optimization techniques to enhance HTTP download mechanisms. These techniques (a) minimize the number of DNS lookups over the wireless link and (b) minimize the number of TCP connections opened by the browser. These optimizations bridge the mismatch caused by wireless links between application-level protocols (such as HTTP) and transportlevel protocols (such as TCP). Our solutions do not require any client-side software and can be deployed transparently on a service provider network to provide 30 50% decrease in end-to-end user perceived latency and 50-100% increase in data throughput across wireless links for HTTP sessions.

Repository for continuous media data differs from that of the traditional text-based data both in storage space and streaming bandwidth requirements. The file systems used for continuous media streams need to support large volumes and high bandwidth. We propose a scalable distributed continuous media file system built using autonomous disks. Autonomous disks are attached directly to the network and are able to perform lightweight processing. We discuss different ways to realize the autonomous disk, and describe a prototype implementation on a Linux platform using PC-based hardware. We present the basic requirements of the continuous media file system and present the design methodology and a prototype Linux-based implementation of the distributed file system that supports the requirements. We present experimental results on the performance of the proposed file system prototyped using autonomous disks. We show that the performance of the file system scales linearly with the number of disks and the number of clients. The file system performs much superior to NFS running on the same hardware platform and can deliver higher raw disk bandwidth to the applications. We also present bandwidth and time sensitive read/write procedures for the file system and show that the file system can provide strict bandwidth guarantees for continuous media streams.

With the proliferation of network attached appliances and inexpensive computing devices there is an increasing demand for inter-networking among these devices in the home, in small offices or even on an ad-hoc basis. While administration may be necessary in today's large complex IP networks, it is unacceptable for emerging networks such as home networks, i.e., networking of consumer electronic devices such as TV, VCR, phone, fax, printer, PC, etc., small office home office (SOHO) networks, automobile networks, airplane networks, ad-hoc networks at conferences, emergency relief stations, and many others. These networks require zero manual administration and configuration. This demand recently initiated a new paradigm of IT networking called zero-configuration (zeroconf) networking. Zeroconf networks are a class of IP networks that do not require any manual configuration or administration. In this paper we examine name-to-address translation in zeroconf networks. We suggest requirements for name-to-address translation algorithms, review the existing solutions, extend these solutions, and show that the proposed solutions satisfy the suggested requirements.

IP hosts and network infrastructure have historically been difficult to configure, requiring network services such as DHCP and DNS servers, and relying on highly trained network administrators. This need for administration has prevented IP networks from being used in many environments such as in homes, in small businesses, in impromptu networks established at conferences, construction sites, emergency relief stations, etc. With the proliferation of IP-enabled network-attached appliances and inexpensive computing devices, the demand to enable plug-and-play, easy-to-use IP networking has increased. This demand has initiated a new paradigm of IP networking called zero configuration, or zeroconf, networking. The goal is to develop a set of zeroconf configuration protocols to enable IP networking without manual configuration or administration. Such IP networks are called zeroconf networks. We examine IP address configuration in zeroconf networks involving two network topologies: (1) A routerless network, which consists of several hosts attached to a segment having no router, (2) A single-router network, which consists of a router joining several segments together into a star-shaped topology. We suggest the requirements for IP address configuration, review the existing solutions, and propose new algorithms to address their deficiencies. Finally, we present a comparison of our algorithms to existing solutions and describe when a particular configuration method should be used.

Zero-configuration (zeroconf) networks are a particular class of IP networks that do not require any user administration for correct operation. IP address configuration in zeroconf networks is an important problem. While there are a few proposals for IP host configuration, a general solution for IP router configuration, an important problem in multi-router zeroconf networks, does not yet exist. In a single-router zeroconf network, the router can easily configure by creating unique IP subnets over each of its directly attached segments. But when several such self-configuring routers are interconnected together to form a multi-router network, there is a need for (1) dynamic exchange of routing information among the routers and (2) consistent assignment of IP subnets in the network, i.e., an IP subnet can not be assigned to different segments. As new routers are added to the zeroconf network, any IP subnet conflicts must be detected and resolved. No solutions for IP address auto-configuration of multi-router networks exist. This paper suggests the requirements for IP address configuration of multi-router zeroconf networks, and proposes IP host and router configuration algorithms to satisfy these requirements. Among the proposed algorithms is a novel routing algorithm designed by augmenting the basic distance vector routing algorithm that can solve both the problem of dynamic routing and consistent IP subnet assignment in multi-router zeroconf networks. We also show how the popular routing information protocol (RIP) can be augmented to implement the proposed routing algorithm, called the zeroconf routing information protocol (ZRIP).

Secure one-to-many multicasting has been a popular research area in the past. Secure many-to-many multicasting is becoming popular with applications such as private conferencing and distributed interactive simulation. Most of the existing secure multicasting protocols use a centralized group manager to enforce access control and for key distribution. In the presence of multiple senders it is desirable to delegate group management responsibility to all the senders. We propose a distributed group key management scheme to support secure many-to-many communication. We divide key distribution overhead evenly among the senders. Our protocol is scalable and places equal trust in all the senders.

Repositories for multimedia data differ from those for traditional text-based data both in terms of storage space and streaming bandwidth requirements. The file systems used in the multimedia environment need to support large volumes and high bandwidth. In this paper, we propose a novel scalable distributed file system built using autonomous disks. Autonomous disks are attached directly to the network and are able to perform lightweight processing. We discuss different ways to realize an autonomous disk, and describe a prototype implementation on a Linux platform using PC-based hardware. We present the design methodology and a prototype Linux-based implementation of the distributed file system that supports such disks. We detail experimental results on the performance of the proposed file system prototyped using autonomous disks. We show that the performance of the file system scales linearly with the number of disks and the number of clients. The file system's performance is much superior to NFS running on the same hardware platform, and it can deliver higher raw disk bandwidth to the applications. We also show that the file system can provide strict bandwidth guarantees for multimedia streams.

A novel quality of service (QoS) scheduling mechanism suitable for transporting variable bit rate video in the upstream direction over a DOCSIS (data over cable system interface specification)-compliant cable network is presented. It is shown, via simulation using real life video traces, that the proposed scheduling service provides significant improvements as compared to the existing DOCSIS QoS scheduling services, with regard to bandwidth utilization and latency distribution. The proposed scheduling service is also applicable to transport integrated services over the Internet and can be utilized by other emerging multimedia applications, where data are bursty in nature and variable in bit rate.

The differentiated services (DiffServ) model, proposed to evolve the current best-effort Internet to a quality-of-service-aware Internet, provides packet level service differentiation on a per-hop basis. The end-to-end service differentiation may be provided by extending the per-hop behavior over multiple network domains through service level agreements between domains. The edge routers of each of the domains monitor the aggregate flow of the incoming packets and demote packets when the aggregate incoming traffic exceeds the negotiated interdomain service agreement. A demoted packet may encounter other edge routers on its path that have sufficient resources to route the packet with its original marking. In this paper, we propose a random early demotion and promotion (REDP) technique that works at the aggregate traffic level and allows (1) fair demotion of packets belonging to different flows, and (2) easy and fair detection and promotion of the demoted packets. Using early and random decisions on packets REDP ensures fairness in promotion and demotion. It uses a three color marking mechanism, reserving one color fur differentiating between a demoted packet and a packet with the original out-of-profile marking. We experiment with the proposed REDP scheme using the ns2 simulator for both TCP and UDP streams. The results demonstrate the fairness of REDP scheme in demoting and promoting packets. Furthermore, we show a variety of results that demonstrates that REDP provides better assured services compared to the previously proposed RIO scheme with or without the provision of promotion.

We propose a dual encryption protocol for scalable secure multicasting. Multicasting is a scalable solution for group communication. It however poses several unique security problems. We use hierarchical subgrouping to achieve scalability. Third-party hosts or members of the multicast group are designated as subgroup managers. They are responsible for secret key distribution and group membership management at the subgroup level. Unlike existing secure multicast protocols, our protocol need not trust the subgroup managers with the distribution of data encryption keys. The dual encryption protocol proposed in this paper distributes encrypted data encryption keys via subgroup managers. We also present a classification of the existing secure multicast protocols, compare their relative merits and show the advantages of our protocol.

Real-time active database systems (RTADB) have attracted the attention of researchers in recent times. Such systems are envisioned as control systems for environments as diverse as process control, network management and automated financial trading. Sensors distributed throughout the system report the state of the system to the database. Unacceptable state reports typically results in corrective actions being triggered with deadlines. Thus RTADB's incorporate both real-time as well as active characteristics. We study buffer management in RTADB. Buffer management is recognized as not being a well studied area in real-time systems. As a result of our work, we postulate PAPER, a new buffer management scheme that relies on two strategies: prefetching and priority based buffer replacement. We report the result of studies of the performance of PAPER, as compared to that of existing buffer management algorithms. The insights derived from this paper impact both real-time database systems as well as real-time, active database systems.

A new service class, called VBR/sup +/ has been proposed for multimedia applications on ATM networks. VBR/sup +/ extends the functionality of the traditional VBR service with the added capability of dynamic resource renegotiation. It makes the specification and modification of the usage parameter controls flexible, and potentially can increase the network resource utilization through statistical multiplexing. These advantages come at the expense of a more complex connection admission controller which should be designed to handle bandwidth renegotiation efficiently. A connection admission controller for the VBR/sup +/ service class is proposed. We identify the desirable features of a VBR/sup +/ connection admission controller, and present a novel one that can achieve them through (1) dynamic resource partitioning, and (2) dynamic resource redistribution among active connections. Simulation results showing the performance of the controller using a number of actual video traces are presented. The results show that the controller is robust in admitting a variety of video sources with widely different traffic burstiness. By partitioning the resource pool dynamically, and distributing resources among contending connections fairly, it can maintain very good quality, and can achieve high utilization. Comparison with the traditional VBR service reveals that the CAC is able to provide comparable quality with higher network utilization.

We propose a simple mechanism named carry-over round robin (CORR) for scheduling cells in asynchronous transfer mode networks. We quantify the operational complexity of CORR scheduling and show that it is comparable to that of a simple round-robin scheduler. We then show that, albeit its simplicity, CORR is very competitive with much more sophisticated and significantly more complex scheduling disciplines in terms of performance. We evaluate the performance of CORR using both analysis and simulation, We derive analytical bounds on the worst case end-to-end delay achieved by a CORR scheduler for different traffic arrival patterns. Using traffic traces from MPEG video streams, we compare the delay performance of CORR with that of packet-by-packet generalized processor sharing (PGPS) and stop-and-go (SG). Our results show that, in terms of delay performance, CORR compares favorably with both PGPS and SG. We also analyze the fairness properties of CORR and show that it achieves near perfect fairness.

One of the major attractions of asynchronous transfer mode (ATM) networks for transporting bursty video traffic is its ability to exploit the multiplexing gains of packet switching while providing quality of service guarantees. Unfortunately, most of the multiplexing mechanisms proposed in the literature fail to exploit the multiplexing gains of ATM. We propose a multirate service mechanism that allows a session to be served at different rates at different times. Applications generating bursty data, such as variable bit-rate (VBR) video, can take advantage of multirate service by requesting a high rate of service for brief periods of bursty arrivals and a much lower rate of service for all other times. Consequently, the applications can improve their delay performance without reserving a high bandwidth for the entire duration of the sessions. Furthermore, the scheduler can multiplex the peaks and the lulls in service rates of different sessions and improve the utilization of the system. Using MPEG video traces from a number of applications, we show that multirate servers outperform single-rate PGPS (packet-by-packet generalized processor sharing) servers and CBR (constant bit-rate) servers in terms of number of connections admitted, while providing the same level of service guarantees. We also investigate the performance of multirate service when service quality need not be guaranteed. We refer to this as predictive service. We propose a measurement-based admission control procedure for predictive service, and show that it helps increase the size of the admissible region even further.

We propose a work-conserving scheduling mechanism for providing deterministic performance guarantees in ATM networks. The most attractive feature of the proposed mechanism, which we call carry-over round robin (CORR), is its simplicity. It is an extension of weighted round robin scheduling. We have derived closed form bounds for worst case end-to-end delay when CORR is used in conjunction with the composite leaky bucket, and moving window regulators. Our results show that albeit its simplicity, CORR is very competitive with some of the more complex scheduling disciplines such as packet-by-packet generalised processor sharing and stop-and-go queueing.

We propose a multirate service mechanism that allows a network session to be served at different rates at different times. Applications generating bursty data, such as VBR video, can take advantage of multirate service by requesting a high rate of service for brief periods of bursty arrivals and a lower rate of service at other times. Consequently, an application can improve its delay performance without reserving high bandwidth for the entire duration of a session. Using MPEG video traces from a number of applications, we show that a multirate server outperforms single rate PGPS (packet-by-packet generalized processor sharing) servers in terms of number of connections admitted, while providing the same level of service guarantees. We also investigate the performance of multirate service when service quality need not be guaranteed. We refer to this as predictive service. We show that multirate servers are superior to single rate servers in providing predictive services.

This paper proposes a traffic control scheme for integrated services ATM networks. The control strategy comprises of two components: a shaping mechanism at the network entry point and a frame based service discipline at the switches. The shaper enforces a short term peak rate, and a long term average rate. The multiplexing scheme at a switch allocates a guaranteed bandwidth to a connection. A connection may get more than the guaranteed amount, up to a connection specific maximum, if slack bandwidth is available. By imposing an upper bound on the allocated bandwidth, we secure a better handle on the delay jitter. Unlike most frame-based schemes, our scheme allows allocation of bandwidth at any arbitrary granularity. We suggest a simple admission control policy and derive deterministic bounds on end-to-end delay and jitter. An outline of a hardware realization of the scheme is also presented.>

This paper addresses the problem of guaranteed delivery of messages with hard deadlines in a DQDB network. The authors present a cyclic reservation scheme capable of allocating bandwidth with any arbitrary granularity and provide deterministic delay guarantees. They propose two implementations of the allocation scheme within the framework of DQDB medium access control protocol. The proposed implementations are very simple, incur minimal overhead and require only minor changes in the adopted standard.>

We study the problem of transmitting time constrained synchronous messages in a slotted ring based local area network, carrying synchronous and asynchronous traffic. A bandwidth allocation scheme for synchronous messages is developed on top of a media access control protocol that assigns preemptive priority to synchronous traffic over asynchronous traffic. We derive sufficient conditions for schedulability of time critical synchronous messages and show that the scheme achieves high levels of schedulable utilization. A slot access protocol is proposed for synchronous streams that implements the allocation scheme with minimal additional overhead and loss of schedulable utilization. The protocol is distributed in the sense that any node can locally determine if it can use a slot, without exchanging any explicit messages with other nodes.>

A protocol for a slotted-ring local area network to handle two classes of jobs in which one class has preemptive priority over the other is presented. The detailed response time distribution analysis for different classes of jobs is given. It is shown that the modeling and analysis can be extended to multiclass jobs.>