Explicit graphs in a functional model for spatial databases

Observing that networks are ubiquitous in applications for spatial databases, we define a new data model and query language that especially supports graph structures. This model integrates concepts of functional data modeling with order-sorted algebra. Besides object and data type hierarchies, graphs are available as an explicit modeling tool, and graph operations are part of the query language. Graphs have three classes of components, namely, nodes, edges, and explicit paths. These are at the same time object types within the object type hierarchy and can be used like any other type. Explicit paths are useful because real-world objects often correspond to paths in a network. Furthermore, a dynamic generalization concept is introduced to handle heterogeneous collections of objects in a query. In connection with spatial data types, this leads to powerful modeling and querying capabilities for spatial databases, in particular for spatially embedded networks such as highways, rivers, public transport, and so forth. We use multilevel order-sorted algebra as a formal framework for the specification of our model. Roughly spoken, the first-level algebra defines types and operations of the query language, whereas the second-level algebra defines kinds (collections of types) and type constructors as functions between kinds, and so provides the types that can be used at the first level     

Complexity results on labeled shortest path problems from wireless routing metrics

Metrics to assess the cost of paths through networks are critical to ensuring the efficiency of network routing. This is particularly true in multi-radio multi-hop wireless networks. Effective metrics for these networks must measure the cost of a wireless path based not only on traditional measures such as throughput, but also on the distribution of wireless channels used. In this paper, we argue that routing metrics over such networks may be viewed as a class of existing shortest path problems, the formal language constrained path problems.On this basis, we describe labeled path problems corresponding to two multi-radio wireless routing metrics: Weighted Cumulative Expected Transmission Time (WCETT), developed by Draves et al., and Metric for Interference and Channel-switch (MIC), developed by Yang et al. For the first, we give a concise proof that calculating shortest WCETT paths is strongly NP-Complete for a variety of graph classes. We also show that the existing heuristic given by Draves et al. is an approximator. For the second, we show that calculating loop-free (simple) shortest MIC paths is NP-Complete, and additionally show that the optimization version of the problem is NPO PB-Complete. This result implies that shortest simple MIC paths are only poorly approximable in the worst case.Furthermore, we demonstrate how the polynomial-time algorithm for shortest MIC paths is derivable from an existing language constrained shortest path algorithm. We use this as a basis to exhibit the general utility of viewing multi-channel wireless routing metrics as labeled graph problems, and discuss how a class of related polynomial-time computable metrics are derivable from this algorithm.     

A Microcomputer Based System for Small Relation Algebras

Algebras of n-ary relations are a useful tool in the investigation of logics with limited resources; for example, the equational logic of Tarski's relation algebras corresponds to the three variable fragment of first order logic. We present a computer system which assists in the generation and investigation of properties of relation algebras.     

On the impact of routing matrix inconsistencies on statistical path monitoring in overlay networks

Overlay networks can be used to find working paths when direct underlay paths are anomalously slow, e.g. because of a network fault. Overlay paths should not use links that are involved in a fault, so choosing which overlay path to use often requires path monitoring, which introduces an overhead. By using a routing matrix ‘M’ to define which links are used in each path, and sorting the matrix according to the degree of independence of paths, we can choose a reduced set of paths to monitor, and so reduce overheads. The state of the unmonitored paths are then predicted using statistical estimation techniques based on information inferred from the monitored paths. However, such methods assume knowledge of routing matrix. We investigate the impact on such methods when knowledge of the routing matrix is only approximate, e.g. as obtained using simple tools like traceroute which have been previously blamed for incorrect mapping of the topology of real world IP networks. This paper investigates the impact of routing matrix errors on such statistical path estimation approaches. We show that mitigation or removal of such errors leads to improved path metric prediction and anomaly detection.     

Finding non-dominated bicriteria shortest pairs of disjoint simple paths

In this paper we introduce a method to compute non-dominated bicriteria shortest pairs, each including two disjoint simple paths. The method is based on an algorithm for ranking pairs of disjoint simple paths by non-decreasing order of cost, that is an adaptation of a path ranking algorithm applied to a network obtained from the original one after a suitable modification of the topology. Each path in this new network corresponds to a pair of paths in the former one. Computational results are presented and analysed for randomly generated networks.     

一个简洁高效的Ad Hoc移动自组网络仿真工具

针对目前Ad Hoc移动自组网络仿真系统使用复杂、难以掌握的问题,首先采用面向对象的方法对移动自组网的仿真需求进行了分析,指出Ad Hoc网络仿真需要模拟的几个关键特征,在此基础上完成了面向对象的仿真工具建模,并使用VC＋＋实现了仿真模型。工具设计简洁,易于使用并提供了扩展接口。最后利用仿真环境模拟并分析了两种基于移动自组网的证书管理方案,得出关键的仿真数据,通过对比专业仿真系统的结果可知工具具备较好的可信度,可以满足Ad Hoc网络基本的仿真需求。     

Improving the security of industrial networks by means of formal verification

Computer networks are exposed to serious security threats that can even have catastrophic consequences from both the points of view of economy and safety if such networks control critical infrastructures, such as for example industrial plants. Security must then be considered as a fundamental issue starting from the earlier phases of the design of a system, and suitable techniques and tools should be adopted to satisfy the security-related requirements. The focus of this paper is on how formal methods can help in analysing the standard cryptographic protocols used to implement security-critical services such as authentication and secret keys distribution in critical environments. The analysis of the 802.11 shared key authentication protocol by S³A, a fully automatic software tool that is based on a formal approach, is illustrated as a case study, which also highlights the peculiarities of analysing protocols based on wireless channels.     

PCAR：基于主成分分析的网络关键路径发现算法

大规模的网络进行动态流量监测的一个优化目标是有效减少观测对象,传统的方法通常根据流在空间的相关性减少测量对象。本文提出了一种基于主成分分析的网络的关键路径发现算法PCAR,它通过分析网络流量的时间和空间的相关性来发现网络中的关键路径。我们用Totem公布的Abliene流量数据检验了PCAR算法的有效性。实验表明,该算法与其它算法相比具有计算复杂性小、误判率低等特点。     

The Series Product and Its Application to Quantum Feedforward and Feedback Networks

The purpose of this paper is to present simple and general algebraic methods for describing series connections in quantum networks. These methods build on and generalize existing methods for series (or cascade) connections by allowing for more general interfaces, and by introducing an efficient algebraic tool, the series product. We also introduce another product, which we call the concatenation product, that is useful for assembling and representing systems without necessarily having connections. We show how the concatenation and series products can be used to describe feedforward and feedback networks. A selection of examples from the quantum control literature are analyzed to illustrate the utility of our network modeling methodology.      

Generalized load sharing for packet-switching networks. I. Theory and packet-based algorithm

In this paper, we propose a framework to study how to effectively perform load sharing in multipath communication networks. A generalized load sharing (GLS) model has been developed to conceptualize how traffic is split ideally on a set of active paths. A simple traffic splitting algorithm, called packet-by-packet weighted fair routing (PWFR), has been developed to approximate GLS with the given routing weight vector by transmitting each packet as a whole. We have developed some performance bounds for PWFR and found that PWFR is a deterministically fair traffic splitting algorithm. This attractive property is useful in the provision of service with guaranteed performance when multiple paths can be used simultaneously to transmit packets which belong to the same flow. Our simulation studies, based on a collection of Internet backbone traces, reveal that PWFR outperforms two other traffic splitting algorithms, namely, packet-by-packet generalized round robin routing (PGRR), and packet-by-packet probabilistic routing (PPRR).     

On Learning Gene Regulatory Networks Under the Boolean Network Model

Boolean networks are a popular model class for capturing the interactions of genes and global dynamical behavior of genetic regulatory networks. Recently, a significant amount of attention has been focused on the inference or identification of the model structure from gene expression data. We consider the Consistency as well as Best-Fit Extension problems in the context of inferring the networks from data. The latter approach is especially useful in situations when gene expression measurements are noisy and may lead to inconsistent observations. We propose simple efficient algorithms that can be used to answer the Consistency Problem and find one or all consistent Boolean networks relative to the given examples. The same method is extended to learning gene regulatory networks under the Best-Fit Extension paradigm. We also introduce a simple and fast way of finding all Boolean networks having limited error size in the Best-Fit Extension Problem setting. We apply the inference methods to a real gene expression data set and present the results for a selected set of genes.     

Nonlinear Performance Index (npi): A Tool for Manipulator Dynamics Improvement

The precise control of manipulators depends nonlinearly on the velocity of the motion as well as on manipulator configuration and commanded acceleration requiring complex control strategies. This paper presents a useful tool for identifying and quantifying nonlinear effects appearing during the motion of any manipulator, the Nonlinear Performance Index (npi). The npi takes into account not only the geometrical parameters defining the manipulator but also its structural dynamics through the use of inertial parameters like mass, inertia, centre of mass... The npi can be used in the design stage for analysing and reducing these undesirable nonlinear effects in any general motion or in the trajectory planning looking for paths along which more precise control is expected. The last part of the paper shows how this design optimisation and path planning has been applied to the Agribot, a fruit picking robot designed at the IAI.     

APIS: a software for model identification, simulation and dosage regimen calculations in clinical and experimental pharmacokinetics.

APIS is a software package based on mathematical modelling which provides a reliable approach in optimizing drug therapy. It was designed to assist clinicians in interpreting blood drug levels so that drug therapy may be better and more cost-effective. It is a methodological approach to describe, predict and control the kinetic behaviour of a drug. This software incorporates the principle of Bayesian procedures, i.e. one can use all available patient information (population) to determine patient-specific parameter estimates. These estimates can then be used to design an optimal and individualized drug regimen. APIS is an attractive and useful tool for clinical and experimental pharmacokinetics. APIS may be used on any IBM compatible computer using the Microsoft-Windows environment. The software is menu driven to provide a very user-friendly tool for analysing pharmacokinetic data and for designing dosage regimens.     

Interference-free tool-path generation in the NC machining of parametric compound surfaces

A method is presented for generating interference-free tool paths from parametric compound surfaces. A parametric compound surface is a surface that consists of parametric surface elements. The method is largely composed of two steps: points are obtained from a compound surface to be converted into a triangular polyhedron; tool paths are then generated from the polyhedron. An efficient algorithm is used in the calculation of cutter-location data, and planar tool paths, which are suitable for metal cutting, are produced. The time taken to obtain all the tool paths from a surface model that consists of a large number of parametric surfaces is short. Some real applications are presented.     

Towards an Efficient Path-Oriented Tool for Bounded Reachability Analysis of Linear Hybrid Systems using Linear Programming

The existing techniques for reachability analysis of linear hybrid automata do not scale well to problem sizes of practical interest. Instead of developing a tool to perform reachability check on all the paths of a linear hybrid automaton, a complementary approach is to develop an efficient path-oriented tool to check one path at a time where the length of the path being checked can be made very large and the size of the automaton can be made large enough to handle problems of practical interest. This approach of symbolic execution of paths can be used by design engineers to check important paths and thereby, increase the faith in the correctness of the system. Unlike simple testing, each path in our framework represents a dense set of possible trajectories of the system being analyzed. In this paper, we develop the linear programming based techniques towards an efficient path-oriented tool for the bounded reachability analysis of linear hybrid systems.     

Some new simple Lie algebras in characteristic 2

We describe an algorithm for computing automorphism groups and testing isomorphisms of finite dimensional Lie algebras over finite fields. The algorithm is particularly effective for simple or almost simple Lie algebras. We show how it can be used in a computer search for new low dimensional simple Lie algebras over the field with two elements.     

Semiring induced valuation algebras: Exact and approximate local computation algorithms

Local computation in join trees or acyclic hypertrees has been shown to be linked to a particular algebraic structure, called valuation algebra. There are many models of this algebraic structure ranging from probability theory to numerical analysis, relational databases and various classical and non-classical logics. It turns out that many interesting models of valuation algebras may be derived from semiring valued mappings. In this paper we study how valuation algebras are induced by semirings and how the structure of the valuation algebra is related to the algebraic structure of the semiring. In particular, c-semirings with idempotent multiplication induce idempotent valuation algebras and therefore permit particularly efficient architectures for local computation. Also important are semirings whose multiplicative semigroup is embedded in a union of groups. They induce valuation algebras with a partially defined division. For these valuation algebras, the well-known architectures for Bayesian networks apply. We also extend the general computational framework to allow derivation of bounds and approximations, for when exact computation is not feasible.     

A Kind of Multistage Interconnection Networks with Multiple Paths

1ThisworkwassupportedbytheNationalNaturalScienceFoundationofChina,GralltNo.69473024.1IntroductionMultiprocessorsystemsoftenuseinterconnectionnetworkstoconnectproces-sorsormemorymodules-Atime-sharedbusisthesimplestformofinterconnectionnetworks,butitcannotprovidetheperformancerequiredinmultiprocessorsystemstoday.Acrossbarswitchnetworkisanalternativeusedintheearliersystemstoimplementinterconnection.Theonlydelaytoconnectinputstooutputsisthatofasingleswitchinggate,butacrossbarswitchnetworkisver…     

Path testing of computer programs with loops using a tool for simple loop patterns

The purpose of this paper is to present a method for testing computer programs with iteration loops. Given such programs, we have shown that for classes of program paths, identified as sequences of simple loop paths, there is a characterizing function called a simple loop pattern. The key idea of simple loop patterns is that these special functions form a base set which can represent any path computation in the given program. A software tool called SILOP has been developed to automatically generate these simple loop patterns, and each corresponding sequence of simple loop paths can be considered as a test case. The tester uses each test case, and with knowledge of the application program, can generate corresponding test data. This paper also presents a method for selecting the specific paths and test data to determine the simple loop pattern reliably. The tester can use this selection method to predict the number of tests required. In order to apply this selection method, the given program must be a linear computer program. The SILOP tool and this test selection method have been applied to commercial software; in this paper, this computational experience is reported and several examples are given to demonstrate the approach.     

Fault-tolerant routing over shortest node-disjoint paths in hypercubes

This paper presented a routing algorithm that finds n disjoint shortest paths from the source node s to target node d in the n-dimensional hypercube. Fault-tolerant routing over all shortest node-disjoint paths has been investigated to overcome the failure encountered during routing in hypercube networks. In this paper, we proposed an efficient approach to provide fault-tolerant routing which has been investigated on hypercube networks. The proposed approach is based on all shortest node-disjoint paths concept in order to find a fault-free shortest path among several paths provided. The proposed algorithm is a simple uniform distributed algorithm that can tolerate a large number of process failures, while delivering all n messages over optimal-length disjoint paths. However, no distributed algorithm uses acknowledgement messages (acks) for fault tolerance. So, for dealing the faults, acknowledgement messages (acks) are included in the proposed algorithm for routing messages over node-disjoint paths in a hypercube network.