US 2010/0250589 A1Published application

Tree structured P2P overlay database system

AssigneeGrasstell Networks LLC

InventorWei Kang Tsai

Life of this patent

Estimating the term…

Loading patent…

Abstract

A system and methods to construct and maintain a balanced-tree overlay network are used to host distributed databases. As overlay nodes can detach from and re-attach to an overlay unpredictably, overlay protocols must maintain the overlay tree properly to minimize communication overheads associated with store and retrieval operations of the hosted databases. Unlike a DHT (distributed hash table) approach, the balanced-tree approach has the advantages of stabilizibility and provable correctness of the overlay protocols. Fast inquiry can be achieved by using a caching algorithm that allows each overlay node to keep track of data ranges stored in a neighboring set of nodes. Self-healing and load balancing protocols are also incorporated to enhance the performance and stability of the tree-structured overlay.

Claims14

Dependent claims

A method to implement distributed databases hosted over a P2P tree-structured overlay, comprising:

a plurality of nodes called grassnodes or simply nodes, forming a P2P overlay;
a plurality of users, each with a unique key;
a plurality of data items, each with a unique key;
and a set of distributed overlay protocols called grasshoc protocols;
wherein each said grassnode is connected to other grassnodes through an IP network;
each said grassnode may be associated with a finite number of child grassnodes and a single parent grassnode, thus the entirety of said grassnodes forming approximately a balanced-tree called a grasshoc tree or simply tree;
each said grassnode may be repeatedly attached to and detached from said overlay unpredictably;
and said grasshoc protocol enables said grassnodes to locate the IP address of a grassnode needed for storing, retrieval and other control mechanisms, for the purpose of implementing said distributed databases.

5 more elements

Dependencies are inferred from the claim text.