FRNOG Tools - RANX
Internet routing with BGP
The Internet is:
- More than 20000 interconnected Autonomous Systems (AS). End-User ISPs (Internet Service Providers) or Hosting companies are connected to the rest of the Internet with their own AS through Transit providers or Peering. Transit Providers run an AS in order to provide transit to other ASs.
- A partition of the public IP address space into ranges (prefixes): companies, DSL users, universities, hosting services, etc
Internet routing is handled by the Border Gateway Protocol:
BGP routers propagate reachability of prefixes and maintain a routing table for more than 200000 prefixes that constitute today's Internet. This routing table allows each BGP enabled network to know the route toward any public IP address.
End-to-end Internet routes
Internet paths between hosts rely on:
- BGP routes selected and propagated by BGP routers
- Router paths inside an AS are matter of the ASs internal routing
BGP route selection and propagation rely on:
- Network topology: AS-level and router-level topologies
- Routing Policies of ASs: prefix announcements, route filters, route preferences...
Business agreements are negotiated for AS links
Customer/Provider: C2P/P2C
- Client pays provider for incoming and outgoing traffic
- Client routers send to provider routers own & clients BGP routes
- Provider routers send to client routers all their BGP routes
Peering ("Sender Keep All"): PEER
- In a peering session, routers send ONLY their own & their clients BGP routes
- No guaranty (no Service Level Agreement (SLA))
Others :
- Paid peering (which tends to be more and more common)
- Regional / national transit & peering
- IP prefix-based
- Sibling SIB (same administration)
Decision support for AS interconnections
The Reachability of an AS: BGP paths to prefixes
- Depends on many 'unknown' factors
- Business agreements, Traffic Engineering...
A given reachability implies an underlying quality for IP packet forwarding
- business agreements and neighbors AS shape possible AS-level paths from a given AS
Accurate negotiation of new inter-AS links:
- Needs knowledge about reachable prefixes and routes provided
° Which prefixes? Are they cheaper for example?
° Which hosts belonging to prefixes? Internet clients, provided contents
° What kind of BGP paths toward prefixes?
Prefix and paths are unknown, real impact of a new link also!
AS ranking: motivations
AS ranking: a way to compare transit ASs
- Hierarchical position (economic)
- Topological position (connectivity)
Reachability of an AS is strongly correlated with its position in the Internet Hierarchy
- Customer-to-provider & provider-to-customer agreements create a hierarchy
Mining BGP tomography[1] for Transit
We use BGP feeds from RouteViews : more than 80 full BGP routing tables
How to mind BGP tomography for AS ranking computation?
- Goal is to estimate amount of customer prefixes provided by each AS
° without relying on a model of business agreements...
° without bias introduced by measurement points...
° With freedom on the way to give importance to prefixes
- Keep in mind bias in estimation of amount of prefix observed
° For ASs (limited view of measurement points)
° On AS links (measurement point location)
We search for the amount of IP space "behind" an AS
- End-to-end reachability is maintained:
° Transit providers are responsible for propagation of reachability announces
° Transit providers are observed on paths to customer prefixes
IP Space transited by an AS as seen in a path at an observation point
- For a path (X-Y-Z-T) to prefix p, we record:
° transit (X,Y,Z) of prefix p for Y
° transit (Y,Z,T) of prefix p for Z
Given a set of AS paths, we can compute:
- Set of prefixes transited by each AS X
° Prefixes on sub AS paths of length 3 (*,X,*)
Rank of an AS is the percentage of IP space transited
- This rank can be a weighted sum of each prefix importance
We compute a rank for each AS, from each measurement AS
- We use only measurement AS with full routing tables
The RANX AS ranking concept is based on the average IP space transited by an AS.
Advantages of this ranking method
Intuitive
- Any AS far from a measurement AS is seen to transit its customer prefixes
- Any AS close to a measurement AS has an over-estimated number of prefixes transited
Narrowed bias due to placement of measurement AS
- If some ASs are providers of one or several measurement AS, it will not change the results much
Prefix granularity limits errors due to pure graph-based estimation of connectivity
- example: transit of some prefixes between two Tier 1 AS is not misunderstood!
Compute the average IP space transited by an AS as seen from many measurement
- The sampling of many measurement AS becomes representative for the quantity measured
RANX
We introduce a new AS ranking algorithm
- Use BGP tomography with routeviews public BGP feeds
- It records foreign transit of prefixes by AS
- The value computed can be directly interpreted
Advantages compared to other methods
- It is not a black box [2]
- Take care of measurement bias
° Over-estimated reachability of some ASs is averaged
- Take advantage of multiple routing tables used
° The more tables as input, the more precise is result
- We can restrict the set of prefixes for which ranking is computed so we can generate a ranking for geo-political region
Geo-political Regions
Africa countains the following TLDs: AC BI KM DJ ER ET KE MG MW MU YT MZ RE RW SC SO UG TZ ZM ZW AO CM CF TD CG CD GQ GA ST DZ LY MA SD TN EH BW LS NA ZA SZ BJ BF CV CI GM GH GN GW LR ML MR NE NG SH SN SL TG
Antarctic countains the following TLDs: AQ BV GS HM TF
Asia countains the following TLDs: AP IO TW TP KZ KG TJ TM UZ CN HK MO KP JP MN KR AF BD BT IN MV NP PK LK BN KH ID LA MY MM PH SG TH TL VN AM AZ GE TR
Central America countains the following TLDs: UM AI AG AW BS BB VG KY CU DM DO GD GP HT JM MQ MS AN PR BL KN LC MF VC TT TC VI BZ CR SV GT HN MX NI PA
Europe countains the following TLDs: CS EU FX UK YU CY BY BG CZ HU MD PL RO RU SK UA AX DK EE FO FI GG IS IE IM JE LV LT NO SJ SE GB AL AD BA HR GI GR VA IT MT ME PT SM RS SI ES MK AT BE FR DE LI LU MC NL CH
Middle-East countains the following TLDs: EG IR BH IQ IL JO KW LB PS OM QA SA SY AE YE
North America countains the following TLDs: BM CA GL PM US
Oceania countains the following TLDs: CC CX AU NZ NF FJ NC PG SB VU GU KI MH FM NR MP PW AS CK PF NU PN WS TK TO TV WF
South America countains the following TLDs: AR BO BR CL CO EC FK GF GY PY PE SR UY VE
Sponsors
Hosting sponsored by OVH
Research sponsor is France Telecom R&D
Research data sponsor is Routeviews
Research geolocation sponsor is MaxMind
Contact Us
You can contact us at : philippe -at- frnog.org
[1] See http://en.wikipedia.org/wiki/Tomography
[2] See http://www.nanog.org/mtg-0706/Presentations/MickaelMeulle-Revisiting.pdf for the original presentation of the algorithm by Mickael.
Mickael MEULLE - France Telecom R&D
Web version by Philippe Bourcier - FRNOG
