17666919
Strong Fault-Tolerance: Parallel Routing in Star Networks with Faults
We study the strong fault-tolerance for the star networks. Let G be a network in which all nodes have degree d. We say that G is strongly fault-tolerant if it has the following property: let Gf be a copy of G with at most d - 2 faulty nodes removed, then for any pair of non-faulty nodes u and v in Gf, there is a container of width t between u and v, where t is the minimum of degree of u and degree of v in Gf. We show that the star networks are strongly fault-tolerant and develop an algorithm that constructs a maximum width container of nearly optimal length in a star network with faults. Our algorithm requires no prior knowledge for the faulty nodes and runs in optimal time.
1021255
A minimal and complete set of operators for the development of robust manifold mesh modelers
In this paper, we identify a minimal and complete set of fundamental operators, which is necessary and sufficient for performing all homeomorphic and topological operations on 2- manifold mesh structures. Efficient algorithms are developed for the implementation of these operators. We also developed a set of powerful, user-friendly, and effective operators at the level of user-interface. Using these operators, we have developed a prototype system for robust, interactive, and user-friendly modeling of orientable 2-manifold meshes. Users of our system can perform a large set of homeomorphic and topological changes with these user-interface level operators. Our system is topologically robust in the sense that users will never create invalid 2-manifold mesh structure with these operators. In our system, the homeomorphic and topological surgery operations can be applied alternatively on 2-manifold meshes. With our system, users can blend surfaces, construct rinds, and open holes on these rind shapes. With our system, the shapes that look like solid, non-manifold, or 2-manifold with boundary can be manipulated. The system also provides automatic texture mapping during topology changes.
31382426
Strong Fault-Tolerance: Parallel Routing in Networks with Faults
A d-regular network G is strongly fault-tolerant if for any copy Gf of G with at most d - 2 faulty nodes, every pair of nonfaulty nodes u and v in Gf admits min{df(u), df (v)} node-disjoint paths in Gf from u to v, where df(u) and df(v) are the degrees of the nodes u and v in Gf. We show that popular network structures, such as hypercube and star networks, are strongly fault-tolerant. We develop efficient algorithms that construct the maximum number of node-disjoint paths of optimal or nearly optimal length in these networks with faulty nodes. Our algorithms are optimal in terms of their running time.
16331940
Optimal Parallel Routing in Star Networks
Star networks have recently been proposed as attractive alternatives to the popular hypercube for interconnecting processors on a parallel computer. In this paper, we present an efficient algorithm that constructs an optimal parallel routing in star networks. Our result improves previous results for the problem.
5242879
Interactive rind modeling
In this paper, we describe a technique, with roots in topological graph theory, that we call rind modeling. It provides for the easy creation of surfaces resembling peeled and punctured rinds. We show how the method's two main steps of: 1) creation of a shell or crust like the rind of an orange, and 2) opening holes in the crust by punching or peeling can be encapsulated into a real time semi-automatic interactive algorithm. We include a number of worked examples, some by students in a first modeling course, that demonstrate the ease with which a large variety of intricate rind shapes can be created.
2261180
Graph Ear Decompositions and Graph Embeddings
Ear decomposition of a graph has been extensively studied in relation to graph connectivity. In this paper, a connection of ear decomposition to graph embeddings is exhibited. It is shown that constructing a maximum-paired ear decomposition of a graph and constructing a maximum-genus embedding of the graph are polynomial-time equivalent. Applications of this connection are discussed.
2647804
Extended DBP for (m, k)-Firm Based QoS
In this paper, an extended DBP (E_DBP) scheme is studied for (m,k)-firm constraint. The basic idea of the proposed algorithm takes into account the distance to exit a failure state, which is a symmetrical notion of distance to fall into a failure state in DBP. Quality of Service (QoS) in terms of dynamic failure and delay is evaluated. Simulation results reveal the effectiveness of E_DBP to provide better QoS.
27587317
An executable specification language for specification understanding in object-oriented specification reuse
System analysis time can be reduced through specification reuse which, however, requires specification understanding. This paper presents an object-oriented executable specification language which reduces understanding time through executing specifications. In addition to being executable, the specification language hides as many classes as possible within subsystems, and explicitly specifies relationships between specification components. This facilitates specification modification. Moreover, the language explicitly specifies interface parameters of specification components. This facilitates specification composition.
10445420
Modeling and Predicting Future Trajectories of Moving Objects in a Constrained Network
Advances in wireless sensor networks and positioning technologies enable traffic management (e.g. routing traffic) that uses real-time data monitored by GPS-enabled cars. Location management has become an enabling technology in such application. The location modeling and trajectory prediction of moving objects are the fundamental components of location management in mobile locationaware applications. In this paper, we model the road network and moving objects in a graph of cellular automata (GCA), which makes full use of the constraints of the network and the stochastic behavior of the traffic. A simulation-based method based on graphs of cellular automata is proposed to predict future trajectories. Our technique strongly differs from the linear prediction method, which has low prediction accuracy and requires frequent updates when applied to real traffic with velocity changes. The experiments, carried on two different datasets, show that the simulation-based prediction method provides higher accuracy than the linear prediction method.
15338297
Fast construction of overlay networks
An asynchronous algorithm is described for rapidly constructing an overlay network in a peer-to-peer system where all nodes can in principle communicate with each other directly through an underlying network, but each participating node initially has pointers to only a handful of other participants. The output of the mechanism is a linked list of all participants sorted by their identifiers, which can be used as a foundation for building various linear overlay networks such as Chord or skip graphs. Assuming the initial pointer graph is weakly-connected with maximum degree <i>d</i> and the length of a node identifier is <i>W</i>, the mechanism constructs a binary search tree of nodes of depth <i>O</i>(<i>W</i>) in expected <i>O</i>(<i>W</i> log <i>n</i>) time using expected <i>O</i>((<i>d</i>+<i>W</i>)<i>n</i> log <i>n</i>) messages of size <i>O</i>(<i>W</i>) each. Furthermore, the algorithm has low <i>contention</i>: at any time there are only <i>O</i>(<i>d</i>) undelivered messages for any given recipient. A lower bound of Ω(<i>d</i> + log <i>n</i>) is given for the running time of any procedure in a related synchronous model that yields a sorted list from a degree-<i>d</i> weakly-connected graph of <i>n</i> nodes. We conjecture that this lower bound is tight and could be attained by further improvements to our algorithms.
28550627
An even wiring approach to the ball grid array package routing
An even-wiring router for the BGA package is presented to interconnect each I/O pad of a chip to a corresponding ball distributed on the substrate area. The major phases for the router consist of layer assignment, topological routing, and physical routing. Using this router, we can generate an even distribution of planar and any-angle wires to improve manufacturing yield. We have also conducted various testing examples to verify the efficiency of this router. Experiments show that the router produces very good results, far better than the manual design, thus it can be practically applied to VLSI packaging.