Approximation Algorithm for Optimal Combinations of Scopes in OSI Management Operations


IEICE TRANSACTIONS on Communications   Vol.E80-B   No.6   pp.881-887
Publication Date: 1997/06/25
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Issue on Network Operations and Management)
Category: Protocol
OSI management,  CMIS,  scope,  approximation algorithm,  

Full Text: PDF>>
Buy this Article

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.