« the 30,000 ft. view | Main | a bit more on manifold-g »
December 22, 2004
the manifold algorithms
Okay, so, roughly, what are the Manifold algorithms? They are two different self-organizing algorithms. The first, Manifold-B (Manifold-Broadcast) is used for local/inexact searches, while Manifold-G (Manifold-Global) is used for global self-organizing exact resolution.
Manifold-B
Manifold-B is a typical broadcast-style (or flooding-style) p2p system, similar to gnutella. Basically, on startup a node looks for one or more nodes already in the network (using a list of previously known nodes if available) and establishes connections to some or all of them (depending on individual node load, etc). Once at least one connection is complete queries can begin to propagate. Queries are constrained by a time-to-live (TTL) parameter, propagating across all connections of each node as long as the maximum number of hops has not been reached, as is common in these types of networks.
Some advantages of Manifold-B are:
- Low consistency requirements (ie., no topology structural requirements).
- Allows substring match and multiple key insertion per node.
- Fast in its local environment, with network load controlled by number of nodes.
- Extremely well-adapted to ad hoc wireless environments.
Some disadvantages:
- Local only (not global), and thus limited in reach.
- More overhead than Manifold-G for exact queries.
Manifold-G
Manifold-G is an Overlay, basically a virtual topology built on top of an actual network. Why an overlay? Because when building a virtual topology, we can give it a well-defined structure, that is predictable, with lookup path lengths bounded by a certain limit.
In the case of Manifold-G, the topology used is that of an n-dimensional hypercube (or n-cube, or l-cube, depending on the letter used to specify dimensions :)). Manifold-G assigns each name a particular bit-string, which is controlled by the node with that name (local control was an important component of name resolution, other overlays don't necessarily guarantee locality in that sense, and although you could force them to, they are mostly designed as distributed hashmaps, which maintain a set of keys on each node--which has other great uses!).
The tricky part is that a hypercube can only be navigated predictably when it is complete, i.e., when all its nodes (vertices) are present. So Manifold-G uses the predictability of a structure to its advantage to virtualize those missing nodes. More on the specifics in a later post (if you can't wait, you can also check the text of the dissertation).
Manifold-G advantages:
- Fast! Number of steps to target (or "not found" reported) is a maximum of O(log N) with N the number of nodes in the network.
- There is no penalty for more nodes joining the network, in fact the network works better with more nodes because there are less virtual nodes to take care of. (This is weird, I know, but true).
Disadvantages:
- High consistency requirements. This is probably the weakest point of the algorithm, very clear during join and leave operations of a node, which require a multi-node transactional status to keep the hypercube topology intact and not break searches. This can be minimized by pre-loading information.
- A "neighbor" in Manifold-G can actually be on the other side of the Internet, which can be a problem when slow connections are involved. In small networks (e.g., a few dozen nodes), Manifold-G actually has more overhead than Manifold-B, because the paths in the hypercube do not necessarily adjust to the actual topology. This advantage of Manifold-B is most notable in small-medium ad hoc wireless networks, which do broadcast at the physical layer level. In larger networks, some geolocation-based optimizations as well as proxying are possible, as mentioned in the dissertation.
A couple of things
Aside from serving well for the two main usage modes that I was targeting, the algorithms complement each other. For example, Manifold-B has much lower consistency requirements and so can operate when Manifold-G might not be available, and thus either partially cover some queries, or help Manifold-G in building the network.
It has been shown that it is possible to embed broadcast trees within overlays, but in my opinion maintaining two networks is a small price to pay for the advantages of both, particularly on wireless ad hoc (small-to-medium), where Manifold-B has a clear advantage over the overlay.
Posted by diego at December 22, 2004 11:27 AM