14611954
Limiting path exploration in BGP
Slow convergence in the Internet can be directly attributed to the "path exploration" phenomenon, inherent in all path vector protocols. The root cause for path exploration is the dependency among paths propagated through the network. Addressing this problem in BGP is particularly difficult as the AS paths exchanged between BGP routers are highly summarized. In this paper, we describe why path exploration cannot be countered effectively within the existing BGP framework, and propose a simple, novel mechanism - forward edge sequence numbers - to annotate the AS paths with additional "path dependency" information. We then develop an enhanced path vector algorithm, EPIC, shown to limit path exploration and lead to faster convergence. In contrast to other solutions, ours is shown to be correct on a very general model of Internet topology and BGP operation. Using theoretical analysis and simulations, we demonstrate that EPIC can achieve a dramatic improvement in routing convergence, compared to BGP and other existing solutions.
14053219
Distributed Algorithm for Service Replication in Service Overlay Network
The service overlay network (SON) is an effective mean to deploy end-to-end QoS guaranteed content delivery services on the current Internet. We model the content delivery service on a SON as a service delivery tree (SDT). Previous studies have addressed the optimal distribution tree formulation issues. In this paper, we focus on the problem of maximizing the total operation profit of the SON. In [1], authors introduced a cost model for optimal bandwidth provisioning in SON. In this paper, we extended this concept and propose an alternative approach to maximize the total effective throughput of SDT as well as to minimize the QoS violation penalty of the SON by service replication. We present both centralized and distributed algorithms for the placement of replicated servers on the SDT. Experiments are carried to quantify the merit, effectiveness and the scalability of the proposed service replication algorithm. In particular, the performance gain is very close to the exhaustive search. The algorithm performs well when we scale up the service overlay networks. Finally, we show that one only needs to perform a small number of replications to attain the optimal gain.
3065647
A core stateless bandwidth broker architecture for scalable support of guaranteed services
We present a novel bandwidth broker architecture for scalable support of guaranteed services that decouples the QoS control plane from the packet forwarding plane. More specifically, under this architecture, core routers do not maintain any QoS reservation states, whether per-flow or aggregate. Instead, the QoS reservation states are stored at and managed by a bandwidth broker. There are several advantages of such a bandwidth broker architecture. Among others, it avoids the problem of inconsistent QoS states faced by the conventional hop-by-hop, distributed admission control approach. Furthermore, it allows us to design efficient admission control algorithms without incurring any overhead at core routers. The proposed bandwidth broker architecture is designed based on a core stateless virtual time reference system developed recently. This virtual time reference system provides a unifying framework to characterize, in terms of their abilities to support delay guarantees, both the per-hop behaviors of core routers and the end-to-end properties of their concatenation. We focus on the design of efficient admission control algorithms under the proposed bandwidth broker architecture. We consider both per-flow end-to-end guaranteed delay services and class-based guaranteed delay services with flow aggregation. Using our bandwidth broker architecture, we demonstrate how admission control can be done on a per domain basis instead of on a "hop-by-hop" basis. Such an approach may significantly reduce the complexity of the admission control algorithms. In designing class-based admission control algorithms, we investigate the problem of dynamic flow aggregation in providing guaranteed delay services and devise a new apparatus to effectively circumvent this problem. We conduct detailed analyses to provide theoretical underpinning for our schemes as well as to establish their correctness. Simulations are also performed to demonstrate the efficacy of our schemes.
14141879
Improving VoIP quality through path switching
The current best-effort Internet cannot readily provide the service guarantees that VoIP applications often require. Path switching can potentially address this problem without requiring new network mechanisms, simply by leveraging the robustness to performance variations available from connectivity options such as multi-homing and overlays. In this paper, we evaluate the effectiveness and benefits of path switching in improving the quality of VoIP applications, and demonstrate its feasibility through the design and implementation of a prototype gateway. We argue for an application-driven path switching system that accounts for both network path characteristics and application-specific factors (e.g., codec algorithms, playout buffering schemes). We also develop an application path quality estimator based on the ITU-T E-model for voice quality assessment, and an application-driven path switching algorithm that dynamically adapts the time scales over which path switching decisions are made to maximize voice quality. Through network emulation and experiments over a wide-area multi-homed test bed, we show that, with sufficient path diversity, path switching can yield meaningful improvements in voice quality. Hence by exploiting the inherent path diversity of the Internet, application-driven path switching is a viable option in providing quality-of-service to applications.
33893889
Supporting stored video: reducing rate variability and end-to-end resource requirements through optimal smoothing
Variable-bit-rate (VBR) compressed video can exhibit significant multiple-time-scale bit-rate variability. In this paper we consider the transmission of stored video from a server to a client across a network, and explore how the client buffer space can be used most effectively toward reducing the variability of the transmitted bit rate. Two basic results are presented. First, we show how to achieve the greatest possible reduction in rate variability when sending stored video to a client with given buffer size. We formally establish the optimality of our approach and illustrate its performance over a set of long MPEG-1 encoded video traces. Second, we evaluate the impact of optimal smoothing on the network resources needed for video transport, under two network service models: deterministic guaranteed service (Chang 1994; Wrege et al. 1996) and renegotiated constant-bit-rate (RCBR) service (Grossglauser et al. 1997). Under both models, the impact of optimal smoothing is dramatic.
5876943
Adaptive packet sampling for flow volume measurement
Traffic measurement and monitoring are an important component of network management and traffic engineering. With high-speed Internet backbone links, efficient and effective packet sampling techniques for traffic measurement and monitoring are not only desirable, but also increasingly becoming a necessity. Since the utility of sampling depends on the accuracy and economy of measurement, it is important to control sampling error. In this paper we propose and analyze an adaptive, stratified random packet sampling technique for flow-level traffic measurement. In particular, we address the theoretical and practical issues involved. Through theoretical studies and experiments, we demonstrate that the proposed sampling technique provides unbiased estimation of flow size with controllable error bound, in terms of both packet and byte counts for elephant flows, while avoiding excessive oversampling.
14910614
An inequality between the diameter and the inverse dual degree of a tree
Let T be a nontrivial tree with diameter D(T) and radius R(T). Let I(T) be the inverse dual degree of T which is defined to be ΣueV(T) 1/d(u), where d(u) = (Συ∈ N(u)d(υ))/d(u) for u ∈ V(T). For any longest path P of T, denote by a(P) the number of vertices outside P with degree at least 2, b(P) the number of vertices on P with degree at least 3 and distance at least 2 to each of the end-vertices of P, and c(P) the number of vertices adjacent to one of the end-vertices of P and with degree at least 3. In this note we prove that I(T) ≥ D(T)/2+ a(P)/3 + b(P)/10 + c(P)/12 + 5/6. As a corollary we then get {R(T) + 1/3 if D(T) is odd, I(T) ≥ {R(T) + 5/6 if D(T) is even, with equality if and only if T is a path of at least four vertices. The latter inequality strengthens a conjecture made by the program Graffiti.
42927366
UML Modelling Web Applications via Formal Concept Analysis
2052039
Overlay Node Placement: Analysis, Algorithms and Impact on Applications
Overlay routing has emerged as a promising approach to improving performance and reliability of Internet paths. To fully realize the potential of overlay routing under the constraints of deployment costs in terms of hardware, network connectivity and human effort, it is critical to carefully place infrastructure overlay nodes to balance the trade-off between performance and resource constraints. In this paper, we investigate approaches to perform intelligent placement of overlay nodes to facilitate (i) resilient routing and (ii) TCP performance improvement. We formulate objective functions to accurately capture application behavior: reliability and TCP performance, and develop several placement algorithms, which offer a wide range of trade-offs in complexity and required knowledge of the client- server location and traffic load. Using simulations on synthetic and real Internet topologies, and PlanetLab experiments, we demonstrate the effectiveness of the placement algorithms and objective functions developed, respectively. We conclude that an approach, hybrid of random and greedy approaches, provides the best tradeoff between computational efficiency and accuracy. We also uncover the fundamental challenge in simultaneously optimizing for reliability and TCP performance, and propose a simple unified algorithm to achieve the same.
12105004
New Measurements and Corner-Guidance for Curve Matching with Probabilistic Relaxation
Reliable curve matching is a difficult yet important problem in many vision-based applications including image-based modeling. We describe in this paper two aspects of our research in this area: a new algorithm for curve matching (including lines) within a probabilistic relaxation framework, and an approach of incorporating previously matched points/corners to guide curve matching. We propose similarity-invariant unary and binary measurements suitable for curves, and introduce an additional measurement to model the uncertainty of the binary measurements. The uncertainty measure is proven to be very important in computing the matching support from neighboring matches. We also show how to use a set of previously matched points/corners to guide the curve matching. The role of the corner guidance is explicitly modeled by a set of unary measurements and a similarity function under the same relaxation framework. Preprocessing techniques contributing to the success of our curve matching techniques are also developed and discussed. Experiments with complex real scenes show that the rate of correct matching is higher than 98%.
6801587
Performance analysis of k-fold multicast networks
Multicast involves transmitting information from a single source to multiple destinations, and is an important operation in high-performance networks. A k-fold multicast network was recently proposed as a cost-effective solution to providing better quality-of-service functions in supporting real-world multicast applications. To give a quantitative basis for network designers to determine the suitable value of system parameter k under different traffic loads, in this paper, we propose an analytical model for the performance of k-fold multicast networks under Poisson traffic. We first give the stationary distribution of network states, and then derive the throughput and blocking probability of the network. We also conduct extensive simulations to validate the analytical model, and the results show that the analytical model is very accurate under the assumptions made. The analytical and simulation results reveal that by increasing the fold of the network, network throughput increases very fast when the fanouts of multicast connections are relatively small, compared with the network size.