sFlow: Towards Resource-Efficient and Agile Service Federation in ServiceOverlay NetworksMea Wang, Baochun Li, Zongpeng LiDepartment of Electrical and Computer EngineeringUniversity of Toronto{mea, bli, arcane}@eecg.toronto.eduAbstractExisting research work towards the composition of com-plex federated services has assumed that service requestsand deliveries flow through a particular service path or tree.In this paper, we extend such a service model to a directedacyclic graph, allowing services to be delivered via paral-lel paths and interleaved with each other. Such an assump-tion of the service flow model has apparently introducedcomplexities towards the development of a distributed al-gorithm to federate existing services, as well as the provi-sioning of the required quality in the most resource-efficientfashion. To this end, we propose sFlow, a fully distributedalgorithm to be executed on all service nodes, such that thefederated service flow graph is resource efficient, performswell, and meets the demands of service consumers.1. IntroductionServices have emerged as one of the main motivationsto construct application-layer overlay networks. The con-cept of services in service overlay networks is not specificto certain categories, and is in fact quite generic. Nodes inoverlay networks may process data (filtering, computationor media transcoding services), relay data (proxy or queryforwarding services), store data (storage services) or searchfor data (peer-to-peer search engines). In most cases, theconsumers demand complex services that require the fed-eration or composition of multiple types and instances ofservices in overlay networks. The result of a service federa-tion is referred to as a federated service. The most resource-efficient service federation minimizes the network and com-puting resources requirements.Our original contribution is to propose sFlow, a fully dis-tributed and application-independent algorithm to federateservice instances in a resource efficient fashion and accord-ing to the needs of service consumers, even when the ser-vices are required to serve in a non-sequential order, andmay be characterized by a directed acyclic graph. Usingthe directed acyclic graph as the model for service flowgraphs has one additional benefit: it generally leads to su-perior performance, in terms of bandwidth and service la-tency. These benefits are validated by our extensive resultsin performance evaluations.Towards the direction of end-to-end service federation,Gu et al. [1] and Xu et al. [5] have proposed QoS-awarealgorithms to find point-to-point service paths. In particu-lar, the algorithm proposed by Xu et al. is designed for thehighly connected service mesh generated by cost-effectivemesh augmentation methods. Beyond the concept of ser-vice paths that sequentially connect services, the recent con-cept of service multicast trees [3] makes it possible to cre-ate multiple paths with shared services merged, effectivelyforming a multicast tree. Instead of computing the servicepaths in a centralized fashion, Jin et al. [2] have proposedan distributed service federation algorithm. In this work, theservice overlay network is first organized into a cluster net-work. The service path finding algorithm is then applied hi-erarchically in a divide-and-conquer fashion.Nonetheless, these existing algorithms require servicesperforming tasks consecutively to meet requirements withrespect to resources. This type of service federation is onlyeffective for a limited range of applications, such as mul-timedia transcoding and streaming. In more generic appli-cations, as in our example, multiple services may performtasks independent of each other, and services may be in-terconnected in a more arbitrary fashion. In this paper, weseek to address the more generic cases of federating servicesin service overlay networks, where the relationship amongservices may be characterized as a directed acyclic graph(DAG), referred henceforth as the service flow graph.Inaservice flow graph, federated services may perform tasks ineither a sequential, parallel, or interleaved fashion as neces-sary.The remainder of this paper is organized as follows. InSec. 2 and 3, we present salient properties of service fed-eration in a graph-theoretic setting, and provide theoreticalinsights to these problems. sFlow, our algorithm towardsresource-efficient service federation, is presented in Sec. 4.Sec. 5 presents performance evaluation results of the dis-Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS’04) 1063-6927/04 $20.00 © 2004 IEEEtributed algorithm. The paper is concluded in Sec. 6.2. Towards Resource-Efficient and Agile Ser-vice Federation: Preliminaries2.1. Service RequirementsBefore we present the general model of service require-ments, we first consider the example in Fig. 1, where thesource service (Travel Engine) needs to send the requesteddata to Agency A via the Hotel service. This example il-lustrates the most primitive form of service requirements,where a single chain of services, referred to as the servicepath is specified.13 6 9Travel Engine Hotel CurrencyAgency AFigure 1. Service path: a basic form of ser-vice requirementsService requirements may also be more flexible by al-lowing optional services, as the example illustrated inFig. 2, which takes two alternative graphical representa-tions. The source service (Travel Engine) may send the re-quested data to the Agency A service via a chain of theAttraction Service and either the Map or the Transla-tor services. The topology of services that leads to betterperformance is preferably selected.15 97, 815 8 9 7(a)(b)ORTravel EngineAttraction Map or Translator Agency ATravel EngineAttractionTranslatorMapAgency AFigure 2. Optional services: an enhancedform of service requirementsIt is rather restrictive to require that services be chainedsequentially. We further improve the model of service re-quirements to allow a number of disjoint service paths,which execute service tasks concurrently. These disjointservice paths do not share any particular service except thesource and the sink services. An example of disjoint servicepaths is shown in Fig. 3, where the source service (TravelEngine) sends airline, hotel, and attraction information tothe Agency A service in three disjoint paths.Nonetheless, the results of a particular service may berequired by more than one downstream services, while it111
View Full Document
Unlocking...