Overcoming controllability problems with fewest channels between testers

When testing a system that has multiple physically distributed ports/interfaces it is normal to place a tester at each port. Each tester observes only the events at its port and it is known that this can lead to additional controllability problems. While such controllability problems can be overcome by the exchange of external coordination messages between the testers, this requires the deployment of an external network and may thus increase the costs of testing. The problem studied in this paper is finding a minimum number of coordination channels to overcome controllability problems in distributed testing. Three instances of this problem are considered. The first problem is to find a minimum number of channels between testers in order to overcome the controllability problems in a given test sequence to be applied in testing. The second problem is finding a minimal set of channels that allow us to overcome controllability problems in any test sequence that may be selected from the specification of the system under test. The last problem is to find a test sequence that achieves a particular test objective and in doing so allows fewest channels to be used.     

Using status messages in the distributed test architecture

If the system under test has multiple interfaces/ports and these are physically distributed then in testing we place a tester at each port. If these testers cannot directly communicate with one another and there is no global clock then we are testing in the distributed test architecture. If the distributed test architecture is used then there may be input sequences that cannot be applied in testing without introducing controllability problems. Additionally, observability problems can allow fault masking. In this paper we consider the situation in which the testers can apply a status message: an input that causes the system under test to identify its current state. We show how such a status message can be used in order to overcome controllability and observability problems.     

UIO sequence based checking sequences for distributed test architectures

This study addresses the construction of a preset checking sequence that will not pose controllability (synchronization) and observability (undetectable output shift) problems when applied in distributed test architectures that utilize remote testers. The controllability problem manifests itself when a tester is required to send the current input and because it did not send the previous input nor did it receive the previous output it cannot determine when to send the input. The observability problem manifests itself when a tester is expecting an output in response to either the previous input or the current input and because it is not the one to send the current input, it cannot determine when to start and stop waiting for the output. Based on UIO sequences, a checking sequence construction method is proposed to yield a sequence that is free from controllability and observability problems.     

Checking sequences for distributed test architectures

Controllability and observability problems may manifest themselves during the application of a checking sequence in a test architecture where there are multiple remote testers. These problems often require the use of external coordination message exchanges among testers during testing. However, the use of coordination messages requires the existence of an external network that can increase the cost of testing and can be difficult to implement. In addition, the use of coordination messages introduces delays and this can cause problems where there are timing constraints. Thus, sometimes it is desired to construct a checking sequence from the specification of the system under test that will be free from controllability and observability problems without requiring the use of external coordination message exchanges. This paper gives conditions under which it is possible to produce such a checking sequence, using multiple distinguishing sequences, and an algorithm that achieves this.     

Distributed testing without encountering controllability and observability problems

The objective of testing is to determine whether a system under test conforms to its specification. In distributed test architectures that utilize remote testers, this objective can be complicated by the fact that testers may encounter problems relating to controllability and observability during the application of a test sequence. Existing solutions to these problems involve first constructing a test sequence from the specification of an implementation under test, and then inserting coordination messages or appending selected test subsequences that prevent the occurrences of controllability and observability problems during the application of the resulting test sequence. This paper proposes a method that utilizes a set of transformation rules to construct an auxiliary directed graph from a given specification, and constructs a rural Chinese postman tour in this graph to yield a minimum-length test sequence where there is no potential controllability or observability problems, and where the use of coordination messages is minimized.     

基于同步有向图的同步测试序列生成方法

使用多测试单元的测试系统可以对多端口协议实现进行一致性测试，但是在进行这种一致性测试时，测试系统各个端口之间可能会出现同步问题，现在，解决同步问题常用的办法是在测试单元相应端口之间增加同步连接，然后通过此同步连接相互发送同步消息来进行同步，多端口协议和其它类型的分布式系统可以用有限状态机模型来描述，目前，同步问题被分为双端口同步问题，多端口同步问题，紧同步问题等多种类型，该文考虑两种有限状态机测试问题，第一种是面向端口的测试，不考虑有限状态机测试单元之间的通信问题，第二种面向组的测试，有限状态机中的各个端口被分成互不相关的多个组，属于不同组中的测试单元之间互不通信，该文提出了一种基于同步有向图的同步测试序列生成方法，这种生成方法适用于Pair同步，Port同步和组同步问题，并且，这种方法也可以用来判断如何在非同步测试序列中增加同步通信，将非同步测试序列转化为同步测试序列。     

On controllability of a class of discrete‐time homogeneous bilinear systems with solvable controls

This paper studies the controllability of a class of discrete‐time homogeneous bilinear systems. Necessary and sufficient conditions for the controllability are obtained. In particular, an algorithm for computing the controls, which achieve given states transition, for the controllable systems is given with examples. Furthermore, the necessary and sufficient conditions are applied to present four cases of the change of the controllability for Euler discretization, which show that Euler discretization may and may not change the controllability of nonlinear systems. Copyright © 2011 John Wiley & Sons, Ltd.     

Coordination Algorithm for Distributed Testing

With the emergence of new models, architectures and middleware such as ODP, TINA and CORBA, for developing open distributed systems, testing technology requires adaptation for use within conformance assessment in such systems. All these frameworks are object-based and aim at creating open distributed environments supporting interworking, interoperability, and portability, in spite of heterogeneity and autonomy of the related systems. In this context, an open distributed system may be viewed as a system providing standardized distributed interfaces for interacting with other systems. Conformance of such a system can be assessed by attaching a related tester at each provided interface. However, many problems of controllability and observability influencing fault detection during the testing process, arise if there is no coordination between the testers. In this paper, we show how to cope with these problems by using test coordination procedures in a distributed testing architecture.     

Modeling Parallel Bandwidth: Local versus Global Restrictions

Recently there has been an increasing interest in models of parallel computation that account for the bandwidth limitations in communication networks. Some models (e.g., bsp, logp, and qsm) account for bandwidth limitations using a per-processor parameter g > 1 , such that each processor can send/receive at most h messages in g . . . h time. Other models (e.g., pram(m )) account for bandwidth limitations as an aggregate parameter m < p , such that the p processors can send at most m messages in total at each step. This paper provides the first detailed study of the algorithmic implications of modeling parallel bandwidth as a per-processor (local) limitation versus an aggregate (global) limitation. We consider a number of basic problems such as broadcasting, parity, summation, and sorting, and give several new upper and lower time bounds that demonstrate the advantage of globally limited models over locally limited models given the same aggregate bandwidth (i.e., p . . . 1/g = m ). In general, globally limited models have a possible advantage whenever there is an imbalance in the number of messages sent/received by the processors. To exploit this advantage, the processors must schedule the sending of messages so as to respect the aggregate bandwidth limit. We present a new parallel scheduling algorithm for globally limited models that enable an unknown, arbitrarily unbalanced set of messages to be sent through the limited bandwidth within a (1 + ε) factor of the optimal off-line schedule with high probability, even if the penalty for overloading the network is an exponential function of the overload. We also present a near-optimal algorithm for the case where long messages must be sent as flits in consecutive time steps, as well as for the case where new messages to be sent arrive dynamically over an infinite time line. These results consider both message passing (distributed memory) and shared memory scenarios, and improve upon the best results for the locally limited model by a factor of Θ(g) . Finally, we present results quantifying the power of concurrent reads in a globally limited bandwidth setting, including showing an Ω(p lg m/m lg p) time separation between the exclusive-read and the concurrent-read pram(m ) models, which, when m << p , greatly improves upon the separation known previously. Received June 1, 1997; revised March 10,1998.     

Implementation relations and test generation for systems with distributed interfaces

Some systems interact with their environment at physically distributed interfaces called ports and we separately observe sequences of inputs and outputs at each port. As a result we cannot reconstruct the global sequence that occurred and this reduces our ability to distinguish different systems in testing or in use. In this paper we explore notions of conformance for an input output transition system that has multiple ports, adapting the widely used ioco implementation relation to this situation. We consider two different scenarios. In the first scenario the agents at the different ports are entirely independent. Alternatively, it may be feasible for some external agent to receive information from more than one of the agents at the ports of the system, these local behaviours potentially being brought together and here we require a stronger implementation relation. We define implementation relations for these scenarios and prove that in the case of a single-port system the new implementation relations are equivalent to ioco. In addition, we define what it means for a test case to be controllable and give an algorithm that decides whether this condition holds. We give a test generation algorithm to produce sound and complete test suites. Finally, we study two implementation relations to deal with partially specified systems.     

A novel quasi symmetrical design of the three‐way Gysel power divider using ideal phase inverters

A novel quasi symmetrical three‐way Gysel power divider with frequency‐independent isolation and impedance matching is proposed. Equal magnitudes of the reflection coefficients for the input and the output ports of the three‐way divider can be obtained despite the asymmetrical structure and the different terminal impedances. The divider is analyzed in terms of its equivalent four‐port network. Quasi symmetrical property (|S₁₁| = |S_ii|, i = 2‐4) is proved which means the input port (port. 1) will automatch when the output ports are matched. Closed‐form equations are derived for the design. For verification, based on the microstrip/slotline PI, two examples, which include a three‐way Gysel PD with port impedances (50, 50, 50, 50) Ω, and an ultra‐wideband three way Gysel PD with port impedances (50, 100, 100, 100) Ω with the center frequency of 4 GHZ are designed, fabricated, and measured respectively. The measured results are in great agreement with the simulated ones.     

Local controllability of nonlinear systems

The local controllability of control systems with an arbitrary number of controls is considered, first on an open set and then at a given point; necessary conditions are derived concerning the Lie algebra T′ generated by the input vector fields, and applied to gradient systems.The main results are a geometric sufficient condition for local controllability at a point, and an equivalent condition based on the computation of Lie brackets, assuming T′ to be (n − 1)-dimensional.     

Local controllability of scalar input systems on 3-manifolds

Local controllability of generic C^k pairs of vector fields in a three dimensional connected manifold M is studied, showing that in general a necessary condition is also sufficient on an open dense subset of the set of points where it is verified. The results obtained are used to determine local controllability for scalar input affine control systems.     

Maximizing throughput in multi-queue switches

We study a basic problem in Multi-Queue switches. A switch connectsm input ports to a single output port. Each input port is equipped with an incoming FIFO queue with bounded capacityB. A switch serves its input queues by transmitting packets arriving at these queues, one packet per time unit. Since the arrival rate can be higher than the transmission rate and each queue has limited capacity, packet loss may occur as a result of insufficient queue space. The goal is to maximize the number of transmitted packets. This general scenario models most current networks (e.g. IP networks) which only support a “best effort” service in which all packet streams are treated equally. A 2-competitive algorithm for this problem was designed in [5] for arbitraryB. Recently, a (17/9 ≈ 1.89)-competitive algorithm was presented forB>1 in [3]. Our main result in this paper shows that forB which is not too small our algorithm can do better than 1.89, and approach a competitive ratio ofe/(e − 1) ≈ 1.58. The research of Yossi Azar was supported in part by the Israeli Ministry of Industry and Trade and by the Israel Science Foundation.     

An Optimal Lower Bound for Buffer Management in Multi-Queue Switches

In the online packet buffering problem (also known as the unweighted FIFO variant of buffer management), we focus on a single network packet switching device with several input ports and one output port. This device forwards unit-size, unit-value packets from input ports to the output port. Buffers attached to input ports may accumulate incoming packets for later transmission; if they cannot accommodate all incoming packets, their excess is lost. A packet buffering algorithm has to choose from which buffers to transmit packets in order to minimize the number of lost packets and thus maximize the throughput. We present a tight lower bound of e/(e?1)≈1.582 on the competitive ratio of the throughput maximization, which holds even for fractional or randomized algorithms. This improves the previously best known lower bound of 1.4659 and matches the performance of the algorithm Random Schedule. Our result contradicts the claimed performance of the algorithm Random Permutation; we point out a flaw in its original analysis.     

A menu generator for audio visual networks

An audio visual system can enhance its controllability by an interactive and user-friendly menu through which a user issues commands to control audio visual devices. One of the serious problems encountered in such menu development is that end-user's requirement specifications vary in screen layouts, device configurations and commands contents, and often involves extensive manual programming. We have definedMacroMMenu formally as a tree structure menu system model restricting a menu transition graph, and designed and implemented an automated menu prototyping system which includes a menu generator calledInteractive Proto. UsingInteractive Proto through a visual programming language, end-users themselves, who are usually non-programmers, can easily define menu specification, input this source specification, and the targetMacro Menu is generated automatically.     

An Optimal Algorithm for Broadcasting Multiple Messages in Trees

We consider multiple message broadcasting in tree networks. The source (considered as the root of the tree) has k messages which have to be broadcast to all nodes of the tree. In every time unit each node can send one of its already obtained messages to one of its children. A k-message broadcasting scheme prescribes in which time unit a given node should send a message to which child. It is k-optimal if it achieves the smallest possible time for broadcasting k messages from the source to all nodes. We give an algorithm to construct a k-optimal broadcasting scheme for an arbitrary n-node tree. The time complexity of our algorithm is O(nk), i.e., the best possible.     

The single-input Minimal Controllability Problem for structured systems

This paper considers the Minimal Controllability Problem (MCP), i.e. the problem of controlling a linear system with an input vector having as few non-zero entries as possible. We focus on structured systems which represent an interesting class of parameter dependent linear systems and look for structural controllability properties based on the sparsity pattern of the input vector. We show first that the MCP is solvable when a rank condition is satisfied and show that generically one non-zero entry in the input vector is sufficient to achieve controllability when there is no specific system structure. According to the fixed zero/non-zero pattern of the state matrix entries, we give an explicit characterization of the minimum number and the possible location of non-zero entries in the input vector to ensure generic controllability. The analysis based on graph tools provides with a simple polynomial MCP solution and highlights the structural mechanisms that make it useful to act on some variables to ensure controllability.     

Simple Algorithms for Multimessage Multicasting with Forwarding

We consider multimessage multicasting over the n processor complete (or fully connected) static network when the forwarding of messages is allowed. We present an efficient algorithm that constructs for every degree d problem instance a communication schedule with total communication time at most 2d , where d is the maximum number of messages that each processor may send (or receive). Our algorithm consists of two phases. In the first phase a set of communications are scheduled to be carried out in d time periods in such a way that the resulting problem is a multimessage unicasting problem of degree d . In the second phase we generate a communication schedule for this problem by reducing it to the Makespan Openshop Preemptive Scheduling problem which can be solved in polynomial time. The final schedule is the concatenation of the communication schedules for each of these two phases. For 2 ≤ l ≤ d , we present an algorithm to generate a communication schedule with total communication time at most \lfloor ( 2 - 1/l ) d \rfloor +1 , for problem instances where each processor needs to send messages to at most ld destinations. We also discuss multimessage multicasting for dynamic networks. Received September 22, 1997; revised August 29, 1998.     

Efficient Parallel Graph Algorithms for Coarse-Grained Multicomputers and BSP

In this paper we present deterministic parallel algorithms for the coarse-grained multicomputer (CGM) and bulk synchronous parallel (BSP) models for solving the following well-known graph problems: (1) list ranking, (2) Euler tour construction in a tree, (3) computing the connected components and spanning forest, (4) lowest common ancestor preprocessing, (5) tree contraction and expression tree evaluation, (6) computing an ear decomposition or open ear decomposition, and (7) 2-edge connectivity and biconnectivity (testing and component computation). The algorithms require O(log p) communication rounds with linear sequential work per round (p = no. processors, N = total input size). Each processor creates, during the entire algorithm, messages of total size O(log (p) (N/p)) . The algorithms assume that the local memory per processor (i.e., N/p ) is larger than p ^ε , for some fixed ε > 0 . Our results imply BSP algorithms with O(log p) supersteps, O(g log (p) (N/p)) communication time, and O(log (p) (N/p)) local computation time. It is important to observe that the number of communication rounds/ supersteps obtained in this paper is independent of the problem size, and grows only logarithmically with respect to p . With growing problem size, only the sizes of the messages grow but the total number of messages remains unchanged. Due to the considerable protocol overhead associated with each message transmission, this is an important property. The result for Problem (1) is a considerable improvement over those previously reported. The algorithms for Problems (2)—(7) are the first practically relevant parallel algorithms for these standard graph problems. Received July 5, 2000; revised April 16, 2001.