Link State Routing Based on Compressed Sensing

In table routing protocols such as link state routing, every node in the network periodically broadcasts its link state and the state of its neighbors. These routing updates result in the transmission of a large number of packets. Some of these packets contain correlated or even redundant data which could be compressed if there is central management in the network. However, in autonomous networks, each node acts as a router, in which case central coordination is not possible. In this paper, compressed sensing is used to reduce routing traffic overhead. This can be done at nodes which have greater processing capabilities and no power consumption limitations such as backbone nodes in wireless mesh networks. A method is proposed to select a subset of nodes and thus a subset of links to probe their state. The sensed states are encoded to generate a low dimension sampled vector. This compressed link state vector is broadcast to the entire network. Nodes can then reconstruct link states from this vector using side information. Performance results are presented which demonstrate accurate anomaly detection while adapting to topology changes. Further, it is shown that a proper choice of weighting coefficients in the sampling process can improve detection performance.     

On-demand loop-free routing with link vectors

We present the on-demand link vector (OLIVE) protocol, a routing protocol for ad hoc networks based on link-state information that is free of routing loops and supports destination-based packet forwarding. Routers exchange routing information reactively for each destination in the form of complete paths, and each node creates a labeled source graph based on the paths advertised by its neighbors. A node originates a broadcast route request (RREQ) to obtain a route for a destination for which a complete path does not exist in its source graph. When the original path breaks, a node can select an alternative path based on information reported by neighbors, and a node can send a unicast RREQ to verify that the route is still active. A node that cannot find any alternate path to a destination sends route errors reliably to those neighbors that were using it as next hop to the destination. Using simulation experiments in ns2, OLIVE is shown to outperform dynamic source routing, ad hoc on-demand distance vector, optimized link-state routing protocol, and topology broadcast based on reverse-path forwarding, in terms of control overhead, throughput, and average network delay, while maintaining loop-free routing with no need for source routes.     

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.     

A novel method of link-state update in wavelength-routed networks

Link-state update is a critical component of the routing protocol in wavelength-routed networks. High-frequency updates impose heavy traffic on network control channels as well as excessive burden of electronic processing, while stale link-state information seriously degrades network performance. Therefore, a tradeoff has to be made between control overhead and network blocking probability. This paper proposes a novel link-state update method. By actively regulating the link-state update rate, the proposed method efficiently handles the inherent burstiness of link-state changes without overloading control network with excessive update messages. To improve the blocking performance under limited control bandwidth, it assigns different types of updates with different priorities such that the stale link-state information of more negative impact has a higher chance to be removed. Comprehensive performance evaluations show that the method successfully enforces the control bandwidth quota while achieving much lower blocking probability than existing link-state update methods.     

Routing bandwidth guaranteed paths with local restoration in label switched networks

The emerging multiprotocol label switching (MPLS) networks enable network service providers to route bandwidth guaranteed paths between customer sites. This basic label switched path (LSP) routing is often enhanced using restoration routing which sets up alternate LSPs to guarantee uninterrupted connectivity in case network links or nodes along primary path fail. We address the problem of distributed routing of restoration paths, which can be defined as follows: given a request for a bandwidth guaranteed LSP between two nodes, find a primary LSP, and a set of backup LSPs that protect the links along the primary LSP. A routing algorithm that computes these paths must optimize the restoration latency and the amount of bandwidth used. We introduce the concept of "backtracking" to bound the restoration latency. We consider three different cases characterized by a parameter called backtracking distance D: 1) no backtracking (D=0); 2) limited backtracking (D=k); and 3) unlimited backtracking (D=/spl infin/). We use a link cost model that captures bandwidth sharing among links using various types of aggregate link-state information. We first show that joint optimization of primary and backup paths is NP-hard in all cases. We then consider algorithms that compute primary and backup paths in two separate steps. Using link cost metrics that capture bandwidth sharing, we devise heuristics for each case. Our simulation study shows that these algorithms offer a way to tradeoff bandwidth to meet a range of restoration latency requirements.     

EA-HD: a novel link state update mechanism for ASON

When a connection request comes in a mesh optical network, the routers automatically choose the suitable routing paths and wavelength to it according to the network topology and link-state information saved in its global link-state database. Because some of these wavelengths may be released or occupied at any time, the global state database is always out of date and need update by some update policy. A suitable link-state update policy is critical, since a high-frequency update policy imposes heavy burden on the network, while a low-frequency update would increase the inaccurate of the global link-state database. In this paper, we propose a link-state update policy, named the EA-HD policy, which considers two index of a link, one is the Hamming distance between the local link-state database and the global link-state database, and the other is the used ratio of its wavelengths. The proposed update policy gets a trade-off between the accurate of link-state information and its update cost. Simulation results prove that our scheme achieves a good performance in traffic blocking probability while maintaining moderate volume of update traffic.     

A Framework for Evaluating the Performance of Cluster Algorithms for Hierarchical Networks

Table-driven routing algorithms in flat networks have the scalability problem due to the need for global topology updates. To reduce update cost, networks are hierarchically organized. Clustering algorithms organize flat networks into hierarchical networks. One important problem, which has not been adequately addressed so far, is to evaluate how good a clustering algorithm is. In other words, it is useful to know what the desired properties of hierarchical networks are. In this paper, we address this issue by considering the routing update cost, which can be measured by the total routing table size and the variance of cluster size distribution. We provide a set of desired properties of clustering algorithms. Applying these properties to the cluster structure generated by an algorithm, we can determine how good a clustering algorithm is. Specifically, we discuss how to choose appropriate number of hierarchy levels, number of clusters, and cluster size distribution, such that the topology update cost is minimized. The desired properties obtained from the analysis can be used as guidelines in the design of clustering algorithms for table-driven hierarchical networks. We apply the idea developed in this paper to evaluate three routing algorithms, namely the lowest ID algorithm, the maximum degree algorithm, and the variable degree clustering algorithm. We show how the variable degree clustering algorithm, which takes into account these desired properties, improves routing performance.     

GPSPA: a new adaptive algorithm for maintaining shortest path routing trees in stochastic networks

This paper presents a new efficient solution to the Dynamic Shortest Path Routing Problem, using the principles of Generalized Pursuit Learning. It proposes an efficient algorithm for maintaining shortest path routing trees in networks that undergo stochastic updates in their structure. It involves finding the shortest path in a stochastic network, where there are continuous probabilistically based updates in link‐costs. In vast, rapidly changing telecommunications (wired or wireless) networks, where links go up and down continuously and rapidly, and where there are simultaneous random updates in link costs, the existing algorithms are inefficient. In such cases, shortest paths need to be computed within a very short time (often in the order of microseconds) by scanning and processing the minimal number of nodes and links. The proposed algorithm, referred to as the Generalized Pursuit Shortest Path Algorithm (GPSPA), will be very useful in this regard, because after convergence, it seems to be the best algorithm to‐date for this purpose. Indeed, it has the advantage that it can be used to find the shortest path within the ‘statistical’ average network, which converges irrespective of whether there are new changes in link‐costs or not. Existing algorithms are not characterized by such a behaviour inasmuch as they would recalculate the affected shortest paths after each link‐cost update. The algorithm has been rigorously evaluated experimentally, and it has been found to be a few orders of magnitude superior to the algorithms available in the literature. Copyright © 2004 John Wiley & Sons, Ltd.     

Centralized and Distributed Algorithms for Routing and Weighted Max-Min Fair Bandwidth Allocation

Given a set of demands between pairs of nodes, we examine the traffic engineering problem of flow routing and fair bandwidth allocation where flows can be split to multiple paths (e.g., MPLS tunnels). This paper presents an algorithm for finding an optimal and global per-commodity max-min fair rate vector in a polynomial number of steps. In addition, we present a fast and novel distributed algorithm where each source router can find the routing and the fair rate allocation for its commodities while keeping the locally optimal max-min fair allocation criteria. The distributed algorithm is a fully polynomial epsilon-approximation (FPTAS) algorithm and is based on a primal-dual alternation technique. We implemented these algorithms to demonstrate its correctness, efficiency, and accuracy.      

Avoiding Counting to Infinity in Distance Vector Routing

The Routing Information Protocol (RIP) may introduce misleading routing information into the routing table, due to network topology changes such as link or router failures. This is known as the counting to infinity problem. In the past, the distance metric had to be below 16 hops in order to keep this counting within reasonable limits. In this paper a more elaborate approach is presented in order to recognize those router interfaces which might have received misleading routing messages. This is accomplished by evaluating routing updates more carefully than is done by the well known split horizon approach. This new approach gets by without any additional message exchange between the RIP-protocol partners. In contrast to other approaches, the router interfaces are examined in pairs to determine if a loop exists between them. The algorithm locally extracts all the information it needs from the normal update messages that are exchanged between RIP neighbors and is thus executed in constant time. Only some minor calculations have to be carried out to gain the knowledge that is necessary to recognize those interfaces which may have received misleading routing information. Hence, this new distance vector routing without counting to infinity can be used in complex networking environments.     

A Bandwidth Guaranteed Integrated Routing Algorithm in IP over WDM Optical Networks

In this paper, we have developed an integrated online algorithm for dynamic routing of bandwidth guaranteed label switched paths (LSPs) in IP-over-WDM optical networks. Traditionally, routing at an upper layer (e.g., IP layer) is independent of wavelength routing at the optical layer. Wavelength routing at the optical layer sets up a quasi-static logical topology which is then used at the IP layer for IP routing. The coarse-grain wavelength channels and the pre-determined virtual topologies with respect to some a priori assumed traffic distribution are barriers to efficient resource use and inflexible to changing traffic. We take into account the combined knowledge of resource and topology information at both IP and optical layers. With this added knowledge, an integrated routing approach may extract better network efficiencies, be more robust to changing traffic patterns at the IP layer than schemes that either use dynamic routing information at the IP layer or use a static wavelength topology only. LSP set-up requests are represented in terms of a pair of ingress and egress routers as well as its bandwidth requirement, and arrive one-by-one. There is no a priori knowledge regarding the arrivals and characteristics of future LSP set-up requests. Our proposed algorithm considers not only the importance of critical links, but also their relative importance to routing potential future LSP set-up requests by characterizing their normalized bandwidth contribution to routing future LSP requests with bandwidth requirements. Moreover, link residual bandwidth information that captures the link's capability of routing future LSPs is also incorporated into route calculation. Extensive simulation was conducted to study the performance of our proposed algorithm and to compare it with some existing ones, such as the integrated minimum hop routing algorithm and the maximum open capacity routing algorithm. Simulation results show that our proposed algorithm performs better than both routing algorithms in terms of the number of LSP set-up requests rejected and the total available bandwidth between router pairs.     

Practical Routing in Delay-Tolerant Networks

Delay-tolerant networks (DTNs) have the potential to interconnect devices in regions that current networking technology cannot reach. To realize the DTN vision, routes must be found over multiple unreliable, intermittently-connected hops. In this paper we present a practical routing protocol that uses only observed information about the network. We designed a metric that estimates the average waiting time for each potential next hop. This learned topology information is distributed using a link-state routing protocol, where the link-state packets are "flooded" using epidemic routing. The routing is recomputed each time connections are established, allowing messages to take advantage of unpredictable contacts. A message is forwarded if the topology suggests that the connected node is "closer" to the destination than the current node. We demonstrate through simulation that our protocol provides performance similar to that of schemes that have global knowledge of the network topology, yet without requiring that knowledge. Further, it requires significantly less resources than the alternative, epidemic routing, suggesting that our approach scales better with the number of messages in the network. This performance is achieved with minimal protocol overhead for networks of approximately 100 nodes.     

A path-finding algorithm for loop-free routing

A loop-free path-finding algorithm (LPA) is presented; this is the first routing algorithm that eliminates the formation of temporary routing loops without the need for internodal synchronization spanning multiple hops of the specification of complete or variable-size path information. Like other previous algorithms, the LPA operates by specifying the second-to-last hop and distance to each destination; this feature is used to ensure termination. In addition, the LPA uses an interneighbor synchronization mechanism to eliminate temporary routing loops. A detailed proof of the LPAs correctness and loop-freedom property is presented and its complexity is evaluated. The LPAs average performance is compared by simulation with the performance of algorithms representative of the state of the art in distributed routing, namely an ideal link-state (ILS) algorithm, a loop-free algorithm that is based on internodal coordination spanning multiple hops (DUAL) and a path-finding algorithm without the interneighbor synchronization mechanism. The simulation results show that the LPA is a more scalable alternative than DUAL and ILS in terms of the average number of steps, messages, and operations needed for each algorithm to converge after a topology change     

Multipath routing in the presence of frequent topological changes

In this article we propose a framework for multipath routing in mobile ad hoc networks and provide its analytical evaluation. The instability of the topology (e.g., failure of links) in these types of networks, due to nodal mobility and changes in wireless propagation conditions, makes transmission of time-sensitive information a challenging problem. To combat this inherent unreliability of these networks, we propose a routing scheme that uses multiple paths simultaneously by splitting the information among the multitude of paths, to increase the probability that the essential portion of the information is received at the destination without incurring excessive delay. Our scheme works by adding some overhead to each packet, which is calculated as a linear function of the original packet bits. The resulting packet (information and overhead) is fragmented into smaller blocks and distributed over the available paths. Our goal is, given the failure probabilities of the paths, to find the optimal way to fragment and then distribute the blocks to the paths so that the probability of reconstructing the original information at the destination is maximized. Our algorithm has low time complexity, which is crucial since the path failure characteristics vary with time and the optimal block distribution has to be recalculated in real time     

Incremental survivable network design against node failure in SDH/SONET mesh networks

Network survivability is becoming more and more important for the plenty of information each single fiber carries. Extra network resources are needed to increase network survivability level. In this paper, we investigate the problem of how to augment the network topology with adding new links and allocate spare capacity to maximize the service restorability against node failures in SDH/SONET mesh networks. A scheme called maximal node-disjoint backup paths provisioning with topology augmentation is proposed to tackle the problem, and another scheme called globally optimized path provisioning with topology augmentation, which allows adjusting the existing working paths of network flows, is investigated to optimize the augmented network globally. Both schemes are formulated as mixed integer linear programming models. Furthermore, heuristic algorithms are investigated to be implemented in software. Three algorithms, i.e., added links searching method, successive maximal survivable routing method, and random sequence routing convergence method, are designed and compared. Simulation results show the effectiveness of the algorithms.     

A distributed routing algorithm for multihop packet radio networkswith uni- and bi-directional links

Multihop packet radio networks require routing algorithms which are distributed in nature and which have the ability to timely detect changes in the network topology. These changes are mostly changes in connectivity caused by link or node failures and by the relative motion of the nodes. This paper describes and analyzes an adaptive decentralized routing algorithm for packet radio networks. The network connectivity, as perceived by each node, is translated into a graph representation of the network. The proposed routing mechanism then uses a breadth-first search algorithm along the inbound links of such a graph. Unlike most of the algorithms found in the open literature the one proposed here can be used in networks having both uni- and bi-directional radio links. Examples are shown to illustrate the methodology     

CEDAR: a core-extraction distributed ad hoc routing algorithm

We present CEDAR, a core-extraction distributed ad hoc routing algorithm for quality-of-service (QoS) routing in ad hoc network environments, CEDAR has three key components: (a) the establishment and maintenance of a self-organizing routing infrastructure called the core for performing route computations; (b) the propagation of the link-state of high bandwidth and stable links in the core through increase/decrease waves; and (c) a QoS-route computation algorithm that is executed at the core nodes using only locally available state. The performance evaluations show that CEDAR is a robust and adaptive QoS routing algorithm that reacts quickly and effectively to the dynamics of the network while still approximating the performance of link-state routing for stable networks     

基于K最优路径的QoS路由预计算新算法

针对下一代高速网络中的多约束服务质量路由问题,首先提出了一种精确链路状态信息条件下的路由预计算算法MKPPA.在此基础上根据网络状态信息的动态性,通过引入"警戒点"对MKPPA进行了改进,提出了一种基于警戒点的修正预计算算法M_-MKPPA,该算法能够适应网络链路信息的不精确性.最后通过理论分析表明MKPPA不仅能够解决加性度量参数受约束的QoS路由问题,而且能够解决加性与非加性度量参数混合受约束QoS路由问题,修正预计算算法M -MKPPA能够适应网络链路状态信息的动态特性.计算机仿真结果显示出MKPPA在求解QoS路由问题时,当计算次数不超过已有算法的计算次数时,不论是精确链路状态信息还是非精确链路状态信息条件下,均具有更高的路由计算成功率.     

Dynamic lightpath provisioning in optical WDM mesh networks with asymmetric nodes

The wavelength selective switch-based reconfigurable optical add/drop multiplexers is a promising switching equipment for future reconfigurable wavelength-division multiplexing (WDM) mesh networks. However, its asymmetric switching property complicates the optimal routing and wavelength assignment problem. In an asymmetric switching scenario, using the classic Dijkstra’s algorithm can lead to invalid paths traversing unconnected ports of an asymmetric node. To solve this problem, we propose both link-state (LS) and distance vector (DV) schemes for dynamic lightpath provisioning in optical WDM mesh networks with asymmetric nodes. The proposed LS schemes include the asymmetric switching-aware (ASA) Dijkstra’s algorithm, the $K$ -shortest path-based algorithm, and the entire path searching (EPS) algorithm. Simulation results show that the ASA-Dijkstra’s algorithm will bring notable improvement of the blocking performance with low computational complexity, while the EPS algorithm has much higher complexity and is not suitable to be employed in large-scale networks. On the other hand, our proposed DV solution, i.e., the information diffusion-based routing (IDBR), can achieve the lowest blocking probability with the lowest computational complexity. Moreover, IDBR does not require the distribution of local asymmetric switching information like the LS schemes, thus having a high level of topology confidentiality.     

Dynamic routing of restorable bandwidth-guaranteed tunnels using aggregated network resource usage information

The paper presents new algorithms for dynamic routing of restorable bandwidth-guaranteed paths. We assume that connections are requested one-by-one and there is no prior knowledge of future arrivals. In order to guarantee restorability an alternate link (node) disjoint backup (restoration) path has to be determined, as well as an active path, when the connection is initiated. This joint on-line routing problem is particularly important in optical networks and in MPLS networks for dynamic provisioning of bandwidth-guaranteed or wavelength paths. A simple solution is to find two disjoint paths, but this results in excessive resource usage. Backup path bandwidth usage can be reduced by judicious sharing of backup paths amongst certain active paths while still maintaining restorability. The best sharing performance is achieved if the routing of every path in progress in the network is known to the routing algorithm at the time of a new path setup. We give a new integer programming formulation for this problem. Complete path routing knowledge is a reasonable assumption for a centralized routing algorithm, but is not often desirable, particularly when distributed routing is preferred. We show that a suitably developed algorithm which uses only aggregated information, and not per-path information, is able to perform almost as well as one using complete information. Disseminating this aggregate information is feasible using proposed traffic engineering extensions to routing protocols. We formulate the dynamic restorable bandwidth routing problem in this aggregate information scenario and develop efficient routing algorithms. The performance of our algorithm is close to the complete information bound.