Menu:

Orpheus: A Composable, Value-added Service Overlay Network

Background

The Internet has evolved to become a commercial infrastructure of service delivery instead of merely providing host connectivity. However, the current Internet infrastructure has become inadequate for delivering various services because of the problems pertaining to scalability, implementation and deployment difficulties. Different forms of overlay networks have been developed to provide attractive service provisioning solutions, which are difficult to be implemented and deployed in the IP-layer. The examples include end system multicast, resilient routing, and peer-to-peer file sharing overlay networks. Beyond this, we envision the emergence of value-added service overlay networks, where overlay nodes provide not only application-level data routing but also value-added services, such as media compression/transcoding, language translation, and context-aware encryption or decryption. Each service can have multiple instances, which provide same or different quality-of-service (QoS) levels. Different service instances can be composed on-the-fly into a service path under the constraints of user QoS requirements, such as delay and availability.

Unlike data routing, composing an end-to-end service path requires not only the network connectivity, but also the satisfactions of various constraints such as function constraints and composition constraints. The function constraints mean that the service path has to pass through certain nodes, which provide correct service functions. The composition constraints mean that the composition of service instances on the service path is directed by a set of service-specific constraints. For example, dependency constraints denote that service A is dependent on service B; and consistency constraints specify that the output interface of service A is consistent with the input interface of service B.

Introduction

Service Path Composition.

Previous research has proposed similar service overlay networks, and addressed different aspects of composing service paths in overlay networks. For example, the SAHARA project addresses the fault-resilience and load balancing problems in wide-area service composition. The SPY-Net framework addressed the problem of resource contention while finding multimedia service paths in a media proxy overlay network. However, these systems use information flooding to make each node acquire the global view of the overlay network for service composition, which makes their solutions not scalable. In contrast to a unicast data routing path, a unicast service path can be either linear i.e., a chain of services, or non-linear i.e., the service path is represented by an acyclic directed graph (DAG). However, none of existing work can compose non-linear service paths in overlay networks.

Hence, we propose SpiderNet, a novel quality-aware and composable service overlay network, which aims to provide scalable service path routing under various constraints, namely the function constraints, composition constraints, and QoS constraints for the service path. For scalability, SpiderNet employs an on-demand distributed probing algorithm for constrained routing during the service setup phase. The probing algorithm observes the function and composition constraints at each probed SpiderNet node. Available historical information is used to improve the probing performance. The service path is selected among all probed candidate service paths based on both user QoS requirements and load balancing in SpiderNet. Service overlay networks are highly dynamic systems with node departures and failures. During runtime, an established service path can be failed or have significant performance degradations. Thus, we introduce the runtime service path maintenance, which can quickly re-routing the service path to maintain the QoS assurance probabilities under various overlay network changes. For scalability and real time fault recovery, the dynamic service path maintenance is achieved by simultaneously maintaining a small number of alternative service paths. We have conducted a detailed evaluation of the SpiderNet architecture and algorithms using extensive simulations. The results show that SpiderNet can provide high statistical QoS assurances with low overhead on different overlay network topologies. For dynamic overlay networks with moderate topology variations, SpiderNet can recover most failed service paths by maintaining a small number of alternative service paths. We are implementing a prototype of SpiderNet and test it on PlanetLab.


Service Multicast.

In the past few years, Internet heterogeneity (e.g., in network connections and machines) has more and more become a problem, especially in multimedia scenarios. One of the approaches to solving the heterogeneity problem is to adopt media proxies so that data can be transformed according to the en-to-end requirements. Based on the distributed, composable service model in Internet overlay networks, service routing has emerged as a way of dynamically customizing and transforming end-to-end multimedia data to achieve matching between server's output and client's input in multimedia scenarios. In such a service model, services, which may be widely distributed in media proxies across the Internet overlay networks, can be applied in a chain to accomplish more complex tasks. Given such a scenario, a challenging problem lies in how to maximize service sharing by integrating service routing with multicast. We call such a problem service multicast routing.

Compared to service unicast, service multicast is desirable because it helps to save both network bandwidth and computation at proxies. Unlike data multicast, where the tree links carry homogeneous data, in service multicast, data traversing the tree links is heterogeneous due to the fact that services are transformational. We argue that the conventional data multicast routing protocols (e.g., DVMRP, MOSPF, and PIM) are not readily applicable to service multicast routing, because they lack to deal with the following aspects that are key to service multicast routing: (1) service capability aspect - in data multicast, all network nodes have one single function - to forward data, while in service multicast, proxy nodes may apply different functionalities to data according to their service capability; (2) service dependency aspect - in service routing, services have to be applied following their dependency relations. In summary, while data multicast is solely based on network connectivities, service multicast depends on network connectivities and service requirements (service capability and service dependency).  Clearly, for applications that are QoS demanding, service multicast should further consider QoS issues.

Figure 1(a) shows a network topology where all nodes are deemed equal in the sense that their major task is to forward data. A data multicast tree is highlighted in bold lines. However, in a proxy topology, nodes may be heterogeneous in terms of their service capabilities. For example, in Figure 1(b), n0 and n1 do not contain any transformation services except forwarding, n2 contains a watermarking service - w, and n3 and n4 contain two different filtering services - f1 and f2, respectively. If the end-to-end path from n0 to n3 requires w -> f1 (note the dependency relation between the two services), and the end-to-end path from n0 to n4 requires w -> f2, then a feasible service multicast tree is shown in bold lines. Note that with the same network connectivities, the constructed service multicast tree can be dramatically different from the data multicast tree. We are experimenting with two different approaches for building service multicast trees: source-base and distributed.

Publications

Book Chapter and Journal Conference

Talks

Related Projects

Funding Agencies

The Orpheus project is supported by the NASA Grant (Grant Number NASA NAG 2-1250) and NSF under Grants No. 9870736, 9970139, EIA 99-72884EQ, NSF-CCR-9988199, ANI 03-23434 and CNS CSR-AES 05-09314.

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation or US govenment.