Deterministic load balancing in computer networks

Author

Deng, Xiaotie ; Liu, Hai-Ning ; Xiao, Bing

Author_Institution

Sch. of Comput. Sci., Simon Fraser Univ., Burnaby, BC, Canada

fYear

1990

fDate

9-13 Dec 1990

Firstpage

50

Lastpage

57

Abstract

The paper presents theoretical analysis of the deterministic complexity of the load balancing problem (LBP). Because of difficulty of the general problem, research in the area mostly restricts itself to probabilistic or approximation algorithms, or to the average behavior of a network. The paper provides deterministic analysis of the problem for general networks. It focuses on the worst-case complexity analysis of the problem. It shows certain cases of the LBP to be NP-complete. The paper also discusses situations closely related to computer networks, where there is a global view of load distribution in the network; it provides a polynomial algorithm for solving the load balancing problem in this network

Keywords

computational complexity; computer networks; NP-complete; approximation algorithms; average behavior; computer networks; deterministic analysis; deterministic complexity; load balancing problem; load distribution; polynomial algorithm; probabilistic algorithms; worst-case complexity analysis; Centralized control; Computer networks; Computer science; Decision making; Distributed computing; Distributed databases; Intelligent networks; Load management; Network topology; Polynomials;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Processing, 1990. Proceedings of the Second IEEE Symposium on

Conference_Location

Dallas, TX

Print_ISBN

0-8186-2087-0

Type

conf

DOI

10.1109/SPDP.1990.143506

Filename

143506