Topology inference using network coding. Fragouli, C., Markopoulou, A., & Diggavi, S. N. Allerton, 2006. abstract bibtex The network coding paradigm is based on the idea that independent information flows can be linearly combined throughout the network to give benefits in terms of throughput, complexity etc. In this paper, we explore the application of the network coding paradigm to topology inference. Our goal is to infer the topology of a network using multiple sources and observations at the edges of the network. In particular, we consider networks where multiple sources send probes and intermediate nodes locally combine probe packets (perform XOR-operations in incoming links). In previous works (e.g., Ratnasamy & McCanne '99; Duffield et al '02), the correlation between the observed packet loss patterns is used to infer the underlying topology. In contrast, our main idea behind using network coding is to introduce correlations among multiple probe packets in a topology dependent manner and also develop algorithms that take advantage of these correlations to infer the network topology from end-host observations. Preliminary numerical results illustrate the performance benefits of this approach. In particular, in the absence of packet loss, we can deterministically infer the topology, with very few probes; in the presence of packet loss, we can rapidly infer topology, even at very small loss rates (which was not the case in previous tomography techniques).
@article{fragouli_topology_2006,
abstract = {The network coding paradigm is based on the idea that independent information flows can be linearly combined throughout the network to give benefits in terms of throughput, complexity etc. In this paper, we explore the application of the network coding paradigm to topology inference. Our goal is to infer the topology of a network using multiple sources and observations at the edges of the network. In particular, we consider networks where multiple sources send probes and intermediate nodes locally combine probe packets (perform XOR-operations in incoming links). In previous works (e.g., Ratnasamy \& McCanne '99; Duffield et al '02), the correlation between the observed packet loss patterns is used to infer the underlying topology. In contrast, our main idea behind using network coding is to introduce correlations among multiple probe packets in a topology dependent manner and also develop algorithms that take advantage of these correlations to infer the network topology from end-host observations. Preliminary numerical results illustrate the performance benefits of this approach. In particular, in the absence of packet loss, we can deterministically infer the topology, with very few probes; in the presence of packet loss, we can rapidly infer topology, even at very small loss rates (which was not the case in previous tomography techniques).},
type={4},
author = {Fragouli, C. and Markopoulou, Athina and Diggavi, Suhas N.},
journal = {Allerton},
tags = {network_coding},
title = {Topology inference using network coding},
year = {2006}
}
Downloads: 0
{"_id":"seuL3uYEtChMPhnby","bibbaseid":"fragouli-markopoulou-diggavi-topologyinferenceusingnetworkcoding-2006","authorIDs":["BovhRrwbYouQ7xD9S"],"author_short":["Fragouli, C.","Markopoulou, A.","Diggavi, S. N."],"bibdata":{"bibtype":"article","type":"4","abstract":"The network coding paradigm is based on the idea that independent information flows can be linearly combined throughout the network to give benefits in terms of throughput, complexity etc. In this paper, we explore the application of the network coding paradigm to topology inference. Our goal is to infer the topology of a network using multiple sources and observations at the edges of the network. In particular, we consider networks where multiple sources send probes and intermediate nodes locally combine probe packets (perform XOR-operations in incoming links). In previous works (e.g., Ratnasamy & McCanne '99; Duffield et al '02), the correlation between the observed packet loss patterns is used to infer the underlying topology. In contrast, our main idea behind using network coding is to introduce correlations among multiple probe packets in a topology dependent manner and also develop algorithms that take advantage of these correlations to infer the network topology from end-host observations. Preliminary numerical results illustrate the performance benefits of this approach. In particular, in the absence of packet loss, we can deterministically infer the topology, with very few probes; in the presence of packet loss, we can rapidly infer topology, even at very small loss rates (which was not the case in previous tomography techniques).","author":[{"propositions":[],"lastnames":["Fragouli"],"firstnames":["C."],"suffixes":[]},{"propositions":[],"lastnames":["Markopoulou"],"firstnames":["Athina"],"suffixes":[]},{"propositions":[],"lastnames":["Diggavi"],"firstnames":["Suhas","N."],"suffixes":[]}],"journal":"Allerton","tags":"network_coding","title":"Topology inference using network coding","year":"2006","bibtex":"@article{fragouli_topology_2006,\n abstract = {The network coding paradigm is based on the idea that independent information flows can be linearly combined throughout the network to give benefits in terms of throughput, complexity etc. In this paper, we explore the application of the network coding paradigm to topology inference. Our goal is to infer the topology of a network using multiple sources and observations at the edges of the network. In particular, we consider networks where multiple sources send probes and intermediate nodes locally combine probe packets (perform XOR-operations in incoming links). In previous works (e.g., Ratnasamy \\& McCanne '99; Duffield et al '02), the correlation between the observed packet loss patterns is used to infer the underlying topology. In contrast, our main idea behind using network coding is to introduce correlations among multiple probe packets in a topology dependent manner and also develop algorithms that take advantage of these correlations to infer the network topology from end-host observations. Preliminary numerical results illustrate the performance benefits of this approach. In particular, in the absence of packet loss, we can deterministically infer the topology, with very few probes; in the presence of packet loss, we can rapidly infer topology, even at very small loss rates (which was not the case in previous tomography techniques).},\n type={4},\n author = {Fragouli, C. and Markopoulou, Athina and Diggavi, Suhas N.},\n journal = {Allerton},\n tags = {network_coding},\n title = {Topology inference using network coding},\n year = {2006}\n}\n\n","author_short":["Fragouli, C.","Markopoulou, A.","Diggavi, S. N."],"key":"fragouli_topology_2006","id":"fragouli_topology_2006","bibbaseid":"fragouli-markopoulou-diggavi-topologyinferenceusingnetworkcoding-2006","role":"author","urls":{},"metadata":{"authorlinks":{"fragouli, c":"https://bibbase.org/show?bib=https%3A%2F%2Fbibbase.org%2Fnetwork%2Ffiles%2F52xaJNXvSgauGDmZR&msg=embed&noBootstrap=1"}},"downloads":0},"bibtype":"article","biburl":"https://s3-us-west-2.amazonaws.com/us-west-2.files.campus.edublogs.org/research.seas.ucla.edu/dist/3/23/files/2023/10/arni_db.bib","creationDate":"2020-11-13T02:21:59.549Z","downloads":0,"keywords":[],"search_terms":["topology","inference","using","network","coding","fragouli","markopoulou","diggavi"],"title":"Topology inference using network coding","year":2006,"dataSources":["ZyBHKCcCyS7Qk9n3w","2BHqTGHtDg7BjRAJQ","XpqzCLvCgsYBqbTpK","QNNZyNQzfeETJyTbL","Z6bBhKezwKd3pPWRc"]}