A proposed testbed for evaluating adaptive routing algorithms

This paper discusses a newly-designed tool for evaluating routing algorithms in computer-communication networks. It is called the Adaptive Routing Testbed (ART). When implemented, ART will provide an efficient, effective means for evaluating the performance of routing algorithms in point-to-point networks. The method of simulation was chosen for this tool due to its advantages over analytical methods for this application. A major contribution of ART is its flexibility. It will simulate and evaluate the performance of a wide variety of routing algorithms under any valid network topology, switching mechanism, and traffic load. It will also simulate variations in the topology and traffic load while the algorithm is operating. Another significant contribution of ART is that the flexibility is provided without requiring the user to have programming skills. This is accomplished through a fully parameter-driven design. The specifications of the networks, traffic, component life, and routing algorithms are based on assigning values to parameters. The testbed will apply rules of logic when querying the user for parameter values: the next set of vlaues requested will be based on previous responses.     

FC3D: flow control-based distributed deadlock detection mechanism for true fully adaptive routing in wormhole networks

Two general approaches have been proposed for deadlock handling in wormhole networks. Traditionally, deadlock-avoidance strategies have been used. In this case, either routing is restricted so that there are no cyclic dependencies between channels or cyclic dependencies between channels are allowed provided that there are some escape paths to avoid deadlock. More recently, deadlock recovery strategies have begun to gain acceptance. These strategies allow the use of unrestricted fully adaptive routing, usually outperforming deadlock avoidance techniques. However, they require a deadlock detection mechanism and a deadlock recovery mechanism that is able to recover from deadlocks faster than they occur. In particular, progressive deadlock recovery techniques are very attractive because they allocate a few dedicated resources to quickly deliver deadlocked messages, instead of killing them. Unfortunately, distributed deadlock detection is usually based on crude time-outs, which detect many false deadlocks. As a consequence, messages detected as deadlocked may saturate the bandwidth offered by recovery resources, thus degrading performance. Additionally, the threshold required by the detection mechanism (the time-out) strongly depends on network load, which is not known in advance at the design stage. This limits the applicability of deadlock recovery on actual networks. We propose a novel distributed deadlock detection mechanism that uses only local information, detects all the deadlocks, considerably reduces the probability of false deadlock detection over previously proposed techniques, and is not significantly affected by variations in message length and/or message destination distribution.     

Several algorithms for finite-model adaptive control

Finite-model adaptive control problem is studied for a class of discrete-time nonlinear uncertain systems. This problem was motivated by recent efforts on the capability and limitation of feedback mechanism and has the characteristics of “essentially” finite internal uncertainties. To solve this type of problem, based on different ideas, we introduce several approaches, controller falsification, controller combination, and pseudo-parameter estimation, to design the feedback control law and rigorously establish the stability of closed-loop system for several typical algorithms in these approaches. Our results show that, under reasonably weak conditions, capable feedback control laws exist dealing with the finite internal uncertainties of the system. These results together with related results in companion papers provide partial answers to the finite-model adaptive control problem and may lead to deeper understanding on the capability of the whole feedback mechanism.     

Combined routing and flow control in computer communication networks: A two-level adaptive scheme

The problem of designing combined routing and flow control strategies for packet-switched computer communication networks is considered in this paper and a new two-level adaptive scheme is presented. State dependent models for routing and input buffer limit flow control are introduced to facilitate formulating the problem, for which a solution in the framework of system stabilization is developed. The overall decision-making consists of a distributed computation of the routing parameters and the flow control parameters at the lower level of network nodes and a computation on a slower time-scale of a set of combined parameters by a supervisor (network control center) at a higher hierarchical level. The parameters are adaptively updated at both levels to improve the network performance with respect to a set of objectives concerning delay, throughput, and buffer utilization. Some implementational aspects of the algorithm are discussed and simulation results that illustrate the performance are presented. Major strong points of the present scheme are i) adaptivity to changes in load and/or network topology, ii) capability of handling different objectives individually at different hierarchical levels, and iii) consideration of capacity constrained nodal buffers in addition to capacity limited links, unlike in the earlier developed schemes, for a more realistic representation of network environment.     

A fully adaptive routing algorithm for dynamically injuredhypercubes, meshes, and tori

Unicast V is a progressive, misrouting algorithm for packet or virtual cut-through networks. A progressive protocol forwards a message at an intermediate node if a nonfaulty profitable link is available and waits, deroutes, or aborts otherwise. A misrouting protocol uses both profitable and nonprofitable links at each node; thus, a message can move farther away from its destination at some steps. Unicast V is simple for hardware implementation, requires a very small message overhead, and makes routing decisions by local failure information only. However, it is claimed to be partially adaptive and to be able to tolerate static faults in hypercubes only. In this paper, we uncover some new features of Unicast V: (1) it is fully-adaptive, (2) it also applies to meshes and tori, and (3) it can tolerate dynamic faults by careful implementation. In addition, we also provide bounds on the performance of the algorithm     

Model reference adaptive control algorithms for industrial robots

In this paper some problems concerning the control of multifunctional manipulators (industrial robots) with high speed continuous movements are investigated. Although deterministic approaches to the control of robots, whose model are highly interconnected and non-linear, are known alternative approaches based on the Model Reference Adaptive System (MRAS) method of control are possible and useful. In the paper it is proved that a generalized MRAS control assures the convergence to a suitable reference model for a class of processes: the manipulator is shown to belong to such a class. The paper is completed by some applications evaluated by simulation.     

Compressionless routing: a framework for adaptive andfault-tolerant routing

Compressionless routing (CR) is an adaptive routing framework which provides a unified framework for efficient deadlock free adaptive routing and fault tolerance. CR exploits the tight coupling between wormhole routers for flow control to detect and recover from potential deadlock situations. Fault tolerant compressionless routing (FCR) extends CR to support end to end fault tolerant delivery. Detailed routing algorithms, implementation complexity, and performance simulation results for CR and FCR are presented. These results show that the hardware for CR and FCR networks is modest. Further, CR and FCR networks can achieve superior performance to alternatives such as dimension order routing. Compressionless routing has several key advantages: deadlock free adaptive routing in toroidal networks with no virtual channels, simple router designs, order preserving message transmission, applicability to a wide variety of network topologies, and elimination of the need for buffer allocation messages. Fault tolerant compressionless routing has several additional advantages: data integrity in the presence of transient faults (nonstop fault tolerance), permanent fault tolerance, and elimination of the need for software buffering and retry for reliability. The advantages of CR and FCR not only simplify hardware support for adaptive routing and fault tolerance, they also can simplify software communication layers     

An adaptive system for process control using genetic algorithms

Researchers at the U.S. Bureau of Mines have developed adaptive process control systems in which genetic algorithms (GAs) are used to augment fuzzy logic controllers (FLCs). GAs are search algorithms that rapidly locate near-optimum solutions to a wide spectrum of problems by modeling the search procedures of natural genetics. FLCs are rule based systems that efficiently manipulate a problem environment by modeling the “rule-of-thumb” strategy used in human decision making. Together, GAs and FLCs possess the capabilities necessary to produce powerful, efficient, and robust adaptive control systems. To perform efficiently, such control systems require a control element to manipulate the problem environment, an analysis element to recognize changes in the problem environment, and a learning element to adjust to the changes in the problem environment. Details of an overall adaptive control system are discussed. A specific laboratory acid-base pH system is used to demonstrate the ideas presented.     

An experimental study of adaptive control for evolutionary algorithms

In this paper, we investigate how adaptive operator selection techniques are able to efficiently manage the balance between exploration and exploitation in an evolutionary algorithm, when solving combinatorial optimization problems. We introduce new high level reactive search strategies based on a generic algorithm's controller that is able to schedule the basic variation operators of the evolutionary algorithm, according to the observed state of the search. Our experiments on SAT instances show that reactive search strategies improve the performance of the solving algorithm.     

The development of computer algorithms for multivariable adaptive control

Digital control algorithms suitable for insertion in a multivariable adaptive control configuration are developed. An application of the invariance principle enables the attainment of a range of control objectives with the controllers structured in pre-compensator/feedback form. Feedforward control is considered. In instances the invaritmee-developed controllers are demonstrated equivalent to suboptimal control with quadratic performance index. The techniques are illustrated by results of simulations.     

Efficient adaptive connection admission control algorithms for real-time ATM LANs

This study aims to provide adaptive communication services for real-time applications. In particular, how to admit adaptive real-time connections is addressed. Various search techniques in connection with admission control are investigated, and their tradeoffs under different performance criteria are assessed. The implementation and application of this new connection model in the NetEx system is also discussed.     

改进的实时流媒体中流量自适应控制机制

为了提高实时多媒体通信的服务质量,在综合考虑网络延迟和网络抖动对实时流媒体的影响下,定义了基于RTT的综合标志量。在此基础上,提出了一种改进的实时流量自适应控制机制。仿真结果表明,与基于丢包率和仅考虑延迟的RTT算法相比,该机制有效提高了数据流的平稳性和带宽的利用率,有更高的自适应性。     

应对CDMA系统有界干扰的鲁棒自适应功率控制

提出了一种应对CDMA系统中有界干扰的鲁棒自适应功率控制算法.仿真结果表明,与传统的功率控制算法相比,该算法性能优越,可以使用户获得更高的信噪比和较低的发射功率,且系统容量得到了提高.     

A simple method for the control of divergence in Kalman-filter algorithms

It is found that, under certain conditions, the estimation errors produced by the Standard Kalman-filter algorithm increase rapidly, and become unbounded, even though the predicted error covariance continues to decrease in accordance with the stability properties of the Kalman filter. A very simple modification, which freezes the filter gain when divergence is suspected, is suggested. The modified algorithm would keep these errors within bound without causing an appreciable increase in the computation burden.     

MF-DLB: Multimetric forwarding and directed acyclic graph-based load balancing for geographic routing in FANETs

Flying ad hoc network (FANET) comprising unmanned aerial vehicles (UAVs) emerges as a promising solution for numerous military and civil applications. Transferring data collected from the environment to the ground station (GS) is a primary concern for meeting the communication demands of most of these applications. However, the highly mobile UAVs with limited communication range, resulting in frequent topology change and intermittent connectivity, make data routing challenging. In such scenarios, geographic routing is a viable solution due to its scalability and robustness. However, the basic forwarding mechanism of geographic routing favors the neighboring UAV nearest to the destination, impacted substantially by link failures and routing holes in a dynamic environment. Additionally, routing decisions ignoring the current load over UAVs contribute to performance degradation due to the high concentration of data traffic near the GS. Thus, to address these issues, a geographic routing protocol named MF-DLB comprising multimetric forwarding (MF) and a directed acyclic graph-based load balancing (DLB) scheme is proposed to enhance packet forwarding in FANETs. MF takes account of multiple metrics related to connectivity, geographic progress, link lifetime, and residual energy to select the next hop with a stable communication link while effectively bypassing the routing holes. The second scheme, DLB, focuses on proactively maintaining routing paths near GS for load distribution among underutilized nodes to address the congestion problem. Simulations performed in network simulator ns-3 confirm the outperformance of MF-DLB over other related routing schemes in terms of different performance metrics.     

基于免疫遗传算法的区域交通自适应协调控制

提出一种基于改进免疫遗传算法的城市区域交通自适应协调控制方法.采用两层的递阶分布式结构;分阶段和分级优化控制参数(周期、相位差和绿信比),每个阶段长5~30分钟,周期、相位差由区域控制级每个阶段优化一次,绿信比由路口控制级每个周期优化一次;采用最小化平均延误时间或平均停车次数等为性能指标.周期、相位差和绿信比均采用改进的免疫遗传算法进行优化.仿真结果表明本文提出的方法是可行而有效的.     

Intelligent identification and control for autonomous guided vehicles using adaptive fuzzy-based algorithms

Fuzzy logic was first suggested as the mechanism by which humans drive cars. This paper addresses the use of fuzzy logic and algorithms towards the intelligent autonomous motion control of land vehicles. To cope with vehicle complexities, internal parametric changes, and with unpredictable environmental effects, the controllers that are presented, whilst heuristic in nature, are self-organizing or self-learning in that they generate automatically by observation an experiential rule base that models the vehicle, and via an appropriate performance index an optimal control rule base that is robust to large parametric changes. The methodology presented is applicable to any complex process which is too difficult to model or control using conventional methods, or which has relied on the experience of a human operator. An overview of fuzzy logic and static fuzzy logic control (akin to expert systems) is provided, together with illustrative examples.     

A simple universal adaptive feedback controller for chaos and hyperchaos control

A simple universal adaptive feedback controller is proposed for chaos control. In comparison with previous methods, the proposed scheme, which uses a single feedback gain and converges very fast, is suitable for application to a larger class of chaotic, hyperchaotic and nonhyperbolic chaotic systems. A sufficient condition for selecting the least feedback terms is given, and a numerical example using the Lorenz system verifies the correctness and effectiveness of the proposed approach.     

Phantom: a simple and effective flow control scheme

This paper presents Phantom, a simple constant space algorithm for rate-based flow control. As shown by our simulations, it converges fast to a fair rate allocation while generating a moderate queue length. While our approach can be easily implemented in ATM switches for managing available bit rate (ABR) traffic, it is also suitable for flow control in TCP router-based networks. Both the introduced overhead and the required modifications in TCP flow control systems are minimal. The implementation of this approach in TCP guarantees fairness and provides a unifying interconnection between TCP routers and ATM networks. The new algorithm easily inter-operates with current TCP flow control mechanisms and thus can be gradually introduced into installed-based TCP networks.     

Fully adaptive minimal deadlock-free packet routing in hypercubes,meshes, and other networks: algorithms and simulations

This paper deals with the problem of packet-switched routing in parallel machines. Several new routing algorithms for different interconnection networks are presented. While the new techniques apply to a wide variety of networks, routing algorithms will be shown for the hypercube, the two-dimensional mesh, and the shuffle-exchange. Although the new techniques are designed for packet routing, they can be used alternatively for virtual cut-through routing models. The techniques presented for hypercubes and meshes are fully-adaptive and minimal. A fully-adaptive and minimal routing is one in which all possible minimal paths between a source and a destination are of potential use at the time a message is injected into the network. Minimal paths followed by messages ultimately depend on the local congestion encountered in each node of the network. All of the new techniques are completely free of deadlock situations