Approximation Algorithm for Optimal Combinations of Scopes in OSI Management Operations (Special Issue on Network Operations and Management)

概要

論文の詳細を見る
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.
社団法人電子情報通信学会の論文
1997-06-25