Query flooding
Encyclopedia
Query flooding is a method to search for a resource on a P2P network. It is simple but scale
s very poorly and thus is rarely used. Early versions of the Gnutella
protocol operated by query flooding; newer versions use more efficient search algorithms.
limit is reached.
Query flooding is simple to implement and is practical for small networks with few requests. It contacts all reachable nodes in the network and so can precisely determine whether a resource can be found in the network (Freenet
, for example, only returns a probabilistic result).
On the other hand, every request may cause every node to be contacted. Each node might generate a small number of queries; however, each such query floods the network. Thus, a larger network would generate far more traffic per node than a smaller one, making it inherently unscalable. Additionally, because a node can flood the network simply by issuing a request for a nonexistent resource, it could be possible to launch a denial-of-service attack
on the network.
protocol mandates query routing.
The query routing specification explains how the
ideas of
the original research are implemented. Other file sharing networks, such as the Kad network
, use distributed hash table
s to index files and for keyword searches. BitTorrent creates individual overlay network
s for sharing individual files (or archives). Searches are performed by other mechanisms, such as locating torrent files indexed on a web site. A similar mechanism can be use on the Gnutella network with magnet links. For instance Bitzi
provides a web interface to search for magnet links.
Earlier P2P
networks, such as Napster
, used a centralized database to locate files. This does not have a scaling problem, but the central server is a single point of failure.
Scalability
In electronics scalability is the ability of a system, network, or process, to handle growing amount of work in a graceful manner or its ability to be enlarged to accommodate that growth...
s very poorly and thus is rarely used. Early versions of the Gnutella
Gnutella
Gnutella is a large peer-to-peer network which, at the time of its creation, was the first decentralized peer-to-peer network of its kind, leading to other, later networks adopting the model...
protocol operated by query flooding; newer versions use more efficient search algorithms.
Operation
A P2P network generally consists of a large number of nodes each connected not to all other nodes, but a small subset of the nodes. If a node wants to find a resource on the network, which may be on a node it does not know about, it could simply broadcast its search query to its immediate neighbours. If the neighbours do not have the resource, it then asks its neighbours to forward the query to their neighbours in turn. This is repeated until the resource is found or all the nodes have been contacted, or perhaps a network-imposed hopHop (telecommunications)
In telecommunication, the term hop has the following meanings:#The excursion of a radio wave from the Earth to the ionosphere and back to the Earth...
limit is reached.
Query flooding is simple to implement and is practical for small networks with few requests. It contacts all reachable nodes in the network and so can precisely determine whether a resource can be found in the network (Freenet
Freenet
Freenet is a decentralized, censorship-resistant distributed data store originally designed by Ian Clarke. According to Clarke, Freenet aims to provide freedom of speech through a peer-to-peer network with strong protection of anonymity; as part of supporting its users' freedom, Freenet is free and...
, for example, only returns a probabilistic result).
On the other hand, every request may cause every node to be contacted. Each node might generate a small number of queries; however, each such query floods the network. Thus, a larger network would generate far more traffic per node than a smaller one, making it inherently unscalable. Additionally, because a node can flood the network simply by issuing a request for a nonexistent resource, it could be possible to launch a denial-of-service attack
Denial-of-service attack
A denial-of-service attack or distributed denial-of-service attack is an attempt to make a computer resource unavailable to its intended users...
on the network.
Alternatives
Version 0.6 of the GnutellaGnutella
Gnutella is a large peer-to-peer network which, at the time of its creation, was the first decentralized peer-to-peer network of its kind, leading to other, later networks adopting the model...
protocol mandates query routing.
The query routing specification explains how the
ideas of
the original research are implemented. Other file sharing networks, such as the Kad network
Kad Network
The Kad network is a peer-to-peer network which implements the Kademlia P2P overlay protocol. The majority of users on the Kad Network are also connected to servers on the eDonkey network, and Kad Network clients typically query known nodes on the eDonkey network in order to find an initial node...
, use distributed hash table
Distributed hash table
A distributed hash table is a class of a decentralized distributed system that provides a lookup service similar to a hash table; pairs are stored in a DHT, and any participating node can efficiently retrieve the value associated with a given key...
s to index files and for keyword searches. BitTorrent creates individual overlay network
Overlay network
An overlay network is a computer network which is built on the top of another network. Nodes in the overlay can be thought of as being connected by virtual or logical links, each of which corresponds to a path, perhaps through many physical links, in the underlying network...
s for sharing individual files (or archives). Searches are performed by other mechanisms, such as locating torrent files indexed on a web site. A similar mechanism can be use on the Gnutella network with magnet links. For instance Bitzi
Bitzi
Bitzi is a website where volunteers share reports about any kind of digital file, with identifying metadata, commentary, and other ratings.Information contributed and rated by volunteers is compiled into the Bitpedia data set and reference work, described by Bitzi as a "digital media encyclopedia"...
provides a web interface to search for magnet links.
Earlier P2P
Peer-to-peer
Peer-to-peer computing or networking is a distributed application architecture that partitions tasks or workloads among peers. Peers are equally privileged, equipotent participants in the application...
networks, such as Napster
Napster
Napster is an online music store and a Best Buy company. It was originally founded as a pioneering peer-to-peer file sharing Internet service that emphasized sharing audio files that were typically digitally encoded music as MP3 format files...
, used a centralized database to locate files. This does not have a scaling problem, but the central server is a single point of failure.