Flow generation for IP/ATM label-switched routing over random networks

We address the problem of generating ATM labels which facilitates IP packet flow through the network. We define the virtual flow topology and provide a stochastic algorithm GFLOW, that generates labels for virtual connections using periodic broadcasts providing simple and efficient robustness and oblivious execution. For a random network with N nodes of average degree d̄ and dimeter Θ(k), we demonstrate how our algorithm can be used to generate a mean l=1+(k-1)d̄ labels at each node to provide a probability Θ(1/N) that any pair of nodes will have a virtual connection between them. We show that with probability roughly 1/2 +1/2N any node may route a message along a virtual connection which terminates within an ε-neighborhood of the destination, where ε=Θ(log_d̄ (N/k)), with l as stipulated. Of course the number of labels generated at each node is variable and directly relates to the cost in such a way that a network administrator can trade label space for increased performance. We provide simulation results using Matlab mathematical language interpreter that supports our analysis.