Overlay Network Routing Based on Shadow Price

Overlay network is constructed at application layer to provide higher level services. In the past few years, overlay network has received much attention. As different choices of overlay topologies and overlay routing would have different results on the performance of the network, how to design an efficient overlay topology for overlay routing is considered necessary and important. Traditional approaches of overlay topology or overlay routing are designed based on static state metrics, such as the number of hops, or link cost, the side effect of which caused the routing resulting the traffic bottleneck, finally declining the performance of network routing. There existed many candidate routing schemes to provide overlay networking. Recently, with the assist of network providers, some users construct a minimum spanning tree for overlay routing. Minimum spanning tree is efficient, but more efficient topology will exist. In this paper, aiming at distributing network traffics, the concept of shadow price is introduced to design the topology. Shadow price considers the future condition of network based on current network status, and is useful to design more efficient overlay networks.