CAN

The Content Addressable Network (CAN) is a member of the distributed-hash tables (DHT) family. The CAN distributes the nodes in a d-dimensional Cartesian coordinate space. In PeerfactSim.KOM, CAN is currently realized in 2-dimensional version. The virtual coordinate space is used to store the key-value pairs. Every pair has its own fixed position. This position is determined from the key. In the following, the SHA-1 hash function is used to resolve the key from the data name, but any kind of hash function which gives a unique key can be used.

In this space every node gets its own zone. To reduce the size of the routing table which is stored in each node and to make the overlay easily scalable, every node just knows its direct neighbors. In a d-dimensional coordinate space two nodes are neighbors if their zones overlap in d-1 dimensions and abut along one dimension. If the nodes are uniformly distributed over the space, the amount of neighbors is almost equal in every node. The nodes know all needed information of their neighbors, including overlay ID, IP-address and owned zone. Due to the small size of the routing table, only a small amount of nodes are affected if something changes in the network. The CAN overlay is self-organizing, no central node is needed to organize the overlay. The nodes learn about their neighbors and organize them during the join process.

Chord

Chord uses a one dimensional ID space. The IDs are arranged with increasing IDs on the ring. The ring can have IDs ranging from 0 to 2^m-1 (in our implementation m = 160). Each node has a successor and a predecessor. The successor to a node is the next node in the circle in the clockwise direction. The predecessor of a node is the next node in the circle but in the counter-clockwise direction. A node is responsible for a range between its own ID and the ID of its predecessor on the ring. Besides its successor and predecessor, each Chord node knows some short-cuts, so called fingers, to other nodes further away. The finger table has at most m entries (from 0 to m - 1). The ith entry in the table at node n contains the node ID of the successor of the key n+2i .

Gia

Gia enhances Gnutella-like overlays by allowing the peers to adapt the amount of load they have to handle in the overlay to their capabilities (in terms of e.g. available bandwidth). Unlike Gnutella 0.6, there is no classification into ultrapeers and leaves, instead, a capacity value is assigned to every peer in the overlay. The capacity value is used in the connection establishment procedure and in the query relaying step. The Gia protocol is more complex than Gnutella 0.6, but allows for a better load balancing between the peers ad their use of bandwidth

Gnutella 0.4

Gnutella 0.4 is an unstructured overlay, regarding the storing and look-up of resources. In its basic version, a peer may arbitrarily connect to other peers. New peers are discovered through multi-hop ping discovery mechanisms. A query is simply flooded from one peer to another with a Time-to-Live (TTL) between 2 to 6. Since the basic Gnutella overlay scales badly, some improvements have been proposed and are used in practice.

Gnutella 0.6

Gnutella 0.6 is one of the improvements of the original Gnutella overlay (Gnutella 0.4), implemented for example by the file sharing client LimeWire. In the Internet, the amount of bandwidth available at the peers is very heterogeneous. In Gnutella 0.6, we split the network into two types of nodes, the ultrapeers and the leaves. Peers with only a little amount of bandwidth will become leaves, the rest that is capable of carrying a larger part of Gnutella's overlay traffic will become ultrapeers. Leaves connect to ultrapeers like clients connect to a server. For connection resilience reasons, leaves connect to multiple ultrapeers (e.g. 3). If an ultrapeer fails, the leaf is still connected to two other ultrapeers and does not lose its connection to the overlay.

Kademlia

The actual implementation of Kademlia in PeerfactSim.KOM contains further modified versions of Kademlia like KAD, HKademlia and Kandy. Kademlia belongs to the family of distributed hash tables (DHT). Therefore its main purpose is to efficiently store and lookup key-value pairs distributed among all peers of the system. To form the overlay network each peer has an unique overlay identifier (overlay-ID), represented as 160-bit number. The ID is generated randomly or by hashing the peer’s IP-address. Furthermore, data items stored within the DHT are also assigned to IDs, which are generated by hashing the item’s content. They lie within the same key space as the overlay-IDs. A Peer is responsible for storing data items whose IDs are near to its own overlay-ID in means of the XOR distance metric. This metric is symmetric and implies that two keys are close to each other if they share a long prefix.

VON

The VON overlay belongs to the family of Information Dissemination Overlays (short “IDO”). It is designed to provide a highly scalable P2P-overlay structure for networked virtual environments such as multi-player online games. Fundamental to such virtual environment is a large number of users, with each user corresponding to a virtual entity in the environment such as a game character. Each entity features a position on the world map of the virtual environment and may move through this map as a result of user actions. Given that all entities may move through the world, the focus of the IDO is to give each entity a consistent knowledge about other entities nearby their position, to enable an efficient direct communication between them. This is very essential as nearby entities might have to be directly informed about important user actions without high delays. The need for this becomes clear if considering the most prominent examples, online multi-player game, where actions of one player may directly influence the state of other players, e.g. during a fight between the entities of players. While the direct communication to neighbors is the most important goal of an IDO, it is also important that an entity does not know too many neighbors. This would result in a system that is not scalable, as too many connections would have to be maintained and unnecessary network load would be generated due to messages being sent to neighbors that are not interested in the events of the sender.

To provide the described functionality, VON partitions the space of the virtual world by using Voronoi diagrams. This is a mathematical concept from the field of geometry which allows to completely decompose a space into non-overlapping regions. Each of these regions is enclosing a single point from a given finite set of points placed in the space. Simply spoken, the region belonging to a given point is defined by the part of the space which is closer to this point than to any other point of the set. In VON the set of points is derived from the positions of the nodes that are part of the overlay. Each node corresponds to a point in the global Voronoi diagram. However, the idea of a global Voronoi diagram is just conceptual to clarify the basic idea. To make the system scalable, the knowledge a node has about the overall system must be limited and should includes only a small subset of the nodes in the system. This is realized by the concept of a so called area-of-interest (AOI). The AOI is simply defined by a radius, which describes a circle around a node. All other nodes that are inside this circle are called AOI neighbors and have to be known by the node in the center. In addition to this, a node has to know all other nodes whose regions directly enclose its own region. These neighbors may already be included in the set of AOI neighbors, but can also lie outside the AOI circle. This way it is ensured that the overlay is kept connected, even if there are parts of the virtual world that only contain a small number of nodes.

pSense

To be completed

A A A | Drucken | Impressum | Sitemap | Suche | Kontakt
Zum SeitenanfangZum Seitenanfang