The idea of sharing resources across the network has become very popular during the last few years, leading to a diversified scenario in which shared resources include not only files and videos but also storage and CPU cycles. A new trend is to extend this paradigm toward a distributed architecture in which multiple network nodes cooperate to provide services in a distributed fashion, thus ensuring robustness and scalability. Peer-to-peer (P2P) overlays are the natural solution to achieve this goal as, thanks to their simplicity and flexibility, they can change their topology in order to fit the needs of the different kinds of services that can be provided on top of them. This chapter focuses on the indexing of nodes (i.e., the service providers) in these P2P systems, presenting the state-of-the-art solutions concerning the P2P-based indexing architectures and a taxonomy of possible services that can be built upon different overlay structures. Finally, emphasis is given to mechanisms implementing service selection based on some cost parameters (e.g., topological proximity) in order to introduce some mechanism based on optimality in case multiple service providers exist.
TopIntroduction
Sharing resources across the network became a mainstream technology in the mid-Eighties when Microsoft/IBM LAN Manager and UNIX NFS appeared on the market. At that time, sharing was mainly intended for disks and printing resources and was limited to local area networks. Only some years later, these systems were extended in order to operate also across the Internet; this required also deep changes, e.g., in case of IBM/Microsoft LAN Manager, the original NetBEUI protocol (which was non-routable) had to be replaced with TCP/IP. Before that, sharing was mainly intended as a way to use CPU cycles of a powerful supercomputer (and, later, minicomputer) from other remote terminals.
The tremendous growth in terms of processing and storage capabilities in the recent years made the idea of resource sharing extremely interesting, since most of modern PCs have a huge amount of resources (CPU cycles, disk space, and, recently, bandwidth) that are not used for most of the time, and that can be shared without penalizing the local user of the machine. Therefore, the idea of sharing resources across the network has become very popular, leading to diversified scenarios in which shared resources include not just files but also storage (e.g., distributed file systems), bandwidth (e.g., network proxies, anonymizers, or real-time video streaming) and CPU cycles. In general, this same idea has broadened to encompass not only basic resources available on the different machines, but also application services (i.e. application software providing some sort of service to other users over the network).
The resulting situation is that the same term is used with different meanings, in different contexts and communities. It is important to introduce definitions of the most important terms used in this chapter, without claiming that those definitions are universally accepted. The human users or some automatic routines require services – e.g. some mathematical computation on special hardware, the content of one file, a telephone call, some disk space. A service is accessible by contacting one or more service providers, which are hosted in one or more network nodes, with the access to a specific service provider available on a single node. Each node may supply the access to one or more service providers. A service may require the use of other services, in order to be executed, resulting in a composed service. However, from the point of view of the indexing of nodes providing a service, there is no distinction between composed and non-composed services.
The transition from early days resource sharing to nowadays distributed systems has been possible thanks to two important changes: (a) a shift in the technical paradigm that enables resource sharing, and (b) a new user-level perspective. With respect to the first point, resource sharing was previously based mostly on a client-server paradigm (a server shared its resources with a set of clients), while recently each user is a service provider and a client at the same time. The unprecedented number of service providers required the development of a new generation of technologies, which are able to organize such systems in a more efficient way than the old centralized topology (which is the paradigm commonly adopted in client-server applications). With respect to the second point, systems are becoming transparent to the end-user. While in the early days a user was able to select if a given resource was local or remote, in the most recent systems the user asks for a service, and the systems provides it to him. While the user do not know the physical location of the resource (neither he wants to know), the system has to keep into consideration additional parameters that are typical in a location-aware distributed system. For instance, when a user ask for storage capabilities, such system does not have to locate simply a service provider with enough disk space, but this location must be possibly close enough so that the user does not even recognize that its data is flowing through the network.