OpenRaiser/Intern-Atlas huggingface dataset:
Ethernet Topology Discovery: A Survey
Venue: arXiv cs.NI 2009
Year: 2009

Ethernet networks have undergone impressive growth since the past few decades. This growth can be appreciated in terms of the equipment, such as switches and links, that have been added, as well as in the number of users that it supports. In parallel to this expansion, over the past decade the networking research community has shown a growing interest in discovering and analyzing the Ethernet topology. Research in this area has concentrated on the theoretical analysis of Ethernet topology as well as developing tools and methods for mapping the network layout. These efforts have brought us to a crucial juncture for Ethernet topology measurement infrastructures: while, previously, these were both small (in terms of number of measurement points), we are starting to see the deployment of large-scale distributed systems composed of hundreds or thousands of monitors. As we look forward to this next generation of systems, we take stock of what has been achieved so far. In this survey, we discuss past and current mechanisms for discovering the Ethernet topology from theoretical and practical prospective. In addition to discovery techniques, we provide insights into some of the well known open issues related to Ethernet topology discovery.
COMMENTARY ON: Citing and Reading Behavours in High-Energy Physics (arXiv:0906.5418)
Venue: arXiv cs.DL 2009
Year: 2009

Evidence confirming that OA increases impact will not be sufficient to induce enough researchers to provide OA; only mandates from their institutions and funders can ensure that. HEP researchers continue to submit their papers to peer-reviewed journals, as they always did, depositing both their unrefereed preprints and their refereed postprints. None of that has changed. In fields like HEP and astrophysics, the journal affordability/accessibility problem is not as great as in many other fields, where it the HEP Early Access impact advantage translates into the OA impact advantage itself. Almost no one has ever argued that Gold OA provides a greater OA advantage than Green OA. The OA advantage is the OA advantage, whether Green or Gold.
Breaking a Chaotic Cryptographic Scheme Based on Composition Maps
Venue: arXiv cs.CR 2009
Year: 2009

Recently, a chaotic cryptographic scheme based on composition maps was proposed. This paper studies the security of the scheme and reports the following findings: 1) the scheme can be broken by a differential attack with $6+\lceil\log_L(MN)\rceil$ chosen-plaintext, where $MN$ is the size of plaintext and $L$ is the number of different elements in plain-text; 2) the scheme is not sensitive to the changes of plaintext; 3) the two composition maps do not work well as a secure and efficient random number source.
A Mathematical Unification of Geometric Crossovers Defined on Phenotype Space
Venue: arXiv cs.NE 2009
Year: 2009

Geometric crossover is a representation-independent definition of crossover based on the distance of the search space interpreted as a metric space. It generalizes the traditional crossover for binary strings and other important recombination operators for the most frequently used representations. Using a distance tailored to the problem at hand, the abstract definition of crossover can be used to design new problem specific crossovers that embed problem knowledge in the search. This paper is motivated by the fact that genotype-phenotype mapping can be theoretically interpreted using the concept of quotient space in mathematics. In this paper, we study a metric transformation, the quotient metric space, that gives rise to the notion of quotient geometric crossover. This turns out to be a very versatile notion. We give many example applications of the quotient geometric crossover.
Registration of Standardized Histological Images in Feature Space
Venue: arXiv cs.CV 2009
Year: 2009

In this paper, we propose three novel and important methods for the registration of histological images for 3D reconstruction. First, possible intensity variations and nonstandardness in images are corrected by an intensity standardization process which maps the image scale into a standard scale where the similar intensities correspond to similar tissues meaning. Second, 2D histological images are mapped into a feature space where continuous variables are used as high confidence image features for accurate registration. Third, we propose an automatic best reference slice selection algorithm that improves reconstruction quality based on both image entropy and mean square error of the registration process. We demonstrate that the choice of reference slice has a significant impact on registration error, standardization, feature space and entropy information. After 2D histological slices are registered through an affine transformation with respect to an automatically chosen reference, the 3D volume is reconstructed by co-registering 2D slices elastically.
New Binomial Bent Function over the Finite Fields of Odd Characteristic
Venue: arXiv cs.DM 2009
Year: 2009

The $p$-ary function $f(x)$ mapping $\mathrm{GF}(p^{4k})$ to $\mathrm{GF}(p)$ given by $f(x)={\rm Tr}_{4k}\big(x^{p^{3k}+p^{2k}-p^k+1}+x^2\big)$ is proven to be a weakly regular bent function and the exact values of its Walsh transform coefficients are found. The proof is based on a few new results in the area of exponential sums and polynomials over finite fields that may also be interesting as independent problems.
Measuring Password Strength: An Empirical Analysis
Venue: arXiv cs.CR 2009
Year: 2009

We present an in-depth analysis on the strength of the almost 10,000 passwords from users of an instant messaging server in Italy. We estimate the strength of those passwords, and compare the effectiveness of state-of-the-art attack methods such as dictionaries and Markov chain-based techniques. We show that the strength of passwords chosen by users varies enormously, and that the cost of attacks based on password strength grows very quickly when the attacker wants to obtain a higher success percentage. In accordance with existing studies we observe that, in the absence of measures for enforcing password strength, weak passwords are common. On the other hand we discover that there will always be a subset of users with extremely strong passwords that are very unlikely to be broken. The results of our study will help in evaluating the security of password-based authentication means, and they provide important insights for inspiring new and better proactive password checkers and password recovery tools.
Investigating the Change of Web Pages' Titles Over Time
Venue: arXiv cs.IR 2009
Year: 2009

Inaccessible web pages are part of the browsing experience. The content of these pages however is often not completely lost but rather missing. Lexical signatures (LS) generated from the web pages' textual content have been shown to be suitable as search engine queries when trying to discover a (missing) web page. Since LSs are expensive to generate, we investigate the potential of web pages' titles as they are available at a lower cost. We present the results from studying the change of titles over time. We take titles from copies provided by the Internet Archive of randomly sampled web pages and show the frequency of change as well as the degree of change in terms of the Levenshtein score. We found very low frequencies of change and high Levenshtein scores indicating that titles, on average, change little from their original, first observed values (rooted comparison) and even less from the values of their previous observation (sliding).
Optimization of Synthesis Oversampled Complex Filter Banks
Venue: arXiv cs.IT 2009
Year: 2009

An important issue with oversampled FIR analysis filter banks (FBs) is to determine inverse synthesis FBs, when they exist. Given any complex oversampled FIR analysis FB, we first provide an algorithm to determine whether there exists an inverse FIR synthesis system. We also provide a method to ensure the Hermitian symmetry property on the synthesis side, which is serviceable to processing real-valued signals. As an invertible analysis scheme corresponds to a redundant decomposition, there is no unique inverse FB. Given a particular solution, we parameterize the whole family of inverses through a null space projection. The resulting reduced parameter set simplifies design procedures, since the perfect reconstruction constrained optimization problem is recast as an unconstrained optimization problem. The design of optimized synthesis FBs based on time or frequency localization criteria is then investigated, using a simple yet efficient gradient algorithm.
Artificial Dendritic Cells: Multi-faceted Perspectives
Venue: arXiv cs.AI 2009
Year: 2009

Dendritic cells are the crime scene investigators of the human immune system. Their function is to correlate potentially anomalous invading entities with observed damage to the body. The detection of such invaders by dendritic cells results in the activation of the adaptive immune system, eventually leading to the removal of the invader from the host body. This mechanism has provided inspiration for the development of a novel bio-inspired algorithm, the Dendritic Cell Algorithm. This algorithm processes information at multiple levels of resolution, resulting in the creation of information granules of variable structure. In this chapter we examine the multi-faceted nature of immunology and how research in this field has shaped the function of the resulting Dendritic Cell Algorithm. A brief overview of the algorithm is given in combination with the details of the processes used for its development. The chapter is concluded with a discussion of the parallels between our understanding of the human immune system and how such knowledge influences the design of artificial immune systems.
The Basic Discrete Hilbert Transform with an Information Hiding Application
Venue: arXiv cs.CR 2009
Year: 2009

This paper presents several experimental findings related to the basic discrete Hilbert transform. The errors in the use of a finite set of the transform values have been tabulated for the more commonly used functions. The error can be quite small and, for example, it is of the order of 10^{-17} for the chirp signal. The use of the discrete Hilbert transform in hiding information is presented.
On Descriptional Complexity of the Planarity Problem for Gauss Words
Venue: arXiv cs.FL 2009
Year: 2009

In this paper we investigate the descriptional complexity of knot theoretic problems and show upper bounds for planarity problem of signed and unsigned knot diagrams represented by Gauss words. Since a topological equivalence of knots can involve knot diagrams with arbitrarily many crossings then Gauss words will be considered as strings over an infinite (unbounded) alphabet. For establishing the upper bounds on recognition of knot properties, we study these problems in a context of automata models over an infinite alphabet.
Buffered Aloha with K-Exponential Backoff -- Part I: Stability and Throughput Analysis
Venue: arXiv cs.NI 2009
Year: 2009

This two-part paper series studies the performance of buffered Aloha networks with K-Exponential Backoff collision resolution algorithms. Part I focuses on stability and throughput analysis and Part II presents the delay analysis. In Part I, the buffered Aloha network is modeled as a multi-queue single-server system. We adopt a widely used approach in packet switching systems to decompose the multi-queue system into independent first-in-first-out (FIFO) queues, which are hinged together by the probability of success of head-of-line (HOL) packets. A unified method is devised to tackle the stability and throughput problems of K-Exponential Backoff with any cutoff phase K. We demonstrate that a network with K-Exponential Backoff can be stabilized if the retransmission factor q is properly selected. The stable region of q is characterized and illustrated via examples of Geometric Retransmission (K=1) and Exponential Backoff (K=infinity). With an increasing number of nodes n, we show that the stable region of Geometric Retransmission rapidly shrinks, and vanishes as n goes to infinity. In contrast, the stable region of Exponential Backoff does not vary with the network population n, implying that a stable throughput can be achieved in networks with Exponential Backoff even with an infinite number of nodes. All the analytical results presented in this paper series are verified by simulations.
Domination Problems in Nowhere-Dense Classes of Graphs
Venue: arXiv cs.DS 2009
Year: 2009

We investigate the parameterized complexity of generalisations and variations of the dominating set problem on classes of graphs that are nowhere dense. In particular, we show that the distance-d dominating-set problem, also known as the (k,d)-centres problem, is fixed-parameter tractable on any class that is nowhere dense and closed under induced subgraphs. This generalises known results about the dominating set problem on H-minor free classes, classes with locally excluded minors and classes of graphs of bounded expansion. A key feature of our proof is that it is based simply on the fact that these graph classes are uniformly quasi-wide, and does not rely on a structural decomposition. Our result also establishes that the distance-d dominating-set problem is FPT on classes of bounded expansion, answering a question of Ne{\v s}et{ř}il and Ossona de Mendez.
Dynamic Deformation of Uniform Elastic Two-Layer Objects
Venue: arXiv cs.GR 2009
Year: 2009

This thesis presents a two-layer uniform facet elastic object for real-time simulation based on physics modeling method. It describes the elastic object procedural modeling algorithm with particle system from the simplest one-dimensional object, to more complex two-dimensional and three-dimensional objects. The double-layered elastic object consists of inner and outer elastic mass spring surfaces and compressible internal pressure. The density of the inner layer can be set different from the density of the outer layer; the motion of the inner layer can be opposite to the motion of the outer layer. These special features, which cannot be achieved by a single layered object, result in improved imitation of a soft body, such as tissue's liquidity non-uniform deformation. The construction of the double-layered elastic object is closer to the real tissue's physical structure. The inertial behavior of the elastic object is well illustrated in environments with gravity and collisions with walls, ceiling, and floor. The collision detection is defined by elastic collision penalty method and the motion of the object is guided by the Ordinary Differential Equation computation. Users can interact with the modeled objects, deform them, and observe the response to their action in real time.
Full abstraction for nominal general references
Venue: arXiv cs.PL 2009
Year: 2009

Game semantics has been used with considerable success in formulating fully abstract semantics for languages with higher-order procedures and a wide range of computational effects. Recently, nominal games have been proposed for modelling functional languages with names. These are ordinary, stateful games cast in the theory of nominal sets developed by Pitts and Gabbay. Here we take nominal games one step further, by developing a fully abstract semantics for a language with nominal general references.
Distributed MIMO radar using compressive sampling
Venue: arXiv cs.IT 2009
Year: 2009

A distributed MIMO radar is considered, in which the transmit and receive antennas belong to nodes of a small scale wireless network. The transmit waveforms could be uncorrelated, or correlated in order to achieve a desirable beampattern. The concept of compressive sampling is employed at the receive nodes in order to perform direction of arrival (DOA) estimation. According to the theory of compressive sampling, a signal that is sparse in some domain can be recovered based on far fewer samples than required by the Nyquist sampling theorem. The DOAs of targets form a sparse vector in the angle space, and therefore, compressive sampling can be applied for DOA estimation. The proposed approach achieves the superior resolution of MIMO radar with far fewer samples than other approaches. This is particularly useful in a distributed scenario, in which the results at each receive node need to be transmitted to a fusion center.
A Survey on BGP Issues and Solutions
Venue: arXiv cs.NI 2009
Year: 2009

BGP is the de facto protocol used for inter-autonomous system routing in the Internet. Generally speaking, BGP has been proven to be secure, efficient, scalable, and robust. However, with the rapid evolving of the Internet in the past few decades, there are increasing concerns about BGS's ability to meet the needs of the Internet routing. There are two major limitations of BGP which are its failure to address several key security issues, and some operational related problems. The design and ubiquity of BGP have complicated past efforts at securing inter-domain routing. This paper surveys the past work related to BGP security and operational issues. We explore the limitations and advantages of proposed solutions in these two limitations.
Fingerprints in the Ether: Using the Physical Layer for Wireless Authentication
Venue: arXiv cs.CR 2009
Year: 2009

The wireless medium contains domain-specific information that can be used to complement and enhance traditional security mechanisms. In this paper we propose ways to exploit the fact that, in a typically rich scattering environment, the radio channel response decorrelates quite rapidly in space. Specifically, we describe a physical-layer algorithm that combines channel probing (M complex frequency response samples over a bandwidth W) with hypothesis testing to determine whether current and prior communication attempts are made by the same user (same channel response). In this way, legitimate users can be reliably authenticated and false users can be reliably detected. To evaluate the feasibility of our algorithm, we simulate spatially variable channel responses in real environments using the WiSE ray-tracing tool; and we analyze the ability of a receiver to discriminate between transmitters (users) based on their channel frequency responses in a given office environment. For several rooms in the extremities of the building we considered, we have confirmed the efficacy of our approach under static channel conditions. For example, measuring five frequency response samples over a bandwidth of 100 MHz and using a transmit power of 100 mW, valid users can be verified with 99% confidence while rejecting false users with greater than 95% confidence.
How much does a Hamiltonian cycle weigh?
Venue: arXiv cs.DM 2009
Year: 2009

In this paper we investigate how much Hamiltonian cycles weigh in K_4 and K_5 compare to the total weight of the graph and establish precise estimates.
Mutation of Directed Graphs -- Corresponding Regular Expressions and Complexity of Their Generation
Venue: arXiv cs.FL 2009
Year: 2009

Directed graphs (DG), interpreted as state transition diagrams, are traditionally used to represent finite-state automata (FSA). In the context of formal languages, both FSA and regular expressions (RE) are equivalent in that they accept and generate, respectively, type-3 (regular) languages. Based on our previous work, this paper analyzes effects of graph manipulations on corresponding RE. In this present, starting stage we assume that the DG under consideration contains no cycles. Graph manipulation is performed by deleting or inserting of nodes or arcs. Combined and/or multiple application of these basic operators enable a great variety of transformations of DG (and corresponding RE) that can be seen as mutants of the original DG (and corresponding RE). DG are popular for modeling complex systems; however they easily become intractable if the system under consideration is complex and/or large. In such situations, we propose to switch to corresponding RE in order to benefit from their compact format for modeling and algebraic operations for analysis. The results of the study are of great potential interest to mutation testing.
On Measuring Non-Recursive Trade-Offs
Venue: arXiv cs.FL 2009
Year: 2009

We investigate the phenomenon of non-recursive trade-offs between descriptional systems in an abstract fashion. We aim at categorizing non-recursive trade-offs by bounds on their growth rate, and show how to deduce such bounds in general. We also identify criteria which, in the spirit of abstract language theory, allow us to deduce non-recursive tradeoffs from effective closure properties of language families on the one hand, and differences in the decidability status of basic decision problems on the other. We develop a qualitative classification of non-recursive trade-offs in order to obtain a better understanding of this very fundamental behaviour of descriptional systems.
Integrated Modeling and Verification of Real-Time Systems through Multiple Paradigms
Venue: arXiv cs.LO 2009
Year: 2009

Complex systems typically have many different parts and facets, with different characteristics. In a multi-paradigm approach to modeling, formalisms with different natures are used in combination to describe complementary parts and aspects of the system. This can have a beneficial impact on the modeling activity, as different paradigms an be better suited to describe different aspects of the system. While each paradigm provides a different view on the many facets of the system, it is of paramount importance that a coherent comprehensive model emerges from the combination of the various partial descriptions. In this paper we present a technique to model different aspects of the same system with different formalisms, while keeping the various models tightly integrated with one another. In addition, our approach leverages the flexibility provided by a bounded satisfiability checker to encode the verification problem of the integrated model in the propositional satisfiability (SAT) problem; this allows users to carry out formal verification activities both on the whole model and on parts thereof. The effectiveness of the approach is illustrated through the example of a monitoring system.
Negative circuits and sustained oscillations in asynchronous automata networks
Venue: arXiv cs.DM 2009
Year: 2009

The biologist René Thomas conjectured, twenty years ago, that the presence of a negative feedback circuit in the interaction graph of a dynamical system is a necessary condition for this system to produce sustained oscillations. In this paper, we state and prove this conjecture for asynchronous automata networks, a class of discrete dynamical systems extensively used to model the behaviors of gene networks. As a corollary, we obtain the following fixed point theorem: given a product $X$ of $n$ finite intervals of integers, and a map $F$ from $X$ to itself, if the interaction graph associated with $F$ has no negative circuit, then $F$ has at least one fixed point.
State Complexity Approximation
Venue: arXiv cs.FL 2009
Year: 2009

In this paper, we introduce the new concept of state complexity approximation, which is a further development of state complexity estimation. We show that this new concept is useful in both of the following two cases: the exact state complexities are not known and the state complexities have been obtained but are in incomprehensible form.