Private:pCDN:Peer Matching

Important Dates

• ACM MM: April 17, 2009
• ACM MM (short): May 8, 2009

Previous (2008) Simulation

Experimental Setup

• First, we get info of all the ASes in the world from Team CYRMU's IP to ASNum Mapping Project using netcat. Using this project, e get all ASes' numbers and their names along with the country they belong to. We filter to derive only CA ASes.
  • http://www.team-cymru.org/?sec=8&opt=26
• CAIDA provides dataset on inter-AS relationships among all ASes. We filter to derive inter-AS relationships within Canada using only CA ASes generated from step 1. This accounts for 375 ASes, 643 links (53 p2p, 5 s2s, 585 c2p).
  • http://as-rank.caida.org/data/2008/as-rel.20080414.a0.01000.txt
• Using these links and ASes, we generate a shortest policy path matrix which contains the shortest paths between any two ASes using the algorithm discussed in [Mao et al].
  • http://www.eecs.umich.edu/~zmao/Papers/routescope.pdf
  • To test whether the distances computed are correct, we verified with Rogers BGP site and Teleglobe
    • https://supernoc.rogerstelecom.net/ops/ and
    • http://lg.as6453.net/bin/lg.cgi
• AT & T provides IP Range and AS number mapping. We use this dataset to extract only Canadian IP Ranges and corresponding ASes. We generate 84000 number of IPs belonging to these ASes; 10 each from every IP range – AS mapping.
  • http://www.research.att.com/~jiawang/as_traceroute/
• Using IP-Geo database, we identify the latitude and longitude for each of these peers.
  • Maxmind IP-Geo database
• We test 4 algorithms - AS Order, Geo-location, Random, Network - on a varied size of set of peers {100, 300, 500, 1000, 3000, 5000, 10000, 15000, 20000} randomly picked from 84000 peers generated in step 4. We run all 3 algorithms on the same set of peers and note insertion, lookup, deletion times as well as AS Hops. We repeat this experiment 5 times.
  • For testing of N peers, we take an array of 2N peers. First N peers are used for inserting and deleting. The rest N peers are used for searching. That is, we first insert N peers (from 1 to N), then lookup for next N peers (N+1 to 2N) and then delete N peers (from 1 to N). We note each individual time.
• The simulation has been implemented in Java and the experiments have been performed on a 2GHz and 2GB RAM machine.

ISP Friendly Algorithm

Steps:

• We populate IP to AS Map (IPASMap) using the IP Range and AS mapping present in AT & T dataset. This map can be used for searching an AS for a given IP.

• We then load the pre-computed shortest policy path matrix (ShortestPathMatrix) which contains the shortest distance between every 2 individual ASes.

• The data structure we use is a HashMap (ASMap) which contains ASNum as the key and the peerlist (the list of peers in that AS) corresponding to that AS.

Ideas

• Verification of AS Shortest Paths

• Experimental Setup
  • # Peers: {100, 300, 500, 1000, 3000, 5000, 8000}
  • # Senders: {2, 5, 10, 15, 20}
  • # Sessions: 1000
  • Algos: Random, Network, Geo, AS_Order(ISP-Friendly)
  • Metrics: Min, Avg, Max, Output
  • Output: Hops (Aggregate, P2P, C2P)

• Search Efficiency:
  • If multiple shortest paths are existing, choose the least "cost" (s2s=0, p2p=1, c2p=2)

• Check practicality
  • What kind of data we need initially and periodically
  • How often we need them
  • We implement the algorithm to determine AS relationships

• Large graphs
  • Can we get the US & CA graph?
  • Can we optimize this matrix.

• Usage of ISP + Network / Geolocation Algorithms
  • We reduce the number of IP hops

• Diameter of the Canada's AS graph: 13 AS Hops

References and Links

• IP to ASNum Mapping project from Team CYRMU
  • http://www.team-cymru.org/?sec=8&opt=26
• CAIDA's Inter-AS relationships
  • http://as-rank.caida.org/data/2008/as-rel.20080414.a0.01000.txt
• On AS-level Path Inference
  • http://www.eecs.umich.edu/~zmao/Papers/routescope.pdf
• AT & T IP-Range and ASNum mapping
  • a. http://www.research.att.com/~jiawang/as_traceroute/