Modelling for flexible manufacturing systems and structural properties of optimal work routing policy

We consider flexible manufacturing systems (FMSs) which are composed of a set of workstations linked together with a material handling system (MHS). Each workstation consists of an input buffer, a single machine and an output buffer. The MHS consisting of a single cart routes work among the workstations according to the process paths required by the work. We deal with an optimal control problem in this FMS. We model the FMS as a closed queueing network. In the model, the cart routes the work to the workstations in accordance with a Markov routing with exponentially distributed routing time, and the machines process work with exponentially distributed processing time. An objective is to find a work routing policy that maximizes the total expected reward earned by operating machines. This optimal control problem is formulated as an undiscounted semi-Markov decision process. Structural properties of an optimal policy are analysed. Moreover, a sufficient condition is derived for the optimal policy to be of control limit type. An example is given to illustrate the result.     

Adaptive deadlock- and livelock-free routing with all minimal pathsin torus networks

This paper consists of two parts. In the first part, two new algorithms for deadlock- and livelock-free wormhole routing in the torus network are presented. The first algorithm, called Channels, is for the n-dimensional torus network. This technique is fully-adaptive minimal, that is, all paths with a minimal number of hops from source to destination are available for routing, and needs only five virtual channels per bidirectional link, the lowest channel requirement known in the literature for fully-adaptive minimal worm-hole routing. In addition, this result also yields the lowest buffer requirement known in the literature for packet-switched fully-adaptive minimal routing. The second algorithm, called 4-Classes, is for the bidimensional torus network. This technique is fully-adaptive minimal and requires only eight virtual channels per bidirectional link. Also, it allows for a highly parallel implementation of its associated routing node. In the second part of this paper, four worm-hole routing techniques for the two-dimensional torus are experimentally evaluated using a dynamic message injection model and different traffic patterns and message lengths     

YOMNA – An efficient deadlock-free multicast wormhole algorithm in 2-D mesh multicomputers

A mesh network is a popular architecture which has been implemented in many multicomputer systems. It is preferred because it offers useful edge connectivity and is partitioned into units that are still meshes. It is also scalable and has a number of features that make it particularly amenable to high-performance computing. The 2-D mesh topology has become increasingly important to multicomputer design because of its many desirable properties including scalability, low bandwidth and fixed degree of nodes.The essential pattern in new multicomputer generations is the multicast wormhole pattern, which corresponds to one-to-many communication in which one source sends the same message to multiple destination nodes. In wormhole routing, a message is decomposed into words or flits, and flits of one message may be spread out among several nodes. Deadlock in the interconnection network occurs when no message can advance towards its destination. Some deadlock-free routing algorithms for wormhole routing were proposed, but the network latency and the network traffic were not taken into consideration. An optimal message routing should achieve both minimum traffic and minimum latency for the communication patterns involved. Unfortunately, finding optimal message routing has been shown to be NP-hard for most common multicomputer topologies.In this paper, an efficient algorithm (YOMNA) is introduced to find a deadlock-free multicast wormhole routing in 2-D mesh parallel machines. YOMNA algorithm is a tree-based technique, in which the router simultaneously sends incoming flits on more than one outgoing channel. YOMNA algorithm is compared with the dual-path multicast routing, which is a path-based technique. YOMNA algorithm has proved to be deadlock free. The network latency and the network traffic are calculated for YOMNA algorithm and for the dual-path multicast routing. The results demonstrate that YOMNA algorithm outperformed the dual-path routing.     

On the performance of multicomputer interconnection networks

Several researchers have analysed the performance of k-ary n-cubes taking into account channel bandwidth constraints imposed by implementation technology, namely the constant wiring density and pin-out constraints for VLSI and multiple-chip technology respectively. For instance, Dally [IEEE Trans. Comput. 39(6) (1990) 775], Abraham [Issues in the architecture of direct interconnection networks schemes for multiprocessors, Ph.D. thesis, University of Illinois at Urbana-Champaign, 1992], and Agrawal [IEEE Trans. Parallel Distributed Syst. 2(4) (1991) 398] have shown that low-dimensional k-ary n-cubes (known as tori) outperform their high-dimensional counterparts (known as hypercubes) under the constant wiring density constraint. However, Abraham and Agrawal have arrived at an opposite conclusion when they considered the constant pin-out constraint. Most of these analyses have assumed deterministic routing, where a message always uses the same network path between a given pair of nodes. More recent multicomputers have incorporated adaptive routing to improve performance. This paper re-examines the relative performance merits of the torus and hypercube in the context of adaptive routing. Our analysis reveals that the torus manages to exploit its wider channels under light traffic. As traffic increases, however, the hypercube can provide better performance than the torus. Our conclusion under the constant wiring density constraint is different from that of the works mentioned above because adaptive routing enables the hypercube to exploit its richer connectivity to reduce message blocking.     

Optimal routing policy of a stochastic-flow network

Under the assumption that each arc’s capacity of the network is deterministic, the quickest path problem is to find a path sending a given amount of data from the source to the sink such that the transmission time is minimized. However, in many real-life networks such as computer systems, telecommunication systems, etc., the capacity of each arc is stochastic due to failure, maintenance, etc. Such a network is named a stochastic-flow network. Hence, the minimum transmission time is not fixed. We try to evaluate the probability that d units of data can be sent through the stochastic-flow network within the time constraint according to a routing policy. Such a probability is named the system reliability, which is a performance index to measure the system quality. This paper mainly finds the optimal routing policy with highest system reliability. The solution procedure is presented to calculate the system reliability with respect to a routing policy. An efficient algorithm is subsequently proposed to derive the optimal routing policy.     

Depth-first search approach for fault-tolerant routing in hypercubemulticomputers

Using depth-first search, the authors develop and analyze the performance of a routing scheme for hypercube multicomputers in the presence of an arbitrary number of faulty components. They derive an exact expression for the probability of routing messages by way of optimal paths (of length equal to the Hamming distance between the corresponding pair of nodes) from the source node to an obstructed node. The obstructed node is defined as the first node encountered by the message that finds no optimal path to the destination node. It is noted that the probability of routing messages over an optimal path between any two nodes is a special case of the present results and can be obtained by replacing the obstructed node with the destination node. Numerical examples are given to illustrate the results, and they show that, in the presence of component failures, depth-first search routing can route a message to its destination by means of an optimal path with a very high probability     

移动社会网络中基于社区的消息机会传输策略

移动社会网络是一种由大量具有社会特征的节点组成的机会网络.已有的基于社区的路由算法大多选用社会性最优的节点参与转发,而没有考虑到社区分布对节点移动的影响,将这些算法直接用于移动社会网络中会导致网络资源消耗高、传输成功率低等问题.针对这些问题,提出一种基于社区的消息机会传输算法,在社区间根据节点到目标社区的传输概率选择社区间的最优传输路径,在社区内选择与目标节点相遇概率较高的节点完成社区内传输.仿真实验结果表明,在移动社会网络中,该算法与 Prophet,Spray and Wait 等经典算法相比,提高了消息传输成功率,降低了网络开销.     

A method to evaluate routing policy through p minimal paths for stochastic case

In this paper, a stochastic-flow network is presented to model a computer network in which each arc has various possible capacities and may fail. In order to shorten the transmission time, the transmission protocol allowing the data to be sent through multiple minimal paths simultaneously is utilized for the computer network. However, the minimum transmission time to send a given amount of data is not fixed due to the property of stochastic capacity. Accordingly, the first addressed issue is to evaluate the probability that the network is able to send the data within a time constraint by adopting the transmission protocol. Such a probability is named as transmission reliability that is regarded as a performance indicator to measure the QoS for a computer network. Without knowing all minimal paths in advance, an efficient solution procedure is proposed to calculate transmission reliability. The experimental results of 35 random networks show that the proposed algorithm can be executed efficiently. Moreover, in order to increase transmission reliability, the network administrator decides the routing policy to designate the first and the second priority p minimal paths. The second addressed issue is to evaluate transmission reliability associated with the routing policy. A sort criterion is subsequently presented to find an ideal routing policy.     

基于规则引擎的无线传感器网络动态路由系统

无线传感器网络路由协议往往是针对特定的任务类型和网络状态设计的,动态路由系统可以在运行时,自适应地选择性能最优的路由协议.利用规则引擎设计了一种无线传感器网络动态路由系统.采用了模块化的设计方法,使得多路由协议共存时可以共享资源.利用规则引擎的灵活性和智能性实现路由协议的自适应切换机制.实验结果显示,在多任务网络环境下,动态路由在满足服务质量的同时可以有效地降低网络能耗.     

Dynamic Prediction based Multi Queue (DPMQ) drop policy for probabilistic routing protocols of delay tolerant network

Two most important issues should be considered to achieve data delivery in DTN networking: routing protocols for the network and intelligent buffer management policy for everyone node in the network. The routing scheme decides which messages should be forwarded when nodes meet, and the buffer management policy determines which message is purged when the buffer overflows in a node. This study proposes a buffer management policy named as Dynamic Prediction based Multi Queue (DPMQ) for probabilistic routing protocols. It works by classification of local buffer into three queues of messages, which are DCTL, HPTL and LPTL. The simulation results have proven that the DPMQ performs well as compared to DLA, DOA, MOFO, LIFO, LEPR and LIFO in terms of reducing the message relay, message drop, hop counts average and overhead while rising in the delivery probability.