Title :
Resource Discovery in Networks under Bandwidth Limitations
Author :
Konwar, Kishori M. ; Shvartsman, Alex A.
Author_Institution :
Dept. of Comput. Sci. & Eng., Connecticut Univ., Storrs, CT
Abstract :
The resource discovery problem, where cooperating machines need to find one another in a network, was introduced by Harchol-Balter, Leighton, and Lewin (1999) in the context of Akamai Technologies with the goal of building an Internet-wide content-distribution system. In the solutions for the synchronous setting proposed so far in the papers by Harchol-Bartel et al. (1999), Kutten et al. (2001) and Law and Siu (2000), there is a possibility that during some time step many machines may contact a single machine, and this is not a realistic assumption. This work assumes a synchronous model, however at each step a machine can send and receive only a constant number of messages. It is shown that the conjectured poly-logarithmic upper bound (Harchol-Bartel et al., 1999) for such a setting is not possible. This is done by proving a lower bound on time of Omega(n), where n is the number of participating nodes. For this model a randomized algorithm is presented that solves the resource discovery problem in O(n log2 n) time, i.e., within a poly-logarithmic factor of the corresponding lower bound. The algorithm has a O(n2 log2 n) message complexity and O(n3 log3 n) communication complexity. Simulation results for the algorithm illustrate the lower and upper bounds, and lead to interesting observations
Keywords :
bandwidth allocation; communication complexity; distributed processing; randomised algorithms; bandwidth limitations; communication complexity; message complexity; network resource discovery; randomized algorithm; synchronous model; Bandwidth; Broadcasting; Complexity theory; Computer science; Distributed computing; File systems; IP networks; Internet; Peer to peer computing; Upper bound;
Conference_Titel :
Parallel and Distributed Computing, 2006. ISPDC '06. The Fifth International Symposium on
Conference_Location :
Timisoara
Print_ISBN :
0-7695-2638-1
DOI :
10.1109/ISPDC.2006.40