17340710
Stochastic analysis of packet-pair probing for network bandwidth estimation
In this paper, we perform a stochastic analysis of the packet-pair technique, which is a widely used method for estimating the network bandwidth in an end-to-end manner. There has been no explicit delay model of the packet-pair technique primarily because the stochastic behavior of a packet pair has not been fully understood. Our analysis is based on a novel insight that the transient analysis of the G/D/1 system can accurately describe the behavior of a packet pair, providing an explicit stochastic model. We first investigate a single-hop case and derive an analytical relationship between the input and the output probing gaps of a packet pair. Using this single-hop model, we provide a multi-hop model under an assumption of a single tight link. Our model shows the following two important features of the packet-pair technique: (i) The difference between the proposed model and the previous fluid model becomes significant when the input probing gap is around the characteristic value. (ii) The available bandwidth of any link after the tight link is not observable. We verify our model via ns-2 simulations and empirical results. We give a discussion on recent packet-pair models in relation to the proposed model and show that most of them can be regarded as special cases of the proposed model.
16295634
Robust delay estimator for playout buffering in Internet audio applications
In this paper, we propose a robust delay estimation scheme for Internet multimedia applications. The proposed scheme adopts an autoregressive (AR) model for the delay process. The adopted AR model is a natural generalization of the Jacobson's algorithm in TCP retransmission timeout (RTO) estimation. However, unlike fixed parameter values in the Jacobson's algorithm, the parameters of the proposed scheme adapt themselves to the estimation error via a robust identification algorithm. This robust identification algorithm usually leads to better performance when the noise is correlated and/or non-stationary, and it is also more robust to modeling uncertainties. As an application of the proposed algorithm, we consider the problem of delay prediction for audio playout buffering. We rigorously formulate the proposed scheme in the realm of multimedia audio mechanisms and give simulation result which shows its effectiveness.
14489739
Robust playout mechanism for Internet audio applications
In Internet audio applications, delay and delay jitter affect mostly the applications' quality of service. Since packet delays are different and changing over time, the receiver needs to buffer some amount of packets before playout. Therefore, the amount of buffered packets and the timing of playout are very important for the performance of applications. We adopt an autoregressive (AR) model for estimation of packet delay and deploy a robust identification algorithm for adjustment of the parameters of the AR process. In our preliminary experiments, this robust algorithm leads to better performance when the noise is correlated and/or non-stationary, and also it is robust to model uncertainties.
17238529
A distributed protocol for multi-class QoS provision in noncooperative many-switch systems
This paper presents an architecture for multi-class quality of service (QoS) provision in wide area networks. Users or applications are assumed to be selfish and end-to-end QoS is determined by the service levels received by an application traffic flow at each router or switch along a path. In previous work, we have given a comprehensive analysis of the noncooperative multi-class QoS provision game for single-switch systems showing when Nash equilibria exist and under what conditions they are Pareto and/or system optimal. In this paper, we propose a specific network architecture for facilitating noncooperative and of provision in many-switch systems such as the Internet with emphasis on realizability. We shield the user from having to choose the service classes on the switches along a route-a hard combinatorial optimization problem even assuming perfect knowledge about network state-while preserving the basic premise of selfishness. This is achieved by employing a set of QoS agents installed at routers which act on behalf of an user's traffic flow. The QoS agent intercepts packets entering a switch implementing generalized processor sharing (GPS) packet scheduling-and using only constant space packet header overhead and zero per-connection state at the routers-determines which service class to assign the packet to to satisfy the user's end-to-end QoS requirement at minimum cost. We present simulation results which show that our architecture is able to provide stable, stratified services to application traffic with diverse QoS requirements.
37635676
Efficient Algorithms for Approximate String Matching with Swaps
Most research on the edit distance problem and thek-differences problem considered the set of edit operations consisting of changes, insertions, and deletions. In this paper we include theswapoperation that interchanges two adjacent characters into the set of allowable edit operations, and we present anO(tmin(m,n))-time algorithm for the extended edit distance problem, wheretis the edit distance between the given strings, and anO(kn)-time algorithm for the extendedk-differences problem. That is, we add swaps into the set of edit operations without increasing the time complexities of previous algorithms that consider only changes, insertions, and deletions for the edit distance andk-differences problems.
11662197
pKASSO: Towards Seamless Authentication Providing Non-Repudiation on Resource-Constrained Devices
PKI is generally considered as the most appropriate solution for e-commerce and mutual authentication, owing to its digital signature and non-repudiation features. Asymmetric key operations of PKI require by far more CPU cycles than a symmetric cryptographic algorithm. It hampers the usability of PKI on resource-constrained devices. To overcome these limitations, we propose a new PKI- based authentication protocol and security infrastructure enhanced with single sign-on and delegation technology for a device with a restricted computing power. Although a conventional delegation mechanism cannot support non-repudiation mechanism against malicious user's behavior, our proposed protocol and security infrastructure can provide the mechanism by devising a referee server that generates binding information between a device and authentication messages, and retains the information in its local storage for future accusation.
11301244
On the effectiveness of route-based packet filtering for distributed DoS attack prevention in power-law internets
Denial of service (DoS) attack on the Internet has become a pressing problem. In this paper, we describe and evaluate route-based distributed packet filtering (DPF), a novel approach to distributed DoS (DDoS) attack prevention. We show that DPF achieves proactiveness and scalability, and we show that there is an intimate relationship between the effectiveness of DPF at mitigating DDoS attack and power-law network topology.The salient features of this work are two-fold. First, we show that DPF is able to proactively filter out a significant fraction of spoofed packet flows and prevent attack packets from reaching their targets in the first place. The IP flows that cannot be proactively curtailed are extremely sparse so that their origin can be localized---i.e., IP traceback---to within a small, constant number of candidate sites. We show that the two proactive and reactive performance effects can be achieved by implementing route-based filtering on less than 20% of Internet autonomous system (AS) sites. Second, we show that the two complementary performance measures are dependent on the properties of the underlying AS graph. In particular, we show that the power-law structure of Internet AS topology leads to connectivity properties which are crucial in facilitating the observed performance effects.
14277915
QoS-sensitive transport of real-time MPEG video using adaptive redundancy control
This paper presents an adaptive end-to-end protocol for quality of service (QoS)-sensitive transport of real-time MPEG video using packet-level forward error correction in dynamic networks. The objective is to facilitate a user-specified QoS end-to-end - i.e. without special network support - for real-time MPEG video whose timing constraints rule out the use of retransmission-based congestion control and QoS provisioning schemes. The degree of redundancy - overcode in forward error correction - injected into the network is adjusted as a function of network state, decreasing when the network is well-behaved to minimize unnecessary network resource consumption, and increasing when it is not to compensate for adverse network effects so as to maintain an invariant level of end-to-end QoS. We describe an adaptive packet-level forward error correction protocol called AFEC and analyze its properties with respect to optimality and stability. The optimal control problem is nontrivial due to the fact that increased redundancy, beyond a certain point, can backfire resulting in self-induced congestion which impedes the timely recovery of information - MPEG video frames - at the receiver. We experimentally evaluate the efficacy of our end-to-end QoS control by implementing and customizing AFEC to the transport of real-time MPEG video. We realize the system as a transport/application layer protocol running on UNIX workstations, and measure its performance over controlled network environments. We show that AFEC is able to effectively hide potentially adverse network effects such as packet drops and delays stemming from traffic burstiness and nonstationary structural changes using adaptive redundancy control, exporting a constant QoS service commensurate with user-specified QoS.