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