TY - GEN
T1 - The K-observer problem in computer networks
AU - Acharya, H. B.
AU - Choi, Taehwan
AU - Bazzi, Rida
AU - Gouda, Mohamed G.
PY - 2011/10/21
Y1 - 2011/10/21
N2 - For any non-negative integer K, a K-observer P of a network N is a set of nodes in N such that each message, that travels at least K hops in N, is handled (and so observed) by at least one node in P. A K-observer P of a network N is minimum iff the number of nodes in P is less than or equal the number of nodes in every K-observer of N. The nodes in a minimum K-observer of a network N can be used to monitor the message traffic in network N, detect denial-of-service attacks, and act as firewalls to identify and discard attack messages. This paper considers the problem of constructing a minimum K-observer for any given network. We show that the problem is NP-hard for general networks, and give linear-time algorithms for constructing minimum or near-minimum K-observers for special classes of networks: trees, rings, L-rings, and large grids.
AB - For any non-negative integer K, a K-observer P of a network N is a set of nodes in N such that each message, that travels at least K hops in N, is handled (and so observed) by at least one node in P. A K-observer P of a network N is minimum iff the number of nodes in P is less than or equal the number of nodes in every K-observer of N. The nodes in a minimum K-observer of a network N can be used to monitor the message traffic in network N, detect denial-of-service attacks, and act as firewalls to identify and discard attack messages. This paper considers the problem of constructing a minimum K-observer for any given network. We show that the problem is NP-hard for general networks, and give linear-time algorithms for constructing minimum or near-minimum K-observers for special classes of networks: trees, rings, L-rings, and large grids.
UR - http://www.scopus.com/inward/record.url?scp=80054706158&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80054706158&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-24550-3_3
DO - 10.1007/978-3-642-24550-3_3
M3 - Conference contribution
AN - SCOPUS:80054706158
SN - 9783642245497
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 5
EP - 18
BT - Stabilization, Safety, and Security of Distributed Systems - 13th International Symposium, SSS 2011, Proceedings
T2 - 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2011
Y2 - 10 October 2011 through 12 October 2011
ER -