Cyclic Queuing and Forwarding (CQF) is a mechanism defined by IEEE TSN for providing low jitter in a deterministic network. CQF uses a common time cycle and two buffers per node output port: during one cycle incoming packets are stored in one buffer while packets in the other buffer are being transmitted; at the end of a cycle, the roles of the two buffers are exchanged. The cycle start times are determined by a time offset that may be different for every output buffer. A guard band at both cycle ends is devised in order to compensate for misalignment and timing inaccuracies. The proper operation of CQF requires that the guard band and the offsets are computed such that nodes are sufficiently time-aligned. First, we give necessary and sufficient conditions for this to be guaranteed. The sufficient conditions lend themselves to tractable computations and we show that they are close to optimal. Our conditions account for nonideal clocks and non-zero propagation times; we show that accounting for these two elements does matter. Second, we give a method for computing the minimal duration of the guard band, given prior choices of time offsets. Third, a judicious choice of time offsets can considerably decrease the required duration of the guard band: we give a practical algorithm, based on a Mixed Integer Linear Program, for computing offsets that minimize the guard band. We illustrate our results on several CQF network topologies with or without cyclic dependencies.

In feed-forward time-sensitive networks with Deficit Round-Robin (DRR), worst-case delay bounds were obtained by combining Total Flow Analysis (TFA) with the strict service curve characterization of DRR by Tabatabaee et al. The latter is the best-known single server analysis of DRR, however the former is dominated by Polynomial-size Linear Programming (PLP), which improves the TFA bounds and stability region, but was never applied to DRR networks. We first perform the necessary adaptation of PLP to DRR by computing burstiness bounds per-class and per-output aggregate and by enabling PLP to support non-convex service curves. Second, we extend the methodology to support networks with cyclic dependencies: This raises further dependency loops, as, on one hand, DRR strict service curves rely on traffic characteristics inside the network, which comes as output of the network analysis, and on the other hand, TFA or PLP requires prior knowledge of the DRR service curves. This can be solved by iterative methods, however PLP itself requires making cuts, which imposes other levels of iteration, and it is not clear how to combine them. We propose a generic method, called PLP-DRR, for combining all the iterations sequentially or in parallel. We show that the obtained bounds are always valid even before convergence; furthermore, at convergence, the bounds are the same regardless of how the iterations are combined. This provides the best-known worst-case bounds for time-sensitive networks, with general topology, with DRR. We apply the method to an industrial network, where we find significant improvements compared to the state-of-the-art.

Total Flow Analysis (TFA) is a method for the worstcase analysis of time-sensitive networks. It uses service curve characterizations of the network nodes and arrival curves of flows at their sources; for tractability, the latter are often taken to be linear functions. For periodic flows, which are common in timesensitive networks, linear arrival curves are known to provide less good bounds than ultimately pseudo-periodic (UPP) arrival curves, which exactly capture the periodic behaviours. However, in existing tools, applying TFA with many flows and UPP curves quickly becomes intractable because when aggregating several UPP curves, the pseudo-period of the aggregate might become extremely large. We propose a solution to this problem, called Finite-Horizon TFA. The method computes finite horizons over which arrival and service curves can be restricted without affecting the end-results of TFA. It can be applied to networks with cyclic dependencies. We numerically show that, while remaining computationally feasible, the method significantly improves the bounds obtained by TFA when using linear curves.

A key metric to express the timeliness of status updates in latency-sensitive networked systems is the age of information (AoI), i.e., the time elapsed since the generation of the last received informative status message. This metric allows studying a number of applications including updates of sensory and control information in cyber-physical systems and vehicular networks as well as, job and resource allocation in cloud clusters. State-of-the-art approaches to analyzing the AoI rely on queueing models that are composed of one or many queuing systems endowed with service order, e.g., FIFO, LIFO, or last-generated-first-out order. A major difficulty arising in these analysis methods is capturing the AoI under message reordering when the delivery is non-preemptive and non-FIFO, i.e., when messages can overtake each other and the reception of informative messages may obsolete some messages that are underway. In this paper, we derive an exact formulation for the distribution of AoI in non-preemptive, non-FIFO systems where the main ingredients of our analysis are Palm calculus and time inversion. Owing to the rationality of the Laplace-Stieltjes transforms that are used in our approach, we obtain computable exact expressions for the distribution of AoI.

In time-sensitive networks, bounds on worst-case delays are typically obtained by using network calculus and assuming that flows are constrained by bit-level arrival curves. However, in IEEE TSN or IETF DetNet, source flows are constrained on the number of packets rather than bits. A common approach to obtain a delay bound is to derive a bit-level arrival curve from a packet-level arrival curve. However, such a method is not tight: we show that better bounds can be obtained by directly exploiting the arrival curves expressed at the packet level. Our analysis method also obtains better bounds when flows are constrained with g-regulation, such as the recently proposed Length-Rate Quotient rule. It can also be used to generalize some recently proposed network-calculus delay-bounds for a service curve element with known transmission rate.

Time-sensitive networks (IEEE TSN or IETF DetNet) may tolerate some packet reordering. Re-sequencing buffers are then used to provide in-order delivery, the parameters of which (timeout, buffer size) may affect worst-case delay and delay jitter. There is so far no precise understanding of per-flow reordering metrics nor of the dimensioning of re-sequencing buffers in order to provide worst-case guarantees, as required in such networks. First, we show that a previously proposed per-flow metric, reordering late time offset (RTO), determines the timeout value. If the network is lossless, another previously defined metric, the reordering byte offset (RBO), determines the required buffer. If packet losses cannot be ignored, the required buffer may be larger than RBO, and depends on jitter, an arrival curve of the flow at its source, and the timeout. Then we develop a calculus to compute the RTO for a flow path; the method uses a novel relation with jitter and arrival curve, together with a decomposition of the path into non order-preserving and order-preserving elements. We also analyse the effect of re-sequencing buffers on worst-case delay, jitter and propagation of arrival curves. We show in particular that, in a lossless (but non order-preserving) network, re-sequencing is “for free”, namely, it does not increase worst-case delay nor jitter, whereas in a lossy network, re-sequencing increases the worst-case delay and jitter. We apply the analysis to evaluate the performance impact of placing re-sequencing buffers at intermediate points and illustrate the results on two industrial test cases.

Dampers are devices that reduce delay jitter in the context of time-sensitive networks, by delaying packets for the amount written in packet headers. Jitter reduction is required by some real-time applications; beyond this, dampers have the potential to solve the burstiness cascade problem of deterministic networks in a scalable way, as they can be stateless. Dampers exist in several variants: some apply only to earliest-deadline-first schedulers, whereas others can be associated with any packet schedulers; some enforce FIFO ordering whereas some others do not. Existing analyses of dampers are specific to some implementations and some network configurations; also, they assume ideal, non-realistic clocks. In this paper, we provide a taxonomy of all existing dampers in general network settings and analyze their timing properties in presence of non-ideal clocks. In particular, we give formulas for computing residual jitter bounds of networks with dampers of any kind. We show that non-FIFO dampers may cause reordering due to clock non-idealities and that the combination of FIFO dampers with non-FIFO network elements may very negatively affect the performance bounds. Our results can be used to analyze timing properties and burstiness increase in any time-sensitive network, as we illustrate on an industrial case-study.

Deficit Round-Robin (DRR) is a widespread scheduling algorithm that provides fair queueing with variable-length packets. Bounds on worst-case delays for DRR were found by Boyer et al., who used a rigorous network calculus approach and characterized the service obtained by one flow of interest by means of a convex strict service curve. These bounds do not make any assumptions on the interfering traffic hence are pessimistic when the interfering traffic is constrained by some arrival curves. For such cases, two improvements were proposed. The former, by Soni et al., uses a correction term derived from a semi-rigorous heuristic; unfortunately, these bounds are incorrect, as we show by exhibiting a counter-example. The latter, by Bouillard, rigorously derive convex strict service curves for DRR that account for the arrival curve constraints of the interfering traffic. In this paper, we improve on these results in two ways. First, we derive a non-convex strict service curve for DRR that improves on Boyer et al. when there is no arrival constraint on the interfering traffic. Second, we provide an iterative method to improve any strict service curve (including Bouillard’s) when there are arrival constraints for the interfering traffic. As of today, our results provide the best-known worst-case delay bounds for DRR. They are obtained by using the method of the pseudo-inverse.

Packet replication and elimination functions are used by time-sensitive networks (as in the context of IEEE TSN and IETF DetNet) to increase the reliability of the network. Packets are replicated onto redundant paths by a replication function. Later the paths merge again and an elimination function removes the duplicates. This redundancy scheme has an effect on the timing behavior of time-sensitive networks and many challenges arise from conducting timing analyses. The replication can induce a burstiness increase along the paths of replicates, as well as packet mis-ordering that could increase the delays in the crossed bridges or routers. The induced packet mis-ordering could also negatively affect the interactions between the redundancy and scheduling mechanisms such as traffic regulators (as with per-flow regulators and interleaved regulators, implemented by TSN asynchronous traffic shaping). Using the network calculus framework, we provide a method of worst-case timing analysis for time-sensitive networks that implement redundancy mechanisms in the general use case, i.e., at end-devices and/or intermediate nodes. We first provide a network calculus toolbox for bounding the burstiness increase and the amount of reordering caused by the elimination function of duplicate packets. We then analyze the interactions with traffic regulators and show that their shaping-for-free property does not hold when placed after a packet elimination function. We provide a bound for the delay penalty when using per-flow regulators and prove that the penalty is not bounded with interleaved regulators. Finally, we use an industrial use-case to show the applicability and the benefits of our findings.

Deficit Round-Robin (DRR) is a widespread scheduling algorithm that provides fair queueing with variable-length packets. Bounds on worst-case delays obtained with DRR were found by Boyer et al. They used a rigorous network calculus approach and characterized the service obtained by one flow of interest by means of a strict service curve. These bounds do not make any assumptions on the interfering traffic flows hence are pessimistic when the interfering traffic is constrained by some arrival curves. For such cases, Soni et al. improved the worstcase delay bounds by a correction term that accounts for arrival curve constraints of interfering traffic, using a semi-rigorous approach. Unfortunately, these latter bounds are incorrect, as we show by exhibiting a counter-example. Then we derive new service curves for DRR, which are rigorously proven, and we account for arrival curve constraints of interfering traffic. Hence, the resulting delay bounds are guaranteed to be correct. Furthermore, we find numerically that they are smaller than the incorrect ones obtained with the method of Soni et al. These bounds also improve on the results by Boyer et al. when there is no constraint on interfering traffic. Therefore, as of today, they are the best known delay bounds for DRR. Our results are obtained by applying the method of the pseudo-inverse.

In this paper, we focus on the localization of a passive source from time difference of arrival (TDOA) measurements. TDOA values are computed with respect to pairs of fixed sensors that are required to be accurately time-synchronized. This constitutes a weakness as all synchronization techniques are vulnerable to delay injections. Attackers are able either to spoof the signal or to inject asymmetric delays in the communication channel. By nature, TDOA measurements are highly sensitive to time-synchronization offsets between sensors. We first illustrate that time-synchronization attacks can severely affect the localization process. With a delay of a few microseconds injected on one sensor, the resulting estimate might be several kilometers away from the true location of the unknown source. We show that residual analysis does not enable the detection and identification of time-synchronization attacks. Our main contribution is then to propose a two-step TDOA-localization technique that is robust against time-synchronization attacks. It uses a known source to define a weight for each pair of sensors, reflecting the confidence in their time synchronization. Our solution then uses the weighted least-squares estimator with the newly created weights and the TDOA measurements received from the unknown source. As a result, our method either identifies the network as being too corrupt to localize, or gives a corrected estimate of the unknown position along with a confidence metric. Numerical results illustrate the performance of our technique.

For time-sensitive networks, as in the context of IEEE TSN and IETF Detnet, cyclic dependencies are associated with certain fundamental properties such as improving availability and decreasing reconfiguration effort. Nevertheless, the existence of cyclic dependencies can cause very large latency bounds or even global instability, thus making the proof of the timing predictability of such networks a much more challenging issue. Cyclic dependencies can be removed by reshaping flows inside the network, by means of regulators. We consider FIFO-per-class networks with two types of regulators: perflow regulators and interleaved regulators (the latter reshape entire flow aggregates). Such regulators come with a hardware cost that is less for an interleaved regulator than for a perflow regulator; both can affect the latency bounds in different ways. We analyze the benefits of both types of regulators in partial and full deployments in terms of latency. First, we propose Low-Cost Acyclic Network (LCAN), a new algorithm for finding the optimum number of regulators for breaking all cyclic dependencies. Then, we provide another algorithm, Fixed- Point Total Flow Analysis (FP-TFA), for computing end-to-end delay bounds for general topologies, i.e., with and without cyclic dependencies. An extensive analysis of these proposed algorithms was conducted on generic grid topologies. For these test networks, we find that FP-TFA computes small latency bounds; but, at a medium to high utilization, the benefit of regulators becomes apparent. At high utilization or for high line transmission-rates, a small number of per-flow regulators has an effect on the latency bound larger than a small number of interleaved regulators. Moreover, interleaved regulators need to be placed everywhere in the network to provide noticeable improvements. We validate the applicability of our approaches on a realistic industrial timesensitive network.

Real-time control systems (RTCSs) perform complex control and require low response times. They typically use third-party software libraries and are deployed on generic hardware, which suffer from delay faults that can cause serious damage. To improve availability and latency, the controllers in RTCSs are replicated on physical nodes. As physical replication is expensive, we study the alternative of exploiting virtualization technology to run multiple virtual replicas on the same physical node. As virtual replicas share the same resources, the delay faults they experience might be correlated, which would make such a replication method unsuitable. We conduct several experiments with an RTCS for electric grids, with multiple virtual replicas of its controller. We find that although the delay of a virtual machine is higher than of a physical machine, the correlation between high delays among the virtual replicas is insignificant, causing an overall improved availability. We conclude that virtual replication is indeed applicable to certain RTCSs, as it can improve reliability without added cost.

Real-time control systems use controllers that compute and issue setpoints within stringent delay constraints. Failure to do so, due to a crash or delay as a result of software and/or hardware faults, can cause failure of the controlled resources. Recently, Axo, a protocol for masking crash and delay faults by replicating the controller, was proposed. Axo provides safety by discarding delayed setpoints, and it relies on the presence of valid setpoints for providing availability. To ensure that enough valid setpoints are issued, faulty controller replicas need to be detected and recovered. We present a mechanism for detection and recovery of delay- and crash-faulty replicas under the Axo framework. These mechanisms were designed to be soft state (i.e., their state can be reconstructed from received messages) to enable seamless additions of new replicas. Besides presenting the design, we analytically characterize the time to detect and recover a faulty replica, and we validate them experimentally. We demonstrate the performance of Axo by using two case studies: the first provides a stability analysis of an inverted pendulum system with Axo, and the second shows the fault-tolerance performance of Axo through a deployment on a real-time control system that controls a CIGRÉ low-voltage benchmark microgrid.

The existing approaches to control electrical grids combine frequency and voltage controls at different time-scales. When applied in microgrids with stochastic distributed generation, grid quality of service problems may occur, such as under- or overvoltages as well as congestion of lines and transformers. The COMMELEC framework proposes to solve this compelling issue by performing explicit control of power flows with two novel strategies: 1) a common abstract model is used by resources to advertise their state in real time to a grid agent; and 2) subsystems can be aggregated into virtual devices that hide their internal complexity in order to ensure scalability. While the framework has already been published in the literature, in this paper, we present the first experimental validation of a practicable explicit power-flow primary control applied in a real-scale test-bed microgrid. We demonstrate how an explicit power-flow control solves the active and reactive power sharing problem in real time, easily allowing the microgrid to be dispatchable in real time (i.e., it is able to participate in energy markets) and capable of providing frequency support, while always maintaining quality of service.

We introduce Pi-regulation, a new definition of traffic regulation which extends both the arrival curves of network calculus and Chang's max-plus g-regulation, and also includes new types of regulation, such as packet rate limitations. We provide a new exact equivalence between min-plus and max-plus formulations of traffic regulation. We show the existence and a max-plus representation of per-flow minimal regulators, which extends the concepts of packetized greedy shapers and minimal g-regulators. We show that any minimal regulator, placed after any arbitrary system that is FIFO for the flow of interest, does not increase the worst-case delay of the flow. We extend the theory to interleaved regulation and introduce the concept of minimal interleaved regulator. It generalizes the urgency-based shaper that was recently proposed by Specht and Samii as a simpler alternative to per-flow regulators in deterministic networks with aggregate scheduling. With this regulator, packets of multiple flows are processed in one FIFO queue and only the packet at the head of the queue is examined against the regulation constraints of its flow. We show that any minimal interleaved regulator, placed after any arbitrary FIFO system does not increase the worst-case delay of the combination.

Multiple software agents can be used to perform the real-time control of electrical grids. The control performance of such solutions is influenced by software non-idealities such as crashes and delays of the software agents, and message losses and delays due to the underlying communication network. To study the effect of these non-idealities on control systems, we present an open-source software testbed, named T-RECS. It uses software containers to test existing software without modification. The communication network among the software containers is emulated using Mininet framework, which allows for real packets being exchanged. The electric resources in the grid are simulated using state-of-the-art models, whereas the grid itself is modeled in the phasor domain. As control agents are run as is and message exchanges are emulated, T-RECS accurately captures the real-world properties of the control framework. We demonstrate the working of T-RECS with the Commelec control framework and show the effect of network non-idealities on the control performance. We make a beta version available.

Real-time control systems (RTCSs) tolerate delay and crash faults by replicating the controller. Each replica computes and issues setpoints to actuators over a network that might drop or delay messages. Hence, the actuators might receive an inconsistent set of setpoints. Such inconsistency is avoided either by having a single primary replica compute and issue setpoints (in passive replication) or a consensus algorithm select one sending-replica (in active replication). However, due to the impossibility of a perfect failure-detector, passive-replication schemes can have multiple primaries, causing inconsistency, especially in the presence of intermittent delay faults. Furthermore, the impossibility of bounded-latency consensus causes both schemes to have poor real-time performance. We identified three properties of RTCSs that enable active-replication schemes to agree on the measurements before computing, instead of using traditional consensus. As all computing replicas compute with the same state, the resulting setpoints are guaranteed to be consistent. We present the design of Quarts, an agreement solution for active replication that guarantees consistency and bounded latency-overhead. We prove the guarantees and compare the performance of Quarts with existing solutions through simulation. We show that Quarts provides an availability higher than existing solutions, and that the availability improvement is up to 10x with two replicas.

We consider real-time control systems that consist of a controller that computes and sends setpoints to be implemented in physical processes through process agents. We focus on systems that use commercial off-the-shelf hardware and software components. Setpoints of these systems have strict real-time constraints: Implementing a setpoint after its deadline, or not receiving setpoints within a deadline, can cause failure. In this paper, we address delay faults: faults that cause setpoints to violate their real-time constraints. We present Axo, a fault-tolerance protocol that guarantees safety and improves availability for a class of such systems that exhibit two main properties: the setpoints must have a known validity horizon, and process agents must be capable of handling duplicate setpoints. To reason about delay faults, and consequently design Axo, we present an abstraction of a controller; the abstraction applies to a wide range of real-time control systems. We prove guarantees of safety and availability. Finally, we present an implementation of Axo and the results of the tests performed with Commelec, a real-time control system for electric grids.

Reliable packet delivery within stringent delay constraints is of paramount importance to mission-critical computer applications with hard real-time constraints. Because retransmission and coding techniques counteract the delay requirements, reliability may be achieved through replication over multiple fail-independent paths. The existing solutions, such as the parallel redundancy protocol (PRP), replicate all packets at the media access control layer over parallel paths. PRP works best in local area networks; however, it is not viable for IP networks that are a key element of emerging mission-critical systems. This limitation, coupled with diagnostic inability and lack of security, renders PRP unsuitable for reliable data delivery in these IP networks. To address this issue, we present a transport-layer solution: the IP parallel redundancy protocol (iPRP). Designing iPRP poses nontrivial challenges in the form of selective packet-replication, and soft-state and multicast support. iPRP replicates only time-critical unicast or multicast user datagram protocol traffic. iPRP requires no modifications to the existing monitoring application, end-device operating system, or to the intermediate network devices. It only requires a simple software installation on the end devices. iPRP has a set of diagnostic tools for network debugging. With our implementation of iPRP in Linux, we show that iPRP supports multiple flows with minimal processing-and-delay overhead. It is being installed in our campus smart-grid network and is publicly available.

Reliable packet delivery within stringent delay constraints is of primal importance to industrial processes with hard real-time constraints, such as electrical grid monitoring. Because retransmission and coding techniques counteract the delay requirements, reliability is achieved through replication over multiple fail-independent paths. Existing solutions such as parallel redundancy protocol (PRP) replicate all packets at the MAC layer over parallel paths. PRP works best in local area networks, e.g., sub-station networks. However, it is not viable for IP layer wide area networks which are a part of emerging smart grids. Such a limitation on scalability, coupled with lack of security, and diagnostic inability, renders it unsuitable for reliable data delivery in smart grids. To address this issue, we present a transport-layer design: IP parallel redundancy protocol (iPRP). Designing iPRP poses non-trivial challenges in the form of selective packet replication, soft-state and multicast support. Besides unicast, iPRP supports multicast, which is widely using in smart grid networks. It duplicates only time-critical UDP traffic. iPRP only requires a simple software installation on the end-devices. No other modification to the existing monitoring application, end-device operating system or intermediate network devices is needed. iPRP has a set of diagnostic tools for network debugging. With our implementation of iPRP in Linux, we show that iPRP supports multiple flows with minimal processing and delay overhead. It is being installed in our campus smart grid network and is publicly available.

Multipath TCP (MPTCP) has been proposed recently as a mechanism for transparently supporting multiple connections to the application layer. It is under discussion at the IETF. We nevertheless demonstrate that the current MPTCP suffers from two problems: P1) Upgrading some TCP users to MPTCP can reduce the throughput of others without any benefit to the upgraded users, which is a symptom of not being Pareto-optimal; and P2) MPTCP users could be excessively aggressive toward TCP users. We attribute these problems to the linked-increases algorithm (LIA) of MPTCP and, more specifically, to an excessive amount of traffic transmitted over congested paths. The design of LIA forces a tradeoff between optimal resource pooling and responsiveness. We revisit the problem and show that it is possible to provide these two properties simultaneously. We implement the resulting algorithm, called the opportunistic linked-increases algorithm (OLIA), in the Linux kernel, and we study its performance over our testbed by simulations and by theoretical analysis. We prove that OLIA is Pareto-optimal and satisfies the design goals of MPTCP. Hence, it can avoid the problems P1 and P2. Our measurements and simulations indicate that MPTCP with OLIA is as responsive and nonflappy as MPTCP with LIA and that it solves problems P1 and P2.

The mainstream approach to protecting the location-privacy of mobile users in location-based services (LBSs) is to alter the users' actual locations in order to reduce the location information exposed to the service provider. The location obfuscation algorithm behind an effective location-privacy preserving mechanism (LPPM) must consider three fundamental elements: the privacy requirements of the users, the adversary's knowledge and capabilities, and the maximal tolerated service quality degradation stemming from the obfuscation of true locations. We propose the first methodology, to the best of our knowledge, that enables a designer to find the optimal LPPM for a LBS given each user's service quality constraints against an adversary implementing the optimal inference algorithm. Such LPPM is the one that maximizes the expected distortion (error) that the optimal adversary incurs in reconstructing the actual location of a user, while fulfilling the user's service-quality requirement. We formalize the mutual optimization of user-adversary objectives (location privacy vs. correctness of localization) by using the framework of Stackelberg Bayesian games. In such setting, we develop two linear programs that output the best LPPM strategy and its corresponding optimal inference attack. Our optimal user-centric LPPM can be easily integrated in the users' mobile devices they use to access LBSs. We validate the efficacy of our game theoretic method against real location traces. Our evaluation confirms that the optimal LPPM strategy is superior to a straightforward obfuscation method, and that the optimal localization attack performs better compared to a Bayesian inference attack.

MPTCP has been proposed recently as a mechanism for supporting transparently multiple connections to the application layer. It is under discussion at the IETF. We show, however, that the current MPTCP suffers from two problems: (P1) Upgrading some TCP users to MPTCP can reduce the throughput of others without any benefit to the upgraded users, which is a symptom of not being Pareto-optimal; and (P2) MPTCP users could be excessively aggressive towards TCP users. We attribute these problems to the linked-increases algorithm (LIA) of MPTCP and, more specifically, to an excessive amount of traffic transmitted over congested paths.

Contact-based simulations are a very popular tool for the analysis of opportunistic networks. They are used for evaluation of networking metrics, for quantifying the effects of infrastructure and for the design of forwarding strategies. However, little evidence exists that the results of such simulations accurately describe the performance of opportunistic networks, as they commonly ignore some important factors (like limited transmission bandwidth) or they rely on assumptions such as infinite user cache sizes. In order to evaluate this issue, we design a testbed with a real application and real users; we collect application data in addition to the contact traces and compare measured performance to the results of the contact-based simulations. We find that contact-based simulations significantly overestimate delivery ratio, while the captured delay tends to be 2-3 times lower than the experimentally obtained delay. We show that assuming infinite cache sizes leads to misinterpretation of the effects of backbone on an opportunistic network. Finally, we show that contact traces can be used to analytically estimate the delivery ratios and the impact of backbone, through the dependency between a user centrality measure and her delivery ratio.

Performance evaluation of the 802.11 MAC protocol is classically based on the decoupling assumption, which hypothesizes that the backoff processes at different nodes are independent. This decoupling assumption results from mean field convergence and is generally true in transient regime in the asymptotic sense (when the number of wireless nodes tends to infinity), but, contrary to widespread belief, may not necessarily hold in stationary regime. The issue is often related with the existence and uniqueness of a solution to a fixed point equation; however, it was also recently shown that this condition is not sufficient; in contrast, a sufficient condition is a global stability property of the associated ordinary differential equation. In this paper, we give a simple condition that establishes the asymptotic validity of the decoupling assumption for the homogeneous case (all nodes have the same parameters). We also discuss the heterogeneous and the differentiated service cases and formulate a new ordinary differential equation. We show that the uniqueness of a solution to the associated fixed point equation is not sufficient; we exhibit one case where the fixed point equation has a unique solution but the decoupling assumption is not valid in the asymptotic sense in stationary regime.

To provide high ranging precision in multipath environments, a ranging protocol should find the first arriving path, rather than the strongest path. We demonstrate a new attack vector that disrupts such precise Time-of-Arrival (ToA) estimation, and allows an adversary to decrease the measured distance by a value in the order of the channel spread (10-20 meters). This attack vector can be used in previously reported physical-communication-layer (PHY) attacks against secure ranging (or distance bounding). Furthermore, it creates a new type of attack based on malicious interference: This attack is much easier to mount than the previously known external PHY attack (distance-decreasing relay) and it can work even if secret preamble codes are used. We evaluate the effectiveness of this attack for a PHY that is particularly well suited for precise ranging in multipath environments: Impulse Radio Ultra-Wideband (IR-UWB). We show, with PHY simulations and experiments, that the attack is effective against a variety of receivers and modulation schemes. Furthermore, we identify and evaluate three types of countermeasures that allow for precise and secure ranging.

HomePlug AV (HPAV) was designed to provide high speed in-home communication with 200Mbps PHY rate, with the goal to overcome various noises over power wires and to jump from one phase to a neighboring one. A HomePlug AV Logical Networks (AVLN) is defined by cryptographic means, i.e. stations that share the same key and hear each other are in the same AVLN; however, AVLNs which coexist in a neighborhood cannot communicate but share the same physical layer. These points imply that people using HomePlug AV may share system throughput with neighbors without being aware of it. In order to assess the reality of this potential problem, we performed measurements on an experimental testbed with several AVLNs and equipment from different manufacturers. Our results are: 1. we verified that HomePlug AV stations can communicate even over physically separated wires, and thus neighboring stations in the same AVLN or in different AVLNs may share the same throughput; 2. when stations are placed in two different AVLNs, system performance is noticeably less compared to having the same stations at the same locations but in one single AVLN; 3. HPAV stations from different manufacturers do interoperate but experience heavy per-pair throughput outages. Our findings suggest that HPAV does not perform satisfactorily in large deployments. A possible solution to the problem would be to make different AVLNs quasi-orthogonal at the physical layer, perhaps using the cryptographic key to seed an OFDM hopping sequence.

We derive the Ziv-Zakai lower bound for Impulse Radio (IR) Ultra-WideBand (UWB) ranging error correlation matrix under a classical IR-UWB positioning system. We present the numerical evaluations with IEEE 802.15.4a channel model and the geometry of indoor environments of interest. As our derived bound depends on the geometry of the indoor environments, our bound can be used in real environments with the channel measurements from real environments.

The increase in data consumed by smartphones is becoming a huge problem for mobile operators. In three years, mobile data traffic in AT&T's network rose 5000%. The US operators invest $50 billion in the data networks every year and the technology upgrades and innovation still fail to keep up with the demand. In this paper we design two algorithms for delay-tolerant offloading of bulky, socially recommended content from 3G networks. The first one, called "MixZones", uses opportunistic, ad hoc transfers between users, and is assisted by predictions made by the network operator. The second one, called "HotZones", exploits delay tolerance and tries to download contents when users are close to Wi-Fi access points; it is also assisted by predictions made by the operator. We evaluate both algorithms using a large data set, obtained from a major mobile operator and a realistic application similar to Apple's Ping music social network. The metrics address the amount of offloading, delay and mobile energy efficiency. We find that both solutions succeed in offloading a significant amount of traffic, with a positive impact on user battery lifetime. Surprisingly, we also find that all the benefit obtained from the operator with the MixZones algorithm (i.e with ad hoc exchanges between users) can be achieved with the HotZones algorithm and a small investment in Wi-Fi access points. Note that the latter is considerably less complex to deploy than the former.

It is a well-known fact that the progress of personal communication devices leads to serious concerns about privacy in general, and location privacy in particular. As a response to these issues, a number of Location-Privacy Protection Mechanisms (LPPMs) have been proposed during the last decade. However, their assessment and comparison remains problematic because of the absence of a systematic method to quantify them. In particular, the assumptions about the attacker's model tend to be incomplete, with the risk of a possibly wrong estimation of the users' location privacy. In this paper, we address these issues by providing a formal framework for the analysis of LPPMs, it captures, in particular, the prior information that might be available to the attacker, and various attacks that he can perform. The privacy of users and the success of the adversary in his location-inference attacks are two sides of the same coin. We revise location privacy by giving a simple, yet comprehensive, model to formulate all types of location-information disclosure attacks. Thus, by formalizing the adversary's performance, we propose and justify the right metric to quantify location privacy. We clarify the difference between three aspects of the adversary's inference attacks, namely their accuracy, certainty, and correctness. We show that correctness determines the privacy of users. In other words, the expected estimation error of the adversary is the metric of users' location privacy. We rely on well-established statistical methods to formalize and implement the attacks in a tool: the Location-Privacy Meter that measures the location privacy of mobile users, given various LPPMs. In addition to evaluating some example LPPMs, by using our tool, we assess the appropriateness of some popular metrics for location privacy: entropy and k-anonymity. The results show a lack of satisfactory correlation between these two metrics and the success of the adversary in inferring the users' actual locations.

Impulse Radio Ultra-Wideband, in particular the recent standard IEEE 802.15.4a, is a primary candidate for implementing distance bounding protocols, thanks to its ability to perform accurate indoor ranging. Distance bounding protocols allow two wireless devices to securely estimate the distance between themselves, with the guarantee that the estimate is an upper-bound on the actual distance. These protocols serve as building blocks in security-sensitive applications such as tracking, physical access control, or localization. We investigate the resilience of IEEE 802.15.4a to physical-communication-layer attacks that decrease the distance measured by distance bounding protocols, thus violating their security. We consider two attack types: malicious prover (internal) and distance-decreasing relay (external). We show that if the honest devices use energy-detection receivers (popular due to their low cost and complexity), then an adversary can perform highly effective internal and external attacks, decreasing the distance by hundreds of meters. However, by using more sophisticated rake receivers, or by implementing small modifications to IEEE 802.15.4a and employing energy-detection receivers with a simple countermeasure, honest devices can reduce the effectiveness of external distance-decreasing relay attacks to the order of 10m. The same is true for malicious prover attacks, provided that an additional modification to IEEE 802.15.4a is implemented.

In this paper, we derive the Ziv-Zakai lower bounds for Impulse Radio (IR) Ultra-WideBand (UWB) Time Of Arrival (TOA)-based positioning and Time Difference Of Arrival (TDOA)-based positioning error based on geometry of indoor environments. We present the numerical evaluations with IEEE 802.15.4a channel model and the geometry of indoor environments of interest. As our derived bounds depend on the geometry of the indoor environments, our bounds can also be used in real environments with the channel measurements from real environments.

We consider the Ziv-Zakai lower bound for Impulse Radio (IR) Ultra-WideBand (UWB) ranging error under dense multipath environments and additive Gaussian noise. In contrast to previous work (for example and), our derived bound has following novel points: (1) Our derived bound depends on the geometry of the indoor environments of interest. The uniform distribution is a special case in our bound. (2) We do not introduce any approximation for our log-likelihood function during our derivation process. Therefore, we obtain a more accurate Ziv-Zakai lower bound for the IR-UWB ranging error with IEEE 802.15.4a channel models. (3) Based on the geometry of the indoor environments, we can find the "best" position of the base station which provides the lowest Ziv-Zakai lower bound of the IR-UWB ranging error. (4) Our derived bound can also be used in real environments with the channel measurements from real environments.

In many envisioned mobile ad hoc networks, nodes are expected to periodically beacon to advertise their presence. In this way, they can receive messages addressed to them or participate in routing operations. Yet, these beacons leak information about the nodes and thus hamper their privacy. A classic remedy consists of each node making use of (certified) pseudonyms and changing its pseudonym in specific locations called mix zones. Of course, privacy is then higher if the pseudonyms are short-lived (i.e., nodes have a short distance-to-confusion), but pseudonyms can be costly, as they are usually obtained from an external authority. In this paper, we provide a detailed analytical evaluation of the age of pseudonyms based on differential equations. We corroborate this model by a set of simulations. This paper thus provides a detailed quantitative framework for selecting the parameters of a pseudonym-based privacy system in peer-to-peer wireless networks.

Collaborative ad-hoc dissemination of information has been proposed as an efficient means to disseminate information among devices in a wireless ad-hoc network. Devices help in forwarding the information channels to the entire network, by disseminating the channels they subscribe to, plus others. We consider the case where devices have a limited amount of storage that they are willing to devote to the public good, and thus have to decide which channels they are willing to help disseminate. We are interested in finding channel selection strategies which optimize the dissemination time across the channels. We first consider a simple model under the random mixing assumption; we show that channel dissemination time can be characterized in terms of the number of nodes that forward this channel. Then we show that maximizing a social welfare is equivalent to an assignment problem, whose solution can be obtained by a centralized greedy algorithm. We show empirical evidence, based on Zune data, that there is a substantial difference between the utility of the optimal assignment and heuristics that were used in the past. We also show that the optimal assignment can be approximated in a distributed way by a Metropolis-Hastings sampling algorithm. We also give a variant that accounts for battery level. This leads to a practical channel selection and re-selection algorithm that can be implemented without any central control.

We expose the vulnerability of an emerging wireless ranging technology, impulse radio ultra-wide band (IR-UWB), to distance-decreasing attacks on the physical communication layer (PHY). These attacks violate the security of secure ranging protocols that allow two wireless devices to securely estimate the distance between them, with the guarantee that the estimate is an upper-bound on the actual distance. Such protocols serve as crucial building blocks in security-sensitive applications such as location tracking, physical access control, or localization.

We examine the fundamental properties that determine the basic performance metrics for opportunistic communications. We first consider the distribution of intercontact times between mobile devices. Using a diverse set of measured mobility traces, we find as an invariant property that there is a characteristic time, order of half a day, beyond which the distribution decays exponentially. Up to this value, the distribution in many cases follows a power law, as shown in recent work. This power law finding was previously used to support the hypothesis that intercontact time has a power law tail, and that common mobility models are not adequate. However, we observe that the timescale of interest for opportunistic forwarding may be of the same order as the characteristic time, and thus, the exponential tail is important. We further show that already simple models such as random walk and random waypoint can exhibit the same dichotomy in the distribution of intercontact time as in empirical traces. Finally, we perform an extensive analysis of several properties of human mobility patterns across several dimensions, and we present empirical evidence that the return time of a mobile device to its favorite location site may already explain the observed dichotomy. Our findings suggest that existing results on the performance of forwarding schemes based on power law tails might be overly pessimistic.

We consider the problem of ranging with Impulse Radio (IR) Ultra-WideBand (UWB) radio under weak Line Of Sight (LOS) environments and additive Gaussian noise. We use a Bayesian approach where the prior distribution of the channel follows the IEEE 802.15.4a channel model, to estimate the joint posterior probability density function (pdf) of the channel and the targeted distance. One of applications of the joint posterior pdf of the channel and the targeted distance is the ranging determination with classical posterior estimators (such as Minimum Mean Square Error Estimator (MMSE)). For computing the joint posterior pdf of the channel and the targeted distance, we derived a novel algorithm which is based on importance sampling and expectation maximum techniques. Furthermore, we propose a reduced-complexity architecture of IR UWB ranging system using our proposed algorithm. The complexity analysis of the algorithm shows the proposed algorithm is a low-complexity one. Numerical evaluations under the IEEE 802.15.4a channel model are presented to demonstrate the good performance of the proposed estimator.

Non-coherent energy-detection receivers are an attractive choice for IEEE 802.15.4a networks. They can exploit the ranging capabilities and the multipath resistance of impulse-radio ultra-wide band (IR-UWB) at a low complexity. However, IEEE 802.15.4a receivers operate with interference created by uncontrolled piconets and an uncoordinated medium access control layer. The performance of an energy-detection IR-UWB receiver is greatly degraded in such scenarios, for both timing acquisition and decoding. In this paper, we focus on timing acquisition: we present PICNIC, a robust and low-complexity algorithm that allows for reliable timing acquisition with an IR-UWB energy-detection receiver in the presence of multiuser interference (MUI), even in near-far scenarios. At the cost of a negligible performance reduction in single-user scenarios, PICNIC outperforms classic timing acquisition algorithms by up to two orders of magnitude if MUI is present. Furthermore, PICNIC exhibits a near perfect capture property: if several transmitters compete for timing acquisition at the receiver, one signal will be acquired with practically no false detection.

Practical impulse radio ultra-wideband (IR-UWB) ranging systems always have to work in multi-user and weak non-line-of-sight (NLOS) environments. In this paper, we derive a novel IR-UWB ranging estimator under multi-user and weak NLOS environments. We model MUI with complex Gaussian mixture model (CGMM) in the frequency domain. We propose a novel estimator for the UWB time of arrival (ToA) parameters based on the expectation maximization (EM) algorithm, the pseudo quadratic maximum likelihood (PQML) algorithm and CGMM. The estimator reduce the MUI in the frequency domain so that the cost function becomes asymptotically noiseless. Ranging is obtained by translating the obtained delay estimates into an estimate of the distance. And numerical evaluations under IEEE 802.15.3a channel model are presented to demonstrate the good performance of the proposed estimator.

User-generated podcasting service over human-centric opportunistic network can facilitate user-generated content sharing while humans are on the move beyond the coverage of infrastructure networks. We focus on the aspects of designing efficient forwarding and cache replacement schemes of such service under the constraints of limited capability of handheld device and limited network capacity. In particular, the design of those schemes is challenged by the lack of podcast channel popularity information at each node which is crucial for forwarding and caching decisions. We design a distributed reputation system based on modified Bayesian framework that enable each node estimates the channel popularity in a efficient way. It estimates channel popularity by not only first hand observations but also second hand observations from other nodes. Our simulation result shows reputation system can always well estimate most popular, intermediate and low popular channels, compare to history-based rank scheme which can only well estimate a few most popular channels. Reputation system significantly outperforms history-based rank when the public cache size is small or "a" parameter of Zipf-like distribution is small.

We consider evolving games with finite number of players, in which each player interacts with other randomly selected players. The types and actions of each player in an interaction together determine the instantaneous payoff for all involved players. They also determine the rate of transition between type-actions. We provide a rigorous derivation of the asymptotic behavior of this system as the size of the population grows. We show that the large population asymptotic of the microscopic model is equivalent to a macroscopic evolutionary game in which a local interaction is described by a single player against an evolving population profile. We derive various classes of evolutionary game dynamics. We apply these results to spatial random access games in wireless networks.

For impulse-radio ultrawideband (IR-UWB) networks without global synchronization, the first step for correct packet reception is packet detection and timing acquisition: Before recovering the payload of the packet, the destination must detect that the packet is on the medium and determine when exactly the payload begins. Packet detection and timing acquisition rely on the presence of an acquisition preamble at the beginning of each packet. How this preamble is chosen is a network design issue and it may have quite an impact on the network performance. A simple design choice of the network is to use a common acquisition preamble for the whole network. A second design choice is to use an acquisition preamble that is private to each destination. The throughput with the latter choice is likely to be much higher, albeit at the cost of learning the private acquisition preamble of a destination. In this paper, we evaluate how using a common or private acquisition preambles affects the network throughput. Our analysis is based on analytical modeling and simulations. Using our analytical model, we show that a private acquisition preamble yields a tremendous increase in throughput compared to a common acquisition preamble. The throughput difference grows with the number of concurrent transmitters and interferers. This result is confirmed by simulations. Furthermore, additional simulations on multihop topologies with TCP flows demonstrate that a network using private acquisition preambles has a stable throughput. On the contrary, using a common acquisition preamble exhibits the presence of a compounding effect similar to the exposed terminal issue in IEEE 802.11 networks: The throughput is severely degraded and complete flow starvation may occur.

We propose a high-resolution ranging algorithm for impulse radio (IR) ultra-WideBand (UWB) communication systems in additive white Gaussian noise. We formulate the ranging problem as a maximum- likelihood (ML) estimation problem for the channel delays and amplitudes at the receiver. Then we translate the obtained delay estimates into an estimate of the distance. The ML estimation problem is a non-linear problem and is hard to solve. Some previous works focus on finding alternative estimation procedures, for example by denoising. In contrast, we tackle the ML estimation problem directly. First, we use the same transformation as the first step of Iterative quadratic maximum likelihood (IQML) and we transform the ML problem into another optimization problem that avoids the estimation of the amplitude coefficients. Second, we solve the remaining optimization problem with a gradient descent approach (pseudo-quadratic maximum likelihood (PQML) algorithm). To demonstrate the good performance of the proposed estimator, we present the numerical evaluations under the IEEE 802.15.4a channel model. We show that our algorithm performs significantly better than previously published heuristics. We also derive a reduced complexity version of the algorithm algorithm, which will be implemented on the Xinlix field-programmable gate array (FPGA) board in the future. We test the approach in a real weak line of sight (LOS) propagation environment and obtained good accuracy for the ranging.

Aggregate scheduling is one of the most promising solutions to the issue of scalability in networks, like DiffServ networks and high speed switches, where hard QoS guarantees are required. For networks of FIFO aggregate schedulers, the main existing sufficient conditions for stability (the possibility to derive bounds to delay and backlog at each node) are of little practical utility, as they are either relative to specific topologies, or based on strong ATM-like assumptions on the network (the so-called "RIN" result), or they imply an extremely low node utilization. We use a deterministic approach to this problem. We identify a nonlinear operator on a vector space of finite (but large) dimension, and we derive a first sufficient condition for stability, based on the super-additive closure of this operator. Second, we use different upper bounds of this operator to obtain practical results. We find new sufficient conditions for stability, valid in an heterogeneous environment and without any of the restrictions of existing results. We present a polynomial time algorithm to test our sufficient conditions for stability. We show that with leaky bucket constrained flows the inner bound to the stability region derived with our algorithm is always larger than the one determined by all existing results. We prove that all the main existing results can be derived as special cases of our results. We also present a method to compute delay bounds in practical cases.

The Internet of Things, emerging pervasive and sensor networks are low data-rate wireless networks with, a priori, no specific topology and no fixed infrastructure. Their primary requirements are twofold: first, low power consumption and, due to environmental concerns, low emitted power. Second, robustness to poor propagation environments and multi-user interference. Impulse-radio ultra-wide band (IR-UWB) physical layers have the potential to satisfy these requirements. Because the features of IR-UWB physical layers differ from narrow-band physical layers, the design rules of IR-UWB networks are likely to be different than for narrow-band wireless networks. Indeed, to optimally use the resources available, it is crucial for the network layers to take into account and take advantage of the underlying physical layer. Therefore, we are interested in the design of IR-UWB networks in a low data-rate, self-organized, and multi-hop context. We concentrate on the medium access control (MAC) layer and the physical layer. In the case of low data-rate IR-UWB networks, the optimal design is to allow for parallel and concurrent transmissions at the MAC layer. Interference is managed with rate adaptation, no power control and an interference mitigation scheme at the physical layer. A protocol that implements the optimal design and allows for parallel transmissions outperforms protocols that use exclusion or power control.

We examine the fundamental properties that determine the basic performance metrics for opportunistic communications. We first consider the distribution of inter-contact times between mobile devices. Using a diverse set of measured mobility traces, we find as an invariant property that there is a characteristic time, order of half a day, beyond which the distribution decays exponentially. Up to this value, the distribution in many cases follows a power law, as shown in recent work. This powerlaw finding was previously used to support the hypothesis that inter-contact time has a power law tail, and that common mobility models are not adequate. However, we observe that the time scale of interest for opportunistic forwarding may be of the same order as the characteristic time, and thus the exponential tail is important. We further show that already simple models such as random walk and random way point can exhibit the same dichotomy in the distribution of inter-contact time ascin empirical traces. Finally, we perform an extensive analysis of several properties of human mobility patterns across several dimensions, and we present empirical evidence that the return time of a mobile device to its favorite location site may already explain the observed dichotomy. Our findings suggest that existing results on the performance of forwarding schemes basedon power-law tails might be overly pessimistic.

One of the challenges of today's overlay networks, especially P2P, is still scalability. A key issue in almost all of the current overlay architectures is the link count per single node. If the link count is too high, the management overhead in terms of keep-alive messages increases. If the amount of links per node is too low, the resilience of the system against network splits decreases and the system can hardly route in an optimal way. Moreover, if keep-alive messages are not sent frequently enough, outdated information could be propagated, which again could cause net splits. This paper presents a new cooperative keep-alive algorithm that strongly reduces the costs for sending keep- alive messages and, at the same time, preserves the effectiveness and reliability of standard keep-alive mechanisms in today's overlay networks. The algorithm allows to increase the number of links per node, and, thus, to improve the connectivity and routing efficiency in the network, while keeping the keep-alive overhead low. When used without increasing the link count, the algorithm reduces drastically the keep-alive traffic. The properties of the algorithm are evaluated analytically and simulatively and compared to existing keep-alive techniques.

We pose the estimation of the parameters of multiple superimposed exponential signals in additive Gaussian noise problem as a maximum likelihood (ML) estimation problem. The ML problem is non linear and hard to solve. Some previous works focused on finding alternative estimation procedures, for example by denoising. In contrast, we tackle the ML estimation problem directly. First, we use the same transformation as the first step of iterative quadratic maximum likelihood (IQML) and transform the ML problem into another optimization problem that gets rid of the amplitude coefficients. Second, we solve the remaining optimization problem with a gradient descent approach ("pseudo-quadratic maximum likelihood"). We also use this algorithm for ultra-wideband channel estimation and estimate ranging in non-line of sight environment.

We identify vulnerabilities in epidemic forwarding. We address broadcast applications over wireless ad-hoc networks. Epidemic forwarding employes several mechanisms such as inhibition and spread control, and each of them can be implemented using alternative methods. Thus, the existence of vulnerabilities is highly dependent on the methods used. We examine the links between them. We classify vulnerabilities into two categories: maliccious and rational. We examine the effect of the attacks according to the number of attackers and the different network settings such as density, mobility and congestion. We show that malicious attacks are hard to achieve and their impacts are scenario dependent. In contrast, rational attackers always obtain a significant benefit. The evaluation is carried out using detailed realistic simulations over networks with up to 1000 nodes. We consider static scenarios, as well as vehicular networks.

Abstract — We show that network coding allows to realize en-ergy savings in a wireless ad-hoc network, when each node of the network is a source that wants to transmit information to all other nodes. Energy efficiency directly affects battery life and thus is a critical design parameter for wireless networks. We propose an implementable method for performing network coding in such a setting. We analyze theoretical cases in detail, and use the insights gained to propose a practical, fully distributed method for realistic wireless ad-hoc scenarios. We address practical issues such as setting the forwarding factor, managing generations, and impact of transmission range. We use theoretical analysis and packet level simulation. I.

We consider the design of the MAC layer for low power, low data-rate, and impulse-radio ultra-wide band (IR-UWB) networks. In such networks, the primary concern is energy consumption rather than rate efficiency. We explore several dimensions such as power control, rate adaptation, mutual exclusion, slotted versus non-slotted operation, power saving modes and interference mitigation. We analyze the effect of these design choices on the energy consumption and rate efficiency. We use a method of energy quanta for computing the energy consumption. We find that for both cases, the optimal operation is non-coordinated and with no power control. Sources should send at their maximum power and not pay attention to neighboring nodes. However, sources should constantly adapt their transmission rate to the level of interference

Distributed hash tables (DHTs) provide a scalable mechanism for mapping identifiers to socket addresses. As each peer in the network can initiate lookup requests, a DHT has to process concurrently a potentially very large number of requests. In this paper, we look at congestion control for DHTs. Our goal is to control the flow of lookup requests that are routed in the overlay network. We first show that congestion control is essential for certain applications with high lookup rates. We then present two congestion control mechanisms for DHTs and compare their performances in different network conditions

We define "random trip", a generic mobility model for independent mobiles that contains as special cases: the random waypoint on convex or non convex domains, random walk with reflection or wrapping, city section, space graph and other models. We use Palm calculus to study the model and give a necessary and sufficient condition for a stationary regime to exist. When this condition is satisfied, we compute the stationary regime and give an algorithm to start a simulation in steady state (perfect simulation). The algorithm does not require the knowledge of geometric constants. For the special case of random waypoint, we provide for the first time a proof and a sufficient and necessary condition of the existence of a stationary regime. Further, we extend its applicability to a broad class of non convex and multi-site examples, and provide a ready-to-use algorithm for perfect simulation. For the special case of random walks with reflection or wrapping, we show that, in the stationary regime, the mobile location is uniformly distributed and is independent of the speed vector, and that there is no speed decay. Our framework provides a rich set of well understood models that can be used to simulate mobile networks with independent node movements. Our perfect sampling is implemented to use with ns-2, and it is freely available to download from http://ica1www.epfl.ch/RandomTrip.

Using decentralized reputation systems is a promising approach to ensuring cooperation and fairness in mobile ad-hoc networks. However, they are vulnerable to liars and robustness has not been analyzed in detail. With our work, we provide a first step to the analysis of a reputation system based on a deviation test. Nodes accept second hand information only if this does not differ too much from their reputation values. Whereas our earlier paper [J. Mundinger and J.-Y. Le Boudec, 2005] dealt with a simplified one-dimensional model, we now consider the original two-dimensional system. We show that the system exhibits a phase transition. In the subcritical regime, it is robust and lying has no effect. In the supercritical regime, lying does have an impact. We compute the critical values via a mean-field approach and use simulations to verify our results. Thus, we obtain conditions for the deviation test to make the reputation system robust and provide guidelines for a good choice of parameters.

We consider the design of optimal strategies for joint power adaptation, rate adaptation and scheduling in a multi-hop wireless network. Most existing strategies control either power and scheduling, or rates and scheduling, but not all three together as we do. We assume the underlying physical layer is in the linear regime (the rate of a link can be approximated by a linear function of the signal-to-interference-and-noise ratio), as in time hopping UWB (TH-UWB) and low gain CDMA systems, and that it allows fine-grained rate adaptation, as in 802.11a/g, HDR/CDMA, TH-UWB. The goal is to find properties of the power control in an optimal joint design. Our main finding is that optimal power control is simple 0-P/sup MAX/ power control, i.e. when a node is sending it uses the maximum transmitting power allowed. We consider both high rate networks, where the goal is to maximize rates under power constraints, and low power networks, where the goal is to minimize average consumed power while meeting minimum rate constraints. We prove analytically that, in both scenarios, the optimal can always be attained with 0-P/sup MAX/ power allocation. Moreover, we prove that, when maximizing rates, and if power constraints are on peak and not average, 0-P/sup MAX/ is the only optimal power control strategy, and any other is strictly suboptimal.

Using location information to help routing is often proposed as a means to achieve scalability in large mobile ad hoc networks. However, location-based routing is difficult when there are holes in the network topology and nodes are mobile or frequently disconnected to save battery. Terminode routing, presented here, addresses these issues. It uses a combination of location-based routing (terminode remote routing, TRR), used when the destination is far, and link state-routing (terminode local routing, TLR), used when the destination is close. TRR uses anchored paths, a list of geographic points (not nodes) used as loose source routing information. Anchored paths are discovered and managed by sources, using one of two low overhead protocols: friend assisted path discovery and geographical map-based path discovery. Our simulation results show that terminode routing performs well in networks of various sizes. In smaller networks; the performance is comparable to MANET routing protocols. In larger networks that are not uniformly populated with nodes, terminode routing outperforms, existing location-based or MANET routing protocols.

In "Stationary distributions for the random waypoint mobility model" (TMC, Vol. 3, No, 1), Navidi and Camp find the stationary distribution of the random waypoint model, with or without pause on a rectangular area. In this short note, we show that, under the stationary regime, speed and location are independent.

In mobile ad hoc networks, nodes act both as terminals and information relays, and they participate in a common routing protocol, such as dynamic source routing (DSR). The network is vulnerable to routing misbehavior, due to faulty or malicious nodes. Misbehavior detection systems aim at removing this vulnerability. In this paper, we investigate the use of an artificial immune system (AIS) to detect node misbehavior in a mobile ad hoc network using DSR. The system is inspired by the natural immune system (IS) of vertebrates. Our goal is to build a system that, like its natural counterpart, automatically learns, and detects new misbehavior. We describe our solution for the classification task of the AIS; it employs negative selection and clonal selection, the algorithms for learning and adaptation used by the natural IS. We define how we map the natural IS concepts such as self, antigen, and antibody to a mobile ad hoc network and give the resulting algorithm for classifying nodes as misbehaving. We implemented the system in the network simulator Glomosim; we present detection results and discuss how the system parameters affect the performance of primary and secondary response. Further steps will extend the design by using an analogy to the innate system, danger signal, and memory cells.

We consider unicast equation-based rate control, where, at some points in time, a source adjusts its rate to f(p,r). Here p is an on-line estimate of the loss-event rate, r, of the mean round-trip time, both as observed by this source, and f is a TCP throughput formula. It was generally believed that such a source would be TCP-friendly, that is, under the same operating conditions, its long-run time-average send rate (throughput) would not be larger than that of a TCP source. Our goal is to identify whether, and how far, this is true. First, we identify factors that play a role in TCP friendliness and find that it is important to study them separately. Then we analyze the importance of individual factors. A first factor is conservativeness (= throughput not larger than f(p,r)). We show that conservativeness is influenced by some convexity properties of f(p,r) with respect to p, and the covariance of the loss process. We show that in many real life cases these conditions result in conservativeness and, sometimes, excessive conservativeness. This explains the previously observed phenomena of throughput-drop when losses are high and f is the so-called PFTK formula. The second factor is that the source may experience considerably different loss-event rate than a TCP source. We identify and analyze two limit cases where this may lead to either TCP-friendliness or, in contrast, non-TCP-friendliness. Other factors such as round trip time and obedience of TCP to its own formula are found to be less significant. Our claims are obtained by analysis, and verified by numerical examples, simulations, laboratory and Internet experiments. Our results suggest that TCP-friendliness is difficult to verify in practice, whereas conservativeness is easier.

Abstract Due to environmental concerns and strict constraints on interference imposed on other networks, the radiated power of emerging pervasive wireless networks needs to be strictly limited, yet without sacrificing acceptable data rates. Pulsed time‐hopping ultra‐wideband (TH‐UWB) is a radio technology that has the potential to satisfy this requirement. Although TH‐UWB is a multi‐user radio technology, non‐zero cross‐correlation between TH sequences, time‐asynchronicity between sources and a multipath channel environment make it sensitive to strong interferers and near‐far scenarios. While most protocols manage interference and multiple‐access through power control or mutual exclusion, we base our design on rate control, a relatively unexplored dimension for multiple‐access and interference management. We further take an advantage of the nature of pulsed TH‐UWB to propose an interference mitigation scheme that alleviates the need for an exclusion scheme. A source is always allowed to send and continuously adapts its channel code (hence its rate) to the interference experienced at the destination. In contrast to power control or exclusion, our MAC layer is local to sender and receiver, and does not need coordination among neighbors not involved in the transmission. We show by simulation that we achieve a significant increase in the network throughput compared to alternative designs. Copyright © 2005 John Wiley & Sons, Ltd.

We present a joint PHY/MAC architecture (DCC-MAC) for 802.15.4a-like networks based on PPM-UWB. Unlike traditional approaches, it fully utilizes the specific nature of UWB to achieve high rates at low protocol complexity. It is the first MAC protocol that adapts the channel code (and thus the bit rate) to interference from concurrent transmissions instead of enforcing exclusion. In order to avoid a complex mutual exclusion protocol at the MAC layer, we propose an interference mitigation scheme. The scheme is based on a modification of the physical layer that cancels much of the interfering energy, in particular from nearby interferers. We further use dynamic channel coding to combat the remaining interference. Sources constantly adjust their channel codes to the level of interference and send incremental redundancy as required. Contention between sources sending to the same destination is solved by a "private MAC" protocol that involves only the nodes that want to talk to the same destination. The private MAC does not use any common channel; this avoids the issues of hidden and exposed terminals altogether. We show by simulation that our MAC protocol fully satisfies the application requirements of 802.15.4a in terms of link lengths, rates and mobility. We further show that it achieves a significant increase in network throughput, compared to traditional MAC protocols like 802.15.4, that are separated from the physical layer.

We consider the maximization when designing ad-hoc wireless network protocols such as routing or MAC. We focus on maximizing rates under battery lifetime and power constraints. Commonly used metrics are total capacity (in the case of cellular networks) and transport capacity (in the case of ad-hoc networks). We review this issue for wireless ad-hoc networks. The story is different for max-min fairness. We show that, in the limit of long battery lifetime, the max-min allocation of rates always leads to strictly equal rates, regardless of the MAC layer, network topology, choice of routes and power constraints. This is due to the "solidarity" property of the set of feasible rates. This results in all flows receiving the rate of the worst flow, and leads to severe inefficiency. We show numerically that the problem persists when battery lifetime constraints are finite. This generalizes the observation reported in the literature that, in heterogeneous settings, 802.11 allocates the worst rate to all stations, and shows that this is inherent to any protocol that implements max-min fairness. Proportional fairness is an alternative to max-min fairness that approximates rate allocation performed by TCP in the Internet. We show by numerical simulations that proportional fairness of rates or transport rates is robust and achieves a good trade-off between efficiency and fairness, unlike total rate or maximum fairness. We thus recommend that metrics for the rate performance of mobile ad-hoc networking protocols be based on proportional fairness.

Ultra-wideband (UWB) is an emerging wireless physical layer technology that uses a very large bandwidth. We are interested in finding the design objectives of the medium access [medium-access control (MAC), namely, power control and scheduling] and routing protocols of a multihop, best-effort, UWB network. Our objective is to maximize flow rates (more precisely, log-utility of flow rates) given node power constraints. The specificity of UWB is expressed by the linear dependence between rate and signal-to-noise ratio at the receiver. It is known that, in wireless networks, different routing strategies can imply differences in MAC protocol design. Hence, we search for the jointly optimal routing, scheduling and power control. We find that the optimal solution is characterized by the following. 1) When data is being sent over a link, it is optimal to have an exclusion region around the destination, in which all nodes remain silent during transmission, whereas nodes outside of this region can transmit in parallel, regardless of the interference they produce at the destination. Additionally, the source adapts its transmission rate according to the level of interference at the destination due to sources outside of the exclusion region. 2) The optimal size of this exclusion region depends only on the transmission power of the source of the link, and not on the length of the link nor on positions of nodes in its vicinity. 3) Each node in a given time slot either sends data at the maximum power, or does not send at all. As for the routing, we restrict ourselves to a subset of routes where on each successive hop we decrease the distance toward the destination, and we show that 4) relaying along a minimum energy and loss route is always better than using longer hops or sending directly, which is not obvious since we optimize rate and not power consumption. Finally 5), the design of the optimal MAC protocol is independent of the choice of the routing protocol. For narrowband networks, 2), 4), and 5) do not hold, which shows that the design of an UWB network should be addressed in a different way than for narrowband. Our technical approach is based on expressing the design requirements as a mathematical optimization problem. We solve it exactly for simple networks on a line and approximately on random topologies in a plane with up to 50 nodes with various power constraints, traffic matrices, and mobility parameters.

We consider the question of what performance metric to maximize when designing ad hoc wireless network protocols such as routing or MAC. We focus on maximizing rates under battery-lifetime and power constraints. Commonly used metrics are total capacity (in the case of cellular networks) and transport capacity (in the case of ad hoc networks). However, it is known in traditional wired networking that maximizing total capacity conflicts with fairness, and this is why fairness-oriented rate allocations, such as max-min fairness, are often used. We review this issue for wireless ad hoc networks. Indeed, the mathematical model for wireless networks has a specificity that makes some of the findings different. It has been reported in the literature on ultra wide band that gross unfairness occurs when maximizing total capacity or transport capacity, and we confirm by a theoretical analysis that this is a fundamental shortcoming of these metrics in wireless ad hoc networks, as it is for wired networks. The story is different for max-min fairness. Although it is perfectly viable for a wired network, it is much less so in our setting. We show that, in the limit of long battery lifetimes, the max-min allocation of rates always leads to strictly equal rates, regardless of the MAC layer, network topology, channel variations, or choice of routes and power constraints. This is due to the "solidarity" property of the set of feasible rates. This results in all flows receiving the rate of the worst flow, and leads to severe inefficiency. We show numerically that the problem persists when battery-lifetime constraints are finite. This generalizes the observation reported in the literature that, in heterogeneous settings, 802.11 allocates the worst rate to all stations, and shows that this is inherent to any protocol that implements max-min fairness. Utility fairness is an alternative to max-min fairness, which approximates rate allocation performed by TCP in the Internet. We analyze by numerical simulations different utility functions and we show that the proportional fairness of rates or transport rates, a particular instance of utility-based metrics, is robust and achieves a good tradeoff between efficiency and fairness, unlike total rate or maximum fairness. We thus recommend that metrics for the rate performance of mobile ad hoc networking protocols be based on proportional fairness.

A joint playout buffer and forward error correction (FEC) adjustment scheme are developed for Internet telephony, which incorporates the impact of end-to-end delay on the perceived audio quality. We show that it provides better quality than the adjustment schemes for playout buffer and FEC that were previously published. This is important because of a threshold effect when the end-to-end delay of interactive audio is around 150 ms. We represent the perceived audio quality as a function of both the end-to-end delay and the distortion of the voice signal. We develop a joint rate/error/playout delay control algorithm that optimizes this measure of quality and is TCP-friendly. It uses a channel model for both loss and delay. We validate our approach by simulation and show that (1) our scheme allows a source to increase its utility by avoiding an increase of the playout delay when it is not really necessary, (2) it performs better than direct combinations of existing algorithms in the cases where end-to-end delay is important and (3) adaptive delay aware FEC adjustment brings significant improvements only if it is coupled with an adaptive playout adjustment.

We consider the problem of bounding the probability of buffer overflow in a network node fed with independent arrival processes that are each constrained by arrival curves, but that are served as an aggregate. Existing results assume that the node is a constant rate server. However, in practice, one finds complex network nodes that do not provide a constant service rate, and thus, to which the existing bounds do not apply. Now many nodes can be adequately abstracted by a service curve property. We extend previous results to such cases. As a by-product, we also provide a slight improvement to the bound in Chang et al. (see Proc. Sigmettics 2001, Cambridge, MA, May 2001, p.184-193). Our bounds are valid for both discrete and continuous time models.

Packet scale rate guarantee (PSRG) is a generic node model which underlies the definition of expedited forwarding (EF) proposed in the context of Internet differentiated services. For the case of first-in-first-out (FIFO) nodes, PSRG is equivalent to the well-understood concept of adaptive service curve. However, in practice, many devices do not necessarily preserve the FIFO property, and therefore, known FIFO results do not hold. This paper analyzes the properties of PSRG in the absence of FIFO assumption. Our analysis is based on a novel characterization of PSRG which avoids the use of virtual finish times and is obtained by min-max algebra. We use it to show that delay bounds previously obtained for the FIFO case are still valid; in contrast, we find that this is not true for the characterization of the concatenation of two nodes.

Packet scale rate guarantee (PSRG) is a generic node model which underlies the definition of expedited forwarding (EF) proposed in the context of Internet differentiated services (DiffServ). For the case of FIFO nodes, PSRG is equivalent to the well-understood concept of adaptive service curve. However, in practice, many devices do not necessarily preserve the FIFO property, and therefore known FIFO results do not hold. This paper analyzes the properties of PSRG in the absence of FIFO assumptions. Our analysis is based on a novel characterization of PSRG which avoids the use of virtual finish times; it is obtained by min-max algebra. We use it to show that delay bounds previously obtained for the FIFO case are still valid; in contrast, we find that this is not true for the characterization of the concatenation of two nodes.

A novel scheme for processing packets in a router is presented, which provides for load sharing among multiple network processors distributed within the router. It is complemented by a feedback control mechanism designed to prevent processor overload. Incoming traffic is scheduled to multiple processors based on a deterministic mapping. The mapping formula is derived from the robust hash routing (also known as the highest random weight - HRW) scheme, introduced in K.W. Ross, IEEE Network, vol. 11, no. 6 (1997), and D.G. Thaler et al, IEEE Trans. Networking, vol. 6, no. 1 (1998). No state information on individual flow mapping needs to be stored, but for each packet, a mapping function is computed over an identifier vector, a predefined set of fields in the packet. An adaptive extension to the HRW scheme is provided in order to cope with biased traffic patterns. We prove that our adaptation possesses the minimal disruption property with respect to the mapping and exploit that property in order to minimize the probability of flow reordering. Simulation results indicate that the scheme achieves significant improvements in processor utilization. A higher number of router interfaces can thus be supported with the same amount of processing power.

We consider stochastic guarantees for networks with aggregate scheduling, in particular, Expedited Forwarding (EF). Our approach is based on the assumption that a node can be abstracted by a service curve, and the input flows are regulated individually at the network ingress. Both of these assumptions are in line with EF. For a service curve node, we derive bounds on the complementary distributions of the steady-state backlog and backlog as seen by packet arrivals. We also give a bound on the long-run loss ratio for a service curve node where the buffer size is too small to guarantee loss-free operation. For a packet scale rate guarantee node, we use the delay from the backlog bound to obtain a probabilistic bound on the delay. Our analysis is exact under the given assumptions. Our results should help us to understand the performance of networks with aggregate scheduling, and provide the basis for dimensioning such networks.

Mobile ad-hoc networking works properly only if the participating nodes cooperate in routing and forwarding. However,it may be advantageous for individual nodes not to cooperate. We propose a protocol, called CONFIDANT, for making misbehavior unattractive; it is based on selective altruism and utilitarianism. It aims at detecting and isolating misbehaving nodes, thus making it unattractive to deny cooperation. Trust relationships and routing decisions are based on experienced, observed, or reported routing and forwarding behavior of other nodes. The detailed implementation of CONFIDANT in this paper assumes that the network layer is based on the Dynamic Source Routing (DSR) protocol. We present a performance analysis of DSR fortified by CONFIDANT and compare it to regular defenseless DSR. It shows that a network with CONFIDANT and up to 60% of misbehaving nodes behaves almost as well as a benign network, in sharp contrast to a defenseless network. All simulations have been implemented and performed in GloMoSim.

We consider unicast equation-based rate control, where a source estimates the loss event ratio $p$, and, primarily at loss events, adjusts its send rate to $f(p)$. Function $f$ is assumed to represent the loss-throughput relation that TCP would experience. When no loss occurs, the rate may also be increased according to some additional mechanism. We assume that the loss event interval estimator is non-biased. If the loss process is deterministic, the control is TCP-friendly in the long-run, i.e, the average throughput does not exceed that of TCP. If, in contrast, losses are random, it is a priori not clear whether this holds, due to the non-linearity of $f$, and a phenomenon similar to Feller's paradox. Our goal is to identify the key factors that drive whether, and how far, the control is TCP friendly (in the long run). As TCP and our source may experience different loss event intervals, we distinguish between TCP-friendliness and conservativeness (throughput does not exceed $f(p)$). We give a representation of the long term throughput, and derive that conservativeness is primarily influenced by various convexity properties of $f$, the variability of loss events, and the correlation structure of the loss process. In many cases, these factors lead to conservativeness, but we show reasonable experiments where the control is clearly non-conservative. However, our analysis also suggests that our source should experience a higher loss event ratio than TCP, which would make non-TCP friendliness less likely. Our findings provide guidelines that help understand when an equation base control is indeed TCP-friendly in the long-run, and in some cases, excessively so. The effects of round trip time and its variations are not included in this study.

We survey advances in theories and models for Internet quality of service (QoS). We start with the theory of network calculus, which lays the foundation for support of deterministic performance guarantees in networks, and illustrate its applications to integrated services, differentiated services, and streaming media playback delays. We also present mechanisms and architecture for scalable support of guaranteed services in the Internet, based on the concept of a stateless core. Methods for scalable control operations are also discussed. We then turn our attention to statistical performance guarantees and describe several new probabilistic results that can be used for a statistical dimensioning of differentiated services. Lastly, we review proposals and results in supporting performance guarantees in a best effort context. These include models for elastic throughput guarantees based on TCP performance modeling, techniques for some QoS differentiation without access control, and methods that allow an application to control the performance it receives, in the absence of network support.

We consider the definition of the expedited forwarding per-hop behavior (EF PHB) as given in RFC 2598 and its impact on worst case end-to-end delay jitter. On the one hand, the definition in RFC 2598 can be used to predict extremely low end-to-end delay jitter, independent of the network scale. On the other hand, the worst case delay jitter can be made arbitrarily large, while each flow traverses at most a specified number of hops, if we allow networks to become arbitrarily large; this is in contradiction with the previous statement. We analyze where the contradiction originates and find the explanation. It resides in the fact that the definition in RFC 2598 is not easily implementable in known schedulers, mainly because it is not formal enough and also because it does not contain an error term. We propose a new definition for the EF PHB, called "packet scale rate guarantee" (PSRG) that preserves the spirit of RFC 2598 while allowing a number of reasonable implementations and has very useful properties for per-node and end-to-end network engineering. We show that this definition implies a rate-latency service curve property. We also show that it is equivalent, in some sense, to the stronger concept of "adaptive service guarantee". Then we propose some proven bounds on delay jitter for networks implementing this new definition in cases without loss and with loss.

The min-plus theory of greedy shapers has been developed from R.L. Cruz's results (1991) on the calculus of network delays. The theory of greedy shapers establishes a number of properties such as the series decomposition of shapers or the conservation of arrival constraints by reshaping. It applies either to fluid systems or to packets of constant size such as ATM. For variable length packets, due to the distortion introduced by packetization, the theory is no longer valid. We elucidate the relationship between shaping and packetization effects. We show a central result, the min-plus representation of a packetized greedy shaper. We find a sufficient condition under which series decomposition of shapers and conservation of arrival constraints still holds in the presence of packetization effects. This allows us to demonstrate the equivalence of implementing a buffered leaky bucket controller based on either virtual finish times or on bucket replenishment. However, in some examples, if the condition is not satisfied, then the property may no longer hold. Thus, for variable size packets, there is a fundamental difference between constraints based on leaky buckets and constraints based on general arrival curves, such as spacing constraints. The latter are used in the context of ATM to obtain tight end-to-end delay bounds. We use a min-plus theory and obtain results on greedy shapers for variable length packets which are not readily explained with the max-plus theory of C.S. Chang (see "Performance Guarantees in Communication Networks", Springer-Verlag, 2000).

By extending the system theory under the (min, +) algebra to the time-varying setting, we solve the problem of constrained traffic regulation and develop a calculus for dynamic service guarantees. For a constrained traffic-regulation problem with maximum tolerable delay d and maximum buffer size q, the optimal regulator that generates the output traffic conforming to a subadditive envelope f and minimizes the number of discarded packets is a concatenation of the g-clipper with g(t) = min[f(t+ d), f (t)+q] and the maximal f-regulator. The g-clipper is a bufferless device, which optimally drops packets as necessary in order that its output be conformant to an envelope g. The maximal f-regulator is a buffered device that delays packets as necessary in order that its output be conformant to an envelope f. The maximal f-regulator is a linear time-invariant filter with impulse response f, under the (min, +) algebra. To provide dynamic service guarantees in a network, we develop the concept of a dynamic server as a basic network element. Dynamic servers can be joined by concatenation, "filter bank summation," and feedback to form a composite dynamic server. We also show that dynamic service guarantees for multiple input streams sharing a work-conserving link can be achieved by a dynamic service curve earliest deadline scheduling algorithm, if an appropriate admission control is enforced.

This paper considers the problem of routing in a wide area mobile ad-hoc network called terminode network. Our routing scheme is a combination of two protocols called terminode local routing (TLR) and terminode remote routing (TRR). TRR is activated when the destination is remote and uses location of the destination obtained either via location management or by location tracking. TLR acts when the packet gets close to the destination. The use of TRR results in a scalable solution that reduces dependence on the intermediate systems, while TLR allows us to reduce problems due to location inaccuracy. The paper describes TLR and TRR protocols and presents some simulation results.

We consider the problem of bounding the probability of buffer overflow in a network node receiving independent inputs that are each constrained by arrival curves, but that are served as an aggregate. Existing results (Kesidis et al., (2000), and Chang et al., (2001)) assume that the node is a constant rate server. However, in practice, one finds various types of schedulers that do not provide a constant service rate, and thus to which the existing bounds do not apply. Now many schedulers can be adequately abstracted by a service curve property. We extend the results in Kesidis and Chang to such cases. As a by-product, we also provide a slight improvement to the bound in Chang. Our bounds are valid for both discrete and continuous time models.

We consider the definition of the expedited forwarding per-hop behaviour (EF PHB) as given in RFC 2598 (Jacobsen et al. 1999), and its impact on worst case end-to-end delay jitter. On one hand, the definition in RFC 2598 can be used to predict extremely low end-to-end delay jitter, independent of the network scale. On the other hand, we find that the worst case delay jitter can be made arbitrarily large, while each flow traverses at most a specified number of hops, if we allow networks to become arbitrarily large; this is in contradiction with the previous statement. We analyze where the contradiction originates, and find the explanation. It resides in the fact that the definition in RFC 2598 is not easily implementable in schedulers we know of, mainly because it is not formal enough, and also because it does not contain an error term. We propose a new definition for the EF PHB, called "packet scale rate guarantee", which preserves the spirit of RFC 2598, while allowing a number of reasonable implementations, and has very useful properties for per-node and end-to-end network engineering. We show that this definition implies the rate-latency service curve guarantee. Then we propose some proven bounds on delay jitter for networks implementing this new definition, both in cases without loss and with loss.

We consider a scenario where multimedia data are sent over a network offering a guaranteed service. A smoothing device writes the stream into a transmitting device with limited input buffer; at the destination, the decoder waits for an initial playback delay and reads the stream from the receiver buffer. We assume that some limited look-ahead is possible at the source, and that the playback buffer size is limited. First, we consider the case where the stream is delivered from the source directly to the destination buffer. We obtain closed-form expressions of the minimal required values in the case of a CBR smoothing. Then we consider the case where the stream is first transmitted through a backbone network to an intermediate server, which relays the multimedia data to the final destination via an access network. We compute the requirements on playback delay, buffer sizes and amount of look-ahead.

We consider the transmission of variable bit rate (VBR) video over a network offering a guaranteed service such as ATM VBR or the guaranteed service of the IETF. The guaranteed service requires that the flow accepted by the network has to be conforming with a traffic envelope /spl sigma/. In this context, the output of the video encoder is constrained by the traffic envelope defined at the network entry point, the playback delay budget and the decoding buffer size. In previous works, the constraints are satisfied either by smoothing a fixed coder output, or by modifying the encoding parameters. In this paper we take a combined approach. This shows us to find a joint source rate selection/smoothing solution which minimizes the total average distortion while satisfying constraints on the traffic envelope, playback delay and decoding buffer size. Our solution is based on a Viterbi-like algorithm. Our approach is. Made possible by the representation of the optimally smoothed output as the time inverse of a shaper output. Experimental results exhibit significant improvements in terms of total average distortion compared to the smoothing of a fixed coder output, under equivalent traffic parameters and decoding constraints.

In this paper we simulated terminode routing. This routing scheme is designed for wide area networks, where a large part or all the nodes are mobile. Terminode routing is a combination of two protocols called Terminode Local Routing (TLR) and Terminode Remote Routing (TRR). TLR is used to route packets to close destinations. TRR is used to route to remote destinations and is composed of the following elements: Anchored Geodesic Packet Forwarding (AGPF), Anchored Path Discovery (APD), multipath routing and path maintenance. We performed simulations of the TLR and TRR protocols using the GloMoSim simulator. In order to do that, we have implemented a new mobility model that we call ``restricted random waypoint

Consider a network with an arbitrary topology and arbitrary communication delays, in which congestion control is based on additive-increase and multiplicative-decrease. We show that the source rates tend to be distributed in order to maximize an objective function called F/sub A//sup h/ ("F/sub A//sup h/ fairness"). We derive this result under the assumption of rate proportional negative feedback and for the regime of rare negative feedback. This applies to TCP in moderately loaded networks, and to those TCP implementations that are designed to interpret multiple packet losses within one RTT as a single congestion indication and do not rely on re-transmission timeout. This result provides some insight into the distribution of rates, and hence of packet loss ratios, which can be expected in a given network with a number of competing TCP or TCP-friendly sources. We validate our findings by analyzing a multiple-bottleneck scenario, and comparing with previous results (Floyd, 1991, Mathis et al, 1997) and an extensive numerical simulation with realistic parameter settings. We apply F/sub A//sup h/ fairness to gain a more accurate understanding of the bias of TCP against long round-trip times.

Network calculus is a collection of results based on MinPlus algebra, which applies to deterministic queuing systems found in communication networks. It can be used, for example, to understand the computations for delays used in the IETF guaranteed service, why re-shaping delays can be ignored in shapers or spacer-controllers, a common model for schedulers, etc. This short tutorial presents the basic results of network calculus and their application to some fundamental performance bounds in communication networks.

For pt. I see ibid., vol.4, p.93-6 (May 2000). We model some queuing systems arising in guaranteed service networks (such as RSVP/IP or ATM) as nonlinear min-plus systems that can be bounded by linear systems. We apply this method to the window flow control problem previously studied by Chang (1997), Agrawal and Rajan (1996), to the optimal smoothing of video through a network offering guaranteed service. We revisit the greedy shaper, and we also show how the same method enables us to compute the losses in a shaper by modelling it as a linear min-plus system. Finally, we describe the time-varying shaper.

Terminodes are personal devices that provide functionality of both the terminals and the nodes of the network. A network of terminodes is an autonomous, fully self-organized, wireless network, independent of any infrastructure. It must be able to scale up to millions of units, without any fixed backbone or server. In this paper we present the main challenges and discuss the main technical directions.

For original paper see Chlamtac et al. (IEEE/ACM Trans. Networking, vol.6, no.4, p.422-31, 1998 August). We prove that the buffer bound in the above paper, can be improved by using a modification of the proofs in the original paper together with so-called network calculus bounds. We also show that the delay bound in the above paper, is the sum of worst-case queueing delays at all nodes along the path of a connection.

We consider the transmission of variable bit rate (VBR) video over a network offering a guaranteed service such as ATM VBR or the guaranteed service of the IETF. The guaranteed service requires that the flow accepted by the network has to be conforming with a traffic envelope /spl sigma/; in return, it receives a service guarantee expressed by a network service curve /spl beta/. Functions /spl alpha/ and /spl beta/ are derived from the parameters used for setting up the reservation, for example, from the T-SPEC and R-SPEC fields used with the resource reservation protocol (RSVP). In order to satisfy the traffic envelope constraint, the output of the encoder is fed to a smoother, possibly with some look-ahead. The resulting stream is transported by the network; at the destination, the decoder waits for an initial playback delay and reads the stream from the receive buffer. We consider the problem of whether there exists one optimal strategy at the smoother which minimizes the playback delay and the receive buffer size, given the traffic envelope /spl alpha/ and the service curve /spl beta/. We show that there does exist such an optimal smoothing, and give an explicit representation for it. We also obtain a simple expression for the smallest playback delay and playback buffer size which can be achieved over all possible smoothing and playback strategies. We show that the computation of optimal smoothing and minimum playback delay do not depend on the past. We show that separate delay equalization is optimal in the constant bit rate (CBR) case, but not otherwise. We also apply the theory to the analysis of which T-SPEC should be requested by a source-destination pair, given some playback delay and buffer constraint, and given the path characteristics advertised in RSVP PATH messages.

The failure of a single optical link or node in a wavelength division multiplexing (WDM) network may cause the simultaneous failure of several optical channels. In some cases, this simultaneity may make it impossible for the higher level (SONET or IP) to restore service. This occurs when the higher level is not aware of the internal details of network design at the WDM level. We call this phenomenon "failure propagation." We analyze three types of failure propagation, called "bottleneck," "connectivity," and "multiple groups." Then we present a solution based on the definition of appropriate requirements at network design and a WDM channel placement algorithm, protection interoperability for WDM (PIW). Our method does not require the higher level to be aware of WDM internals, but still avoids the three types of failure propagation mentioned above. We finally show the result on various network examples.

Connection admission control (CAC) algorithms are used to decide whether an incoming connection should be accepted or rejected in a node of a network offering reservation based services in order to maintain the guaranteed quality of service (QoS) in the network. In this paper, we consider the statistical CAC algorithm proposed by Elwalid et al. (see IEEE JSAC, vol.13, no.6, p.1048-56, 1995). The traffic model is made of on-off sources and the QoS parameter is the loss probability. Based on the traffic descriptors of existing and incoming connections, the algorithm takes its decision by computing an upper bound of this probability and checking whether it is larger than a given tolerance /spl epsiv/. Usually this tolerance is a fixed, given parameter. We propose here to adapt /spl epsiv/ to react to the actual losses experienced at the node using a simple regulation mechanism: if the actual loss rate is much smaller than the targeted loss rate, /spl epsiv/ is increased to make a more aggressive usage of the available resources, and vice versa if the actual loss rate is too high. We discuss the influence of the regulation parameters and we show that despite its simplicity this regulated CAC improves significantly the performance of its non-tunable counterpart.

With wavelength division multiplexing (WDM) networks the failure of a single link or component may cause the simultaneous failure of several optical channels, potentially making impossible restoration by rerouting directly in higher layers directly using the optical network (SDH, ATM, internal protocol (IP)). To address this, we introduce the concept of design protection, which aims at making such failure propagations impossible. We present the disjoint alternate path (DAP) algorithm which places optical channels in order to maximize design protection. We show the result on various network examples.

We use previous network calculus results to study some properties of lossless multiplexing as it may be used in guaranteed service networks. We call network calculus a set of results that apply min-plus algebra to packet networks. We provide a simple proof that shaping a traffic stream to conform to a burstiness constraint preserves the original constraints satisfied by the traffic stream. We show how all rate-based packet schedulers can be modeled with a simple rate latency service curve. Then we define a general form of deterministic effective bandwidth and equivalent capacity. We find that call acceptance regions based on deterministic criteria (loss or delay) are convex, in contrast to statistical cases where it is the complement of the region which is convex. We thus find that, in general, the limit of the call acceptance region based on statistical multiplexing when the loss probability target tends to 0 may be strictly larger than the call acceptance region based on lossless multiplexing. Finally, we consider the problem of determining the optimal parameters of a variable bit rate (VBR) connection when it is used as a trunk, or tunnel, given that the input traffic is known. We find that there is an optimal peak rate for the VBR trunk, essentially insensitive to the optimization criteria. For a linear cost function, we find an explicit algorithm for the optimal remaining parameters of the VBR trunk.

We consider schemes for protecting a network using a wavelength division multiplexing (WDM) infrastructure against component or link failures. First, we explain how protection can be achieved by hardware redundancy. Then, we consider that with WDM networks, the failure of a single link or component may cause the simultaneous failure of several optical channels, potentially making impossible the restoration by rerouting in higher layers (SDH, ATM, IP). To address this, we introduce the concept of design protection, which aims at making such failure propagation impossible. We present the disjoint alternate path (DAP) algorithm which places optical channels in order to maximise design protection. We show the result on the example of the ARPA-2 network.

We consider the multiplexing of several variable bit rate (VBR) connections over one variable bit rate connection where the multiplexing uses a multiplexing buffer of size B. The VBR trunk is itself a connection and has a multidimensional connection descriptor, reflecting peak and sustainable rates. Given a cost function for the VBR trunk and a connection admission control (CAC) method for the input connections, we focus on the problem of finding the VBR trunk connection descriptor that minimizes the cost function and is able to accept set given set of VBR input connections. First, we show that, under reasonable assumptions on the cost function, the optimization problem can be reduced to a simpler one. Then we consider the homogeneous, loss-free case, for which we give an explicit CAC method. In this case, we find that, for all reasonable cost functions, the optimal VBR trunk is either of the CBR type, or is truly VBR, with a burst duration equal to the burst duration of the input connections. We show that the optimal peak cell rate is fixed for a given B (thus for a CBR trunk), and a VBR choice can only be an improvement. Lastly, we take as an example of the cost function the equivalent capacity of the VBR trunk. These results are expected to form the basis for a general method for a connection manager at a multiplexing node in an integrated services packet network.

We present a protocol for controlling a shared ATM multicast tree supporting many-to-many communication. The protocol supports one or several ATM virtual channel connections (VCCs) of the many-to-many type. The number of VCCs is independent of the number of endpoints. The protocol guarantees that there is no interleaving on any VCC of the tree. The protocol also guarantees that the traffic contract associated with the VCCs is respected, thus making it possible to use ordinary VCCs of the constant bit rate (CBR), variable bit rate (VBR), or unspecified bit rate (UBR) class. No resequencing server or cell buffering inside the network is required, and all cell forwarding is performed at the ATM layer. We describe the protocol both informally and formally.

article Free Access Share on About maximum transfer rates for fast packet switching networks Author: Jean-Yves Le Boudec IBM Research Division, Zurich Research Laboratory, 8803 Rüschlikon, Switzerland IBM Research Division, Zurich Research Laboratory, 8803 Rüschlikon, SwitzerlandView Profile Authors Info & Claims ACM SIGCOMM Computer Communication ReviewVolume 21Issue 4Sept. 1991 pp 295–305https://doi.org/10.1145/115994.116019Online:01 August 1991Publication History 2citation350DownloadsMetricsTotal Citations2Total Downloads350Last 12 Months14Last 6 weeks2 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Algorithms for solving for the cell loss rates in an asynchronous transfer mode (ATM) network using cell loss priorities are presented. With the loss priority scheme, cells of low-priority classes are accepted only if the instantaneous buffer queue length at the cell arrival epoch is below a given threshold. The input is modeled by Markov-modulated Bernoulli processes. The effect of the loss priority scheme on data, voice, and video traffic is investigated.>

We consider a multiclass service station with B identical exponential servers, with constant service rate μ. At a station, the classes of customers are sorted into M concurrent groups ; the discipline of service is on a first come first served basis, but two customers of the same group cannot be served simultaneously. We show that product form is maintained when such stations are inserted in BCMP networks, and give closed form expressions for the steady-state probabilities.