Class FindCentroid

java.lang.Object
  |
  +--FindCentroid

public class FindCentroid

extends java.lang.Object

FindCentroid.java Jim Gast, jgast@cs.wisc.edu FindCentroid finds the Internet AS numbers that can reach 90% of the AS numbers in use in 3 hops or less. It reads the BGP Table to discover which ASNs connect to which other ASNs. (This is not entirely an accurate way to tell if two ASNs are connected, but it is easy and public BGP tables are easy to get from Oregon Route-Views.) FindCentroid is the main class which gets input from BGP routing tables and starts everything out. USAGE: java FindCentroid bgpTableFile hopLimit densityPct

• bgpTableFile, (default BGPTable.txt) from "show ip bgp" in Cisco format
• hopLimit. (default 3), number of hops out to consider
• densityPct, (default 80) percentage of the Internet that the node sees

Field Summary

static ASN[]	asnList
static int[]	asnSeen
static java.util.TreeMap	hash

Constructor Summary

FindCentroid()

Method Summary

static int	calcDensityWithinNHops(int base, int hopLimit) prints the number of ASes in the cloud within hopLimit hops of AS base.
static int	countASNumbersSeen()
static void	incrCount(int from, int to)
static void	main(java.lang.String[] args) main method reads BGP table and counts distance to BB from every AS
static void	readRoutingFile(BGPReader bReader) readRoutingFile reads lines of a BGP routing file until EOF.
static void	readRoutingLine(java.lang.String str) readRoutingLine finds all pairs of ASNumbers whether on best paths or worst.
static void	showDensitiesWithinNHops(int hopLimit, int densityThreshold)
static void	sortNeighbors()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

hash

public static java.util.TreeMap hash

asnSeen

public static int[] asnSeen

asnList

public static ASN[] asnList

Constructor Detail

FindCentroid

public FindCentroid()

Method Detail

main

public static void main(java.lang.String[] args)
                 throws java.io.IOException

main method reads BGP table and counts distance to BB from every AS

java.io.IOException

readRoutingFile

public static void readRoutingFile(BGPReader bReader)

readRoutingFile reads lines of a BGP routing file until EOF. The routing file is expected to have: # Lines that start with "#" are comments * Routings start with "*" *> Best routes start with "*>" The only tricky part is that the destination IP address is not repeated if it is the same as the prior line. Example: 24.0.101.0/24 193.0.0.56 0 3333 1103 6453 1239 6172 ? 134.55.24.6 0 293 1800 1239 6172 ? > 144.228.240.93 35 0 1239 6172 ? The example shows 3 routes to 24.0.101.0/24. The third is the "best route".

readRoutingLine

public static void readRoutingLine(java.lang.String str)

readRoutingLine finds all pairs of ASNumbers whether on best paths or worst. This routine parses the line and prints out one line for each adjacent pair of ASNumbers. By implication, there is a route that directly connects those Autonomous Systems in a single hop.

showDensitiesWithinNHops

public static void showDensitiesWithinNHops(int hopLimit,
                                            int densityThreshold)

calcDensityWithinNHops

public static int calcDensityWithinNHops(int base,
                                         int hopLimit)

prints the number of ASes in the cloud within hopLimit hops of AS base.

sortNeighbors

public static void sortNeighbors()

incrCount

public static void incrCount(int from,
                             int to)

countASNumbersSeen

public static int countASNumbersSeen()