The freshness of sensor data is critical for all types of cyber-physical systems. An established measure for quantifying data freshness is the Age-of-Information (AoI), which has been the subject of extensive research. Recently, there has been increased interest in multi-sensor systems: redundant sensors producing samples of the same physical process, sensors such as cameras producing overlapping views, or distributed sensors producing correlated samples. When the information from a particular sensor is outdated, fresh samples from other correlated sensors can be helpful. To quantify the utility of distant but correlated samples, we put forth a two-dimensional (2D) model of AoI that takes into account the sensor distance in an age-equivalent representation. Since we define 2D-AoI as equivalent to AoI, it can be readily linked to existing AoI research, especially on parallel systems. We consider physical phenomena modeled as spatio-temporal processes and derive the 2D-AoI for different Gaussian covariance kernels. For a basic exponential product kernel, we find that spatial distance causes an additive offset of the AoI, while for other kernels the effects of spatial distance are more complex and vary with time. Using our methodology, we evaluate the 2D-AoI of different spatial topologies and sensor densities.

An established policy for updating systems is zerowait: a source immediately sends a new sample as soon as the sink acknowledges the receipt of the previous one. The rationale of zero-wait is that with instantaneous feedback, the transmission of samples can fully utilize the forward link without ever causing a queue. However, this ideal behavior does not extend to multihop networks and two-way delay. One approach to generalize zero-wait for use in larger networks is message pipelining, where there is a fixed number of samples and acknowledgments $k \geq 1$ in the network at any time. We analyze the peak age-of-information of updating systems with pipelining in multi-hop networks with arbitrarily many queues in the forward and feedback paths. While pipelining improves network utilization, it also increases queuing delays, and the optimal degree k must strike a balance between the two. We show how this depends on the diameter and topology of the network, the presence of bottlenecks, and the statistical distribution of service times. In an a priori unknown and changing network, it is beneficial to adjust the pipelining adaptively. We demonstrate how basic delay-based congestion control can be effectively used to achieve this goal.

Age-of-information is a metric that quantifies the freshness of information obtained by sampling a remote sensor. In signal-agnostic sampling, sensor updates are triggered at certain times without being conditioned on the actual sensor signal. Optimal update policies have been researched and it is accepted that periodic updates achieve smaller age-of-information than random updates. We contribute a study of a signal-aware policy, where updates are triggered randomly by a defined sensor event. By definition, this implies random updates and as a consequence inferior age-of-information. Considering a notion of deviation-of-information as a signal-aware metric, our results show, however, that event-triggered systems can perform equally well as time-triggered systems while causing smaller mean network utilization. We use the stochastic network calculus to derive bounds of age- and deviation-of-information that are exceeded at most with a small, defined probability. We include simulation results that confirm the tail decay of the bounds. We also evaluate a hybrid time- and event-triggered policy where the event-triggered system is complemented by a minimal and a maximal update interval.

Models of parallel processing systems typically assume that one has$l$workers and jobs are split into an equal number of$k=l$tasks. Splitting jobs into$k > l$smaller tasks, i.e. using “tiny tasks”, can yield performance and stability improvements because it reduces the variance in the amount of work assigned to each worker, but as$k$increases, the overhead involved in scheduling and managing the tasks begins to overtake the performance benefit. We perform extensive experiments on the effects of task granularity on an Apache Spark cluster, and based on these, develop a four-parameter model for task and job overhead that, in simulation, produces sojourn time distributions that match those of the real system. We also present analytical results which illustrate how using tiny tasks improves the stability region of split-merge systems, and analytical bounds on the sojourn and waiting time distributions of both split-merge and single-queue fork-join systems with tiny tasks. Finally we combine the overhead model with the analytical models to produce an analytical approximation to the sojourn and waiting time distributions of systems with tiny tasks which include overhead. We also perform analogous tiny-tasks experiments on a hybrid multi-processor shared memory system based on MPI and OpenMP which has no load-balancing between nodes. Though no longer strict analytical bounds, our analytical approximations with overhead match both the Spark and MPI/OpenMP experimental results very well.

We consider networked sources that generate update messages with a defined rate and we investigate the age of that information at the receiver. Typical applications are in cyber-physical systems that depend on timely sensor updates. We phrase the age of information in the min-plus algebra of the network calculus. This facilitates a variety of models including wireless channels and schedulers with random cross-traffic, as well as sources with periodic and random updates, respectively. We show how the age of information depends on the network service where, e.g., outages of a wireless channel cause delays. Further, our analytical expressions show two regimes depending on the update rate, where the age of information is either dominated by congestive delays or by idle waiting. We find that the optimal update rate strikes a balance between these two effects.

Parallel systems divide jobs into smaller tasks that can be serviced by many workers at the same time. Some parallel systems have blocking barriers that require all of their tasks to start and/or depart in unison. This is true of many parallelized machine learning workloads, and the popular Apache Spark processing engine has recently added support for Barrier Execution Mode, which allows users to add such barriers to their jobs. The drawback of these barriers is reduced performance and stability compared to equivalent non-blocking systems.We derive analytical expressions for the stability regions for parallel systems with blocking start and/or departure barriers. We extend results from queueing theory to derive waiting and sojourn time bounds for systems with blocking start barriers. Our results show that for a given system utilization and number of servers, there is an optimal degree of parallelism that balances waiting time and job execution time. This observation leads us to propose and implement a class of self-adaptive schedulers, we call "Take-Half", that modulate the allowed degree of parallelism based on the instantaneous system load, improving mean performance and eliminating stability issues.

Models of parallel processing systems typically assume that one has l servers and jobs are split into an equal number of k = l tasks. This seemingly simple approximation has surprisingly large consequences for the resulting stability and performance bounds. In reality, best practices for modern mapreduce systems indicate that a job's partitioning factor should be much larger than the number of servers available, with some researchers going to far as to advocate for a "tiny tasks" regime, where jobs are split into over 10,000 tasks. In this paper we use recent advances in stochastic network calculus to fundamentally understand the effects of task granularity on parallel systems' scaling, stability, and performance. For the split-merge model, we show that when one allows for tiny tasks, the stability region is actually much better than had previously been concluded. For the single-queue fork-join model, we show that sojourn times quickly approach the optimal case when l "big tasks" are subdivided into k≫ l "tiny tasks". Our results are validated using extensive simulations, and the applicability of the models used is validated by experPiments on an Apache Spark cluster.

This paper investigates the behavior of several popular congestion control algorithms in LTE networks. Since TCP does not differentiate between different types of connections, the same loss-based congestion control algorithms are usually used with Ethernet, WiFi, and LTE. However, because packet losses are often concealed in LTE networks, the performance of such algorithms can be very poor, especially in mobile scenarios typical for LTE. We use measurements to analyze the behavior of these algorithms in a static case as well as a mobile scenario where the user equipment moves away from the eNodeB on a highway. In our measurements, we found that loss-based algorithms like Reno and CUBIC had trouble adjusting to quick changes of capacity due to their unawareness of packet losses, which also led to high delays. The combined delay- and loss-based approach of Compound TCP also performed poorly, as only the loss-based component was active most of the time. BBR (Bottleneck bandwidth and round-trip propagation time), a congestion control algorithm that adjusts its window based on changes in round-trip-times, was able to react to a changing capacity very quickly and therefore did not lead to additional delays like the other algorithms analyzed in this work.

In this paper, we consider a multi-access communication channel with many transmitters that randomly enter a channel and send their data to a receiver. The transmitters are not synchronized and the receiver does not send any feedback to the transmitters. We propose a Medium Access Control (MAC) protocol, which we call Multi-Access Spreading over Time (MAST). In this protocol, in order to mitigate the effects of user interference, each transmitter spreads its access over a time frame that is much larger than its encoded and modulated packet size. In order to perform this operation, the transmitters choose a spreading matrix from a set, which is known by all the transmitters and the receiver. We obtain the packet decoding probability analytically under user interference conditions, and substantiate our results with simulations. We finally compare the symbol-error probability performance of our protocol with the one of the Zig-zag protocol, and show that MAST outperforms the Zig-zag protocol under the same spreading conditions in both low and high signal-to-noise ratio regimes.

While steady-state solutions of backlog and delay have been derived for wireless systems, the analysis of transient phases still poses significant challenges. Considering the majority of short-lived and interactive flows, transient startup effects, as caused by sleep scheduling in cellular networks, have, however, a substantial impact on the performance. To facilitate reasoning about the transient behavior of systems, this paper contributes a notion of non-stationary service curves. Models of systems with sleep scheduling are derived and transient backlogs and delays are analyzed. Further, measurement methods that estimate the service of an unknown system from observations of selected probe traffic are developed. Fundamental limitations of existing measurement methods are explained by the non-convexity of the transient service and further difficulties are shown to be due to the super-additivity of network service processes. A novel two-phase probing technique is devised that first determines the shape of a minimal probe and subsequently obtains an accurate estimate of the unknown service. In a comprehensive measurement campaign, the method is used to evaluate the service of cellular networks with sleep scheduling (2G, 3G, and 4G), revealing considerable transient backlog and delay overshoots that persist for long relaxation times.

Parallel computing has become a standard tool with architectures such as Google MapReduce, Hadoop, and Spark being broadly used in applications such as data processing and machine learning. Common to these systems are a fork operation, where jobs are first divided into tasks that are processed in parallel, and a join operation where completed tasks wait for the other tasks of the job before leaving the system. The synchronization constraint of the join operation makes the analysis of fork-join systems challenging, and few explicit results are known. In this work, we formulate a max-plus server model for parallel systems which allows us to derive performance bounds for a variety of systems in the GII GI and G I G cases. We contribute end-to-end delay bounds for multi-stage fork-join networks. We perform a detailed comparison of different multi-server configurations, including an analysis of single-queue fork-join systems that achieve a fundamental performance gain. We compare these results to both simulation and a live Spark system.

In the context of continually growing data volumes, which have to be processed and transmitted in modern and future road traffic, the importance of the LTE technology will increase. While the extensively evaluated 802.11p standard shows its strength in regards to road safety applications, data-intensive comfort and infotainment services, which cause high data volume mainly in downlink direction, can best be provided by LTE. Therefore, the investigation of the download performance and availability is essential. In this paper, we present measurement results that evaluate how LTE's download speed is affected by relevant parameters. We perform two measurement campaigns in a major commercial LTE network. In a mobile scenario, we analyze position dependent parameters, such as frequency bands, the corresponding bandwidth, and the channel's signal quality, i.e., SINR and RSSI. Furthermore, a statistical performance evaluation provides insight into the parameters' impact on the download speed and their consistency in urban and rural areas. In addition, we compare the influence of main transport protocols, i.e., TCP and UDP. Finally, we identify diurnal and weekday dependent patterns. Concerning the download speeds in LTE, our results show on the one hand a higher spatial variability in cities and on the other hand that the signal quality and channel bandwidth are the most important influencing factors.

Closed-loop flow control protocols, such as the prominent implementation transmission control protocol (TCP), are prevalent in the Internet, today. TCP has continuously been improved for greedy traffic sources to achieve high throughput over networks with large bandwidth delay products. Recently, the increasing use for streaming and interactive applications, such as voice and video, has shifted the focus toward its delay performance. Given the need for real-time communication of non-greedy sources via TCP, we present an estimation method for performance evaluation of closed-loop flow control protocols. We characterize an end-to-end connection by a service curve that provides statistical guarantees for arbitrary traffic. The estimation is based on end-to-end measurements at the application level that include all effects induced by the network and by the protocol stacks of the end systems. From our measurements, we identify different causes for delays. We show that significant delays are due to queueing in protocol stacks. Notably, this occurs even if the utilization is moderate. Using our estimation method, we compare the impact of fundamental mechanisms of TCP on delays at the application level: in detail, we analyze parameters relevant for network dimensioning, including buffer provisioning and active queue management, and parameters for server configuration, such as the congestion control algorithm. By applying our method as a benchmark, we find that a good selection can largely improve the delay performance of TCP.

TCP is widely used for delay-sensitive applications including video streaming, voice, and instant messaging. Therefore, a performance parameter of interest is the end-to-end delay at the application level. In the past, much research was performed in the optimization of TCP's throughput. Besides throughput, delay is an important issue in todays networks. However, it was often disregarded. Amongst others, extensive queueing inside the network induces large delays that account for a significant share of the end-to-end delay. This phenomenon is termed bufferbloat. We show that another reason for extensive delays is queueing in the TCP stack that originates primarily from TCP's congestion control. We analyze this using the analogy of a queueing model for end-to-end delays from simulating TCP's congestion control mechanism. The causes of these delays could be identified and the connection between basic TCP mechanisms and network dimensioning and configuration is presented.

Parallel systems have received increasing attention with numerous recent applications such as fork-join systems, load-balancing, and l-out-of-k redundancy. Common to these systems is a join or resequencing stage, where tasks that have finished service may have to wait for the completion of other tasks so that they leave the system in a predefined order. These synchronization constraints make the analysis of parallel systems challenging and few explicit results are known. In this work, we model parallel systems using a max-plus approach that enables us to derive statistical bounds of waiting and sojourn times. Taking advantage of max-plus system theory, we also show end-to-end delay bounds for multi-stage fork-join networks. We contribute solutions for basic G|G|1 fork-join systems, parallel systems with load-balancing, as well as general (k, l) fork-join systems with redundancy. Our results provide insights into the respective advantages of l-out-of-k redundancy vs. load-balancing.

Closed-loop flow control protocols, such as the prominent implementation TCP, are prevalent in the Internet, today. TCP has continuously been improved for greedy traffic sources to achieve high throughput over networks with large bandwidth delay products. Recently, the increasing use for streaming and interactive applications, such as voice and video, has shifted the focus towards its delay performance. Given the need for real-time communication of non-greedy sources via TCP, we present an estimation method for performance evaluation of closed-loop flow control protocols. We characterize an end-to-end connection by a transfer function that provides statistical service guarantees for arbitrary traffic. The estimation is based on end-to-end measurements at the application level, that include all effects induced by the network and by the protocol stacks of the end systems. From our measurements, we identify different causes for delays. We show that significant delays are due to queueing in protocol stacks. Notably, this occurs even if the utilization is moderate. Using our estimation method, we compare the impact of fundamental mechanisms of TCP. In detail, we analyze buffer provisioning and its impact on delays at the application level. We find that a good selection can largely improve the delay performance of TCP.

We investigate instantaneous transmission rate strategies for secondary users in cognitive radio networks by analyzing their effective capacity performance in different signal-to-noise ratio regimes with different quality-of-service constraints and transmission block sizes. Describing a channel model with one secondary transmitter and one secondary receiver with the potential presence of primary users, we present an interference power constraint that limits the transmission power of secondary users not only when a channel is sensed as busy but also when a channel is sensed as idle. Calling the existing transmission rate strategy Optimistic Policy, we introduce two other strategies, particularly Conservative Policy and Greedy Policy. Secondary users in Optimistic Policy set the instantaneous transmission rate to the instantaneous mutual information assuming the correctness of channel sensing results, whereas they set the instantaneous transmission rate to the instantaneous mutual information regarding possible transmission outages in Conservative Policy and disregarding possible transmission outages in Greedy Policy. We construct a state transition diagram and formulate the effective capacity employing these policies. We calculate the minimum energy-per-bit requirements and the high signal-to-noise ratio slope in order to explore performance variations in low and high signal-to-noise ratio regimes, respectively. Correspondingly, we show that Optimistic Policy is, in general, more favorable in secondary users when the quality-of-service constraints are loose, the transmission blocks are shorter, and the signal-to-noise ratio is low. On the other hand, Conservative Policy is better when the quality-of-service constraints are strict, the transmission blocks are longer, and the signal-to-noise ratio is high.

Recent advances in free-viewpoint rendering techniques as well as the continued improvements of the internet network infrastructure open the door for challenging new applications. In this paper, we present a framework for interactive free-viewpoint streaming with open standards and software. Network bandwidth, encoding strategy as well as codec support for open source browsers are key constraints to be considered for our interactive streaming applications. Our framework is capable of real-time server-side rendering and interactively streaming the output by means of open source streaming. To enable viewer interaction with the free-viewpoint video rendering back-end in a standard browser, user events are captured with Javascript and transmitted using WebSockets. The rendered video is streamed to the browser using the FFmpeg free software project. This paper discusses the applicability of open source streaming and presents timing measurements for video-frame transmission over network.

Adaptive resource allocation arises naturally as a technique to optimize resource utilization in communication networks with scarce resources under dynamic conditions. One prominent example is cellular communication where service providers seek to utilize the costly resources in the most effective way. In this work, we investigate an uplink resource allocation scheme that takes into account the buffer occupation at the transmitter to retain a given level of quality of service (QoS). First, we regard exact results for the class of Poisson traffic where we investigate the sensitivity of the resource adaptation and QoS level to the actuating variables. We show relevant resource savings in comparison with a static allocation. Further, we regard a queueing setting with general random arrival and service processes. In particular, we consider the service of wireless fading channels. We show two different resource adaptation mechanisms that depend on the strictness of different assumptions. Finally, we present simulation results that show substantial resource savings using the queue-aware scheduling scheme, where we provide insight on the implementation and operation of such an adaptive system.

This paper develops a notion of capacity-delay-error (CDE) boundaries as a performance model of networked sources and systems. The goal is to provision effective capacities that sustain certain statistical delay guarantees with a small probability of error. We use a stochastic non-equilibrium approach that models the variability of traffic and service to formalize the influence of delay constraints on the effective capacity. Permitting unbounded delays, known ergodic capacity results from information theory are recovered in the limit. We prove that the model has the property of additivity, which enables composing CDE boundaries obtained for sources and systems as if in isolation. A method for construction of CDE boundaries is devised based on moment-generating functions, which includes the large body of results from the theory of effective bandwidths. Solutions for essential sources, channels, and respective coders are derived, including Huffman coding, MPEG video, Rayleigh fading, and hybrid automatic repeat request. Results for tandem channels and for the composition of sources and channels are shown.

Many of today's Internet applications such as mobile web browsing and live video streaming are delay and throughput sensitive. In face of the great success of cellular networking, especially with the advent of the high-speed LTE access tech-nology, it is noteworthy that there is little consensus on the performance experienced by applications running over cellular networks. In this paper we present application-level performance results measured in a major commercial LTE network. We replicate measurements in a wired access network to provide a reference for the wireless results. We investigate the performance of common web application scenarios over LTE. In addition, we deploy controlled measurement nodes to discover transparent middleboxes in the LTE network. The introduction of middle-boxes to LTE results in a faster connection establishment on the client side and notable performance gain for HTTP. However, this improvement comes at the price of ambiguity as some middlebox operations may introduce unnecessary timeouts. Further, we pinpoint LTE specific delays that arise from network signalling, energy saving algorithms and Hybrid Automatic Repeat reQuest (HARQ). Our analysis provides insights into the interaction between transport protocols and LTE.

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.

In packet switched networks, statistical multiplexing of independent variable bit rate flows achieves significant resource savings, i.e., N flows require considerably less than N times the resources needed for one flow. In this work, we explore statistical multiplexing using methods from the current stochastic network calculus, where we compare the accuracy of different analytical approaches. While these approaches are known to provide identical results for a single flow, we find significant differences if several independent flows are multiplexed. Recent results on the concatenation of nodes along a network path allow us to investigate both single- as well as multi-node networks with cross traffic. The analysis enables us to distinguish different independence assumptions between traffic flows at a single node as well as between cross traffic flows at consecutive nodes of a network path. We contribute insights into the scaling of end-to-end delay bounds in the number of nodes n of a network path under statistical independence. Our work is complemented by numerical applications, e.g., on access multiplexer dimensioning and traffic trunk management.

This paper establishes a link between information and queueing theory using an envelope-based approach. Unlike classical, equilibrium information theory, information envelopes focus on the dynamics of sources and coders, using functions of time that bound the number of bits generated. In the limit the information envelopes converge to the expected value and recover the entropy of a source, respectively, the average codeword length of a coder. In contrast, on short time scales and for sources with memory it is shown that large deviations from known equilibrium results occur with non-negligible probability. These can cause significant network delays. Using results from the stochastic network calculus, the envelopes yield a characterization of the operating points of source coders by the triplet of capacity, delay, and error. In the limit, assuming an optimal coder the required capacity approaches the entropy with arbitrarily small probability of error if infinitely large delays are permitted. We derive a corresponding characterization of channels and prove that the model has the desirable property of additivity, that allows analyzing sources and channels as if in isolation.

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.

Packet switched networks achieve significant re source savings due to statistical multiplexing. In this work we explore statistical multiplexing gains in single and multi-hop networks. To this end, we analyze performance metrics such as delay bounds for a through flow comparing different results from the stochastic network calculus. We distinguish different multiplexing gains that stem from independence assumptions between flows at a single hop as well as flows at consecutive hops of a network path. Further, we show corresponding numerical results. In addition to deriving the benefits of various statistical multiplexing models on performance bounds, we contribute insights into the scaling of end-to-end delay bounds in the number of hops not a network path under statistical independence.

Fractional Brownian motion (fBm) emerged as a useful model for self-similar and long-range dependent Internet traffic. Asymptotic, respectively, approximate performance measures are known from large deviations theory for single queuing systems with fBm traffic. In this paper we prove a rigorous sample path envelope for fBm that complements previous results. We find that both approaches agree in their outcome that overflow probabilities for fBm traffic have a Weibull tail. We show numerical results on the impact of the variability and the correlation of fBm traffic on the queuing performance.

Fractional Brownian motion (fBm) became known as a useful model for Internet traffic incorporating its self-similar and long-range dependent properties. In this paper we derive end-to-end performance bounds for a through flow in a network of tandem queues under fBm cross traffic. We build on a previously derived sample path envelope for fBm, which possesses a Weibullian decay of overflow probabilities. We employ the sample path envelope and the concept of leftover service curves to model the remaining service after scheduling fBm cross traffic at a system. Using composition results for tandem systems from the stochastic network calculus we derive end-to-end statistical performance bounds for individual flows in networks under fBm cross traffic. We discover that these bounds grow in O(n(log n)1/2-2H) for n systems in series where H is the Hurst parameter of the fBm cross traffic. We show numerical results on the impact of the variability and the correlation of fBm traffic on network performance.

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.

The distributed coordination function (DCF) aims at fair and efficient medium access in IEEE 802.11. In face of its success, it is remarkable that there is little consensus on the actual degree of fairness achieved, particularly bearing its impact on quality of service in mind. In this paper we provide an accurate model for the fairness of the DCF. Given M greedy stations we assume fairness if a tagged station contributes a share of 1/M to the overall number of packets transmitted. We derive the probability distribution of fairness deviations and support our analytical results by an extensive set of measurements. We find a closed-form expression for the improvement of long-term over short-term fairness. Regarding the random countdown values we quantify the significance of their distribution whereas we discover that fairness is largely insensitive to the distribution parameters. Based on our findings we view the DCF as emulating an ideal fair queuing system to quantify the deviations from a fair rate allocation. We deduce a stochastic service curve model for the DCF to predict packet delays in IEEE 802.11. We show how a station can estimate its fair bandwidth share from passive measurements of its traffic arrivals and departures.

Network calculus has proven as a valuable and versatile methodology for worst-case analysis of communication networks. One issue in which it is still lacking is the treatment of aggregate multiplexing, in particular if the FIFO property cannot be assumed when flows are merged. In this paper, we address the problem of bounding the delay of individual traffic flows in feed-forward networks under arbitrary multiplexing. Somewhat surprisingly, we find that direct application of network calculus results in loose bounds even in seemingly simple scenarios. The reasons for this "failure" of network calculus are discussed in detail and a method to arrive at tight delay bounds for arbitrary (aggregate) multiplexing is presented. This method is based on the solution of an optimization problem. For the special case of sink-tree networks this optimization problem is solved explicitly, thus arriving at a closed-form expression for the delay bound. Numerical experiments illustrate that in sink-tree networks the improvement over bounds based on direct application of network calculus can be considerable.

Variable bit rate encoding is considered to outper- form constant bit rate encoding with regard to compression gain and constancy of the video quality. The drawback is, however, that variable bit rate video streams usually exhibit a significant degree of burstiness which may result in poor multiplexing properties, buffer overflows, and large network delays. In this work we show how the explicit selection of slice mode types can effectively be used to generally avoid the use of large intracoded frames while still providing robustness against packet losses in the network. The employed encoding scheme provides a considerable smoothing of variable bit rate video traffic, resulting in less delay, less delay jitter, and less loss due to buffer overflows and late arrivals. It preserves the efficiency of variable bit rate video encoding, has little overhead, and is in accordance with current video coding standards.

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.

Network calculus is an established theory for deterministic quality of service analysis of fixed networks. Due to the failures inherent in fading channels it is, however, not applicable to radio systems. Emerging probabilistic equivalents allow closing this gap. Based on the recent network calculus with moment generating functions we present a methodology for performance analysis of fading channels. We use a service curve representation of radio links which facilitates an efficient analysis of radio networks. We investigate fading channels with memory and our results show that the fading speed impacts service guarantees significantly. Numerical performance bounds are provided for an example taken from cellular radio communications for which the effects of opportunistic scheduling are quantified. Simulation results are shown which confirm the efficiency of the approach.

Network calculus is a min-plus system theory for performance evaluation of queuing networks. Its elegance steins from intuitive convolution formulas for concatenation of deterministic servers. Recent research dispenses with the worst-case assumptions of network calculus to develop a probabilistic equivalent that benefits from statistical multiplexing. Significant achievements have been made, owing for example to the theory of effective bandwidths; however, the outstanding scalability set up by concatenation of deterministic servers has not been shown. This paper establishes a concise, probabilistic network calculus with moment generating functions. The presented work features closed-form, end-to-end, probabilistic performance bounds that achieve the objective of scaling linearly in the number of servers in series. The consistent application of moment generating functions put forth in this paper utilizes independence beyond the scope of current statistical multiplexing of flows. A relevant additional gain is demonstrated for tandem servers with independent cross-traffic

The application of queuing theory to communication systems often requires that the respective networks are of a feed-forward nature, that is they have to be cycle-free. An effective way to ensure this property is to prohibit the use of a certain set of turns, where a turn is a combination of two adjacent, consecutive links. Unfortunately, current routing algorithms are usually not equipped to handle forbidden turns and the required extensions are far from being trivial. In this paper we discuss the relevant issues for the example of the widely deployed Dijkstra algorithm. Then, we address the general case and present our Turnnet concept, which supports arbitrary combinations of routing algorithms with turn-prohibiting feed-forward mechanisms.

Grid computing requires network services beyond what is currently provided by the Best-Effort Internet. Among the different approaches towards network Quality of Service, aggregate scheduling, which maps micro-flows to a small number of different service classes, offers sufficient scalability up to the size of the Internet. The Differentiated Services architecture of the Internet Engineering Task Force is such an approach. Recently further Best-Effort like services have been proposed that are based on aggregate scheduling, like the less than Best-Effort Scavenger Service and the Alternative Best-Effort Service. In this paper we introduce the existing aggregate based approaches to Quality of Service. We take a heterogeneous mix of Transmission Control Protocol and User Datagram Protocol flows into account and complement services by adding transport protocol specific elements, if appropriate. In particular we show multi-class applications that are designed to apply a Guaranteed Rate Service and a Scavenger Service in parallel. Doing so we can show a performance gain and achieve a more economical use of the available resources without impacting responsive Best-Effort flows.

In this paper we describe the implementation of a network providing advanced services such as a Premium service that aims at providing low loss, low delay, and low delay jitter and an Olympic service that allows for a service differentiation in terms of delay within three additional classes. Our implementation of this network is based on the Differentiated Services Architecture, which is the most recent approach of the Internet Engineering Task Force towards quality of service. Access to service classes is controlled by a bandwidth broker, which can perform traffic engineering by means of multiprotocol label switching. The Premium service is implemented as expedited forwarding and the Olympic service as a group of assured forwarding per-hop-behavior. We present a thorough evaluation of the proposed services implemented by the careful assignment of micro-flows to a small set of per-hop behaviors.

Multimedia applications are becoming increasingly popular on the Internet. These include semi real-time applications like video playback, but also interactive applications with hard real-time requirements like Internet telephony or videoconferencing. Common to the real-time applications is an inevitable requirement for transmission services with certain guaranteed qualities. The differentiated services architecture aims at providing these services. A prioritized transmission, which is necessary in the case of real-time data, can be achieved by applying the expedited forwarding, defined as a premium service. Nevertheless, especially if current hierarchical video encoding techniques are used, great benefits can be gained by extending the expedited forwarding by different levels of forwarding guarantees. Doing so allows finely tuned reactions to congestion in the network, based on the importance of the individual data packets, which is given by the hierarchy of the video encoding layers. In this paper we present a queue management and scheduling model, which is the basis for a new differentiated services per hop behavior group. The per hop behavior group extends the expedited forwarding by certain forwarding guarantees, as already applied by the assured forwarding per hop behavior group. We show simulation results, which prove the usefulness of this extension, especially for the transmission of hierarchically encoded video streams.