Acyclic Type-of-Relationship Problems on the Internet

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

KOSUB, Sven, Moritz G. MAASS, Hanjo TÄUBIG, 2006. Acyclic Type-of-Relationship Problems on the Internet. Workshop on Combinatorial and Algorithmic Aspects of Networking. Chester, UK, Jul 2, 2006. In: ERLEBACH, Thomas, ed.. Combinatorial and Algorithmic Aspects of Networking : Third Workshop, CAAN 2006, Revised Papers. Berlin:Springer, pp. 98-111. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-48822-4. Available under: doi: 10.1007/11922377_9

@inproceedings{Kosub2006Acycl-44983, title={Acyclic Type-of-Relationship Problems on the Internet}, year={2006}, doi={10.1007/11922377_9}, number={4235}, isbn={978-3-540-48822-4}, issn={0302-9743}, address={Berlin}, publisher={Springer}, series={Lecture Notes in Computer Science}, booktitle={Combinatorial and Algorithmic Aspects of Networking : Third Workshop, CAAN 2006, Revised Papers}, pages={98--111}, editor={Erlebach, Thomas}, author={Kosub, Sven and Maaß, Moritz G. and Täubig, Hanjo} }

<rdf:RDF xmlns:dcterms="" xmlns:dc="" xmlns:rdf="" xmlns:bibo="" xmlns:dspace="" xmlns:foaf="" xmlns:void="" xmlns:xsd="" > <rdf:Description rdf:about=""> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:language>eng</dc:language> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dspace:isPartOfCollection rdf:resource=""/> <dc:creator>Täubig, Hanjo</dc:creator> <dc:date rdf:datatype="">2019-02-12T11:43:56Z</dc:date> <dcterms:available rdf:datatype="">2019-02-12T11:43:56Z</dcterms:available> <dc:creator>Kosub, Sven</dc:creator> <dcterms:isPartOf rdf:resource=""/> <dcterms:title>Acyclic Type-of-Relationship Problems on the Internet</dcterms:title> <dcterms:issued>2006</dcterms:issued> <dcterms:abstract xml:lang="eng">We contribute to the study of inferring commercial relationships between autonomous systems (AS relationships) from observable BGP routes. We deduce several forbidden patterns of AS relationships that impose a certain type of acyclicity on the AS graph. We investigate algorithms for solving the acyclic all-paths type-of-relationship problem, i.e., given a set of AS paths, find an orientation of the edges according to some types of AS relationships such that the oriented AS graph is acyclic (with respect to the forbidden patterns) and all AS paths are valley-free. As possible AS relationships we include customer-to-provider, peer-to-peer, and sibling-to-sibling. Moreover, we examine a number of problem versions parameterized by sets K and U where K is the set of edge types available for describing explicit pre-knowledge and U is the set of edge types available for completion of partial orientations. A complete complexity classification of all 56 cases (8 type sets for pre-knowledge and 7 type sets for completion) is given. The most relevant practical result is a linear-time algorithm for finding an acyclic and valley-free completion using customer-to-provider relations given any kind of pre-knowledge. Interestingly, if we allow sibling-to-sibling relations for completions then most of the non-trivial inference problems become NP-hard.</dcterms:abstract> <dc:contributor>Kosub, Sven</dc:contributor> <dc:contributor>Maaß, Moritz G.</dc:contributor> <bibo:uri rdf:resource=""/> <dc:creator>Maaß, Moritz G.</dc:creator> <dc:contributor>Täubig, Hanjo</dc:contributor> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


My Account