Unformatted text preview:

1Internet MeasurementsArvind KrishnamurthyFall 2004Motivation Types of measurements Understand the topology of the Internet Measure performance characteristics Tools: BGP Tables Traceroute measurements Probes for latency, bandwidth and loss-rateEconomics of the InternetISP YISP ZISP XISP PTransit ($)Transit ($$$)Transit ($$)PeeringTransit ($$$)Transit ($)Transit ($$)Transit ($$$)PeeringC1 C2 C3 C4 Transit relationship: Reveal customers to everyone Reveal all known paths to customers ISP Y will advertise paths to C2 and C3Peering RelationshipsISP YISP ZISP XISP PTransit ($)Transit ($$$)Transit ($$)PeeringTransit ($$$)Transit ($)Transit ($$)Transit ($$$)PeeringC1 C2 C3 C4 ISP Y peers with ISP Z Y informs Z of C2 and C3 Z informs Y of C4Peering RelationshipsISP YISP ZISP XISP PTransit ($)Transit ($$$)Transit ($$)PeeringTransit ($$$)Transit ($)Transit ($$)Transit ($$$)PeeringC1 C2 C3 C4 ISP Y peers with ISP X Y informs X of C2 and C3 X informs Y of C1 Y does not tell X of the path to C4 Y needs to have transit relationship with P to route to C4Multi-Exit Discriminator C has a transit relationship with P C needs to send a packet into P’s domain Packet origin: Boston, packet destination: SF It has two choices: transit into P earlier (near Boston) or transit later (near SF) Prefer early transit2Routing Preferences In general, customer > peer > provider Use LOCAL PREF to ensure this Routing through customer and peer could lower latency and lower traffic costs Processing order of path attributes: Select route with highest LOCAL-PREF Select route with shortest AS-PATH For routes learned from same neighbor: Apply multi-exit discriminatorRouting algorithms for the internet Link state or distance vector? Problems with link state: LS database too large – entire Internet Metric used by routers not the same May expose policies to other AS’s Can we use distance-vector algorithms for policy routing?Distance Vector with Path Each routing update carries the entire path Loops are detected as follows: When AS gets route check if AS already in path If yes, reject route If no, add self and (possibly) advertise route further Advantage: Metrics are local - AS chooses path, protocol ensures no loops Hop-by-hop Model BGP advertises to neighbors only those routes that it uses Consistent with the hop-by-hop Internet paradigm e.g., AS1 cannot tell AS2 to route to other AS’s in a manner different than what AS2 has chosen (need source routing for that)Terminology Each POP is a physical location where the ISP houses a collection of routers.  The ISP backboneconnects these POPs, and the routers attached to inter-POP links are called backboneor core routers.  Within every POP, accessrouters provide an intermediate layer between the ISP backbone and routers in neighboring networks.3Points of Presence and BackboneRocketfuel Methodology ISPs release “helpful” information: BGP - which prefixes are served Traceroute - what the paths are DNS - where routers are and what they do Build detailed maps: Backbone POPs Peering linksTraceroutes Publicly available traceroute servers Challenge: To build accurate ISP maps using few measurements Brute Force Method 784 vantage points to 120,000 allocated prefixes in BGP table Queried every 1.5 minutes: 125 days to complete a map. Take all paths and use portions of the paths to determine structure of target ASDirected probing Capitalize on BGP routing information Identify traceroutes which transit the ISP networkGoal: map AS 7Need to consider only those paths that go through AS 71) Probes to dependent prefixes traverse AS 7Dependent Prefixes: 4.5.0.0/162) Probes from insiders to outside in dependent prefixes3) Up/down traces: AS 11 to 1.2.3.0/24Path ReductionsIngress ReductionNext-hop AS ReductionEgress ReductionT1 and T2 enter the ISP at the same point on the way to the same destinationPaths to P1 and P2 leave the ISP at the same pointReduction Effectiveness Brute force : 90-150 million traceroutes required BGP directed probes : 0.2-15 million traceroutes required Executed after path reduction : 8-300 thousand traceroutes required4Location and Role Discovery Where is this router located?use DNS namesS1-bb11-nyc-3-0.sprintlink.net is a Sprint router in New York Cityuse connectivity informationif a router connects only to routers in Seatles, it is in Seattle What role does this router play in the topology?only backbone routers connect to other citiesuse DNS namess1-gw2-sea-3-1.sprintlink.net is a Sprint gateway routerAlias resolution problemAT & T SprintLevel 3Internet MeasurementsNow we have router-level topology in an ISPMore information: link weights? Connectivity is not enough to derive best path Link weights in an ISP is not publicInferring link weights provides  a simple, concise, and useful model of intra-domain routing. Common routing protocols choose least-cost paths using link weightsIt extends router-level ISP maps Includes connectivity Link weights consistent with routing5Problem Formulation Input  Network topology Routing as a set of chosen paths (lowest weight) Output: Assign weights for each link, so that shortest paths match chosen paths Not a unique solution Scaling all weights with same factor Changing the weight of a link within boundsBasic Solution Two key observations Chosen path has less weight than any other path between two nodes If multiple chosen paths exist, they have equal weightBasic solution Chosen paths between A-G  ADG and ABEG Similar constraints for chosen paths between all other node-pairs Linear programming  Shortcomings?Reduce Constraints Chosen Paths:  S-M-N-D, S-A-I, I-B-D Weight Constrains SMND < SAI + IBD SAI < SXI IBD < IYD SMND < SXI + IYD will be redundant All alternative paths from S to D through I, except path SAIBD Actual number of constraints is much lower than n3S DIABM NXYShortcomings In Measurement Data Two shortcomings from using traceroute measurements Some paths might not be shortest path due to transient events (e.g. failures) Not all chosen paths can be observedApproach to resolve the first shortcoming To associate error variables with constraints  Associate with error variables for observed


View Full Document

Yale CPSC 424 - Internet Measurements

Download Internet Measurements
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Internet Measurements and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Internet Measurements 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?