"Jane" == Pawlukiewicz Jane <pawlukiewicz_jane@bah.com> writes:
>> Even if we were to model it, the best data we could get for >> the "Internet" would be BGP routing tables. These are also >> subjectve views of the rest of the net. We could take a full >> table, map all the ASN adjacencies, and then pick arbtrary >> ASN's to "fail", then see who is still connected, but we are >> still dealing with connectivity relatve to us and our peers, >> even 5+ AS-hops away. Jane> I want to make sure I understand this. As I understand it, Jane> this would work regarding routing only. It would be a model Jane> that would have a result of ones and zeros, so to speak, Jane> meaning either you're connected or you're not. What this Jane> doesn't take into consideration, I believe, is the effects Jane> of congestion regarding increased traffic due to news Jane> traffic and rerouting that takes place whenever there is a Jane> loss of a site. I believe you are correct. Modelling the connectivity matrix [1] is good as a first approximation. The next thing to do would be to estimate the transition probabilities between ASi and ASj (you could do this by looking at the adjacencies one step out [2], for example. There are other methods of estimating the transition probabilities but most are foiled by a lack of available data. You can get a pretty good adjacency map doing table dumps from all of the route servers, looking glasses, etc.) Once you have the TP matrix, construct a vector of initial conditions to represent likely traffic sources -- i.e. the ASs containing CNN and the BBC, for example -- and look at how the traffic dissipates through an n-step Markov process [3]. This will tell you something about how heavily loaded with traffic certain ASs (the accumulation points) become, at least as a ratio to "normal", but since we have no information about channel capacity available within each AS, it doesn't say much about actual congestion. It will, however, suggest where congestion is likely to occur if links have not been overprovisioned by some ratio. I think ;) The trick is in estimating the transition probabilities. I'm not sure this is a good method. Using adjacencies from one hop out assumes transit to two hops out. Using n hops out implies transit to n+1 hops and the bigger n gets the less accurately it will start representing the real mesh since it starts implicitly assuming symmetric transit everywhere once n is greater than, say, 4 or 5 or whatever the average AS path length is these days. -w [1] C_ij = 1 if i and j connected or i == j, 0 otherwise [2] If A_i is the number of adjacencies for ASi, then set transition probabilities P_ij proportional to (C_ij * A_j) / Sum_k (C_jk * A_k), normalized so that Sum_j P_ij = 1. [3] n-th step transition probabilities are (P_ij)^n -- William Waites <ww@styx.org> +1 416-717-2661 finger ww@styx.org for PGP keys Idiosyntactix Research Laboratories http://www.irl.styx.org -- NetBSD: ça marche!