Private:pCDN:Peer Matching
From NMSL
Revision as of 08:53, 29 April 2008 by Nitin.chiluka (talk | contribs)
Proposed Algorithm 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, we get all ASes' numbers and their names along with the country they belong to. We filter to derive only CA ASes.
- 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).
- 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
- 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.
- 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
Important Dates
- Conferences
- May 2: SIGCOMM
- Aug 9: InfoComm
References and Links
- IP to ASNum Mapping project from Team CYRMU
- CAIDA's Inter-AS relationships
- On AS-level Path Inference
- AT & T IP-Range and ASNum mapping
