34879998
On fault tolerance of 3-dimensional mesh networks
In this paper, the concept ofk-submesh andk-submesh connectivity fault tolerance model is proposed. And the fault tolerance of 3-D mesh networks is studied under a more realistic model in which each network node has an independent failure probability. It is first observed that if the node failure probability is fixed, then the connectivity probability of 3-D mesh networks can be arbitrarily small when the network size is sufficiently large. Thus, it is practically important for multicomputer system manufacturer to determine the upper bound for node failure probability when the probability of network connectivity and the network size are given. A novel technique is developed to formally derive lower bounds on the connectivity probability for 3-D mesh networks. The study shows that 3-D mesh networks of practical size can tolerate a large number of faulty nodes thus are reliable enough for multicomputer systems. A number of advantages of 3-D mesh networks over other popular network topologies are given. Compared to 2-D mesh networks, 3-D mesh networks are much stronger in tolerating faulty nodes, while for practical network size, the fault tolerance of 3-D mesh networks is comparable with that of hypercube networks but enjoys much lower node degree.
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.
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.
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.
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.
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.
1479779
Programming by demonstration: removing sub-optimal actions in a partially known configuration space
Programming by demonstration is a promising approach to automatic robot programming, however, methods are required to remove suboptimal actions that can be demonstrated by end users. In this paper we use the partial knowledge of configuration space (C-space) derived in the previous work by Chen et al. (2000) to remove suboptimal actions from a demonstration. Our idea is to use demonstrated paths to predict what regions in C-space are obstacle free. Suboptimal actions in a demonstration are then avoided by planning alternative actions that pass through the obstacle free regions. Experimental results show the validity of the approach. A demonstrated path containing significant sub-optimality was converted by the approach into a short, efficient path suitable for execution by the robot.
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.
3103973
Sprite: a simple, cheat-proof, credit-based system for mobile ad-hoc networks
Mobile ad hoc networking has been an active research area for several years. How to stimulate cooperation among selfish mobile nodes, however, is not well addressed yet. In this paper, we propose Sprite, a simple, cheat-proof, credit-based system for stimulating cooperation among selfish nodes in mobile ad hoc networks. Our system provides incentive for mobile nodes to cooperate and report actions honestly. Compared with previous approaches, our system does not require any tamper-proof hardware at any node. Furthermore, we present a formal model of our system and prove its properties. Evaluations of a prototype implementation show that the overhead of our system is small. Simulations and analysis show that mobile nodes can cooperate and forward each other's messages, unless the resource of each node is extremely low.
12280706
A distributed multi-agent system for collaborative information management and sharing
In this paper, we present DIAMS, a system of distributed, collaborative agents to help users access, manage, share and exchange information. A DIAMS personal agent helps its owner find information most relevant to current needs. It provides tools and utilities for users to manage their information repositories with dynamic organization and virtual views. Flexible hierarchical display is integrated with indexed query search to support effective information access. Automatic indexing methods are employed to support user queries and communication between agents.
14690444
Fluid-flow analysis of TCP Westwood with RED
This paper concerns TCP Westwood (TCPW), a recently developed modification of TCP, in combination with RED queue management. We develop a fluid-flow model of TCPW with RED and use it to study both equilibrium and dynamic features. On the equilibrium side, we identify the scaling of window with loss-probability, and compare it to TCP NewReno. We also use the model to find the boundary of stability, beyond which we see large oscillations; we find that the stable region of TCPW is enhanced with respect to TCP NewReno. Furthermore we show preliminary evidence that oscillations, when they occur, have a limited impact on network throughput. Fairness and friendliness of TCPW is also analyzed and compared with NewReno. Our results show that TCPW is more fair than NewReno for flows with heterogenous round trip time. We also found that TCPW friendliness to NewReno is dependent on the difference between equilibrium queue size and the product of bandwidth and delay.