Routing

Routing is a broad topic. An entire book (in fact, many) could be devoted to the subject of Internet routing. P2P introduces application-level routing that overlays network routing. This is the area we will focus on.

Overlay Networks

A P2P network forms a self-organizing overlay network on the Internet. Any Internet-connected host that runs P2P software and has proper credentials can participate in the overlay network. Each P2P node typically has a unique ID.

The P2P software builds a routing table that attempts to organize the overlay network to increase efficiency and resiliency. The sophistication of locality metrics, and the location, or path diversity, improves the performance of the overlay network.

Locality

Locality is based on a proximity metric. In other words, efficiency can be gained if you know the "distance" between any pair of nodes. This distance value represents the number of hops required to get from point A to point B. Or, it might represent the latency, or time delay between points. How it is computed or determined is implementation-specific.

The most simplistic routing implementation ignores locality considerations altogether. Every peer in the routing table is considered equal. Any peer can be used to transfer a discovery or search request. Message propagation ensures that as many peers as possible are queried. In this scenario, you typically limit the number of peers (connections) in the routing table. In addition, you must implement a loopback mechanism to drop message requests you have already received. A unique message ID is stored for each message to determine redundant requests. This is the routing technique employed in most flooding broadcast systems.

A more sophisticated approach recognizes the distance metric. The function that determines distance is critical to the overlay network's effectiveness. Peers that are determined to be close will receive preferential routing. However, that has to be balanced to ensure diversity in the routing table population.

Diversity

Diversity is based on a distribution metric. The goal of the distribution metric is to ensure that discovery requests are appropriately partitioned. Unlike locality, which optimizes distance, diversity optimizes geographic distribution.

The uniform distribution of peers such as relays and rendezvous points improves the scalability of the virtual space by reducing or eliminating a large number of discovery requests. This requires a function that is capable of computing a distribution metric when given a unique value, such as an IP address, or the preconfiguration of pivot points in the network. A pivot point provides a route from one major network segment to another.

The uniform distribution of peers ensures an even population of the virtual space (network), and reduces the size requirements of the routing table. Each node within the routing table can refer to one of potentially many nodes within a geographic distribution.

Node Redundancy

Finally, redundancy ensures that pivot points in the routing map, such as those that implement diversity, are replicated and redundant. This is to ensure that no single point of failure exists in the overall virtual space.

Flat Network Model

In a flat overlay network, each peer processes and propagates requests they receive to other peers to ensure the broad distribution of requests, as shown in Figure 6.7. As mentioned previously, network traffic will grow exponentially given a linear increase in peers or queries within the network.

Figure 6.7. A flat overlay network model will broadcast requests to every reachable peer. This model grows exponentially as the network grows linearly. Bandwidth saturation quickly becomes an issue. This model is only applicable for small work groups.

Simple broadcast is only viable in small networks.

Hierarchical Network Model

A hierarchical overlay network will reduce network traffic by organizing peers into a group hierarchy. Peers are only capable of discovery within their own group, or peers only communicate with peers that possess certain operational characteristics. For instance, hierarchical organization can result from differentiating high-bandwidth, dedicated peers from slower, less powerful ones. Hierarchies can be built from metadata that defines network intelligence and peer capabilities. Such metadata can include the following:

• Equate resource consumption to the level of network participation. Discovery and search requests are discarded from noncontributing (sharing) peers.

• Avoid expensive protocol operations such as unnecessary broadcast replies with intelligent forwarding to intended destinations.

• Implement connection profiles to favor higher-bandwidth connections over slower modem connections.

• Allow high-bandwidth broadband users to act as proxies for slower modem users.

• Collect peer performance and measurement metrics.