Avoiding Transient Loops During the Convergence of Link-State Routing Protocols

When using link-state protocols such as OSPF or IS-IS, forwarding loops can occur transiently when the routers adapt their forwarding tables as a response to a topological change. In this paper, we present a mechanism that lets the network converge to its optimal forwarding state without risking any transient loops and the related packet loss. The mechanism is based on an ordering of the updates of the forwarding tables of the routers. Our solution can be used in the case of a planned change in the state of a set of links and in the case of unpredictable changes when combined with a local protection scheme. The supported topology changes are link transitions from up to down, down to up, and updates of link metrics. Finally, we show by simulations that sub-second loop-free convergence is possible on a large Tier-1 ISP network.     

Forwarding state scalability for multicast provisioning in IP networks

Forwarding state scalability is one of the critical issues that delay the multicast deployment in IP networks. With traditional multicast routing protocols, a forwarding tree is built for each multicast session, and each router is required to maintain a forwarding entry for each multicast session whose distribution tree passes through the router. This poses the multicast forwarding state scalability issue when the number of concurrent multicast sessions is very large. We first present a survey of existing work addressing this scalability issue for providing scalable IP multicast. Then we extend an existing multicast routing protocol, Multicast Extension to OSPF (MOSPF), to scale well with respect to the number of concurrent multicast sessions by introducing tunnel support. This extension aims to reduce the protocol overhead associated with MOSPF. Simulation results show that the extension can significantly reduce multicast forwarding state and computational overhead at routers without affecting the per-destination shortest path characteristic of a resulting tree or introducing extra control overhead.     

Dissemination of routing information in broadcast networks: OSPFversus IS-IS

OSPF and IS-IS are two main standard link state routing protocols designed to operate in various complex network topologies. One aspect that both protocols handle is the reliable dissemination of routing information over broadcast networks such as Ethernet and FDDI. Both protocols suggest different schemes for this purpose and in this article we compare the two. The performance criteria being checked are: the longest arrival time of a routing update packet at all the routers; the average arrival time of routing update packets at all the routers; the total required bandwidth; and the number of memory accesses a router performs, which is evidence of the amount of internal work it performs. We find that in our model of broadcast networks the scheme suggested in IS-IS is more efficient than that of OSPF in terms of the arrival times of routing update packets. In particular, the average arrival time of routing update packets in OSPF is 2-10 times longer than in IS-IS. In terms of the bandwidth each scheme consumes, there are scenarios where OSPF outperforms IS-IS and vice versa. In terms of the number of memory accesses routers perform in each scheme, IS-IS outperforms OSPF     

Self-configuring loop-free alternates with high link failure coverage

A change in network topology triggers the re-convergence process of routing protocols. The re-convergence time of current routing protocols (e.g. OSPF) is constrained by the possibility of having transient loops due to the independent calculation of shortest paths between routers affected by a network failure. Several IP Fast-ReRoute (IPFRR) schemes have been developed to pro-actively calculate and install alternate forwarding entries almost instantaneously once a topology update message is received, without causing temporary micro-loops. The IPFRR scheme which has been used most extensively so far makes use of Loop-Free Alternates (LFA). While these are easy to configure, LFAs still require manual configuration, and the resulting ratio of covered link failures is only about 60 to 70 percent. This paper presents a logical extension of the Loop-Free Alternate concept, proposes a self-configuring scheme to populate the corresponding alternate entries, and evaluates the performance of the scheme with respect to coverage, configuration time and path length in a simulation environment.     

Differentiated transmission services and optimization based on two‐dimensional forwarding for Internet traffic in the AS

Two‐dimensional routing (TD routing) implements flexible multipath transmission according to the inherent fields of IP packets. However, it may cause large overhead on routers' control plane and data plane. Focusing on autonomous systems with multiple exits, this paper proposes a differentiated transmission services and optimization based on two‐dimensional forwarding for Internet traffic in the autonomous system (AS) (DOTF). The optimal path from the access router to the border router is calculated by the border router. Then two‐dimensional routing information (TDRI) is advertised hop by hop along the reverse path of the optimal path to establish a TD transmission path. DOTF propagates routing information by extending the open shortest path first (OSPF). It compresses message content and optimizes the TDRI structure. TDRI is only released on the specific paths, which greatly reduces the resource consumption in the routers' control plane and data plane. We also analyze the merging of TD routing and one‐dimensional routing (OD routing), reducing the deployment of TD routing entries (TD‐REs). Our experiments on real routers demonstrate the performance of DOTF. The convergence characteristics of TD routing are also analyzed.     

Scalable multi-QoS IP+ATM switch router architecture

This article proposes a scalable multi-QoS IP+ATM switch router architecture. The proposed switch router is based on a core ATM switching system with multi-QoS capability. Forwarding engines and a routing engine are attached in front of the line cards of the ATM switching system. The FEs and RE are interconnected with each other via internal VCs. A novel longest matching algorithm is employed at the FE to achieve packet forwarding at wire-speed of OC-12c rate (622.08 Mb/s). Wire-speed unicast and multicast packet forwarding are performed using point-to-point and point-to-multipoint VCs in a unified way. Because FEs and RE are decoupled from the base ATM switching system, the full spectrum of ATM QoS capability is nicely applied for IP QoS control with a packet classification at the edge of the network. The core switching fabric is scalable from 40 to 160 Gb/s capacity (371 MPPS in terms of packet forwarding throughput). Feedback rate control is employed at each line card to eliminate congestion in the high-speed core switching fabric even with a small amount of buffer.     

并行网络模拟中远程路由策略的研究

首先对并行网络模拟所采用的远程路由策略进行了分析研究,之后提出了基于优化边界的远程路由策略.该策略用边界路由器ID取代目的IP地址作为路由转发方式,有效地提高了路由查询速度.同时,通过树区域收缩、后连节点去重和边界路由器去重3种方法降低了内存的占用量.基于PDNS的实验结果表明,相对于基于边界路由器的远程路由策略,该方法降低了85％的内存使用量,并减少了75％的模拟时间.     

Mesh IP Video Surveillance Systems Model Design and Performance Evaluation

This paper proposes a model for Internet Protocol (IP) mesh video surveillance systems and presents the performance evaluation of Ah-hoc On-demand Distance Vector (AODV) and Open Shortest Path First (OSPF) routing protocols in wireless mesh video surveillance system. A wireless mesh video surveillance network consists of IP cameras linked to mesh routers which are then linked to the mesh gateways. Local monitoring can be done by inserting a switch or router between the gateways and the Internet while remote monitoring can be done through the Internet. Routing provides selection, constructing and management of routes in order to maximize throughput and minimize video packet losses, end-to-end delays and Jitter. Results show that the OSPF routing protocol outperformed the AODV in throughput, packet loss, end-to- end delay and Jitter terms with a throughput advantage of 35%.     

核心路由器转发引擎缓存需求分析

 路由器是一种存储转发设备,其缓存设置的大小直接影响路由器的性能,进而还会影响整个网络的性能.本文针对路由器核心部件—转发引擎的缓存需求进行分析.首先,将流水线技术引入转发引擎设计中,提出了一条转发引擎流水线,然后分转发引擎处理能力不小于、小于外部输入速率两种情况对转发引擎缓存需求进行了分析.分析结果和实验表明:当处理能力不小于外部输入速率时,几个最长包的缓存便能满足转发引擎的缓存需求,当处理能力小于外部输入速率时,从缓存的使用效率来看,小数量缓存(10个包左右的缓存)仍然是一个合理的选择,更大的缓存对丢包率的降低作用并不明显.     

Design of OSPF networks using subpath consistent routing patterns

We address the problem of designing IP networks where the traffic is routed using the OSPF protocol. Routers in OSPF networks use link weights set by an administrator for determining how to route the traffic. The routers use all shortest paths when traffic is routed to a destination, and the traffic is evenly balanced by the routers when several paths are equally short. We present a new model for the OSPF network design problem. The model is based on routing patterns and does not explicitly include OSPF weights. The OSPF protocol is modeled by ensuring that all pairs of routing patterns are subpath consistent, which is a necessary condition for the existence of weights. A Lagrangean heuristic is proposed as solution method, and feasible solutions to the problem are generated using a tabu search method. Computational results are reported for random instances and for real-life instances.     

Using tunneling techniques to realize virtual routers

The evolution of the router architecture has gradually changed from a conventional architecture, which processes all functions on one operating system/processor, to a remote architecture, which can be split into a control plane and a data plane with their respective functions. The control plane is mainly responsible for the operations of the routing/signaling protocols and the data plane is responsible for forwarding the large amount of data packets. Furthermore, the remote architecture facilitates the realization of virtual routers. Virtual routers are created basically by logically splitting a routing processor in the control plane into many virtual routing units that have independent routing tables, use independent protocols, and connect to the external network through different interfaces. A virtual router with a remote architecture is more flexible and efficient than conventional routers; however, it requires an additional communication mechanism between the control plane and the data plane. We propose using existing tunneling techniques to provide a communication mechanism between the control plane and the data plane. Many design and implementation issues on the software architecture and protocol ramification are identified. We discuss solutions to these issues and successfully demonstrate a working virtual router with our proposed solutions.     

OPERA: an optical packet experimental routing architecture withlabel swapping capability

This paper describes experimental and simulation results of the optical packet experimental routing architecture (OPERA) project. The OPERA network is based on a novel optical network interface router design that is optically regenerative and supports optical Internet protocol related functions including label swapping, packet routing and forwarding operations and wavelength reuse. Routing is based on subcarrier multiplexed header addressing, packet-rate wavelength conversion, and arrayed waveguide router technology. The routers are cascadable and use a unique double stage wavelength converter that supports header regeneration/replacement and maintains the payload extinction ratio. This approach overcomes dispersion limitations normally encountered using double sideband subcarrier multiplexing across a network. A discrete time simulation of the physical transport in an 8-hop network is reported. Multihop routing is experimentally demonstrated between two all-optical nodes and three input-output (I-O) ports of a waveguide grating array router. Packet-rate subcarrier header processing and wavelength conversion between six wavelengths is shown with high signal-to-noise ratio (SNR) of recovered payload and headers at each hop     

Integrating machine learning in ad hoc routing: A wireless adaptive routing protocol

The nodes in a wireless ad hoc network act as routers in a self‐configuring network without infrastructure. An application running on the nodes in the ad hoc network may require that intermediate nodes act as routers, receiving and forwarding data packets to other nodes to overcome the limitations of noise, router congestion and limited transmission power. In existing routing protocols, the ‘self‐configuring’ aspects of network construction have generally been limited to the construction of routes that minimize the number of intermediate nodes on a route while ignoring the effects that the resulting traffic has on the overall communication capacity of the network. This paper presents a context‐aware routing metric that factors the effects of environmental noise and router congestion into a single time‐based metric, and further presents a new cross‐layer routing protocol, called Warp‐5 (Wireless Adaptive Routing Protocol, Version 5), that uses the new metric to make better routing decisions in heterogeneous network systems. Simulation results for Warp‐5 are presented and compared to the existing, well‐known AODV (Ad hoc On‐Demand Distance Vector) routing protocol and the reinforcement‐learning based routing protocol, Q‐routing. The results show Warp‐5 to be superior to shortest path routing protocols and Q‐routing for preventing router congestion and packet loss due to noise. Copyright © 2011 John Wiley & Sons, Ltd.     

New dynamic algorithms for shortest path tree computation

The open shortest path first (OSPF) and IS-IS routing protocols widely used in today's Internet compute a shortest path tree (SPT) from each router to other routers in a routing area. Many existing commercial routers recompute an SPT from scratch following changes in the link states of the network. Such recomputation of an entire SPT is inefficient and may consume a considerable amount of CPU time. Moreover, as there may coexist multiple SPTs in a network with a set of given link states, recomputation from scratch causes frequent unnecessary changes in the topology of an existing SPT and may lead to routing instability. We present new dynamic SPT algorithms that make use of the structure of the previously computed SPT. Besides efficiency, our algorithm design objective is to achieve routing stability by making minimum changes to the topology of an existing SPT (while maintaining shortest path property) when some link states in the network have changed. We establish an algorithmic framework that allows us to characterize a variety of dynamic SPT algorithms including dynamic versions of the well-known Dijkstra, Bellman-Ford, D'Esopo-Pape algorithms, and to establish proofs of correctness for these algorithms in a unified way. The theoretical asymptotic complexity of our new dynamic algorithms matches the best known results in the literature     

Adaptive quality of service‐based routing approaches: development of neuro‐dynamic state‐dependent reinforcement learning algorithms

In this paper, we propose two adaptive routing algorithms based on reinforcement learning. In the first algorithm, we have used a neural network to approximate the reinforcement signal, allowing the learner to take into account various parameters such as local queue size, for distance estimation. Moreover, each router uses an online learning module to optimize the path in terms of average packet delivery time, by taking into account the waiting queue states of neighbouring routers. In the second algorithm, the exploration of paths is limited to N‐best non‐loop paths in terms of hops number (number of routers in a path), leading to a substantial reduction of convergence time. The performances of the proposed algorithms are evaluated experimentally with OPNET simulator for different levels of traffic's load and compared with standard shortest‐path and Q‐routing algorithms. Our approach proves superior to classical algorithms and is able to route efficiently even when the network load varies in an irregular manner. We also tested our approach on a large network topology to proof its scalability and adaptability. Copyright © 2006 John Wiley & Sons, Ltd.     

Achieving Sub-50 Milliseconds Recovery Upon BGP Peering Link Failures

Recent measurements show that BGP peering links can fail as frequently as intradomain links and usually for short periods of time. We propose a new fast-reroute technique where routers are prepared to react quickly to interdomain link failures. For each of its interdomain links, a router precomputes a protection tunnel, i.e., an IP tunnel to an alternate nexthop which can reach the same destinations as via the protected link. We propose a BGP- based auto-discovery technique that allows each router to learn the candidate protection tunnels for its links. Each router selects the best protection tunnels for its links and when it detects an interdomain link failure, it immediately encapsulates the packets to send them through the protection tunnel. Our solution is applicable for the links between large transit ISPs and also for the links between multi-homed stub networks and their providers. Furthermore, we show that transient forwarding loops (and thus the corresponding packet losses) can be avoided during the routing convergence that follows the deactivation of a protection tunnel in BGP/MPLS VPNs and in IP networks using encapsulation.     

A routing architecture for mobile integrated services networks

A drawback of the conventional Internet routing architecture is that its route computation and packet forwarding mechanisms are poorly integrated with congestion control mechanisms. Any datagram offered to the network is accepted; routers forward packets on a best-effort basis and react to congestion only after the network resources have already been wasted. A number of proposals improve on this to support multimedia applications; a promising example is the Integrated Services Packet Network (ISPN) architecture. However, these proposals are oriented to networks with fairly static topologies and rely on the same conventional Internet routing protocols to operate. This paper presents a routing architecture for mobile integrated services networks in which network nodes (routers) can move constantly while providing end-to-end performance guarantees. In the proposed connectionless routing architecture, packets are individually routed towards their destinations on a hop by hop basis. A packet intended for a given destination is allowed to enter the network if and only if there is at least one path of routers with enough resources to ensure its delivery within a finite time. Once a packet is accepted into the network, it is delivered to its destination, unless resource failures prevent it. Each router reserves resources for each active destination, rather than for each source–destination session, and forwards a received packet along one of multiple loop-free paths towards the destination. The resources and available paths for each destination are updated to adapt to congestion and topology changes. This mechanism could be extended to aggregate dissimilar flows as well. This revised version was published online in June 2006 with corrections to the Cover Date.     

All-optical tree-based greedy router using optical logic gates and optical flip-flops

Due to ever-increasing throughput demands, the lookup in conventional IP routers based on longest prefix matching is becoming a bottleneck. Additionally, the scalability of current routing protocols is limited by the size of the routing tables. Geometric greedy routing is an alternative to IP routing which replaces longest prefix matching with a simple calculation employing only local information for packet forwarding. For the first time, in this paper we propose a novel and truly all-optical geometric greedy router based on optical logic gates and optical flip-flops. The circuit of the router is constructed through the interconnection of SOAs and directional couplers. The successful functionality of the proposed router is verified through simulation. The circuit enables high data rate throughput.     

The Application of NPs in WCDMA Systems

Recent efforts to add new services to the wide-band code division multiple accesses （WCDMA） system have increased interest in network processor （NP）-based routers that are easy to extend and evolve. In this paper, an application of NPs in routing engine module （REM） of radio network controller （RNC） in WCDMA system is proposed. The measuring results show that NPs have good performance and efficiency in routing traffic of the communication network and the simulation verifies the fast forwarding function of NPs.     

Novel hardware architecture for fast address lookups

For every packet an IP router receives, it makes a routing decision based on the packet's destination address. The router's forwarding rate is usually limited by the rate at which it can make these decisions. We describe a new method for implementing route lookups in hardware. Our method can be implemented in the forwarding engine of a network processor or router using a small on-chip SRAM and an off-chip DRAM, and it achieves a rate of one lookup per DRAM random access time. We present our method and discuss an implementation that uses a DRAM with 64 ns random access time to give over 15 million lookups per second. Our tests show that the method performs well for realistic routing tables while using only modest amounts of memory.