The emerging area of network science studies the structural characteristics of networks and dynamic processes on networks such as spread of epidemics and vulnerability of power grids to cascading failures etc. Treating each element of a graph as a resistance, Kirchhoff index defined by the chemistry community is sum of the effective resistances across all pairs of nodes of the graph. This index has been studied using the graph Laplacian matrix which is the same as the indefinite admittance matrix of a resistance network. In this paper we introduce the concept of Weighted Kirchhoff index of a graph and its relationship to Foster's theorems. We present a generalization of Foster's theorems that retains the circuit theoretic flavor and elegance of these theorems. Furthermore we also present a dual form of Foster's first theorem.

The survivable logical topology mapping (routing) problem in IP-over-wavelength-division multiplexing networks is to map each link in the logical topology (IP layer) onto a lightpath in the physical topology (optical layer), such that failure of a physical link does not cause the logical topology to become disconnected. In this paper, we propose a novel approach based on the concept of protecting spanning tree set of the logical topology. We present necessary and sufficient conditions based on this concept and study three optimization problems with varying degrees of difficulty. We study a generalized logical routing problem with the objective to protect the logical topology against maximal number of physical link failures. The new problem aims to find a survivable routing if one exists, or achieve maximal protection of physical link failures otherwise. We also show that the problem is equivalent to the minimum dominating set problem in bipartite graphs. We discuss how one can use the column generation technique to speed up the execution of this formulation, which obviates the need to find all spanning trees at the beginning of the execution of this formulation. In addition, we also present which has several nice features a heuristic approach, which incorporates a method to augment the logical topology with additional links to guarantee a survivable routing, which only requires a shortest path algorithm and an algorithm to generate an appropriate spanning tree. We provide the results of extensive simulations conducted to evaluate our formulations and demonstrate the effectiveness of our new approach.

Cloud computing services are realized through the mapping of the service layer network into the physical infrastructure. Multiple failures in the physical infrastructure could disrupt cloud network connectivity and cause cascading failures impacting cloud service customers. As the physical infrastructure has limited resources, most early research works for survivable virtual network mapping were concentrated on the single link failure scenario. In this paper, we study survivable cloud network mapping with multiple physical link failures and a special case, Shared Risk Link Group (SRLG) failure. We present the necessary and sufficient conditions to guarantee a survivable mapping with multiple physical link failures. Corresponding mixedinteger linear programming (MILP) formulations which avoid the enumeration of failure link combinations are proposed. We also provide the corresponding formulations for the SRLG case. Computation results demonstrate the viability of our approaches.

The emerging area of network science studies the properties of networks and dynamic processes on networks (such as spread of epidemics) that arises in a variety of applications including electrical, communication, internet, biological, ecological networks etc. Treating each element of a graph as a resistance, Kirchhoff index defined by the chemistry community is the sum of the effective resistances across all pairs of nodes of the graph. This index has been studied using the graph Laplacian (same as the indefinite admittance matrix). In this paper we present a simpler formula for Kirchhoff index based on the properties of the node-to-datum resistance matrix, considerably reducing the computational effort. A byproduct of this formula is a new invariant property of node-to-conductance matrix that does not depend on the choice of the datum node, extending the currently available knowledge on the determinant of the node-to-conductance matrix. Furthermore it can be shown that link congestion (if random-walk routing is used) can be estimated using the elements of the node-to-datum resistance matrix.

A fundamental problem in survivable routing in wavelength division multiplexing (WDM) optical networks is the computation of a pair of link-disjoint (or node-disjoint) lightpaths connecting a source with a destination, subject to the wavelength continuity constraint. However, this problem is NP-hard when the underlying network topology is a general mesh network. As a result, heuristic algorithms and integer linear programming (ILP) formulations for solving this problem have been proposed. In this paper, we advocate the use of 2-edge connected (or 2-node connected) subgraphs of minimum isolated failure immune networks as the underlying topology for WDM optical networks. We present a polynomial-time algorithm for computing a pair of link-disjoint lightpaths with shortest total length in such networks. The running time of our algorithm is O(nW2), where n is the number of nodes, and W is the number of wavelengths per link. Numerical results are presented to demonstrate the effectiveness and scalability of our algorithm. Extension of our algorithm to the node-disjoint case is straightforward.

VPN service providers (VSP) and IP-VPN customers have traditionally maintained service demarcation boundaries between their routing and signaling entities. This has resulted in the VPNs viewing the VSP network as an opaque entity and therefore limiting any meaningful interaction between the VSP and the VPNs. The purpose of this research is to address this issue by enabling a VSP to share its core topology information with the VPNs through a novel topology abstraction (TA) service which is both practical and scalable in the context of managed IP-VPNs. TA service provides tunable visibility of state of the VSP's network leading to better VPN performance. A key challenge of the TA service is to generate TA with relevant network resource information for each VPN in an accurate and fair manner. We develop three decentralized schemes for generating TAs with different performance characteristics. These decentralized schemes achieve improved call performance, fair resource sharing for VPNs, and higher network utilization for the VSP. We validate the idea of the VPN TA service and study the performance of the proposed techniques using various simulation scenarios over several topologies.

Delay constrained path selection is concerned with finding a source-to-destination path so that the delay of the path is within a given delay bound. When the network is modeled by a directed graph where the delay of a link is a random variable with a known mean and a known variance, the problem becomes that of computing a most probable delay constrained path. In this paper, we present a comprehensive theoretical study of this problem. First, we prove that the problem is NP-hard. Next, for the case where there exists a source-to-destination path with a delay mean no more than the given delay bound, we present a fully polynomial time approximation scheme. In other words, for any given constant ε such that 0 <; ε <; 1, our algorithm computes a path whose probability of satisfying the delay constraint is at least (1-ε) times the probability that the optimal path satisfies the delay constraint, with a time complexity bounded by a polynomial in the number of network nodes and 1/ε. Finally, for the case where any source-to-destination path has a delay mean larger than the given delay bound, we present a simple approximation algorithm with an approximation ratio bounded by the square root of the hop count of the optimal path.

Continuing advances in the semiconductor technology have made possible the development of very large digital systems comprising hundreds of thousands of components or units. Yet it is impossible to build such systems without defects. As the size of a system grows, it is more likely to develop faults both in the manufacturing process and during the operation period. Testing of such systems becomes extremely difficult due to their large sizes. In 1967, Preparata, Metze and Chien proposed a model and a framework, called System-Level Diagnosis, for dealing with this problem. In recent years, the rapidly expanding technology of cellular communication, wireless LANs and satellite services will make information available anywhere and at any time. This new mobile computing environment has given rise to a host of new research challenges in areas such as address, mobility, data distribution, security and bandwidth managements. Following this trend, we propose to study in this paper the following project: Distributed testing and diagnosis in a mobile computing environment. We build our work on the pioneering works in distributed diagnosis reported in the past. We design appropriate distributed protocols to demonstrate, through experimentation, the feasibility of incorporating distributed system level diagnosis techniques for testing in a mobile computing environment. Our development and experimentation have been based the RDZ-algorithm of Rangarajan, Dahbura, and Ziegler [18]. Our results collected during this research clearly provide evidence that the RDZ-algorithm can be implemented in an Ad-Hoc wireless network whose network connectivity (topology) may change dramatically at any moment. We conclude with a discussion of some of our experiences relating to distributed testing in a mobile environment.

Given a logical topology GLand a physical topology G, the survivable logical topology design problem in an IP-over- WDM optical network is to map the logical links into lightpaths in G such that GLremains connected after the failure of any edge in G. In view of its fundamental nature and its practical importance, this problem has received considerable attention in the literature. The SMART algorithmic framework based on the circuits in GLis a novel and very significant contribution to this problem. Taking advantage of the dual relationship between circuits and cutsets in a graph, we first present in this paper the primal algorithm CIRCUIT-SMART (similar to SMART) and algorithm CUTSET-SMART that is dual of CIRCUIT-SMART and proofs of correctness of these algorithms. To guarantee survivability we add additional logical links called protection edges, if necessary. This investigation has provided much insight into the structural properties of solutions to this problem and the structure of survivable logical graphs. Specifically, we present a highly simplified version of CUTSET-SMART that always provides a survivable mapping as long as G is 3-edge connected, and a survivable logical topology structure. We also present algorithm INCIDENCE-SMART that uses incidence sets that are special cases of a cut. Two efficient heuristics, one based on maximum matching theory and the other based on both the primal and dual algorithms are also presented. Simulation results comparing the different algorithms in terms of computational time, protection capacity and survivability success rate are also presented.

Most research works in routing and design of optical networks assume that the optical medium can carry signals without any bit error. However, the physical impairments on the optical signal quality introduced by optical components, such as erbium-doped fiber amplifiers (EDFA) and optical cross connects (OXCs), must be considered in the routing and design problems of WDM networks in practice. In this paper, we studied the dynamic connection provisioning problem in WDM networks under multiple signal quality constraints. We present a polynomial time optimal algorithm that finds an active path for an incoming connection request with minimum network resource consumption. Simulation results show that our solution outperforms the previously best solution to the problem.

The problem of designing high capacity and high bit rate IP-over-WDM networks, which can provide uninterrupted service in the presence of network equipment failures, continues to attract significant interest from the research community. An IP-over-WDM network implements Internet Protocol (IP) directly over physical WDM network by establishing lightpaths using IP routers, optical crossconnects (OXC) and optical fibers. Generally an optical fiber carries several lightpaths and all of them get disconnected, if the fiber carrying them fails. Such failures can quickly impact the performance of the entire network. If IP routers can find paths to all the nodes in the network, then the network can continue to provide service without significant performance degradation. This can be achieved by reserving network resources (protection) or provisioning the network with some additional capacity (restoration). Such networks are usually called survivable networks. In this paper, we propose four algorithms based on SMART framework proposed by Kurant and Thiran, and a hybrid approach by Shenai and Sivalingam. The algorithms use a combination of protection and restoration mechanisms to make IP-over-WDM networks survivable such that the protection capacity required is not significant.

Managed service framework enables a service provider to offer more demanding and revenue generating services. IETF proposed Provider Provisioned IP-VPN service is a well known managed service. In [6] we first proposed a new framework to enable managed dynamic VPN service using the notion of topology abstraction. In [7] we proposed several distributed heuristics that can be applied in the context of [6]. The focus of this paper is to study the problem of enabling dynamic managed service using topology abstraction in a centralized manner whose objective is to maximize the network utilization and VPN call performance. The centralized scheme proposed in this paper applies the maximum concurrent flow theory and proposes two extensions to it. The two extension aims at improving the conservative nature of using maximum concurrent flow theory by improving the statistical multiplexing of available core network resources among the VPNs. We study the proposed approaches using a simulation environment of an IP/MPLS network providing managed IP-VPN service with appropriate extensions required to realize the components of the Managed Dynamic VPN Service as proposed in [6].

Wavelength Division Multiplexing (WDM) can increase the carrying capacity of an optical network without laying additional fibers. However, a disruption in such a high speed and high capacity network can quickly impact the entire network. A fast protection and restoration recovery mechanism is needed to provide uninterrupted data delivery. Implementing IP directly over a WDM optical network, using optical crossconnects and IP routers, is emerging as the preferred method to efficiently utilize the enormous bandwidth offered by WDM networks. However, in such networks, a single link failure in the WDM layer can affect multiple links in the IP layer, which may greatly degrade data delivery. Several solutions have been proposed in the literature to avert such a scenario. These solutions mostly focus on finding paths for the IP connections in the WDM layer in such a way that the failure of a single WDM link does not disconnect the IP topology. Such a mapping is called "survivable". Due to the NP-completeness of the problem, various heuristics based on ILP formulations, tabu search, and shortest path variants have been proposed in the literature. In this paper we study a recent approach by Thiran and Kurant, point out certain attractive features and difficulties with this approach, and present enhancements to their basic approach to achieve better fault coverage and to add robustness to the survivable routing schemes. We provide simulation results evaluating the new heuristics.

VPN as a managed service enables the service provider to offer more demanding and revenue generating services. In this paper we try to tackle an important problem of service providers providing bandwidth service on demand on an IP/MPLS core network. We propose a managed VPN architecture for such a service highlighting the novelty in our architecture. We concentrate on an important aspect of service definition called the topology abstraction service and define a new problem called the VPN core capacity sharing problem that arises in this context. We propose three schemes to solve this problem borrowing from results from graph theory. As part of our simulation study, we evaluate each of these strategies with different call arrival scenarios and present the results.

Routing and wavelength assignment (RWA) aims to assign the limited number of wavelengths in a wavelength-division multiplexed (WDM) optical network so as to achieve greater capacity. In a recent paper, Datta et al. studied the problem of establishing a set of disjoint lightpaths on a tree topology using a single wavelength to maximize the total traffic supported by the chosen set of lightpaths. They discussed applications of this problem to RWA and presented a dynamic programming algorithm which optimally solves this problem in /spl Oscr/(n/sup 4/+n/spl Dscr//sup 3/) time, where n is the number of nodes in the network and /spl Dscr/ is the maximum node degree. In this paper, we present an improved algorithm with a time complexity of /spl Oscr/(n/sup 2/+n/spl Dscr//sup 2/).

Given a directed network with two integer weights, cost and delay, associated with each link, quality-of-service (QoS) routing requires the determination of a minimum cost path from one node to another node such that the delay of the path is bounded by a specified integer value. This problem, also known as the constrained shortest path problem (CSP), admits an integer linear programming (ILP) formulation. Due to the integrality constraints, the problem is NP-hard. So, approximation algorithms have been presented in the literature. Among these, the LARAC algorithm, based on the dual of the LP relaxation of the CSP problem, is very efficient. In contrast to most of the currently available approaches, we study this problem from a primal perspective. Several issues relating to efficient implementations of our approach are discussed. We present two algorithms of pseudopolynomial time complexity. One of these allows degenerate pivots and uses an anticycling strategy and the other, called the NBS algorithm, is based on a novel strategy which avoids degenerate pivots. Experimental results comparing the NBS algorithm, the LARAC algorithm, and general purpose LP solvers are presented. In all cases, the NBS algorithm compares favorably with others and beats them on dense networks.

In this paper, we study dynamic light trail routing in a WDM optical network. We present an efficient algorithm for establishing a light trail routing for a new connection request, while using minimum network resources. We also study survivable routing using light trail technology. We present an efficient heuristic for computing a pair of working and protection light trails for a given connection request. Simulation results are presented which demonstrate the advantages of our routing schemes.

VPN as a managed service enables the service provider to offer more demanding and revenue generating services. Some of the common managed VPN services known today include auto discovery, security, and also a potential ability to perform on demand signaling. In this paper we try to tackle an important problem of service providers namely topology dissemination to VPN customers seeking dynamic bandwidth service. Topology dissemination can easily be translated into a VPN service. In this regard we define this service and its associated SLA. Further we elaborate on four basic QoS enabled topology abstraction services: fully meshed, source rooted star, star, and simple node. The paper also describes a generic framework to generate these abstractions and presents simulation results comparing performance of each of these schemes.

As a generalization of the traditional path protection scheme in WDM networks where a backup path is needed for each active path, the partial path protection scheme uses a collection of backup paths to protect an active path, where each backup path in the collection protects one or more links on the active path such that every link on the active path is protected by one of the backup paths. While there is no known polynomial time algorithm for computing an active path and a corresponding backup path using the path protection scheme for a source-destination node pair, we show that an active path and a corresponding collection of backup paths using the partial path protection scheme can be computed in polynomial time, whenever they exist, under each of the following two network models: (a) dedicated protection in WDM networks without wavelength converters; and (b) shared protection in WDM networks without wavelength converters. Under each of the two models, we prove, that for any given source s and destination d in the network, if one candidate active path connecting s and d is protectable using partial path protection, then any candidate active path connecting s and d is also protectable using partial path protection. This fundamental property leads to efficient shortest active path algorithms that can find an active path and its corresponding partial path protections whenever they exist. Simulation results show that shared partial path protection outperforms shared path protection in terms of blocking probability.

A few faulty nodes can make an n-dimensional mesh or torus network unsafe for fault-tolerant routing methods based on the block fault model, where the whole system (n-dimensional space) forms a fault block. A new concept, called extended local safety information in meshes or tori, is proposed to guide fault-tolerant routing, and classifies fault-free nodes inside 2-dimensional planes. Many nodes globally marked as unsafe become locally enabled inside 2-dimensional planes. A fault-tolerant routing algorithm based on extended local safety information is proposed for k-ary n-dimensional meshes/tori. Our method does not need to disable any fault-free nodes, unlike many previous methods, and this enhances the computational power of the system and improves performance of the routing algorithm greatly. All fault blocks are constructed inside 2-dimensional planes rather than in the whole system. Extensive simulation results are presented and compared with the previous methods.

Medard, Finn, Barry and Gallager proposed an elegant recovery scheme (known as the MFBG scheme) using redundant trees. Xue, Chen and Thulasiraman extended the MFBG scheme and introduced the concept of quality of protection (QoP) as a metric of multifailure recovery capabilities for single failure recovery schemes. In this paper, we present three linear time algorithms for constructing redundant trees for single link failure recovery in 2-edge connected graphs and for single node failure recovery in 2-connected graphs. Our first algorithm aims at high QoP for single link recovery schemes in 2-edge connected graphs. The previous best algorithm has a running time of O(n/sup 2/(m+n)), where n and m are the number of nodes and links in the network. Our algorithm has a running time of O(m+n), with comparable performance. Our second algorithm aims at high QoS for single link recovery schemes in 2-edge connected graphs. Our algorithm improves the previous best algorithm with O(n/sup 2/(m+n)) time complexity to O(m+n) time complexity with comparable performance. Our third algorithm aims at high QoS for single node recovery schemes in 2-connected graphs. Again, our algorithm improves the previous best algorithm with O(n/sup 2/(m+n)) time complexity to O(m+n) time complexity with comparable performance. Simulation results show that our new algorithms outperform previously known linear time algorithms significantly in terms of QoP or QoS, and outperform other known algorithms in terms of running time, with comparable QoP of QoS performance.

Quality-of-service (QoS) routing problem requires the determination of a minimum cost path from a source node s to a destination node t in a data network such that the delay of the path is bounded by /spl Delta/ (> 0). This problem also known as the constrained shortest path (CSP) problem is NP-hard. So, heuristics and approximation algorithms have been presented in the literature. Among the heuristics, the LARAC algorithm, based on the dual of the LP relaxation or the Lagrangian relaxation of the CSP problem is very efficient. In this paper we study the primal simplex approach to the LP relaxation of the CSP problem and present an approximation algorithm to this problem. Several issues relating to efficient implementations of our approach are discussed. Experimental results comparing the performance of the new algorithm with that of the LARAC algorithm are presented.

Given a communication network modeled as a directed graph with a delay parameter associated with each link, we consider the problem of determining the most probable delay constrained path from a source node to a destination node. Assuming that the link delays are random variables with continuous and differentiable probability density function and using the central limit theorem this problem can be formulated as a path problem which involves simultaneously optimizing two additive path parameters. Two cases arise. When there is one path with mean delay less than the delay bound, we present an exact pseudo polynomial algorithm, a fully polynomial time /spl epsi/-approximation algorithm and a strongly polynomial heuristic algorithm. In the unlikely case when this assumption is violated, the problem is shown to be NP-hard and no constant factor approximation algorithm exists if P /spl ne/ NP. We also study the path protection problem under inaccurate state information.

We study quality-of-service (QoS) and quality-of-protection (QoP) issues in redundant tree based preplanned recovery schemes for a single-link failure in two-edge connected graphs and for a single-node failure in two-connected graphs. We present schemes (to be called G-MFBG schemes) that generalize the schemes (to be called MFBG schemes) developed by Medard et al. (1997) to construct a pair of redundant trees, called red and blue trees, which guarantees fast recovery from any single-link/node failure, as long as the failed node is not the root node. Using the G-MFBG schemes, we study QoS issues relating to red/blue trees. We present effective heuristics for computing a pair of redundant trees with low average delay or small total cost. We develop an optimal algorithm for computing a pair of red/blue trees with maximum bandwidth. Furthermore, a pair of red/blue trees guarantees fast recovery from simultaneous multiple failures if it satisfies certain properties. This leads us to define the concept of QoP of a pair of red/blue trees. We present an effective heuristic to construct a pair of red/blue trees with high QoP. The paper concludes with a discussion of computational results that demonstrate the effectiveness of the different algorithms presented.

Traditional centralized network management solutions do not scale to present-day large-scale computer/communication networks. Decentralization/distributed solutions can solve some of these problems (Goldszmidt, G. and Yemini, Y., 1995), and thus there is considerable interest in distributed/decentralized network management applications. We present the design and evaluation of an SNMP-based distributed network fault detection/monitoring system. We integrate into the SNMP framework our ML-ADSD algorithm (Su, M.-S. et al., Proc. 39th Annual Allerton Conf. on Commun., Control, and Computers, 2001; Su, "Multilevel distributed diagnosis and the design of a distributed network fault detection system based on the SNMP protocol", Ph.D. Thesis, School of Computer Science, University of Oklahoma, 2002) for fault diagnosis in a distributed processor system. The algorithm uses the multilevel paradigm and requires only minor modifications to be scalable to networks of varying sizes. The system is fault tolerant, allowing processor failure and/or recovery during the diagnosis process. We have implemented the system on an Ethernet network of 32 machines. Our results show that the diagnosis latency (or time to termination) is much better than that of earlier solutions. Also, the system's bandwidth utilization is insignificant, demonstrating the practicality of its deployment in a real network. We have successfully integrated three modern disciplines: network management, distributed computing and system level diagnosis.

Protection and restoration in high speed networks is an important issue, especially for applications in SONET and WDM networks. We study quality of service issues in preplanned recovery using redundant trees in 2-vertex connected graphs and 2-edge connected graphs. In particular, we present efficient heuristic algorithms for finding a pair of working-protection trees with small delay in the working tree. Extensive computational results show that our algorithms reduce the average delay in the working tree by 60% to 90%. Many challenging problems remain open.

We study quality of service issues in preplanned recovery using redundant trees in vertex-redundant or edge-redundant graphs. In particular, we present efficient heuristic algorithms for finding a pair of working-protection trees with large bandwidth in the working tree. Computational results are presented to demonstrate the effectiveness of our algorithms. Many challenging problems remain open.

We show that, in any given uniform orientation metric plane, the shortest network interconnecting a given set of points under a fixed topology can be computed by solving a linear programming problem whose size is bounded by a polynomial in the number of terminals and the number of legal orientations. When the given topology is restricted to a Steiner topology, our result implies that the Steiner minimum tree under a given Steiner topology can be computed in polynomial time in any given uniform orientation metric with /spl lambda/ legal orientations for any fixed integer /spl lambda/ /spl ges/ 2. This settles an open problem posed by Brazil, Thomas and Weng (2000).

The objectives in this paper are twofold: design an approach for the netlist partitioning problem using the cooperative multilevel search paradigm introduced by Toulouse et al. and study the effectiveness of this paradigm for solving combinatorial optimization problems, in particular, those arising in the very large scale integration (VLSI) computer-aided design (CAD) area. The authors present a cooperative multilevel search algorithm CoMHP and describe a parallel implementation on the SGI O2000 system. Experiments on ISPD98 benchmark suite of circuits show, for four-way and eight-way partitioning, a reduction of 3% to 15% in the size of hyperedge cuts compared to those obtained by hMETIS. Bisections of hypergraphs based on the algorithm also outperform hMETIS, although more modestly. The authors present experimental results to demonstrate that the cooperation scheme plays a key role in the performance of CoMHP. In fact, the improvement in the quality of the solutions produced by CoMHP is to a large extent independent of the partitioners used in the implementation of CoMHP. The experimental results also demonstrate the effectiveness of the cooperative multilevel search paradigm for solving the netlist partitioning problem.

Article Free Access Share on Multilevel cooperative search: application to the circuit/hypergraph partitioning problem Authors: Min Ouyang U. Nebraska-Lincoln Dept CS&E U. Nebraska-Lincoln Dept CS&EView Profile , Michel Toulouse U. Manitabo Dept CS U. Manitabo Dept CSView Profile , Krishnaiyan Thulasiraman U. Oklahoma School of CS U. Oklahoma School of CSView Profile , Fred Glover U. Colorado Graduate School of Business U. Colorado Graduate School of BusinessView Profile , Jitender S. Deogun U. Nebraska-Lincoln Dept CS&E U. Nebraska-Lincoln Dept CS&EView Profile Authors Info & Claims ISPD '00: Proceedings of the 2000 international symposium on Physical designMay 2000 Pages 192–198https://doi.org/10.1145/332357.332399Online:01 May 2000Publication History 6citation255DownloadsMetricsTotal Citations6Total Downloads255Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The minimum length test sequence generation method proposed previously (1988) for conformance testing of a protocol uses Unique Input Sequences (UIS) for state identification. This method, called the U-method, requires that the test graph, a graph derived from the protocol, be connected. This requirement also needs to be satisfied in the case of the MU-method, which assumes that the multiple UISs are available for each state. Thus, the U-method and the MU-method may not provide minimum length test sequences in cases where the test graph is not connected. Nevertheless, these methods generate minimum length test sequences with high fault coverage whenever the test graph is connected. This raises an important problem: Does there exist an assignment of UISs to the transitions such that the resulting test graph is connected? In this paper, we formulate this problem as a maximum cardinality two matroid intersection problem and discuss an efficient algorithmic solution. We also point out the role of the work in the minimum length test sequence generation problem.

The search history of memory based heuristics like tabu search can be used to design a category of parallel algorithms, called cooperative search. These algorithms execute in parallel several search programs on the same optimization problem instance. At run time, the data gathered in the memory by one sequential search program need not be used only by this program, but it can be recycled and shared with other concurrently executing tabu search programs for the same purpose. In this paper we compare the global behavior of cooperating and non-cooperating tabu search programs. We show that cooperating programs tend to have a search pattern which is less diversified than non-cooperating programs. Our findings also indicate that this second order impact of the sharing of gathered data on the search behaviors of cooperating programs is not related to the optimization properties of the individual tabu programs.

A probabilistic diagnosis algorithm is presented for constant degree structures. The performance of the algorithm is analyzed under a negative binomial failure distribution to account for fault clustering. It is shown that the algorithm can correctly identify almost all units even when the yield is low (much lower than 50%) and when faults are clustered. A wafer test structure is proposed, which utilizes the test access port of each die to perform comparison tests on its neighbors and incorporates a localized version of the diagnosis algorithm to determine the status of each die. Both the test time and the diagnosis time are invariant with respect to the number of dies on the wafer. The saving of test costs could be significant as compared with probe testing, because with probe testing dies are probed one at a time while they are tested in parallel with this scheme. The scheme is unique in that it is shown to work well when faults are clustered and when the yield is low.

A number of test sequence generation methods proposed for protocols represented as extended finite state machines (EFSMs) use state identification sequences for checking the states. However, neither a formal definition nor a method of computation of these sequences for an EFSM state is known. We define a new type of state identification sequence, called context independent unique sequence (CIUS) and present an algorithm for computing it. A unified method based on CIUSes is developed for automatically generating executable test cases for both control flow and data flow aspects of an EFSM. In control flow testing, CIUSes are very useful in confirming the tail state of the transitions. In data flow testing, CIUSes improve the observability of the test cases for the def-use associations of different variables used in the EFSM. Unlike general state identification sequences, the use of CIUSes does not increase the complexity of the already intractable feasibility problem in the test case generation.

Let n be an integer and F={f/sub 1/:1/spl les/i/spl les/t for some integer t} be a finite set of linear functions. We define a linear congruential graph G(F, n) as a graph on the vertex set V={0, 1, ..., n-1}, in which any x/spl isin/V is adjacent to f/sub i/(x) mod n, 1/spl les/i/spl les/t. For a linear function g, and a subset V/sub 1/ of V we define a linear congruential graph G(F, n, g,V/sub 1/) as a graph on vertex set V, in which any x/spl isin/V is adjacent to f/sub i/(x) mod n, 1/spl les/i/spl les/t, and any x/spl isin/V/sub 1/ is also adjacent to g(x) mod n. These graphs generalize several well known families of graphs, e.g. the de Bruijn graphs. We give a family of linear functions, called DCC linear functions, that generate regular, highly connected graphs which are of substantially larger order than de Bruijn graphs of the same degree and diameter. Some theoretical and empirical properties of these graphs are given and their structural properties are studied.

In this paper we present a parallel global routing algorithm for general cell layout. The algorithm applies a hierarchical decomposition strategy that recursively divides routing problems into simple, independent subproblems for parallel processing. The solution of each subproblem is based on integer programming and network flow optimization. The algorithm is implemented on a shared-memory machine and experiment results on different examples show relative speedup between 4 and 5 for 8 processors. The speedup is achieved without compromising the quality of the routing results.

This paper presents a floorplanner for datapath with the capability of re-allocating data storage for minimizing the interconnect area and critical path delay without altering the number of functional units and the schedule. The tool has combined two novel approaches: 1-A placement and routing model to handle different architectural topologies (mux. and/or bus based) suitable for FPGA's. 2-An efficient formulation for the binding of register/interconnect and combined floorplanning. The complexity of the architectural and floorplanning model, and of the cost function, have led us to the use of a stochastic optimization process. The running time of the whole process indicates the viability of the method. We show through various examples how the floorplanner improves the area and critical path delay of the datapath compared to a plain floorplanner. The improvement is about 20% for the critical path delay when this objective is a stringent constraint.

A simple diagnosis algorithm is presented for constant degree systems such as rectangular grids connected as tori. The algorithm determines the status of a unit according to the size of its faction, a cluster of units that call each other fault-free but outsiders faulty. Almost all units are correctly identified with this algorithm under a binomial failure distribution even when the probability of failure is rather high. The complexity of the algorithm is O(n), where n is the number of units in a constant degree system. The application of the algorithm to production testing of VLSI chips is also considered. With a test board that houses a large number of chips to be tested, all the chips can be tested in parallel in a way that they test each other and the test outcomes, not necessarily correct, are reported to a host system for analysis. The actual status of each chip is determined by using this new diagnosis algorithm. The above chip screening process can be repeated for higher accuracy. It is shown that no more than two steps are needed in most real situations. Compared with testing by test equipment that usually tests only one chip at a time, the saving of test time and the test equipment cost could be significant with our approach.>

This paper presents a novel layout model and floorplanning tool particularly suitable for taking into account user defined layout constraints on specific sets of modules and specific locations. The user defined layout constraints can be the setting of any common topological property associated with a group of specific modules such as the neighboring property for example. Or the use of any topological regularities in a design such as regular bus structure or the use of the structural property such as the bit-sliceable or non bit-sliceable feature of a module set, or their similar shape. The exploitation of these structural information helps in producing more compact layout especially for datapath oriented architectures. Moreover, in addition to the area and total wiring length, the critical path delay is systematically minimized through a global cost function. The potential candidates for the critical path computation can be specifically defined by the user. The core of the optimization process is based on simulated annealing.>

A classic PMC (Preparata, Metze, and Chien) multiprocessor system [F. P Preparata, G. Metze, and R. T. Chien, IEEE Trans. Electr. Comput., EC-16 (1967), pp. 848–854] composed of n units is said to be ${t / {(t + 1)}}$ diagnosable [A. D. Friedman, A new measure of digital system diagnosis, in Dig. 1975 Int. Symp. Fault-Tolerant Comput., 1975, pp. 167–170] if, given a syndrome (complete collection of test results), the set of faulty units can be isolated to within a set of at most $t + 1$ units, assuming that at most t units in the system are faulty. This paper presents a methodology for determining when a unit $\upsilon $ can belong to an allowable fault set of cardinality at most t. Based on this methodology, for a given syndrome in a ${t / {(t + 1)}}$-diagnosable system, the authors establish a necessary and sufficient condition for a vertex v to belong to an allowable fault set of cardinality at most t and certain properties of ${t / {(t + 1)}}$-diagnosable systems. This condition leads to an ${{O(n^{3.5} )t} / {(t + 1)}}$-diagnosis algorithm. This ${t / {(t + 1)}}$-diagnosis algorithm complements the ${t / {(t + 1)}}$-diagnosability algorithm of Sullivan [The complexity of system-level fault diagnosis and diagnosability, Ph.D. thesis, Yale University, New Haven, CT, 1986].

A new genetic algorithm for channel routing in the physical design process of VLSI circuits is presented. The algorithm is based on a problem-specific representation scheme and problem-specific genetic operators. The genetic encoding and our genetic operators are described in detail. The performance of the algorithm is tested on different benchmarks, and it is shown that the results obtained using the proposed algorithm are either qualitatively similar to or better than the best published results.

The authors study the fault diagnosis of multiprocessor systems when fault constraints in the local domain of each processor are specified. They use the comparison-based model. A multiprocessor system S is t-in-L diagnosable if, given a syndrome, all faulty processors can be uniquely identified provided there are at most t faulty processors in the local domain L(u/sub i/) union (u/sub i/) of every processor, u/sub i/ in S, where L (u/sub i/) denotes the set of processors adjacent to u/sub i/. Certain basic results that lead to efficient conditions for unique diagnosis of a system when certain fault constraints are satisfied in the local domain of each processor in the system are presented. The t-in-L diagnosability of certain regular interconnected systems is examined under the assumption that less than half of the processors in the system are faulty. Diagnosis algorithms for these systems are presented.>

A new algorithm for solving the graph bisectioning problem based on tabu search is proposed. The authors run the tabu search algorithm and the Kernighan-Lin algorithm on the same set of random graphs with 50 to 500 nodes and compare their performances. They demonstrate that for all of the graphs their tabu search algorithm provides lower bisection cost than the Kernighan-Lin algorithm; and for all of the graphs with more than 200 nodes, their tabu search algorithm takes less time than the Kernighan-Lin algorithm.>

Two new measures of network performance, namely, the incremental distance sequence and the incremental diameter sequence, are introduced for application in network topology design. These sequences can be defined for both vertex deletions and edge deletions. A complete characterization of the vertex-deleted incremental distance sequence is presented. Proof of this characterization is constructive in nature. A condition for the feasibility of an edge-deleted incremental distance sequence and a procedure for realizing such a sequence are given. Interrelationships between the elements of incremental distance sequences and incremental diameter sequences are studied. Using these results, it is shown that a graph that has a specified diameter and a specified maximum increase in diameters for deletions of vertex sets of given cardinalities can be designed.>

Abstract Relationships among graph invariants such as the number of vertices, diameter, connectivity, maximum and minimum degrees, and regularity are being studied recently, motivated by their usefulness in the design of fault‐tolerant and low‐cost communication and interconnection networks. A graph is called a (d,c,r) graph if it has diameter d, connectivity c, and regularity r. The minimum number of vertices in (d, 1,3), (d,2,3), (d,3,3), and (d,c,c) graphs have been reported in the literature. In this paper, the minimum number of vertices in a (d,c,r) graph with r > c is determined, thereby exhausting all the possible choices of values for d, c, and r. Our proof is constructive and hence we get a collection of optimal (d,c,r) graphs.

The authors present two O(n/sup 2/) planarization algorithms, PLANARIZE and MAXIMAL-PLANARIZE. These algorithms are based on A. Lempel, S. Even, and I. Cederbaum's (1967) planarity testing algorithm and its implementation using PQ-trees. Algorithm PLANARIZE is for the construction of a spanning planar subgraph of an n-vertex nonplanar graph. The algorithm proceeds by embedding one vertex at a time and, at each step, adds the maximum number of edges possible without creating nonplanarity of the resultant graph. Given a biconnected spanning planar subgraph G/sub p/ of a nonplanar graph G, the MAXIMAL-PLANARIZE algorithm constructs a maximal planar subgraph of G which contains G/sub p/. This latter algorithm can also be used to planarize maximally a biconnected planar graph.>

The design is discussed of distributed algorithms for the single-source shortest-path problem to run on an asynchronous directed network in which some of the edges may be associated with negative weights, and thus in which a cycle of negative total weight may also exist. The only existing solution in the literature for this problem is due to K.M. Chandy and J. Misra (1982), and it has, in the worst case, an unbounded message complexity. A synchronous version of the Chandy-Misra algorithm is described and studied, and it is proved that for a network with m edges and n nodes, the worst case message and time complexities of this algorithm are O(mn) and O(n), respectively. This algorithm is then combined with an efficient synchronizer to yield an asynchronous protocol that retains the same message and time complexities.>