Browse ORBi by ORBi project

- Background
- Content
- Benefits and challenges
- Legal aspects
- Functions and services
- Team
- Help and tutorials

Rating Network Paths for Locality-Aware Overlay Construction and Routing ; Liao, Yongjun ; et al in IEEE/ACM Transactions on Networking (2015), 23(5), 1661-1673 This paper investigates the rating of network paths, i.e. acquiring quantized measures of path properties such as round-trip time and available bandwidth. Comparing to finegrained measurements, coarse ... [more ▼] This paper investigates the rating of network paths, i.e. acquiring quantized measures of path properties such as round-trip time and available bandwidth. Comparing to finegrained measurements, coarse-grained ratings are appealing in that they are not only informative but also cheap to obtain. Motivated by this insight, we firstly address the scalable acquisition of path ratings by statistical inference. By observing similarities to recommender systems, we examine the applicability of solutions to recommender system and show that our inference problem can be solved by a class of matrix factorization techniques. A technical contribution is an active and progressive inference framework that not only improves the accuracy by selectively measuring more informative paths but also speeds up the convergence for available bandwidth by incorporating its measurement methodology. Then, we investigate the usability of rating-based network measurement and inference in applications. A case study is performed on whether locality awareness can be achieved for overlay networks of Pastry and BitTorrent using inferred ratings. We show that such coarse-grained knowledge can improve the performance of peer selection and that finer granularities do not always lead to larger improvements. [less ▲] Detailed reference viewed: 230 (17 ULg)Cross-check of Analysis Modules and Reasoner Interactions ; ; et al Report (2015) This deliverable presents an extended set of Analysis Modules, including both the improvements done to those presented in deliverable D4.1 as well as the new analysis algorithms designed and developed to ... [more ▼] This deliverable presents an extended set of Analysis Modules, including both the improvements done to those presented in deliverable D4.1 as well as the new analysis algorithms designed and developed to address use-cases. The deliverable also describes a complete workflow description for the different use-cases, including both stream processing for real-time monitoring applications as well as batch processing for “off-line” analysis. This workflow description specifies the iterative interaction loop between WP2, WP3, T4.1, and T4.2, thereby allowing for a cross-checking of the analysis modules and the reasoner interactions. [less ▲] Detailed reference viewed: 31 (0 ULg)Design of Analysis Modules ; ; et al Report (2013) This public deliverable describes the design and specification of a first set of basic analysis modules for addressing the use cases identified in WP1. The document focuses on the required algorithms ... [more ▼] This public deliverable describes the design and specification of a first set of basic analysis modules for addressing the use cases identified in WP1. The document focuses on the required algorithms, which use as input the measurements and analysis provided by the lower layers (WP2 and WP3) of the mPlane architecture to provide more advanced analysis and answers towards the resolution of the problem addressed by the use case. These analysis modules include both stream and batch processing algorithms and address issues such as classifications, estimations, predictions, detections, correlations and diagnosis. [less ▲] Detailed reference viewed: 18 (0 ULg)DMFSGD: A Decentralized Matrix Factorization Algorithm for Network Distance Prediction Liao, Yongjun ; ; Geurts, Pierre et al in IEEE/ACM Transactions on Networking (2013), 21(5), 1511-1524 The knowledge of end-to-end network distances is essential to many Internet applications. As active probing of all pairwise distances is infeasible in large-scale networks, a natural idea is to measure a ... [more ▼] The knowledge of end-to-end network distances is essential to many Internet applications. As active probing of all pairwise distances is infeasible in large-scale networks, a natural idea is to measure a few pairs and to predict the other ones without actually measuring them. This paper formulates the prediction problem as matrix completion where the unknown entries in a pairwise distance matrix constructed from a network are to be predicted. By assuming that the distance matrix has a low-rank characteristics, the problem is solvable by lowrank approximation based on matrix factorization. The new formulation circumvents the well-known drawbacks of existing approaches based on Euclidean embedding. A new algorithm, so-called Decentralized Matrix Factorization by Stochastic Gradient Descent (DMFSGD), is proposed. By letting network nodes exchange messages with each other, the algorithm is fully decentralized and only requires each node to collect and to process local measurements, with neither explicit matrix constructions nor special nodes such as landmarks and central servers. In addition, we compared comprehensively matrix factorization and Euclidean embedding to demonstrate the suitability of the former on network distance prediction. We further studied the incorporation of a robust loss function and of non-negativity constraints. Extensive experiments on various publicly-available datasets of network delays show not only the scalability and the accuracy of our approach, but also its usability in real Internet applications. [less ▲] Detailed reference viewed: 205 (30 ULg)Learning to Predict End-to-End Network Performance Liao, Yongjun Doctoral thesis (2013) The knowledge of end-to-end network performance is essential to many Internet applications and systems including traffic engineering, content distribution networks, overlay routing, application-level ... [more ▼] The knowledge of end-to-end network performance is essential to many Internet applications and systems including traffic engineering, content distribution networks, overlay routing, application-level multicast, and peer-to-peer applications. On the one hand, such knowledge allows service providers to adjust their services according to the dynamic network conditions. On the other hand, as many systems are flexible in choosing their communication paths and targets, knowing network performance enables to optimize services by e.g. intelligent path selection. In the networking field, end-to-end network performance refers to some property of a network path measured by various metrics such as round-trip time (RTT), available bandwidth (ABW) and packet loss rate (PLR). While much progress has been made in network measurement, a main challenge in the acquisition of network performance on large-scale networks is the quadratical growth of the measurement overheads with respect to the number of network nodes, which renders the active probing of all paths infeasible. Thus, a natural idea is to measure a small set of paths and then predict the others where there are no direct measurements. This understanding has motivated numerous research on approaches to network performance prediction. Commonly, the success of a prediction system is built on its scalability, efficiency, accuracy and practicability. For network performance prediction, two specific requirements have to be met. First, the prediction system should have a decentralized architecture which allows the natural deployment of the system within a networked application. Second, as different performance metrics are useful for different applications, the prediction system should be general and flexible to deal with various metrics in a unified framework. This thesis presents practical approaches to network performance prediction. There are three main contributions. First, the problem of network performance prediction is formulated as a matrix completion problem where the matrix contains performance measures between network nodes with some of them known and the others unknown and thus to be filled. This new formulation is advantageous in that it is flexible to deal with various metrics in a unified framework, despite their diverse nature. The only requirement is that the matrix to be completed has a low-rank characteristic, which has long been observed in performance matrices constructed from various networks and in various metrics. Second, the matrix completion problem is solved by a novel approach called Decentralized Matrix Factorization by Stochastic Gradient Descent (DMFSGD). The approach requires neither explicit constructions of matrices nor special nodes such as landmarks and central servers. Instead, by letting network nodes exchange messages with each other, matrix factorization is collaboratively and iteratively achieved at all nodes, with each node equally retrieving a number of measurements. The approach is practical in that it is simple, with no infrastructure, and is computationally lightweight, containing only vector operations. Third, instead of the conventional representation of exact metric values, this thesis also investigates coarse performance representations including binary classes (The performance is classified into binary classes of either ``good'' or ``bad''.) and ordinal ratings (The performance is quantized from 1 star to 5 stars.). Such more qualitative than quantitative measures not only fulfill the requirements of many Internet applications, but also reduce the measurement cost and enable a unified treatment of various metrics. In addition, as both class and rating measures can be nicely integrated in the matrix completion framework, the same DMFSGD approach is applicable for their prediction, with little modification required. The resulting prediction system has been extensively evaluated on various publicly-available datasets of two kinds of metrics, namely RTT and ABW. These experiments demonstrate not only the scalability and the accuracy of the DMFSGD approach but also its usability in real Internet applications. In addition, the benefits of predicting performance classes and ratings, rather than their actual values, are demonstrated by a case study on peer selection, a function that is commonly required in a number of network applications. [less ▲] Detailed reference viewed: 99 (18 ULg)Ordinal Rating of Network Performance and Inference by Matrix Completion ; Liao, Yongjun ; Geurts, Pierre et al Report (2012) This paper addresses the large-scale acquisition of end-to-end network performance. We made two distinct contributions: ordinal rating of network performance and inference by matrix completion. The former ... [more ▼] This paper addresses the large-scale acquisition of end-to-end network performance. We made two distinct contributions: ordinal rating of network performance and inference by matrix completion. The former reduces measurement costs and unifies various metrics which eases their processing in applications. The latter enables scalable and accurate inference with no requirement of structural information of the network nor geometric constraints. By combining both, the acquisition problem bears strong similarities to recommender systems. This paper investigates the applicability of various matrix factorization models used in recommender systems. We found that the simple regularized matrix factorization is not only practical but also produces accurate results that are beneficial for peer selection. [less ▲] Detailed reference viewed: 51 (6 ULg)DMFSGD: A Decentralized Matrix Factorization Algorithm for Network Distance Prediction Liao, Yongjun ; ; Geurts, Pierre et al Report (2012) The knowledge of end-to-end network distances is essential to many Internet applications. As active probing of all pairwise distances is infeasible in large-scale networks, a natural idea is to measure a ... [more ▼] The knowledge of end-to-end network distances is essential to many Internet applications. As active probing of all pairwise distances is infeasible in large-scale networks, a natural idea is to measure a few pairs and to predict the other ones without actually measuring them. This paper formulates the distance prediction problem as matrix completion where unknown entries of an incomplete matrix of pairwise distances are to be predicted. The problem is solvable because strong correlations among network distances exist and cause the constructed distance matrix to be low rank. The new formulation circumvents the well-known drawbacks of existing approaches based on Euclidean embedding. A new algorithm, so-called Decentralized Matrix Factorization by Stochastic Gradient Descent (DMFSGD), is proposed to solve the network distance prediction problem. By letting network nodes exchange messages with each other, the algorithm is fully decentralized and only requires each node to collect and to process local measurements, with neither explicit matrix constructions nor special nodes such as landmarks and central servers. In addition, we compared comprehensively matrix factorization and Euclidean embedding to demonstrate the suitability of the former on network distance prediction. We further studied the incorporation of a robust loss function and of non-negativity constraints. Extensive experiments on various publicly-available datasets of network delays show not only the scalability and the accuracy of our approach but also its usability in real Internet applications. [less ▲] Detailed reference viewed: 48 (3 ULg)Decentralized Prediction of End-to-End Network Performance Classes Liao, Yongjun ; ; Geurts, Pierre et al in Proc. of the 7th International Conference on emerging Networking EXperiments and Technologies (CoNEXT) (2011, December 08) In large-scale networks, full-mesh active probing of end-to-end performance metrics is infeasible. Measuring a small set of pairs and predicting the others is more scalable. Under this framework, we ... [more ▼] In large-scale networks, full-mesh active probing of end-to-end performance metrics is infeasible. Measuring a small set of pairs and predicting the others is more scalable. Under this framework, we formulate the prediction problem as matrix completion, whereby unknown entries of an incomplete matrix of pairwise measurements are to be predicted. This problem can be solved by matrix factorization because performance matrices have a low rank, thanks to the correlations among measurements. Moreover, its resolution can be fully decentralized without actually building matrices nor relying on special landmarks or central servers. In this paper we demonstrate that this approach is also applicable when the performance values are not measured exactly, but are only known to belong to one among some predefined performance classes, such as "good" and "bad". Such classification-based formulation not only fulfills the requirements of many Internet applications but also reduces the measurement cost and enables a unified treatment of various performance metrics. We propose a decentralized approach based on Stochastic Gradient Descent to solve this class-based matrix completion problem. Experiments on various datasets, relative to two kinds of metrics, show the accuracy of the approach, its robustness against erroneous measurements and its usability on peer selection. [less ▲] Detailed reference viewed: 191 (20 ULg)Network Distance Prediction Based on Decentralized Matrix Factorization Liao, Yongjun ; Geurts, Pierre ; Leduc, Guy in Lecture Notes in Computer Science (2010, May 11), 6091 Network Coordinate Systems (NCS) are promising techniques to predict unknown network distances from a limited number of measurements. Most NCS algorithms are based on metric space embedding and suffer ... [more ▼] Network Coordinate Systems (NCS) are promising techniques to predict unknown network distances from a limited number of measurements. Most NCS algorithms are based on metric space embedding and suffer from the inability to represent distance asymmetries and Triangle Inequality Violations (TIVs). To overcome these drawbacks, we formulate the problem of network distance prediction as guessing the missing elements of a distance matrix and solve it by matrix factorization. A distinct feature of our approach, called Decentralized Matrix Factorization (DMF), is that it is fully decentralized. The factorization of the incomplete distance matrix is collaboratively and iteratively done at all nodes with each node retrieving only a small number of distance measurements. There are no special nodes such as landmarks nor a central node where the distance measurements are collected and stored. We compare DMF with two popular NCS algorithms: Vivaldi and IDES. The former is based on metric space embedding, while the latter is also based on matrix factorization but uses landmarks. Experimental results show thatDMF achieves competitive accuracy with the double advantage of having no landmarks and of being able to represent distance asymmetries and TIVs. [less ▲] Detailed reference viewed: 142 (20 ULg)Triangle Inequality Violation Avoidance in Internet Coordinate Systems Liao, Yongjun ; Leduc, Guy Poster (2009, August 24) Detailed reference viewed: 90 (15 ULg)Detecting Triangle Inequality Violations in Internet Coordinate Systems by Supervised Learning Liao, Yongjun ; ; et al in Lecture Notes in Computer Science (2009, May 12), 5550 Internet Coordinates Systems (ICS) are used to predict Internet distances with limited measurements. However the precision of an ICS is degraded by the presence of Triangle Inequality Violations (TIVs ... [more ▼] Internet Coordinates Systems (ICS) are used to predict Internet distances with limited measurements. However the precision of an ICS is degraded by the presence of Triangle Inequality Violations (TIVs). Simple methods have been proposed to detect TIVs, based e.g. on the empirical observation that a TIV is more likely when the distance is underestimated by the coordinates. In this paper, we apply supervised machine learning techniques to try and derive more powerful criteria to detect TIVs. We first show that (ensembles of) Decision Trees (DTs) learnt on our datasets are very good models for this problem. Moreover, our approach brings out a discriminative variable (called OREE), which combines the classical estimation error with the variance of the estimated distance. This variable alone is as good as an ensemble of DTs, and provides a much simpler criterion. If every node of the ICS sorts its neighbours according to OREE, we show that cutting these lists after a given number of neighbours, or when OREE crosses a given threshold value, achieves very good performance to detect TIVs. [less ▲] Detailed reference viewed: 127 (32 ULg) |
||