Peer-to-peer systems are overlay networks used to distribute content to large sets of users by relying on computing and network resources directly provided by users that are receiving content. The current implementations of such systems are not specifically designed for considering the underlying internet topology or ISP link costs, resulting in a large amount of cross-ISP traffic. In this paper we analyze the impact of two P4P techniques aiming to optimize the distribution of content in the BitTorrent protocol. Results show that the proposed approaches can be beneficial from the ISP point of view. Moreover, the QoS perceived by users does not undergo any significant variation, especially when the load of the network is low.

In this paper, we propose a new algorithm for bilateral multi-attribute negotiations between autonomous agents with nonlinear utilities and detail on its application for pricing the wireless access services. In particular, we consider a scenario in which a wireless service provider adapts its offer of wireless bandwidth to the dynamics of the access demand and of the available spectrum. To achieve this, the provider performs one-to-one negotiations with the customers over the service transmission rate and the service price. The proposed negotiation algorithm is a practical solution for pricing those customers that require constant-rate service. Numerical simulations provide in-depth illustration of the scheme performance for various network settings.

Current multicast routing algorithms for multiprocessor systems are based on the reservation of transmission resources and buffer space for messages before transmission. This strategy causes cyclic dependencies among messages and, in turn, deadlock situations. This paper proposes and evaluates the performance of a new multicast routing algorithm, called Deadlock-Free Multicast Routing (DFMR), which removes the root cause of deadlocks. DFMR prevents deadlocks by allowing nodes to send flits as soon as internode links are available for transmission. This is obtained by allowing any possible interleaving of flits from all messages on internode links. The resulting routing algorithm eliminates the need to implement deadlock avoidance, detection, and recovery mechanisms, but needs larger output buffers. In DFMR, message flits carry additional information overhead which is used to avoid deadlock. Simulation results show that this information overhead has a negligible impact on overall performance which is considerably greater than that of previous algorithms.

The statistical approaches of resource allocation require that input traffic is Gaussian. The Gaussian hypothesis is guaranteed by the central limit theorem (CLT), that is verified when several hundreds of independent flows are multiplexed. In realistic scenarios few flows and long range dependent video traces can be multiplexed, in this case the input traffic can't be considered Gaussian. In this paper, we propose a procedure in order to evaluate the statistical quality-of-service (QoS) guarantees expressed in terms of a delay bound, d and a delay violation probability, p. In particular, we extend the network calculus, developed for Gaussian traffic and founded on the maximum variance approximation (MVA), to scenarios with non-Gaussian traffic where few users download MPEG movies. The analysis is carried out for single and multiple-node, with homogeneous and heterogeneous traffic flows. We provide an approximation of the end-to-end delay violation probability evaluated by means of a new framework for stochastic network calculus, denoted as the bounded-variance network calculus. The results show that our procedure, in all scenarios, provides a delay violation probability for non-Gaussian input traffic (MPEG video traces), very close to the values obtained with simulations.

In this paper, we develop a method for analyzing time-varying wireless channels in the context of the modern theory of the stochastic network calculus. In particular, our technique is applicable to channels that can be modeled as Markov chains, which is the case of channels subject to Rayleigh fading. Our approach relies on theoretical results on the convergence time of reversible Markov processes and is applicable to chains with an arbitrary number of states. We provide two expressions for the delay tail distribution of traffic transmitted over a fading channel fed by a Markov source. The first expression is tighter and only requires a simple numerical minimization, the second expression is looser, but is in closed form.

This paper proposes an analytical method to evaluate the delay violation probability of traffic flows with statistical quality-of-service (QoS) guarantees in a generalized processor sharing scheduler. The statistical QoS targets, for each service class, are expressed in terms of a delay threshold and delay violation probability. We study both the single node and the end- to-end paths comprising multiple schedulers. Moreover, we assume that traffic admits a linear variance envelope, therefore, we account for leaky-bucket-regulated traffic, for general Markov-modulated Poisson process sources and Markov-modulated fluid process sources and, more in general, to the wide class of sources for which the variance of the cumulative generated traffic can be upper bounded by a linear function of time. Under these assumptions, we are able to derive an approximation on delay distributions for each class of the GPS scheduler. Moreover, by exploiting a novel framework for the calculation of statistical end-to-end delay bounds (the bounded variance network calculus) we iterate our formulas, derived for the isolated node, to multi-node paths and, in turn, we provide analytical forms for the end-to-end delay. Numerical investigation shows that our approximations are very close to the simulated values.

Given a policer with a generic deterministic constraint function and given an input traffic with average rate smaller than the average service rate of the policer, the variance var(y(t)) of the policer's cumulative output traffic y(t) satisfies the asymptotic property var(y(t)) isin O(t2) for t rarr infin.

Application- and context-aware infrastructures involve the network in the execution of distributed applications through special devices, namely, theapplication cards, placed in network nodes. The sharp separation of applications and network is smoothed, and by performing part of the distributed application inside the network, it is possible to reduce costs and improve performance with a better optimization of the whole distributed information and communication technology (ICT) infrastructure. This optimization is allowed by the additional degrees of freedom of placing cards in nodes and of assigning applications to such cards. In this paper, we provide an optimization algorithm that minimizes the total cost of the entire distributed ICT infrastructure, given a target performance objective defined as the end-to-end delay for the completion of the distributed application tasks. We focus on two sample applications that are well suited for application- and context-aware infrastructures:cachingandprotocol translation. The joint optimization of computing and communication resources is an innovative contribution of this paper, as, in the literature, hardware and network components are typically optimized separately. Results show that the total infrastructural cost savings are in the range of 15%-20%. However, savings can be obtained only if cards satisfy a cost-performance curve that is also analyzed.

Long-range dependence (LRD) is a widely verified property of Internet traffic, which severeiy affects network performance yielding longer queuing delays. Token-bucket policers are commonly proposed to enforce the statistical profile of input traffic, but they can hardly reduce LRD and thus can be ineffective to protect service level agreements against LRD increase in input traffic. In this paper, we investigate by simulation the queuing performance in a downstream scheduler of LRD traffic regulated by token-bucket policers. We compare the delay distributions of regulated and unregulated LRD flows. We demonstrate that policers reduce significantly the downstream queuing delay, although they do not alter much the 1/falphaspectrum of regulated traffic. We observe also that the policed traffic does not obey a plain fractional Gaussian traffic model: first, it is not Gaussian anymore; moreover, also its third-order two-lags covariance is altered by the policer. Finally, we point out that policers can reduce noticeably the negative impact of traffic LRD increase on queuing delay, although they can diminish actual LRD only slightly.

Long-range dependence (LRD) is a widely verified property of traffic crossing the wireless LAN radio interface. LRD severely affects network performance yielding longer queuing delays. In this paper, we study how LRD and non-LRD traffic flows influence each other in the IEEE 802.11e wireless access network and their queuing behaviour in downstream schedulers. We consider scenarios with one and two wireless hops. We investigate interaction of traffic flows with the service class separation enabled by the IEEE 802.11e EDCA function, comparing results with those of the basic scenario with a single service class shared by all traffic flows. We find that a partial isolation of service classes is enabled by the IEEE 802.11e access function. However, competing flows exhibit a queuing behavior, in downstream schedulers, which cannot be accounted for by standard LRD traffic descriptors.

Long-range dependence (LRD) is a widely verified property of Internet traffic, which severely impacts network performance yielding longer queuing delays. Moreover, LRD is almost ubiquitous and very hard to remove or control. In this work, we investigated by thorough simulation the effect of schedulers on traffic LRD. We analyzed the output traffic of schedulers merging LRD flows according to various service policies, viz. plain FIFO, static-priority, earliest-deadline-first and general processor sharing. First, we noticed that traffic LRD is not affected much by crossing the scheduler, for any type of service policy. Second, we showed that LRD also propagates across different service classes with any policy except balanced GPS, which ensures complete separation between classes. This phenomenon may explain in part why LRD is so widespread in Internet traffic.

In this paper, we study the Skype system in order to determine the presence of bottleneck for its scalability. In fact, as the Internet grows and the number of Skype users increases constantly, the Skype traffic carried by network links grows and also the load of Skype supernodes increases, mainly due to the need of relaying calls for users behind NAT restrictions. We model both the underlay Internet at the inter-autonomous system level and the overlay Skype system. We let the two systems interact through a computer implementation of their respective models and, by varying critical parameters such as the size of the underlay Internet, the number of Skype users, the per-user traffic and the percentage of users behind NAT restrictions, we calculate the sensitivity of link load and of the supernode load to these parameters. In this way, we are able to determine in which conditions link load and supernode load may become a bottleneck for the scalability of the Skype system.

Currently, the most advanced framework for stochastic network calculus is the min-plus algebra, providing bounds for the end-to-end delay in networks. The bounds calculated with the min-plus algebra are tight, if compared with previous methods, but we still observe a significant degradation of the tightness of bounds as the number of nodes crossed by flows increases. Moreover, even if the calculations are greatly simplified relatively to previous methods, they are still complicated as numerical optimizations are necessary. In this paper, we propose a novel framework for the approximated calculation of end-to-end delay: the bounded-variance network calculus, by which we provide two important results. Firstly, we obtain an evaluation of end-to-end delay significantly tighter than that offered by the min-plus algebra. Secondly, the calculations needed to compute our approximations of delay are much simpler and we show that in a typical application scenario used to test the accuracy of the frameworks for network calculus, our approximations are obtained in a closed analytical form, as opposed to the numerical bounds of the other methods. These two advantages constitute an important progress in the direction of evolving statistical network calculus into a practical tool for network analysis.

Peer-to-peer networks are an increasingly popular solution for the distribution of media content to a large number of users, with limited investments for network infrastructures. The distribution of a real time video stream imposes strict performance requirements such as small playback delays and few frame losses. In this paper, we focus on peer-to-peer video streaming systems with tree or forest content distribution structure and we provide a sensitivity analysis to investigate the impact of three critical parameters - rejoin time, average permanence time of peers and playback threshold - over the quality of the video stream received by users. The study, carried out through simulation, considers a general peer-to-peer video streaming reference model with tree/forest topology.

Access control for group communication must ensure that the legitimate users are able to access the authorized data streams, while preventing the non-legitimate users from gleaning any unauthorized data stream. This could be done by distributing an encrypting key to each member of the group to be secured. To achieve a high level of security, the group key should be changed every time a user joins or leaves the group, so that a former group member has no access to current communications and a new member has no access to previous communications. Since group memberships could be very dynamic, the group key should be changed frequently. So far, different schemes for efficient key distribution have been proposed to limit the key-distribution overhead. In previous works, the performance comparison among these different schemes have been based on simulative experiments, where a set of users join and leave a secure group according to a basic statistical representation of users’ behavior. In this paper we propose a new statistical model to represent users’ behavior and compare it to the modelling approach so far adopted in the literature. Our new model is able to achieve a superior statistical confidence of the results and to lead the system to a steady state. In particular, we apply our new model to the comparison of two recent proposals for key distribution in order to show the better quality of the results achieved by means of our model.

Long-range dependence (LRD) is a largely verified property of Internet traffic, which severely affects network queuing An approach for guaranteeing performance requirements is controlling the statistical profile of input traffic by policing or shaping regulators. In this paper, it is investigated by simulation how the 1/falphaspectrum of LRD traffic is altered when this is regulated by either policers or shapers. Traffic spectral analysis is carried out mainly by the Modified Allan Variance, a time-domain quantity with demonstrated superior accuracy in fractional-noise parameter estimation. The queuing behaviour of LRD regulated traffic in FIFO schedulers is also investigated. Conditions under which service level agreements based on delay bounds can be violated, by varying alpha in input LRD traffic, are examined.

In this paper, we develop a method for using traffic sources modelled as a Markov modulated Poisson processes (MMPP) in the framework of the recently developed theory of the statistical traffic and service envelopes, referred to as thestatisticalapproach. The statistical approach is a powerful and general framework for providing straightforwardly an approximated evaluation of the delay and buffer tail distributions in network schedulers. However, the input of the statistical approach is the statistical traffic envelope, which is not available for generic MMPP sources. We provide two statistical traffic envelopes, namedtwo-momentsandupper-boundingbucket, for a generic MMPP source, so as to use the rich collection of MMPP models of voice, audio, data and video sources available in the literature within the framework of the statistical approach. In this way, we can avoid the computational complexity of traditional Markov analysis with MMPP traffic, due to the exploding number of states as the number of MMPP sources grows. The tighter approximation is provided by the two-moments envelope while with the upper-bounding bucket envelope we can obtain simple closed-form solutions.

Long-range dependence (LRD) is a largely verified property of Internet traffic, which severely affects queuing performance in network buffers. A common approach for guaranteeing performance requirements is to control the statistical profile of the input traffic by regulators based on the leaky bucket scheme. In this paper, we investigate by simulation how the l/falphapower-law spectrum of LRD traffic is altered when traffic is regulated by a leaky bucket policer. Analysis of the traffic spectral characteristics is carried out mainly by means of the modified Allan variance, a time-domain quantity with demonstrated superior accuracy in fractional-noise parameter estimation, recently introduced also for traffic analysis. This approach allows to get a finer insight into power-law spectral characteristics of policed traffic. We also investigate some other properties of the leaky bucket fed with LRD traffic, such as its dropping probability and its effect on queuing delay in a following FIFO scheduler.

In this paper, we study the problems of resource allocation and admission control of traffic flows with guaranteed quality of service. Specifically, we deal with traffic flows regulated by dual-leaky buckets and we establish the analytical expressions for (a) the minimum capacity to be allocated in order to guarantee the required delay performance and for (b) the maximum number of flows that is possible to accept, known the link capacity, with statistical QoS constraints on the delay. With the closed-form formulae obtained with our analysis, we compare the performance of the dual-leaky-bucket and of the simpler token-bucket regulators, and we discuss the conditions that make the dual-leaky bucket outperform the token bucket.

A linear bounded arrival process (LBAP) traffic regulator is characterized by two parameters, the token rate r and the bucket size b, and the design of such a traffic regulator consists in selecting the most appropriate (r, b) pair according to a performance metric to be optimized. This (r, b) pair is currently selected through a two-step process. Firstly, the LBAP curve of the regulator, formed by all the pairs (r, b) satisfying an assigned performance target, is calculated. On the LBAP curve, all the pairs (r, b) are equivalent, as far as the assigned performance target is concerned. In the second step the preferred (r, b) pair on the LBAP curve is chosen according to an additional criterion, which makes it possible to optimise an objective function. Usually, this objective function accounts for the performance of the regulator only, without considering the transport of the regulated traffic flow from the output of the regulator to the final destination through the network. In this work, we propose an alternative approach to perform the second step of the selection of the (r, b) pair on the LBAP curve. Our approach, the minimum capacity criterion, as opposed to traditional methods considering the regulator alone, chooses the (r, b) pair which minimizes the network capacity allocated in order to guarantee the end-to-end negotiated delay of the traffic flow. We show that with our criterion this capacity is much smaller than that required with other criterions presented in the literature.

A novel location-based multicast routing protocol for ad-hoc networks is proposed. Starting from a well-known extension of the GPSR protocol to multicast, reduced bandwidth consumption is obtained by performing clustering estimation of the destination group and by considering each cluster as a single node for packet forwarding. As the new protocol limits the number of packet replications, network efficiency is improved. When real-time multicast traffic is carried, the packet delivery ratio is increased without noticeably affecting end-to-end delay. We study the performance of our protocol through simulation, with a simulator implementing a full MAC protocol. This allows to measure the performance in bandwidth-limited scenarios and to validate the results

This paper proposes a routing algorithm for the interconnection of multiple processors based on the shortest-path and deflection-routing principles. The routing algorithm, named SPDRA (Shortest Path and Deflection Routing Algorithm), is applied to multiprocessor systems with a single-stage shuffle physical topology. SPDRA is general-purpose, as opposed to the majority of routing algorithms for multiprocessor systems which are optimized for particular traffic patterns generated by a restricted class of parallel algorithms. The general-purpose nature of SPDRA allows perfomance comparisons with a wide class of routing algorithms for multiprocessor systems that, similar to the single-stage shuffle physical topology, have a fixed node-to-processor ratio. The paper compares SPDRA with hypercube algorithms for bidimensional meshes and torus physical topologies, routing algorithms for hierarchical tridimensional tori, and algorithms for routing permutations in shuffle networks, which constitute the most widely accepted approaches for multiprocessor interconnection. SPDRA exhibits a performance advantage for a broad range of network sizes and, in general, the performance advantage grows as the number of processors increases. However, this paper compares the SPDRA algorithm against a limited set of multiprocessor systems and does not demonstrate a general superiority of SPDRA over all systems with a fixed node-to-processor ratio and, especially, with a growing node-to-processor ratio, such as multistage networks.

The paper faces the problem of the runtime negotiation on the traffic conditioning agreement (TCA) and service level agreement (SLA) in IP differentiated services (DiffServ) networks. A first contribution of the paper with respect to previous literature is to propose a multi-attribute description of QoS targets and traffic profile. A second contribution of this work is to provide a mathematical formalization of the negotiation problem suitable for automated negotiation. The model is tested through simulation to a) verify the convergence of the negotiation process, which is critical to ensure that negotiation can be performed automatically and b) analyze the agreement solutions that are reached by negotiation parties for different values of quality of service and price parameters. Results show that the model has a sound convergence. With this paper's negotiation model, the primary goal of negotiating parties is to maintain the value of their utility function constant by searching a trade-off between QoS and price. However, the willingness to cooperate of the negotiating parties has a strong impact on the agreement value of negotiation parameters.

This work proposes an enhancement of the GPSR routing protocol to improve the performance of point-to-point IP-based voice communications in a vehicular ad-hoc network. Our enhancement reduces significantly the end-to-end delay in ad-hoc networks using a TDMA-based medium access control protocol. The proposed enhancement of GPSR routing basically consists in an optimized choice of the next hop node based on the time slot used by the node to transmit outgoing packets. We evaluate the performance improvements in terms of end-to-end packet delay, packet loss ratio and synthetic mean opinion score that users would assign to the voice communications. We show that, with our procedure, it is possible to obtain a significant performance improvement in terms of network scalability and quality of IP telephone calls

We propose a new power control algorithm capable of managing the topology of a vehicular ad hoc network by adjusting transmission power dynamically. Our algorithm is simple to implement, as it is based only on local information and no exchange of power-related signaling among nodes is required. The algorithm has the objective of making the network operate with both a very low and a very high user density, while maintaining its performance unaltered. This target is obtained by controlling transmission power, so that the number of neighbors of each node is always within a minimum and maximum threshold. In this way, it is possible to cope concurrently with the problems of node isolation and clustering at low load and of excessive competition for radio resources at high load. Finally, the algorithm provides high channel availability for connected users. The algorithm is robust, as performance does not depend on user speed, which has a large variance in a vehicular scenario.

Most analytical models for the evaluation of convergence and capacity of WCDMA systems aim at evaluating only the outage probability of a given cellular deployment scenario. This is not in line with the ETSI guidelines for performance evaluation, which state that the coverage and the capacity of the system should be measured in terms of a given percentage of unsatisfied users. In this paper, we elaborate an analytical model capable of giving such a figure. In addition, a comparison between analytical and simulation results confirms the validity of the proposed model.

The design of an efficient MAC protocol is of paramount interest for the definition of a wireless ATM (WATM) access. In the case of TDMA-TDD WATM access, the current trend in the standardization bodies is to adopt frames of fixed duration, whose slots are shared among uplink and downlink connections under the control of a MAC scheduler located in the base station. In this paper, we first compare polling and contention techniques, in order to identify the best access scheme to serve ATM connections. Then, since the knowledge of the queue status of the portable terminals can be used by the centralized scheduler to increase the efficiency of the slot assignment procedure, we propose different algorithms to code the buffer occupancy status. Moreover, we compare their performance by considering two different scenarios; the first loaded with ON-OFF sources served by nrt-VBR ATM connections, and the second with TCP/IP sources served by UBR ATM connections. The results show the superiority of the contention access and the advantages of the buffer status notification for the scheduler at the base station.

Extended generalized shuffle (EGS) networks are a wide class of interconnection networks introduced by Richards (1993). In this work, we study the blocking performance of EGS networks under point-to-multipoint traffic. Two new routing algorithms for multicast connections in EGS networks are defined, and a theorem proving that these algorithms construct minimum-cost connection trees is enclosed. Simulation results show that the blocking performance of EGS networks under multicast traffic is much better than that of three-stage Clos networks of equal complexity.

The Internet Engineering Task Force (IETF) has defined the integrated IP services (IIS), with guaranteed quality of service (QoS): the guaranteed and the controlled load services. In particular, the controlled load service (CLS) offers a level of service close to that of the classic best-effort service also under a heavy load. The IETF is considering the ATM CBR, nrt-VBR, and ABR service classes for the transport of CLS over ATM. The first two classes are compared, in order to determine which is the most convenient.

Shuffleout is a blocking multistage asynchronous transfer mode (ATM) switch using shortest path routing with deflection, in which output queues are connected to all the stages. This paper describes a model for the performance evaluation of the shuffleout switch under arbitrary nonuniform traffic patterns. The analytical model that has been developed computes the load distribution on each interstage link by properly taking into account the switch inlet on which the packet has been received and the switch outlet the packet is addressing. Such a model allows the computation not only of the average load per stage but also its distribution over the different links belonging to the interstage pattern for each switch input/output pair. Different classes of nonuniform traffic patterns have been identified and for each of them the traffic performance of the switch is evaluated by thus emphasizing the evaluation of the network unfairness.

The paper studies three-stage switching networks capable of routing point-to-multipoint connections. Strict-sense non-blocking operation is addressed and, in particular, the necessary and sufficient condition for a three-stage switching network to be strictly non-blocking when it is offered point-to-multipoint traffic is derived. This condition is given as a function both of the minimum and the maximum number of network outlets addressed by each connection. In this respect, the paper extends the well known Clos' result, giving the necessary and sufficient condition for a three-stage switching network to be strictly non-blocking when it is offered point-to-point traffic. The complexity of a three-stage network is lower than that of a crossbar of equal size only for small values of the maximum admissible fanout of the incoming connections.>

A new class of switching architectures for broadband packet networks, called shuffleout, is described and analyzed in the paper. Shuffleout is basically an output-queued architecture with a multistage interconnection network built out of unbuffered b/spl times/2b switching elements. Its structure is such that the number of cells that can be concurrently switched from the inlets to each output queue equals the number of stages in the interconnection network. The switching element operates the cell self-routing adopting a shortest path algorithm which, in case of conflict for interstage links, is coupled with deflection routing. The paper presents the basic shuffleout architecture, called open-loop shuffleout, in which the cells that cross the whole interconnection network without entering the addressed output queues are lost. The key target of the proposed architecture is coupling the implementation feasibility of a self-routing switch with the desirable traffic performance typical of output queueing.>

A new class of switching architectures for broadband packet networks, called shuffleout, is described and analyzed. Shuffleout is basically an output-queued architecture with a multistage interconnection network built out of unbuffered b/spl times/2b switching elements. Its structure is such that the number of cells that can be concurrently switched from the inlets to each output queue equals the number of stages in the interconnection network. The switching element operates the cell self-routing adopting a shortest path algorithm which, in case of conflict for interstage links, is coupled with deflection routing. The basic version of this architecture is called open-loop shuffleout. This paper describes the closed-loop shuffleout architecture with 2/spl times/4 switching elements in which cells that have crossed the whole interconnection network re-enter the network as long as they are not successfully routed to the addressed switch outlet. This result is accomplished by adding to the basic open-loop structure recirculation paths so that each packet can cross several times the interconnection network. Two different solutions are proposed to implement such functionality, the buffered closed-loop shuffleout and the expanded closed-loop shuffleout architecture. Both these solutions aim at reducing the number of stages in the network, compared to the open-loop structure, so as to reduce the complexity of the switch internal wiring and to simplify the output queue interface.>

A new class of asynchronous transfer mode (ATM) switching architectures for broadband packet networks, called Shuffleout, is introduced. Its interconnection network is a multistage structure built out of unbuffered 2*4 switching elements. Shuffleout is basically an output-queued architecture in which the number of cells that can be concurrently switched from the inlets to each output queue equals the number of stages in the interconnection network. The switching element operates the cell self-routing adopting a shortest path algorithm which, in case of conflict for interstage links, is coupled with deflection routing. The specific architecture presented is called Closed-Loop Shuffleout, since the cells that cross the whole interconnection network without entering the addressed output queues are lost. The key target of the proposed architecture is coupling the implementation feasibility of a self-routing switch with the desirable traffic performance typical of output queueing.>