Overlay networks have been studied extensively in recent years as a flexible means to improving the reliability, resiliency, and performance of many networking applications. In this paper we present a novel use of overlay networks and distributed mechanisms to construct them for handling information assurance issues in networking systems. The problem is explored in the context of constructing an overlay that satisfies a given access control policies in decentralized information sharing systems. We formulate a new graph-theoretic optimization problem of constructing a minimum policy-compatible graph, which we show is NP-complete. We provide efficient centralized and fully-distributed heuristics, and prove the convergence property of the distributed process. Our simulation study with synthetic and empirical data set shows that our methods result in the performance (in terms of total number of links) very close to the optimal case (within 3%) for small input, and that they can reduce the number by up to 30% compared to a method based on minimum spanning tree algorithm for larger data set.
By: Bong Jun Ko; Starsky H. Y. Wong; Kang-Won Lee; Chi-Kin Chau
Published in: RC24935 in 2010
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .