Patent ID: 7647215

Claim:
A system that creates directed scale-free random graphs of networks comprising: a memory; one or more processors operatively coupled to the memory and disposed within one or more devices; a generating module that generates a directed scale-free random graph that includes a plurality of vertices and directed edges that are incrementally created in accordance with three probabilities; a sample directed network topology generated by the generating module; wherein the generating module independently generates two random numbers λ(v) and μ(v) from specified distributions D in and D out for a new vertex v of the graph and utilizes the random numbers to update vertices of the graph by: choosing an existing vertex w according to λ(w)(d in +∂ in ) such that Pr(w=w j ) αλ(w j )(d in (w j )+∂ in ), wherein d in is an in-degree shift and ∂ in is a non-negative parameter added to the in-degree shift of a vertex, while α is a probability, w j is a vertical column j of vertex w and λ(w) and λ(w j ) are random numbers; choosing an existing vertex v according to μ(w)(d out +∂ out ) and a second existing vertex w according to λ(w)(d in +∂ in ), so that Pr(v =v i , w=w j ) α μ(v i )λ(w j )(d out (v i +∂ out )(d in (w j )+∂ in ), wherein d out is an out-degree shift and ∂ out is a non-negative parameter added to the out-degree shift of a vertex, while α is the probability and w j is a vertical column j of vertex w and v i is a horizontal row of i of vertex v; and selecting an existing vertex w according to μ(w)(d out +∂ out ) such that Pr(w=w i ) α (w i )(d out (w i )+∂ out ); and a testing component that uses the sample directed network topology generated by the generating module to test directed internet routing protocols.