Tetiana Kot

Larisa Globa

Alexander Schill

Advanced Approach to Future Service Development

Keywords: service development, OSS/BSS, non-functional requirements, workflow design and transformation, Dia editor

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Today, companies, working in global environment, constantly renovate and improve their technologies, providing services by web-oriented applications [START_REF] Kornel Terplan | OSS Essentials: Support System Solutions for Service Providers / Kornel Terplan[END_REF]. This is realized via service development and re-engineering. Companies tend to minimize time of service provision, constantly improving communication technologies and applications. Thus, means and tools for fast workflow design and reengineering during system runtime and for providing services within a minimal time are in high demand.

The lifecycle of service development is an iterative process, consisting of the following stages:

1. workflow design: development and description of computation independent and computational workflows, including service planning, applications prototyping;

2. workflow analysis and simulation, considering several system parameters; 3. workflow enactment, providing deployment models, considering both hardware and software service deployment alternatives; 4. service/workflows monitoring, leading to services re-configuration.

Currently the service planning stage is performed manually. This does not result in optimal solutions because a lot of factors have to be considered when planning differentiated services [START_REF]Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers[END_REF]. Furthermore, in the current state-of-the-art computational independent workflow design, being performed using existing notations and tools on one hand all required parameters, necessary on the service planning stage, such as numerical values of execution time and resources, and also document and information flows, supporting service provision, are not considered and on the other hand poor connection to system functionality, realizing these workflows are provide.

When service design and deployment, an important aspect concerns NFR1 to service provision. It is extremely important to meet NFR on design stage, otherwise provided service may be useless in practice.

Currently, NFR are not considered with perspective of provided services list as legacy methods can design service according to NFR, but cannot model an influence of concurrent services on particular NFR because of collaboration between services. There are also no tools allowing flexible balancing between services.

Transformation processes between workflow modeling stages is still an open question, though there are transformation standards and languages [START_REF] Recker | On the Translation between BPMN and BPEL: Conceptual Mismatch between Process Modeling Languages[END_REF], but this issue is not fully automated and has to be investigated to make service design correct.

This paper describes an advanced approach to future service development, including novel computational independent workflow design method, NFR balancing method and modified service workflows transformation method.

The paper is structured as follows: Section 2 contains state of the art analysis of workflow design notations and tools. State of the art analysis of methods and approaches to considering NFR. NFR analysis methods and service implementation technologies are described. BPMN to BPEL transformation strategies are also considered.

Section 3 introduces advanced approach to service development. It includes workflow design method, focusing on two core aspects: a computational independent workflow model and workflow analysis method, providing service provisioning time minimization; NFR balancing method, focusing on functional and non-functional requirements collaboration; modified service workflows transformation method.

Section 4 presents a prototypical realization of the advanced approach, including design and transformation tools and highlights evaluation results of the developed tools. The evaluation has been applied using a real-world scenario within a telecommunication company.

Section 5 concludes the work with a summary and outlook on future work.

2

State of the art and Background

Workflow design notations and tools

Service planning is defined by finding a good way to create service provision at minimal time, having specific resource values as a limitation. In the following a summary of the state of the art of the central areas of this overall field will be discussed. A state of the art analysis of workflow design notations and tools, workflow analysis methods and systems, parameters, which should be taken into account at the planning stage and NRF design methods are presented.

Computational independent workflow design.

Computational independent workflows are designed using graphical standards, allowing their formalization in a diagrammatic way. Analysis has shown that in practice computational independent workflows are usually designed using graphical notations such as BPMN 2.02 , UML AD3 , USLD 4 and tools such as CA ERwin Process Modeler 5 and Enterprise Architect 6 .

The main criteria, used when analyzing current state-of-the-art notations and tools for computational independent workflow design, are possibility to consider and analyze several parameters, necessary on the service planning stage, such as service provision time and resources, and on the other hand provide connection to system functionality, which should realize these workflows.

USDL doesn't meet all the requirements of workflows analysis and design, its usage is difficult due to its complexity, in spite of its comprehensiveness.

The main argument against using regular BPMN is that management of resources can be expressed only via lanes (actors, roles, etc.) or performers of user or manual tasks [START_REF] Börger | Approaches to modeling business processes: a critical analysis of BPMN, workflow patterns and YAWL[END_REF], when execution time parameters are not considered. All further existing workflow modeling notations have this core criticism in common.

Nevertheless, BPMN, providing computational independent to computing workflows transformation (BPEL7 diagrams), was applied as a basic notation for computational independent workflow design, being extended with added missing concepts [START_REF] Kot | Applying business process modeling method when telecommunication services development[END_REF].

Workflow analysis.

The overview of the workflow analysis methods and tools has shown, that there exist two types of analysis, both considering computational workflow [START_REF] Kot | A novel approach to increase efficiency of OSS/BSS workflow planning and design[END_REF]:

1. Design time analysis (simulation and verification); 2. Runtime analysis (i.e., process mining, based on the execution logs).

Software tools such as Cactus, ASKALON, GLUE, etc. [START_REF] Taylor | Workflows for e-Science Scientific Workflows for Grids[END_REF] are used for these analysis fields. Mentioned and analyzed current possibilities for this task stage are very limited. Shortcomings of workflow analysis methods and tools are clearly described in [START_REF] Van Der Aalst | BPM and Workflow Analysis[END_REF]. The central criticism is that the requirements analysis stage is applied mainly in a manual manner.

Methods and approaches to considering NFR

Early-phase requirements engineering should address organizational and NFR, while later-phase engineering focuses on completeness, consistency and automated verification of requirements. Not proper dealing with NFR leads to considerable delays in the project and consequently to significant increase of the final costs [START_REF].5 Billion Annually[END_REF]. NFR are considered on design stage and there are several approaches to model NFR within the scope of developed service. NFR framework [START_REF] Chung | Non-Functional Requirements in Software Engineering[END_REF] is a methodology that guides system to accommodate change with replaceable components. Such NFR as security, accuracy, performance and cost are used to drive the overall design process and choosing design alternatives.

KAOS [START_REF] Kaos | [END_REF] is another methodology, considering NFR. It allows requirements engineering, enabling analysts to build requirements models and derive requirements documents from KAOS models.

There are some other approached and methods to NRF modeling [START_REF] Yu | Social Modeling for Requirements Engineering[END_REF][START_REF] Van Lamsweerde | Requirements Engineering: From System Goals to UML Models to Software Specifications[END_REF], but all of them don't consider collaboration between FR 8 and NFR. The legacy software tools, such as NFR-Assistant CASE 9 , ARIS 10 , don't provide functionality to model NRF and consider their influence on system functionality.

BPMN to BPEL transformation strategies

There are various BPMN to BPEL transformation strategies, such as Element-Preservation, Element-Minimization, Structure-Maximization and Structure-Identification [START_REF] Mendling | Transformation Strategies between Block-Oriented and Graph-Oriented Process Modelling Languages[END_REF], Event-Condition-Action-Rules [START_REF] Mendling | On the Transformation of Control Flow between Block-Oriented and Graph-Oriented Process Modeling Languages // IJBPIM[END_REF] and others. A basic idea of mapping which is used in most algorithms of translating BPMN or any other WF-net into BPEL code uses a mix of mentioned strategies. Two categories of tools are applied in practice:

1. BPMN graph is serialized to an XML document. Then the last one is automatically translated into an abstract BPEL document. The abstract BPEL is enriched with the pieces of information, necessary to make it executable. 2. BPMN graph is translated directly into executable BPEL code. This is only possible when input/output files of the future Web Service (WSDL files) are created in advance. 8 Functional requirements 9 Quan Tran "NFR-Assistant: tool support for achieving quality", Application-Specific Systems and Software Engineering and Technology, 1999. ASSET '99. Proceedings. 1999 IEEE Symposium. 10 http://www.softwareag.com/corporate/products/aris_platform/default.asp There are three main problems of BPMN-BPEL translation:

─ fundamental mismatch between these two languages: BPMN is graph-structured notation while BPEL is block-structured language; ─ readability of the resulting BPEL code is very low; ─ translation of extended notations with additional workflow parameters, is not possible.

Hence, development of the method providing automated translation of extended BPMN elements is an important aspect in service development process.

Advanced approach to service development

Proposed advanced approach to future service development includes:

1. novel computational independent workflow design method, focusing on the workflow model and its analysis, allowing to automate service planning stages; 2. NFR balancing method, focusing on collaboration between functional and nonfunctional requirements, allowing to automate service planning stages; 3. modified service workflows transformation method, providing abstract to execution workflows transformation, considering workflows required parameters.

Each of the proposed methods is briefly described below.

Workflow design method

Workflow design includes workflow modeling and simulation. The novel method of workflow design presented in this section is focused on computational independent workflow and consists of the following stages:

─ extended modeling of computational independent workflow; ─ computational independent workflow analysis, including: ─ forming workflow graph and verifying its connectivity; ─ workflow execution time minimization; ─ transformation of workflow to realization diagram.

The suggested method modifies MDA 11 on the business logic level [START_REF] Kot | A novel approach to increase efficiency of OSS/BSS workflow planning and design[END_REF].

Workflow model.

The workflow model is one of the core aspects of the proposed method, allowing its formal description and thus its in-depth analysis and transformation to more finegrained representations. In the following the workflow formalization variant used within our approach is presented.

The mathematical formalization of a workflow can be done by using:

BP = (E, I, P) ( 1
)
where E is the set of workflow identification objects; I is the set of workflow informational objects and P is the set of workflow parameters of service provisioning.

The identification objects {E id, id=1,4 } include:

E 1 = name, E 2 = description, E 3 = executor, E 4 = O -set of works.
The set of workflow informational objects includes income and outcome document and data objects:

I = {I doc in }U{I dat in } U {I doc out }U{I dat out } (2)
The workflow parameters {P i, i=1,6 } cover: P 1 = T ex -execution time; P 2 = R -resource, required for execution; P 3 = А -ability to be automatically executed; P 4 = Sset of subsystems, used for workflow execution; P 5 = F S -set of separate subsystem functions, realizing task execution; P 6 = P ad -set of additional workflow parameters. Separate work models can be represented in a formal manner as:

O = (O, I O , P) ( 3
)
where O is the set of identification objects; I O is the set of informational objects; P is the set of service provision parameters. Identification objects {O id, id=1,3 } include: The proposed model allows to perform workflow analysis at a planning stage, applying graph theory and optimization algorithm, represented below.

O 1 = N o -name; O 2 = d -description; O 3 = E -

Workflow analysis.

The workflow analysis method, providing workflow model verification, execution time minimization and automating its transformation, is briefly described below.

The workflow graph model can be represented as sequential stages, containing a few parallel executed tasks, enabling the definition of execution time as follows:

∑ = k kl kl l ex r T ) ( max ξ (5)
The suggested method of workflow analysis is represented mathematically as:

M = (G f , G V , M min , M tr ) (6)
where G f is the graph generating procedure; G V is the graph connectivity verification; M min is the execution time minimization and M tr is the diagram representing the model to realization transformation. Each of the procedure is described in details in [START_REF] Kot | A novel approach to increase efficiency of OSS/BSS workflow planning and design[END_REF].

Each work of the workflow has one to three implementation variants, defining execution time and resources, the task is to find such implementation variant for each task to minimize the total workflow execution time, when the total resource is limited and known. The objective function of the task is represented below:

∑ ∑ = = k kl kl l r r r M r F kl kl ) ( max min ) ( ξ (7)
It is also necessary to find the implementation variant for each task, i.e. } { , 1,..., , 1,...,

kl r k n l m = =
, where the required minimum of time ( 7) is reached. Finding the function [START_REF] Taylor | Workflows for e-Science Scientific Workflows for Grids[END_REF], applying dynamic programming, is described in [START_REF] Kot | A novel approach to increase efficiency of OSS/BSS workflow planning and design[END_REF].

NFR balancing method

The proposed NFR balancing method is based on creating FR and NFR collaboration model. Implementation of functional requirements is presented by listed FB 13 . Each of FB is responsible for particular logical function. The proposed method includes NFR Catalogue development, FR decomposition, NFR mapping, FB distribution and Balancing stages. NFR balancing method uses NFR Catalogue and FR and create collaboration model between them. The main stages of the concept are described [START_REF] Kot | Method of non-functional requirements balancing when service development[END_REF] and briefly represented below.

Catalogue of NFR. It is proposed to operate with catalogues for performance and serviceability. Catalogues are updated with further operationalizations to keep own NFR catalogues updated, which facilitates reuse of acquired knowledge on NFR.

FR decomposition. It describes influence of services features on NFR. Services and features are depicted for each FB (Table 1). NFR mapping. Each call of FB requests a defined amount of system resources (memory, processor time, etc.) and has list of characteristics: response time, availability, etc. These characteristics are mapped to NFR from catalogue with values, specifying how exact FB meets particular NFR (it is graded from 0 to 100, Table 2). One FB can provide the same functionality with different NFR (FB1.1, FB1.2). From functional point of view there is no difference between these two blocks. The difference is how each FB meets the NFR. NFR mapping requires considering every service and connecting it to required FB, covering requested functionality. Balancing and target models. The target model is obtained by using balancing between NFR and approaches to implementation of a particular functionality with FB. For instance, there is the Customer's demand for service supporting the highest availability and there is no specified requirement for security and performance. Such case can be realized by the model, represented on Fig. 2. A priority is assigned to the requirements, considered during target model development.

Modified service workflows transformation method

The modified method is based on BPD2BPEL translation algorithm [START_REF] Ouyang | From Business Process Models to Process-Oriented Software Systems[END_REF] which can translate arbitrary diagrams into BPEL code. BPMN extension (BPNE) [START_REF] Kot | Applying business process modeling method when telecommunication services development[END_REF] has been taken as an input extended business process diagram.

Key feature of proposed method is modified analysis process. When the element is analyzed, its additional parameters are also checked. If new parameters are found, information about them is saved for their subsequent transformation into BPEL elements. Proposed method considers each BPNE element. BPNE-BPEL transformation tool implements presented BPNE-BPEL transformation method (fig. 4) [START_REF] Pukhkaiev | Globa Translating BPMN/BPNE into BPEL // 11-th International Conference «TCSET'2012». Conference Proceedings[END_REF]. The tool performs transformation of data, extracted from BPNE file, into representation form, convenient for the subsequent work; translation of BPNE elements into BPEL code, using its object-oriented model; gathering all translated elements and components in a single BPEL file.

4.1

Case-study Workflow design. BPMA has been tested during the planning and design of several services, such as «Bonus program», «Selling Electronic Voucher», «Tariff Plan Change» [START_REF] Kot | A novel approach to increase efficiency of OSS/BSS workflow planning and design[END_REF], in the SITRONICS Telecom Solutions company. Testing results have shown that for services, having 1-1.5 months of development time, it can be reduced by 3-5 days and development costs can be decreased by 5-7 man-days for one service; the proposed workflow analysis can reduce the time used for service provision up to 20 seconds for the services, provided in 3-5 minutes by finding the combination of tasks implementation variants, having the same resource limit.

NFR balancing. Evaluation of the proposed NFR balancing method is demonstrated on charging of GPRS service. Its FR decomposition is shown in Table 3. GPRS service availability and service delay are taken as main NFRs. Considering statistical data and enterprise knowledgebase, GPRS service characteristics were estimated (Table 4) and the GPRS service target model (fig. 5) was got. The target model provides service optimal deployment configuration, ensuring service highest availability with minimal delay. The proposed method is experimentally proved to be efficient when services design and deployment, providing NFR modeling, providing service functionality with required functional and non-functional parameters.

Summary and outlook

A novel approach for analyzing and developing modern services, provided by web-oriented applications, has been proposed. The discussion is focused on the development of a computational independent workflow model, its analysis, transformation of abstract into executional workflows, and also aspect of NFR balancing when service development. The proposed workflow model provides formalization of service provision parameters, required for the planning stage. The analysis methods allow automating service planning and minimizing service provision time. The workflow design method reduces the time of system adaptation up to 10% by improving and automating the service planning stage.

The proposed NFR balancing method provides NFR description, considering collaboration between services and meeting NFR by system FB. The method increases efficiency of service development on design and deployment stages and allows fast system reconfiguration on customer demand.

Modified BPMN-BPEL transformation method and tool provides automation of abstract workflows transformation into execution ones, allowing to consider workflow required parameters.

Future work will focus on analysis of computing workflows and their enactment, services monitoring and re-configuration, which are strongly connected to the design and analysis stages. NFR balancing method will be extended with possibility to consider possible change of NFR list and their priorities during different time period (e.g. periods with high load) and also take into account changing priority between services.

Key aspects of the proposed approach to future service development can be applied to extend ISO/IEC/IEEE 29148:2011 Standard, dealing with the processes and products related to the engineering of requirements for systems and software products and services throughout the life cycle, to raise the overall efficiency of service development and re-engineering.

7 =

 7 executor. Task informational objects include income and outcome informational objects (document and data). Set of work parameters {P O i, i=1,7 } include: P O 1 = ξ kl (r kl ) -execution time of work l of stage k; P O 2 = r kl -resource, required for execution work l of stage k; P O 3 = a -the ability to be automatically executed; P O 4 = S -set of OSS/BSS 12 subsystems, used for workflow execution; P O 5 = F S -set of OSS/BSS subsystem functions, realizing works execution; P O 6 = R О n -work realization alternatives, defining execution time and resource values: P ad -set of additional work parameters.

Fig. 1 . 2 .

 12 Fig. 1. Functional blocks distribution Fig. 2. Target deployment model

FB1. 1 FB1. 2 FB

 12 proposed workflow design method is implemented in a new developed tool BPMA14 (fig.3). It uses standard GTK+, Dia diagram editor, PyDia interface, Python Interpreter, PyGTK15 and developed module BPEA, implementing workflow modeling and analysis algorithms. Main BPMA components functions are described further. "Init" realizes Dia and user intercommunication and launches modules functions. "Props" provides setting, changing and saving of workflows and its objects parameters. "Bplyzer" implements time minimization algorithms. "Transform" implements the transformation logic to create a realization diagram from workflow requirements. "Reports" generates reports on workflow modeling and analysis.

Fig. 3 .

 3 Fig. 3. BPMA functioning scheme.

Fig. 4 .

 4 Fig. 4. Structural scheme of the BPNE-BPEL transformation tool

Table 1 .

 1 FR decomposition

	Service	Functional Block	Functional Requirement
	Service1	FB1.1 or FB1.2	FR1, FR2
	Service1	FB2.1 and FB2.2	FR3, FR1
	Service2	FB1.1	FR5, FR6
	Service2	FB3	FR1, FR7

Table 2 .

 2 NFR mapping Using NFR catalogues and FR decomposition, FB distribution can be realized. Fig.1shows that FR 1 and FR 2 from Table1can be implemented either by FB1.1 or FB1.2. The implementation way depends on NFR specification for particular case.

	Functional block/ NFR	Availability	Performance	Security
	FB1.1	90	80	10
	FB1.2	80	70	20
	FB2.1	50	10	10
	FB2.2	5	20	30
	FB distribution.

Table 3 .

 3 FR decomposition of GPRS service

	Service	Functional Block	Functional Requirement
	GPRS	LBS1.1 or LBS1.2	Location Base Charging
	GPRS	RF2.1 and RF2.2	Step Charging
	GPRS	NB3.1 or NB 3.2 or NB3.3.	User notification

Table 4 .

 4 NFR mapping of GPRS service

	Functional block/ NFR	Availability	Delay
	LBS1.1-location based module implemented as	90	80
	internal cache in Online Charging System
	LBS1.2 -external Home Zone Billing -HZB platform	50	10
	RF2.1 -internal Rating	50	20
	RF2.2 -external Rating	5	15
	NB3.1 -notification via SMS	40	50
	NB3.2 -online notification via USSD	50	40
	NB3.3 -offline notification via email	50	10

Non-functional requirements

http://www.omg.org/spec/BPMN/2.0/

UML Activity Diagram

http://www.internet-of-services.com/index.php?id=264

http://erwin.com/products/detail/ca_erwin_process_modeler/

http://www.sparxsystems.com/products/index.html

Business Process Execution Language

Business Process Modeling & Analysis


Joachim Zeiß

Peter Reichl

Jean-Marie Bonnin

Jürgen Dorn
email: juergen.dorn@ec.tuwien.ac.at

DOMINO -An Efficient Algorithm for Policy Definition and Processing in Distributed Environments Based on Atomic Data Structures

Keywords: semantic policies, semantic data abstraction, rule definition, distributed reasoning, mobile reasoning, artificial intelligence

While two decades of semantic web research so far have failed to fulfill the high initial promises and expectations, and the underlying quest for categorizing the world has led to increasing complexity and new levels of bureaucracy instead, in this paper we introduce a new concept for distributed reasoning aiming at simplicity, consistency and computational efficiency. To this end, we propose the DOMINO algorithm, which is based on term logic for realizing an efficient syllogism reasoner. This novel concept is illustrated and evaluated for a context experience sharing system and can be applied in distributed reasoning use cases integrating mobile devices.

Introduction and Motivation

Following Tim Berners-Lee's vision that "a new form of Web content that is meaningful to computers will unleash a revolution of new possibilities" [START_REF] Berners-Lee | The Semantic Web. Feature Article[END_REF], significant research efforts have been undertaken to realize his idea of a "Semantic Web", focusing on converting raw data into information and turning search queries into questionanswer use cases between human and machine. At the same time, Web service architects have integrated semantic web technologies into their API definitions, e.g. WSDL files for finding and collaborating automatically with Web services inside the cloud. However, after two decades of semantic web research, we have to observe that the initial dreams have not come true so far, and have rather turned into increasing complexity and creating yet another level of bureaucracy instead, eventually causing more problems than they intended to solve. Indeed, the somewhat exaggerated desire for categorizing the world has led to a dictatorship of ontologies versus the democracy of folksonomies (currently blooming in Web 2.0), leaving key concepts of artificial intelligence, formal semantics and logic programming unexploited.

In this paper, we argue that, instead of e.g. introducing yet another (graphical) tool or a novel method or procedure for complexity reduction, we better use the powerful rich set of features in a simple way by introducing machine-readable rules which allow devices to act autonomously on behalf of their users. This enables a new way of distributed reasoning with software executing decisions based on user defined policies. More precisely, we aim at simplicity and intuitiveness by allowing users to verbally define their intents with (almost) no predefined vocabulary, only minimal semantic and syntactic requirements, and without the need to explicitly distinguish between conditions and conclusions. At the same time, detecting contradictions and contraries becomes part of the reasoning process and is performed directly while defining policies. Finally, for a given set of policy definitions, the reasoner should be able to run in a browser with reasonable response time, thus guaranteeing sufficient performance.

In order to achieve these goals, we have designed and implemented a reasoning system and language based on (Aristotelian) term logic [START_REF] Glashoff | Computational Aristotelian Term Logic: Introduction[END_REF] which has experienced a revival since the 1970s, mainly due to the constant criticism that predicate logic is unnatural as its syntax does not follow the one used in people's everyday reasoning. Also in the field of artificial intelligence it has gained momentum, e.g. as probabilistic term logic, "Non-Axiomatic Reasoning System" (NARS) or "OpenCog" [7][8]. The remainder of this paper is structured as follows: in Section 2, we provide essential background on term logic and discuss related work. Section 3 presents the DOMINO algorithm for semantic reasoning. Section 4 discusses the application of this approach for a specific use case, i.e. the context experience sharing system KRAMER [START_REF] Szczcerbak | Generalizing Contextual Situations[END_REF]. Section 5 concludes the paper with a brief summary and outlook on future work.

Background and Related Work

Syllogisms and Term-based Logic

The DOMINO reasoning system as described later is based on Aristotelian logic which is composed of the three doctrines of categorical terms, propositions and syllogisms. Here, (categorical) terms are universal concepts like "man", "mammal", "human", "animal", etc. In the following description we will denote these terms with small letters x, y, z etc. (Categorical) propositions are formal sentences combining two different terms, e.g. x and y. There exist four different types of propositions:

• A(x,y): All x are y; e.g.: All man are mammal.

• E(x,y): No x are y; e.g.: No mammal are birds.

• I(x,y): Some x are y; e.g.: Some Austrians are musicians.

• O(x,y): Some x are not y; e.g.: Some mammal are not vegetarians According to the above propositions, we call the x term "subject" and the y term "predicate". A proposition is called "premise" when it is applied to a syllogism for concluding a new proposition. Finally, "(categorical) syllogisms" are rules which allow inferring from a set of propositions (premises) additional propositions (conclusions). For instance, from the premises "All swan are white: A(s,w)" and "No white are raven: E(w,r)", the Aristotelian system will conclude "No swan are raven: E(s,r)".

The corresponding rule is denoted as "A(x,y), E(y,z) → E(x,z)". Aristotle has defined 14 different such rules (the "συλλογισµοι"), see [START_REF] Cohen | Aristotle's Syllogistic[END_REF] for comments on the proofs.

2.2

Computational Syllogism

For implementing these rules, when comparing any two premises, first their terms x, y, z are compared. If any of the terms in one premise matches with a term in the other premise, concluding a new proposition is possible. To this end, it is checked whether the types of the premises match one of the mentioned rules; if yes, the rule is executed to produce a new proposition, which itself can serve as an additional premise, and so on. If a new proposition is already included in the set of existing premises, it is not added as a new premise; the iteration process ends if no new propositions are found. While [START_REF] Glashoff | Computational Aristotelian Term Logic: Introduction[END_REF] describes a computational syllogism web page implemented on a php server, we have implemented our own DOMINO reasoner in pure Javascript. The implementation has a small footprint, does not depend on server side computing and can be run in any browser (even as local html file) or used as a library for W3C or other HTML widgets or apps for the WAC [START_REF] Zeiss | The Role of WAC in the Mobile Apps Ecosystem[END_REF] runtime, the Firefox OS or Google Chrome. Our Javascript code allows detecting contradictions, contraries and sub-contraries to identify misleading ambiguities in premise definitions or conclusions. For the usage of our reasoner, triggers and their namespaces are defined as Javascript functions which are executed if namespace and trigger name match the terms in a concluded proposition.

DOMINO

Basic Idea of the DOMINO Algorithm

We now introduce a novel method for reasoning over data for automated decision making. We call it DOMINO as its basic functionality reminds of the well-known social game where bricks with two numbers on each side are connected to a chain where bricks with equal numbers lay side by side (see Fig. 1). In our DOMINO system, the bricks correspond to term logic premises, where each premise is composed of two terms (subject and predicate). Like with the domino game, bricks are linked according to syllogistic rules [START_REF] Cohen | Aristotle's Syllogistic[END_REF], which can be computed by software [START_REF] Glashoff | Computational Aristotelian Term Logic: Introduction[END_REF].

In principle, DOMINO may use the full set of syllogism rules. However, just like with Horn clauses [START_REF] Horn | On sentences which are true of direct unions of algebras[END_REF], for decision-making based on positive affirmation using a single rule is sufficient, and we therefore restrict ourselves to a well-known rule which is traditionally called "Barbara" and chains propositions which are of type "all" and have the term x in common: A(p,x),A(x,q)→A(p,q). For computation purposes, the terms are represented as strings, and DOMINO checks whether they are matching. Note that matching of two expressions can be defined in different ways, e.g numbers checked for equality or matching strings (as used in [START_REF] Glashoff | Computational Aristotelian Term Logic: Introduction[END_REF]).

In DOMINO, we opt for flexibility and allow numbers to be compared, or being matched with intervals or "<" and ">" relations, while strings could be matched using regular expressions. This also allows pattern matching, a feature no other reasoner of this kind provides as of today. Other matching strategies are conceivable, e.g. for matching date/time expressions and periods. DOMINO also allows executions on conclusion results validating the subject and predicate of a concluded proposition for an existing function to be invoked. The subject of a proposition would hold for the namespace in which a function with the name of the predicate would be executed. Such a function may even inject arbitrarily created new propositions for further com-putation of conclusions. As no duplication of premises is possible, each trigger function routine would be called exactly once. By linking DOMINO bricks all of which include execution triggers, a sequence of function executions can be defined. Alternatively, one does not need to trigger functionality during the computation: instead, once as all possible conclusions have been obtained, one could search for particular expressions and take decisions based on the filtering results. The reasoning process would be performed only once and its results are kept in a cache. The conclusion process is finished if no new (unknown) proposition can be deduced, and the list of all given and conducted proposition is the result set of the reasoning. Summarizing, DOMINO is a computational syllogism system using a subset of term logic figures and conditions to reason over data represented as term logic premises.

The basic exercise of concluding new information out of existing premises is performed by linking the term of one premise with a term of another premise. Two premises may be linked if they have a common term, which computationally is verified by checking if the terms in string format are equal. DOMINO extends this notion of identity also to checking number range and regular expressions, as basically any kind of rule or procedure could be used to declare two terms as being equal. Also multistep comparison is possible, where initially high accuracy strict checking is applied, and if this does not bring the desired result, in a second run comparison checks can be relaxed, to produce a match according to the "Barbara" rule. Another novelty added to DOMINO is the possibility to trigger execution of software routines if new premises are concluded. Note that, while Aristotelian syllogisms are concluding on categories, not on individuals, for pragmatic reasons we do not distinguish between categories and individuals, classes or instances in DOMINO. Thus, the syllogistic terms may lose their philosophical meaning, the validity of conclusions, however, remains.

Formal Description

As we only use premises of type A(p,q) in the sense of "all p are q", we abbreviate this statement to be a simple data tuple t made of the two values p and q as follows:

) , ( ) , ( q p t q p A = ⇔ (1)
Next, we define the conjunction operator " " for the "Barbara" syllogism:

(

Then, let define the initial set of all predefined tuples where none of the tuples in the set has identical p and q values (to avoid indicating mere tautologies which are useless for producing new tuples). This initial set of tuples represents the entire data (facts and rules) of our knowledge base, i.e. all data or information which is already known before starting the reasoning process:

(3) where X is the set of indices related to the tuples. Finally, we define the cardinality of a tuple as being 1 for elements of 0 K :

⊕ ) , ( ) , ( ) , ( ) , ( ) , ( ), , ( q p q x x p q p A q x A x p A = ⊕ ⇔ → 0 K { } X x q p q p K x x x x ∈ ≠ = ; ) , ( 0 if (4)
for all [START_REF] Berners-Lee | The Semantic Web. Feature Article[END_REF] The cardinality of a derived tuple equals the sum of the cardinality of the two tuples on which the derivation is based. As no tuple can be represented twice, always the shortest way to produce tuple t k applies, and the cardinality is thus uniquely defined.

We now define formally the DOMINO algorithm. Starting with 0 K as described in (3), step i of the algorithm uses the elements of B represents all the new information inferred based on set

1 - i K , therefore (7)
and so on for

 , 3 , 2 , 1 = i , until ∅ = i B
. The algorithm converges as 0 K is a finite set and no tuple can be represented twice. Note that the cardinality of a tuple represents its importance in terms of the new information, i.e. newly inferred tuples are considered more important as already existing information. In general, the cardinality n of a tuple is rooted in chaining n-1 other tuples, hence the larger n the more previous information has been condensed to this new piece of information, indicating as well a higher computational effort.

Evaluation Against Triple-Based Reasoning

Defining Horn clauses with DOMINO

With traditional inferring systems, Horn clauses are used to define rules or formulae for computing conclusions. A definite clause has exactly one positive literal, while a clause with no negative literal is called a fact and in propositional logic is expressed as

u t q p ∨ ¬ ∨ ∨ ¬ ∨ ¬ 
, which can also be written in the form of an implication, i.e.

u t q p → ∧ ∧ ∧ ) (  (
meaning: if p, q, ..., t are all true then u must be true as well). Declaration of those rules, e.g. for policy definitions, is based on implications, i.e. "IF-THEN" declarations, quantification and variables. Decision-making is declared by means of logic programming in conjunction with semantic web ontologies. With DOMINO, it is not necessary to define quantifications, and IF-THEN statements become obsolete, as declaring a decision as well as executing a decision process by the reasoner is entirely based on linking DOMINO bricks (like with the social game). While DOMINO is not capable of quantifying variables, it is possible to define rules the same way it is done for Horn clauses in propositional logic, and any Horn clause construct can be expressed as a DOMINO sequence, see Fig. 1. Basically, DOMINO expresses implications by splitting conditions when they are defined, and recombining them when they are evaluated with actual data.

1 ) , ( = = q p t 0 ) , ( K q p ∈ k j k j t t t t + = ⊕  , 2 , 1 ; , 1 = ∈ - i K t t i k j { } X y x K q p K q q K q p q q p B i y y i y x i x y x y y i ∈ ∉ ∧ ∈ ∧ ∈ ∃ = - - - , ; ) , ( ) , ( ) , ( : ) , ( 1 1 1 i i i B K K ∪ = -1
For example, a single condition for buying a product when the price matches 99.90 ("price = 99.9 ⇒ buy") reads with DOMINO as "{(trigger, price), (99.9,buy)}".

When only these tuples are present, no conclusions can be drawn, but if another tuple is added (e.g. by browsing through a database or checking the annotated web page of an online shop) which says "(price, 99.9)", applying the conjunction results in (price, 99.9) ⊕ (99.9, buy) = (price, buy), and we can conclude (trigger, price) ⊕ (price, buy) = (trigger, buy). Hence, upon conclusion of a new tuple, DOMINO checks the namespace "trigger" for a function called "buy" and, if present, will execute it.

which will execute the functions "action1" and "action2" in namespace "trigger". Finally, we would also like to demonstrate how to model Horn clauses for a rule like "if p and q have the same value then do action". The Horn clause reads [START_REF] Cohen | Aristotle's Syllogistic[END_REF] The corresponding DOMINO tuples look like [START_REF] Szczerbak | Collaborative context experience in a phonebook[END_REF] Eventually, the tuples specified in [START_REF] Szczerbak | Collaborative context experience in a phonebook[END_REF]

Declaring decision trees with DOMINO

Although separated in the examples so far, in DOMINO there is no difference between data declarations and defining conditions or implications -it is all about declaring pairs of terms. This generalization or abstraction of facts and rules into a common format allows declaring also complex decision patterns, for example decision trees. The example given in Figure 2 maps to the following DOMINO sequences and can be proved by recursively applying the conjunction operator: (0,1) ⊕ (1,2) = (0,2), (0,2) ⊕ (2,3) = (0,3), (0,3) ⊕ (3,5) = (0,5). (0,1) ⊕ (1,2) = (0,2), (0,2) ⊕ (2,4) = (0,4), (0,4) ⊕ (4,6) = (0,6). (0,1) ⊕ (1,2) = (0,2), (0,2) ⊕ (2,4) = (0,4), (0,4) ⊕ (4,7) = (0,7). (0,1) ⊕ (1,2) = (0,2), (0,2) ⊕ (2,4) = (0,4), (0,4) ⊕ (4,8) = (0,8).

In fact, not only trees but any kind of graph topology can be described. If, e.g. by accident, a graph is created which contains loops, the reasoning process will still come to an end, as each derived tuple is added to the set of existing tuples for reiteration if and only if it does not already exist.

Advantages over Conventional Semantic Reasoning

The advantages of DOMINO over existing reasoning systems based on propositional or first order logic are manifold. As it does rely on term based calculation for its reasoning instead of logical operations, it allows for • human readable data and rule definitions;

• easy integration with tag based systems and hence relating messages and media of different topics down the conclusion chain and defining their informational distance using cardinalities (for example, given T1 containing tags #x and #y, T2 containing tags #y and #z and T3 containing #z and #w, T1 on topic #x would be associated to T3 about topic #w because of T2); • easy integration of pattern matching or any other equality concept (e.g. range checks, probability or similarity statements) into the reasoning algorithm. Furthermore, DOMINO allows for closing knowledge gaps by asking the user simple yes/no questions: tuples that might be worth being combined, as they have a certain cardinality value, can be presented to the user asking if the second value of one tuple can be related to the first value of another tuple. In contrast to reasoners based on predicate logic, DOMINO avoids running into loops, which is especially important when it comes to allowing user-defined rules and reasoning on mobile devices. Finally, DOMINO does not require any special set up or topology descriptions for distributed evaluation of rules. Instead, distributed reasoning becomes as simple as putting tuples together from any data sources. As DOMINO's knowledge base solely consists of tuples and does not distinct between rules and facts, rules may change dynamically based on new data arriving or additional data sources tied in the reasoning process.

Readability of DOMINO Tuples

The human readability of DOMINO tuples relies on the usage of terms and the linking of pairs of terms through the "Barbara" syllogism which is closely related to natural thinking (cf. G. Evan's homophonic theories for semantic investigations [START_REF] Evans | Pronouns, Quantifiers, and Relative Clauses (I)[END_REF]). Consider for instance the information "My availability status is busy" which translates to (my_availability_status, busy). This transition is typical for patterns à la "all a are b", "this is that" or "c has d", e.g. "My house has a door.", "The door is green.", etc. Verbally expressed rules in DOMINO are defined as follows: "Check the eyes. Are they blue? Check hair. Is it blonde? Ask for a date. Check humor. Is it good? Marry this person!" will become (check, eyes), (

, marry!). With data tuples (hair, blonde) and (eyes, blue) the check would result in asking for a date, and with an additional tuple (humor, good), the happy end becomes almost inevitable. Hence, a tuple (1) can be a name-value pair, (2) when inferred/produced it can be a question and answer, and (3) for a rule the left side entry is the expected value of a previous parameter and the right side entry the name of the next parameter to evaluate. Alternatively, hashing the terms of a sentence can produce tuples, e.g.: "Today #Peter was very #happy and the #weather was #nice" leads to (peter, happy), (weather, nice). When interested in special properties, this can be filtered and combined to new tuples. Finally, in formal logic, the word "not" is an operator, while DOMINO does not imply the concept of negation. The semantic relevance of "not" is assigned to the person using it: "Should I buy the house? The wall is green, the roof is pink, do not buy it" is modeled as (should_I_buy_the_house, wall), (green, roof), (pink, do_not_buy_it). With (wall, green) and (roof, pink), DOMINO suggests (should_I_buy_the_house, do_not_buy_the_house), where the way the word "not" is interpreted is up to the user.

Application Example: KRAMER

In [START_REF] Szczerbak | Collaborative context experience in a phonebook[END_REF] a phonebook application has been introduced that provides users with context information about their contacts and notifies them in important situations. This application deploys the so-called KRAMER system, which uses an abstraction process to derive situations where to perform the afore-mentioned notifications by identifying semantic generalizations of user-defined situations that are similar to each another [START_REF] Szczcerbak | Generalizing Contextual Situations[END_REF].

In this chapter we describe how DOMINO can be used to perfectly describe semantic information for decision making in such an environment.

Semantic similarity is defined by two conditions [START_REF] Szczcerbak | Generalizing Contextual Situations[END_REF]: (1) the conceptual graphs of similar situations have to match, and (2) there needs to be a close semantic distance between each other. Both can be easily evaluated with DOMINO by first checking if tuples exist where start nodes and end nodes are comparable for all the graphs. Secondly, due to the substitution process during DOMINO reasoning, these (start-node, end-node) tuples will also be generated if sub-graphs are added or if nodes are linked to each other via several paths. The cardinality of those tuples is used to compare the similarity of these paths. Eventually, we have derived the three taxonomy sets: Expected tuples to be produced are: (me, location) and (me, availability). If these tuples are produced, the sample situations below can be considered to be similar to the concept. These two tuples also express that for the given situation: "I am at location: location and my contact is available for: availability".

A = A 1 ∪ A 2 ∪ A 3 ; L = L 1 ∪ L 2 ; R = R 1 ∪ R 2

Conclusions and Outlook

In this paper we have introduced a new concept for distributed reasoning in mobile networks. Based on term logic, we aim at simplicity, consistency, and computing efficiency. For easy adaptation by users in mobile networks we intend to achieve simplicity and intuitiveness by allowing them to verbally define their intents. We provided a formal description of the algorithm and demonstrated its capability by remodeling standard proposition logic and decision graph concepts. We finally illustrated and evaluated this concept for a context experience sharing system targeted for mobile applications.

K

  to produce a new set of tuples:[START_REF] Glashoff | Computational Aristotelian Term Logic: Introduction[END_REF] Hence, i

Figure 1 :

 1 Figure 1: Domino decision sequence The same principle works for an arbitrary number of conditions. Consider for instance the Horn clause " action2 action1, → = ∧ = ∧ = z r y q x p". This rule will be represented as the following set of DOMINO tuples:[START_REF]Opencog: General Intelligence via Cognitive Synergy[END_REF]

Figure 2 :

 2 Figure 2: Domino decision tree

Figure 3 :

 3 Figure3: KRAMER availability taxonomy (source[START_REF] Szczcerbak | Generalizing Contextual Situations[END_REF]) Fig.3depicts the KRAMER availability taxonomy. With DOMINO, the is-a relationship taxonomy is described in the form of A-type propositions, such that the relationship "x is-a y" is expressed by the proposition "all y are x", giving the DOMINO tuple (y,x). Hence, the relationships denoted in Fig.3result in the DOMINO sets:A 1 = {(any_av, availability), (free, any_av), (occupied, any_av), (busy, any_av), (talk_to_me, free), (doing_nothing, free), (ready_in_a_minute, occupied), (it_may_take_a_while, occupied), (at_a_meeting, busy), (do_not_disturb, busy)}Applying the DOMINO algorithm produces the following tuples with cardinality 2:A 2 = {(at_a_meeting, any_av), (do_not_disturb, any_av),(ready_in_a_minute, any_av), (it_may_take_a_while, any_av), (talk_to_me, any_av), (doing_nothing, any_av), (free, availability), (occupied, availability), (busy, availability)} After one more iteration, the following tuples with cardinality of 3 are produced: A 3 = {(at_a_meeting, availability), (do_not_disturb, availability), (ready_in_a_minute, availability), (it_may_take_a_while, availability), (talk_to_me, availability), (doing_nothing, availability)} For the location taxonomy, the following tuples exist: L 1 = {(any_loc, location), (bistro, any_loc), (bar, any_loc), (office, any_loc), (downtown, any_loc)} We now apply the DOMINO algorithm and get L 2 = {(bistro, location),(bar, location),(office, location),(downtown, location)} The third taxonomy is about relations: R 1 = {(any_rel, relation), (mother, any_rel), (parent, any_rel),(boss, any_rel)} After applying DOMINO yet for another time, we end up with

Figure 4 :

 4 Figure 4: Kramer sample situation concept (source [1]) According to Fig. 4, the concept suggests that the location of the user and the availability of the related contact person should be of interest. In terms of DOMINO: C = {(me, my_availability), (any_av, my_location), (location, my_relation), (relation, con_location), (any_loc, con_availability)} Note that we introduced the identifiers location from the Location taxonomy set L and relation from the Relation taxonomy set R. This allows for any value under location and relation in their related taxonomy trees to be valid.Expected tuples to be produced are: (me, location) and (me, availability). If these tuples are produced, the sample situations below can be considered to be similar to the concept. These two tuples also express that for the given situation: "I am at location: location and my contact is available for: availability".

Table 1 :

 1 Example contact situations (source[START_REF] Szczcerbak | Generalizing Contextual Situations[END_REF]) Now we apply: S i ∪ C ∪ L ∪ R for all the samples, which adds following start-node, stop-node tuples mentioned above to the following situation sample sets:S 1 : (me, bistro), (me, talk_to_me) S 2 : (me, bistro), (me, free) S 3 : (me, bar), (me, doing nothing) S 4 : (me, bistro), (me, downtown) S 5 : (me, office), (me, busy) S 6 : (me, bar), (me, it_may_take_a_while) Observe that S1, S2, S3, S5 and S6 match the concept, whereas S4 does not. The difference becomes more obvious when we also add the availability set A to all S: S 1 : (me, location), (me, availability) // also (me, free) S 2 : (me, location), (me, availability) S 3 : (me, location), (me, availability) // also (me, free) S 4 : (me, location) S 5 : (me, location), (me, availability) S 6 : (me, location), (me, availability) // also (me, occupied)With this final evaluation we come to the same and potentially more granular grouping of situation as the KRAMER system shown in table 2.

			me		contact
		location availability relation	location	availability
	1	bistro	any	mother	any	talk to me
	2	bistro	any	parent	any	free
	3	bar	any	mother	any	doing nothing
	4	bistro	any	mother	downtown	free
	5	office	any	boss	any	busy
	6	bar	any	mother	any	it may take a while
	Taking the exemplary contact situations listed in table 1 [1] gives the DOMINO sets:
	S 1 = {(my_availability, any_av), (my_location, bistro) (my_relation, mother),
	(con_location, any_loc), (con_availability, talk_to_me)}
	S 2 = {(my_availability, any_av), (my_location, bistro) (my_relation, parent),
	(con_location, any_loc),(con_availability, free)}
	S 3 = {(my_availability, any_av), (my_location, bar) (my_relation, mother),
	(con_location, any_loc), (con_availability, doing_nth)}
	S 4 = {(my_availability, any_av), (my_location, bistro) (my_relation, mother),
	(con_location, downtown), (con_availability, free)}

Table 2 :

 2 Kramer semantic grouping (source[START_REF] Szczcerbak | Generalizing Contextual Situations[END_REF])

Summarizing, the DOMINO concept is a novel approach for automated decision making in a distributed mobile environment. The advantages over traditional semantic web or first order logic programming approaches are its simplicity, flexibility and adaptability for verbal human reasoning. As the system is designed for end users, as part of our future work we plan to perform a user study and compare the results with related work in [4,[14][15][16] to show the advantages over predicate logic based systems. We will investigate a simplified modeling of conditional variables and the interpretation of tuple cardinalities as semantic similarity indicators and quantification of information quality. Beyond that, current and future work uses the DOMINO algorithm for various other applications (like, e.g., Location-Aware Campaigning).


Dávid Szabó
email: david.szabo@tmit.bme.hu

András Gulyás
email: gulyas@tmit.bme.hu

Notes on the Topological Consequences of BGP Policy Routing on the Internet AS Topology

Keywords: Network formation games, BGP policy routing, AS level topology

On the Internet AS level topology, BGP policy routing is in charge of dictating the characteristics of routes which can be used for packet transmission. Furthermore the peculiarities of the BGP policies clearly affect the peering strategies of the ISP-s, hereby influencing the emerging topology. This paper takes a first step towards identifying the topological footprint issued by these policies. For this purpose we modify the framework of network formation games to support the most fundamental BGP policy called valley-free routing. We show the topological properties of the equilibrium topologies of this game in an analytical manner.

Introduction

Resembling many of real world networks (e.g. social networks, biological networks etc.), the Internet AS level topology is a complex network exhibiting similar macroscopic features such as power-law degree distribution, high clustering coefficient and logarithmic diameter [START_REF] Fan | Complex networks: small-world, scale-free and beyond[END_REF]. Exploiting this amazing structural resemblance, general complex network models are widely used for generating Internet-like topologies as an input for evaluating Internet related architectures, business models, protocols etc. For obtaining more realistic AS topology models one should incorporate also some microscopic features, which cannot be captured by high level statistics but contribute fundamentally to the final shape of the network.

In this paper we try to grab some of the microscopic features of the AS level topology. First we notice that there is a mutual correspondence between the network topology and the used routing policy. Topology trivially affects routing since one cannot choose routes having edges not contained in the topology. On the other side of the coin, the routing policy can fundamentally influence the topology of the network. For the illustration of this idea consider the simple example on Fig. 1. Clearly if the routing policy is the shortest path policy, then we have to use all the links. If the policy is the "widest path" meaning that we are shooting for the highest bandwidth between the nodes, then the third topology from the left is the appropriate choice. Finally if the policy is the "most reliable path" policy then the corresponding network will be the leftmost topology.

According to our best knowledge, the topological footprint1 of the Internet's routing policy, called the BGP [START_REF] Rekhter | A border gateway protocol 4 (bgp-4)[END_REF] policy routing, are not fully understood and hence not incorporated in the current structural models of the AS level topology2 . Our goal in this paper is therefore to take a first step towards characterizing the topological artifacts imposed by the BGP policies. We show the footprint of the most fundamental BGP policy called valley-free routing on the AS topology in an analytical manner. Since the AS level the topology of the Internet is formed by the business interactions between the ISP-s, such an analysis should be highly incentive-oriented. For this purpose we generalize the concept of Network Formation Games (NFG) and define a network game accommodating the valley-free routing policy. We study the Nash equilibrium topology of this game and characterize its features.

The rest of the paper is organized as follows. In Section 2 we give a brief overview on network formation games and the valley-free routing policy. In Section 3 after modifying the NFG framework to incorporate the valley-free policy, we examine the topological consequences of valley-free routing in an analytical manner. Section 4 discusses our findings and describes future work.

Background

Network Formation Games -Network Formation Games constitute a game theoretic framework which provides considerable insight into the mechanisms that forms the topology of networks [START_REF] Maneva | On a network creation game[END_REF]. In the NFG the players are identified as the nodes of the network, while the strategies of the players is to create some set of links towards an arbitrary subset of the other players. The goal of the players is to minimize their cost function which consists of two parts: link costs and communication costs. The cost function for some player u was originally defined by Fabrikant [START_REF] Maneva | On a network creation game[END_REF] as:

c u = ∀u =v d sh G(s) (u, v) communication costs + α|s u | link costs , u, v ∈ P, (1)
where d sh G(s) (u, v) denotes the length of the shortest path between players u and v on the graph G(s) characterized by the union the strategies of the players, s u stands for the set of nodes towards which u creates links, while α represents the cost of building one edge. Thus the NFG effectively analyzes the trade-off between link costs and communication costs for rational (selfish) players, as the key incentives of building specific topologies. As defined in (1), distance is usually measured as the average length of shortest path from the given node to all other nodes. An important state of the game is called as Nash equilibrium in which no player (node) has anything to gain by unilaterally changing it's strategy. The valley-free routing policy -BGP is the core inter-domain routing protocol of the Internet. It is responsible for distributing available forwarding paths between Autonomous Systems (ASes) and lets each one to choose the path it prefers according to its own special interests. The business relationships of different ASes can be diverse, based on exclusive contracts, service-level agreements and other policy issues. Still we can classify most AS-AS links into basically just two major groups [START_REF] Huston | Interconnection, peering and settlements: Part I[END_REF]: in a customer-provider relationship one AS pays another for forwarding its traffic, while in a peering relationship neighboring ASes voluntarily exchange traffic with each other in a settlement-free manner 3 . In this paper we focus on the topological consequences of the most fundamental policy called valley-free routing [15] [16]. This policy encompasses the basic economic fact that the flow of traffic must obey the flow of cash. The policy dictates that AS A can use a link to a neighboring AS B to route traffic if and only if either the incoming traffic is from a customer or B is a customer of A. All paths that induce valley-free routing have the same preference; the only concern this policy addresses is not violating elemental business rules.

Topological consequences of valley-free routing

For the analysis of the topological footprint generated by valley-free routing we modify the framework of network formation games as follows: Players and valley-free routing -Let P be the a set of players (identified as network nodes) with cardinality N . Recall that the rules of the valley-free policy dictate that a player u can forward traffic originated from player w to a neighboring player v if and only if: (i) the incoming traffic of u is from a customer (in this case the relationship between u and v is indifferent and can be both provider-customer or peering), or (ii) v is customer of u (in this case the type of relationship between w and u becomes indifferent). In other words: after a provider-customer edge or a peer edge, the path can not traverse customerprovider edge or another peer edge. [START_REF] Gao | On inferring autonomous system relationships in the internet[END_REF] Strategies and topology -The strategy space of player u ∈ P is to create some set of undirected edges to other players in the network. The created edges can be of types customer-to-provider (p) and peer (r) edges in accordance with the relationships of the valley-free routing. The r edges are paid at both sides, however p edges are paid by the customer. Note that in some of the following arguments, according to the direction of traversing customer-to-provider links, we may write provider-to-customer link but these terms are referring to the same edge. Thus the complete strategy space of player u is S u = 3 P\{u} , where the number 3 covers the third choice of node u: creating no edge. Let s be a strategy vector containing the strategies of all players hereby representing the current state of the game: s = (s 0 , s 1 , ..., s N -1 ) ∈ (S 0 , S 1 , ..., S N -1 ). Then the graph G(s) = ∪ N -1 i=0 (i × s i ) represents the topology between the players. Payoff -The goal of the players is to minimize their costs. The cost of player u is defined as:

C u = ∀v =u d G(s) (u, v) + ϕ p u p + ϕ r u r , u, v ∈ P (2)
where ϕ x is the cost an edge of type x, u x is the number edges of type x and d G(s) (u, v) is the communication cost between u and v over G(s) given by: d G(s) (u, v) = 0 if valley free path exists between u and v ∞ otherwise.

In what follows we identify the Nash equilibrium of the game in different settings of the parameters. The Nash equilibrium is one of the most fundamental states of a game, because it shows a stable state in which none of the nodes would alter its strategy, though they are rational (selfish) players being interested in their own utility.

Definition 1 (Valley-free footprint (VFF))

A graph is a valley-free footprint if consists of (i) a clique K r comprising peer (r) links only, and (ii) trees rooted at some subset of V (K r ) having customer-to-provider links (p) only, such that the provider in the relationship is always closer to the root than the customer (see Fig. 2). Proof. The proof consists of three parts: first we show that a VFF with |V (K r )| = ϕp ϕr + 1 is a Nash equilibrium, secondly that a VFF with |V (K r )| = ϕp ϕr + 1 is not and finally that a non-VFF topology is also not a Nash equilibrium.

1. The VFF topology with |V (K r )| = ϕp ϕr + 1 is a Nash equilibrium: We show that no player has anything to gain by changing his own strategy if others don't change theirs. Let C u represent the cost of player u residing in the VFF. It is clear that in a VFF every player can reach others through valleyfree paths, hence in the cost functions the communication cost is always zero ( ∀v =u d G(s) (u, v) = 0). Moreover it is clear that any meaningful state of the game permits valley-free paths between arbitrary pairs of players (otherwise the cost of some player would be infinite), so we will omit writing this tag hereafter. (a) if u ∈ K r :

C u = ϕ r u r = ϕ r (|V (K r )| -1) = ϕ r ϕ p ϕ r (4)
If u wants to deviate then it will use some other strategy. In this case the corresponding cost is given by

C u = ϕ r u r , + ϕ p u p , . If u p , ≥ 1 then C u ≤ C u since: C u = ϕ r ϕ p ϕ r ≤ ϕ r ϕ p ϕ r = ϕ p ≤ C u . (5)
If u p , = 0 then again C u ≤ C u since u r ≤ u r , must hold to ensure valley-free connectivity to all other nodes. This is because if u r > u r , then there is at least one node v ∈ K r to whom u is not connected thus cannot be reached from u via valley-free path.

(b) if u / ∈ K r : C u = ϕ p (6)
u p , ≥ 1 is trivially not an option for u since that case immediately implies C u ≤ C u . What remains is the case u , p = 0. In this case to ensure valleyfree connectivity u has to create r edges to all other nodes residing in K r . This would mean C u = ϕ r ( ϕp ϕr + 1), but even then C u < C u :

C u = ϕ p = ϕ r ϕ p ϕ r ≤ ϕ r ϕ p ϕ r ≤ ϕ r ( ϕ p ϕ r + 1) = C u (7)
2. The VFF topology with

|V (K r )| = ϕp ϕr + 1 is NOT a Nash equilibrium: Easily if |V (K r )| < ϕp ϕr + 1,
then any leaf node u from a rooted tree can lower its cost by joining K r as:

C u = ϕ r (|V (K r )| -1) < ϕ r ϕ p ϕ r ≤ ϕ r ϕ p ϕ r = ϕ p = C u (8)
Similarly if |V (K r )| > ϕp ϕr + 1 then some node u ∈ K r can lower its cost by leaving K r and connect to some other w ∈ K r , w = u with a p edge.

C u = ϕ p = ϕ r ϕ p ϕ r ≤ ϕ r ϕ p ϕ r < ϕ r (|V (K r )| -1) = C u (9)
3. Finally we show that graphs differing from VFF can't constitute Nash equilibria. Let G be an arbitrary graph on which the valley-free connectivity is satisfied, i.e., ∀u ∈ G : C u = ∞. It's obvious that without this property G can't constitute a Nash equilibrium. In such graph let u be a node whose strategy differs from the nodes in a VFF. The possible cases are: (a) u has p edge: The strategy of the nodes in the VFF having p edges is to pay for only a single p edge and nothing more (They can have other p edges attached to them but these are paid by their customers, see Fig. 2). Since u differs from this, the corresponding cost function is characterized as:

C u = ϕ p u p + ϕ r u r , u p ≥ 1, u r ≥ 0 : (u p , u r ) = (1, 0). ( 10
)
Now let the edge (u, w) be a p edge of u. Since w can reach every other player via valley-free path, u also has valley-free paths to all others through w. This means that u can delete its edges except the (u, w) edge, giving C u > C u = ϕ p . (b) u doesn't have a p edge: The cost function of u is:

C u = ϕ r u r . (11)
The valley-free connectivity implies that every path from u to others starts with one r edge which can be followed only by provider-tocustomer edges. Let t be the number of nodes having no p edges. Such nodes must be the neighbors of u otherwise u cannot reach them. This imposes u r ≥ t. Furthermore for differing from VFF u r = t must also hold. In summary we get u r > t. In this case u has edges (u, w) where w has a provider. Now these edges can be deleted since u can reach w through its provider too. This gives:

C u = ϕ r u r > ϕ r t = C u (12)
According to Theorem 1 aside from two trivial cases -(i) ϕ p ≥ (n -1)ϕ r , when the Nash equilibria is a tree, and (ii) ϕ r > ϕ p , when the Nash equilibria is a complete graph -the Nash equilibria of our very simple game exhibits some level of structural resemblance with the Internet AS level topology. It is well known, that on the AS level topology there are only a few nodes in the whole network which can reach every other node without purchasing service (i.e. without having a customer-to-provider edge), we call such node a tier-1 (T1). T1s are in a clique having peering agreements with each other, this is the top of the hierarchy. The rest of the nodes are customers of T1s either in a direct or in an indirect way. These topological features are clearly reflected by our results and now we can understand them as a clear consequence of the valley-free policy.

Discussion and future work

In this paper we have taken a first step towards identifying which topological features of the AS level Internet follow from BGP routing policy. We modified the framework of network formation games for support the valley-free routing, which is the most fundamental BGP policy, and defined a new game. We've given a mathematical analysis for the Nash equilibria. For positioning our work we recall that our main motivation is to gain deeper insight into the driving forces forming the topology of the Internet. Since BGP is the core inter-domain routing protocol of the Internet our long-term goal is to identify what topological features this protocol implies. As the first step we have analyzed the topological footprint of its core building block, the valley-free policy, and identified the VFF as its consequence. Meanwhile the topologies produced by our simple model seems promising they are far from being realistic. In the future we plan to broaden the spectrum of BGP policies and investigate the topological consequences of the local preference rule and the effect of the AS pathlength. The in depth analysis of these policies may eventually lead us to more realistic AS level topology generators which may worth the comparison with the existing models as well.

Fig. 1 .

 1 Fig. 1. Policy drives topology: We have three nodes (A, B, C) among which we decide to build a network. The characteristics of the possible edges (A, B), (A, C), (B, C) are defined by a triplet: latency, bandwidth and reliability (l, b, r) (rightmost). Now we have to decide what topology we should build.Clearly if the routing policy is the shortest path policy, then we have to use all the links. If the policy is the "widest path" meaning that we are shooting for the highest bandwidth between the nodes, then the third topology from the left is the appropriate choice. Finally if the policy is the "most reliable path" policy then the corresponding network will be the leftmost topology.

Theorem 1

 1 Every Nash equilibrium of the game is a VFF having |V (K r )| = ϕp ϕr + 1.

Fig. 2 .

 2 Fig. 2. Example for a VFF topology. In such a topology there could be two type of nodes, T1 and none T1. T1s are connected by r edges, which are counted on both sides in the cost function, however p edges are paid only by the customer, who requested it. The flow of cash is visualized by arcs. Conversely there are two possible cost functions: (i) Cu = ϕrur = ϕr(|V (Kr)| -1) and (ii) Cv = ϕp.

Several other aspects (e.g. stability[START_REF] Gao | Inherently safe backup routing with bgp[END_REF], memory requirement[START_REF] Rétvári | Compact policy routing[END_REF], path diversity[START_REF] Arjona-Villicana | The internet's unexploited path diversity[END_REF] etc. ) of BGP policy routing have been analyzed so far.

There are "computational" models[START_REF] Lodhi | Genesis: An agent-based model of interdomain network formation, traffic flow and economics[END_REF][START_REF] Dhamdhere | An agent-based model for the evolution of the internet ecosystem[END_REF] which can generate very realistic AS level topologies based on fully emulating the business decisions of the AS-s fed by complex datasets. Although these models generate considerably realistic networks they can scale only for around a few hundred nodes.

For the sake of simplicity, we omit sibling and backup relationships in this paper.

Acknowledgement This work was partially supported by the European Union and the European Social Fund through project FuturICT.hu (grant no.: TAMOP-4.2.2.C-11/1/KONV-2012-0013).


Patrick Zwickl
email: zwickl@ftw.at

Peter Reichl
email: peter.reichl@telecom-bretagne.eu

Graph-Theoretic Roots of Value Network Quantification

Keywords: Network Economics, Value Networks, Network Interconnection

Value Networks (VN) are gaining increasing importance for the analysis of highly complex business ecosystems. While most of the related work focuses on qualitative aspects, we are mainly interested in developing tools for a quantitative VN analysis. In this paper, we discuss the fundamental relationship between graph theory and VN analysis and outline some of the consequences for the specific use case of network interconnection services.

Introduction

While in the telecommunications industry, tremendous network IP traffic growth rates [START_REF]Cisco Visual Networking Index: Forecast and Methodology[END_REF] are opposed by fading revenues 1 , a proper understanding of inter-firm business relationships has become critical for Network Service Providers (NSPs), especially in the interconnection (IC) business. Tough, the traditionally prevailing sequential description of production activities as value chains is not sufficient for the strategic assessment of such complex business ecosystems anymore. Instead, we aim at capturing the inter-firm perspective through Value Network (VN) analysis [START_REF] Gulati | Strategic Networks[END_REF][3] which focuses on interactions between business entities in networks rather than sequential chains. Orthogonally, the broadly applied intra-firm concept of Business Models has emerged about a decade ago [START_REF] Teece | Business Models, Business Strategy and Innovation[END_REF], and recently has been interlinked with VN concepts [START_REF] Ballon | Business models revisited: the configuration of control and value[END_REF]. In this paper, we thus focus on strategic inter-firm aspects playing a key role in networking IC, while providing proper links to Business Model Design aspects known from literature. While the relatively limited amount of related work on VN analysis [START_REF] Gulati | Strategic Networks[END_REF][6] strongly emphasizes a qualitative approach, we are mainly interested in tools supporting the quantitative analysis of inter-actor value creation. More specifically, this paper outlines the fundamental relationship between graph theory and VN analysis and thus aims at a very general perspective on VN quantification. The remainder of the paper is structured as follows: in Section 2, we briefly review recent advances in quantitative VN analysis, before we describe in Section 3 the concept of Value Network Graphs (VNG) and atomic operations on them. Section 4 out-lines resulting extensions to the basic model, before Section 5 concludes with a brief summary and outlook on future work.

Value Network Quantification

Our general approach for quantifying VN dependencies is depicted in Fig. 1, with three main building blocks: (i) competitive information as input for VN quantification, mainly based on a VN dependency model [START_REF] Zwickl | On the Quantification of Value Networks: A Dependency Model for Interconnection Scenarios[END_REF], (ii) the computation phase which calculates actual dependencies, and (iii) the resulting dependency indicators. In contrast to [START_REF] Zwickl | On the Quantification of Value Networks: A Dependency Model for Interconnection Scenarios[END_REF] which is based on six relevant factors strongly inspired by Porter's "five forces" [START_REF] Porter | How Competitive Forces Shape Strategy[END_REF] and putting them to an inter-firm context, in the present model we aim at an aggregation into two dependency indicators only which are synthesized from and revised over [START_REF] Zwickl | An Instance-based Approach for the Quantitative Assessment of Key Value Network Dependencies[END_REF]. They are derived separately from the bargaining power of suppliers and customers and joined into a final dependency metric afterwards. Computation starts from the utility assessment of potential relationship alternatives, e.g. due to industry rivalry, potential market entrance or substitution. The utility is subject to the fungibility of exchanged resources, which equals the fraction of entities to which a resource could be supplied or sold. Then, the utility for the j-th best alternative for a given relationship of an entity is calculated using exponential spreading factors, which ensures that alternatives with high utility (low j) are picked with higher probability. The revised utilities then feed a Gini-based value distribution coefficient -widely applied in economics -for each entity. In this way, we determine a dependency indicator relative to the maximum Gini coefficient for any outgoing/incoming (to customers/suppliers) relationship. Thus, the dependency quantification shifts towards fine-granular relationship instances, which together reflect an entity's bargaining power of suppliers/customers [START_REF] Zwickl | An Instance-based Approach for the Quantitative Assessment of Key Value Network Dependencies[END_REF]. Furthermore, whenever an entity strongly depends on a single customer/supplier, its relative dependency rises w.r.t. the VN.

While the idea of dependency indicators is built on well-known concepts, it still lacks formal validation of its adequacy. Therefore, in the rest of the paper we provide first steps into this direction, leveraging on graph-theoretic foundations, defining the concept of VN Graphs and discussing their properties as starting point for an axiomatic derivation of basic forces which impact dependency indicators for VN quantification.

Value Network Graphs

In order to be able to create and manipulate graphs representing VNs, we define a Value Network Graph (VNG) as a directed, labeled consistent graph where each node represents an entity of the VN, and each edge corresponds to a business relationship between two entities, whose properties are described by corresponding labels. The following atomic modifications of VNG are considered relevant:

• Addition and deletion of edges or nodes: this is caused by product development and/or stakeholder substitution (→ influence on bargaining powers). • Modification of edges or nodes: this may be caused by the exchange of different resources (→ fungibility), redirection e.g. due to diversification (→ substitution, influence on bargaining powers), entity size changes and market entrance/exit (→ competition, influence bargaining powers, risks). • VNG evolution over time: this results from perspective changes, e.g. due to temporal development of vertical integration. Based on that, we obtain a total of eight forces causing the changes: bargaining power of suppliers, bargaining power of customers, substitution, industry rivalry, market entrance, resource type, entity size, and risks. As these factors seem to have a high influence on the graph representing a VN, we argue that they have to be considered as forces on entities (nodes) also in the inter-firm case of VNs. Nevertheless, following up on [START_REF] Zwickl | An Instance-based Approach for the Quantitative Assessment of Key Value Network Dependencies[END_REF] we see that several forces can be merged to form the mechanism in Fig. 1. Besides that, all factors (not exclusively) arise from atomic edge or node modifications. The resource type dependency (fungibility of resources) may result from modifying the type (e.g., to money) of the edge, as already targeted in [START_REF] Zwickl | On the Quantification of Value Networks: A Dependency Model for Interconnection Scenarios[END_REF][9] based on [START_REF] Biem | A Value Network Model for Strategic Analysis[END_REF]. However, the size of entities has not been sufficiently targeted so far: in the context of economies of scale of Internet services, the size of companies may have considerable influence on their dependency on a VN. Furthermore, risks like e.g. customer ownership, large-scale substitutions, and product evolutions of other entities represent more complex special cases and may have relevant influence on the nature of the graph. Moreover, unmentioned risks like financial risks or unstable business partners may pose dis-utilities for a firm's long-term strategic positioning, while being hardly captured by graph manipulations. The following section will give an outlook on how these missing components can be added to the quantification concept of [7][9].

Revised Dependency Quantification

So far, our graph-theoretic analysis supports the relevance of the six factors identified in [START_REF] Zwickl | On the Quantification of Value Networks: A Dependency Model for Interconnection Scenarios[END_REF] as well as the need for risk and size of entity forces as additional forces. In this chapter we briefly discuss the consequences for the model in [START_REF] Zwickl | An Instance-based Approach for the Quantitative Assessment of Key Value Network Dependencies[END_REF]. As demand-side and supply-side bargaining powers need to be independently assessed, two independent dependency factors are created whose weights may vary from industry to industry, depending on the role of economies of scale. The dependency resulting from entity sizes may best be captured by the worth/volume of resources exchanged with suppliers and customers, i.e., shifts in bargaining powers. Risk forces are more complex to be treated. While low profitability may lead to drop outs or defaults and thus creates risks for business partners, comparable risks may originate from many intrafirm sources and are hardly to be controlled exogenously.

Moreover, entities at larger distances to customers or (raw) materials may especially be prone to spreading risks, i.e., customer ownership is critical. However, such factors spanning multiple nodes may be difficult to be captured by graph modifications, and thus we propose to additionally resort to context-independent risk analysis methods.

There exists a wide range of risk analysis concepts in literature [START_REF] White | Application of system thinking to risk management: a review of the literature[END_REF], however no approach dedicated to network services is available, and thus we have to adapt more generic frameworks like the Composite Risk Index (CRI) for our purpose. Our aim is to construct such an adaptation for the networking industry on the basis of feasible VN crossings with Business Model (BM) design parameters. Likewise to [START_REF] Ballon | Business models revisited: the configuration of control and value[END_REF], we distinguish control parameters (VN parameters, functional architecture parameters) and value parameters (financial model parameters, value proposition parameters), which amongst others cover customer ownership in the VN parameters. From this we derive corresponding risk categories, which are eventually quantified or estimated.

Conclusions and Outlook

Our graph theoretic analysis has largely confirmed VN dependency indicators introduced by [7][9]. By a top-down reorganization originating from the bargaining powers of entities and an integration of context-optimal risk assessment techniques as well as entity sizes as scaling factors, an enhanced and modular quantification system has been derived. The determination of corresponding weighting factors together with the revision of quantification details and practical applications remain for further work.

Figure 1 :

 1 Figure 1: Framework for VN Dependency Quantification

Tellabs: http://www.tellabs.com/markets/tlab_end-of-profit_study.pdf, last accessed: June

26,


Róbert L Szabó
email: szabo.robert@etik.hu

Károly Farkas
email: farkask@hit.bme.hu

A Publish-Subscribe Scheme Based Open Architecture for Crowd-sourcing

Participatory sensing, when a crowd of users collaborate to collect useful information, based applications are getting popular these days thanks to the proliferation of powerful mobile devices. The builtin sensors of smartphones offer an easy and handy way to monitor the environment and collect data which can serve as the basis of smart applications. However, the quick and flexible development and deployment of these applications call for a unifying open architecture. In this paper we propose a publish-subscribe based open participatory sensing architecture.

Introduction

The vision of collecting information by the assistance of the crowd and exploiting its voluntary work has been boosted recently thanks to the emergence of the web and mobile technologies. This is called participatory sensing whose power is that basically everybody has the possibility to contribute on a voluntary basis. In essence, a participatory sensing system enlists and utilizes a crowd of users to collaborate in building a system that is beneficial to the whole community.

The form of participatory sensing has been influenced by the development of technologies. Smart mobile devices open the way for mobile participatory sensing. They do not only serve as the key computing and communication platforms of choice, but also come with a rich set of embedded sensors, such as accelerometer, digital compass, gyroscope, GPS, microphone and camera. Collectively, these sensors are enabling new applications across a wide variety of domains, such as healthcare, social networks, safety, environmental monitoring and transportation [START_REF] Lane | A survey of mobile phone sensing[END_REF]. Thus, mobile smartphones are possible bridges of everyday objects to our enriched world and a plethora of Internet of Things (IoT) applications can be envisioned that will be available in the future through community based sensing and monitoring [START_REF] Ganti | Mobile Crowdsensing: Current State and Future Challenges[END_REF].

Today the development of a participatory sensing application follows the Silo approach. These applications are developed in a stand-alone manner recreating all the necessary building blocks from scratch on both the client and the server/cloud side. This makes the development slow, cumbersome, error-prone and inflexible. On the contrary, instead of the vertically integrated Silo approach our goal is to design a horizontally layered application framework and an open architecture enabling rapid prototyping to experiment with participatory sensing based innovative use-case scenarios. In such a situation, an architecture based on the publish-subscribe (pubsub) communication scheme is well suited where information sources publish events autonomously to the pubsub service whenever something happens. Users can subscribe to event contents and the pubsub service delivers the events to all the interested parties.

In the next section, we propose an XMPP publish subscribe based architecture for mobile participatory sensing.

2 Open Participatory Sensing Architecture

Requirements

Unifying open architecture: A typical participatory sensing application today has two application specific components: i) one at the user's device and ii) another one in the cloud [START_REF] Ganti | Mobile Crowdsensing: Current State and Future Challenges[END_REF]. This results in many parallelism, unnecessary developments and slow application innovation cycle.

We envision that the separation of application logics and some core communication, privacy and trust functions could result in a unifying open architecture where innovation can be done at the end systems focusing on the application and presentation layers. This could boost the developments similarly to the innovation at the application front enabled by IP. Such unifying open architecture shall not only allow independent application development but also the independent development of application support services.

Extensible information model: We want to allow independent application innovation. This can only be done if the middleware can transparently pass extra information which applications may attach to the basic messages.

Decoupling between producers and consumers: If we accept the fact that by participatory sensing we aim at monitoring a larger-scale phenomena that cannot be easily monitored by individuals, then we need to decouple producers and consumers efficiently in space, time and synchronization.

System Model

We propose a generic publish-subscribe interaction scheme with an extensible event language as our system model. The roles in this model are Producers, Service Providers and Consumers. They communicate through event based pubsub nodes as the core service. The model must be easily extensible and support the needs of the basic pubsub operations.

Producers: They are original participatory information sources in our model and are central to a participatory sensing setup. These individuals are actively involved in contributing their sensor data related to a larger-scale phenomena. They produce the raw data to the system.

Service Providers: They would like to introduce extra value to the raw data collected by participatory sensing. Thus, Service Providers add extra value to the information flow from participatory Producers to the Consumers. They might collect (Consumer role), store and analyze Producers' information to produce (Service Provider role) new information. Therefore they might, but not necessarily must, act at the same time as both Service Provider and Consumer. For example, data can be introduced into the participatory application from external systems/sources. If this data is larger in scope what an individual can possibly provide, then we call the associated role as Service Provider.

Consumers: They are the beneficiaries of the information flow. In general, participatory sensing is considered to be an open call for anybody to participate typically on-line in a task. This task can either belong to an owner (e.g., a company seeking solutions to its problem) or to a community or group of users. Nevertheless, the task (collection, analysis and dissemination of data) aims to give value to some beneficiaries or Consumers. Sometimes, these Consumers also act as Producers. When users act on both the Producer and the Consumer side of the process we call them as Prosumers.

Event Service: It realizes the publish-subscribe communication scheme, whereby decoupling Producers (publishers) and Consumers (subscribers) in time, space and synchronization.

Producers create original information by sensing their environment. They publish (marked with empty arrowheads) their information to event nodes (raw information nodes marked with blue). Service Providers subscribe (black arrowheads) to raw event nodes and receive information asynchronously. They combine their information with the participatory sensed data to publish value added information to Consumers. The information they produce are published to different content nodes. Consumers subscribe to content nodes according to their topics of interest and receive information from these nodes asynchronously.

Architecture

Our model can be directly mapped to the Extensible Messaging and Presence Protocol's (XMPP) [START_REF] Saint-Andre | Extensible Messaging and Presence Protocol (XMPP): Core. RFC 6120 (Proposed Standard)[END_REF] publish-subscribe service as follows (see Fig. 1):

A Service Provider creates a raw pubsub data node to collect Producers' data for their services. Producers must have at least publisher-only affiliation to be able to publish into these nodes. This requires either a pre-authorization or an extended access right management at the XMPP side.Similarly to the open node access mode, an open-publish-only node access can be introduced, whereby Consumers can openly publish to the corresponding nodes, but only affiliated Consumers and the owner can retrieve events. Producers with proper access rights can publish (stream) their sensors' data or annotations to these raw data nodes at the XMPP server. Service Providers collect these data by the pubsub subscription service and map their value added services to a structure, which allows reasonable content filtering for their Consumers. Prosumers participate in sensing and publish their sensor data or annotations into some raw XMPP pubsub nodes. Service Providers subscribed to these raw pubsub nodes collect, store and analyze data and derive new information realizing value added services (related to a larger scale phenomena). This information is published into a structured collection of pubsub nodes, to which Consumers (Prosumers) can subscribe. The structure of pubsub service nodes can utilize XMPP's aggregation feature through collection nodes, where a collection node simply receives all events of its child nodes. Note however, that XMPP's collection node cannot filter events throughout the aggregation mechanism, therefore scalable content aggregation can only be realized through the Service Provider role. Such use-case is shown in the figure, where XMPP's aggregations are depicted with dark circles at the container node while empty circles represent only logical containment and intelligent aggregation through the service logic.

Summary

We proposed a horizontally layered, open, participatory sensing architecture based on XMPP's publish-subscribe interaction scheme. We described players and their roles related of the architecture. Use cases and implementation experiments will be shown in the accompanying poster.

Fig

  Fig. XMPP Based Publish-Subscribe Architecture

Acknowledgments: The publication was supported by the T ÁMOP-4.2.2.C-11/1/KONV-2012-0001 project. The project has been supported by the European Union, co-financed by the European Social Fund. This work has been partially supported by the KIC ICTLabs under the activity 13064 CityCrowdSource of the action line Digital Cities. Károly Farkas has been partially supported by the János Bolyai Research Scholarship of the Hungarian Academy of Sciences.