2002 · 230 citations · 19 references
ComputingComputer ScienceComputer SystemsComputer NetworksInterconnection NetworksTransportInternet RoutingNetwork ProtocolsNetwork TopologyRoutingRouting AlgorithmsRouting ProtocolsConstrained Shortest PathsConstraint-based OptimizationIntradomain RoutingRouting In Weighted GraphsRouting MetricsRouting OptimizationShortest Paths
We describe a novel constraint-based approach to approximate ISP link weights using only end-to-end measurements. Common routing protocols such as OSPF and IS-IS choose least-cost paths using link weights, so inferred weights provide a simple, concise, and useful model of intradomain routing. Our approach extends router-level ISP maps, which include only connectivity, with link weights that are consistent with routing. Our inferred weights agree well with observed routing: while our inferred weights fully characterize the set of shortest paths between 84--99% of the router-pairs, alternative models based on hop count and latency do so for only 47--81% of the pairs.
19
Measuring ISP topologies with rocketfuel
Neil Spring, Ratul Mahajan, David Wetherall · 2002 · 1.3K citations
Internet traffic engineering by optimizing OSPF weights
Bernard Fortz, Mikkel Thorup · 2002 · 1.1K citations
Heuristics for Internet map discovery
Ramesh Govindan, Hongsuda Tangmunarunkit · 2002 · 699 citations