In the context of streaming dataflow queries, the task placement problem aims to identify a mapping of operator tasks to physical resources in a distributed cluster. We show that task placement not only significantly affects query performance but also the convergence and accuracy of auto-scaling controllers. We propose CAPSys, an adaptive resource controller for dataflow stream processors, that considers auto-scaling and task placement in concert. CAPSys relies on Contention-Aware Placement Search (CAPS), a new placement strategy that ensures compute-intensive, I/O-intensive, and networkintensive tasks are balanced across available resources.

Due to the increasing complexity of cloud architectures, automatically tracking and inspecting container packages in Platform-as-a-Service (PaaS) clusters are challenging tasks. This introspection capability, however, is critical to identify vulnerable packages and compile an accurate Software Bill of Materials (SBOM). Motivated by introspection frameworks focusing on virtual machine (VM) settings and ML methods for software discovery, we design PraxiPaaS as a framework to inspect PaaS container images with a highly scalable ML inference pipeline by scanning file changes during package installations. Our ML pipeline includes a structured collection of word2vec encoders and a corresponding structured ML model to achieve short incremental training time for incorporating additional packages while maintaining a high F1-score in generating the SBOM. Our evaluation shows that our structured ML pipeline provides an exponential drop in incremental training time from 2.8 hours to $8.6 \mathbf{s}$ with 32 CPU cores, while maintaining an F1-score of 0.82, compared to the traditional monolithic model design. We deploy a prototype of PraxiPaaS in the New England Research Cloud (NERC) OpenShift cluster and evaluate the inference time comparing structured versus monolithic model design.

We explore the problem of scheduling in a distributed multi-cloud serverless scenario, in the case where requests to function instances contend over the same resources. For this case, we present an efficient scheduling algorithm that leverages function profiling to detect resource contention, and improves the response time of requests, as well as the overall completion time of all requests. We compare our work to other schedulers such as a simple random scheduler, a simple round-robin scheduler, and schedulers that either load balance requests for each function across clouds, choose the cloud with the best profile, or select the cloud with the most available resources. Besides simulations, we have created a simple experiment of our scheduler running against two OpenWhisk serverless instances over the FABRIC testbed. We show that our inverse response time ratio scheduling algorithm can yield an improvement in average response time of around 32% over the best of the other schedulers when the execution time of a function on a given cloud is twice as much as on another. We also show that the improvement increases as the dispersion of the execution time across the distributed environment increases.

Every day, large amounts of sensitive data are distributed across mobile phones, wearable devices, and other sensors. Traditionally, these enormous datasets have been processed on a single system, with complex models being trained to make valuable predictions. Distributed machine learning techniques such as Federated and Split Learning have recently been developed to protect user data and privacy better while ensuring high performance. Both of these distributed learning architectures have advantages and disadvantages. In this article, we examine these tradeoffs and suggest a new hybrid Federated Split Learning architecture that combines the efficiency and privacy benefits of both. Our evaluation demonstrates how our hybrid Federated Split Learning approach can lower the amount of processing power required by each client running a distributed learning system, and reduce training and inference time while keeping a similar accuracy. We also discuss the resiliency of our approach to deep learning privacy inference attacks and compare our solution to other recently proposed benchmarks.

In the last decade, serverless computing emerged as a new compelling paradigm for the deployment of cloud applications and services. It represents an evolution of cloud computing with a simplified programming model, that aims to abstract away most operational concerns. Running serverless applications requires users to configure multiple parameters, such as memory, CPU, cloud provider,etc. While relatively simpler, configuring such parameters correctly while minimizing cost and meeting delay constraints is not trivial. In this paper, we present COSE, a framework that uses Bayesian Optimization to find the optimal resource configuration and placement for functions in a serverless application. COSE uses statistical learning techniques to intelligently collect samples and predict the cost and execution time of a serverless function across unseen configuration values. Our framework uses the predicted cost and execution time on available locations to select the “best” configuration parameters and placement for running a serverless application while satisfying customer objectives. We evaluate COSE on AWS Lambda with real-world applications consisting of multiple functions (both linear chains and service graphs), where we successfully found optimal/near-optimal configurations. We also evaluate COSE over a wide range of simulated distributed cloud environments that confirm the efficacy of our approach.

Mobile phones, wearable devices, and other sensors produce every day a large amount of distributed and sensitive data. Classical machine learning approaches process these large datasets usually on a single machine, training complex models to obtain useful predictions. To better preserve user and data privacy and at the same time guarantee high performance, distributed machine learning techniques such as Federated and Split Learning have been recently proposed. Both of these distributed learning architectures have merits but also drawbacks. In this work, we analyze such tradeoffs and propose a new hybrid Federated Split Learning architecture, to combine the benefits of both in terms of efficiency and privacy. Our evaluation shows how Federated Split Learning may reduce the computational power required for each client running a Federated Learning and enable Split Learning parallelization while maintaining a high prediction accuracy with unbalanced datasets during training. Furthermore, FSL provides a better accuracy-privacy tradeoff in specific privacy approaches compared to Parallel Split Learning.

Function-as-a-Service (FaaS) has recently emerged to reduce the deployment cost of running cloud applications compared to Infrastructure-as-a-Service (IaaS). FaaS follows a serverless “pay-as-you-go” computing model; it comes at a higher cost per unit of execution time but typically application functions experience lower provisioning time (startup delay). IaaS requires the provisioning of Virtual Machines, which typically suffer from longer cold-start delays that cause higher queuing delays and higher request drop rates. We present LIBRA, a balanced (hybrid) approach that leverages both VM-based and serverless resources to efficiently manage cloud resources for the applications. LIBRA closely monitors the application demand and provisions appropriate VM and serverless resources such that the running cost is minimized and Service-Level Agreements are met. Unlike state of the art, LIBRA not only hides VM cold-start delays, and hence reduces response time, by leveraging serverless, but also directs a low-rate bursty portion of the demand to serverless where it would be less costly than spinning up new VMs. We evaluate LIBRA on real traces in a simulated environment as well as on the AWS commercial cloud. Our results show that LIBRA outperforms other resource-provisioning policies, including a recent hybrid approach - LIBRA achieves more than 85% reduction in SLA violations and up to 53% cost savings.

Next-generation networks are expected to provide higher data rates and ultra-low latency in support of demanding applications, such as virtual and augmented reality, robots and drones, etc. To meet these stringent requirements of applications, edge computing constitutes a central piece of the solution architecture wherein functional components of an application can be deployed over the edge network to reduce bandwidth demand over the core network while providing ultra-low latency communication to users. In this article, we provide solutions to resource orchestration and management for applications over a virtualized client-edge-server infrastructure. We investigate the problem of optimal placement of pipelines of application functions (virtual service chains) and the steering of traffic through them, over a multi-technology edge network model consisting of both wired and wireless millimeter-wave (mmWave) links. This problem is NP-hard. We provide a comprehensive “microscopic” binary integer program to model the system, along with a heuristic that is one order of magnitude faster than optimally solving the problem. Extensive evaluations demonstrate the benefits of orchestrating virtual service chains (by distributing them over the edge network) compared to a baseline “middlebox” approach in terms of overall admissible virtual capacity. Moreover, we observe significant gains when deploying a small number of mmWave links that complement the Wire physical infrastructure in high node density networks.

Distributed learning systems are increasingly being adopted for a variety of applications as centralized training becomes unfeasible. A few architectures have emerged to divide and conquer the computational load, or to run privacy-aware deep learning models, using split or federated learning. Each architecture has benefits and drawbacks. In this work, we compare the efficiency and privacy performance of two distributed learning architectures that combine the principles of split and federated learning, trying to get the best of both. In particular, our design goal is to reduce the computational power required by each client in Federated Learning and to parallelize Split Learning. We share some initial lessons learned from our implementation that leverages the PySyft and PyGrid libraries.

Serverless computing has emerged as a new compelling paradigm for the deployment of applications and services. It represents an evolution of cloud computing with a simplified programming model, that aims to abstract away most operational concerns. Running serverless functions requires users to configure multiple parameters, such as memory, CPU, cloud provider, etc. While relatively simpler, configuring such parameters correctly while minimizing cost and meeting delay constraints is not trivial. In this paper, we present COSE, a framework that uses Bayesian Optimization to find the optimal configuration for serverless functions. COSE uses statistical learning techniques to intelligently collect samples and predict the cost and execution time of a serverless function across unseen configuration values. Our framework uses the predicted cost and execution time, to select the "best" configuration parameters for running a single or a chain of functions, while satisfying customer objectives. In addition, COSE has the ability to adapt to changes in the execution time of a serverless function. We evaluate COSE not only on a commercial cloud provider, where we successfully found optimal/near-optimal configurations in as few as five samples, but also over a wide range of simulated distributed cloud environments that confirm the efficacy of our approach.

Vehicles such as cars are expected to use communication technologies for retrieving different kinds of information and exchanging information with other vehicles for safety and infotainment purposes. This results in vehicular networks, where vehicles can connect to other vehicles or communication infrastructures such as Road Side Units. The Recursive Inter- Network Architecture (RINA) has been proposed as a Future Internet architecture. This paper investigates and analyses how vehicular networks can be supported by RINA and how a RINA based vehicular network architecture can be designed to support efficient management of mobile vehicles.

Autonomic communications aim to provide the quality-of-service in networks using self-management mechanisms. It inherits many characteristics from autonomic computing, in particular, when communication systems are running as specialized applications in software-defined networking (SDN) and network function virtualization (NFV)-enabled cloud environments. This paper surveys autonomic computing and communications in the context of software-driven networks, i.e., networks based on SDN/NFV concepts. Autonomic communications create new challenges in terms of security, operations, and business support. We discuss several goals, research challenges, and development issues on self-management mechanisms and architectures in software-driven networks. This paper covers multiple perspectives of autonomic communications in software-driven networks, such as automatic testing, integration, and deployment of network functions. We also focus on self-management and optimization, which make use of machine learning techniques.

The Network Innovators Community Event (GENI NICE) is the premier event for researchers to demonstrate and present research results and to discuss work in progress related to the NSF's Global Environment for Network Innovations (GENI) and related advanced cyberinfrastructure testbeds.

Control theory and SDN (Software Defined Networking) are key components for NFV (Network Function Virtualization) deployment. However little has been done to use a control-theoretic approach for SDN and NFV management. In this demo, we describe a use case for NFV management using control theory and SDN. We use the management architecture of RINA (a clean-slate Recursive InterNetwork Architecture) to manage Virtual Network Function (VNF) instances over the GENI testbed. We deploy Snort, an Intrusion Detection System (IDS) as the VNF. Our network topology has source and destination hosts, multiple IDSes, an Open vSwitch (OVS) and an OpenFlow controller. A distributed management application running on RINA measures the state of the VNF instances and communicates this information to a Proportional Integral (PI) controller, which then provides load balancing information to the OpenFlow controller. The latter controller in turn updates traffic flow forwarding rules on the OVS switch, thus balancing load across the VNF instances. This demo demonstrates the benefits of using such a control-theoretic load balancing approach and the RINA management architecture in virtualized environments for NFV management. It also illustrates that the GENI testbed can easily support a wide range of SDN and NFV related experiments.

Control theory and SDN (Software Defined Networking) are key components for NFV (Network Function Virtualization) deployment. However little has been done to use a control-theoretic approach for SDN and NFV management. In this paper, we describe a use case for NFV management using control theory and SDN. We use the management architecture of RINA (a clean-slate Recursive InterNetwork Architecture) to manage Virtual Network Function (VNF) instances over the GENI testbed. We deploy Snort, an Intrusion Detection System (IDS) as the VNF. Our network topology has source and destination hosts, multiple IDSes, an Open vSwitch (OVS) and an OpenFlow controller. A distributed management application running on RINA measures the state of the VNF instances and communicates this information to a Proportional Integral (PI) controller, which then provides load balancing information to the OpenFlow controller. The latter controller in turn updates traffic flow forwarding rules on the OVS switch, thus balancing load across the VNF instances. This paper demonstrates the benefits of using such a control-theoretic load balancing approach and the RINA management architecture in virtualized environments for NFV management. It also illustrates that GENI can easily support a wide range of SDN and NFV related experiments.

Traditional network management is tied to the TCP/IP architecture, thus it inherits its many limitations. Additionally there is no unified framework for application management, and service providers have to rely on their own ad-hoc mechanisms to manage their application services. The Recursive InterNetwork Architecture (RINA) is our solution to achieve better network management. RINA provides a unified framework for application-driven network management along with built-in mechanisms. It allows the dynamic formation of secure communication containers for service providers in support of various requirements. In this paper, we focus on how application-driven network management can be achieved over the GENI testbed using ProtoRINA, a user-space prototype of RINA. We use video multicast as an example, and experimental results show that application-driven network management enabled by ProtoRINA can achieve better network and application performance.

To provide wide-area network services, resources from different infrastructure providers are needed. Leveraging the consensus-based resource allocation literature, we propose a general distributed auction mechanism for the (NP-hard) virtual network (VNET) embedding problem. Under reasonable assumptions on the bidding scheme, the proposed mechanism is proven to converge, and it is shown that the solutions guarantee a worst-case efficiency of (1-(1/e)) relative to the optimal node embedding, or VNET embedding if virtual links are mapped to exactly one physical link. This bound is optimal, that is, no better polynomial-time approximation algorithm exists, unless P=NP. Using extensive simulations, we confirm superior convergence properties and resource utilization when compared to existing distributed VNET embedding solutions, and we show how by appropriate policy design, our mechanism can be instantiated to accommodate the embedding goals of different service and infrastructure providers, resulting in an attractive and flexible resource allocation solution.

Network virtualization has enabled new business models by allowing infrastructure providers to lease or share their physical network. A fundamental management problem that cloud providers face to support customized virtual network (VN) services is the virtual network embedding. This requires solving the (NP-hard) problem of matching constrained virtual networks onto the physical network. In this paper we present VINEA, a policy-based virtual network embedding architecture, and its system implementation. VINEA leverages our previous results on VN embedding optimality and convergence guarantees, and it is based on a network utility maximization approach that separates policies (i.e., high-level goals) from underlying embedding mechanisms: resource discovery, virtual network mapping, and allocation on the physical infrastructure. We show how VINEA can subsume existing embedding approaches, and how it can be used to design novel solutions that adapt to different scenarios, by merely instantiating different policies. We describe the VINEA architecture, as well as our object model: our VINO protocol and the API to program the embedding policies; we then analyze key representative tradeoffs among novel and existing VN embedding policy configurations, via event-driven simulations, and with our prototype implementation. Among our findings, our evaluation shows how, in contrast to existing solutions, simultaneously embedding nodes and links may lead to lower providers' revenue. We release our implementation on a testbed that uses a Linux system architecture to reserve virtual node and link capacities. Our prototype can be also used to augment existing open-source “Networking as a Service” architectures such as OpenStack Neutron, that currently lacks a VN embedding protocol, and as a policy-programmable solution to the “slice stitching” problem within wide-area virtual network testbeds.

Abstract—Making the network programmable simplifies net-work management and enables network innovations. The Recur-sive InterNetwork Architecture (RINA) is our solution to enable network programmability. ProtoRINA is a user-space prototype of RINA and provides users with a framework with common mechanisms so a user can program recursive-networking policies without implementing mechanisms from scratch. In this paper, we focus on how routing policies, which is an important aspect of network management, can be programmed using ProtoRINA, and demonstrate how ProtoRINA can be used to achieve better performance for a video streaming application by instantiating different routing policies over the GENI (Global Environment for Network Innovations) testbed, which provides a large-scale experimental facility for networking research. I.

Computer networks are becoming increasingly complex and difficult to manage. The research community has been expending a lot of efforts to come up with a general management paradigm that is able to hide the details of the physical infrastructure and enable flexible network management. Software Defined Networking (SDN) is such a paradigm that simplifies network management and enables network innovations. In this survey paper, by reviewing existing SDN management layers (platforms), we identify the general common management architecture for SDN networks, and further identify the design requirements of the management layer that is at the core of the architecture. We also point out open issues and weaknesses of existing SDN management layers. We conclude with a promising future direction for improving the SDN management layer.

The TCP/IP architecture was originally designed without taking security measures into consideration. Over the years, it has been subjected to many attacks, which has led to many patches to counter them. Our investigations into the fundamental principles of networking have shown that carefully following an abstract model of Inter-Process Communication (IPC) addresses many problems [1]. Guided by this IPC principle, we designed a clean-slate Recursive InterNetwork Architecture (RINA) [2]. In this paper, we show how, without the aid of cryptographic techniques, the bare-bones architecture of RINA can resist most of the security attacks faced by TCP/IP, and of course, is only more secure if cryptographic techniques are employed. Specifically, the RINA model decouples different concerns that makes it more resistant to transport-level attacks: (1) RINA decouples authentication from connection management, thus transport-level attacks are limited to “insider” attacks, and (2) RINA decouples transport port allocation and access control from data synchronization and transfer, thus making transport-level attacks much harder to mount. Using typical field lengths in packet headers, we analyze how hard it is for an intruder to compromise RINA.

Computer systems are increasingly driven by workloads that reflect large-scale social behavior, such as rapid changes in the popularity of media items like videos. Capacity planners and system designers must plan for rapid, massive changes in workloads when such social behavior is a factor. In this paper we make two contributions intended to assist in the design and provisioning of such systems.We analyze an extensive dataset consisting of the daily access counts of hundreds of thousands of YouTube videos. In this dataset, we find that there are two types of videos: those that show rapid changes in popularity, and those that are consistently popular over long time periods. We call these two types rarely-accessed and frequently-accessed videos, respectively. We observe that most of the videos in our data set clearly fall in one of these two types. In this work, we study the frequently-accessed videos by asking two questions: first, is there a relatively simple model that can describe its daily access patterns? And second, can we use this simple model to predict the number of accesses that a video will have in the near future, as a tool for capacity planning? To answer these questions we develop a framework for characterization and forecasting of access patterns. We show that for frequently-accessed videos, daily access patterns can be extracted via principal component analysis, and used efficiently for forecasting.

Mobility models have traditionally been tailored to specific application domains such as human, military, or ad hoc transportation scenarios. This tailored approach often renders a mobility model useless when the application domain changes, and leads to wrong conclusions about the performance of protocols and applications running atop of different domains. In this work we propose and implement a mobility modeling framework (UMMF) based on the observation that the mobility characteristics of most mobility-based applications can be captured in terms of a few fundamental factors: (1) Targets; (2) Obstacles; (3) Dynamic events; (4) Navigation; (5) Steering behaviors; and (6) Dynamic behaviors. We demonstrate the mapping of application-domain-specifics to UMMF elements, showing the power and flexibility of our approach.

We consider a Delay Tolerant Network (DTN) whose users (nodes) are connected by an underlying Mobile Ad hoc Network (MANET) substrate. Users can declaratively express high-level policy constraints on how "content" should be routed. For example, content can be directed through an intermediary DTN node for the purposes of preprocessing, authentication, etc., or content from a malicious MANET node can be dropped. To support such content routing at the DTN level, we implement Predicate Routing where high-level constraints of DTN nodes are mapped into low-level routing predicates within the MANET nodes. Our testbed uses a Linux system architecture with User Mode Linux to emulate every DTN node with a DTN Reference Implementation code. In our initial architecture prototype, we use the On Demand Distance Vector (AODV) routing protocol at the MANET level. We use the network simulator ns-2 (nsemulation version) to simulate the wireless connectivity of both DTN and MANET nodes. Preliminary results show the efficient and correct operation of propagating routing predicates. For the application of content re-routing through an intermediary, as a side effect, results demonstrate the performance benefit of content re-routing that dynamically (on-demand) breaks the underlying end-to-end TCP connections into shorter-length TCP connections.

We introduce the Dynamic Policy Routing (DPR) model that captures the propagation of route updates under arbitrary changes in topology or path preferences. DPR introduces the notion of causation chains where the route flap at one node causes a flap at the next node along the chain.

The initial phase in a content distribution (file sharing) scenario is delicate due to the lack of global knowledge and the dynamics of the overlay. An unwise distribution of the pieces in this phase can cause delays in reaching steady state, thus increasing file download times. We devise a scheduling algorithm at the seed (source peer with full content), based on a proportional fair approach, and we implement it on a real file sharing client. In dynamic overlays, our solution improves by up to 25% the average downloading time of a standard protocol ala BitTorrent.

This position paper outlines a new network architecture that is based on the fundamental principle that networking is interprocess communication (IPC). In this model, application processes (APes) communicate via an IPC facility. The IPC processes that make up this facility provide a protocol that implements an IPC mechanism, and a protocol for managing distributed IPC (routing, security and other management tasks). Our architecture is recursive in that the IPC processes can themselves be APes requesting services from lower IPC facilities. We present the repeating patterns and structures in our architecture, and show how the proposed model would cope with the challenges faced by today's Internet (and that of the future).

Personal communication devices are increasingly equipped with sensors for passive monitoring of encounters and surroundings. We envision the emergence of services that enable a community of mobile users carrying such resource-limited devices to query such information at remote locations in the field in which they collectively roam. One approach to implement such a service is directed placement and retrieval (DPR), whereby readings/queries about a specific location are routed to a node responsible for that location. In a mobile, potentially sparse setting, where end-to-end paths are unavailable, DPR is not an attractive solution as it would require the use of delay-tolerant (flooding-based store-carry-forward) routing of both readings and queries, which is inappropriate for applications with data freshness constraints, and which is incompatible with stringent device power/memory constraints. Alternatively, we propose the use of amorphous placement and retrieval (APR), in which routing and field monitoring are integrated through the use of a cache management scheme coupled with an informed exchange of cached samples to diffuse sensory data throughout the network, in such a way that a query answer is likely to be found close to the query origin. We argue that knowledge of the distribution of query targets could be used effectively by an informed cache management policy to maximize the utility of collective storage of all devices. Using a simple analytical model, we show that the use of informed cache management is particularly important when the mobility model results in a non-uniform distribution of users over the field. We present results from extensive simulations which show that in sparsely-connected networks, APR is more cost-effective than DPR, that it provides extra resilience to node failure and packet losses, and that its use of informed cache management yields superior performance.

We present a transport protocol whose goal is to reduce power consumption without compromising delivery requirements of applications. To meet its goal of energy efficiency, our transport protocol (1) contains mechanisms to balance end-to-end vs. local retransmissions; (2) minimizes acknowledgment traffic using receiver regulated rate-based flow control combined with selected acknowledgements and in-network caching of packets; and (3) aggressively seeks to avoid any congestion-based packet loss. Within a recently developed ultra low-power multi-hop wireless network system, extensive simulations and experimental results demonstrate that our transport protocol meets its goal of preserving the energy efficiency of the underlying network.

Traditionally, slotted communication protocols have employed guard times to delineate and align slots. These guard times may expand the slot duration significantly, especially when clocks are allowed to drift for longer time to reduce clock synchronization overhead. Recently, a new class of lightweight protocols for statistical estimation in wireless sensor networks have been proposed. This new class requires very short transmission durations (jam signals), thus the traditional approach of using guard times would impose significant overhead. We propose a new, more efficient algorithm to align slots. Based on geometrical properties of space, we prove that our approach bounds the slot duration by only a constant factor of what is needed. Furthermore, we show by simulation that this bound is loose and an even smaller slot duration is required, making our approach even more efficient.

One key adaptation mechanism often deployed in networking and computing systems is dynamic load balancing. The goal from employing dynamic load balancers is to ensure that the offered load would be judiciously distributed across resources to optimize the overall performance. To that end, this paper discovers and studies new instances of Reduction of Quality (RoQ) attacks that target the dynamic operation of load balancers. Our exposition is focused on a number of load balancing policies that are either employed in current commercial products or have been proposed in literature for future deployment. Through queuing theory analysis, numerical solutions, simulations and Internet experiments, we are able to assess the impact of RoQ attacks through the potency metric. We identify the key factors, such as feedback delay and averaging parameters, that expose the trade-offs between resilience and susceptibility to RoQ attacks. These factors could be used to harden load balancers against RoQ attacks. To the best of our knowledge, this work is the first to study adversarial exploits on the dynamic operation of load balancers.

Although cooperation generally increases the amount of resources available to a community of nodes, thus improving individual and collective performance, it also allows for the appearance of potential mistreatment problems through the exposition of one node's resources to others. We study such concerns by considering a group of independent, rational, self-aware nodes that cooperate using online caching algorithms, where the exposed resource is the storage at each node. Motivated by content networking applications - including Web caching, content delivery networks (CDNs), and peer-to-peer (P2P) - this paper extends our previous work on the offline version of the problem, which was conducted under a game-theoretic framework and limited to object replication. We identify and investigate two causes of mistreatment: 1) cache state interactions (due to the cooperative servicing of requests) and 2) the adoption of a common scheme for cache management policies. Using analytic models, numerical solutions of these models, and simulation experiments, we show that online cooperation schemes using caching are fairly robust to mistreatment caused by state interactions. To appear in a substantial manner, the interaction through the exchange of miss streams has to be very intense, making it feasible for the mistreated nodes to detect and react to exploitation. This robustness ceases to exist when nodes fetch and store objects in response to remote requests, that is, when they operate as level-2 caches (or proxies) for other nodes. Regarding mistreatment due to a common scheme, we show that this can easily take place when the "outlier" characteristics of some of the nodes get overlooked. This finding underscores the importance of allowing cooperative caching nodes the flexibility of choosing from a diverse set of schemes to fit the peculiarities of individual nodes. To that end, we outline an emulation-based framework for the development of mistreatment-resilient distributed selfish caching schemes.

Recent research have exposed new breeds of attacks that are capable of denying service or inflicting significant damage to TCP flows, without sustaining the attack traffic. Such attacks are often referred to as "low-rate" attacks and they stand in sharp contrast against traditional Denial of Service (DoS) attacks that can completely shut off TCP flows by flooding an Internet link. In this paper, we study the impact of these new breeds of attacks and the extent to which defense mechanisms are capable of mitigating the attack's impact. Through adopting a simple discrete-time model with a single TCP flow and a non-oblivious adversary, we were able to expose new variants of these low-rate attacks that could potentially have high attack potency per attack burst. Our analysis is focused towards worst-case scenarios, thus our results should be regarded as upper bounds on the impact of low-rate attacks rather than a real assessment under a specific attack scenario.

The heterogeneity and open nature of network systems make analysis of compositions of components quite challenging, making the design and implementation of robust network services largely inaccessible to the average programmer. We propose the development of a novel type system and practical type spaces which reflect simplified representations of the results and conclusions which can be derived from complex compositional theories in more accessible ways, essentially allowing the system architect or programmer to be exposed only to the inputs and output of compositional analysis without having to be familiar with the ins and outs of its internals. Toward this end, we present the TRAFFIC (typed representation and analysis of flows for interoperability checks) framework, a simple flow-composition and typing language with corresponding type system. We then discuss and demonstrate the expressive power of a type space for TRAFFIC derived from the network calculus, allowing us to reason about and infer such properties as data arrival, transit, and loss rates in large composite network applications

Current computing systems depend on adaptation mechanisms to ensure that they remain in quiescent operating regions. These regions are often defined using efficiency, fairness, and stability properties. To that end, traditional research works in scalable server architectures and protocols have focused on promoting these properties by proposing even more sophisticated adaptation mechanisms, without the proper attention to security implications. In this paper, we exemplify such security implications by exposing the vulnerabilities of admission control mechanisms that are widely deployed in Internet end systems to reduction of quality (RoQ) attacks. RoQ attacks target the transients of a system's adaptive behavior as opposed to its limited steady-state capacity. We show that a well orchestrated RoQ attack on an end-system admission control policy could introduce significant inefficiencies that could potentially deprive an Internet end-system from much of its capacity, or significantly reduce its service quality, while evading detection by consuming an unsuspicious, small fraction of that system's hijacked capacity. We develop a control theoretic model for assessing the impact of RoQ attacks on an end-system's admission controller. We quantify the damage inflicted by an attacker through deriving appropriate metrics. We validate our findings through real Internet experiments performed in our lab.

We leverage the buffering capabilities of end-systems to achieve scalable, asynchronous delivery of streams in a peer-to-peer environment. Unlike existing cache-and-relay schemes, we propose a distributed prefetching protocol where peers prefetch and store portions of the streaming media ahead of their playout time, thus not only turning themselves to possible sources for other peers but their prefetched data can allow them to overcome the departure of their source-peer. This stands in sharp contrast to existing cache-and-relay schemes where the departure of the source-peer forces its peer children to go the original server, thus disrupting their service and increasing server and network load. Through mathematical analysis and simulations, we show the effectiveness of maintaining such asynchronous multicasts from several source-peers to other children peers, and the efficacy of prefetching in the face of peer departures. We confirm the scalability of our dPAM protocol as it is shown to significantly reduce server load.

With the increased use of Virtual Machines (VMs) as vehicles that isolate applications running on the same host, it is necessary to devise techniques that enable multiple VMs to share underlying resources both fairly and efficiently. To that end, one common approach is to deploy complex resource management techniques in the hosting infrastructure. Alternately, in this paper, we advocate the use of self-adaptation in the VMs themselves based on feedback about resource usage and availability. Consequently, we define Friendly VM (FVM) to be a virtual machine that adjusts its demand for system resources, so that they are both efficiently and fairly allocated to competing FVMs. Such properties are ensured using one of many provably convergent control rules, such as Additive-Increase/Multiplicative-Decrease (AIMD). By adopting this distributed application-based approach to resource management, it is not necessary to make assumptions about the underlying resources nor about the requirements of FVMs competing for these resources. To demonstrate the elegance and simplicity of our approach, we present a prototype implementation of our FVM framework in User-Mode Linux (UML)---an implementation that consists of less than 500 lines of code changes to UML. We present an analytic, control-theoretic model of FVM adaptation, which establishes convergence and fairness properties. These properties are also backed up with experimental results using our prototype FVM implementation.

We study the effect of the IP router buffer size on the throughput of HighSpeed TCP (HSTCP). We are motivated by the fact that, in high speed routers, the buffer size is important, as a large buffer size might be a constraint. We first derive an analytical model for HighSpeed TCP and we show that for a small buffer size, equal to 10% of the bandwidth-delay product, HighSpeed TCP can achieve more than 90% of the bottleneck capacity. We also show that setting the buffer size equal to 20% can increase the utilization of HighSpeed TCP up to 98%. On the contrary, setting the buffer size to less than 10% of the bandwidth-delay product can decrease HighSpeed TCP's throughput significantly. We also study the performance effects under both DropTail and RED AQM (active queue management). Analytical results obtained using a fixed-point approach are compared to those obtained by simulation.

We expose an unorthodox adversarial attack that exploits the transients of a system's adaptive behavior, as opposed to its limited steady-state capacity. We show that a well orchestrated attack could introduce significant inefficiencies that could potentially deprive a network element from much of its capacity, or significantly reduce its service quality, while evading detection by consuming an unsuspicious, small fraction of that element's hijacked capacity. This type of attack stands in sharp contrast to traditional brute-force, sustained high-rate DoS attacks, as well as recently proposed attacks that exploit specific protocol settings such as TCP timeouts. We exemplify what we term as reduction of quality (RoQ) attacks by exposing the vulnerabilities of common adaptation mechanisms. We develop control-theoretic models and associated metrics to quantify these vulnerabilities. We present numerical and simulation results, which we validate with observations from real Internet experiments. Our findings motivate the need for the development of adaptation mechanisms that are resilient to these new forms of attacks.

The best-effort nature of the Internet poses a significant obstacle to the deployment of many applications that require guaranteed bandwidth. We present a novel approach that enables two edge/border routers which we call Internet traffic managers (ITM) - to use an adaptive number of TCP connections to set up a tunnel of desirable bandwidth between them. The number of TCP connections that comprise this tunnel is elastic in the sense that it increases/decreases in tandem with competing cross traffic to maintain a target bandwidth. An origin ITM would then schedule incoming packets from an application requiring guaranteed bandwidth over that elastic tunnel. Unlike many proposed solutions that aim to deliver soft QoS guarantees, our elastic-tunnel approach does not require any support from core routers (as with IntServ and DiffServ); it is scalable in the sense that core routers do not have to maintain per-flow state (as with IntServ); and it is readily deployable within a single ISP or across multiple ISPs. To evaluate our approach, we develop a flow-level control theoretic model to study the transient behavior of established elastic TCP-based tunnels. The model captures the effect of cross-traffic connections on our bandwidth allocation policies. Through extensive simulations, we confirm the effectiveness of our approach in providing soft bandwidth guarantees.

Wireless sensor networks are characterized by limited energy resources. To conserve energy, application-specific aggregation (fusion) of data reports from multiple sensors can be beneficial in reducing the amount of data flowing over the network. Furthermore, controlling the topology by scheduling the activity of nodes between active and sleep modes has often been used to uniformly distribute the energy consumption among all nodes by de-synchronizing their activities. We present an integrated analytical model to study the joint performance of in-network aggregation and topology control. We define performance metrics that capture the tradeoffs among delay, energy, and fidelity of the aggregation. Our results indicate that to achieve high fidelity levels under medium to high event reporting load, shorter and fatter aggregation/routing trees (toward the sink) offer the best delay-energy tradeoff as long as topology control is well coordinated with routing.

No abstract available.

Finite-state Markov chain (FSMC) models have often been used to characterize the wireless channel. The fitting is typically performed by partitioning the range of the received signal-to-noise ratio (SNR) into a set of intervals (states). Different partitioning criteria have been proposed in the literature, but none of them was targeted to facilitating the analysis of the packet delay and loss performance over the wireless link. In this paper, we propose a new partitioning approach that results in an FSMC model with tractable queueing performance. Our approach utilizes Jake's level-crossing analysis, the distribution of the received SNR, and the elegant analytical structure of Mitra's producer-consumer fluid queueing model. An algorithm is provided for computing the various parameters of the model, which are then used in deriving closed-form expressions for the effective bandwidth (EB) subject to packet loss and delay constraints. Resource allocation based on the EB is key to improving the perceived capacity of the wireless medium. Numerical investigations are carried out to study the interactions among various key parameters, verify the adequacy of the analysis, and study the impact of error control parameters on the allocated bandwidth for guaranteed packet loss and delay performance.

One relatively unexplored question about the Internet's physical structure concerns the geographical location of its components: routers, links, and autonomous systems (ASes). We study this question using two large inventories of Internet routers and links, collected by different methods and about two years apart. We first map each router to its geographical location using two different state-of-the-art tools. We then study the relationship between router location and population density; between geographic distance and link density; and between the size and geographic extent of ASes. Our findings are consistent across the two datasets and both mapping methods. First, as expected, router density per person varies widely over different economic regions; however, in economically homogeneous regions, router density shows a strong superlinear relationship to population density. Second, the probability that two routers are directly connected is strongly dependent on distance; our data is consistent with a model in which a majority (up to 75%-95%) of link formation is based on geographical distance (as in the Waxman (1988) topology generation method). Finally, we find that ASes show high variability in geographic size, which is correlated with other measures of AS size (degree and number of interfaces). Among small to medium ASes, ASes show wide variability in their geographic dispersal; however, all ASes exceeding a certain threshold in size are maximally dispersed geographically. These findings have many implications for the next generation of topology generators, which we envisage as producing router-level graphs annotated with attributes such as link latencies, AS identifiers, and geographical locations.

The increasing diversity of Internet application requirements has spurred recent interest in transport protocols with flexible transmission controls. In window-based congestion control schemes, increase rules determine how to probe available bandwidth, whereas decrease rules determine how to back off when losses due to congestion are detected. The control rules are parameterized so as to ensure that the resulting protocol is TCP-friendly in terms of the relationship between throughput and loss rate. This paper presents a comprehensive study of a new spectrum of window-based congestion controls, which are TCP-friendly as well as TCP-compatible under RED. Our controls utilize history information in their control rules, and by doing so, they improve the transient behavior. We demonstrate analytically, and through extensive ns simulations, the steady-state and transient behavior of several instances of this new spectrum.

The current congestion-oriented design of TCP hinders its ability to perform well in hybrid wireless/wired networks. We propose a new improvement on TCP NewReno (NewReno-FF) using a new loss labeling technique to discriminate wireless from congestion losses. The proposed technique is based on the estimation of average and variance of the round trip time using a filter, called flip flop filter, that is augmented with history information. We show the comparative performance of TCP NewReno, NewReno-FF and TCP Westwood through extensive simulations. We study the fundamental gains and limits using TCP NewReno with varying loss labeling accuracy (NewReno-LL) as a benchmark. Lastly our investigation opens up important research directions. First, there is a need for a finer grained classification of losses (even within congestion and wireless losses) for TCP in heterogeneous networks. Second, it is essential to develop an appropriate control strategy for recovery after the correct classification of a packet loss.

No abstract available.

Previous job scheduling studies indicate that providing rapid response to interactive jobs which place frequent but small demands, can reduce the overall system average response time [1], especially when the job size distribution is skewed (see [2] and references therein). Since the distribution of Internet flows is skewed, it is natural to design a network system that favors short file transfers through service differentiation. However, to maintain system scalability, detailed per-flow state such as flow length is generally not available inside the network. As a result, we usually resort to a threshold-based heuristic to identify and give preference to short flows. Specifically, packets from a new flow are always given the highest priority. However, the priority is reduced once the flow has transferred a certain amount of packets.In this paper, we use the MultiLevel (ML) feedback queue [3] to characterize this discriminatory system. However, the solution given in [3] is in the form of an integral equation, and to date the equation has been solved only for job size distribution that has the form of mixed exponential functions. We adopt an alternative approach, namely using a conservation law by Kleinrock [1], to solve for the average response time in such system. To that end, we approximate the average response time of jobs by a linear function in the job size and solve for the stretch (service slowdown) factors. We show by simulation that such approximation works well for job (flow) size distributions that possess the heavy-tailed property [2], although it does not work so well for exponential distributions.Due to the limited space available, in Section 2 we briefly describe the queueing model and summarize our approximation approach to solving for the average response time of the M/G/1/ML queueing system. We conclude our paper in Section 3.

In recent years mobile computing has experienced significant growth, mainly due to the integration of wireless networks with the wired Internet. This integration itself experienced several stages of evolution: from the functional issues of network heterogeneity to the optimization of the Internet protocols. Currently, the design issues of reliable protocols for mobile computing possess a fundamental locus. More precisely, performance evaluation, throughput optimization, energy saving, and network/device functionality within the layered Internet call for further attention. Within this context, this special issue addresses the design concerns of reliable protocols for mobile computing. We have selected seven papers for presentation in the special issue, from a large pool of submitted papers in response to our call for papers. The first paper, authored by the guest editors, discusses open issues on the design of the dominant Internet protocol, the Transmission Control Protocol (TCP). The paper classifies the recent work based on the functionality of the proposed modifications, realizes the need for new performance metrics and presents selected results of two recent approaches to mobile TCP, namely TCP-Probing and WTCP. The paper by Eckhardt and Steenkiste investigates the possibility of dealing with wireless link errors by combining a link-level local error control with error-sensitive link scheduling. Having a direct target the improvement of TCP over wireless networks, Chen, Hsiao, Hou, Ge, and Fitz propose the use of Syndrome. Syndrome is a light-weight approach to improving TCP's throughput performance. The combination of TCP's sequence numbers and the additional base station-attached numbers allow for detection of the error's location (i.e., wired vs. wireless). This is a significant step toward error correction especially owing to the fact that the base station does not need to buffer packets or a significant amount of states. Vaidya, Mehta, Perkins, and Montenegro propose an alternative TCP-unaware technique where the wireless client delays duplicate acknowledgments to avoid fast retransmit at the sender. This is in sharp contrast to TCP-aware techniques such as Snoop. Along the lines of performance evaluation, the paper by Xu and Saadawi compares the performance of various TCP versions over ad-hoc (multi-hop wireless) networks and suggests appropriate parameter tuning in order for those versions to behave appropriately. Emphasizing the energy/throughput tradeoff, Zorzi, Rossi, and Mazzini investigate the performance of TCP over wideband CDMA air interface. Such interfaces are typical of third-generation wireless networks. The authors introduce a universal throughput curve and exploit the possibility of selecting an optimal power control threshold thereby optimizing the tradeoff between throughput gains and energy expenditure. Finally, to deal with reliable handoffs, the paper by Jobin, Tripathi, Gokhale and Faloutsos quantifies the effectiveness of a predictive reservations scheme using metrics which characterize the mobility profile of users. We would like to offer special thanks to the reviewers and to the authors for their contribution to this special issue.

Abstract We discuss the design principles of TCP within the context of heterogeneous wired/wireless networks and mobile networking. We identify three shortcomings in TCP's behavior: (i) the protocol's error detection mechanism, which does not distinguish different types of errors and thus does not suffice for heterogeneous wired/wireless environments, (ii) the error recovery, which is not responsive to the distinctive characteristics of wireless networks such as transient or burst errors due to handoffs and fading channels, and (iii) the protocol strategy, which does not control the tradeoff between performance measures such as goodput and energy consumption, and often entails a wasteful effort of retransmission and energy expenditure. We discuss a solution‐framework based on selected research proposals and the associated evaluation criteria for the suggested modifications. We highlight an important angle that did not attract the required attention so far: the need for new performance metrics, appropriate for evaluating the impact of protocol strategies on battery‐powered devices. Copyright © 2001 John Wiley & Sons, Ltd.

Recent measurement based studies reveal that most of the Internet connections are short in terms of the amount of traffic they carry (mice), while a small fraction of the connections are carrying a large portion of the traffic (elephants). A careful study of the TCP protocol shows that without help from an active queue management (AQM) policy, short connections tend to lose to long connections in their competition for bandwidth. This is because short connections do not gain detailed knowledge of the network state, and therefore they are doomed to be less competitive due to the conservative nature of the TCP congestion control algorithm. Inspired by the differentiated services (Diffserv) architecture, we propose to give preferential treatment to short connections inside the bottleneck queue, so that short connections experience less packet drop rate than long connections. This is done by employing the RIO (RED with In and Out) queue management policy which uses different drop functions for different classes of traffic. Our simulation results show that: (1) in a highly loaded network, preferential treatment is necessary to provide short TCP connections with better response time and fairness without hurting the performance of long TCP connections; (2) the proposed scheme still delivers packets in FIFO manner at each link, thus it maintains statistical multiplexing gain and does not misorder packets; (3) choosing a smaller default initial timeout value for TCP can help enhance the performance of short TCP flows, however not as effectively as our scheme and at the risk of congestion collapse; (4) in the worst case, our proposal works as well as a regular RED scheme, in terms of response time and goodput.

The increased diversity of Internet application requirements has spurred interest in flexible congestion control mechanisms. Window-based congestion control schemes use increase rules to probe available bandwidth, and decrease rules to back off when congestion is detected. The control rules are parameterized so as to ensure that the resulting protocol is TCP-friendly in terms of the relationship between throughput and packet loss rate. We propose a novel window-based congestion control algorithm called SIMD (Square-Increase/Multiplicative-Decrease). Contrary to previous memoryless controls, SIMD utilizes history information in its control rules. It uses multiplicative decrease but the increase in window size is in proportion to the square of the time elapsed since the detection of the last loss event. Thus, SIMD can efficiently probe available bandwidth. Nevertheless, SIMD is TCP-friendly as well as TCP-compatible through RED routers. Furthermore, SIMD has much better convergence behavior than TCP-friendly AIMD and binomial algorithms proposed previously.

We present a new reliable multicast protocol, called ARM for adaptive reliable multicast. Our protocol integrates ARQ and FEC techniques. The objectives of ARM are (1) reduce the message overhead due to NACK requests, (2) reduce the amount of data transmission, and (3) reduce the time it takes for all receivers to receive the data intact (without loss). During data transmission, the sender periodically informs the receivers of the number of packets that are yet to be transmitted. Based on this information, each receiver predicts whether this amount is enough to recover its losses. Only if it is not enough, that the receiver requests the sender to encode additional redundant packets. Using ns simulations, we show the superiority of our hybrid ARQ-FEC protocol over the well-known scalable reliable multicast (SRM) protocol.

The majority of the traffic (bytes) flowing over the Internet today have been attributed to the Transmission Control Protocol (TCP). This strong presence of TCP has spurred further investigations into its congestion control mechanism and its effect on the performance of short and long data transfers. We investigate the interaction among short and long TCP flows, and how TCP service can be improved by employing a low-cost service differentiation scheme. Through control-theoretic arguments and extensive simulations, we show the utility, of isolating TCP flows into two classes based on their life-time/size, time/size one class of short flows and another of long flows. With such class-based isolation, short and long TCP flows have separate service queues at routers. This protects each class of flows from the other as they possess different characteristics, such as burstiness of arrivals/departures and congestion/sending window dynamics. We show the benefits of isolation, in terms of better predictability and fairness, over traditional shared queueing systems with both tail-drop and random-early-drop (RED) packet dropping policies.

Previously, Rangarajan et al. (see Proc. of the 25th International Symposium on Fault-Tolerant Computing, 1995) presented the design, specification and proof of correctness of a fully distributed location management scheme for PCS networks and argued that fully replicating location information is both appropriate and efficient for small PCS networks. In this paper, we extend our previous work by first analyzing the performance of our scheme. Then, we extend the scheme in a hierarchical environment so as to reduce the overhead and scale to large PCS networks. Through extensive numerical results, we show the superiority of our scheme compared to the current IS-41 standard.

To provide real time service, integrated networks require the underlying routing algorithm to be able to find low cost paths that satisfy given Quality of Service (QoS) constraints. The problem of constrained shortest (least cost) path routing is known to be NP hard, and some heuristics have been proposed to find a near optimal solution. However, these heuristics either impose relationships among the link metrics to reduce the complexity of the problem which may limit the general applicability of the heuristic, or are too costly in terms of execution time to be applicable to large networks. We focus on solving the delay constrained minimum cost path problem, and present a fast algorithm to find a near optimal solution. This algorithm, called DCCR (Delay-Cost-Constrained Routing), is a variant of the k-shortest path algorithm. DCCR uses a new adaptive path weight function, together with an additional constraint imposed on the path cost, to restrict the search space. Thus, DCCR can return a near optimal solution in a very short time. Furthermore, we use the method proposed by D. Blokh and G. Gutin (1995) to further reduce the search space by using a tighter bound on path cost. This makes our algorithm more accurate and even faster. We call this improved algorithm SSR+DCCR (Search Space Reduction+DCCR). Through extensive simulations, we confirm that SSR+DCCR performs very well compared to the optimal but very expensive solution.

Personal communication networks support the delivery of communication services as the user moves from one region to another. When a mobile user/terminal receives a call, the network has to quickly determine its current location. The existing approach suffers from high delay in locating the mobile as it requires maintaining the current location in a stable storage that has to be always consulted to reach the mobile. To reduce this delay, many proposed schemes rely on caching the locations of mobiles, especially those which do not move too frequently. To measure mobility, the node that originates the call usually measures only those movements that it sees between successive calls to that mobile. In this paper, we present a caching scheme based on fully disseminating the location updates of mobiles to every node so as to increase the chance that the cache entry points to the correct location of the mobile user. We analyze our full dissemination based scheme and compare it to other caching and non-caching based schemes.

Many distributed real-time applications, such as audio- and video-conferencing, require the network to construct a multicast path (tree) from a sender to multiple receivers. Furthermore, real-time applications have quality-of-service (QoS) requirements (e.g, bandwidth). The objective of the routing protocol is to build a tree that is both feasible (i.e., satisfies the requested QoS) and least costly. The cost of a tree depends on the costs of its links. The cost of a link should reflect the effect of allocating resources to the new connection on existing and future connections. Many studies have proposed multicast algorithms to construct low-cost QoS-constrained trees. However, these studies assume that some cost is given for each link, and they do not examine the effect of the link cost function. In this paper, we examine the effect of various link cost functions on the performance of two classes of multicast routing algorithms under both uniform and skewed real-time workload. We also investigate the impact of inaccurate network state information. Our simulation results show that when network state information is accurate (most up-to-date) at each router, the choice of the link cost function only has a negligible effect, if any, on the routing performance. More interestingly, we find that a link cost function that is more sensitive to load performs better when link state information is relatively accurate, while when link state information is more stale, a link cost function that is less sensitive to load performs better. This is more pronounced under higher load and when multicast groups are more dense.

Computer supported cooperative work (CSCW) has the potential of providing the environment needed for groups of diverse users to cooperate to achieve their common goals. This potential has been under-utilized. One major obstacle is the lack of cooperation between CSCW systems and the underlying network services to accommodate the dynamic behavior of CSCW groups. Multicast routing presents a strong case where current network services are inadequate for the traffic generated in CSCW environments. We demonstrate the need for CSCW-specific multicast routing and present an integrated QoS architecture where a router QoS manager, on behalf of a multicast routing manager, negotiates with host and CSCW-specific QoS managers for efficient resource utilization and guaranteed QoS delivery. The multicast routing manager switches between routing trees or algorithms as guaranteed by the changes in the characteristics and requirements of the CSCW systems running at the hosts. We discuss an aspect-oriented programming approach to the efficient description and flexible implementation of adaptive application and network protocol behavior.

We study a new approach to routing multi-class traffic flows with guaranteed bandwidth requirements. The approach is based on our concept of load profiling (Bestavros and Matta, 1997). We thoroughly characterize routing performance using load profiling and contrast it to routing using load balancing and load packing. We do so both analytically and via extensive simulations on virtual path (VP) based networks. Our findings confirm that load balancing is not desirable as it results in VP bandwidth fragmentation, which adversely affects the likelihood of accepting new flow requests. This fragmentation is more pronounced when the granularity of the requests is large. Our simulation results also show that our load-profiling routing scheme performs better or as well as the traditional load-balancing routing in terms of revenue under both skewed and uniform workloads. Furthermore, load-profiling routing improves routing fairness by proactively increasing the chances of admitting high-bandwidth flows.

The transmission control protocol (TCP) used in the Internet has been mainly designed assuming a relatively reliable wireline network. The TCP assumes that any loss is due to congestion and consequently invokes congestion control measures. This has been shown to yield poor performance in the presence of wireless links as a large number of segment losses will occur more often because of wireless channel errors or host mobility. We present an efficient transmission control scheme (WTCP) that requires the base station to buffer data packets destined for the mobile host and retransmit lost packets. Through simulations, we show that our scheme yields better throughput than other existing proposals while maintaining the TCP's end-to-end semantics. One salient feature of WTCP is that it effectively hides the time spent by the base station to locally recover so that the TCP's round trip time estimation at the source is not affected. This is critical since otherwise the ability of the source to effectively detect congestion in the wireline network will be hindered.

We examine various schemes for dynamically routing virtual circuits (VCs) in a multi-class network. A VC setup request may be rejected by admission control because resources are either unavailable or being reserved for future incoming VCs. We examine least-loaded based schemes, which attempt to balance the load among available routes. In addition, we examine packing based schemes, which attempt to reduce bandwidth fragmentation possibly at the expense of load balancing. Our simulation results show that under skewed workload, our packing based scheme outperforms a traditional least-loaded based scheme in terms of revenue (or equivalently, network utilization). Under uniform workload, both schemes provide similar revenue.

High-speed networks, such as ATM networks, are expected to support real-time Quality of Service (QoS) guarantees required by many applications such as those that involve voice and video communication. To support such services, routing algorithms that allow for the reservation of the needed bandwidth over a Virtual Circuit (VC) have been proposed. Commonly, these algorithms assign VCs to routes using the least-loaded concept, and thus result in balancing the load over the set of all candidate routes. In this paper, we show that for such reservation-based VC routing algorithms-which allow for the exclusive use of a preset fraction of a resource's bandwidth for an extended period of time-load balancing is not desirable as it results in resource fragmentation, which adversely affects the likelihood of accepting new VC requests. We present an on-line VC routing scheme that is based on the concept of "load profiling", which allows a distribution of "available" bandwidth across a set of candidate routes to match the characteristics of incoming VC QoS requests. We show the effectiveness of our load-profiling approach when compared to traditional load-balancing and load-packing VC routing schemes.

Future integrated services networks, such as ATM networks, will support diverse services, including the guaranteed real-time service required by many applications such as voice and video. To support such services, virtual circuit (VC) routing algorithms are often proposed. Typically, the source maintains a view of the network, and uses this view to select a path to the destination. A request is then made to setup a real-time VC over this path through resource reservations. The request is blocked if the requested resources are not available. These VC routing algorithms are usually evaluated individually in terms of steady-state performance measures. In this paper, we compare several VC routing schemes in terms of instantaneous measures using a time-dependent evaluation method. Our results show that a routing scheme which defines the cost of a path as the sum of measured link utilizations yields more stable behavior and lower VC blocking probability over a wide range of workload parameters and network configurations than other traditional schemes.

We present a scalable VC routing protocol based on the viewserver hierarchy. Each viewserver maintains a partial view of the network. By querying these viewservers, a source obtains a merged view that contains a path to the destination. The source then sends a setup request packet over this path to reserve resources. We use simulation to compare our protocol to a simple approach that maintains a full view of the network. In addition to the savings in storage, our protocol performs as well or better in terms of the VC carried load and blocking probability over a wide range of real-time workload.

Multiple-class multiple-resource (MCMR) systems, where each class of customers requires a particular set of resources, are common. These systems are often analyzed under steady-state conditions. We describe a simple method, referred to as Z-iteration, to estimate both transient and steady-state performances of such systems. The method makes use of results and techniques available from queueing theory, network analysis, dynamic flow theory, and numerical analysis. We show the generality of the Z-iteration by applying it to an ATM network, a parallel disk system, and a distributed batch system. Validations against discrete-event simulations show the accuracy and computational advantages of the Z-iteration.

The Internet is expected to support various services, including best-effort services and guaranteed services. For best-effort services, we propose a new approach to achieving type-of-service (TOS) classes with adaptive next-hop routing. We consider two TOS classes, namely, delay-sensitive and throughput-sensitive. As in routing protocols such as OSPF and integrated IS-IS, each node has a different next-hop for each destination and TOS class. Traditionally, a node has a single FCFS queue for each outgoing link, and the next-hops are computed using link measurements. In our approach, we attempt to isolate the two traffic classes by using for each outgoing link a separate FCFS queue for each TOS class; the link is shared cyclicly between its TOS queues. The next-hops for the delay-sensitive traffic adapts to link delays of that traffic. The next-hops for the throughput-sensitive traffic adapts to overall link utilizations. We compare our approach with the traditional approach using discrete-event simulation and Lyapunov analysis (for stability of routes). Our approach offers lower end-to-end delay to the delay-sensitive traffic. A related property is that the routes for the delay-sensitive traffic are more stable, i.e., less oscillations. An unexpected property is that the overall end-to-end delay is lower, because the throughput-sensitive traffic moves away to under-utilized routes.>

Future networks are expected to integrate diverse services. For this purpose, new algorithms and protocols have been proposed for link scheduling, admission control, and routing. The interaction between these three components is crucial to the performance of the network. However, this interaction is difficult to model realistically using available techniques. We present an iterative discrete-time approach that yields a realistic model which takes into account this interaction. The model applies to connection-oriented networks with different types of real-time connections. It allows the investigation of various control schemes for both transient and steady-state performances. Preliminary results indicate that our approach is computationally much cheaper than discrete-event simulation, and yields sufficiently accurate performance measures.>

The authors propose a new approach to achieving type-of-service (TOS) with adaptive next-hop routing in wide-area networks such as the Internet. They consider two traffic classes, namely delay-sensitive and throughput-sensitive. Their approach attempts to isolate the two traffic classes by using two FCFS queues at each out-going link, one for each TOS; the link is shared cyclicly between the two TOS queues. The next-hops for the delay-sensitive traffic adapts to link delays of that traffic. The next-hops for the throughput-sensitive traffic adapts to overall link utilizations. They compare their approach with a traditional approach using discrete-event simulation and Lyapunov analysis (for stability of routes). Because of the isolation feature, the proposed approach offers lower end-to-end delays for both traffic classes.>

There are two approaches to adaptive routing protocols for wide-area store-and-forward networks: distance-vector and link-state. Distance-vector algorithms use O(N x e) storage at each node, whereas link-state algorithms use O(N2), where N is the number of nodes in the network and e is the average degree of a node. The ARPANET started with a distance-vector algorithm (Distributed Bellman-Ford), but because of long-lived loops, changed to a link-state algorithm (SPF). We show, using a recently developed network simulator, MaRS, that a newly proposed distance-vector algorithm (ExBF) performs as well as SPF. This suggests that distance-vector algorithms are appropriate for very large wide-area networks.