Date Added: Mar 2011
A foundational issue underlying many overlay network applications ranging from routing to peer-to-peer file sharing is that of the network formation, i.e., folding new arrivals into an existing overlay, and re-wiring to cope with changing network conditions. Previous work has considered the problem from two perspectives: devising practical heuristics for the case of cooperative peers, and performing game theoretic analysis for the case of selfish peers. In the paper, the authors unify the aforementioned thrusts by defining and studying the Selfish Neighbor Selection (SNS) game and its application to overlay routing. At the heart of SNS stands the restriction that peers are allowed up to a certain number of neighbors.