Typed Abstraction of Complex Network Compositions

The heterogeneity and open nature of network systems make analysis of compositions of components quite challenging, making the design and implementation of robust network services largely inaccessible to the average programmer. We propose the development of a novel type system and practical type spaces which reflect simplified representations of the results and conclusions which can be derived from complex compositional theories in more accessible ways, essentially allowing the system architect or programmer to be exposed only to the inputs and output of compositional analysis without having to be familiar with the ins and outs of its internals. Toward this end we present the TRAFFIC (Typed Representation and Analysis of Flows For Interoperability Checks) framework, a simple flow-composition and typing language with corresponding type system. We then discuss and demonstrate the expressive power of a type space for TRAFFIC derived from the network calculus, allowing us to reason about and infer such properties as data arrival, transit, and loss rates in large composite network applications.

Safe Compositional Specification of Networking Systems: TRAFFIC The Language and Its Type Checking

This paper formally defines the operational semantic for TRAFFIC, a specification language for flow composition applications proposed in BUCS-TR-2005-014, and presents a type system based on desired safety assurance. We provide proofs on reduction (weak-confluence, strong-normalization and unique normal form), on soundness and completeness of type system with respect to reduction, and on equivalence classes of flow specifications. Finally, we provide a pseudo-code listing of a syntax-directed type checking algorithm implementing rules of the type system capable of inferring the type of a closed flow specification.

An Invariant Representation for Matching Trajectories across Uncalibrated Video Streams

We introduce a view-point invariant representation of moving object trajectories that can be used in video database applications. It is assumed that trajectories lie on a surface that can be locally approximated with a plane. Raw trajectory data is first locally approximated with a cubic spline via least squares fitting. For each sampled point of the obtained curve, a projective invariant feature is computed using a small number of points in its neighborhood. The resulting sequence of invariant features computed along the entire trajectory forms the view invariant descriptor of the trajectory itself. Time parametrization has been exploited to compute cross ratios without ambiguity due to point ordering. Similarity between descriptors of different trajectories is measured with a distance that takes into account the statistical properties of the cross ratio, and its symmetry with respect to the point at infinity. In experiments, an overall correct classification rate of about 95% has been obtained on a dataset of 58 trajectories of players in soccer video, and an overall correct classification rate of about 80% has been obtained on matching partial segments of trajectories collected from two overlapping views of outdoor scenes with moving people and cars.

View Registration Using Interesting Segments of Planar Trajectories

We introduce a method for recovering the spatial and temporal alignment between two or more views of objects moving over a ground plane. Existing approaches either assume that the streams are globally synchronized, so that only solving the spatial alignment is needed, or that the temporal misalignment is small enough so that exhaustive search can be performed. In contrast, our approach can recover both the spatial and temporal alignment. We compute for each trajectory a number of interesting segments, and we use their description to form putative matches between trajectories. Each pair of corresponding interesting segments induces a temporal alignment, and defines an interval of common support across two views of an object that is used to recover the spatial alignment. Interesting segments and their descriptors are defined using algebraic projective invariants measured along the trajectories. Similarity between interesting segments is computed taking into account the statistics of such invariants. Candidate alignment parameters are verified checking the consistency, in terms of the symmetric transfer error, of all the putative pairs of corresponding interesting segments. Experiments are conducted with two different sets of data, one with two views of an outdoor scene featuring moving people and cars, and one with four views of a laboratory sequence featuring moving radio-controlled cars.

Foreground Object Segmentation from Binocular Stereo Video

Moving cameras are needed for a wide range of applications in robotics, vehicle systems, surveillance, etc. However, many foreground object segmentation methods reported in the literature are unsuitable for such settings; these methods assume that the camera is fixed and the background changes slowly, and are inadequate for segmenting objects in video if there is significant motion of the camera or background. To address this shortcoming, a new method for segmenting foreground objects is proposed that utilizes binocular video. The method is demonstrated in the application of tracking and segmenting people in video who are approximately facing the binocular camera rig. Given a stereo image pair, the system first tries to find faces. Starting at each face, the region containing the person is grown by merging regions from an over-segmented color image. The disparity map is used to guide this merging process. The system has been implemented on a consumer-grade PC, and tested on video sequences of people indoors obtained from a moving camera rig. As can be expected, the proposed method works well in situations where other foreground-background segmentation methods typically fail. We believe that this superior performance is partly due to the use of object detection to guide region merging in disparity/color foreground segmentation, and partly due to the use of disparity information available with a binocular rig, in contrast with most previous methods that assumed monocular sequences.

An Adaptive Management Approach to Resolving Policy Conflicts

The Border Gateway Protocol (BGP) is the current inter-domain routing protocol used to exchange reachability information between Autonomous Systems (ASes) in the Internet. BGP supports policy-based routing which allows each AS to independently define a set of local policies on which routes it accepts and advertises from/to other networks, as well as on which route it prefers when more than one route becomes available. However, independently chosen local policies may cause global conflicts, which result in protocol divergence. In this paper, we propose a new algorithm, called Adaptive Policy Management Scheme(APMS), to resolve policy conflicts in a distributed manner. Akin to distributed feedback control systems, each AS independently classifies the state of the network as either conflict-free or potentially conflicting by observing its local history only (namely, route flaps). Based on the degree of measured conflicts, each AS dynamically adjusts its own path preferences---increasing its preference for observably stable paths over flapping paths. APMS also includes a mechanism to distinguish route flaps due to topology changes, so as not to confuse them with those due to policy conflicts. A correctness and convergence analysis of APMS based on the sub-stability property of chosen paths is presented. Implementation in the SSF network simulator is performed, and simulation results for different performance metrics are presented. The metrics capture the dynamic performance (in terms of instantaneous throughput, delay, etc.) of APMS and other competing solutions, thus exposing the often neglected aspects of performance.

Fishing quota markets

In 1986, New Zealand responded to the open-access problem by establishing the world's largest individual transferable quota (ITQ) system. Using a 15-year panel dataset from New Zealand that covers 33 species and more than 150 markets for fishing quotas, we assess trends in market activity, price dispersion, and the fundamentals determining quota prices. We find that market activity is sufficiently high in the economically important markets and that price dispersion has decreased. We also find evidence of economically rational behavior through the relationship between quota lease and sale prices and fishing output and input prices, ecological variability, and market interest rates. Controlling for these factors, our results show a greater increase in quota prices for fish stocks that faced significant reductions, consistent with increased profitability due to rationalization. Overall, this suggests that these markets are operating reasonably well, implying that ITQs can be effective instruments for efficient fisheries management. © 2004 Elsevier Inc. All rights reserved.

Physiological levels of PTEN control the size of the cellular Ins(1,3,4,5,6)P5 pool

To understand how a signaling molecule's activities are regulated, we need insight into the processes controlling the dynamic balance between its synthesis and degradation. For the Ins(1,3,4,5,6)P5 signal, this information is woefully inadequate. For example, the only known cytosolic enzyme with the capacity to degrade Ins(1,3,4,5,6)P5 is the tumour-suppressor PTEN [J.J. Caffrey, T. Darden, M.R. Wenk, S.B. Shears, FEBS Lett. 499 (2001) 6 ], but the biological relevance has been questioned by others [E.A. Orchiston, D. Bennett, N.R. Leslie, R.G. Clarke, L. Winward, C.P. Downes, S.T. Safrany, J. Biol. Chem. 279 (2004) 1116 ]. The current study emphasizes the role of physiological levels of PTEN in Ins(1,3,4,5,6)P5 homeostasis. We employed two cell models. First, we used a human U87MG glioblastoma PTEN-null cell line that hosts an ecdysone-inducible PTEN expression system. Second, the human H1299 bronchial cell line, in which PTEN is hypomorphic due to promoter methylation, has been stably transfected with physiologically relevant levels of PTEN. In both models, a novel consequence of PTEN expression was to increase Ins(1,3,4,5,6)P5 pool size by 30-40% (p<0.01); this response was wortmannin-insensitive and, therefore, independent of the PtdIns 3-kinase pathway. In U87MG cells, induction of the G129R catalytically inactive PTEN mutant did not affect Ins(1,3,4,5,6)P(5) levels. PTEN induction did not alter the expression of enzymes participating in Ins(1,3,4,5,6)P5 synthesis. Another effect of PTEN expression in U87MG cells was to decrease InsP6 levels by 13% (p<0.02). The InsP6-phosphatase, MIPP, may be responsible for the latter effect; we show that recombinant human MIPP dephosphorylates InsP6 to D/L-Ins(1,2,4,5,6)P5, levels of which increased 60% (p<0.05) following PTEN expression in U87MG cells. Overall, our data add higher inositol phosphates to the list of important cellular regulators [Y. Huang, R.P. Wernyj, D.D. Norton, P. Precht, M.C. Seminario, R.L. Wange, Oncogene, 24 (2005) 3819 ] the levels of which are modulated by expression of the highly pleiotropic PTEN protein.

Construyendo matemáticas con nuestro abanico: funciones sinusoidales

El estudio de las funciones sinusoidales en la secundaria y en el bachillerato se suele realizar desde una perspectiva alejada de la experimentación y la intuición. En este artículo pretendemos mostrar una propuesta de trabajo para introducir las funciones sinusoidales de una manera intuitiva y experimental, en una fase previa a su estudio analítico, a través de algunos ejemplos de la vida cotidiana como andar, parpadear, fregar el suelo o hacer abdominales.

Forward and inverse transport of particulate matter and gaseous pollutants affecting the region bordering the English Channel

The ATTMA "Aerosol Transport in the Trans-Manche Atmosphere" project investigates the transportation and dispersion of air pollutants across the English Channel, in collaboration with local authorities and other Universities in Southern England and Northern France. The research is concerned with both forward and inverse (receptor based) tracking. Two alternative dispersion simulation methods are used: (a) Lagrangian Particle Dispersion (LPD) models, (b) Eulerian Finite Volume type models. This paper is concerned with part (a), the simulations based on LPD models. Two widely applied LPD models are used and compared. Since in many observed episodes the source of pollution is traced outside the region of interest, long range, trans-continental transport is also investigated.

Two-machine flow shop scheduling problems with no-wait jobs

In this paper we provide a fairly complete complexity classification of various versions of the two-machine permutation flow shop scheduling problem to minimize the makespan in which some of the jobs have to be processed with no-wait in process. For some version, we offer a fully polynomial-time approximation scheme and a 43-approximation algorithm.

Spatial variability of air pollution in the vicinity of a permanent monitoring station in central Paris

The strong spatial and temporal variability of traffic-related air pollution detected at roadside locations in a number of European cities has raised the question of how representative the site and time period of air quality measurements actually can be. To address this question, a 7-month sampling campaign was carried out on a major road axis (Avenue Leclerc) leading to a very busy intersection (Place Basch) in central Paris, covering the surroundings of a permanent air quality monitoring station. This station has recorded the highest CO and NOx concentrations during recent years in the region of Paris. Diffusive BTX samplers as well as a mobile monitoring unit equipped with real-time CO, NOx and O3 analysers and meteorological instruments were used to reveal the small-scale pollution gradients and their temporal trends near the permanent monitoring station. The diffusive measurements provided 7-day averages of benzene, toluene, xylene and other hydrocarbons at different heights above the ground and distances from the kerb covering summer and winter periods. Relevant traffic and meteorological data were also obtained on an hourly basis. Furthermore, three semiempirical dispersion models (STREET-SRI, OSPM and AEOLIUS) were tested for an asymmetric canyon location in Av. Leclerc. The analysis of this comprehensive data set has helped to assess the representativeness of air quality monitoring information.

[Review] M. Feistauer, J. Felcman, I. Straskbraba, Mathematical and Computational Methods for Compressible Flow, Oxford Science Publication, Oxford, ISBN 0198505884, 2004 (535pp.)

The growth of computer power allows the solution of complex problems related to compressible flow, which is an important class of problems in modern day CFD. Over the last 15 years or so, many review works on CFD have been published. This book concerns both mathematical and numerical methods for compressible flow. In particular, it provides a clear cut introduction as well as in depth treatment of modern numerical methods in CFD. This book is organised in two parts. The first part consists of Chapters 1 and 2, and is mainly devoted to theoretical discussions and results. Chapter 1 concerns fundamental physical concepts and theoretical results in gas dynamics. Chapter 2 describes the basic mathematical theory of compressible flow using the inviscid Euler equations and the viscous Navier–Stokes equations. Existence and uniqueness results are also included. The second part consists of modern numerical methods for the Euler and Navier–Stokes equations. Chapter 3 is devoted entirely to the finite volume method for the numerical solution of the Euler equations and covers fundamental concepts such as order of numerical schemes, stability and high-order schemes. The finite volume method is illustrated for 1-D as well as multidimensional Euler equations. Chapter 4 covers the theory of the finite element method and its application to compressible flow. A section is devoted to the combined finite volume–finite element method, and its background theory is also included. Throughout the book numerous examples have been included to demonstrate the numerical methods. The book provides a good insight into the numerical schemes, theoretical analysis, and validation of test problems. It is a very useful reference for applied mathematicians, numerical analysts, and practice engineers. It is also an important reference for postgraduate researchers in the field of scientific computing and CFD.

Matching search in fractal video compression and its parallel implementation in distributed computing environments

Fractal video compression is a relatively new video compression method. Its attraction is due to the high compression ratio and the simple decompression algorithm. But its computational complexity is high and as a result parallel algorithms on high performance machines become one way out. In this study we partition the matching search, which occupies the majority of the work in a fractal video compression process, into small tasks and implement them in two distributed computing environments, one using DCOM and the other using .NET Remoting technology, based on a local area network consists of loosely coupled PCs. Experimental results show that the parallel algorithm is able to achieve a high speedup in these distributed environments.