DSpace Collection:

Stochastic optimization for airport inventory management

2011-10-24T23:38:23Z

Stochastic optimization for airport inventory management Cesaro, Annalisa 2010-03-30 Effective supply chain management is currently recognized as a key determinant of competitiveness and success in manufacturing and services, because the implementation of supply chain management has signiﬁcant impact on cost, service and quality. Numerous strategies for achieving these targets have been proposed. The improvements in information technology coupled with the substantial reduction in the cost of processing, storing and analyzing data have made new strategies more attractive. On such strategy allows movements of stock between locations at the same echelon level via lateral transshipment. Despite the above technology improvements, the implementation of such transshipment strategy requires still great eﬃciency especially in real life problems, because it suffers from computer memory limits and long computation times when the number of warehouses gets large, or when the number of parallel items to ba analyzed following an item approach gets large, too.In fact, a drawback of the policy of interest is the state dependent nature of the re-forwardings in the systems. Therefore an effective tactical planning requires joint contribution from various disciplines in order to be implemented eﬃciently, such as engineering, mathematics, economics and computer science. New solution methods have to be explored in order to effectively implementing new management strategies. This thesis uses operations research techniques in order to study a single echelon, one-for-one ordering policy with complete pooling, with a deterministic rule for lateral transshipments. Speciﬁcally we propose new evaluation and optimization methods thus handling real life problems within a reasonable amount of computation time. In fact, we test all the proposed methods on the practical case study motivated by the practical needs of an Italian logistics, supporting the activity of 38 civil airports spread over the Italian territory. The company handles 17 warehouses and manages the overall process of purchasing, holding, ensuring that the overall reliability of safety equipments is always within contractual limits. The aim of the company is therefore to grant the prescribed quality of service at minimum cost. The items to be managed in such a context are typically expensive ones and with low demand, but we clearly recognize that there are many different types of service parts and that they perform many different functions. Therefore, in such a context also parts with a lower ratio between holding and transshipment costs may be encountered and managed. Thus with all the uncertainties that exist, a tactical plan should be created that will provide the ﬂexibility needed to meet a wide range of scenarios, pointing the attention on the characteristics of the majority of items. Common techniques models the management policy with a Markov chain approach, thus evaluating such a policy given a spare parts allocation. The optimal stock allocation problem is formulated as an integer program with non linear objective function and non linear constraints. Therefore total enumeration methods or approximation algorithms can be employed for optimally solve it. Based on the needs summarized above, the following research objectives have been achieved in this dissertation. We have focused on a single echelon one-forone ordering policy with complete pooling, with a deterministic rule for lateral transshipments. We have formalized mathematically the Spares Allocation Problem (SAP) and have understood its mathematical structure for building an exact algorithm for optimally allocating the spares. In fact, in literature to the best of our knowledge no exact algorithm has been proposed for allocating optimally the spares in a continuous review setting rather than a total enumerative algorithm. By exploiting the above algorithm it is interesting – Making insight in the SAP and underline which factors inﬂuence inventories in such a context. – Evaluating fast and accurate heuristics for SAP. Efficient and accurate models for assessing the performance of a single echelon replenishment policy have been proposed and evaluated especially for large numbers of locations. A drawback of the policy of interest is the state dependent nature of the re-forwardings in the systems, it has been therefore interesting. – understanding the properties of the Markov chain associated to the chosen policy. – exploring, despite its state dependent nature, the possibility of expressing the state probabilities of the associated Markov chain model exactly in product form – developing fast and accurate approximate models for evaluating the performance and costs in the system, since computing the state probabilities is not practical as the number of states in the Markov chain increases. The achievement of the ﬁrst objective clearly required a strong connection with the resolution of the second objective. In fact, the development of an exact algorithm for allocating the spares may require in contexts with a large number of warehouses and high rates approximate models for assessing the performance and evaluating the costs. Speciﬁcally, n this thesis by using a suitable optimization model we have shown that the Markov chain cannot be decomposed exactly in product form. In fact, the best product form approximation returns a positive accuracy error, which implies that an exact product form does not exist. Hence, we have adapted four approximation techniques to our model and evaluate their performance in terms of computational effort, memory requirement and error with respect to the exact value. Three techniques approximate state probabilities with others that can be expressed in product form, so that the Markov chain can be decomposed. Speciﬁcally, we adapt a method by Alfredsson and Verrijdt, the Equivalent Random Traﬃc (ERT) method and the Interrupted Poisson Process (IPP) method. The last two techniques have been proposed for exploring the inﬂuence of peakedness in approximation models with respect to the accuracy of performance estimation due to the state dependent nature of the re-forwardings in the system. The fourth technique is based on the multi-dimensional scaling down approach, which studies an equivalent reduced Markov chain rather than decomposing the original one. The scaling down method outperforms the decomposition techniques for small OA values (OA < 0.997), while the percentage error is similar for larger OA values. Besides the better performance shown in ﬁgure, in our experiments the scaling down method provides OA values smaller than the exact ones in more than 80% of the experiments while the decomposition methods ﬁnd OA values always larger than the exact ones. The scaling down method is therefore more conservative than the decomposition methods, and this is an important feature when the method has to be used within an optimization The formulation and solution of the Spares Allocation Problem (SAP) is one of the main achievements of this thesis. The mathematical structure of the problem has been investigated to build an eﬃcient exact algorithm for optimally allocating the spares. Two assumption on the cost structure of the problem leads to prove properties of the cost function that in turns allow to design a new efficient branch and bound procedure. The lower bound is obtained by solving a reduced problem with convex objective function, solvable at optimally very efficiently. A new fast heuristic algorithm is also developed to ﬁnd a feasible allocation within small computation time. Computational experiments demonstrate that the branch and bound technique is able to optimally solve almost all tested instances within reasonable computation time. The heuristic algorithm ﬁnds quite good solutions within very limited computation time, thus being a promising approach for ﬁnding feasible solutions to difficult instances. Moreover we have analyzed several cost structure scenarios and we have observed that the transshipment cost is often comparable with the holding cost and therefore it cannot be neglected in the solution of the problem.

Production scheduling in pharmaceutical industry

2011-10-24T23:38:22Z

Production scheduling in pharmaceutical industry Venditti, Luca 2010-03-30 Production scheduling is the phase of production management that produces a detailed description of operations to be executed in a given period of time, typically short. Manufacturing process in pharmaceutical industry is characterized by an high complexity of processes. Moreover, compared to other manufacturing processes, the pharmaceutical industry gives higher importance to on-time delivery over throughput maximization, due to the economical and legal implications of late deliveries and stock-outs at the final customers. In this contest, it is evident that scheduling is a critical operation and so, that an automated scheduling system is important, both to obtain good scheduling solutions and to have a better control of the production process. A first aim of this thesis is to give a demonstration of the improvements that may derive from an automated scheduling. At the same time, the issue concerning the difficulty of solving practical scheduling problems is arisen. A real case study of production scheduling, concerning the Packaging department in a real pharmaceutical industry, is studied. A complex model and a tabu search algorithm have been developed to solve the related very hard scheduling problem, modeled as a multi-purpose machine problem with setup and removal times, release and due dates and additional resource availability constraints. The algorithm is able to find good solutions within short computation time, compared to the solutions found by human schedulers. This result conforms that scheduling technology is mature to solve complex real problems; to this aim, however, it is important to make use of detailed scheduling models. Besides operations management in a single stage, another interesting issue in production management, and in general for supply chain management, is the coordination between stages. This issue is particularly important in the pharmaceutical supply chain, in which the legal and economical implications of product stock-out requires the adoption of standards of product quality and availability close to 100%. Availability of final products requires not only to achieve excellence at each stage of the planning process, from strategic planning to real time scheduling and delivery, but also in the coordination between different stages. A second aim of this thesis is to investigate on the benefits that the introduction of a centralized decision support system can bring with respect to an uncoordinated decentralized one; the case study of coordination between the Packaging department and the subsequent Distribution stage of the real pharmaceutical plant, i.e between the packaging of final products and their distribution to wholesalers, is addressed. The distribution problem can be formulated as a vehicle routing problem with soft time windows. A classic tabu search algorithm is adapted to solve the scheduling problems of the two departments separately with a decentralized approach, and then to face the combined scheduling and delivery problem with a centralized approach. Results have demonstrated that the centralized approach provides much better results than the decentralized one with even a less computational effort. These results confirm the need for excellence in the coordination among different stages of the production process, other than within each stage, when high standards of quality and reliability must be provided to the final customers.

On the existence and optimality of some planar graph embeddings

2011-10-24T23:38:05Z

On the existence and optimality of some planar graph embeddings Angelini, Patrizio 2010-03-30 A graph is an abstract mathematical representation of a set of objects, called vertices, together with a pairwise relationship between such objects, that is represented by a collection of edges connecting pairs of vertices. Examples of relationships among objects that are representable by a graph can be found in every ﬁeld, ranging from interpersonal relationships to computer networks and from knowledge representation to bioinformatics. Of course, the best way to make such a relationship clearly understandable is to visualize the graph so that vertices and edges are easily recognizable at human eye. Such an issue is addressed in the research ﬁeld of Graph Drawing, which can be regarded as a cross between the areas of Graph Theory, Graph Algorithmic, and Computational Geometry. In Graph Drawing, the most common way to visualize a graph is to draw each vertex as a point in the plane and each edge as a curve connecting the corresponding points. The placement of the vertices in the plane and the drawing of the curves should be performed in such a way that the resulting drawing be nice and readable, in the sense that the information described by the graph should be possibly understandable at a glance. In order to obtain the desired nice and readable visualization, it is important to formalize the aesthetic criteria that distinguish a “good” drawing from a “bad” one. Then, the goal of Graph Drawing is to create algorithms that automatically produce drawings respecting such criteria. The most natural aesthetic criterion that one can think of is probably the absence of partial or complete overlapping among vertices and edges, that is called planarity. Another important criterion that one has to consider when drawing a graph is the area of the drawing, as a drawing with a small area can be better visualized inside a small screen. Observe that, while planarity is a property that a drawing may satisfy or not, the drawing area is a measure of quality that can be used to compare two drawings. Many other properties and quality measures can be deﬁned concerning the visualization of graphs, even with the possibility of combining some of them. However, the “best” drawing of a graph might not exist, since drawings that are “good” in terms of a certain criterium may be “bad” in terms of another. It is interesting to observe that some of the aesthetic criteria of a drawing of a graph only depend on its topological features, while other criteria also depend on the geometrical realization. For example, an important theorem in Graph Drawing, known as Fary’s Theorem, states that every graph admitting a planar drawing also admits a planar drawing in which edges are represented by straight-line segments. This implies that, in order to decide whether a given graph admits a planar drawing, it is possible to study whether such a graph admits a planar embedding, that is, a circular ordering of the edges around each vertex that determines no topological crossing in the induced drawing, rather than computing the actual coordinates of the points representing the vertices. On the other hand, given a graph with a ﬁxed embedding, diﬀerent geometrical realizations may lead to drawings with diﬀerent area. Several natural and interesting to study questions can be formulated concerning the aesthetic criteria deﬁned for the graphical representation of graphs. When considering a graph property, the ﬁrst, and probably most natural, arising question is the one about the existence of graphs satisfying such a property and of graphs not satisfying it. If both positive and negative instances exist, the problem can then be studied by either asking for a characterization of the family of graphs that satisfy the desired property, or by determining the computational complexity of the problem of deciding whether a given graph satisﬁes the property. On the other hand, when considering a particular measure of quality of a drawing or of an embedding, the two most natural questions are certainly the one asking for the optimal value of such a measure among all the graphs of a certain family and the one asking for an eﬃcient algorithm that optimizes such a measure for a given graph. In this thesis we address and partially answer such questions on several classes and types of graphs, as we propose algorithms for computing planar embeddings or drawings that satisfy certain properties or that are optimal with respect to certain measures of quality. We mainly deal with planar graphs and with graph properties and measures that depend on the topology of the graph (Part II) and on its geometry (Part III). Also, we consider the same questions on simultaneous graph drawing problems (Part IV), that is, problems involving more than one graph, and on clustered graphs (Part V), that is, graphs where the vertices are grouped into clusters by means of a hierarchical structure.

Quality of mappings for data exchange applications

2011-10-13T23:35:34Z

Quality of mappings for data exchange applications Raunich, Salvatore 2010-03-30 Research has investigated mappings among data sources under two perspectives. On one side, there are studies of practical tools for schema mapping generation; these focus on algorithms to generate mappings based on visual specifications provided by users. On the other side, we have theoretical researches about data exchange. These study how to generate a solution -- i.e., a target instance -- given a set of mappings usually specified as tuple generating dependencies. However, these two research lines have progressed in a rather independent way and we are still far away from having a complete understanding of the properties that a "good" schema mapping system should have; to give an example, there are many possible solutions for a data exchange problem. In fact, there is no consensus yet on a notion of quality for schema mappings. In this thesis, based on concepts provided by schema mapping and data exchange research, we aim at investigate such a notion. Our goal is to identify a fairly general formal context that incorporates the different mapping-generation systems proposed in the literature, and to develop algorithms, tools and methods for characterizing the quality of mappings generated by those systems.

Understanding and detecting BGP instabilities

2011-10-13T23:37:44Z

Understanding and detecting BGP instabilities Cittadini, Luca 2010-03-30 Communication networks have reached amazing size and complexity nowadays. The Internet, which was born as an experimental network connecting a handful of volunteer research institutes, has grown to become a huge distributed system interconnecting almost 700 millions of hosts at present. As soon as it was clear that computer networks would have driven the information revolution, the Internet drew a lot of interest both from academia and from industry. Moreover, the demand for features that were not envisaged when the Internet was designed grew alongside with the size and complexity of the Internet itself. Routing, that is, ﬁnding a path in a network that interconnects a given source to a given destination, also needed to evolve accordingly: as soon as the Internet got into its commercial era, there was a strong demand for routing protocols that supported policies. Among the wide variety of routing protocols that can be found today in the Internet, the Border Gateway Protocol (BGP) is responsible for connecting large administrative domains (called Autonomous Systems, or ASes), each administering its own network. BGP conﬁguration languages allow network administrators to deﬁne ﬁne-grained policies to inﬂuence the selection and the dissemination of routes over the network, and is therefore classiﬁed as a policy-based interdomain routing protocol. BGP policies allow each AS to autonomously conﬁgure its network in order, e.g., to minimize the cost of routing traﬃc, or to optimize delay. Ideally, BGP was designed to let each administrative domain choose the best route (where “best” obviously has local signiﬁcance) given the alternatives proposed by neighboring ASes. Unfortunately, as it is often the case in other branches of computer science, many agents that independently pursue a local optimum do not always converge into a global optimum. In particular, it has been shown that there exist sets of BGP policies that cannot be satisﬁed at the same time, and trap the protocol in inﬁnite oscillations in which a stable routing choice is never reached. This fact spurred lots of research eﬀorts towards techniques to characterize, discover, mitigate and eliminate BGP instabilities. This thesis presents novel research contributions as well as related work regarding the characterization and the detection of BGP instabilities under a common framework. We cover both the necessary theoretical background, as well as practical techniques and methodologies to analyze real BGP networks. First, we tackle the problem of ﬁnding a suitable model for studying BGP oscillations. This is indeed a nontrivial task, as many of the simplifying assumptions that have often been made to ease the analysis provably make the model unable to capture certain kinds of routing instabilities. Besides allowing us to pick the model that is best ﬁt to study oscillations, the insight provided by our study also makes us able to review related work with a deeper understanding of the interplay among many diﬀerent models for BGP. This thesis makes three main contributions. First, we show a suﬃcient and necessary condition for BGP safety under ﬁltering, that is, the property of a BGP network to have guaranteed convergence under arbitrary ﬁltering of BGP routes. To the best of our knowledge, this is the ﬁrst complete characterization of safety under ﬁltering. We exploit this ﬁnding to show a debugging technique that is able to spot the potential trouble points of a network by just analyzing two diﬀerent routing states. Second, we study the possibility of manipulating internal BGP (iBGP) attributes. While in general such a practice exacerbates the BGP stability problem, adherence to simple guidelines ensures BGP stability while still providing some beneﬁts in terms, e.g., of traﬃc engineering capabilities. Third, we devise and implement an algorithm which is able to tell whether a given BGP network is stable. This algorithm is provably free from false positives, and it is able to pinpoint the trouble points of a potentially unstable network. We show that this algorithm, together with techniques to perform some preprocessing on BGP networks, can be implemented eﬃciently enough to deal with Internet scale BGP topologies as well as very large iBGP networks. Finally, we propose a BGP monitoring system that is able to collect BGP data in such a way to enable the analysis of what-if scenarios.

Adaptive techiniques in web-based education

2011-10-13T23:37:58Z

Adaptive techiniques in web-based education Vaste, Giulia 2010-03-30 This dissertation proposes the use of artiﬁcial intelligence methodologies and techniques for providing personalization of web-based courses. Almost all web-based systems try to carry out personalization in order to be more useful, more attractive, and more eﬃcient in fulﬁlling user’s needs. However, personalization has a cost in terms of background operations, for instance in educational systems in terms of teacher’s effort. What is a reasonable compromise between soﬁsticated personalization methodologies and their realization? Is it possible to provide personalization with an acceptable effort for the domain expert responsible for contents producing? This dissertation focuses on these questions, considering in particular systems for web-based education, and proposes a methodology that aims to carry out a reasonable compromise between an effective personalization from the student’s point of view and from the teacher’s point of view, or, in general, from the user’s point of view and from the domain expert’s point of view. From the student’s point of view, personalization is provided on the basis of student’s knowledge and learning styles and guiding the student during the fruition of the course, like a teacher could do: proposing a sequence of contents suitable for the student at the beginning of the course and performing recovery strategies, during the fruition of the course, if the study does not proceed as it should. From the teacher’s point of view personalized courses are generated automatically, on the basis of the student model. The teacher is required to specify few metadata, necessary for characterizing learning materials, such as prerequisite relations and suitability of contents for a given type of student. The teacher is helped by a graphical interface, allowing a global vision of the course, and he can express didactic preferencies, such as the level of the course, according to the Bloom’s Taxonomy. The effort required to the teacher is as near as possible to his “way of thinking”: prerequisite relations are generally deﬁned, even if implicitly, when a course is arranged; learning materials are tagged, according to the Felder and Silverman’s learning styles model. Ad- iv herence to this model is not, however, a strict constraint for the teacher: the estimate of student’s learning styles is in fact updated taking into account the teacher’s tagging of the learning materials. In this way, relevance is given to the matching between the teacher’s tagging of the learning materials and the student’s way of learning: if the student studies a given material with success, the material is considered suitable for the student and his learning styles are updated towards the weights given by the teacher to that material. On the basis of the above-mentioned methodologies the LS-Plan system has been proposed. LS-Plan provides educational hypermedia with adaptivity; it has been integrated in the Lecomps educational hypermedia in order to carry out evaluations both from the student’s and from the teacher’s point of view. A layered and an as a whole evaluation, together with evaluations of teacher’s functionalities, have been performed and have shown positive results. Different approaches have been proposed in the literature for curriculum sequencing, that is “help the student to ﬁnd an “optimal path” through the learning material”. According to the aim of providing support for teachers in performing personalization, a suitable system, LS-Lab, for comparing different algorithms has been proposed. LS-Lab provides a uniform environment in which several algorithms can be compared using the same input, i.e. the same set of didactic materials, the same sample student models and the same learning objective. The subjective comparison, made by teachers or domain experts, is supported by some metrics and by the visualization of the produced sequences. According to the necessity of providing an easy-to-use personalization for background actors, the personalization methodologies proposed for the educational domain have been applied also for cultural visits personalization. Analogies and differences between course personalization and cultural visits personalization have been detected and the framework for course personalization has been adapted and enhanced taking into account visitor’s interests.

A methodology for generating grammars for multimodal languages

2011-07-12T00:03:19Z

A methodology for generating grammars for multimodal languages D'Ulizia, Arianna 2009-04-02 Human communication is naturally multimodal. People normally interact through several communication channels, such as gesture, drawing, handwriting, facial expressions, gaze in combination with speech or speech only, which is the prevalent modality. This synergistic use of multiple interaction channels makes human communication flexible, natural and robust. In the last years several efforts have been made to endow computer interface with similar flexibility, naturalness and robustness. The research presented in this thesis represents one of this effort. The main contributions of this thesis are twofold. First of all, it provides a methodology for multimodal language definition that is general enough to be applicable for whatever modalities and in whichever domains. Secondly, it provides an efficient incremental learning algorithm that, following an approach "by example", allows to generate the production rules of the defined grammar starting from the acceptable multimodal sentences.

Coherence problem between Business Rules and Business Processes

2011-07-12T00:03:16Z

Coherence problem between Business Rules and Business Processes Lezoche, Mario 2009-04-02 Business Process (BP) transformation is a key aspect of BP lifecycle. There are several reasons that may cause BP modi.cations. Among these, particularly important are the changes of the enterprise organization and operation strategies, which can be captured by business rules (BRs). This work focuses on a BP-based organization that is regulated by a set of BRs: such BPs and BRs need to be globally consistent (and have to be maintained consistent after any changes). In this thesis is presented an ontological approach capable of representing BRs and BPs in a coherent way. Then, the objective is identifying all processes in the BP repository that are (or have become) inconsistent with the BRs and thus need to be changed to reestablish the overall consistency.

Dealing with multimodal languages ambiguities : a classification and solution method

2011-07-12T00:03:15Z

Dealing with multimodal languages ambiguities : a classification and solution method Caschera, Maria Chiara 2009-04-02 Starting from discussing the problem of ambiguity and its pervasiveness on communication processes, this thesis dissertation faces problems of classifying and solving ambiguities for multimodal languages. This thesis gives an overview of the works proposed in literature about ambiguities in natural language and visual languages and discusses some existing proposals on multimodal ambiguities. An original classification of multimodal ambiguities has been defined using a linguistic perspective, introducing the notions of multimodal grammar, multimodal sentence and multimodal language. An overview of methods that the literature proposes for avoiding and detecting ambiguities has been done. These methods are grouped into: prevention of ambiguities, a-posterior resolution and approximation resolution methods. The analysis of these methods has underlined the suitability of Hidden Markov Models (HMMs) for disambiguation processes. However, due to the complexity of ambiguities for multimodal interaction, this thesis uses the Hierarchical Hidden Markov Models to manage the semantic and syntactic classes of ambiguities for multimodal sentences; this choice permits to operate at different levels going from the terminal elements to the multimodal sentence. The proposed methods for classifying and solving multimodal ambiguities have been used to design and implement two software modules. The experimental results of these modules have underlined a good level of accuracy during the classification and solution processes of multimodal ambiguities.

Root cause analysis and forensics in interdomain routing: models, methodologies and tools

2011-07-05T00:03:14Z

Root cause analysis and forensics in interdomain routing: models, methodologies and tools Refice, Tiziana 2009-04-02 The Internet is an interconnection of administrative domains called Autonomous Systems (ASes). Each AS contains one or multiple destination networks and each network is identified by an IP prefix. The Border Gateway Protocol (BGP) [RLH06] is the de-facto standard routing protocol used to exchange reachability information among ASes and a BGP session between two distinct ASes is called peering. Each AS learns through BGP its "best" route towards each destination in the Internet, updates it in response to network events (e.g., link failures, router resets, or policy changes) and propagates the change by BGP messages called updates. The propagation of BGP updates can be par- tially controlled via routing policy specifications. In order to investigate the Internet behavior over time, several repositories provide historical data. Since 1997 and 1999, respectively, the University of Oregon RouteViews Project (RV ) [roua] and the RIPE NCC Routing Infor- mation Service (RIS) [roub] spread worldwide passive monitors (or vantage points), which continuously gather BGP routing data from the Internet, per- manently store them and make them publicly available. Currently, there are about 800 such monitors. Also, in 1995 the Internet Routing Registry (IRR) was established and started collecting inter-AS routing policies of many of the networks in the Internet with the main purpose to promote stability, consis- tency, and security of the global interdomain routing. As the Internet becomes a more and more critical infrastructure, the need for understanding and (at least at some extent) controlling the interdomain routing increases. Internet Service Providers (ISPs) - in order to improve the quality of service offered to their customers - want to monitor the reachability of specific prefixes, check the effectiveness of their own routing policies, and assess the impact of traffic engineering configurations. In this context, it is crucial to be able to detect and debug misconfigurations or faults, in order to possibly fix them. More generally, the problem of identifying Internet events, locating their root causes, and understanding their dynamics is attracting increasing attention from both researchers and network operators. However, despite the large amount of research effort, routing dynamics di- agnosis remains very difficult for several reasons: (i) The system has a sheer size. As of December 2008, there are about 280, 000 prefixes and more than 30, 000 Autonomous Systems densely connected between each other. (ii) The Internet is highly dynamic. In fact, RIS' and RV's monitors currently receive an average of about 1, 500 BGP updates per minute, with peaks of more than 50, 000 updates per minute. (iii) Due to complex interconnects among ASes and routing policies, the effects of network events are often separated (both in time and space) from their causes and different vantage points record different data in response to the same routing changes. Also, multiple routing events can occur simultaneously. Overall, given such size and dynamics, "naive" ap- proaches to extract relevant information from the Internet routing data are neither effective nor efficient. Therefore, both researchers and network operators interested in understand- ing the interdomain routing have to cope with several major challenges. First, in order to deal with such a huge and complex network, they need to define what to measure, i.e., they need a model of the Internet routing that captures the main dynamics, filtering out the "noise" (e.g., routing changes that do not provide information relevant to the identification of network events). Based on such model, they need a methodology that, given the currently available data sources, detects network events and infers when and where they hap- pened. Furthermore, they need tools that efficiently handle the huge amount of data, support the analysis of the network behavior over time, and provide real-time information in order to spot and possibly fix outages as soon as they occur. Since the analysis of network events often requires manual work, ef- fective paradigms for the visualization of routing data are also very helpful. Previous works leave most of these problems still open. The research work described throughout this thesis addresses these prob- lems and proposes approaches to (at least partially) solve them. Namely, this thesis presents the following contributions. This thesis illustrates a new perspective to drive the analysis of the Internet dynamics without getting lost in the huge BGP dataset. Basically, while previ- ous works usually address the root cause analysis from a "global perspective" - i.e., by taking into account the dynamics of the whole Internet and trying to identify major events affecting it - this thesis tackles the same problem with an ISP-oriented approach: it assumes that ISPs are usually more interested in the reachability of their own prefixes, rather than in the status of the whole Network; hence, it focuses the analysis on user-specified prefixes and corre- lates their behaviors to the global Internet dynamics. In particular, this thesis formally models the Internet as a flow-based system, where monitors are the sources of the flows and ASes originating BGP updates are the sinks. This thesis also defines a methodology which correlates such flow variations to rout- ing changes in order to spot network events and the root causes that triggered them. Furthermore, BGPath has been developed to support this methodol- ogy and this thesis describes its main features. BGPath is a publicly available tool that uses BGP data collected by the RIS and the RV projects and pro- vides the user with routing information from both a single and cross-vantage point views. BGPath also assesses the reliability of the collection system, in order to avoid measurement artifacts. The algorithms BGPath relies on are shown to efficiently process huge streams of BGP data, fulfilling nearly-real time constraints. While the ISP-oriented approach presented in this thesis gives a good in- sight on both major and minor events affecting specific portions of the Internet, approaching the root cause analysis problem from a "global perspective" usu- ally does not provide with such fine-grained results. On the other hand, the global approach is critical to identify major interdomain events, without any a- priori knowledge of the prefixes and/or the ASes involved. This thesis explores this perspective too. Specifically, this thesis proposes a novel methodology based on the Principal Component Analysis (PCA), a well-known statistical technique that is commonly used to reduce the number of dimensions of multi- dimensional datasets in order to highlight the most significant trends of the data. Since the interdomain routing dataset is inherently multi-dimensional (in time, space, prefixes, observation points, ...), this thesis suggests to apply the PCA to this dataset in order to identify the most significant contributors to the Internet dynamics. BGP data collected by RIS' and RV's monitors provide a detailed view of the actual status of the interdomain routing. However, it does not report all the inter-AS peering relationships which are not active. For example, in "normal" conditions, backup links do not appear in the routing tables. Still, in order to understand the reasons behind some network events and to pre- dict the evolution of the routing when an event occurs, such information is actually very important. To cope with the intrinsic limitations of the RIS and RV dataset, this thesis analyzes the data stored in the Internet Routing Reg- istry and describes how to extract peering relationships from routing policies collected within. Moreover, the proposed approach specifies how to solve in- consistencies among the distinct databases the IRR consists of. The obtained results show that - even though the IRR data is often out-of-date, it still pro- vides a quite unique amount of topological information which usually does not appear in the global routing. The research work described in the thesis relies on the assumption that Internet is a graph where ASes are atomic entities in the interdomain rout- ing. However, recent papers [MFM+ 06, MUF+ 07] show that such a model can mislead the understanding of the global routing behavior. Thus, this thesis in- vestigates this problem by measuring the route diversity that can be observed by passive remote vantage points, defining a methodology to compute it from a dynamic BGP dataset and characterizing it in terms of location of ASes in the Internet customer-provider hierarchy and choice of monitors. The thesis documents forensic analysis of two well-know events that oc- curred at the beginning of 2007, where models, methodologies and tools de- scribed in the thesis are exemplified using real case studies.

Outsourced storage services : authentication and security visualization

2011-07-05T00:03:38Z

Outsourced storage services : authentication and security visualization Palazzi, Bernardo 2009-04-02 We address the problem of authenticating data in outsourced, often un- trusted, services, when a user stores more or less confidential information in a remote service such as an online calendar, remote storage, outsourced DBMS, and others. How can outsourced data be proven authentic? Data authentication captures the security needs of many computing applications that save and use sensitive information in hostile remote distributed environments and its importance increases, given the current trend in modern system design towards outsourced services with minimal trust assumptions. Solutions should not only be provably secure, but efficient and easily implementable. This dissertation presents an extensive study of data authentication and introduces a general method, based on a security middleware, external to the service, that performs authentication operations in parallel with standard service functions to minimize the time overhead. We examine the problem for different services, and design efficient new techniques with authenticating general classes of operations, such as relational primitives, multidimensional queries and relational join and remote storage management. Another important issue that we cover in this dissertation is the security usability of outsourced services. In particular we analyze the information security visualization techniques and we address the problem of file permissions visualization. TrACE, a prototype tool based on a treemap is presented with an extensive user study to show the usability improvement of this tool.

Small Screens and Large Graphs: Area-Effcient Drawings of Planar Combinatorial Structures

2011-07-05T00:02:54Z

Small Screens and Large Graphs: Area-Effcient Drawings of Planar Combinatorial Structures Frati, Fabrizio 2009-04-02 Small Screens and Large Graphs: Area-Efficient Drawings of Planar Combinatorial Structures Fabrizio Frati Dipartimento di Informatica e Automazione - Roma Tre University Abstract Graphs are the most widely used data structures to represent relationships among objects. Maps, networks, circuits, molecules, compounds are a few examples of structures that are commonly represented by graphs. The clearest way to express the information conveyed in a graph is to visualize it. Namely, a drawing of a graph represents each object (in the graph terminology: vertex) of the graph as a point in the plane and each relationship (in the graph terminology: edge) between two objects as a line connecting the corresponding points. However, not every drawing can be regarded as a good representation of the graph. In fact, a drawing should be readable, that is, the human eye should be able to easily identify the relationships among the objects in the graph at the first glance to the drawing. Clearly, this is not a formal definition of what differentiates a good drawing from a bad drawing. However, a few topological and geometric features have been recognized and accepted as the criteria a drawing should satisfy in order to be readable. Planarity is probably the best characteristic a drawing can have. The absence of intersections between the edges of the graph allows a viewer to easily distinguish the line representing any edge and hence to immediately understand which are the vertices connected by the edge. From a geometric perspective, it would be preferable that edges are drawn as straight-lines, namely edges bending and repeatedly changing direction are detrimental for the readability of the drawing. When the straight-line requirement can not be met, it would be still desiderable to have edges drawn as poly-lines bending only a limited number of times. When the size of the graph to be represented is too large in order for the drawing to be constructed manually, there is a need for an algorithm automatically constructing such a drawing. Graph Drawing deals with the design of algorithms to automatically construct drawings of graphs. Usually a Graph Drawing algorithm takes as an input a graph, a set of requirements the drawing must satisfy (as being planar or having straight-line edges), and a set of aesthetics the drawing should satisfy as much as possible. The most important aesthetic a drawing should satisfy is probably the one of having a small area. In fact, automatic drawings usually have to be displayed on a computer screen of bounded size, hence they have to fit in the space available on the screen. The study of graph drawings in small area has been first motivated by the design of VLSI circuits and has attracted intense research efforts for almost thirty years now. In this thesis we deal with algorithms and bounds for drawing graphs in small area. We mainly deal with planar graphs (Part I of the thesis), series-parallel graphs and outerplanar graphs (Part II), trees (Part III), and clustered graphs (Part IV), and for each of these graph classes we consider the problem of obtaining drawings in small area under a large number of drawing conventions (e.g., straight-line, poly-line, orthogonal, upward). We design several algorithms for the construction of graph drawings in small area and we obtain lower bounds for the area requirements of several drawing styles. The graph classes and the drawing conventions we consider are among the most commonly used for applications. Nevertheless, the beauty of some combinatorial, topological, and geometric problems concerning the construction of graph drawings in small area justifies their study even when looking at them from a purely theoretical point of view. 1

Interoperability of Semantic Annotations

2011-07-05T00:03:25Z

Interoperability of Semantic Annotations Paolozzi, Stefano 2009-04-02 Abstract The Semantic Web is the new generation World Wide Web. It extends the Web by giving information a well defined meaning, allowing it to be pro- cessed by machines. This vision is going to become reality thanks to a set of technologies which have been specified and maintained by the World Wide Web Consortium (W3C), and more and more research efforts from the industry and the academia. Therefore, the basis for the Semantic Web are computer- understandable descriptions of resources. We can create such descriptions by annotating resources with metadata, resulting in "annotations" about that re- source. Semantic annotation is the creation of metadata and relations between them with the task of defining new methods of access to information and en- riching the potentialities of the ones already existent. The main goal is to have information on the Web, defined in such a way that its meaning could be explicitly interpreted also by automatic systems, not just by humans. There is huge amount of interesting and important information represented through semantic annotations, but there are still a lot of different formalisms showing a lack of standardization and a consequent need of interoperability. This growing need of interoperability in this field convinces us to extend our first proposal, strictly related to database models, in order to address also semantic annotations. Our proposal, mainly based on Model Management techniques, focuses on the problem of translating schemas and data between Semantic Web data models and the integration of those models with databases models that are a more rigid and well-defined structure. In this work we underline the main concepts of our approach discussing a proposal for the implementation of the model management operator Model- Gen, which translates schemas from one model to another focusing on semantic annotation context. The approach expresses the translation as Datalog rules and exposes the source and target of the translation in a generic relational dic- tionary. This makes the translation transparent, easy to customize and model- independent. The proposal includes automatic generation of translations as composition of basic steps.

Modeling and interoperability: a high level perspective

2011-07-05T00:02:49Z

Modeling and interoperability: a high level perspective Del Nostro, Pierluigi 2009-04-02 Abstract This thesis tackles modeling and interoperability issues in different con- texts. We started by studying different Semantic Web models with the goal of translating from one to another by means of a model independent approach. The metamodel approach that we follow is called MIDST and is based on the concept of supermodel, a generic model that we use to describe other models. We have extended this approach, to allow the interoperability between Seman- tic Web formalisms. MIDST leverage on a relational dictionary that we have exploited as a repository for RDF documents. The logical organization that we have defined, together with tuning techniques at the physical level, allows us to obtain a framework for storing and querying RDF, that produced great re- sults in terms of performance and scalability. Following the experience gained in modeling Semantic Web models, we have produced a new enhancement in MIDST expressivity, allowing the interchange of information between ontolo- gies and databases. Changing context, this thesis finally describe a framework for the modeling of time in data-intensive Web sites. We here developed a tool that allows to automatically generate the Web site as a consequence of the design choices.

Combinatorial structures for communication networks

2011-06-17T00:01:44Z

Combinatorial structures for communication networks Sperduto, Ezio 2009-04-02 This thesis deals with a class of theoretical problems arising in applications in communication networks. The dissertation is mainly divided in two parts. In the first part, we attempt to solve a set of survivability network design problems. Network survivability refers to the guarantees that a communication network provides in the event that one or more failures occur. An attack or failure can significantly reduce the capability of the communication network to efficiently deliver basic services to users. In several cases, when a failure occurs, the network operators are interested in restoring traffic by re-routing it through different links. Since re-routing traffic can be rather expensive and may cause delays in transmissions, a key property is that of requiring that traffic which is not affected by the failure is not redirected in failure situations. We study the problem of determining whether a given network, where the traffic is commonly routed on the edges of a shortest path tree (e.g. Ethernet networks with the Spanning Tree Protocol), may satisfy the above mentioned property. We provide computational complexity results for directed and undirected net- works. In particular, for the directed case, we prove that such problem is in general NP-hard and that it remains NP-hard also in some special cases. More- over, we show how to assign weights to the links of the network in order to configure a routing topology with the above mentioned property. In the second part of the thesis, we deal with a problem regarding broadcast- ing in telecommunication networks. We investigate a new version of the well known Minimum Broadcast Time problem which has been deeply studied in the past, since broadcasting is a basic primitive in the communication networks area. Fundamental requirements for a broadcast process are that it completes in the quickest way and that, at the end of the procedure, all the peers in the net- work are informed. In this thesis we deal with an objective function that takes into account the quality of the service associated with the broadcast, namely the minimization of the average broadcast time of the peers. We show that the considered version of the broadcast problem is an NP-hard problem. Indeed, the problem becomes polynomially solvable, if the instance graph is a tree. We also provide a distributed approximation algorithm for our version of the broadcast problem, in which every network node does not know the network topology.

Mathematical model and statistical learning of HIV- 1 genetic evolution mechanisms under drug pressure for treatment optimisation

2008-12-12T01:31:00Z

Mathematical model and statistical learning of HIV- 1 genetic evolution mechanisms under drug pressure for treatment optimisation Prosperi, Mattia 2008-04-07

The localization problem : From robotics to sensor networks

2008-12-12T01:30:50Z

The localization problem : From robotics to sensor networks Gasparri, Andrea 2008-04-07