Browse ORBi by ORBi project

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

Improving Overlay Routing scalability using an Internet Coordinate System Cantin, François Doctoral thesis (2012) Nowadays lots of real time applications are used over the Internet: voice over IP, online video games, etc. For these applications the performance of the path between two communicating nodes is critical ... [more ▼] Nowadays lots of real time applications are used over the Internet: voice over IP, online video games, etc. For these applications the performance of the path between two communicating nodes is critical. Particularly, most of these applications require small delays between communicating nodes. For these applications, the problem is that the choice of the routes in the Internet is generally not very much guided by performance concerns. It is well known that for lots of node pairs the default Internet path is suboptimal and there exists an alternative path providing a smaller delay between these nodes. In this thesis, we mainly address the problem of finding these alternative paths. Replacing Internet's routing philosophy in order to obtain default paths providing the best performance possible should be a good theoretical solution. However, replacing Internet's routing philosophy by a brand new one is very difficult or even impossible in practice. Another solution is to leave the default routes as they are and to perform indirect routing. Consider a path AB between two nodes A and B. If a path ACB has a smaller delay than AB, then, instead of sending data directly to B, A can send them to C and C can relay them to B. This is called overlay routing because we manage the routing in an overlay network built on top of the Internet (i.e. at the application level). Overlay routing is a promising way to improve the quality of service in the Internet but its main drawback is its poor scalability: measuring the characteristics of the paths, exchanging the measurement results between the nodes and computing the best routes in the full mesh overlay network generally implies a high consumption of resources. In this thesis, our main contribution is the design of a lightweight one-hop overlay routing mechanism improving the latencies: we define criteria that rely on the information provided by an Internet Coordinate System (ICS) in order to provide a small set of potential one-hop shortcuts for any given path in the network with small costs. Our best criterion does not guarantee to find the best shortcut for any given path in a network but, even in networks with hundreds or thousands of nodes, it will restrict the search for potential shortcuts to about one or two percent of the total number of nodes. Even if the estimation-based approach of overlay routing is our main contribution, this thesis also presents general results about routing shortcuts and Internet Coordinate Systems. For an ICS, a routing shortcut is a Triangle Inequality Violation (TIV) and it is often a big problem. Indeed, a TIV will cause estimation errors since, in this particular case, nodes cannot be embedded into any metric space. In this thesis, we study TIVs existing in the Internet and their impact on the Vivaldi ICS. This analysis leads to two contributions. Firstly, we propose criteria to establish, with a high probability of success, if there exists a shortcut or not for a given path AB. Secondly, we propose a Two-Tier architecture for ICSes that mitigates the effect of TIVs on the estimations. Finally, this thesis also discusses the efficiency of two solutions proposed in the literature in order to obtain an ICS that can deal with TIVs. The first one consists in applying non-linear transformations to delays before trying to embed them in a metric space. The second one consists in modelling the estimation problem as a matrix completion problem in order to completely avoid the embedding in a metric space. [less ▲] Detailed reference viewed: 202 (25 ULg)Finding Routing Shortcuts using an Internet Coordinate System Cantin, François ; Leduc, Guy in Lecture Notes in Computer Science (2011, February 23), 6557 Overlay routing is a promising way to improve the quality of service in the Internet but its main drawback is scalability: measuring the characteristics of the paths, exchanging the measurement results ... [more ▼] Overlay routing is a promising way to improve the quality of service in the Internet but its main drawback is scalability: measuring the characteristics of the paths, exchanging the measurement results between the nodes and computing the best routes in the full mesh overlay network generally imply a high consumption of resources. In this paper, we design the basis of a lightweight self-organising one-hop overlay routing mechanism improving the latencies: we define criteria that rely on the information provided by an Internet Coordinate System (ICS) in order to provide a small set of potential one-hop shortcuts for any given path in the network with a small measurement cost. Our best criterion does not guarantee to find the best shortcut for any given path in a network but, even in networks with hundreds or thousands of nodes, it will restrict the search for potential shortcuts to about one or two percent of the total number of nodes. [less ▲] Detailed reference viewed: 91 (16 ULg)Transformation non linéaire des distances : une solution au problème des violations des inégalités triangulaires dans les systèmes de coordonnées ? Cantin, François ; Leduc, Guy ; Gueye, Cheikh Ahmadou Bamba in CFIP'2009 (2009, October 12) Network coordinate systems embed delay measurements (e.g. RTT) between Internet nodes into some metric space. It is well known that triangle inequality violations by the measured delays are a source of ... [more ▼] Network coordinate systems embed delay measurements (e.g. RTT) between Internet nodes into some metric space. It is well known that triangle inequality violations by the measured delays are a source of inaccuracy for coordinate systems. A solution to this problem has been proposed in [wan08]. The idea is to apply a non linear transformation to the measured delays in order to obtain delays which respect the triangle inequality. With this approach we can expect to obtain an estimated delay matrix that contains the triangule inequalities of the measured matrix. Such result is really interesting but we will show in this paper that the results are not as good as hoped. By using simulations, we have observed that the estimated delay matrices obtained by using non linear transformations of the delays are more accurate than what is usually obtained with a coordinate system. However, despite what [wan08] lets hope, it seems really difficult to obtain an estimated delay matrix that contains the same triangle inequality violations than the measured delay matrix. [less ▲] Detailed reference viewed: 163 (23 ULg)Detecting Triangle Inequality Violations in Internet Coordinate Systems ; Cantin, François ; Gueye, Cheikh Ahmadou Bamba et al in Future Networks 2009 (2009, June 18) Internet Coordinate Systems (ICS) have been proposed as a method for estimating delays between hosts without direct measurement. However, they can only be accurate when the triangle inequality holds for ... [more ▼] Internet Coordinate Systems (ICS) have been proposed as a method for estimating delays between hosts without direct measurement. However, they can only be accurate when the triangle inequality holds for Internet delays. Actually Triangle Inequality Violations (TIVs) are frequent and are likely to remain a property of the Internet due to routing policies or path inflation. In this paper we propose methods to detect TIVs with high confidence by observing various metrics such as the relative estimation error on the coordinates. Indeed, the detection of TIVs can be used for mitigating their impact on the ICS itself, by excluding some disturbing nodes from clusters running their own ICS, or more generally by improving their neighbor selection mechanism. [less ▲] Detailed reference viewed: 80 (29 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)Computing Convex Hulls by Automata Iteration Cantin, François ; ; Wolper, Pierre in International Journal of Foundations of Computer Science (2009), 20(4), 647-667 This paper considers the problem of computing the real convex hull of a finite set of n-dimensional integer vectors. The starting point is a finite-automaton representation of the initial set of vectors ... [more ▼] This paper considers the problem of computing the real convex hull of a finite set of n-dimensional integer vectors. The starting point is a finite-automaton representation of the initial set of vectors. The proposed method consists in computing a sequence of automata representing approximations of the convex hull and using extrapolation techniques to compute the limit of this sequence. The convex hull can then be directly computed from this limit in the form of an automaton-based representation of the corresponding set of real vectors. The technique is quite general and has been implemented. [less ▲] Detailed reference viewed: 79 (23 ULg)A Self-Organized clustering scheme for overlay networks Cantin, François ; Gueye, Cheikh Ahmadou Bamba ; Kaafar, Mohamed Ali et al in Lecture Notes in Computer Science (2008, December), 5343 Hierarchical approaches, where nodes are clustered based on their network distances, have been shown to allow for robust and scalable topology-aware overlays. Moreover, recent research works have shown ... [more ▼] Hierarchical approaches, where nodes are clustered based on their network distances, have been shown to allow for robust and scalable topology-aware overlays. Moreover, recent research works have shown that cluster-based deployments of Internet Coordinates Systems (ICS), where nodes estimate both intra-cluster and inter-cluster distances, do mitigate the impact of Triangle Inequality Violations (TIVs) on the distance predictions, and hence offer more accurate internet latency estimations. To allow the construction of such useful clusters we propose a self-organized distributed clustering scheme. For better scalability and efficiency, our algorithm uses the coordinates of a subset of nodes, known by running an ICS system, as first approximations of node positions. We designed and evaluated two variants of this algorithm. The first one, based on some cooperation among nodes, aims at reducing the expected time to construct clusters. The second variant, where nodes are selfish, aims at reducing the induced communication overhead. [less ▲] Detailed reference viewed: 93 (20 ULg)Overlay Routing using Coordinate Systems Cantin, François ; Gueye, Cheikh Ahmadou Bamba ; Kaafar, Mohamed Ali et al Poster (2008, December) We address the problem of finding indirect overlay paths that reduce the latency between pairs of nodes in an overlay. To this end we propose to rely on an Internet Coordinate System (ICS), namely Vivaldi ... [more ▼] We address the problem of finding indirect overlay paths that reduce the latency between pairs of nodes in an overlay. To this end we propose to rely on an Internet Coordinate System (ICS), namely Vivaldi, to estimate RTTs and help find these interesting detours. We define two initial criteria to illustrate our approach and assess their true/false positive rates. [less ▲] Detailed reference viewed: 111 (48 ULg)Computing Convex Hulls by Automata Iteration Cantin, François ; ; Wolper, Pierre in Lecture Notes in Computer Science (2008, July), 5148 This paper considers the problem of computing the real convex hull of a finite set of n-dimensional integer vectors. The starting point is a finite-automaton representation of the initial set of vectors ... [more ▼] This paper considers the problem of computing the real convex hull of a finite set of n-dimensional integer vectors. The starting point is a finite-automaton representation of the initial set of vectors. The proposed method consists in computing a sequence of automata representing approximations of the convex hull and using extrapolation techniques to compute the limit of this sequence. The convex hull can then be directly computed from this limit in the form of an automatonbased representation of the corresponding set of real vectors. The technique is quite general and has been implemented. Also, our result fits in a wider scheme whose objective is to improve the techniques for converting automata-based representation of constraints to formulas. [less ▲] Detailed reference viewed: 97 (37 ULg)Towards a Two-Tier Internet coordinate system to mitigate the impact of Triangle Inequality Violations Kaafar, Mohamed Ali ; Gueye, Cheikh Ahmadou Bamba ; Cantin, François et al in Lecture Notes in Computer Science (2008, May), 4982 Routing policies or path inflation can give rise to violations of the Triangle Inequality with respect to delay (RTTs) in the Internet. In network coordinate systems, such Triangle Inequality Violations ... [more ▼] Routing policies or path inflation can give rise to violations of the Triangle Inequality with respect to delay (RTTs) in the Internet. In network coordinate systems, such Triangle Inequality Violations (TIVs) will introduce inaccuracy, as nodes in this particular case could not be embedded into any metric space. In this paper, we consider these TIVs as an inherent and natural property of the Internet; rather than trying to remove them, we consider characterizing them and mitigating their impact on distributed coordinate systems. In a first step, we study TIVs existing in the Internet, using different metrics in order to quantify various levels of TIVs’ severity. Our results show that path lengths do have an effect on the impact of these TIVs. In particular, the shorter the link between any two nodes is, the less severe TIVs involved in are. In a second step, we do leverage our study to reduce the impact of TIVs on coordinate systems. We focus on the particular case of the Vivaldi coordinate system and we explore how TIVs may impact its accuracy and stability. In particular, we observed correlation between the (in)stability and high effective error of nodes’ coordinates with respect to their involvement in TIVs situations. We finally propose a Two-Tier architecture opposed to a flat structure of Vivaldi that do mitigate the effect of TIVs on the distances predictions. [less ▲] Detailed reference viewed: 133 (23 ULg)Explication et réduction de l’impact des violations d’inégalités triangulaires dans Vivaldi Cantin, François ; Gueye, Cheikh Ahmadou Bamba ; Kaafar, Mohamed Ali et al in CFIP'2008 (2008, March) Les systèmes de coordonnées sont des systèmes distribués ayant pour but, à partir de mesures de distance (par exemple RTT) entre certaines paires de noeuds, d’associer des coordonnées à chaque noeud dans ... [more ▼] Les systèmes de coordonnées sont des systèmes distribués ayant pour but, à partir de mesures de distance (par exemple RTT) entre certaines paires de noeuds, d’associer des coordonnées à chaque noeud dans un espace métrique. Toutefois, de tels systèmes ne fonctionnent pas correctement lorsque les distances mesurées ne respectent pas les inégalités triangulaires. Or, les violations de ces inégalités, appelées TIV, sont fréquentes dans l’Internet. Nous proposons une étude approfondie de l’impact des TIV sur le système de coordonnées Vivaldi. Nous quantifions et expliquons les erreurs de prédiction de distance et l’instabilité des coordonnées causées par les TIV selon leur fréquence et leur sévérité. Nous montrons aussi que la distance entre deux noeuds, mesurée par le RTT, est corrélée à la probabilité d’existence d’une TIV. Enfin, nous recommandons un système de coordonnées hiérarchique, et nous montrons, par des simulations sur une matrice de délais réelle, qu’une telle approche réduit l’impact des TIV. [less ▲] Detailed reference viewed: 62 (13 ULg) |
||