Information Technology Reference
In-Depth Information
just by hashing local keys. For example, in Fig. 2, if after evicting “user2” we
assume that “user4” and “user5” knew about
2
K
1
, we are also certain that they
3
in their local store, and we could safely delete node 3 from the
estimate of the KHT-WS.
As we mentioned in Section 1, it is sometimes dicult for a KHT-CM to keep
track of the key state of all its possible clients, in particular when the KHT-CM
is not part of the group. Therefore, the best that the KHT-CM can expect is to
obtain an approximation of the KHT-WS conservative enough so that it contains
the real KHT-WS, but small enough to be communicated eciently.
The heuristic that we use to derive the KHT-WS approximation works in the
following way: first, we try to approximate the size of the working set,
already have
K
WS
size
.
Then, we compute for each node in the KHT the likelihood of being part of that
working set,
P
i
. Finally, we obtain the KHT-WS as formed with the
WS
size
nodes of the KHT that have the highest
P
i
.
WS
size
depends on whether the KHT-
CM can obtain precise feedback on how useful the information that it is broad-
casting is for clients. For example, every time our estimation of the KHT-WS
fails, and a client cannot recover the current key from the information provided,
the KHT-CM should be notified. In our implementation we assume that the
LKH KM is providing everybody with accurate statistics of clients that need to
re-register with him, and we dynamically adjust the window size. The magnitude
of these adjustments is computed using a variant of the Newton optimization
method, and is based on the changes of failure rate caused by previous variations
of the KHT WS.
In order to compute the relative importance of each KHT node,
How accurately we can determine the
P
i
, we use a
combination of ageing with an estimate of the number of possible clients that will
need that node. Ageing information is computed by time-stamping when a node
was first added to the KHT-WS
2
, and uses an overall estimate of how frequently
nodes update their state, since the state update behaviour of all clients is uniform
(or non-uniform but unpredictable) across the tree. The number of clients that
need that node is linked to the distance to the root, since our allocation strategy
tries to keep the tree reasonably balanced.
4
Anonymous Group Content Delivery with KHT
In Anonymous Group Content Delivery (AGCD), content is distributed e-
ciently to a subscribed community, e.g., to enforce a “pay-per-view” scheme,
but guaranteeing that the distribution source cannot learn what a particular
client downloads. A practical solution is to encrypt content with a key shared
by the current “paying” members, and use multicasting or caching of encrypted
content for ecient delivery. However, since these members are not “on-line” all
the time, key updates should be somehow embedded within the content so that
the majority
of valid members can still recover the current key. Our simulation
2
Nodes that have never been added to the KHT-WS have the highest priority, to
ensure that new updates are quickly propagated.
