Sustainability and climate monitoring efforts create a need for long-term in-situ sensing of large geographic areas. However, environmental monitoring in remote areas of developing countries remains impeded by a lack of low-cost, scalable Internet of Things (IoT) solutions. Whereas IoT systems for in-situ sensing abound, they mostly are either low-cost or suitable for large areas, but not both. In this article, we present a low-cost low-power network solution for in-situ sensing of areas up to hundreds of square kilometers. Taking advantage of LoRa technology, we develop a self-organizing mesh network that can be scaled to a hundred and more nodes. Scalability is achieved by developing methods that mitigate packet collisions during data collection. We present a protocol, called CottonCandy, with which nodes self-organize in a spanning-tree network topology in a distributed fashion. A power profile on a custom-built circuit board shows that CottonCandy nodes can run thousands of duty cycles on 2 AA batteries, sufficient to operate for years in many applications. Using off-the-shelf components, the cost of a CottonCandy node is less than U.S.$\$ $15. Evaluations by simulation show that CottonCandy networks with 100 nodes achieve a packet delivery ratio (PDR) of >90%. Measurements of an outdoor deployment with 15 nodes corroborate the high PDR in a real-life setting.

introduction Share on Introduction to the Special Section on Recent Advances in Networks and Distributed Systems Authors: Mathias Fischer Universität Hamburg, Hamburg, Germany Universität Hamburg, Hamburg, GermanySearch about this author , Winfried Lamersdorf Universität Hamburg, Hamburg, Germany Universität Hamburg, Hamburg, GermanySearch about this author , Jörg Liebeherr University of Toronto, Toronto, Ontario, Canada University of Toronto, Toronto, Ontario, CanadaSearch about this author , Max Mühlhäuser TU Darmstadt, Darmstadt, Germany TU Darmstadt, Darmstadt, GermanySearch about this author Authors Info & Claims ACM Transactions on Internet TechnologyVolume 22Issue 4November 2022 Article No.: 93pp 1–3https://doi.org/10.1145/3584743Published:15 March 2023Publication History 0citation0DownloadsMetricsTotal Citations0Total Downloads0Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Hierarchical link sharing addresses the demand for fine-grain traffic control at multiple levels of aggregation. At present, packet schedulers that can support hierarchical link sharing are not suitable for an implementation at line rates, whereas deployed schedulers perform poorly at distributing excess capacity to classes that need additional bandwidth. We present HLS, a packet scheduler that ensures a hierarchical max-min fair allocation of the link bandwidth. HLS supports minimum rate guarantees and isolation between classes. Since it is realized as a non-hierarchical round-robin scheduler, it is suitable to operate at high rates. We implement HLS in the Linux kernel and evaluate it with respect to achieved rate allocations and overhead. We compare the results with those obtained for CBQ and HTB, the existing scheduling algorithms in Linux for hierarchical link sharing. We show that the overhead of HLS is comparable to that of other classful packet schedulers.

In recent years, there has been significant interest in the development of wireless train control systems. Among those, communication-based train control (CBTC) systems are new generation rail signaling systems, aimed at achieving real-time, automated train control through wireless communication between the train and a network of access points (APs).Radio channel characterization in railway environments is indispensable for the effective design and deployment of CBTC systems. In this paper, our recent work on the development of a physics-based wireless channel model is summarized. The validity of our developed model is verified against experimental data in various practical scenarios including the London Underground subway network in UK. On the application side, the developed physics-based wireless channel can be integrated with network-level performance metrics to optimize the placement of APs for CBTC systems. Network protocol design can benefit by harnessing a deeper understanding of the underlying physics of electromagnetic propagation in railway environments.

A primary concern in fog computing is how to efficiently allocate limited fog resources to applications with diverse resource requirements. In fog computing, applications that consist of a set of interdependent microservices are mapped to computing and communication devices, referred to as fog nodes. While placement of microservices can be done centrally, the essentially decentralized infrastructure of participating end-user devices motivates the search for distributed solutions. In this paper, we present a distributed placement strategy that seeks to optimize energy consumption and communication costs. We devise a game-theoretic approximation method that is inspired by an iterative combinatorial auction. By properly restricting the types of bids that can be made in an auction, we can avoid the need for a centralized auctioneer. We devise a fully distributed service placement algorithm without central coordination or global state information. The algorithm operates in rounds, where the number of rounds is bounded by the number of applications and the total number of microservices. Numerical examples show that our placement algorithm outperforms existing heuristics in terms of efficiency and network utilization while achieving comparable utilization and load balancing.

Fog computing recently emerged as novel distributed virtualized computing paradigm, where cloud services are extended to the edge of the network, thereby increasing network capacity and reducing latencies. In fog computing, applications are composed of building blocks, called microservices, that are mapped to edge computing and communication devices, referred to as fog nodes. A crucial component in fog computing are placement algorithms that assign microservices to fog nodes, since they determine the overall system performance in terms of energy consumption, communication costs, load balancing, and others. Placement strategies for virtual machines in cloud computing abound, but are generally centralized and therefore not well suited for decentralized fog systems. In this paper, we develop a fully distributed placement strategy that jointly optimizes energy consumption of fog nodes and communication costs of applications. We follow a Markov approximation approach for the design of a fully distributed autonomic service placement strategy without central coordination or global state information. Using numerical examples, we show that our placement algorithm finds solutions that are comparable to existing centralized solutions.

By providing a global infrastructure for information exchange, the Internet has had a transformational impact on society at large. At the same time, a number of indicators, among them an observed ossification phenomenon, raise concerns about the ability of the Internet to support future communication needs and stipulate interest in alternative methods for internetworking. This paper considers an internetworking approach based on self-organizing application-layer networks. Rather than building a single global infrastructure that provides universal access, these networks take advantage of a diverse collection of network infrastructures to interconnect users and devices participating in a networked application. In this paper, we discuss aspects such as scalability, ability to adapt after disruptions, heterogeneous substrate networks, distributed security, and dynamically created network services. The discussions are supported by numerous measurement experiments.

Communication-Based Train Control (CBTC) is a train control system that uses radio communication to exchange information between trains and a central control station. As an inherently time-critical application, CBTC imposes stringent requirements on communication availability and latency. In this paper, we propose to enhance the communication availability in CBTC systems with Application-layer Service Overlay Network (ASON) technology. We show that ASONs can facilitate the switchover from the CBTC infrastructure network to a backup network with alternative communication paths. We employ Application-layer Service Overlay Network (ASON) technology to facilitate the switchover between the CBTC infrastructure network and a backup network. We conduct measurement experiments to evaluate whether the switchover delay to an ASON over an LTE network can satisfy the delay and bandwidth requirements of a time-critical train control application.

In Communication-Based Train Control (CBTC) systems, trains communicate with wayside access points (APs) placed along a track using 802.11 or similar wireless technologies. A critical component of the communication system is the handover algorithm used by a train to select an AP as it moves along a track. As a safety-critical system, the number of handovers should be kept small and selected APs must satisfy given QoS requirements. We present a novel measurement-based handover algorithm for CBTC systems that exploits the predictable motion paths of trains. Using empirical measurements from a rail communication system, we show that our algorithm keeps the number of required handovers small, while avoiding ping-pong handovers, i.e., situations where a train bounces back and forth between the same access points.

Feedback mechanisms are integral components of network protocols and traffic control algorithms. Their performance evaluation is hard due to intricate time correlations introduced by feedback. Network calculus has been successfully applied for the analysis of feedback mechanisms in deterministic systems. However, an extension to random systems has remained an open problem for more than a decade. We present a stochastic network calculus analysis of a random system with feedback, specifically, a window flow control system with random service and fixed feedback delay. We quantify the service impediment due to the feedback mechanism by deriving statistical lower bounds on the available service, and obtain complementary upper bounds. We also discover special cases where an exact description of the service is feasible.

A fundamental problem for the delay and backlog analysis across multihop paths in wireless networks is how to account for the random properties of the wireless channel. Since the usual statistical models for radio signals in a propagation environment do not lend themselves easily to a description of the available service rate, the performance analysis of wireless networks has resorted to higher-layer abstractions, e.g., using Markov chain models. In this paper, we propose a network calculus that can incorporate common statistical models of fading channels and obtain statistical bounds on delay and backlog across multiple nodes. We conduct the analysis in a transfer domain, where the service process at a link is characterized by the instantaneous signal-to-noise ratio at the receiver. We discover that, in the transfer domain, the network model is governed by a dioid algebra, which we refer to as the (min, ×) algebra. Using this algebra, we derive the desired delay and backlog bounds. Using arguments from large deviations theory, we show that the bounds are asymptotically tight. An application of the analysis is demonstrated for a multihop network of Rayleigh fading channels with cross traffic at each hop.

We consider private commons for secondary sharing of licensed spectrum bands with no access coordination provided by the primary license holder. In such environments, heterogeneity in demand patterns of the secondary users can lead to constant changes in the interference levels, and thus can be a source of volatility to the utilities of the users. In this paper, we consider secondary users to be service providers that provide downlink services. We formulate the spectrum sharing problem as a non-cooperative iterated game of power control where service providers change their power levels to fix their long-term average rates at utility-maximizing values. First, we show that in any iterated 2x 2 game, the structure of the single-stage game dictates the degree of control that a service provider can exert on the long-term outcome of the game. Then we show that if service providers use binary actions either to access or not to access the channel at any round of the game, then the long-term rate can be fixed regardless of the strategy of the opponent. We identify these rates and show that they can be achieved using mixed Markovian strategies which will be also identified.

Numerous methods for available bandwidth estimation have been developed for wireline networks, and their effectiveness is well-documented. However, most methods fail to predict bandwidth availability reliably in a wireless setting. It is accepted that the increased variability of wireless channel conditions makes bandwidth estimation more difficult. However, a (satisfactory) explanation why these methods are failing is missing. This paper seeks to provide insights into the problem of bandwidth estimation in wireless networks or, more broadly, in networks with random service. We express bandwidth availability in terms of bounding functions with a defined violation probability. Exploiting properties of a stochastic min-plus linear system theory, the task of bandwidth estimation is formulated as inferring an unknown bounding function from measurements of probing traffic. We present derivations showing that simply using the expected value of the available bandwidth in networks with random service leads to a systematic overestimation of the traffic departures. Furthermore, we show that in a multihop setting with random service at each node, available bandwidth estimates requires observations over (in principle infinitely) long time periods. We propose a new estimation method for random service that is based on iterative constant-rate probes that take advantage of statistical methods. We show how our estimation method can be realized to achieve both good accuracy and confidence levels. We evaluate our method for wired single-and multihop networks, as well as for wireless networks.

A fundamental problem for the delay and backlog analysis across multi-hop paths in wireless networks is how to account for the random properties of the wireless channel. Since the usual statistical models for radio signals in a propagation environment do not lend themselves easily to a description of the available service rate, the performance analysis of wireless networks has resorted to higher-layer abstractions, e.g., using Markov chain models. In this work, we propose a network calculus that can incorporate common statistical models of fading channels and obtain statistical bounds on delay and backlog across multiple nodes. We conduct the analysis in a transfer domain, which we refer to as the SNR domain, where the service process at a link is characterized by the instantaneous signal-to-noise ratio at the receiver. We discover that, in the transfer domain, the network model is governed by a dioid algebra, which we refer to as (min, ×) algebra. Using this algebra we derive the desired delay and backlog bounds. An application of the analysis is demonstrated for a simple multi-hop network with Rayleigh fading channels.

Capacity and buffer sizes are critical design parameters in schedulers which multiplex many flows. Previous studies show that in an asymptotic regime, when the number of traffic flows N goes to infinity, the choice of scheduling algorithm does not have a big impact on performance. We raise the question whether or not the choice of scheduling algorithm impacts the capacity and buffer sizing for moderate values of N (e.g., few hundred). For Markov-modulated On-Off sources and for finite N, we show that the choice of scheduling is influential on (1) buffer overflow probability, (2) capacity provisioning, and (3) the viability of network decomposition in a non-asymptotic regime. This conclusion is drawn based on numerical examples and by a comparison of the scaling properties of different scheduling algorithms. In particular, we show that the per-flow capacity converges to the per-flow long-term average rate of the arrivals with convergence speeds ranging from O (√log N/N) to O(1/N) depending on the scheduling algorithm. This speed of convergences of the required capacities for different schedulers (to meet a target buffer overflow probability) is perceptible even for moderate values of N in our numerical examples.

In many applications, the traffic traversing the network has interpacket dependencies due to application-level encoding schemes. For some applications, e.g., multimedia streaming, dropping a single packet may render useless the delivery of a whole sequence. In such environments, the algorithm used to decide which packet to drop in case of buffer overflows must be carefully designed, to avoid goodput degradation. We present a model that captures such interpacket dependencies, and design algorithms for performing packet discard. Traffic consists of an aggregation of multiple streams, each of which consists of a sequence of interdependent packets. We provide two guidelines for designing buffer management algorithms, and demonstrate their effectiveness. We devise an algorithm according to these guidelines and evaluate its performance analytically, using competitive analysis. We also perform a simulation study that shows that the performance of our algorithm is within a small fraction of the performance of the best known offline algorithm.

Traffic with self-similar and heavy-tailed characteristics has been widely reported in communication networks, yet, the state-of-the-art of analytically predicting the delay performance of such networks is lacking. This work addresses heavy-tailed traffic that has a finite first moment, but no second moment, and presents end-to-end delay bounds for such traffic. The derived performance bounds are non-asymptotic in that they do not assume a steady state, large buffer, or many sources regime. The analysis follows a network calculus approach where traffic is characterized by envelope functions and service is described by service curves. The system model is a multi-hop path of fixed-capacity links with heavy-tailed self-similar cross traffic at each node. A key contribution of the paper is a probabilistic sample-path bound for heavy-tailed arrival and service processes, which is based on a scale-free sampling method. The paper explores how delay bounds scale as a function of the length of the path, and compares them with lower bounds. A comparison with simulations illustrates pitfalls when simulating self-similar heavy-tailed traffic, providing further evidence for the need of analytical bounds.

We study how the choice of packet scheduling algorithms influences end-to-end performance on long network paths. Taking a network calculus approach, we consider both deterministic and statistical performance metrics. A key enabling contribution for our analysis is a significantly sharpened method for computing a statistical bound for the service given to a flow by the network as a whole. For a suitably parsimonious traffic model we develop closed-form expressions for end-to-end delays, backlog, and output burstiness. The deterministic versions of our bounds yield optimal bounds on end-to-end backlog and output burstiness for some schedulers, and are highly accurate for end-to-end delay bounds.

We develop a stochastic foundation for bandwidth estimation of networks with random service, where bandwidth availability is expressed in terms of bounding functions with a defined violation probability. Exploiting properties of a stochastic max-plus algebra and system theory, the task of bandwidth estimation is formulated as inferring an unknown bounding function from measurements of probing traffic. We derive an estimation methodology that is based on iterative constant rate probes. Our solution provides evidence for the utility of packet trains for bandwidth estimation in the presence of variable cross traffic. Taking advantage of statistical methods, we show how our estimation method can be realized in practice, with adaptive train lengths of probe packets, probing rates, and replicated measurements required to achieve both high accuracy and confidence levels. We evaluate our method in a controlled testbed network, where we show the impact of cross traffic variability on the time-scales of service availability, and provide a comparison with existing bandwidth estimation tools.

We seek to provide an analytical answer whether the impact of link scheduling algorithms on end-to-end delays diminishes on long network paths. The answer is provided through a detailed multi-hop delay analysis, which is applicable to a broad class of scheduling algorithms, and which can account for statistical multiplexing. The analysis is enabled by two contributions: (1) We derive a function that can characterize the available bandwidth at a buffered link for various scheduling algorithms. This characterization is sharp enough to provide necessary and sufficient conditions for satisfying worst-case delay bounds at a single link; (2) We obtain end-to-end delay bounds by solving an optimization problem, in which the service received on a multi-hop path is subsumed into a single function. Since our analysis captures the properties of a broad group of schedulers in a single parameter, it can provide insight how the choice of scheduling algorithms impacts end-to-end delay bounds. An important finding of this paper is that schedulers may exhibit noticeable performance differences which persist in a network setting with long paths.

We investigate scaling properties of end-to-end delays in packet networks for a flow that traverses a sequence ofHnodes and that experiences cross traffic at each node. When the traffic flow and the cross traffic do not satisfy independence assumptions, we find that delay bounds scale faster than linearly. More precisely, for exponentially bounded packetized traffic, we show that delays grow with Θ(HlogH) in the number of nodes on the network path. This superlinear scaling of delays is qualitatively different from the scaling behavior predicted by a worst-case analysis or by a probabilistic analysis assuming independence of traffic arrivals at network nodes.

We seek to provide an analytical answer whether the impact of the selection of link scheduling algorithms diminishes on long network paths. The answer is provided through a detailed multi-node delay analysis, which is applicable to a broad class of scheduling algorithms, and which can account for statistical multiplexing. The analysis is enabled by two contributions: (1) We derive a function that can characterize the available bandwidth at a node for various scheduling algorithms. The function has an accuracy that recovers necessary and sufficient conditions for satisfying worst-case delay bounds at a single node, (2) We obtain end-to-end delay bounds by providing an explicit solution to an optimization problem, in which the service received at multiple nodes is subsumed into a single function. By presenting a unified analysis that captures the properties of a broad group of schedulers in a single parameter, we can provide insight how the choice of scheduling algorithms impacts end-to-end delay bounds. An important finding of this paper is that some schedulers show noticeable performance differences which persist in a network setting with long paths.

Traffic with self-similar and heavy-tailed characteristics has been widely reported in networks, yet, only few analytical results are available for predicting the delay performance of such networks. We address a particularly difficult type of heavy-tailed traffic where only the first moment can be computed, and present the first non-asymptotic end-to-end delay bounds for such traffic. The derived performance bounds are non-asymptotic in that they do not assume a steady state, large buffer, or many sources regime. Our analysis considers a multi-hop path of fixed-capacity links with heavy-tailed self-similar cross traffic at each node. A key contribution of the analysis is a probabilistic sample-path bound for heavy-tailed arrival and service processes, which is based on a scale-free sampling method. We explore how delays scale as a function of the length of the path, and compare them with lower bounds. A comparison with simulations illustrates pitfalls when simulating self-similar heavy-tailed traffic, providing further evidence for the need of analytical bounds.

In many applications the traffic traversing the network has inter-packet dependencies due to application-level encoding schemes. For some applications, e.g., multimedia streaming, dropping a single packet may render useless the delivery of a whole sequence. In such environments, the algorithm used to decide which packet to drop in case of buffer overflows must be carefully designed, to avoid goodput degradation. We present a model that captures such inter-packet dependencies, and design algorithms for performing packet discards. Traffic consists of an aggregation of multiple streams, each of which consists of a sequence of inter-dependent packets. We provide two guidelines for designing buffer management algorithms for this problem, and demonstrate the effectiveness of these criteria. We devise an algorithm according to these guidelines and evaluate its performance analytically, using competitive analysis. We also present a simulation study that shows that the performance of our algorithm is within a small fraction of the performance of the best offline algorithm.

This paper presents a new foundational approach to reason about available bandwidth estimation as the analysis of a min-plus linear system. The available bandwidth of a link or complete path is expressed in terms of aservice curve, which is a function that appears in the network calculus to express the service available to a traffic flow. The service curve is estimated based on measurements of a sequence of probing packets or passive measurements of a sample path of arrivals. It is shown that existing bandwidth estimation methods can be derived in the min-plus algebra of the network calculus, thus providing further mathematical justification for these methods. Principal difficulties of estimating available bandwidth from measurements of network probes are related to potential nonlinearities of the underlying network. When networks are viewed as systems that operate either in a linear or in a nonlinear regime, it is argued that probing schemes extract the most information at a point when the network crosses from a linear to a nonlinear regime. Experiments on the Emulab testbed at the University of Utah, Salt Lake City, evaluate the robustness of the system-theoretic interpretation of networks in practice. Multinode experiments evaluate how well the convolution operation of the min-plus algebra provides estimates for the available bandwidth of a path from estimates of individual links.

Recent findings showing that the output of traffic flows at packet switches has similar characteristics as the corresponding input enable a decomposition analysis of a network where nodes can be studied in isolation, thus simplifying an end- to-end analysis of networks. However, network decomposition results currently available are mostly many-sources asymptotics. In this paper we explore the viability of network decomposition in a non-asymptotic regime with a finite number of flows. For traffic with Exponentially Bounded Burstiness (EBB) we derive statistical bounds for the output traffic at a FIFO buffer and compare them with bounds on the input. By evaluating the accuracy of the output bounds with exact results available for special cases and by using numerical examples we find that conditions for network decomposition appear favorable even if the number of flows is relatively small.

A recent result in network calculus theory provided statistical delay bounds for exponentially bounded traffic that grow as O(H log H) with the number of nodes on the network path. In this paper we establish the corresponding lower bound which shows that for such such types of traffic, typical end-to-end delays can indeed grow as Theta (H log H). The lower bound is obtained by analyzing the end-to-end delay in a tandem network where each packet maintains the same service time at each traversed node. The results of this paper provide conclusive evidence that, in general, delays have a qualitatively different scaling behavior than is suggested by a worst-case analysis or by an analysis that assumes independent service times at network nodes.

Significant research has been dedicated to methods that estimate the available bandwidth in a network from traffic measurements. While estimation methods abound, less progress has been made on achieving a foundational understanding of the bandwidth estimation problem. In this paper, we develop a min-plus system theoretic formulation of bandwidth estimation. We show that the problem as well as previously proposed solutions can be concisely described and derived using min-plus system theory, thus establishing the existence of a strong link between network calculus and network probing methods. We relate difficulties in network probing to potential non-linearities of the underlying systems, and provide a justification for the distinctive treatment of FIFO scheduling in network probing.

The network calculus offers an elegant framework for determining worst-case bounds on delay and backlog in a network. This paper extends the network calculus to a probabilistic framework with statistical service guarantees. The notion of a statistical service curve is presented as a probabilistic bound on the service received by an individual flow or an aggregate of flows. The problem of concatenating per-node statistical service curves to form an end-to-end (network) statistical service curve is explored. Two solution approaches are presented that can each yield statistical network service curves. The first approach requires the availability of time scale bounds at which arrivals and departures at each node are correlated. The second approach considers a service curve that describes service over time intervals. Although the latter description of service is less general, it is argued that many practically relevant service curves may be compliant to this description.

The stochastic network calculus is an evolving new methodology for backlog and delay analysis of networks that can account for statistical multiplexing gain. This paper advances the stochastic network calculus by deriving a network service curve, which expresses the service given to a flow by the network as a whole in terms of a probabilistic bound. The presented network service curve permits the calculation of statistical end-to-end delay and backlog bounds for broad classes of arrival and service distributions. The benefits of the derived service curve are illustrated for the exponentially bounded burstiness (EBB) traffic model. It is shown that end-to-end performance measures computed with a network service curve are bounded by /spl Oscr/(H log H), where H is the number of nodes traversed by a flow. Using currently available techniques, which compute end-to-end bounds by adding single node results, the corresponding performance measures are bounded by /spl Oscr/(H/sup 3/).

The stochastic network calculus is an evolving new methodology for backlog and delay analysis of networks that can account for statistical multiplexing gain. This paper advances the stochastic network calculus by deriving a network service curve, which expresses the service given to a flow by the network as a whole in terms of a probabilistic bound. The presented network service curve permits the calculation of statistical end-to-end delay and backlog bounds for broad classes of arrival and service distributions. The benefits of the derived service curve are illustrated for the exponentially bounded burstiness (EBB) traffic model. It is shown that end-to-end performance measures computed with a network service curve are bounded by O(Hlog H), where H is the number of nodes traversed by a flow. Using currently available techniques that compute end-to-end bounds by adding single node results, the corresponding performance measures are bounded by O(H3).

The Internet still lacks adequate support for QoS applications with real-time requirements. In great part, this is due to the fact that provisioning of end-to-end QoS to traffic that traverses multiple autonomous systems (ASs) requires a level of cooperation between ASs that is difficult to achieve in the current architecture. Recently, service overlay networks have been considered as an approach to QoS deployment that avoids these difficulties. In this study, we address the problem of the topological synthesis of a service overlay network, where endsystems and nodes of the overlay network (provider nodes) are connected through ISPs that supports bandwidth reservations. We express the topology design problem as an optimization problem. Even though the design problem is related to the (in general NP-hard) quadratic assignment problem, we are able to show that relatively simple heuristic algorithms can deliver results that are sometimes close to the optimal solution.

Scalability concerns of QoS implementations have stipulated service architectures where QoS is not provisioned separately to each flow, but instead to aggregates of flows. This paper determines stochastic bounds for the service experienced by a single flow when resources are managed for aggregates of flows and when the scheduling algorithms used in the network are not known. Using a recently developed statistical network calculus, per-flow bounds can be calculated for backlog, delay, and the burstiness of output traffic.

The Assured Forwarding (AF) service of the IETF DiffServ architecture provides a qualitative service differentiation between classes of traffic, in the sense that a low-priority class experiences higher loss rates and higher delays than a high-priority class. However, the AF service does not quantify the difference in the service given to classes. In an effort to strengthen the service guarantees of the AF service, we propose a Quantitative Assured Forwarding service with absolute and proportional differentiation of loss, service rates, and packet delays. We present a feedback-based algorithm which enforces the desired class-level differentiation on a per-hop basis, without the need for admission control or signaling. Measurement results from a testbed of FreeBSD PC-routers on a 100 Mbit/s Ethernet network show the effectiveness of the proposed service, and indicate that our implementation is suitable for networks with high data rates.

Application-layer multicast supports group applications without the need for a network-layer multicast protocol. Here, applications arrange themselves in a logical overlay network and transfer data within the overlay. We present an application-layer multicast solution that uses a Delaunay triangulation as an overlay network topology. An advantage of using a Delaunay triangulation is that it allows each application to locally derive next-hop routing information without requiring a routing protocol in the overlay. A disadvantage of using a Delaunay triangulation is that the mapping of the overlay to the network topology at the network and data link layer may be suboptimal. We present a protocol, called Delaunay triangulation (DT protocol), which constructs Delaunay triangulation overlay networks. We present measurement experiments of the DT protocol for overlay networks with up to 10 000 members, that are running on a local PC cluster with 100 Linux PCs. The results show that the protocol stabilizes quickly, e.g., an overlay network with 10 000 nodes can be built in just over 30 s. The traffic measurements indicate that the average overhead of a node is only a few kilobits per second if the overlay network is in a steady state. Results of throughput experiments of multicast transmissions (using TCP unicast connections between neighbors in the overlay network) show an achievable throughput of approximately 15 Mb/s in an overlay with 100 nodes and 2 Mb/s in an overlay with 1000 nodes.

Recently, application-layer multicast has emerged as an attempt to support group applications without the need for a network-layer multicast protocol, such as IP multicast. In application-layer multicast, applications arrange themselves as a logical overlay network and transfer data within the overlay network. In this paper, Delaunay triangulations are investigated as an overlay network topology for application-layer multicast. An advantage of Delaunay triangulations is that each application can locally derive next-hop routing information without the need for a routing protocol in the overlay. A disadvantage of a Delaunay triangulation as an overlay topology is that the mapping of the overlay to the network-layer infrastructure may be suboptimal. It is shown that this disadvantage can be partially addressed with a hierarchical organization of Delaunay triangulations. Using network topology generators, the Delaunay triangulation is compared to other proposed overlay topologies for application-layer multicast.

Previous work on differentiated services in the Internet has defined new notions of QoS that apply to aggregates of traffic in networks with coarse spatial granularity. Most proposals for differentiated services involve traffic control algorithms for aggregate service levels, packet marking and policing, and preferential treatment of unmarked packets in the network core. The issue of routing for enhancing aggregate QoS has not received a lot of attention. This study investigates the potential benefit of using alternate routing strategies in support of differentiated services. We propose a traffic control scheme, called simple alternate routing, wherein portions of unmarked packet flows can be assigned to alternate paths through a service provider network (SPN) in response to congestion feedback information. The scheme is simple, requiring only minor changes to the SPN border routers so that alternately routed packets can be tunneled via conventional paths to an intermediate border node and then tunneled from there to the original egress border node. We present distributed algorithms for (1) discovering congestion within the SPN, and (2) allocating traffic to alternate paths that are uncongested. We have implemented the scheme in a packet-level simulation, and we have examined the transient response of the algorithm to perturbations in the nominal traffic levels experienced by the SPN. The experimental study of this paper provides some understanding of the scheme's ability to adapt in routing packets around congestion. Our results indicate that the alternate routing framework shows promise and warrants further consideration.

A statistical network service which allows a certain fraction of traffic to not meet its QoS guarantees can extract additional capacity from a network by exploiting the statistical properties of the traffic. Here we consider a statistical service which assumes statistical independence of flows, but does not make any assumptions on the statistics of traffic sources, other than that they are regulated, e.g., by a leaky bucket. Under these conditions, we present functions, so-called local effective envelopes and global effective envelopes, which are, with high certainty, upper bounds of multiplexed traffic. We show that these envelopes can be used to obtain bounds on the amount of traffic on a link that can be provisioned with statistical QoS. A key advantage of our bounds is that they can be applied with a variety of scheduling algorithms. In fact, we show that one can reuse existing admission control functions that are available for scheduling algorithms with a deterministic service. We present numerical examples which compare the number of flows with statistical QoS guarantees that can be admitted with our effective envelope approach to those achieved with existing methods.

Network services for the most demanding advanced networked applications which require absolute, per-flow service assurances can be deterministic or statistical. By exploiting the statistical properties of traffic, statistical assurances can extract more capacity from a network than deterministic assurances. We consider statistical service assurances for traffic scheduling algorithms. We present functions, so-called effective envelopes, which are, with high certainty, upper bounds of multiplexed traffic. Effective envelopes can be used to obtain bounds on the amount of traffic on a link that can be provisioned with statistical service assurances. We show that our bounds can be applied to a variety of traffic scheduling algorithms. In fact, one can reuse existing admission control functions for scheduling algorithms with deterministic assurances. We present numerical examples which compare the number of flows with statistical assurances that can be admitted with our effective envelope approach to those achieved with existing methods.

In order to support quality-of-service (QoS) for real-time data communications such as voice, video and interactive services, multiaccess networks must provide an effective priority mechanism. The context of this work is the IEEE 802.14 standard for hybrid fiber coaxial (HFC) networks which has a shared upstream channel for transmissions from stations to the headend. This work presents a multilevel priority collision resolution scheme, which separates and resolves collisions between stations in a priority order, thereby, achieving the capability for preemptive priorities. We present a set of simulation scenarios which show the robustness and efficiency of the scheme, such as its ability to isolate higher priority traffic from lower priorities and to provide quick access to high-priority requests. In March 1998, a framework for handling priorities in the collision resolution process, which adopts a semantics similar to the semantics of our scheme, was included in the 802.14 standard.

All recently proposed packet-scheduling algorithms for output-buffered switches that support quality-of-service (QoS) transmit packets in some priority order, e.g., according to deadlines, virtual finishing times, eligibility times, or other time stamps that are associated with a packet. Since maintaining a sorted priority queue introduces significant overhead, much emphasis on QoS scheduler design is put on methods to simplify the task of maintaining a priority queue. In this paper, we consider an approach that attempts to approximate a sorted priority queue at an output-buffered switch. The goal is to trade off less accurate sorting for lower computational overhead. Specifically, this paper presents a scheduler that approximates the sorted queue of an earliest-deadline-first (EDF) scheduler. The approximate scheduler is implemented using a set of prioritized first-in/first-out (FIFO) queues that are periodically relabeled. The scheduler can be efficiently implemented with a fixed number of pointer manipulations, thus enabling an implementation in hardware. Necessary and sufficient conditions for the worst-case delays of the scheduler with approximate sorting are presented. Numerical examples, including traces based on MPEG video, demonstrate that in realistic scenarios, scheduling with approximate sorting is a viable option.

In order to provide quality of service (QoS) to users with real-time data such as voice, video and interactive services, the evolving IEEE 802.14 standard for hybrid fiber coaxial (HFC) networks must include an effective priority scheme. In this paper we investigate the ability of the current IEEE 802.14 specification to provide priority service and show that a preemptive scheduler is not a sufficient solution. We propose to augment the scheduler with a novel scheme for implementing priority access in an HFC random access environment. The proposed mechanism integrates a multilevel priority collision resolution system into the proposed IEEE 802.14 MAC. The scheme separates and resolves collisions between stations in a priority order. A set of simulation scenarios is presented that shows the robustness and efficiency of the protocol, such as its ability to isolate higher priorities from lower ones and provide quick access to high priority requests.

Large-scale multicast applications for the Internet require the availability of multicast protocols that enhance the basic connectionless IP multicast service. A critical requirement of such protocols in their ability to support a large group of simultaneous users. In this paper, we present a new approach for distributing control information within a multicast group. The goal of our approach is to scale to very large group sizes (in excess of 100,000 users). Multicast group members are organized as a logical n-dimensional hypercube, and all control information is transmitted along the edges of the hypercube. We analyze the scalability of the hypercube control topology and show that the hypercube balances the load per member for processing control information better than existing topologies.

There are many scenarios in which the same data must be delivered over a packet switched network to a large set of receivers. The Internet enables efficient multipoint transmissions through IP multicast by allowing data transmission to all receivers with a single send. Most approaches to scalable reliable multicast utilize receiver-oriented retransmissions. Defining an API for receiver-oriented reliable multicast is difficult because it is not clear how to manage the sender's cache and to schedule repairs. We outline an approach to defining an API based on logical cache persistence that addresses these problems. We also we explore the issues involved in defining an API for reliable multicast protocol on the Internet that can scale to millions of receivers.

A packet scheduler in a quality-of-service (QoS) network should be sophisticated enough to support stringent QoS constraints at high loads, but it must also have a simple implementation so that packets can be processed at the speed of the transmission link. The earliest-deadline-first (EDF) scheduler is the optimal scheduler for bounded-delay services in the sense that it provides the tightest delay guarantees of any scheduler, but an implementation of EDF requires the sorting of packets, a complex operation that is not practical for high-speed networks. In this study we present the design, implementation and analysis of the novel rotating-priority-queues/sup +/ (RPQ/sup +/) scheduler that is near-optimal in the sense that it can approximate EDF with arbitrary precision. The RPQ/sup +/ scheduler uses a set of prioritized FIFO queues whose priorities are rearranged (rotated) periodically to increase the priority of waiting packets. We derive admission control tests for RPQ/sup +/ and show that it has the following desirable properties: its implementation requires operations independent of the number of queued packets, it can provide worst-case delay guarantees, and its efficiency is "between" that of EDF and static-priority (SP) schedulers. We use numerical examples, including examples based on MPEG video, to show that in realistic scenarios RPQ/sup +/ can closely approximate EDF even for infrequent queue rotations.

The Available-Bit-Rate (ABR) service that is being standardized by the ATM Forum dynamically determines the maximum transmission rate, so-called explicit rate, of a connection. A drawback of the ABR control scheme for calculating the explicit rates is that it tries to allocate the same bandwidth to all ABR connections regardless of the application type of the connection. In this study a multi-level explicit rate scheme is proposed that can allocate different explicit rates for different classes of connections. ABR traffic is controlled at three levels. At the topmost level, bandwidth is dynamically regulated between CBR, VER, and ABR traffic sources. At the next level, bandwidth is controlled between different classes of ABR traffic. At the lowest level bandwidth is distributed among connections belonging to the same ABR traffic class. The effectiveness of the proposed scheme is demonstrated in simulation experiments.

One of the most important traffic types in future packet-switched networks is high-bandwidth, variable-bit-rate (VBR) video. Since video is a delay-sensitive media, the network must allocate resources to maintain quality-of-service (QoS) guarantees on throughput, delay, and delay jitter to video connections. A key component of resource allocation is the traffic characterization of video sources that determines the resources required to support video connections. In this study, we propose a method for characterizing VBR video traffic with a fixed number of leaky buckets in networks with a deterministic service. We explore tradeoffs of network utilization in two directions: (1) the number of leaky buckets used for traffic characterisation, and (2) the amount of information from a video sequence used to produce the characterization. We evaluate our method with a set of 30-minute long MPEG-compressed video traces.

To support the requirements for the transmission of continuous media, such as audio and video, multiservice packet-switching networks must provide service guarantees to connections, including guarantees on throughput, network delays, and network delay variations. For the most demanding applications, the network must offer a service which provides deterministically bounded delay guarantees, referred to as "bounded delay service." The admission control functions in a network with a bounded delay service require 'schedulability conditions' that detect violations of delay guarantees in a network switch. Exact schedulability conditions are presented for three packet scheduling methods: earliest-deadline-first (EDF), static-priority (SP), and a novel scheduling method, referred to as rotating-priority-queues (RPQ). By characterizing the worst-case traffic with general subadditive functions, the presented schedulability conditions can be applied to a large class of traffic models. Examples, which include actual MPEG video traces, are presented to demonstrate the trade-offs involved in selecting a packet scheduling method for a bounded delay service.

Compressed digital video is one of the most important traffic types in future integrated services networks. However, a network service that supports delay-sensitive video imposes many problems since compressed video sources are variable bit rate (VBR) with a high degree of burstiness. In this paper, we consider a network service that can provide deterministic guarantees on the minimum throughput and the maximum delay of VBR video traffic. A common belief is that due to the burstiness of VBR traffic, such a service will not be efficient and will necessarily result in low network utilization. We investigate the fundamental limits and trade-offs in providing deterministic performance guarantees to video and use a set of 10 to 30 min. long MPEG-compressed video traces for evaluation. Contrary to conventional wisdom, we are able to show that, in many cases, a deterministic service can be provided to video traffic while maintaining a reasonable level of network utilization. We first consider an ideal network environment that employs the most accurate deterministic, time-invariant video traffic characterizations, the optimal earliest-deadline-first packet schedulers, and exact admission control conditions. The utilization achievable in this situation provides the fundamental limits of a deterministic service. We then investigate the utilization limits in a network environment that takes into account practical constraints, such as the need for simple and efficient policing mechanisms, packet scheduling algorithms, and admission control tests.

A novel packet multiplexing technique, called rotating-priority-queues (RPQ), is presented which exploits the tradeoff between high efficiency, i.e., the ability to support many connections with delay bounds, and low complexity. The operations required by the RPQ multiplexer are similar to those of the simple, but inefficient, static-priority (SP) multiplexer. The overhead of RPQ, as compared to SP, consists of a periodic rearrangement (rotation) of the priority queues. It is shown that queue rotations can be implemented by updating a set of pointers. The efficiency of RPQ can be made arbitrarily close to the highly efficient, yet complex, earliest-deadline-first (EDF) multiplexer. Exact expressions for the worst case delays in an RPQ multiplexer are presented and compared to expressions for an EDF multiplexer.

A novel bandwidth regulation mechanism is proposed which improves the ability of a packet-switching network to cope with multiple real-time and non-real-time traffic classes. The mechanism achieves regulation of link bandwidth at two levels. At the first level, bandwidth is dynamically regulated between different traffic classes. The concept of 'inter-class regulation' is introduced which enforces that the bandwidth left unused by a traffic class is divided among traffic classes with high bandwidth demands. At the second level, bandwidth regulation is enforced on end-to-end traffic streams, so-called flows, such that flows from the same class with identical routes have the same throughput constraints. This concept is referred to as 'intra-class regulation'. A simple distributed protocol is presented that achieves a intra-class and inter-class regulation in a general internetwork. The effectiveness of the protocol is demonstrated by simulation experiments.

Compressed digital video is one of the most important traffic types in future integrated services networks. However, a network service that supports delay-sensitive video imposes many problems since compressed video sources are variable bit rate (VBR) with a high degree of burstiness. In this paper, we consider a network service that can provide deterministic guarantees on the minimum throughput and the maximum delay of VBR video traffic. A common belief is that due to the burstiness of VBR traffic, such a service will not be efficient and will necessarily result in low network utilization. We investigate the fundamental limits and tradeoffs in providing deterministic performance guarantees to video and use a set of 10 to 90 minute long MPEG-compressed video traces for evaluation. Contrary to conventional wisdom, we are able to show that, in many cases, a deterministic service can be provided to video traffic while maintaining a reasonable level of network utilization. We first consider an ideal network environment that employs the most accurate deterministic, time-invariant video traffic characterizations, Earliest-Deadline-First packet schedulers, and exact admission control conditions. The utilization achievable in this situation provides the fundamental limits of a deterministic service. We then investigate the utilization limits in a network environment that takes into account practical constraints, such as the need for fast policing mechanisms, simple packet scheduling algorithms, and efficient admission control tests.

Optimal scheduling of real-time tasks on multiprocessor systems is known to be computationally intractable for large task sets. Any practical scheduling algorithm for assigning real-time tasks to a multiprocessor system presents a trade-off between its computational complexity and its performance. In this study, new schedulability conditions are presented for homogeneous multiprocessor systems where individual processors execute the rate-monotonic scheduling algorithm. The conditions are used to develop new strategies for assigning real-time tasks to processors. The performance of the new strategies is shown to be significantly better than suggested by the existing literature. Under the realistic assumption that the load of each real-time task is small compared to the processing speed of each processor, it is shown that the processors can be almost fully utilized.

A new, unified approach towards the delay and error constraints that influence the quality of a digitized voice over asynchronous local computer networks is proposed. This approach, called Slack automatic repeat request (ARQ) (S-ARQ), proposes an extension of the control time mechanism for jitter control in order to provide error recovery through retransmissions in the case of packet losses in the network. While existing packet voice protocols do not use retransmission schemes, the authors' simulation studies indicate that extended control time can provide significant error coverage while remaining within the same order of magnitude as the control time required for jitter control. Simulation experiments reveal that the concept is clearly feasible within the end-to-end delay constraints in packet voice transmissions.

A protocol with strictly preemptive priorities that does not admit low-priority traffic if the load from high-priority traffic exceeds the capacity of the transmission channel in a MAN is presented. The protocol guarantees fairness for transmissions at the highest priority level. By introducing a general characterization of bandwidth allocation schemes for dual bus networks, existing priority mechanisms can be categorized according to the provided quality of service. The unique existence of a bandwidth allocation scheme for multiple priority traffic is shown with a full utilization of the channel capacity, with a fair distribution of bandwidth respective to traffic from a particular priority level, and with preemptive priorities. The performance of the presented protocol is compared to existing proposals for multiple priority mechanisms. It is shown that adopting the new protocol results in shorter access delays for high-priority transmissions. The protocol allows the stations of the network to react quickly to load changes. It is shown that the effectiveness of the priority scheme, compared to priority schemes using the bandwidth-balancing mechanism, is less dependent on increasing the transmission speed of the network.>

A media access protocol that achieves a fair distribution of the bandwidth in one round-trip delay is presented. The protocol is based on a unique solution to a fair and waste-free bandwidth allocation. This bandwidth allocation can be implemented in a distributed manner. A comparison of the new protocol with the DQDB (distributed queue dual bus) protocol shows considerable advantages regarding the transmission delay of messages and the time a station needs to obtain a fair portion of the available bandwidth. The advantages of the protocol become more apparent for large networks and high transmission speeds. In addition, the new protocol can perform nonuniform bandwidth allocations.>

An indexing scheme called partitioned global indexes (PGI) for a locally distributed database system is presented. The scheme builds a global index for the entire relation and partitions the index across the sites. A strategy for processing such an index is also presented. In order to evaluate the performance of the scheme, a simulation model is developed. The simulation results are compared to the classical scheme, called partial indexes (PI), in which corresponding index and data entries are stored at the same site. The advantages and disadvantages of the indexing schemes when processing conjuctive queries are analytically investigated. Analysis and simulation experiments show that tradeoffs between the new and the classical scheme.>

A protocol for dual bus networks that does not show the disadvantages inherent in the IEEE 802.6 standard for metropolitan area networks is proposed. The protocol obtains a fair distribution of bandwidth after a time equal to one round-trip delay and allows a full utilization of the available bandwidth. The protocol is derived from a fair and waste-free bandwidth allocation scheme. The features of the protocol can be included in the existing IEEE 802.6 standard. It is shown that the proposed protocol has significant performance advantages over the IEEE 802.6 standard.>

The IEEE 802.6 standard for Metropolitan Area Networks does not provide multiple priority traffic for connectionless data services. A priority mechanism that was considered for the standard showed to be not effective. As of now, there exists no protocol for multiple access dual bus networks that is able to implement pre-emptive priorites and, at the same time, can satisfy minimal fairness requirements for transmissions at the highest priority level. In this study, a protocol with strictly pre-emptive priorities, i.e., a protocol that does not admit low priority traffic if the load from high priority traffic exceeds the capacity of the transmission channel, is presented. The protocol is derived from a unique bandwidth allocation scheme with a full utilization of the bus capacity, with a fair distribution of bandwidth respective to traffic from a particular priority level and with pre-emptive priorities. The performance of the presented protocol is compared to a priority mechanism that is based on the bandwidth balancing mechanism. It is shown that adopting the new protocol results in shorter access delays for high priority transmissions.

The following configurations of interconnected networks are studied: (i) the gateways and the channels of local area networks have no buffer capacity constraints; (ii) only gateways have buffer capacity constraints; (iii) only the channels of local area networks have buffer capacity constraints; and (iv) both the gateways and the channels of the local area networks have buffer capacity constraints. An approximation method that makes it possible to compute the throughput for the above network configurations is introduced. Examples are given to demonstrate the effects of gateway buffer capacity on the performance of the network. Approximate results are validated by simulation.>

A method is developed which allows the application of Norton's theorem on queuing networks with finite capacities. A node is arbitrarily selected and the subnetwork containing all remaining nodes is replaced by a composite node with infinite capacity; thus the entire network is reduced to a two-node network having the node of interest and the composite node. Although blocking causes interdependencies between nodes in the network, the selected node is totally isolated from the rest of the network by constructing phases in the server which reflect the blocking events. An algorithm is given to compute the parameters of the phases. Several examples are discussed to demonstrate the efficiency and generality of the technique. Comparisons with simulation results show that the proposed technique provides accurate results for throughput values.>