Narrow Results

We propose a deadlock-free routing scheme in irregular networks using prefix routing. Prefix routing is a special type of routing with a compact routing table associated with each node (processor). Basically, each outgoing channel of a node is assigned a special label and an outgoing channel is selected if its label is a prefix of the label of the destination node. Node and channel labeling in an irregular network is done through constructing a spanning tree. The routing process follows a two-phase process of going up and then down along the spanning tree, with a possible cross channel (shortcut) between two branches of the tree between two phases. We show that the proposed routing scheme is deadlock- and livelock-free. We also compare prefix routing with the existing up*/down* routing which has been widely used in irregular networks. Possible extensions are also discussed.

In [10] the authors proved upper bounds for the arc-congestion and wave-length number of any permutation demand on a bidirected ring. In this note, we give generalizations of their results in two directions. The first one is that instead of considering only permutation demands we consider any balanced demand, and the second one is that instead of the ring network we consider any Hamilton decomposable network.

Thus, we obtain upper bounds (which are best possible in general) for the arc-congestion and wavelength number of any balanced demand on a Hamilton decomposable network. As a special case, we obtain upper bounds on arc- and edge-forwarding indices of Hamilton decomposable networks that are in many cases better than the known ones.

We equate a routing algorithm in a (faulty) interconnection network whose underlying graph is a k-ary n-cube or a hypercube, that attempts to route a packet from a fixed source node to a fixed destination node, with the sub-digraph of (healthy) links potentially usable by this routing algorithm as it attempts to route the packet. This gives rise to a naturally defined problem, parameterized by this routing algorithm, relating to whether a packet can be routed from a given source node to a given destination node in one of our interconnection networks in which there are (possibly exponentially many) faulty links. We show that there exist such problems that are PSPACE-complete (all are solvable in PSPACE) but that there are (existing and popular) routing algorithms for which the computational complexity of the corresponding problem is significantly easier (yet still computationally intractable).

Wireless Sensor Networks (WSN) consists of numerous of low cost and less-energy sensor nodes that are responsible to gather and transmit the data packets from one node to destination point. WSN has a wide range of applications over agriculture, military, traffic monitoring, instrument surveillance, and security monitoring. In WSN, the nodes are located in a specific region to create a wireless network. The effective data communication among sensors is a challenging task because of different complex parameters. Typically, clustering is a well-preferred methodology to provide the effective communication by partitioning the nodes into different clusters. Every cluster possesses individual cluster head that transmits the data to other sensor nodes. Therefore, it is substantial to choose optimal cluster head and optimal route for effective transmission with less energy consumption and less delay. To increase the network efficiency and sink utilization, an energy aware routing algorithm called Fractional Competitive Fruit Fly Optimizer (FrCFFO) is designed, which is an integration of Fractional concept into the Competitive Fruit Fly Optimizer (CFFO). Here, the energy prediction is performed using Deep Quantum Neural Network (QNN). Effective CH selection and routing is done using the proposed FrCFFO and the fitness parameter is considered depending upon the factors like energy, distance, link lifetime, trust, and delay. Moreover, the developed FrCFFO has achieved effective performance with minimum delay of 0.098sec, maximum energy of 0.233J, and maximum PDR of 90.81%.

In this paper we study the fault-tolerant properties of the Supercube, a new inter-connection network recently introduced by Sen [15]. The Supercube is a generalization of the Hypercube that can be realized for any number of nodes and not only for powers of 2. Moreover, it has the same diameter and connectivity of the Hypercube.

We shall prove that the diameter of the surviving route graph of the N-node Supercube S_N, if less than [log₂ N] nodes or edges fail, is at most 4 for any minimal routing, and exhibit a minimal routing for which the surviving route graph has diameter 2. Then, we will show that, when 2^s+2^s−1≤N<2^s+1 the failures are [log₂ N], the diameter of the surviving route graph is at most 5 for any minimal routing.

We will also prove that the fault diameter of S_N is exactly [log₂ N]+1 when N∉{2^s+1−1, 2^s+1−2, 2^s+2^s−1+1} and [log₂ N]+2 otherwise.

We study the problems of permutation routing and sorting on several models of meshes with fixed and reconfigurable row and column buses. We describe two fast and fairly simple deterministic algorithms for permutation routing on two-dimensional networks, and a more complicated algorithm for multi-dimensional networks. The algorithms are obtained by converting two known off-line routing schemes into deterministic routing algorithms, and they can be implemented on a variety of different models of meshes with buses. We also give a deterministic algorithm for 1–1 sorting whose running time matches that for permutation routing, and another algorithm that matches the bisection lower bound on reconfigurable networks of arbitrary constant dimension.

We consider routing and sorting problems on mesh connected processor arrays under a very weak model of reconfiguration: we allow only uni-directional row or column buses, point-to-point communication, one-port-at-the-time serve by each processor. We present a scheme which is asymptoticly optimal for k-k sorting, for any arbitrary k > 0. It works optimally on meshes of arbitrary dimensions d, from the linear array to hypercubic networks with d < n^1/3. The algorithm can also be used to perform k-k routing in the same time bound. We give an alternative scheme for permutation routing, which is asymptoticly slower, but has much better performance for realistic problem sizes.

In this paper we study the problem of fault-tolerant parallel routing in the star network, i.e., we assume that all processors send packets according to the prescribed protocol but some packets may fail to reach (on time) their destination. Using the Information Dispersal Algorithm (IDA) we obtain a fault-tolerant randomised routing algorithm whose probability of success is 1 - N^-Θ(n), where N = n! is the number of nodes of the star graph S_n.

Parallel object-oriented environments have a high degree of dynamicity and need specialised support to achieve efficiency of execution. Static strategies are not suitable for these environments: any prediction before execution can only roughly estimate the real behaviour. In object-oriented environments, the decision to create/destroy objects is usually taken at run-time and object allocation can change during the execution. The requirement of dynamicity should be considered in the design of every component of the support. The routing system, for instance, must ensure delivery even in case of object dynamic allocation/reallocation.

The paper argues that routing algorithms for parallel object-oriented environments in massively parallel architectures should be both adaptive and efficient. We adopted a routing strategy designed to be effective in case of objects dynamically created/destroyed and capable of moving during the execution. Our adaptive strategy does not assume any knowlegde of both object allocation and system topology configuration.

The surviving route graph R(G, ρ)/F for a graph G, a routing ρ and a set of failures F is a graph consisting of all non-faulty vertices of G and with an edge between two vertices if there are no failures in the routing between the two vertices. Numerous papers have studied the diameter of R(G, ρ)/F as a measure of the fault-tolerance of G and ρ, assuming that the cardinality of F is strictly smaller than the connectivity of G. In this paper we study the diameter of R(G, ρ)/F, when G is either the n-star graph or the n-dimensional hypercube and ρ is any minimal length routing, under the assumption that F is any set of failures not containing all the neighbours of any vertex and |F| is at most twice the connectivity of G minus 3.

Routing is the process, performed at each site of a communication network upon receipt of a message, that decides to which neighbor the message is to be sent or that the message is to be received locally. We present a general model of routing based on a decision tree representation of routing information. We describe several classes of optimally routable networks, i.e., networks for which the maximum size of a routing tree over all sites of the network is ⌈log2 n⌉.