Armin Sharafi
email: armin.sharafi@in.tum.de

Petra Wolf
email: petra.wolf@in.tum.de

Helmut Krcmar
email: krcmar@in.tum.de

Process and data-oriented approach for bundling corporate reporting duties to public authorities -A case study on the example of waste management reporting

Keywords: eGovernment, process bundling, data reuse, reporting duties, bureaucracy costs

Recent bureaucracy cost surveys identify the issue of high financial burdens on government authorities and businesses. These burdens are often caused by a large number of regulations. Therefore, the purpose of process bundling is to redesign Business-to-government processes in a way that eliminates redundant contacts, but still fulfils all reporting duties. The application of our bundling approach shows benefits by replacing similar reporting duties. One possibility to do so is to reuse available data on the business side for numerous duties. This research illustrates an approach for identifying opportunities for data reuse and thus to reduction of bureaucracy costs. The case study applies this approach for environmental reporting duties. After surveying reporting duties in Germany, similar reporting duties with overlaps concerning their content and process were selected. Finally, opportunities for data reuse were derived and implemented.

Introduction

In the fall of 2008, the Federal Statistical Office in Germany identified 9.324 reporting duties between businesses and government in Germany. The expenses on the business side for complying with these duties are measured by using the Standard Cost Model (SCM) [1,[START_REF] Krcmar | Standard Cost Model Manual[END_REF]. The SCM "is designed to measure the administrative consequences for businesses. Today, it is the most widely employed method to do so" [START_REF] Krcmar | Standard Cost Model Manual[END_REF]. According to the SCM report, the German economy is charged with an annually amount of approximately 47.6 billion Euros, with 22.5 billion Euros due to national regulations and approximately 25 billion Euros based on EU-and international regulations [1]. As a result, businesses are dissatisfied with public administrations. They accuse their local as well as national government for being insufficiently transparent and following antiquated structures [START_REF] Rodenhagen | Prozessmanagement im Kontext des E-Government 2.0 -Einsatzfelder, Rahmenbedingungen, und aktuelle Maßnahmen[END_REF]. It is considered indispensable to counteract this appearance by reorganizing current administrative processes [START_REF]E-Government 2.0 -Das Programm des Bundes[END_REF]. Lenk authorities -A case study on the example of waste management reporting for example [START_REF] Lenk | Notwendige Revisionen des Geschäftsprozessdenkens[END_REF] states "without process reorganisation it is impossible for information technology to provide help, regarding quality improvement and more efficiency […]" (translated from German into English). As a prerequisite for efficient eGovernment, process integration therefore attempts to achieve common process objectives like simplifying and speeding up administrative procedures, improving quality, enabling new tasks or the extension of opportunities for democratic participation [START_REF] Lenk | Notwendige Revisionen des Geschäftsprozessdenkens[END_REF]. In order to exploit potentials for modernization, it is necessary to examine underlying processes of Business-to-government (B2G) contacts like reporting duties [START_REF] Becker | Vorgehensmodell zur Selektion von eGovernment-Prozessen[END_REF]. Only focusing on organisation-wide processes can enable aspired customer orientation [START_REF] Beyer | Reengineering[END_REF].

Since process reorganisation and process integration have already proved powerful approaches to improve efficiency in the industry domain, they are also applied to the public administration domain. The goal is to lower bureaucratic expenses, especially for businesses. Therefore, we analysed the area of environment reporting duties in order to identify B2G-process structures which might benefit from process. This led us to the following research question: What different types of reporting duties exist in the area of waste disposal management and how can they be bundled? At the same time, the underlying processes will not be modified in their nature. The intention of the process bundle construction can be summarized by contributing to the public welfare (lower bureaucracy costs), improving transparency and protecting the environment from unnecessary pollution.

The paper is structured as follows: Chapter two describes the approach for B2Gprocess analysis and process redesign. Afterwards, chapter three introduces the application domain environment by giving some facts about the waste disposal sector and illustrating three environmental reporting duties: the German electronic waste notification system (eANV), the electronic pollutant release-and transfer register (E-PRTR) and the environmental statistic report. We propose these processes for bundling. Chapter four illustrates the application of the approach in the investigated domain is described. The emphasis is on the content and the data flow between businesses and administration. At the end of this section we show, how the three processes can be bundled by reusing reporting data generated in one process. In section five and six, our findings are discussed and implications for further research are derived.

Method and Approach

We conducted a case study on environmental reporting duties of companies. This was done to identify groups of processes, which might be suitable for bundling. The aim is to provide a more efficient way of reporting a specific type of environment data to government. For being able to decide on "bundling candidates", it was essential to define how B2G processes should be integrated. Based on the assumption that there are many groups of similar reporting duties -referring to the data being reportedcriteria for bundling were chosen to measure similarity of reporting duties. This includes their structure and data content.

The applied approach adopts basic ideas and principles from well-established models used for business process management and reengineering within the industry sector [START_REF] Gaitanides | Prozessorganisation -Entwicklung, Ansätze und Programme des Managements von Geschäftsprozessen[END_REF] [9] [START_REF] Geier | Optimierung der Informationstechnologie bei BPR-Projekten[END_REF]. Each approach aims at integrating processes and is mostly composed of four steps. Gaitanides [START_REF] Gaitanides | Prozessorganisation -Entwicklung, Ansätze und Programme des Managements von Geschäftsprozessen[END_REF] distinguishes between the steps process identification, process analysis, process design and process implementation. He describes the objectives of a goal-oriented management of the value-added chain (process bundle) regarding quality, time, costs and customer satisfaction. Geier [START_REF] Geier | Optimierung der Informationstechnologie bei BPR-Projekten[END_REF] illustrates his procedure model by enumerating the steps determination of project objectives and content, analysis of the current situation, development of a target concept and implementation. Becker et al. [START_REF] Becker | Prozessmanagement[END_REF] try to improve the existing process organisation constantly and incrementally through their concept of "Continuous Process Management". This concept is organized through a cyclic arrangement of its sub processes executing phase, analysis, goal-redefinition phase, modelling phase and business process reengineering phase [START_REF] Becker | Prozessmanagement[END_REF]. To sum up, first the approaches aim at identifying relevant processes as input for further detailed analysis. The process analysis achieves a more detailed structuring of the main process by identifying subprocesses. The following step attains a target concept or design of a new process bundle. This is built up from the examined single processes by meeting the main reengineering goals like e.g. improvement of the chronological and logical order. The step implementation gives advice how to realize the desired construction [START_REF] Schulze | Bürokratie-und Regulierungskosten in der chemischen Industrie -Potenziale zu ihrer Reduktion. Verband der chemischen Industrie[END_REF].

Following the illustrated approaches, we identified basic structures of each model and designed an analysis approach. It is customized for its application to domains, which are characterized by a high number of reporting duties (e.g. environment). The approach is structured as follows (see Fig. 1) [START_REF] Wolf | Machbarkeitsstudie Prozessketten Umwelt[END_REF]: Fig. 1. Process model for process redesign for reporting data reuse (Source: own illustration based on [START_REF] Wolf | Machbarkeitsstudie Prozessketten Umwelt[END_REF])

The derived approach consists of four successive steps. Firstly, it is necessary to define and to analyse the environment of the considered domain (Domain Analysis). Results are B2G processes, which might benefit from bundling. In the second step, selected processes have to be analysed in detail (Process Analysis). This is carried out to prove how they might be redesigned to achieve a more efficient state. Step three points out the issue to redesign processes in order to reuse reporting data (Process Redesign). In the final step, it is important to evaluate the potential benefit of the redesigned process (Multidimensional Cost-Benefit Analysis). Details of the individual steps are described in the course of the following case study. 3 Application Domain Environment

Industry Sector Waste Disposal

This chapter gives some facts to get in touch with the domain waste disposal in Germany. Today, the waste disposal sector covers about 240.000 employees and a volume of about 50 billion Euro [START_REF] Viola | Behörden und Unternehmen entlasten -Bürokratiekosten senken[END_REF]. Since year 2000, the quantity of dangerous waste raised from 15 to 20 million tons a year. Therefore, 250.000 companies and 320 authorities create and deal with round about 10.000 records of proper waste management, 3 million data sheets and 14 million dock receipts concerning the waste notification system [START_REF] Viola | Behörden und Unternehmen entlasten -Bürokratiekosten senken[END_REF]. According to the Federal Statistical Office, 214 reporting duties were identified, including the identified processes in the Domain Analysis, concerning the industrial sector "wastewater, waste and miscellaneous waste disposal" [14]. Through a detailed consideration of each duty regarding corresponding bureaucracy, it is possible to allocate specific costs to 177 reporting duties. Summed up, these processes cause bureaucracy costs of 176,947 million Euro [14]. This amount demonstrates the relevance to measure cost reduction. After a brief explanation of 3 processes analysed in our case study, the Process Analysis explores the listed processes in more detail. The goal is to identify concrete links as possibilities to combine them to integrated process bundles [START_REF] Wolf | Machbarkeitsstudie Prozessketten Umwelt[END_REF].

German Electronic Notification System (eANV)

All involved actors (producer and transporter of waste, waste disposal contractor, authority) have to fill out the "waste data sheet". Besides data about type and quantity of waste, it also contains further data about participating waste disposal partners and the actual transaction [15]. This includes the collection, transport and disposal of waste with an obligation to keep records for the disposal of dangerous waste [START_REF]Zentale Koordinierungsstelle der Länder[END_REF]. So, every involved actor has to keep certain regulations which dictate to create, complete or store corresponding waste data sheets [15]. According to this, many procedures seem to appear regularly with almost the same task. The content of the forms is quite similar, although there are different formats (paper based forms etc.), levels of detail and partially different addressees. The electronic waste notification system (eANV) will soon be introduced in Germany (legislative basis § 45 Abs. 2 KrW-/AbfG). The currently non-automated procedure of the waste notification system often causes redundancies, inconsistencies concerning the data collection and as a result avoidable administrative costs. In order to reduce the appearing paper logistics, eANV aims at substituting paper forms through an electronic way of data registration. The technical infrastructure for running eANV is provided through a central platform. It enables a uniform nationwide data exchange between all involved actors [START_REF]Zentale Koordinierungsstelle der Länder[END_REF]. This will contribute to improvements of the organisation of the nationwide waste disposal and to reduce data exchange efforts [START_REF]Abfallüberwachungssystem ASYS[END_REF].

E-PRTR

The aim of the introduction of the European Pollutant Release and Transfer Register (E-PRTR) is to contribute to transparency and public participation in environmental decision-making [START_REF][END_REF]. The E-PRTR contains important environmental data from industrial facilities within the EU. It replaces and improves upon the previous European Pollutant Emission Register (EPER). The new register contains data, annually reported by some 24.000 industrial facilities covering 65 economic activities across Europe, including several industry sectors like waste and waste water management [START_REF][END_REF]. Each facility which fulfils certain criteria (e.g. exceedance of determined threshold values) has to report to E-PRTR including data about the amounts of pollutant releases to air, water and land as well as off-site transfers of waste and of pollutants in waste water from a list of 91 key pollutants. Data are mostly reported annually by the respective facility to responsible authorities [START_REF][END_REF]. The technical support is a nationally data acquisition software (BUBE), which is used by the operator to transfer reportable data online to PRTR, followed by automated transmission [19]. This reporting duty is important for our considerations, because waste producers and waste disposal contractors have to notify type and amount of waste.

Environmental Statistic Report Waste Disposal

According to the German environmental law (UStatG) § 1, statistics have to be raised for purposes of environmental policies and fulfilling European and international reporting duties. UStatG § 2 demands for statistics which include inquiries about waste disposal, waste which has to be proved for disposal, disposal of certain waste (UStatG § 5), etc. Especially concerning the waste disposal, § 3 paragraph 1 registers data from involved facilities requiring admissions for disposing waste. That is why for example type, amount, nature and origin of the handled waste have to be reported every year. Number, type and location of the facility have to be reported every two years to the responsible authority. The same companies (waste producers and waste disposal contractors) are obliged to report. This is just a small excerpt of the UStatG to display the content of the considered law and its resulting reporting duties [START_REF] Wolf | Machbarkeitsstudie Prozessketten Umwelt[END_REF]. In order to enable electronic processing of reporting duties, the need for an online-available reporting system arised. Therefore, the eSTATISTIC.core system was built up in 2005, developed by national statistical agencies. It provides the possibility for companies and authorities to report automatically data online [START_REF]eSTATISTIK.core[END_REF].

Application of the Analysis Approach

The following sections describe the four phases of the approach in detail as well as its application in our use case. authorities -A case study on the example of waste management reporting

Domain Analysis

The development of the Domain Analysis was inspired by the Needs Driven Approach (NDA) [START_REF] Schwabe | Piloting Socio-Technical Innovation[END_REF]. NDA aims at analysing and representing collaboration, for example by identifying involved actors, interactions, tasks or examining legislative frameworks, work processes, used tools or data storages [START_REF] Schwabe | Piloting Socio-Technical Innovation[END_REF]. In this case, the NDA is used to collect B2G contacts in the domain environment. This is required to identify similar reporting duties as a basis for bundling. The Domain Analysis is important, because following steps are based on its results [START_REF] Krallmann | Systemanalyse im Unternehmen[END_REF]. In order to identify domain knowledge within the Domain Analysis, a feasibility study [START_REF] Wolf | Machbarkeitsstudie Prozessketten Umwelt[END_REF] developed an approach to identify and collect reporting duties and B2G processes. This includes the completion of four steps called task analysis, (high-level) work process analysis, interaction analysis and selection of candidates for the process analysis [START_REF] Wolf | Machbarkeitsstudie Prozessketten Umwelt[END_REF].

First of all, the task analysis delimits the field of investigation and identifies reporting duties. Therefore, we studied legislative specifications concerning information and licensing requirements related to environmental protection or environmental authorities. To gain necessary domain knowledge, we used sources like process descriptions (e.g. eGovernment sites), legal documents (e.g. reporting forms) and regulations (e.g. government service catalogues), organisational and task plans, workflow diagrams, descriptions of the IT architecture as well as reports concerning the fulfilment of the designated reporting duties. The result is a list of B2G processes.

In the course of the work process analysis, we categorized identified B2G processes according to their structure or process type (reports, applications, data requests). Further, they were classified referring to their content -i.e. type of substance being reported on (e.g. waste, waste water) and object of reporting (e.g. quantity, pollutants) -on the basis of a domain model for environment compliance [START_REF] Krcmar | Informationssysteme für das Umweltmanagement -Das Referenzmodell ECO-Integral[END_REF]. Finally, we ended up with a systematized composition of the investigated processes.

Thirdly, the interaction analysis aims at identifying all actors involved in a B2G contact. It is based on the analysis of documents, especially legislative specifications and forms used in the domain environment.

Step four, the selection of candidates for the Process Analysis, uses previous results to select suitable bundling candidates for the design of efficient eGovernment processes. All processes are filtered according to certain attributes (similarity of actors and structure), until a set of processes remains [START_REF] Wolf | Analyse und Design von Prozessketten. Fachtagung Verwaltungsinformatik (FTVI)[END_REF].

At the beginning of the research, relevant data about the regarded domain were collected. Relevant in this case are e.g. involved actors on the business side, involved authorities, data to be supplied by the business side, type and frequency of reporting duty, medium, interface and information system for data transfer, legal basis and bureaucracy costs of analysed B2G reporting duties. The collection of relevant data is often difficult, because sub-processes are mostly supported by different IT-systems with different actors and institutions involved in the process. Additionally, most information sources are not digital. That's why problems concerning format inconsistencies occur [START_REF] Becker | Prozessmanagement[END_REF].

According to the analysis phase of the "Continuous Process Management" process [START_REF] Becker | Prozessmanagement[END_REF], collection of required information includes three steps: Firstly, data sources for domain information need to be identified, accompanied by the provision of a corresponding access to the implied information. Secondly, gathered data has to be prepared for its syntactical suitability, for example, to obtain a common data format (e.g. XML). The last step proves the semantic correctness of the collected information. This is done to get an information base, which is suitable for following process evaluation [START_REF] Becker | Prozessmanagement[END_REF]. As a result, the analysis in the field of environment identified 339 processes between business and administration [24]. The structured collection of these processes in a process data library allowed us to select processes for bundling by means of specific criteria (e.g. common laws, involved actors) [START_REF] Wolf | Analyse und Design von Prozessketten. Fachtagung Verwaltungsinformatik (FTVI)[END_REF]. Fig. 2 represents a part of the library.

Fig. 2. Process data library -part of the resulting list through the Domain Analysis

(Source: own illustration according to [START_REF] Wolf | Machbarkeitsstudie Prozessketten Umwelt[END_REF])

By using these criteria, it was possible to form groups with content-related similarities. Those similarities can occur e.g. in form of concerned type of substance, involved actors or corresponding reporting period etc. The largest group -referring to the type of substance to be reported on -turned out to be reporting duties concerning the waste disposal management sector. Three of them deal with type and quantity of waste and are therefore similar in their content. All characteristics mentioned before help to determine a pre-selection of processes. Analogies regarding the classification through certain criteria, like type of substance or regulations by law as well as the consideration of the results of a document analysis, result in a small variety of adequate process bundling candidates. This includes eANV, E-PRTR as well as environmental statistic report.

Process Analysis

The Process Analysis investigates selected processes. The purpose is to reveal possibilities for their integration towards desired process bundles. This step is also

Involved actors (business) Involved actors (government) Classification

based on principles of the NDA, e. g. by performing (detailed) work processes and tools employed [START_REF] Schwabe | Piloting Socio-Technical Innovation[END_REF]. In addition, the Process Analysis uses the concept of standardized data profiles to enable a structured procedure. This allows an examination of regarded processes according to predefined characteristics.

The (detailed) work process analysis aims at identifying starting points and requirements for the integration towards process bundles through a detailed functional description. Techniques used for that purposes are interviews and business process analysis with a functional as-is profile. At the same time, the process costs are analysed according to the SCM model. Besides this, the degree of routine (number of possible appearances) and the complexity concerning the number of possible variants or length of the process will be recorded.

The analysis of the used tools identifies the current IT support including the analysis of interfaces for data exchange as well as transport protocols and data formats. Information required for the Process Analysis comes from legal regulations, public documents, product and system descriptions, interfaces specifications and interviews [START_REF] Wolf | Machbarkeitsstudie Prozessketten Umwelt[END_REF]. Detailed descriptions of processes form the starting point for the following construction of process bundles. Identified processes are analysed regarding their organisational, technical and legal characteristics to derive bundling requirements. The outcome of the Process Analysis consists of three current state profiles. Their investigation (concerning possibilities for connecting them by comparing attributes) ends in a target state profile. The functional conception explores factual requirements, whereas the technical conception examines relevant criteria out of the field information and communication technology [START_REF] Wolf | Machbarkeitsstudie Prozessketten Umwelt[END_REF].

Process Redesign for reporting data reuse

The proposed procedure of redesigning is inspired by the well-established "Structured Analysis" by DeMarco [START_REF] Demarco | Structured Analysis and System Specification[END_REF] which contains methods for an analysis of systems. Comparable approaches exist by Ross and Schomann [START_REF] Ross | Structured analysis for requirements definition[END_REF] or Mac Menamin [START_REF] Macmenamin | Strukturierte Systemanalyse[END_REF]. Following their guidelines, the current state of a system has to be raised through an analysis of existing processes and systems first. Secondly, necessary changes have to be defined to develop the desired model [START_REF] Demarco | Structured Analysis and System Specification[END_REF]. The goal is to replace the redundancy of reporting duties through the reuse of available data. According to [START_REF] Jurisch | Toward a formal approach to process bunding in public administrations[END_REF], process bundling is concerned with changing or redirecting flow of data between activities without changing the actual content of the data.

Every facility producing or dealing with dangerous industrial waste has to report data according to the eANV, PRTR and environmental statistic report waste disposal to the responsible authority (see Fig. 3). The linkage between environmental statistic report waste disposal and eANV takes place through aggregation of reportable data, involved actors which occur in form of the waste disposal contractor and content of the reportable data. The combination of PRTR and the statistic report waste disposal can also be implemented through aggregation of reportable data, involved actors in form of waste producer and waste disposal contractor and content of the report. From the functional point of view, the realization of the process redesign intends to automatically accumulate data. Fig. 3. Three reporting duties of companies (Source: own illustration) Fig. 4 illustrates the data flow between eANV, PRTR and statistical reports as well as the integrated data flow between all involved actors. This BPMN process model shows the combined and integrated overall process. The data of the verification conducted on hazardous waste (eANV) report is used to generate the PRTR report of the producer and the waste disposal contractor. The eANV data are also used for the preparation of statistical reports of both actors. All reports will then be sent in a further step to the appropriate authority. The goal of the design of the technical implementation is to provide as much support as possible for the economy to fulfil reporting tasks demanded by government. Finally, the benefit of bundling is analysed by the use of the Multidimensional Cost-Benefit Analysis. The objectives of the procedure are summarized as reduction of the administrative expense for businesses as well as improvement of data quality. The process bundling simplifies the procedure of reporting data to responsible authorities. Actually, different reporting duties with similar content are often processed in different divisions of a company. This separate processing of data leads to unsatisfactory results in the form of inconsistent reports and resulting contradictions. Through reuse of data, reliability of reported data will be improved and fault rates reduced. Although SCM is not able to give evidence about the detailed saving potential, according to estimations of experts, the proposed approach will pay off. Therefore, it is qualified to reduce bureaucracy costs. But a point of criticism concerning the SCM is that it is not a method to calculate actual administrative costs, but rather delivers estimates, using mean values. So, highly efficient or inefficient procedures will not be taken into account. As a result, the appliance of the SCM can provide distorted results [START_REF] Den Butter | The Transaction Costs Perspective on Costs And Benefits of Government Regulation[END_REF]. To obtain actual data, it is necessary to perform benchmarks including all companies [START_REF]4Z2qZpnO2Yuq2Z6gpJCEfHx9fGym162epYbg2c[END_REF]. Furthermore, there is no statement expressed about the benefit but about costs [START_REF] Slodowicz | Verwendungsmöglichkeiten des Standard-Kosten-Modells -Eine Analyse des schweizerischen Kontexts[END_REF].

Conclusion

Companies suffer from high bureaucracy costs incurred by reporting duties to authorities. This paper describes the application of an approach for process bundling, in order to reduce efforts for businesses. The main target in this case was to bundle several individual processes by reusing reporting data. The application of the approach is illustrated in form of a case study. It is based on and developed by the consideration of common principles of process management and reengineering. The appliance in the selected domain demonstrates a way to reduce bureaucracy costs, as well as to achieve common eGovernment objectives. Individual processes were integrated, which provides advantages such as reduced costs, transparency and higher efficiency. The appliance of the approach in this case was possible because of many overlaps between reporting duties. First, we conducted a Domain Analysis to identify reporting duties in the domain and to filter relevant and similar ones for bundling. The next step (Process Analysis) explored selected processes in detail according to defined characteristics. Then, suitable reporting duties are redesigned with the goal to replace redundancies of reporting duties through the multiple use of available data (Process Bundle Determination). Finally, we evaluated the benefit of the reporting duty bundle to derive the potential of the combined process. The use of the approach also showed the necessity for iterative customizations to meet the requirements of the domain. We identified three reporting duties dealing with data about waste and consolidated them into one integrated process. This illustrates potential to contribute to the reduction of bureaucracy costs.

Outlook

Despite of some restrictive factors (application of the approach in only one domain), the model represents its potential by the combination of several suitable processes in order to reduce bureaucracy costs. This is getting more and more important to consolidate public finance and to improve the capacity to act through more flexibility [START_REF]E-Government 2.0 -Das Programm des Bundes[END_REF]. Since the approach has been applied in the domain environment, the applicability in other areas is not verified yet. This is necessary to draw conclusions about the generalization of the approach. The applicability of the model has to be examined in terms of e.g. simplicity and quality. For that matter it is required to consider which criteria may be used for a bundling of processes. Likewise, it is important to elicit which procedure is applicable to derive process criteria and their relationships for the regarded domain. Furthermore, feasibility of integrated processes as a result of the approach has to be examined. This also applies to potential savings indicated in this paper. Last but not least, it is sensible to review the completeness of the approach. Therefore further research is planned to implement a bundle of reporting duties between business and administration.

Fig. 4 .

 4 Fig. 4. Target process bundle PRTR -eANV -environmental statistic report (Source: own illustration according to [12])

No. Processes domain environment Legislative basis name of process/ reporting duty type (request/re- port/no- tification) type of substance object producer transporter waste disposal contractor Licensing authority waste Licensing authority facility State Office for Statistics

		waste report to
		PRTR (Pollutant							European PRTR
	34	Release and			quantity,	x		x	x	Regulation (E-
		Transfer			type of				PRTR-VO
		Register)	report	waste	waste				VO 166/2006 EU)
									German
	89	environmental statistic report			quantity, type of			x	x	Environmental Statistical
		waste disposal report	waste	waste				Law(UStatG)
									Ordinance on
		verification							Waste Recovery
	239	about the disposal of			quantity,	x	x	x	x	and Disposal Records
		(dangerous)			type of				(Nachweisverord
		waste	notifiation waste	waste				nung -NachwV)

Process and data-oriented approach for bundling corporate reporting duties to public

Process and data-oriented approach for bundling corporate reporting duties to public authorities -A case study on the example of waste management reporting

Process and data-oriented approach for bundling corporate reporting duties to public authorities -A case study on the example of waste management reporting

Acknowledgments. We would like to thank the German Federal Ministry of the Interior for their support and funding of the research project.


Stein Desmet
email: stein.desmet@intec.ugent.be

Bruno Volckaert

Filip De Turck

Autonomous Resource-Aware Scheduling of Large-Scale Media Workflows

Keywords:

The media processing and distribution industry generally requires considerable resources to be able to execute the various tasks and workflows that constitute their business processes. The latter processes are often tied to critical constraints such as strict deadlines. A key issue herein is how to efficiently use the available computational, storage and network resources to be able to cope with the high work load. Optimizing resource usage is not only vital to scalability, but also to the level of QoS (e.g. responsiveness or prioritization) that can be provided. We designed an autonomous platform for scheduling and workflow-to-resource assignment, taking into account the different requirements and constraints. This paper presents the workflow scheduling algorithms, which consider the state and characteristics of the resources (computational, network and storage). The performance of these algorithms is presented in detail in the context of a European media processing and distribution use-case.

Introduction

In the audiovisual industry, the resources required to perform various tasks such as editing and processing of video and audio, are generally quite considerable, not to mention expensive. This is not only true for computational resources but for storage resource and communication resources as well. Converting video material from one format to another can easily take several hours, even on today's multi-core servers. Raw Standard Definition material used during the editing process has bitrates of 60Mbps or more, while HD material easily quadruples these bitrates. This obviously creates high demands on storage and network. Especially for independent film makers, these resource requirements and their cost might pose an obstacle.

The Independent Films In Progress (IFIP) [START_REF]IBBT: Independent films in progress (IFIP)[END_REF] project designs a platform aimed at the media industry, especially the independent film. Its goal is to provide a framework supporting the development of independent productions. Amongst others, it provides a platform for users to automate and submit production processes. The platform offers the possibility for users to submit a series of tasks -e.g. video transcoding or CGI rendering -or workflows they want to be executed within a certain budget and timeframe. The platform autonomously locates appropriate resources for the execution of these workflows, and determines the most appropriate start time of the workflows, taking all their constraints Fig. 1. Overview of the IFIP platform. The scheduler locates resources for the workflows submitted at the portal, and launches them at an appropriate time.

into account. This is illustrated in Figure 1. A user submits a workflow at the IFIP portal, which forwards the flow to the scheduler. The scheduler examines the workflow and the user's constraints defined in the metadata. For each task in the workflow, the scheduler locates resources hosting the required services or applications -taking into account both the user's demands and the current state of the infrastructure -and adds the task-to-resource mapping to the workflow description. Additionally, an optimal starttime for the workflow is determined as well. At that starttime, the scheduler submits the workflow description to the workflow engine, which subsequently executes the workflow.

Considering such a multi-client distributed media processing platform, an efficient allocation of all resources -computational, storage and communication -is of the utmost importance for being able to meet the users' requirements and offer high Quality-of-Service such as responsiveness or budget considerations. Efficient resource usage also results in the ability to handle higher loads. This optimal resource selection is not only location-based (which resource to use), but also time-based (when to use the resource). This scheduling problem is known to be NP-hard [START_REF] Garey | Computers and Intractability : A Guide to the Theory of NP-Completeness[END_REF]. There is already a substantial amount of research on the topic of scheduling tasks in grids and other heterogeneous distributed environments [START_REF] Yu | Workflow scheduling algorithms for grid computing[END_REF][START_REF] Dong | Scheduling algorithms for grid computing: State of the art and open problems[END_REF][START_REF] Kwok | Static scheduling algorithms for allocating directed task graphs to multiprocessors[END_REF].

However, media-oriented cases, including the one presented here, have specific, highly data-intensive and time-constrained demands, to which the workflowto-resource mapping must be specifically tuned. The network in a media environment for example requires special consideration. Due to typical network packet patterns inherent to media transfers, media traffic turns out to behave differently from regular IT traffic. This makes unreliable throughput, packet loss and lost connections due to oversubscription far more likely than in normal situations [START_REF] Andries | Facing media traffic challenges[END_REF][START_REF]IBBT: Grid enabled infrastructure for service oriented high definition media applications (GEISHA[END_REF].

The MediaGrid framework (and accompanying MediaNSG simulator) [START_REF] Volckaert | Gridification of collaborative audiovisual organizations through the mediagrid framework[END_REF] is aimed at employing grid technology in a media production and distribution environment. The IFIP project builds further on this framework, and the research work performed for the GEISHA project [START_REF]IBBT: Grid enabled infrastructure for service oriented high definition media applications (GEISHA[END_REF], the predecessor to the IFIP project. The GEISHA project focused on the actual implementation of a service oriented architecture in media grids, and the associated challenges.

The research project GridCast [START_REF] Harmer | Gridcast-a next generation broadcast infrastructure?[END_REF] is undertaken by the British Broadcasting Company (BBC) and the Belfast e-Science Center, and also aimed at developing a media grid. However, it is intended on the specific BBC topology, whereas we aim to provide a general framework. Furthermore, scheduling in GridCast is mainly focused on scheduling data transfers only.

Another project aimed at media oriented grids is MediaGrid.org [START_REF] Walsh | The media grid: A public utility for digital media[END_REF], an open standards group for the development of a grid platform specifically designed for digital media. Other projects include mmGrid [START_REF] Basu | mmgrid: Distributed resource management infrastructure for multimedia applications[END_REF], a middleware for supporting multimedia applications in a grid environment and Parallel-Horus [START_REF] Seinstra | High-performance distributed video content analysis with parallelhorus[END_REF], a cluster programming library for applications in multimedia grids. However, these projects mainly focus on design and implementation of media grids, rather than the problem of making efficient use of available grid resources.

This paper presents a number of distinct algorithms to schedule workflows to resources in a media environment. The heuristics presented are an adaption of the list scheduling technique [START_REF] Chrétienne | Scheduling Theory and its Applications[END_REF] and use an offline -sometimes also referred to as static -scheduling approach. This refers to the time at which scheduling decisions are taken. In the offline approach, information regarding the state of all resources and every workflow is assumed to be known. This is a valid approach, as users submit their workflows at the portal, and expect results by a certain time, allowing the scheduler to periodically perform scheduling of the pending workflows. For example, each workflow that needs to be executed the next day is known, so scheduling decisions can be made overnight. Online scheduling on the other hand schedules workflows 'on-the-fly' when they are submitted, based on the current system load. This increases responsiveness, but leads to less efficient resource usage, as the global overview of the system is reduced.

This article is organized as follows. Section 2 describes the problem in greater detail and defines the model used. Section 3 gives an overview of the designed algorithms, while Section 4 thoroughly evaluates these algorithms. Finally, Section 5 presents directions for future research.

Problem Model Description

We assume k workflows {w 1 , w 2 , . . . , w k } competing for resources, whose submit time and deadline are known as well as their maximum allowed budget. Each workflow consists of a set of inter-dependent atomic tasks {t 1 , t 2 , . . . , t n } which are represented in a Directed Acyclic Graph (DAG). The edges between nodes represent task dependencies, and a node either represents a task or a control structure such as a decision or a parallel construct. The particular execution path that will be chosen by a decision construct is not known until runtime, i.e. workflows are non-deterministic. By nature, a loop construct is not supported by a DAG. Loops can be handled by for example unfolding or peeling them as described in [START_REF] Ardagna | Adaptive service composition in flexible processes[END_REF].

Each task requires a specific service to execute, such as for example a transcoder or a CGI renderer. It retrieves its input data from a data repository, and stores its output data on a data repository. There is no direct data exchange between tasks, unless through an intermediary data repository. Tasks can retrieve and store their data either streaming or non-streaming. Each task requires a predefined processing time on a standard processor.

The network consists of a set of nodes, interconnected by a number of edges. These edges represent network connections and are considered to be unidirectional. In other words, to create a full duplex link, two edges are needed. Links offer a certain bandwidth at a certain use cost. A node represents a network node, to which a Computational Resource (CR) or Data Resource (DR) can be attached. The routing between two nodes is known in advance and is assumed to be fixed.

Computational resources offer one or more service types -e.g. transcoding or CGI rendering -at a certain execution speed, expressed in relation to a standard processor. Data Resources are the data repositories and can be used for both data retrieval as for storing output data. Similar to Computational Resources, Data Resources have a particular read speed and write speed, and an associated use cost.

Every task must make advance reservations on each resource (computational, data, network) it uses. In other words, the task reserves exclusive use of the resource during a certain period. Note that this reservation system also helps to avoid the earlier mentioned network oversubscription danger. Rather than reserving each resource for the entire duration of a task, we have chosen to reserve them only when they are actually needed (i.e., a Data Resource used for data retrieval is only reserved for the time it takes to actually read the input, not for the whole input -processing -output cycle). This improves resource usage, but complicates the reservation procedure, as dependencies between various reservations need to be taken into account. Furthermore, for Data Resources a distinction is made between reservations for reading and writing. It is assumed that existing files are never overwritten, so reading and writing from the same Data Resource can occur simultaneously.

Furthermore, it is required that every resource can throttle its speed. Suppose a Computational Resource is able to perform a task at a certain speed, but the Data Resource is not able to supply the input data at that speed. It is then necessary for the Computational Resource to slow down until both speeds match.

Scheduling Algorithm Details

The scheduling algorithm's aim is to find suitable resource triplets (i.e., input Data Resource, Computational Resource and output Data Resource) with sufficient network interconnections for each workflow activity. Resource interconnection characteristics are equally responsible for workflow execution times (and cost) and must be taken into account, in order to avoid creating network bottlenecks.

Determining a suitable set of reservations for a resource combination is no trivial task. Reservation length depends on resource speed and task requirements, but also on whether or not the task is streaming its data. Streaming input requires equal duration of input retrieval and task execution, as we assume input data will be streamed during the full time spent on processing. As mentioned earlier, this may require throttling to match both resources' speeds, thus ultimately influencing reservation lengths. This obviously creates dependencies between the reservations of a single task. Furthermore, reservations need a specific order, depending on the nature of the input and output, as illustrated in Figure 2. The figure shows the different reservation orders that must be respected when dealing with streaming/non-streaming input/output data of individual workflow activities.

Apart from these task-level reservation restrictions, there are also workflowlevel restrictions on reservations. Tasks can only execute when all parent tasks have finished. Overlap of reservations on the same resource is not allowed, but provisions are made to support workflows with alternate execution paths. As the actual execution path is not known until runtime, reservations of tasks in alternate paths are allowed to overlap. Only one set of reservations will effectively be used at runtime.

The algorithms presented here are based on the List Scheduling technique [START_REF] Chrétienne | Scheduling Theory and its Applications[END_REF]. The general outline is shown in Listing 3.1. The heuristic is initialized by adding the root nodes of every workflow to the list Q. Subsequently, a priority is assigned to each task in Q according to a certain strategy, discussed in Section 3.1. The task with the highest priority is selected for assignment and removed from Q. The list Q is somewhat similar to a priority queue, but the priorities of its content need to be re-evaluated in each iteration of the algorithm, as the priority of an unassigned task is usually based on that task's properties, the tasks that have already been assigned, and the associated system loads. The latter two change after every iteration of the algorithm.

The selected task is then assigned to a triplet of resources and network interconnections according to certain criteria. Suitable reservations need to be made on the selected resources, taking into account existing reservations and interreservation dependencies. Different approaches can be considered to select the resources and reservations, presented in Section 3.2.

If no acceptable resource combination can be found for the selected task because each possible combination would violate a constraint, action is undertaken to handle this situation. As with deploying tasks and assigning scores, multiple approaches can be considered (Section 3.3). Algorithm 3.1: Solve(W orkf lows, Resources)

Q, P rocessed ← [ ] for each wi ∈ W orkf lows do Q ← Q + root(wi) while Q = [ ] do                                                HighestP riority ← 0 CurrentT ask ← null for each tj ∈ Q do      P riority ←
do if ∀t k ∈ parents(tj) : tj ∈ P rocessed then Q ← Q + tj
Finally, the children of the selected task are considered for insertion in Q, but only if all of a child's parent tasks have already been assigned to resources. This is necessary to preserve the execution order of the workflow.

This entire process is repeated until there are no more tasks left in Q.

In this discussion, we focus on two optimization objectives, the makespan of a workflow -its entire execution length -and the execution cost -the total cost for using the resources. Task deadlines and budget requirements are considered to be strict i.e. violating them means the workflow cannot be executed.

Determining task importance

The following strategies to assign priorities to tasks in Q have been designed.

Random (RC) Assigns random priorities to tasks. ClosestConstraintViolation (CCV) This algorithm assigns higher priority to tasks closer to violating a workflow constraint, i.e. are closer to their deadline or budget. This naturally depends on the tasks of the workflow that have already been assigned. Giving priority to workflows closer to violating a constraint may prevent these workflows from violating that constraint, as they gain precedence for using the available resources.

ClosestRelativeConstraintViolation (CRCV) This algorithm is similar to the previous one, but the time or budget remaining values are first normalized, and priority is given based on these normalized values. In other words, a task whose workflow already uses a high percentage of its allowed budget or time interval, receives priority. TaskLeastAvailableResourceTime (TLART) This approach considers the set of available resources (computational, data and network) for a task and the occupation on these resources. This occupation is evaluated during the time interval in which the task is allowed to execute. Tasks where the average occupation across their available resources during this interval is higher, receive higher priority. In other words, tasks whose available resources are already heavily in use receive priority. Figure 3 shows the available resources and their reservations for two different tasks. The resources of the task in Figure 3(a) are obviously more occupied than the resources of the task in 3(b). TLART would consequently give higher priority to the former task.

TaskMostAvailableResourceTime (TMART) This heuristic is exactly the opposite of TLART, as it gives precedence to tasks with lower average resource occupations. In Figure 3, TMART gives higher priority to the task in Figure 3(b). This is a somewhat greedy strategy, as tasks that are already known to have a high probability of finding a suitable assignment are given priority.

Assigning tasks to resources

The following strategies are available to assign tasks to resources.

RandomInserter (RI) Randomly chooses a Computational Resource able to process the task and an input and output Data Resource containing the required data sets. The task is scheduled to start as early as possible, taking into consideration the current reservations on the Computational, Data and network resources.

This process of finding reservations for a task is illustrated in Figure 4 for a task with non-streaming input and output. Figure 4(a) shows the initial situation. Figure 4(b) shows a first attempt at finding reservations for the current task. The first free interval on the input Data Resource is valid and an overlapping free interval exists for the network link from the Data Resource to the Computational Resource. An adjacent interval is available on the Computational Resource and another adjacent interval is present on the network link going from the Computational Resource to the output Data Resource. However, there is no valid interval available on the output Data Resource. Figure 4(c) shows the second attempt at finding suitable reservations. The second free interval on the input Data Resource is again valid, but if reading from the resource is started as early as possible, then there is insufficient overlap with the free interval on the network link. The correct solution is shown in Figure 4(d). Figure 4 only shows the case of a task with non-streaming input and output. The three other cases are handled differently, as input-, output-and processing time depend on each other.

SimpleInserterWithDelay (SIWD) The algorithm starts by choosing a Computational Resource from the available resources, and subsequently proceeds by choosing an input and output Data Resource for that particular Computational Resource. The resource is selected in terms of completion time, lowest use cost or a weighted average. Determining the best resource in terms of completion time considers both a resource's speed and occupation, by looking for the earliest usable time slot on that resource as shown in Figure 5. In other words, a slower resource might be picked over a faster resource because it has an earlier time slot available. Reservations are made as described earlier for the random algorithm.

Note that this strategy considers each resource separately. A Computational Resource might be selected because it has a very early available time slot, but this slot is not usable due to reservation dependencies on the other resources, and the Computational Resource may have been a poor choice. Furthermore, the practice of first choosing a Computational Resource and then Data Resources can often lead to suboptimal solutions [START_REF] Alhusaini | A unified resource scheduling framework for heterogeneous computing environments[END_REF]. BestCombinationInserter (BCI) This strategy improves SIWD by evaluating every possible resource combination of input Data Resource, output Data Resource and Computational Resource -including the network links involvedaccording to the criteria earliest completion time, lowest use cost or a weighted average of both. To determine the earliest completion time of a task on a particular resource combination, the earliest possible valid set of resource reservations must be found on that combination. The procedure for finding this reservation set is similar to the reservation procedure described for the RandomInserter algorithm (Figure 4). The BCI strategy is obviously computationally considerable more expensive than SIWD.

BestCombinationInserter is illustrated in Figure 6 which lists two possible resource combinations for a task with streaming input and non-streaming output. While combination 6(a) has slower resources (note that the reservation interval lengths are longer), it is still preferable to 6(b) because it has an earlier completion time.

TieBestCombinationInserter (TBCI) This approach improves BestCom-binationInserter by handling tie situations. If two combinations have the same completion time, then the selection is made based on the total cost of each combination, and vice versa.

Handling constraint violations

Only one strategy to handle constraint violation situations is presented here, due to space limitations, although others are available. The DeleteViolatingWorkflow (DVW) strategy simply blacklists the offending task's workflow and removes all reservations that have already been made for that workflow. This enforces strict constraints, and violating workflows are removed to free up resources. Testlab evaluations and field trial implementations require a lot of effort, and are impractical to perform large-scale testing. Only rigorous testing on largescale environments with different setups can provide a true comparison on the performance of different algorithms. Since building large testbeds is costly, time consuming and often impractical, simulation is an important aid in the evaluation of algorithms.

Therefore, a simulation framework is designed and implemented in Java to facilitate the evaluation of the developed algorithms. It is able to simulate any combination of algorithm, network topology and workflow load. The configuration of network infrastructure, workflow load and the scheduling algorithm to use are supplied to the simulator in an XML format. Note that the workflow load supplied to the simulator is a fixed description consisting of a list of workflows including individual submit times and properties such as deadline and budget. This allows us to evaluate different scheduling strategies on the same resource topology and workflow load.

For performance reasons, the simulator performs high-level simulation of network transfers (i.e. not down to packet level but transfer times determined based on data size, network route and individual network link bandwidth). The simulator logs detail information on all tasks and resources.

Simulation Setup

The following evaluation setup has been used to obtain the results presented here. A simulation is run for each algorithm using the same load and network. These simulations are repeated a number of times with different loads and networks to obtain a view on the average performance of the algorithms.

The basic network topology is randomly generated starting from the European network shown in Figure 7 but with varying parameters such as available network bandwidth between nodes, the number, speed and cost of Computational Resources and the number and data repositories of the Data Resources.

Bandwidth between cities is randomly chosen from 1Gbps, 100Mbps or 10Mbps. Cities have a number of nodes connected to them -always through 1Gbps links -on which the Computational and Data Resources reside. Data and Computational Resources never share a node, and each city has at least one Data Resource and one Computational Resource. Three classes of Computational resources exist, executing tasks at 0.5x, 1.0x or 2x reference speed, and for the simulations presented here, tasks can execute on every Computational Resource.

All workflows are line workflows, i.e. there are no parallel or alternative paths. Tasks' input and output data sizes range from 768Mb to 46Gb, according to a random uniform distribution. Input and output can be streaming or nonstreaming. Processing time depends on the size of the input data and the Computational Resource's speed. Processing 768Mb data at reference speed takes 120 seconds, while processing 46Gb takes 2 hours at reference speed. A task has a probability of 0.3 to find its requested input data on a particular Data Resource. Likewise, it has a 0.3 probability to be able to store its output data on a particular Data Resource.

Three different scenarios are evaluated, with workflow loads consisting of respectively 250, 500 and 750 workflows over a 24h interval, with a uniform distribution arrival. These loads are chosen to stress the available resources and the algorithms.

Detailed evaluation results

The results on the following combinations of priority-, assignment-, and constraint handling strategies are presented: RC-RI-DVW, CCV-SIWD-DVW, CCV-BCI-DVW, CCV-TBCI-DVW, CRCV-TBCI-DVW, TLART-TBCI-DVW and TMART-TBCI-DVW. The abbreviations for the different strategies are defined in Section 3.

Figure 8(a) shows the average workflow acceptance rates for 20 different runs, as a function of an increasing workflow load. While these loads may not seem very high, recall that the execution of a single task can take several hours. Half of the runs prioritized makespan, the other half budget. The workflow acceptance rate is the percentage of workflows that can be successfully assigned to resources and executed. Recall that strict constraints are enforced, i.e. workflows that would violate a constraint are simply not started.

Figure 8(b) -which shows the average Computational Resource occupation as a function of an increasing load -serves to illustrate that the decrease in acceptance rates as loads go up is attributed to a saturation of Computational Resources, rather than the algorithms. Note that it is very unlikely for resources to reach full utilisation, due to free time fragmentation on the one hand, and the dependencies between reservations on different resources on the other hand.

From Figure 8(a), it is evident that randomly assigning workflows to resources results in unacceptable workflow acceptance rates. Likewise, using the naive SIWD resource assignment strategy produces barely higher acceptance rates. SIWD is inefficient because it considers Computational and Data Resources independently, which has several implications. Firstly, choosing a fast Computational Resource independently makes no guarantees about the available Data Resources and network links for that resource. Furthermore, always choosing the best Computational Resource ensures that these Computational Resources will quickly become unavailable. Further observations show that the tie considering strategy of TBCI indeed improves the BCI strategy slightly, as it produces a higher acceptance rate.

The results show that the performance of the CRCV priority heuristic compared to the CCV approach drops as the loads go up. The rationale behind the CRCV priority strategy is to give higher priority to workflows that have already used up relatively more of their budget or available time. However, the absolute time or budget remaining is important, as it allows CCV to assign lower priorities to tasks and workflows with loose constraints and high priority to workflows with strict constraints. This is however not the case for CRCV. This can result in situations where workflows or tasks with loose constraints are given priority and thus needlessly reserve fast or cheap resources, while they could have completed with slower or more expensive resources.

The TMART priority algorithm performs considerably worse than TLART. Giving more priority to tasks that are unlikely to be deployed definitely increases the possibility of these tasks being deployed, without adversely affecting tasks that already have a good possibility of getting deployed. The opposite 'greedy' strategy TMART definitely has a negative impact on the amount of workflows that can be deployed.

Figure 9 displays the running times of the algorithms to determine a schedule, as a function of an increasing workflow load. The algorithms are executed in Sun Java 6 on an AMD Opteron 2350 machine with 8Gb memory installed. The less complex SIWD and BCA assignment strategies are obviously considerably faster than the BCI and TBCI strategies, which need to consider every resource combination for each task. Furthermore, the more complex priority assignment algorithms TLART and TMART also cause higher execution times, as they need to evaluate the occupation of every potential resource for each task. The higher execution time of TMART versus TLART can be attributed to the fact that TMART can deploy considerable less workflows than TLART. Consequently, the constraint violation handler is called more often for TMART, resulting in an increased execution time.

Future Work

Areas for future work include a more extensive evaluation on the performance of the various algorithms, not limited to line workflows, but also including completely arbitrary workflows containing parallel paths and alternative paths of decision branches.

Additionally, only one constraint handling strategy has been presented in this paper. Additional constraint violation handling strategies are available, and their evaluation must be presented as well. Alternate (meta-)heuristics may also be evaluated.

Furthermore, online scheduling algorithms have been designed, and their detailed performance evaluation is ongoing at the time of writing.

Conclusions

The Independent Films In Progress (IFIP) project is a framework aimed at the media industry, providing a platform for users to automate and submit production processes such as editing and distribution. Users submit a series of tasks or workflows they want to be executed within certain constraints. The platform autonomously assigns the appropriate resources to the users' workflows and executes them. A key issue in such a platform is how to efficiently allocate tasks to the available resources, hereby improving throughput, scalability and QoS.

To this end, this paper presents a number of offline scheduling algorithms which are based on the List Scheduling technique, but use different strategies to handle the various stages of the heuristic such as assigning priorities to tasks, task-to-resource assignments and constraint violation handling. Extensive evaluation of the developed algorithms has proven that they outperform naive implementations, and shows the importance of selecting adequate priority, deployment and constraint handling strategies.

Fig. 2 .

 2 Fig. 2. Resource reservation order according to streaming or non-streaming nature.

Fig. 3 .

 3 Fig. 3. Two different tasks and the current reservations on their available resources

Fig. 4 .

 4 Fig. 4. Finding the earliest possible reservations and starttime for a task

Fig. 5 .Fig. 6 .

 56 Fig. 5. Resource selection by the SimpleInserterWithDelay strategy

Fig. 7 .

 7 Fig. 7. The European network as a result of the COST-292 project

Fig. 8 .

 8 Fig. 8. Average results over 20 runs including standard deviation, as a function of an increasing workflow load. Loads are over a 24h interval. The standard deviations are shown as well.

Fig. 9 .

 9 Fig. 9. Average execution time of each algorithm as a function of the load, 24h interval. The standard deviations are shown as well.

Acknowledgment

Part of the research described in this paper is funded through the IBBT-project IFIP.


Kristof Verslype

Pieter Verhaeghe

Jorn Lapon

Vincent Naessens

Bart Decker

Bart De Decker

PriMan : A Privacy-Preserving Identity Framework

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

Introduction

The digitalization of our society comes with a lot of benefits. However, privacy of the user is increasingly at stake. The awareness of both citizens and companies is rising. In fact, both can benefit from a higher level of privacy in applications.

Therefore, techniques are being developed to improve the user's anonymity; crowds and mix networks at network level, and anonymous credentials w.r.t. personal user properties. The latter enable to prove only the required properties, e.g. that you are older than 18 if one of the credential attributes is your date of birth.

The privacy enhancing technologies (PETs) are heterogeneous in approach; e.g., pseudonym certificates are sent to the verifier, while Idemix credentials only send proofs. Hence, it will cost the application developer much effort to develop a privacy-friendly application, especially when multiple credential types must be supported. Also, chances are that the privacy issues will be omitted or that the privacy is inadequately protected due to incorrect use of PETs. Moreover, even in privacy-friendly applications, the user remains in the dark about to whom and under which pseudonym personal properties have been disclosed or, in short, about his degree of anonymity towards others.

Therefore, PriMan, a privacy-preserving user-centric identity middleware framework is designed and implemented. It facilitates the development of privacy-enhanced applications. The different credential approaches are reconciled, resulting in a uniform interface enabling the application developer to choose the most appropriate technology and to easily switch to another one when e.g. the requirements change.

Three privacy-preserving applications in three different domains have been built on top of this framework; an ePoll (eGoverment), an eTicketing (eCommerce) and an ePrescription (eHealth) application. The design of the presented framework has been reiterated several times driven by the feedback received from the application developers.

The next section briefly sums up the relevant privacy preserving technologies supported by the framework. The requirements derived from the applications are presented in section 3. The general architecture, the generic credential representation and the validation are given in section 4, 5 and 6. Related work is discussed in section section 7 and the conclusions are given in section 8.

Building Blocks

The supported building blocks and the main credential systems are touched.

Mix networks (e.g. [START_REF] Camenisch | Mix-network with stronger security[END_REF]) and crowds (e.g. [START_REF] Danezis | The wisdom of crowds: Attacks and optimal constructions[END_REF]) guarantee anonymity at network level. A commitment scheme [START_REF] Pedersen | Non-interactive and information-theoretic secure verifiable secret sharing[END_REF][START_REF] Damgard | Statistical secrecy and multi-bit commitments[END_REF] allows an entity to commit to a set of values, while keeping these secret. The commitment hides the values towards the verifier, but allows the creator to prove properties of the committed values. A verifiable encryption scheme (e.g., [START_REF] Cramer | A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack[END_REF]) also allows the creator to prove properties about the encrypted values, while the verifier is ensured that a known TTP will be able to decrypt the ciphertext if necessary. A Pseudonym is an identifier presumably unlinkable to a real identity.

An X.509 certificate is a set of personal attributes and other related properties signed by a certifier using a standard signing algorithm. The certificate owner needs the corresponding private key to prove ownership of it. Presenting it to others implies disclosing all the content in the certificate. X.509 certificates are revoked by adding their serial numbers on a revocation list. Pseudonym certificates [START_REF] Asokan | Towards a framework for handling disputes in payment systems[END_REF] are standard certificates in which the identity information is replaced with a pseudonym. Different shows of the same certificate are linkable, potentialy undermining anonymity. The privacy can further be increased by substituting hashes or MACs for the actual attribute values. This way the certificate owner can decide which attributes to disclose. An anonymous credential [START_REF] Camenisch | An efficient system for non-transferable anonymous credentials with optional anonymity revocation[END_REF][START_REF] Brands | Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy[END_REF] allows for selective disclosure of properties of credential attributes, while hiding the others. The credential itself with its values is not revealed, but instead, a zero-knowledge proof of knowledge that the disclosed properties were certified by the issuer. Usages of anonymous credentials can either be linkable (e.g. UProve) or unlinkable (e.g. Idemix). It is possible to prove membership of a set without revealing anything else. The disclosed properties can also involve attributes in other credentials, in verifiable encryptions and in commitments. Idemix credentials can be shown under a pseudonym to which the credential is not bound. The issuer of an Idemix credential can set a global limit on the number of times the credential can be used. Finally, a credential usage can optionally be deanonymized afterwards by a trusted party in case of abuse.

Requirements

The framework specific requirements are formulated (Fx) and are followed by the framework tasks derived from the applications (Tx). T1-T3 are indispensable. T4-T6 are needed to build a full-fledged privacy-preserving identity framework.

F1. User-centricity. The user controls the disclosure of his personal data.

F2. Usability. A technology agnostic, intuitive interface facilitates the development of

privacy preserving applications and plugging in new implementations (e.g. UProve credentials) must be easy. F3. Modularity. By loading only the required modules and implementations, PriMan can be run on portable devices; e.g. on a doctor's portable device to issue prescriptions on location in the ePrescription application. F4. Protection of (highly) confidential information. Confidential data can be secret keys, but also personal data, since it can reduce users' anonymity. T1. Setting up connections with various properties. An SSL connection might suffice for e.g. registration. However, a mix network might be a better choice to protect the user's anonymity for e.g. anonymous poll signing. T2. Creation and usage of credentials. In all three applications, credentials of different types are issued and used. Proving properties during a credential show often requires commitments and verifiable encryptions. T3. Secure storage of credentials & credential related data. Users often have many credentials, which must be stored and managed securely. Some credentials should always and everywhere be available and, hence, must be stored on a smartcard or on a remote server (e.g. ticketing). [T4.] Anonymity set estimation. The user discloses mandatory properties in the ePoll and eTicketing plus potentially optional ones. The framework must estimate the consequences of these disclosures on the user's anonymity and give advice. [T5.] Profile tracking. In the eTicketing application, multiple purchases by a user of tickets for the same event need to be linkable in order to be able to restrict the maximum number of tickets per customer. If the user discloses different properties when buying tickets at different occasions, his anonymity may decrease. Therefore, the framework has to securely and locally keep track of the properties disclosed under pseudonyms to other parties. [T6.] Dispute solving. In the ePrescription and eTicketing application, abuse is possible. Hence, support for deanonymization must be provided.

General Architecture

The above-formulated requirements led to the PriMan architecture of which a high level overview is presented in figure 1. PriMan consists of abstract handler interfaces and concrete managers. A handler interface provides a uniform interface to a class of technologies such as credentials, connections or storage. A handler is in general a wrapper around an existing implementation of a technology (e.g. Idemix). A provider contains concrete handlers. Multiple providers can be plugged into PriMan. Each of the first six managers corresponds to one of the framework tasks T1-T6 and keeps track of and uses the underlying concrete handlers to offer higher level functionality, since the existing technologies are rather low level. A special manager is the policy manager to automate decisions. The PriManFacade is the application's entry point to the managers. Also, an appropriate GUI can be implemented and loaded; e.g. one GUI for PDAs and one for desktop computers.

A connection hander sets up, listens for and closes connections (T1). The connection manager allows the developer to specify connection properties such as integrity and/or anonymity properties. Based on these properties an appropriate handler is selected to set up the connection.

A credential handler provides the functionality to issue and receive credentials and pseudonyms as well as to authenticate or to sign messages with these credentials (T2). Three subhandler interfaces deal with revocation, commitments and verifiable encryptions. The service provider's access policy will define which credentials are to be used and which properties the user must or may disclose. Based on this request, the user's credential manager obtains the sets of credentials, commitments, pseudonyms and verifiable encryptions able to the request.

Storage of credentials and credential related data such as commitments (T3) is done by the persistence manager. It keeps track of where the different data objects are stored and which handler maintains them. Each handler defines a location type (e.g. smart card or server), an encoding structure (e.g. XML) and the protection mechanism (e.g. password based).

The privacy manager estimates the anonymity of pseudonyms towards other parties and the impact of disclosing certain properties (T4). Each privacy handler provides a concrete metric therefore.

Profile tracking (T5) is done by the profile manager. The profile handler keeps track of one or more profiles. Depending on the framework policy, authorization can be given to external entities to do certain types of queries on one or more profiles: adding or requesting for data which can be application or context specific (e.g. books bought). Also, a user can add data to a profile (e.g. books (s)he is interested in). The profile manager determines to which profile data are added. A profile handler also implements heuristics to probabilistically link profiles.

The Dispute Manager (T6) offers the means to file complaints in case of abuse. Complementary, evidence to protect against false accusations can be stored and later be disclosed to trusted third parties. These parties can do the deanonymization when certain conditions are fulfilled. Since deanonymization is credential type specific, an underlying credential handler is used.

Each provider consists of a set of concrete handlers (e.g. Credential.X509 and Connection.Tor). For each implementation, the provider maintains some bookkeeping information (names, properties, versions, ...)

Generic Credential Representation

The central concept in the framework are credentials. Therefore, this section presents a uniform, technology agnostic representation of credentials and related objects, which facilitates switching to other technologies. Credential technologies with heavily differing approaches such as passwords, X.509 certificates and Idemix credentials fit in the representation. Different object types are defined.

Credential template. It describes everything credentials of a certain category have in common (e.g. Belgian driving licenses with the same issuer public key): 1) technology specific security parameters such as key lengths; 2) control settings defining the credential's validity and usage rights such allowance to sign, the show limit, validity period and credential verification info; 3) the issuer data and 4) an attribute specification which specifies mainly the label and type of each of the attributes.

Credential. A credential consists of 1) a credential template, 2) credential values; i.e. credential's attribute values and the validity start date, 3) a credential trace containing all the information disclosed each time the credential is used (e.g. serial number and public key), and 4) (references to) credential secrets required to use the credential. Credentials never leave the framework. Credential secrets and values are sensitive data and the latter can only be exported by a framework protocol.

Show specification. This describes the properties to disclose or that were disclosed when a credential is/was used to sign, verify or issue a credential.

Disclosure. This contains the show specification and the involved objects required to either prove or verify the properties described in the show specification. Multiple credentials, commitments and verifiable encryptions and a pseudonym can be involved. In addition, deanonymization specifications can be added to specify the deanonymizers and deanonymization conditions (typically abuse). When a prover sends a disclosure to the verifier, information such as secrets and attribute values are removed from the contained objects, such that the received disclosure can only be used for verifications.

Entity. An entity represents a person or organisation and consists of a verifiable disclosure together with a proof (authentication or signature) of this disclosed information. Entities are useful to keep track of the information known to or about others. It allows to verify certification chains, which consist of entities.

Transcript. This is a framework protocol return value which contains all exchanged data and data required to rerun the protocol such as connection id or an entity representing the prover in case of an authentication verification. Transcripts are profile manager input.

The control settings in the templates allow for multiple issue keypairs in one credential and, hence, allow for issuing new credentials of different types with one existing credential; for instance, issuance of Idemix and UProve credentials with an X.509 credential. Similarly, multiple verifiable encryption keypairs can be included.

If the properties in the show specification are proven, the verifier knows in addition the credential trace. Hence, the less information in the credential trace, the better (which is technology dependent). This can be checked by the prover in advance.

As an example, an X.509 certificate without private key is represented as an entity since it represents a person or organization about which properties are certified. The corresponding verifier disclosure contains a credential trace and a credential template which contain all the information such as the attribute names and values and the certification signature to let an X.509 handler recompose the original X.509 certificate. An Idemix credential will have an empty credential trace.

Validation

In the ePoll application, citizens can participate in multiple polls using an anonymous credential, but can only vote once for each poll. Votes of the same user are unlinkable. The poll organizer can restrict the voter set and can invite voters to disclose some additional properties, enabling the generation of more significant poll statistics. For instance; the poll could be restricted to adults and optionally, they may disclose their gender. Poll signatures are published to allow everyone to verify the poll's correctness. In figure 2, a client and server application use different managers to build this application.

First, the client application creates an anonymous connection with the ePoll server (C1-C3,S1), which replies by sending a request (C4,S2). A Request object contains a description of the obligatory and optional properties to be disclosed and can contain a list of sign options. It also lists the templates of acceptable credentials. The received request thus contains the user's different personal property disclosure options and the different choices he can vote for. Based on the request, the client's credential manager is asked to give a description of each credential able to fulfill the request (C5); in the ePoll case, there is one such credential. Based on the request and the credential description, all the possible show specifications are returned (C6); i.e. all the sets of properties the user can disclose using that credential in order to cast a vote. The application could optionally ask the profile manager for the profile containing the information disclosed previously to that poll service (C7). Since the user never signed the poll, this profile will be empty. The privacy manager is asked for the impact on the privacy for each of the possible show specifications (C8). The returned PrivacyInfo object contains the relevant anonymity information for each of the show specifications if the contained properties were disclosed. Now, the application can decide which properties to disclose. Note that the policy manager can already filter out some possibilities.

The user selects the properties to disclose and the option to vote for (C9, C10). The client's credential manager is asked to create the Disclosure object corresponding to the show specification (C11). Therefore, it loads the corresponding credential (using the persistence manager) and creates the required pseudonym. The nym, credential and show specification are put in the disclosure, which is used to create the signature (C12). The disclosure, signature and choice are sent to the poll organizer (C13-15,S3-S5). The client's profile manager is informed that over conn a disclosure has happened, which was in fact a signature on choice and that the signature is published (C16). After receiving a signature, disclosure and the corresponding choice (S3-S5), the server application asks the credential manager if the disclosure matches the request (S6) and if the signature is valid (S7) and it asks the profile manager if the pseudonym in the disclosure has not yet been used (S8). If these three conditions are met, the server application publishes the signature, disclosure and signed choice [START_REF] Irwin | An identifiability-based access control model for privacy protection in open systems[END_REF].

Note that both client and server use the framework in a complementary way and also notice how easy it is to build applications on top of PriMan.

Related Work

Several federated identity management systems (FIMs) exist such as Shibboleth, Windows Cardspace, OpenId, Athens and Higgins. They all have in common that the user data is stored by a trusted identity provider (IdP). Some of the federated identity management systems allow the user to request the IdP a token containing only properties of the user, hence, improving the user's privacy. Still the IdP knows when what properties were requested by the user. None of the current FIMs offers real user-centric identity management, which is made possible using anonymous credentials. Also, none of the FIMs offers the user the possibility to keep track of disclosed properties, nor can they inform the user about his/her anonymity status. Since the IdP can always link an issued token to an identity, the FIMs do not need the possibility of deanonymization. Their tokens are typically based on SAML. Our approach is built upon the idea of real user-centric identity management, centered around the concept of anonymous credentials and offers support for the above-mentioned functionality. In addition, it can offer support for any credential type and is not limited to SAML tokens.

PriMan allows to use different concepts in a coherent way; credentials, connections, persistence, profiles, etc. Hence, the framework integrates current and future implementations and research in one aggregate. For instance, a high-level approach to control the information disclosure based on the sensitivity and the possibility that a user's identity is revealed was proposed [START_REF] Irwin | An identifiability-based access control model for privacy protection in open systems[END_REF] and could be implemented by a privacy handler.

Conclusions

This paper presented PriMan, a flexible middleware framework that considerably facilitates the development of privacy-preserving applications. Although not all building blocks have an implementation yet, PriMan is already a very useful tool for developers.

Fig. 1 .

 1 Fig. 1. High level architecture of PriMan.

Fig. 2 .

 2 Fig. 2. Example: signing an anonymous poll.

Acknowledgements. This research is partially funded by the Interuniversity Attraction Poles Programme Belgian State, Belgian Science Policy and the Research Fund K.U.Leuven and the IWT-SBO project (ADAPID) "Advanced Applications for Electronic Identity Cards in Flanders".