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.     

基于拓扑感知的虚网映射算法框架（英文）

The virtual network embedding/mapping problem is an important issue in network virtualization in Software-Defined Networking(SDN).It is mainly concerned with mapping virtual network requests,which could be a set of SDN flows,onto a shared substrate network automatically and efficiently.Previous researches mainly focus on developing heuristic algorithms for general topology virtual network.In practice however,the virtual network is usually generated with specific topology for specific purpose.Thus,it is a challenge to optimize the heuristic algorithms with these topology information.In order to deal with this problem,we propose a topology-cognitive algorithm framework,which is composed of a guiding principle for topology algorithm developing and a compound algorithm.The compound algorithm is composed of several subalgorithms,which are optimized for specific topologies.We develop star,tree,and ring topology algorithms as examples,other subalgorithms can be easily achieved following the same framework.The simulation results show that the topology-cognitive algorithm framework is effective in developing new topology algorithms,and the developed compound algorithm greatly enhances the performance of the Revenue/Cost(R/C) ratio and the Runtime than traditional heuristic algorithms for multi-topology virtual network embedding problem.     

A ring-based multicast routing topology with QoS support in wireless mesh networks

Wireless mesh networking (WMN) is an emerging technology for future broadband wireless access. The proliferation of the mobile computing devices that are equipped with cameras and ad hoc communication mode creates the possibility of exchanging real-time data between mobile users in wireless mesh networks. In this paper, we argue for a ring-based multicast routing topology with support from infrastructure nodes for group communications in WMNs. We study the performance of multicast communication over a ring routing topology when 802.11 with RTS/CTS scheme is used at the MAC layer to enable reliable multicast services in WMNs. We propose an algorithm to enhance the IP multicast routing on the ring topology. We show that when mesh routers on a ring topology support group communications by employing our proposed algorithms, a significant performance enhancement is realized. We analytically compute the end-to-end delay on a ring multicast routing topology. Our results show that the end-to-end delay is reduced about 33 %, and the capacity of multicast network (i.e., maximum group size that the ring can serve with QoS guarantees) is increased about 50 % as compared to conventional schemes. We also use our analytical results to develop heuristic algorithms for constructing an efficient ring-based multicast routing topology with QoS guarantees. The proposed algorithms take into account all possible traffic interference when constructing the multicast ring topology. Thus, the constructed ring topology provides QoS guarantees for the multicast traffic and minimizes the cost of group communications in WMNs.     

On the physical and logical topology design of large-scale optical networks

We consider the problem of designing a network of optical cross-connects (OXCs) to provide end-to-end lightpath services to large numbers of label switched routers (LSRs). We present a set of heuristic algorithms to address the combined problem of physical topology design (i.e., determine the number of OXCs required and the fiber links among them) and logical topology design (i.e., determine the routing and wavelength assignment for the lightpaths among the LSRs). Unlike previous studies which were limited to small topologies with a handful of nodes and a few tens of lightpaths, we have applied our algorithms to networks with hundreds or thousands of LSRs and with a number of lightpaths that is an order of magnitude larger than the number of LSRs. In order to characterize the performance of our algorithms, we have developed lower bounds which can be computed efficiently. We present numerical results for up to 1000 LSRs and for a wide range of system parameters such as the number of wavelengths per fiber, the number of transceivers per LSR, and the number of ports per OXC. The results indicate that it is possible to build large-scale optical networks with rich connectivity in a cost-effective manner, using relatively few but properly dimensioned OXCs.     

On inferring autonomous system relationships in the Internet

The Internet consists of rapidly increasing number of hosts interconnected by constantly evolving networks of links and routers. Interdomain routing in the Internet is coordinated by the Border Gateway Protocol (BGP). The BGP allows each autonomous system (AS) to choose its own administrative policy in selecting routes and propagating reachability information to others. These routing policies are constrained by the contractual commercial agreements between administrative domains. For example, an AS sets its policy so that it does not provide transit services between its providers. Such policies imply that AS relationships are an important aspect of the Internet structure. We propose an augmented AS graph representation that classifies AS relationships into customer-provider, peering, and sibling relationships. We classify the types of routes that can appear in BGP routing tables based on the relationships between the ASs in the path and present heuristic algorithms that infer AS relationships from BGP routing tables. The algorithms are tested on publicly available BGP routing tables. We verify our inference results with AT&T internal information on its relationship with neighboring ASs. As much as 99.1% of our inference results are confirmed by the AT&T internal information. We also verify our inferred sibling relationships with the information acquired from the WHOIS lookup service. More than half of our inferred sibling-to-sibling relationships are confirmed by the WHOIS lookup service. To the best of our knowledge, there has been no publicly available information about AS relationships and this is the first attempt in understanding and inferring AS relationships in the Internet. We show evidence that some routing table entries stem from router misconfigurations     

A heuristic algorithm for the point of presence design problem in IP networks

We propose a heuristic algorithm for the point of presence (POP) design problem in Internet protocol (IP) networks, where a POP is a node composed of several interconnected co-located routers. This problem consists of selecting the number of routers and their types, selecting the interface card types, connecting the access and the backbone links to the ports and selecting the link types between the co-located routers. A systematic set of experiments is designed to assess the performance of the proposed heuristic algorithm. The results show that quasioptimal solutions can be found with the proposed heuristic.     

Multicast topology inference from measured end-to-end loss

The use of multicast inference on end-to-end measurement has been proposed as a means to infer network internal characteristics such as packet link loss rate and delay. We propose three types of algorithm that use loss measurements to infer the underlying multicast topology: (i) a grouping estimator that exploits the monotonicity of loss rates with increasing path length; (ii) a maximum-likelihood estimator (MLE); and (iii) a Bayesian estimator. We establish their consistency, compare their complexity and accuracy, and analyze the modes of failure and their asymptotic probabilities     

Survivable deployment of cloud-integrated fiber-wireless networks against multi-fiber failure

Cloud-integrated fiber-wireless (FiWi) networks inheriting advantages of optical and wireless access networks have a broad prospect in the future. As various component failures may occur in cloud-integrated FiWi networks, survivability is becoming one of the key important issues. It is necessary to provide survivability strategies for cloud-integrated FiWi networks. Hence, this paper mainly focuses on the survivability of cloud-integrated FiWi networks against multiple fibers failure. Firstly, in this paper, a novel integer linear programming (ILP) solution is proposed to tolerate the failure of multiple distribution fibers with capacity and coverage constraints in the context of urban area. Then, considering the complexity of ILP models, an efficient heuristic scheme is proposed, in order to get the approximate solutions of ILP. Simulation results and analysis give the configurations of optical network units (ONUs) and wireless routers with different constraints and show the network coverage of clients for different number of ONUs and wireless routers with ILP solution and heuristic approach, respectively.     

New algorithm for hub-and-spoke topological virtual networks embedding problem

The virtual network embedding/mapping problem is a core issue of the network virtualization.It's mainly concerned with how to map virtual network requests to the substrate network efficiently.Previous ...     

Dynamic load balancing in WDM packet networks with and without wavelength constraints

We develop load balancing algorithms for WDM-based packet networks where the average traffic between nodes is dynamically changing. In WDM-based packet networks, routers are connected to each other using wavelengths (lightpaths) to form a logical network topology. The logical topology may be reconfigured by rearranging the lightpaths connecting the routers. Our algorithms reconfigure the logical topology to minimize the maximum link load. In this paper, we develop iterative reconfiguration algorithms for load balancing that track rapid changes in the traffic pattern. At each reconfiguration step, our algorithms make only a small change to the network topology hence minimizing the disruption to the network. We study the performance of our algorithms under several dynamic traffic scenarios and show that our algorithms perform near optimally. We further show that these large reconfiguration gains are achievable in systems with a limited number of wavelengths.     

An Algorithm for Traffic Grooming in WDM Optical Mesh Networks with Multiple Objectives

This paper studies a traffic grooming in wavelength-division multiplexing (WDM) mesh networks for the SONET/SDH streams requested between node pairs. The traffic could be groomed at the access node before converting to an optical signal carried in the all-optical network. We design a virtual topology with a given physical topology to satisfy multiple objectives and constraints. The grooming problem of a static demand is considered as an optimization problem. The traditional algorithms found in the literatures mostly focus on a single objective either to maximize the performance or to minimize the cost. We propose a multi-objective evolutionary algorithm to solve a grooming problem that optimizes multiple objectives all together at the same time. In this paper we consider the optimization of three objectives: maximize the traffic throughput, minimize the number of transceivers, and minimize the average propagation delay or average hop counts. The simulation results show that our approach is superior to an existing heuristic approaches in an acceptable running time.     

On the stability of paths, Steiner trees and connected dominating sets in mobile ad hoc networks

We propose algorithms that use the complete knowledge of future topology changes to set up benchmarks for the minimum number of times a communication structure (like paths, trees, connected dominating sets, etc.) should change in the presence of a dynamically changing topology. We first present an efficient algorithm called OptPathTrans that operates on a simple greedy principle: whenever a new source–destination (s–d) path is required at time instant t, choose the longest-living s–d path from time t. The above strategy when repeated over the duration of the s–d session yields a sequence of long-lived stable paths such that number of path transitions is the global minimum. We then propose algorithms to determine the sequence of stable Steiner trees and the sequence of stable connected dominating sets to illustrate that the principle behind OptPathTrans is very general and can be used to find the stable sequence of any communication structure as long as there is a heuristic or algorithm to determine that particular communication structure in a given network graph. We study the performance of the three algorithms in the presence of complete knowledge of future topology changes as well as using models that predict the future locations of nodes. Performance results indicate that the stability of the communication structures could be considerably improved by making use of the knowledge about locations of nodes in the near future.     

Design Method of Logical Topologies with Quality of Reliability in WDM Networks

As the bandwidth capacity of WDM networks continues to grow rapidly,traffic loss caused by a failure of network components is becoming unacceptable. To prevent such traffic loss and thus enhance network reliability, a protection method that prepares backup lightpaths for each working path is now being developed. In this paper, we first introduce the concept of QoR (quality of reliability), which is a realization of QoS with respect to the reliability needed in a WDM network. We define QoR in terms of the recovery time from when a failure occurs to when traffic on the affected primary lightpath is switched to the backup lightpath. After that, we propose a heuristic algorithm that can be used to design a logical topology that satisfies the QoR requirement for every node pair. The objective is to minimize the number of wavelengths needed for a fiber in the logical topology to carry the traffic with the required QoR. We compare this algorithm with two existing algorithms and show that it enables more effective use of wavelength resources; with the proposed algorithm, up to 25% fewer wavelengths are needed than with the other algorithms.     

Multicast with network coding in application-layer overlay networks

All of the advantages of application-layer overlay networks arise from two fundamental properties: 1) the network nodes in an overlay network, as opposed to lower-layer network elements such as routers and switches, are end systems and have capabilities far beyond basic operations of storing and forwarding; 2) the overlay topology, residing above a densely connected Internet protocol-layer wide-area network, can be constructed and manipulated to suit one's purposes. We seek to improve end-to-end throughput significantly in application-layer multicast by taking full advantage of these unique characteristics. This objective is achieved with two novel insights. First, we depart from the conventional view that overlay nodes can only replicate and forward data. Rather, as end systems, these overlay nodes also have the full capability of encoding and decoding data at the message level using efficient linear codes. Second, we depart from traditional wisdom that the multicast topology from source to receivers needs to be a tree, and propose a novel and distributed algorithm to construct a two-redundant multicast graph (a directed acyclic graph) as the multicast topology, on which network coding is applied. We design our algorithm such that the costs of link stress and stretch are explicitly considered as constraints and minimized. We extensively evaluate our algorithm by provable analytical and experimental results, which show that the introduction of two-redundant multicast graph and network coding may indeed bring significant benefits, essentially doubling the end-to-end throughput in most cases.     

Multipath routing with topology aggregation for scalable inter-domain service provisioning in optical networks

In this paper, we propose to use static virtual topology for a scalable inter-domain optical service provisioning, while addressing the resource efficiency issue by using multipath routing. To this end, we discuss methods for virtual topology aggregation with consideration of inter-domain routing, and propose two heuristic algorithms for two representative applications, referred to as real-time streaming and bulk data transfer. We consider specific requirements of each application, including transmission deadline and jitter, and evaluate the impact of differential delay issue of multipath routing on the performance of proposed algorithms. Numerical results show that the proposed multipath routing algorithms yield a low blocking ratio of inter-domain connections even on the static virtual topology, which is known for poor blocking performance otherwise. The resulting differential delay is sufficiently small for the studied applications, and can be compensated with relatively small buffers. We show that a scalable inter-domain service provisioning in optical networks can be achieved by using a combination of static virtual topology and multipath routing.     

Enhancing Multiple Routing Configurations through systematic analysis of topological characteristics

Previous studies show that topological characteristics in IP networks significantly influence the performance of networking algorithms, which therefore should be systematically analyzed using diverse topologies prior to their deployments. In this paper, we present an elaborate topological dependency analysis of a multi‐topology routing‐based IP fast re‐route technology, namely, Multiple Routing Configurations (MRC), using a large topology pool with diverse properties. Through an extensive analysis using our automated topological analysis tool, we discover a significant correlation between the performance of MRC and topological characteristics. MRC needs to construct a higher number of virtual topologies to provide full alternate path coverage if a network topology tends to have more hub nodes, whose degree is much higher than the rest of the network. Inspired by our topological analysis results, we propose a new heuristic algorithm enhancing MRC. Numerical experiments demonstrate that our heuristic significantly improves the performance of MRC confirming the effectiveness of the systematic analysis of topological characteristics. Copyright © 2016 John Wiley & Sons, Ltd.     

Design of wavelength-routed optical networks for packet switchedtraffic

We consider the problem of designing a logical optical network topology for a given physical topology (or fiber layout) and a given traffic demand matrix between the end-users. Traffic between the end-users is carried in a packet-switched form and the objective of our logical topology design is to minimize the maximum congestion on the logical connections in the logical topology. The logical connections are realized by wavelength continuous paths or lightpaths between end-users and they are routed via wavelength-selective routers. Note that a topology with lower maximum link congestion will allow its traffic demand matrix to be scaled up by a larger factor. In the logical topology each node is equipped with a limited number of optical transceivers, hence logical connections cannot be set up between every pair of nodes. In this paper we present an improved lower bound for maximum congestion on any link In the logical topology. The bound is shown to be up to 50% higher than the existing ones. An analytical model for obtaining the maximum and average logical connection loads for a given logical network and traffic demand matrix is also formulated, and it has been confirmed via simulation. Finally, two heuristic algorithms for constructing a logical topology that reduces maximum logical connection congestion are presented     

An efficient QoS routing algorithm for solving MCP in ad hoc networks

Providing guaranteed quality of service (QoS) in wireless networks is a key issue for deploying multimedia applications. To support such a QoS, an arduous problem concerning how to find a feasible end to end path to satisfy multiple QoS constraints should be studied. In general, multi-constrained path selection, with or without optimization, is an NP-complete problem that cannot be exactly solved in polynomial time. Approximation algorithms and heuristics with polynomial and pseudo-polynomial time complexities are often used to deal with this problem. However, existing solutions suffer either from excessive computational complexities that cannot be used for multimedia applications in ad hoc networks characterized by mobility and performance constraints (e.g., limited energy, wireless medium, etc.). Recently a promising heuristic algorithm H_MCOP using a non linear Lagrange relaxation path functions has demonstrated an improvement in its success rate and in finding feasible paths. However, the H_MCOP is not suitable for ad hoc networks and has not exploited the full capability that a Lagrange relaxation could offer. In this paper, we propose an efficient multi-constrained path heuristic called E_MCP, which exploits efficiently the Lagrange relaxation and enhances the path search process to be adequate to mobile ad hoc networks. Using extensive simulations on random mobile network with correlated and uncorrelated link weights, we show that the same level of computational complexity, E_MCP can achieve a higher success ratio of finding feasible paths.     

Resource allocation in underlay cognitive radio networks with full‐duplex cognitive base station

This paper considers an underlay cognitive radio network with a full‐duplex cognitive base station and sets of half‐duplex downlink and uplink secondary users, sharing multiple channels with the primary user. The resource allocation problem to maximize the sum rate of all the secondary users is investigated subject to the transmit power constraints and the interference power constraint. The optimization problem is highly nonconvex, and we jointly use the dual optimization method and the successive convex approximation method to derive resource allocation algorithms to solve the problem. Extensive simulations are shown to verify the performance of the resource allocation algorithms. It is shown that the proposed algorithms achieve much higher sum rate than that of the optimal half‐duplex algorithms and the reference full‐duplex algorithms.     

An algorithm for optimal assignment of a wavelength in a tree topology and its application in WDM networks

In this paper, we present a polynomial time algorithm that gives an optimal solution to the routing and wavelength assignment (RWA) problem in a tree topology. One of the major design issues in wavelength-division multiplexed networks is the assignment of the limited number of wavelengths among network stations so that greater capacity can be achieved. The problem of RWA is known to be NP-hard problem. Many researchers have tackled the problem of RWA with a number of efficient heuristic algorithms. This paper presents an algorithm that optimally assigns a single wavelength to maximize one-hop traffic in a tree topology. The algorithm uses dynamic programming and is shown to be optimal with a time complexity of O(N/sup 4/). We also propose a heuristic scheme to use our optimal algorithm for wavelength assignment in a general graph. The heuristic works on the tree subgraphs of a given graph and the remaining spare wavelengths can be assigned with an existing RWA policy.