A new metric for dynamic routing algorithms

A dynamic routing algorithm that has as its goal the control of congestion in a packet switching network is presented. The algorithm is based in part on the ARPANET SPF algorithm. However, instead of employing a delay metric, the authors make use of a combination of link and buffer utilizations. A detailed simulation model of the ARPANET was constructed to compare the performance of the congestion-based algorithm to the traditional delay-based (SPF) routing algorithm. The results indicate a substantial improvement in the delay and throughput of the network with the congestion-based routing algorithm     

The New Routing Algorithm for the ARPANET

The new ARPANET routing algorithm is an improvement over the old procedure in that it uses fewer network resources, operates on more realistic estimates of network conditions, reacts faster to important network changes, and does not suffer from long-term loops or oscillations. In the new procedure, each node in the network maintains a database describing the complete network topology and the delays on all lines, and uses the database describing the network to generate a tree representing the minimum delay paths from a given root node to every other network node. Because the traffic in the network can be quite variable, each node periodically measures the delays along its outgoing lines and forwards this information to all other nodes. The delay information propagates quickly through the network so that all nodes can update their databases and continue to route traffic in a consistent and efficient manner. An extensive series of tests were conducted on the ARPANET, showing that line overhead and CPU overhead are both less than two percent, most nodes learn of an update within 100 ms, and the algorithm detects congestion and routes packets around congested areas.     

Routing Techniques Used in Computer Communication Networks

An overview is provided in this paper of the routing procedures used in a number of operating networks, as well as in two commercial network architectures. The networks include TYMNET, ARPANET, and TRANSPAC. The network architectures discussed are the IBM SNA and the DEC DNA. The routing algorithms all tend to fall in the shortest path class. In the introductory sections, routing procedures in general are discussed, with specialization to shortest path algorithms. Two shortest path algorithms, one appropriate for centralized computation, the other for distributed computation, are described. These algorithms, in somewhat modified form, provide the basis for the algorithms actually used in the networks discussed.     

基于蚁群系统的QoS单播路由算法

针对QoS路由算法中的QoS要求、资源的优化利用和负载均衡3方面问题,对原有的算法模型进行了改进,提出了相应的启发式信息和链路代价计算公式。对基本算法中的步骤进行改进,使算法能准确、迅速地找到全局最优解。实验结果表明,算法能在整网性能,尤其是网络负载均衡方面大幅优化了传统QoS单播路由算法。     

Dimensioning of adaptively routed networks

The authors present an algorithm for the multihour dimensioning of telephone networks operating with residual capacity adaptive routing. The method is based on dimensioning techniques for networks operating with nonhierarchical alternate routing and relies on a conservative approximation for traffic evaluation. It is a decomposition method involving a set of fixed-point equations which are solved iteratively until the Kuhn-Tucker conditions are met. The authors investigate the convergence of the method and find that some of the variables of the model are almost stationary after only a few iterations. This leads to some simplifications that make it suitable for large networks with minor modifications. They also investigate the optimality of adaptive routing by comparing it with the optimal routing coefficients and verify the operation of this routing in a network dimensioned for adaptive technique. A question of interest is how well an adaptive algorithm can adapt to dimensioning errors and how well it compares with the optimal routing in these situations     

Measuring and Improving the Performance of Network Mobility Management in IPv6 Networks

Measuring the performance of an implementation of a set of protocols and analyzing the results is crucial to understanding the performance and limitations of the protocols in a real network environment. Based on this information, the protocols and their interactions can be improved to enhance the performance of the whole system. To this end, we have developed a network mobility testbed and implemented the network mobility (NEMO) basic support protocol and have identified problems in the architecture which affect the handoff and routing performance. To address the identified handoff performance issues, we have proposed the use of make-before-break handoffs with two network interfaces for NEMO. We have carried out a comparison study of handoffs with NEMO and have shown that the proposed scheme provides near-optimal performance. Further, we have extended a previously proposed route optimization (RO) scheme, OptiNets. We have compared the routing and header overheads using experiments and analysis and shown that the use of the extended OptiNets scheme reduces these overheads of NEMO to a level comparable with Mobile IPv6 RO. Finally, this paper shows that the proposed handoff and RO schemes enable NEMO protocol to be used in applications sensitive to delay and packet loss.     

Online multicast routing with bandwidth guarantees: a new approach using multicast network flow

We present a new algorithm for online routing of bandwidth-guaranteed multicasts where routing requests arrive one by one without any prior knowledge of future requests. A multicast routing request consists of a source, a set of receivers, and a bandwidth requirement. Two multicast applications of interest are routing of point-to-multipoint label-switched paths in multiprotocol label switched (MPLS) networks, and the provision of bandwidth-guaranteed virtual private network (VPN) services under the "hose" service model. Without prior knowledge of multicast requests, offline multicast routing algorithms cannot be used. Online algorithms are needed to handle requests arriving one by one and to satisfy as many potential future demands as possible. Our new online algorithm is based on the idea that a newly routed multicast must follow a route that does not interfere too much with network paths that may be critical to satisfy future demands. We develop a multicast tree selection heuristic based on the idea of deferred loading of certain critical links. The algorithm identifies them as links that, if heavily loaded, would make it impossible to satisfy future demands between certain ingress-egress pairs. The algorithm uses link-state information and some auxiliary capacity information for multicast tree selection and is amenable to distributed implementation. Unlike previous algorithms, our algorithm exploits any available knowledge of the network ingress-egress points of potential future demands, even though the demands themselves are unknown. It performs very well.     

RPSF: A Routing Protocol with Selective Forwarding for Mobile Ad-Hoc Networks

Many existing reactive routing algorithms for mobile ad-hoc networks use a simple broadcasting mechanism for route discovery which can lead to a high redundancy of route-request messages, contention, and collision. Position-based routing algorithms address this problem but require every node to know the position and velocity of every other node at some point in time so that route requests can be propagated towards the destination without flooding the entire network. In a general ad-hoc network, each node maintaining the position information of every other node is expensive or impossible. In this paper, we propose a routing algorithm that addresses these drawbacks. Our algorithm, based on one-hop neighborhood information, allows each node to select a subset of its neighbors to forward route requests. This algorithm greatly reduces the number of route-request packets transmitted in the route-discovery process. We compare the performance of our algorithm with the well known Ad-hoc On-demand Distance Vector (AODV) routing algorithm. On average, our algorithm needs less than 12.6% of the routing-control packets needed by AODV. Simulation results also show that our algorithm has a higher packet-delivery ratio and lower average end-to-end delay than AODV.     

RATES: a server for MPLS traffic engineering

It has been suggested that one of the most significant reasons for multiprotocol label switching (MPLS) network deployment is network traffic engineering. The goal of traffic engineering is to make the best use of the network infrastructure, and this is facilitates by the explicit routing feature of MPLS, which allows many of the shortcomings associated with current IP routing schemes to be addressed. This article describes a software system called Routing and Traffic Engineering Server (RATES) developed for MPLS traffic engineering. It also describes some new routing ideas incorporated in RATES for MPLS explicit path selection. The RATES implementation consists of a policy and flow database, a browser-based interface for policy definition and entering resource provisioning requests, and a Common Open Policy Service protocol server-client implementation for communicating paths and resource information to edge routers. RATES also uses the OSPF topology database for dynamically obtaining link state information. RATES can set up bandwidth-guaranteed label-switched (LSPs) between specified ingress-egress pairs. The path selection for LSPs is on a new minimum-interference routing algorithm aimed at making the best use of network infrastructure in an online environment where LSP requests arrive one by one with no a priori information about future requests. Although developed for an MPLS application, the RATES implementation has many similarities in components to an intradomain differentiated services bandwidth broker     

Dynamic multicast routing based on mean number of new callsaccepted before blocking for single rate loss networks

In this paper, we investigate the dynamic multicast routing problem for single rate loss network and briefly discuss the dynamic multicast routing algorithm called least load multicast routing (LLMR). We propose a new multicast routing algorithm called maximum mean number of new calls accepted before blocking multicast routing (MCBMR), which can more accurately capture the current and future loading of a network. Simulation results show that this algorithm, compared with LLMR, not only has a smaller network revenue loss, but also results in smaller call blocking probabilities for all classes of traffic. We also discuss the implementation issues of our proposed algorithm and develop two approximation methods, state approximation and curve fitting, which can reduce the measurement complexity significantly with only a slight performance degradation     

A Binary PSO Approach for Improving the Performance of Wireless Sensor Networks

Wireless sensor networks are used for low-cost unsupervised observation in a wide-range of environments and their application is largely constrained by the limited power sources of their constituent sensor nodes. Techniques such as routing and clustering are promising and can extend network lifetime significantly, however finding an optimal routing and clustering configuration is a NP-hard problem. In this paper, we present an energy efficient binary particle swarm optimization based routing and clustering algorithm using an intuitive matrix-like particle representation. We propose a novel particle update strategy and an efficient linear transfer function which outperform previously employed particle update strategies and some traditional transfer functions. Detailed experiments confirmed that our routing and clustering algorithm yields significantly higher network lifetime in comparison to existing algorithms. Furthermore, our results suggest that Binary PSO is better equipped to solve discrete problems of routing and clustering than its continuous counterpart, PSO.

     

WRE‐OLSR,a new scheme for enhancing the lifetime within ad hoc and wireless sensor networks

Within ad hoc and wireless sensor networks, communications are accomplished in dynamic environments with a random movement of mobile devices. Thus, routing protocols over these networks are an important concern to offer efficient network scalability, manage topology information, and prolong the network lifetime. Optimized link state routing (OLSR) is one of those routing protocols implemented in ad hoc and wireless sensor networks. Because of its proactive technique, routes between two nodes are established in a very short time, but it can spend a lot of resources for selecting the multipoint relays (MPRs: nodes responsible for routing data) and exchanging topology control information. Thus, nodes playing for a long time a role of MPR within networks implementing such protocol can rapidly exhaust their batteries, which create route failures and affect the network lifetime. Our main approach relies on analyzing this concern by introducing a new criterion that implements a combination between the residual energy of a node and its reachability in order to determine the optimal number of MPRs and sustain the network lifetime. Simulations performed illustrate obviously that our approach is more significant compared with the basic heuristic used by original OLSR to compute the MPR set of a node.     

无线mesh网的跨层设计及其应用

根据无线mesh网跨层设计的基本原理,分析了跨层设计系统中各模块的功能和各种需要考虑的因素。提出一种综合了无线mesh网高效的状态信息交换方法和先进路由算法的跨层设计实现方案,可根据网络当前链路状态、拥塞情况和能量等因素,合理选择传输路径。同时还给出了该方法在电网高压输电监控系统中的应用实例。仿真和实验表明所提方案在实际应用时在强壮性、吞吐量和时延等方面都有良好的性能。     

Throughput in the ARPANET--Protocols and Measurement

The speed at which large files can travel across a computer network is an important performance measure of that network. In this paper we examine the achievable sustained throughput in the ARPANET. Our point of departure is to describe the procedures used for controlling the flow of long messages (multipacket messages) and to identify the limitations that these procedures place on the throughput. We then present the quantitative results of experiments which measured the maximum throughput as a function of topological distance in the ARPANET. We observed a throughput of approximately 38 kbit/s at short distances. This throughput falls off at longer distances in a fashion which depends upon which particular version of the flow control procedure is in use; for example, at a distance of 9 hops, an October 1974 measurement gave 30 kbit/s, whereas a May 1975 experiment gave 27 kbit/s. The two different flow control procedures for these experiments are described, and the sources of throughput degradation at longer distances are identified, a major cause being due to a poor movement of critical limiting resources around in the network (this we call "phasing"). We conclude that flow control is a tricky business, but in spite of this, the ARPANET throughput is respectably high.     

基于多阶梯度的光网络链路抽象方法

文章提出一种多阶梯度链路抽象方法以及在多域路由中辅助此方法来对连接建立请求进行判断的处理模式.使用该链路抽象方法以及辅助处理模式可以近似无差错地体现原始信息,为多域路由提供准确的信息.仿真分析表明,使用多阶梯度链路抽象方法和辅助处理,可以大大减小连接建立请求的误接受和误拒绝的概率,提高网络资源利用率和网络整体性能.     

Maximum lifetime routing in wireless sensor networks

A routing problem in static wireless ad hoc networks is considered as it arises in a rapidly deployed, sensor based, monitoring system known as the wireless sensor network. Information obtained by the monitoring nodes needs to be routed to a set of designated gateway nodes. In these networks, every node is capable of sensing, data processing, and communication, and operates on its limited amount of battery energy consumed mostly in transmission and reception at its radio transceiver. If we assume that the transmitter power level can be adjusted to use the minimum energy required to reach the intended next hop receiver then the energy consumption rate per unit information transmission depends on the choice of the next hop node, i.e., the routing decision. We formulate the routing problem as a linear programming problem, where the objective is to maximize the network lifetime, which is equivalent to the time until the network partition due to battery outage. Two different models are considered for the information-generation processes. One assumes constant rates and the other assumes an arbitrary process. A shortest cost path routing algorithm is proposed which uses link costs that reflect both the communication energy consumption rates and the residual energy levels at the two end nodes. The algorithm is amenable to distributed implementation. Simulation results with both information-generation process models show that the proposed algorithm can achieve network lifetime that is very close to the optimal network lifetime obtained by solving the linear programming problem.     

A Virtual Topology Based Routing Protocol for Multihop Dynamic Wireless Networks

In this paper, a new hierarchical multihop routing algorithm and its performance evaluation is presented for fully dynamic wireless networks. The routing algorithm operates on a virtual topology obtained by partitioning the routing information for mobile terminals and mobile base stations into a hierarchical, distributed database. Based on the virtual topology, each mobile base station stores a fraction of the routing information to balance the complexity of the location-update and the path-finding operations. Mobility of the network entities changes the load distribution and causes processing and memory bottlenecks in some parts of the network. However, since the network routing elements are also mobile, their movement can be used to distribute the load. Thus, new load balancing schemes are intoduced to distribute the routing overhead uniformly among the mobile base stations. The performance of the hierarchical multihop routing algorithm is investigated through simulations. It is shown that the routing protocol can cope with high mobility and deliver packets to the destinations successfully.     

Simulation of the Tree Algorthm in ATM Networks

ＡＴＭｉｓｄｅｐｅｎｄｅｎｔｏｎｔｈｅｄｉｆｆｅｒｅｎｔｃｈａｒａｃｔｅｒｉｓ ｔｉｃｓｉｎａｎｉｎｔｅｇｒａｔｅｄｗａｙｔｏｔｒａｎｓｍｉｔｓｅｒｖｉｃｅｓ[1 ] .ＡＴＭｎｅｔｗｏｒｋｍａｙｉｎｃｌｕｄｅｖｉｄｅｏ ,ｖｏｉｃｅａｎｄｉｍａｇｅｓ,ｉｎｔｅｒａｃｔｉｖｅｃｏｍｐｕｔｅｒｄａｔａａｎｄｆｉｌｅｔｒａｎｓｆｅｒｓ.Ａｎｉｍ ｐｏｒｔａｎｔａｐｐｌｉｃａｔｉｏｎｏｆａｎＡＴＭｎｅｔｗｏｒｋｉｓｔｏｓｕｐｐｏｒｔｍｕｌｔｉｍｅｄｉａｓｙｓｔｅｍｓ,ｓｕｃｈａｓｖｉｄｅｏｃｏｎｆｅｒｅｎｃｉｎｇ…     

Handoffs in Cellular Wireless Networks: The Daedalus Implementation and Experience

Network protocols in cellular wireless data networks must update routes as a mobile host moves between cells. These routing updates combined with some associated state changes are called handoffs. Most current handoff schemes in wireless networks result in data loss or large variations in packet delivery times. Unfortunately, many applications, such as real-time multimedia applications and reliable transport protocols, adapt to long term estimates of end-to-end delay and loss. Violations and rapid fluctuations of these estimates caused by handoff processing often result in degraded performance. For example, loss during handoff adversely affects TCP performance [4], and high packet loss and variable delays result in poor real-time multimedia performance. In this paper, we describe a multicast-based protocol that eliminates data loss and incurs negligible delays during a handoff. The basic technique of the algorithm is to anticipate a handoff using wireless network information in the form of received signal strengths and to multicast data destined for the mobile host to nearby base stations in advance. This routing, combined with intelligent buffering techniques at the base stations, enables very rapid routing updates and eliminates data loss without the use of explicit data forwarding. We have implemented this protocol using IP Multicast and Mobile IP-like routing. In our implementation, handoffs typically take between 8 and 15 ms to complete and result in no data loss.     

On the interplay of network structure and routing strategies in scale-free networks

In this paper, we examine how the structural characteristics of network topologies affect the network performance, and we examine the interplay between structural characteristics of network topologies and routing strategies. We consider routing strategies subject to practical constraints (router technology) and economic considerations (link costs) at layer 3. We propose two new routing methods suitable for implementation in large networks and examine various routing strategies (local, global, and hybrid) with tunable parameters and explore how they can enhance the network performance. We find that there exists an optimal range of values for the tunable parameters to achieve high network performance which depends on the structural properties of the network topology. We also show that our proposed routing scheme, which requires minimum local information, achieves high network performance.