18216276
Locally Subcube-Connected Hypercube Networks: Theoretical Analysis and Experimental Results
We study hypercube networks with a very large number of faulty nodes. A simple and natural condition, the local subcube-connectivity, is identified under which hypercube networks with a very large number of faulty nodes still remain connected. The condition of local subcube-connectivity can be detected and maintained in a distributed manner based on localized management. Efficient routing algorithms on locally subcube-connected hypercube networks are developed. Our algorithms are distributed and local-information-based in the sense that each node in the network knows only its neighbors' status and no global information of the network is required by the algorithms. For a locally subcube-connected hypercube network that may contain up to 37.5 percent faulty nodes, our algorithms run in linear time and, for any two given nonfaulty nodes, find a routing path of length bounded by four times the Hamming distance between the two nodes. Theoretical analysis and experimental results are presented which show that, under a variety of probability distributions of node failures, hypercube networks are locally subcube-connected with a very high probability and our routing algorithms run in linear time and construct routing paths of nearly optimal length.
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.
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.
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.
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.
18417913
IT induction in the food service industry
As part of the business strategy in a competitive environment, for an organization to induct information technology (IT) appropriately, business process reengineering (BPR) must be conducted. We propose a process that incorporates both management information systems and strategic management concepts for the IT induction. First, we develop a business competition strategy based on Porter’s five competitive forces; second, using concepts developed in the field of information systems the business processes are reengineered to improve effectiveness and efficiency; and finally, IT strategy is developed to achieve these goals. A real‐life case in the food service industry is used to illustrate this process.
34159049
Approximation algorithms for scheduling real-time jobs with multiple feasible intervals
Time-critical jobs in many real-time applications have multiple feasible intervals. Such a job is constrained to execute from start to completion in one of its feasible intervals. A job fails if the job remains incomplete at the end of the last feasible interval. Earlier works developed an optimal off-line algorithm to schedule all the jobs in a given job set and on-line heuristics to schedule the jobs in a best effort manner. This paper is concerned with how to find a schedule in which the number of jobs completed in one of their feasible intervals is maximized. We show that the maximization problem is $${\cal N}{\cal P}$$-hard for both non-preemptible and preemptible jobs. This paper develops two approximation algorithms for non-preemptible and preemptible jobs. When jobs are non-preemptible, Algorithm Least Earliest Completion Time First (LECF) is shown to have a 2-approximation factor; when jobs are preemptible, Algorithm Least Execution Time First (LEF) is proved being a 3-approximation algorithm. We show that our analysis for the two algorithms are tight. We also evaluate our algorithms by extensive simulations. Simulation results show that Algorithms LECF and LEF not only guarantee the approximation factors but also outperform other multiple feasible interval scheduling algorithms in average.
15506877
Flexible Temporal Consistency for Fixed-Time Constraint Verification in Grid Workflow Systems
To verify fixed-time constraints in grid workflow systems, the consistency and inconsistency conditions have been defined in the conventional work. However, in this paper, we argue that although the conventional consistency condition is reasonable, the conventional inconsistency condition is too rigorous and covers several different situations. These situations which are handled conventionally by the same exception handling should be handled differently for cost saving. Therefore, we divide the conventional inconsistency into weak consistency,weak inconsistency and strong inconsistency and treat the conventional consistency as strong consistency. Correspondingly, we discuss how to verify them. Especially, for the weak consistency, we present a method on how to adjust it to the strong consistency. For the weak inconsistency, we analyse why it can be handled by simpler and more economical exception handling. The final comparison and discussion further demonstrate that our research can achieve better cost effectiveness than the conventional work.
9759106
Design and analysis of low‐power access protocols for wireless and mobile ATM networks
This paper describes the design and analysis of a low‐power medium access control (MAC) protocol for wireless/mobile ATM networks. The protocol – denoted EC‐MAC (energy conserving medium access control) – is designed to support different traffic types with quality‐of‐service (QoS) provisions. The network is based on the infrastructure model where a base station (BS) serves all the mobiles currently in its cell. A reservation‐based approach is proposed, with appropriate scheduling of the requests from the mobiles. This strategy is utilized to accomplish the dual goals of reduced energy consumption and quality of service provision over wireless links. A priority round robin with dynamic reservation update and error compensation scheduling algorithm is used to schedule the transmission requests of the mobiles. Discrete‐event simulation has been used to study the performance of the protocol. A comparison of energy consumption of the EC‐MAC to a number of other protocols is provided. This comparison indicates the EC‐MAC has, in general, better energy consumption characteristics. Performance analysis of the proposed protocol with respect to different quality‐of‐service parameters using video, audio and data traffic models is provided.