Private:pCDN:Peer Matching

Proposed Algorithm Simulation

Setup: 1. 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, we get all ASes' numbers and their names along with the country they belong to. We filter to derive only CA ASes. a. http://www.team-cymru.org/?sec=8&opt=26 2. 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). a. http://as-rank.caida.org/data/2008/as-rel.20080414.a0.01000.txt 3. 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]. a. http://www.eecs.umich.edu/~zmao/Papers/routescope.pdf b. To test whether the distances computed are correct, we verified with Rogers BGP site and Teleglobe i. https://supernoc.rogerstelecom.net/ops/ and ii. http://lg.as6453.net/bin/lg.cgi 4. 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. a. http://www.research.att.com/~jiawang/as_traceroute/ 5. Using IP-Geo database, we identify the latitude and longitude for each of these peers. a. Maxmind IP-Geo database 6. We test 3 algorithms - AS Order, Geo-location, Random - 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. a. 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. 7. The simulation has been implemented in Java and the experiments have been performed on a 2GHz and 2GB RAM machine.

ISP Friendly Algorithm Steps: 1. 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.

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

3. 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.

i. Insert(Peer peer){ //obtain the AS this peer belongs to ASNum = IPASMap.getASNum(peer.IP);

// check if this AS already exists If (ASNum does not exist in ASMap)

 	    ASMap.insert(ASNum);

// now add this peer to that AS ASMap[ASNum].peerlist.add(peer);

}

ii. Delete(Peer peer){ //obtain the AS this peer belongs to ASNum = IPASMap.getASNum(peer.IP);

//remove the peer from that AS ASMap[ASNum].peerlist.remove(peer);

}

iii. Lookup(Peer peer){ declare RetPeerlist; declare retPeerCount;

//obtain the AS this peer belongs to ASNum = IPASMap.getASNum(peer.IP);

// Get a list of all ASes that are in the data structure ASlist = ASMap.getASList();

// and sort these ASes based on the distance from ASNum // to each of the ASes in ASlist, using the matrix SortedASlist = ASlist.sort(ASNum , ShortestPathMatrix[][]);

count = 0;

// Noting the number of AS hops ashops = 0;

for(i=0;i<SortedASlist.size;i++){

	  j=0;
	  while(count<retPeerCount && j<SortedASlist[i].peerlist.size){
		Peer tmp =  SortedASlist[i].peerlist[j++];
     	RetPeerlist.add(tmp);

       // get the AS this peer belongs to

tmpASNum = SortedASlist[i];

       ashops += ShortestPathMatrix[ASNum][tmpASNum];

count++;

 }
       if(count>=retPeerCount)
             break;

} return RetPeerlist; }

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 graph

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/