Heterogeneous resource allocation under degree constraints in peer-to-peer networks

Peer-to-peer model is one of the commonly used model for distributed computing. Some of the peers are having demand for certain resources some others may be having additional capacity of resources. Peers may have limitations on the number of concurrent connections (degree). In the present work allocation problem of peers having demand, capacity and degree is considered. The problem is to find an allocation of peers such that the number of peers allocated to a particular peer P should not exceed the degree of P and total demand of allocated peers should not exceed the capacity of P, while maximizing the overall throughput. Two versions namely Offline (when peers are known in advance) and Online (when peers can join and leave the network at any time) versions of the problem are considered. By introducing degree constraints the problem becomes NP-complete. Resource augmentation based three approaches are proposed to solve this problem. The performance (in terms of throughput) and the cost (in terms of disconnections and reconnections) of the proposed approaches is compared through a set of extensive simulations. The observed results are impressive.