امروز سه شنبه ، ۱۴۰۱/۰۳/۰۳
بدان

2 مدل سازی DHT مسیریابی: | 2 Modeling DHT Routing:

2 Modeling DHT Routing:

Defining models and metrics to describe performance of different DHT routing architectures is not a trivial task.

An application using the DHT lookup service is mostly interested in lookup latencies and in the ratio of successful lookups.

A user running DHT implementations might also be concerned by resource usage (CPU, memory, storage, bandwidth, etc...) while a network operator is only interested in the overall traffic (lookup + control) generated in the network.

Since most of these describe conflicting objectives, comparison only makes sense if conflicting performance metrics are analyzed together describing fundamental trade-offs.

Some of the commonly used performance metrics (e.g., overlay network diameter, node state) are not directly relevant for neither applications nor users nor net- work operators.

In [25], the author investigates the trade off between node state and overlay network diameter.

Loguinov et al - also use network diameter as the primary metric for routing in [15].

Node state affects primarily memory usage at nodes.

However, the amount of memory required to keep track of connections is typically far from being a bottle- neck in current systems.

Node state can also influence the maintenance bandwidth (e.g., in DHTs using per connection periodic keep-alive messages to detect con- nection failures).

However, it cannot be used as a general metric to characterize maintenance traffic.

Overlay network diameter can be used to derive only lower bounds on the worst- case number of routing hops for a lookup in a given overlay structure.

Short paths between nodes do not guarantee that a distributed routing algorithm is also able to find them [8].

Hence, the distribution or the average number of routing hops is a more informative performance metric which also allows to derive [23] lookup latency – a key performance metric from a user perspective.

Analytical comparison of a performance metric (e.g., the number of routing hops) of different DHTs is usually described by asymptotic notation, commonly used to characterize algorithm complexity.

E.g., CAN [19] with a D dimensional identifier space provides lookups in O( D 2 n D ) hops in a network of n nodes.

Although this is a useful and simple way to determine scalability of a particular algorithm, it has its limitations.

Due to potentially different unknown constants hidden within the notation, it is not possible to compare two different algorithms with the same asymptotic behavior (e.g., O(log n) hop count is typical for many DHTs).

Furthermore, it is also possible that an algorithm with better asymptotic behavior performs worse for practical network sizes.