For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Approximation Algorithm for Optimal Combinations of Scopes in OSI Management Operations
Kiyohito YOSHIHARA Hiroki HORIUCHI Keizo SUGIYAMA Sadao OBANA
IEICE TRANSACTIONS on Communications
Publication Date: 1997/06/25
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Issue on Network Operations and Management)
OSI management, CMIS, scope, approximation algorithm,
Full Text: PDF(579KB)>>
In OSI management, we utilize a scope parameter in Common Management Information Service (CMIS) that enables us to operate multiple Managed Objects (MOs) at one CMIS operation, so that we may reduce the number of communications between a manager and an agent. The more the number of MOs increases, the harder it is to find optimal combinations of scopes. In an existing approximation algorithm for finding optimal combinations of scopes, there are restrictions on the structure of a naming tree for the algorithm to work efficiently and the lower bound of its approximation ratio, n/4, grows in proportion to the number of MOs, n. This paper proposes a new approximation algorithm that removes the restriction on the structure of a naming tree and significantly improves the approximation ratio to (1 + ln n) in the upper bound, by keeping the same time complexity as the existing algorithm.