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.
16597098
Regular meshes
This paper presents our preliminary results on regular meshes in which all faces have the same size and all vertices have the same valence. A regular mesh is denoted by (<i>n, m, g</i>) where <i>n</i> is the number of the sides of faces, <i>m</i> is the valence of vertices and <i>g</i> is the genus of the mesh. For <i>g</i> = 0, regular meshes include regular platonic solids, all two sided polygons. For <i>g</i> = 1 regular meshes include regular tilings of infinite plane. Our work shows that there exist infinitely many regular meshes for <i>g</i> > 1. Moreover, we have constructive proofs that describe how to create high genus regular meshes that consist of triangles and quadrilaterals (3, <i>m</i>, <i>g</i>) and (4, <i>m</i>, <i>g</i>).
42163647
Nearly optimal one-to-many parallel routing in star networks
Star networks were proposed recently as an attractive alternative to the well-known hypercube models for interconnection networks. Extensive research has been performed that shows that star networks are as versatile as hypercubes. This paper is an effort in the same direction. Based on the well-known paradigms, we study the one-to-many parallel routing problem on star networks and develop an improved routing algorithm that finds n-1 node-disjoint paths between one node and a set of other n-1 nodes in the n-star network. These parallel paths are proven of minimum length within a small additive constant, and our algorithm has an optimal time complexity. This result significantly improves the previous known algorithms for the problem. Moreover, the algorithm well illustrates an application of the orthogonal partition of star networks, which was observed by the original inventors of the star networks but seems generally overlooked in the subsequent study. We should also point out that similar problems are already studied for hypercubes and have proven useful in designing efficient and fault tolerant routing algorithms on hypercube networks.
3146463
On Strong Menger-Connectivity of Star Graphs
Motivated by parallel routing in networks with faults, we study the following graph theoretical problem. Let G be a d-regular graph. We say that G is strongly Menger-connected if for any copy Gf of G with at most d - 2 nodes removed, every pair of nodes u and v in Gf are connected by min{deg f(u), deg f(v)} node-disjoint paths in Gf, where deg f(u) and deg f(v) are the degrees of the nodes u and v in Gf, respectively. We show that the star graphs, which are a recently proposed attractive alternative to the widely used hypercubes as network models, are strongly Menger-connected. An algorithm of optimal running time is developed that constructs the maximum number of node-disjoint paths of nearly optimal length in star graphs with faults.
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.
204766
Scalability, fidelity, and containment in the potemkin virtual honeyfarm
The rapid evolution of large-scale worms, viruses and bot-nets have made Internet malware a pressing concern. Such infections are at the root of modern scourges including DDoS extortion, on-line identity theft, SPAM, phishing, and piracy. However, the most widely used tools for gathering intelligence on new malware -- network honeypots -- have forced investigators to choose between monitoring activity at a large scale or capturing behavior with high fidelity. In this paper, we describe an approach to minimize this tension and improve honeypot scalability by up to six orders of magnitude while still closely emulating the execution behavior of individual Internet hosts. We have built a prototype honeyfarm system, called Potemkin, that exploits virtual machines, aggressive memory sharing, and late binding of resources to achieve this goal. While still an immature implementation, Potemkin has emulated over 64,000 Internet honeypots in live test runs, using only a handful of physical servers.
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.
5765721
Architecture of TsinghuAeolus
RoboCup Simulation Server provides a wonderful challenge for all the participants. This paper explains key technology implemented by Tsinghuaeolus RoboCup team played in RoboCup environment, including basic adversarial skills, which is developed by using Dynamic Programming in combination with heuristic search algorithm, and reactive strategy architecture. Tsinghuaeolus was the winner of RoboCup2001.
6409733
Routing in an Internet-scale network emulator
One of the primary challenges facing scalable network emulation and simulation is the overhead of storing network-wide routing tables or computing appropriate routes on a per-packet basis. We present an approach to routing table calculation and storage based on spanning tree construction that provides an order of magnitude reduction in routing table size for Internet-like topologies. In our approach, we maintain a variable number of spanning trees for a given topology and choose the path between two hosts in each tree, choosing the shortest. We also populate offline a negative cache of actual shortest paths for source-destination pairs - typically a few percent of the total - where the lookups result in sub-optimal routes. We have implemented our technique in a popular network emulator, ModelNet, and show that our enhanced version can emulate Internet topologies 10-100 times larger than previously possible.
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.