Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
The K-Observer Problem in Computer Networks
verfasst von : H. B. Acharya, Taehwan Choi, Rida A. Bazzi, Mohamed G. Gouda
Erschienen in: Stabilization, Safety, and Security of Distributed Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.