DOC PREVIEW
UCLA COMSCI 218 - The Impact of Routing Policy on Internet Paths

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

The Impact of Routing Policy on Internet PathsHongsuda Tangmunarunkitt, Ramesh Govindant, Scott Shenker*, Deborah Estrin~Abstract— The impact of routing poticy on Internet paths is poorlyunderstood. In theory, poticy can injate shortest-router-hop paths. Toour knowledge, the extent of this inflation has not been previously ex-amined. Using a simplified model of routing policy in the Internet, weobtain approximate indications of the impact of policy routing on In-ternet paths. Our findings suggest that routing policy does impact thelength of Internet paths significantly. For instance, in our model ofrouting poticy, some 20% of Internet paths are inflated by more thanfive router-level hops.Keywords-Routing, Routing Policy, Policy Routing, Internet PathsI. INTRODUCTIONThe earliest internet routing protocols attempted to con-struct lowest delay paths to destinations [1]. Thereafter,based on operational experience with the stability of delay-sensitive routing [2], deployed routing protocols evolved toessentially support global shortest hop-count routing [3].Today’s Internet contains several administrative domains(or Autonomous Systems, ASS). Within a domain, routinguses hop-count as a metric, but because intra-domain rout-ing protocols support hierarchies, the resulting paths are notnecessarily shortest in terms of hops. Routing between do-mains is determined by policy. Each autonomous system(AS) can, based on configured policy, independently selectrouting information from its neighboring ASS, and selec-tively propagate this information. These policies are not ex-pressed in terms of hop-distance to destinations. Depend-ing on how these policies are constructed, then, the resultingpolicy-based paths to destinations may incur more router-level hops than shortest-router-hop path routing.In this paper, we ask the question: By how much does thishierarchical (inter/intra domain) form of routing affect Inter-net paths? This question was motivated by recent work [4]that observed that, for a significant fraction of Internet paths,there existed an intermediate node such that the compositepath through the intermediate exhibited better performance(delay, throughput). In other words, routing in the Inter-net does not result in delay- or throughput-optimal paths.Perhaps this anomaly can be rectified by changing the In-t H. Tangmunarrmkit and R. Govindarr are with USC/Information Sci-ences Institute, 4676 Admiralty Way, Suite 1001, Marina del Rey, CA90202. E-mail: { hongsuda,govindan} @isi.edu~ S. Shenker is with ACIRI, 1947 Center St., Suite 600, Berkeley, CA94704. E-mail: sherrker(@icsi.berkeley.edu$ D, Estrin is with UCLA aud Information s~ien~es Institute, E-mail:[email protected] work was supported by the Defense Advanced Research ProjectsAgency under grant DABT63-98- 1-0007. Any opinions, findings, and con-clusions or recommendations expressed in this material rwe those of theauthors and do not necesstily reflect the views of the Defense AdvancedResearch Projects Agency.ternet’s routing infrastructure to be delay or load sensitive.Before we do this, however, it would be appropriate to un-derstand how much of these observations can be explainedby the fact that routing hierarchy and policy can result inlonger hop paths. Our paper takes the first step towards thisgoal. Understanding this question can also be important forunderstanding the overall efficiency of the Internet’s routinginfrastructure. Finally, an answer to this question can alsoinform protocol evaluation studies which typically assumeshortest-router-hop path (henceforth, shortest path) routing.To understand how policy routing affects Internet paths,we use a simplified model of inter-AS routing policy thatwe call shortest AS path (Section II). Even though, in the-ory, routing policy can be completely arbitrary, many—butnot all-existing routing policies are based on shortest ASpaths. To infer the router-level path corresponding to thispolicy, we first begin with a router-level map of the Internet.On this map, we assign routers to ASS and obtain an AS over-lay on top of our router-level map. This construction enablesus to compare the router-level policy path between any twonodes with the shortest path on the map. Each of the stepsin our construction represents a simplification of reality. Assuch, then, our results are only approximate indications ofthe impact of policy on Internet paths. However, at eachstage, we carefully validate our construction using a collec-tion of actual traceroutes that represent real paths generatedby policy-based routing. This gives us some confidence thatour conclusions are meaningful.We find several surprising results (Section III). On av-erage, about 20’%0of Internet paths are inflated by 50% ormore. We also find that about half of the source-destinationpairs benefit from a detour. For these pairs, there exists anintermediate node—a detour—such that the overall policypath length through this intermediate node is less than thepolicy path between source and destination.To our knowledge, no related work has addressed the im-pact of routing policy on Internet paths. Our work, however,complements many pieces of recent work aimed at under-standing the structure of the Internet, and the properties ofits paths.. Several efforts have focused on discovering router leveltopologies of the Internet [5], [6], [7]. Such mapping effortsare the crucial first step to help us understand the impact ofrouting policy.. Other work has empirically studied the availability char-acteristics of paths [8], the loss and packet delivery perfor-mance of paths [9], and the existence of alternate paths withlower delay or higher throughput [4]. By considering hop-0-7803-7018-8/01/$10.00 (C) 2001 IEEE IEEE INFOCOM 2001distance between network nodes, our work examines the po-tential inefficiencies resulting from policy routing.. Finally, more recent work has looked at macroscopicproperties of the inter-AS topology [10], [11]. By relatingthe AS structure to the underlying router-level map, our ASoverlay may be able to explain some of the observed macro-scopic properties of the inter-AS topology in terms of theunderlying physical structure.To place our work in context, we point out two importantcaveats. First, it is well known that hierarchical routing canresult in non-optimal paths [12]. Our paper quantifies theextent to which hierarchical routing in the Internet, togetherwith routing policy, affects paths. Second, the


View Full Document

UCLA COMSCI 218 - The Impact of Routing Policy on Internet Paths

Documents in this Course
GSM

GSM

59 pages

Chord

Chord

30 pages

10_2

10_2

9 pages

13_4

13_4

10 pages

RAP

RAP

17 pages

46_4

46_4

9 pages

32_4

32_4

10 pages

umts

umts

39 pages

AdHoc-MAC

AdHoc-MAC

29 pages

rma

rma

8 pages

Lecture

Lecture

29 pages

Load more
Download The Impact of Routing Policy on Internet Paths
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 The Impact of Routing Policy on Internet Paths 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 The Impact of Routing Policy on Internet Paths 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?