A new database allocation scheme for a class of networks
Arif Ghafoor · 1985
With the recent trend towards large computer communication networks, the concept of a distributed database is becoming more attractive. This decentralized environment leads to a very crucial question, that is how to find the optimal sets of nodes in the network at which a reasonable number of duplicate copies of the database can be placed. Optimal solutions for the selections of optimal sites as generally conceived are NP hard. Almost all the previous models developed for this problem are either integer or mixed integer linear programs. This study reports a unique approach towards the solution of this problem. The parameter considered for the optimization is query overhead traffic. This is a rather important parameter, as almost 80% to 90% of the traffic generated by the users of the database is just query traffic. The networks which are studied are those which have regular topology and whose diameter is one less than their degree. These graphs are constructed by using constant weight binary codes. A relationship between the Hamming distance and the physical distance in the network is developed and the database allocation problem is modeled in coding theory. Using these models, a set of algorithms is proposed, which avoid any major combinatorial explosion such as generally occurs in other approaches. As far as complexity is concerned, these algorithms are trivial. The results obtained for this class of networks, are extended to another large class of networks. Furthermore these results are used to define bounds on the query traffic for general networks.