Preemption-Aware Instantaneous Request Call Routing for Networks With Book-Ahead Reservation

This paper presents a new preemption-aware quality of service (QoS) routing algorithm for instantaneous request (IR) call connections in a QoS-enabled network where resources are shared between IR and book-ahead (BA) call connections. BA reservation, which confirms the availability of resources in advance, is a highly attractive technique for time sensitive applications that require high amount of bandwidth with guaranteed QoS. One of the major concerns for the implementation of BA reservation is the need for preemption of on-going IR calls to accommodate BA calls when resource scarcity arises. Preemption disrupts service continuity of on-going calls which is considered as severely detrimental from users' perceived QoS definition found in recent studies. Existing QoS routing algorithms focus on resource conservation or load balancing as the key objective to attain in addition to guaranteed QoS. No works have yet focused on the preemption problem of on-going IR calls at routing stage in the presence of BA calls. We present a mathematical formulation to compute the preemption probability of an incoming IR call at routing stage based on the current IR and future BA load information. We propose a routing strategy by formulating a link cost function comprising of the calculated preemption probability of the incoming IR call and hop count. Simulation results confirm that QoS routing based on the proposed link cost function significantly outperforms widely recommended shortest path and widest path routing algorithms in terms of IR call preemption and blocking rate. The proposed approach also yields higher network utilization and IR effective throughput.     

光网络的快速恢复路径搜索算法

光传送网是电信网的基础，如何在网络发生故障后将受故障影响的业务快速恢复，是光网络面临的重要问题．本文在分析了经典Floyd算法和Dijsktra算法存在的问题的基础上，提出了一种备用路径和搜索算法相结合的恢复算法，且在搜索算法中提出了一种快速不完全遍历算法（FIE算法），该算法适合于网状网结构．当网络发生故障后，首先查找备用路径，在备用路径无法恢复的情况下，以一定的准则进行路径的搜索，并采用双向搜索的方式，从多方面大大缩短了恢复时间．     

异构无线网络中的Ad Hoc路由及QoS分析

首先分析了纯Ad Hoc网络环境下具有QoS保证的几种典型路由协议,然后阐述了异构无线网络的体系架构以及异构网络环境下的Ad Hoc路由,包括基于节点位置信息的路由分级路由、提高网络容量的多跳中继路由、实现网络负载均衡的路由,以及跨层路由协议。最后,总结了在异构网络环境下提出的基于Ad Hoc网络多跳中继路由的负载均衡策略的研究工作,分析了仿真结果。     

Analyzing the performance of deferred reservations

This paper studies the performance of deferred resource reservation in data networks. Conventional resource reservation protocols, such as PNNI and RSVP adopt an all-or-nothing approach, where partially acquired resources must be released if resources are not available at all links on the chosen path. During periods of high network load, this leads users to retry requests repeatedly, adding control traffic at exactly the time when the network’s capacity to process that control traffic is exhausted. Deferred REServation (DRES) can significantly improve performance by reducing the overall call rejection probability, allowing more traffic to be carried, using the same resources. Call admissibility is increased by deferring requests at routers for a limited period of time until resources become available. The paper includes analytical models that predict the blocking probability on a DRES multiplexor and on a multi-hop path, and simulation results for substantial network configurations, using several QoS routing methods. The results show that DRES can provide substantial performance gains over traditional reservations (upto 50% with QoS routing enabled and upto an order of magnitude for non-QoS traditional routing).     

多网关无线Mesh网络干扰与负载感知路由度量

提出一种应用于多网关无线Mesh网络中的路由度量。首先建立多网关网络模型,获取网络拓扑信息并依此为网络节点分配不同的权值;然后通过网络拓扑信息及无线链路的衰落特性,推导网络中链路信号与干扰噪声比SINR的分布特性,进而计算链路的中断概率和中断速率;最后获取Mesh路由器节点缓存包数量,并计算网关节点容量占比,针对客户端业务和Internet业务设计具有保序性的ILR(Interfere and Load aware Routing)路由度量,网络依据路由度量为客户端业务和Internet业务选路。ILR路由度量考虑了网络干扰因素和负载分布信息,能够有效降低网络干扰,达到网络负载均衡、提高网络吞吐量的目的。     

Multi-Service Dynamic QoS Routing Schemes with Call Admission Control: A Comparative Study

In this paper we consider wide-area backbone networks where multiple connection-oriented guaranteed services with differing bandwidth/flow requirements are offered. Specifically, we consider the case where each service requires a quality-of-service (QoS) peak rate bandwidth/flow allocation (different rate for different services) for the duration of the connection in a loss network environment. We present several dynamic routing schemes in such multi-service settings along with an admission control policy. The routing schemes cover issues such as crankback, periodicity of computation of routing, what type of information is to be used in routing decision, and whether to use centralized or decentralized computation. We present results for various measures, i.e., in addition to well-known call blocking performance, we also address and quantify measures such as signaling loads impact due to alternate routing, crankback impact, and revenue impact, and provide a comparative evaluation of various dynamic routing schemes in multi-service settings.     

Decision models for designing and planning private communication networks

We consider the recently developed reconfigurable digital data networks consisting of T1/T3 circuits and Digital Crossconnect Systems (DCSs). A DCS is a device to patch base channels electronically from one T1/T3 circuit to another with a negligible queuing delay at the connecting node. We present new decision models for the design and circuit leasing policies of such digital backbone networks. Our model takes advantage of the special capabilities of the DCS technology and is likely to result in remarkable economic gains for the private network users. The formulation and analyses presented here simultaneously address the following problems: physical link and capacity selection, logical network configuration and channel assignment, and traffic routing on the logical network. The problem formulation results in a large-scale non-linear mixed integer program, and we propose an efficient solution methodology employing Lagrangean relaxation and subgradient optimization. Several numerical results illustrate the utility of our approach for these complex problems. We show that the economies of scale built into the tariff structure of these digital networks can be successfully exploited, and that the inherent flexibility of DCSs leads to logical networks that are dramatically different from their underlying physical topologies.     

Fuzzy Logic-Based Multicast Routing in Multiradio Multichannel Wireless Mesh Networks

The availability of bandwidth in wireless mesh networks (WMNs) introduces it as a prominent choice for implementing bandwidth sensitive services. Multicast services such as teleconferencing, push-based systems, multiplayer games, etc., can be implemented in an efficient way in such networks. Moreover, the severe performance degradations that can result from the interference generated by concurrent data transmissions and environmental noises call for the development of interference-aware routing mechanisms. This paper investigates the impact of wireless interference on network performance for multicast transmission in WMNs. We show that by taking wireless interference into consideration in the design of routing mechanisms, better resource usage can be achieved. Hence, a fuzzy logic–based approach is proposed to choose optimal routes from source to the multicast group in multichannel case. Three fuzzy variables are considered in route selection phase, which are interference, available bandwidth, and hop count. Extensive simulations are conducted aiming at verifying the high performance of the proposed algorithm. Simulation results demonstrated that our proposed algorithm outperforms Link-Controlled Multi-Rate Multi-Channel (LC-MRMC) and Channel Assignment with Multiple Factor (CAMF) algorithms in terms of throughput, packet delivery ratio, and end-to-end delay.     

OPTIMIZATION OF SPARE CAPACITY IN WDM NETWORKS FOR REAL-TIME SERVICE RESTORATION

In the case of network malfunction a network with restoration capability requires spare capacity to be used. Optimization of the spare capacity in this case is to find the minimum amount of spare capacity for the network to survive from network component failures. In this paper, the optimization of the spare capacity problem is investigated for the wavelength division multiplexing (WDM) mesh networks without wavelength conversion. To minimize the spare capacity, we will optimize both the routing and the wavelength assignment. This combinatorial problem is usually called the routing and wavelength assignment (RWA) problem and it is well known to be NP-hard. We give an integer linear programming (ILP) formulation for the problem. Due to the excessive run-times of the ILP, we propose a hybrid genetic algorithm approach (GA) for the problem. For benchmarking purpose, simulated annealing (SA) and Tabu search (TS) are also applied to this problem. To validate the effectiveness of the proposed method, the approach is applied to the China network, which has a more complicated network topology. Simulation results are very favorable to the GA approach.     

Service discovery in mobile ad hoc networks: A field theoretic approach

Service discovery in mobile ad hoc networks is challenging because of the absence of any central intelligence in the network. Traditional solutions as used in the Internet are hence not well suited for mobile ad hoc networks. In this paper, we present a novel decentralized service discovery mechanism for ad hoc networks. The basic idea is to distribute information about available services to the network neighborhood. We achieve this by using the analogy of an electrostatic field: A service is modelled by a (positive) point charge, and service request packets are seen as (negative) test charges which are attracted by the service instances. In our approach, we map the physical model to a mobile ad hoc network in a way where each network element calculates a potential value and routes service requests towards the neighbor with the highest potential, hence towards a service instance. Our approach allows for differentiation of service instances based on their capacity. We define the required protocols and methods which we implemented in a network simulator. Using extensive simulations, we evaluate the performance and robustness of the mechanisms. The results indicate good performance and convergence even in highly mobile environments. We believe that this technique can and should be further exploited, e.g., as a routing protocol in mobile ad hoc networks.     

A new approach for delay-constrained routing

Delay-constrained routing protocols are used to find paths subject to a delay constraint while efficiently using network resources. Many of the delay-constrained routing protocols that have been proposed in the literature give priority to cost minimization during the path computing process. With this approach, paths with end-to-end delays too close to the delay constraint are obtained. We believe that such paths are prone to delay constraint violations during load variations in the network. The root of such violations can be found in the imprecision of delay information during the routing process. In this paper, we propose a new approach for delay-constrained routing which captures the tradeoff between cost minimization and the risk level regarding to the delay constraint. We propose a protocol called Parameterized Delay-Constrained Routing protocol that implements our approach using a simple and efficient parameterized selection function. We expand this work to multicasting by proposing three new delay-constrained multicast routing protocols based on the source (Naïve), destination (Greedy) and mixed multicast routing techniques. Our simulations show that our protocols produce paths and trees which are stable, less risky and suitable for various network conditions.     

A two-layer congestion control protocol for broadband ISDN

In this paper, we present a new, effective connection-oriented congestion control protocol for B-ISDN. The protocol employs the traffic viewpoint hierarchical design approach and is implemented by a two-layer scheme at the call and cell layers. The call layer handles call admission (denial) and provides shortest path connection routing when a call is admitted, while the cell layer allocates switch input buffer space for each traffic type according to each type's cell loss probability grade-of-service requirement. There is a direct interaction between the two layers in processing a connection request. A discrete-time queueing system with geometrically distributed service time and state-dependent Markov modulated Bernoulli process (MMBP) arrivals is established to model heterogeneous networking environments for this protocol and an analytical solution is developed for this queueing system. Numerical results obtained by both analysis and simulation show that the protocol can reduce network congestion as input traffic rates approach switch capacity and, thereby, increase network utilization relative to that possible in the absence of congestion control.     

Explanation of Performance Degradation in Turn Model

The Turn model routing algorithms for mesh interconnection network achieve partial adaptivity without any virtual channels. However, the routing performance measured by simulations is worse than with the simple deterministic routing algorithm. Authors have explained these results simply by uneven dynamic load through the network. However, this phenomenon has not been studied further. This paper investigates performance degradation with Turn model and drawbacks of partially adaptive routing in comparison with the deterministic routing, and it introduces some new concepts. Our simulations deal with individual channels and results are presented by 3D graphs, rather than by commonly used averages. An additional parameter—channel occupation, which is consistent with queuing theory commonly used in many proposed analytical models, is introduced. We also propose a new structure, the Channel Directions Dependency Graph (CDDG). It provides a new approach in analysis, helps in understanding of dynamic routing behaviour, and it can be generalized in other routing algorithms.     

QoS based multicast routing algorithms for real time applications

In recent years, there has been a lot of interest in providing real-time multimedia services like digital audio and video over packet-switched networks such as Internet and ATM. These services require certain quality of service (QoS) from the network. The routing algorithm should take QoS factor for an application into account while selecting the most suitable route for the application. In this paper, we introduce a new routing metric and use it with two different heuristics to compute the multicast tree for guaranteed QoS applications that need firm end-to-end delay bound. We then compare the performance of our algorithms with the other proposed QoS-based routing algorithms. Simulations were run over a number of random networks to measure the performance of different algorithms. We studied routing algorithms along with resource reservation and admission control to measure the call throughput over a number of random networks. Simulation results show that our algorithms give a much better performance in terms of call throughput over other proposed schemes.     

Survivable millimeter-wave mesh networks

Millimeter-wave mesh networks have the potential to provide cost-effective high-bandwidth solutions to many current bandwidth-constrained networks including cellular backhaul. However, the availability of such networks is severely limited due to their susceptibility to weather, such as precipitation and humidity. In this paper, we present a rigorous approach to survivable millimeter-wave mesh networks based on experimentation, modeling, and simulation. Individual link performance is characterised using frame error-rate measurements from millimeter-wave transmissions on test links over a period of one year. A geometric model based on radar-reflectivity data is used to characterise rain storms and determine their impact on spatially correlated links of a mesh network. To mitigate the impact of link impairments on network services, we present two cross-layered routing protocols to route around the failures: P-WARP (predictive weather-assisted routing protocol) and XL-OSPF (cross-layered open shortest-path first). We conduct a performance analysis of the proposed mesh network under the presence of actual weather events as recorded by the US National Weather Service. Results show that the proposed approach yields the highest dependability when compared against existing routing methods.     

Wavelength Conversion in All-Optical Networks with Shortest-Path Routing

We consider all-optical networks with shortest-path routing that use wavelength-division multiplexing and employ wavelength conversion at specific nodes in order to maximize their capacity usage. We present efficient algorithms for deciding whether a placement of wavelength converters allows the network to run at maximum capacity, and for finding an optimal wavelength assignment when such a placement of converters is known. Our algorithms apply to both undirected and directed networks. Furthermore, we show that the problem of designing such networks, i.e., finding an optimal placement of converters, is MAX SNP-hard in both the undirected and the directed case. Finally, we give a linear-time algorithm for finding an optimal placement of converters in undirected triangle-free networks, and show that the problem remains NP-hard in bidirected triangle-free planar networks.     

传输受限的大规模无线传感器网络路由算法

针对大规模无线传感器网络在其传输受限的应用环境下,提出一种基于精细化梯度层次场的有效路由算法（FGLRA）。该算法通过邻居节点集中低层次节点数来刻画节点在层次内的边界位置,实现精细化梯度层次场要求。在此基础上,描述了路由算法的总体框架,并对边界位置值确定、下一跳节点集选择、路由转发机制及数据回传4个关键部分进行了详细分析设计。最后,通过不同规模环境下的仿真模拟,并与融合树、位置辅助等路由算法进行了相关比较。结果表明,该路由算法能有效降低网络能耗、均匀网络负载、延长网络生命周期。     

Strategic parameter-driven routing models for multidestinationtraffic in telecommunication networks

We present mathematical models that determine the optimal parameters for strategically routing multidestination traffic in an end-to-end network setting. Multidestination traffic refers to a traffic type that can be routed to any one of a multiple number of destinations. A growing number of communication services is based on multidestination routing. In this parameter-driven approach, a multidestination call is routed to one of the candidate destination nodes in accordance with predetermined decision parameters associated with each candidate node. We present three different approaches: (1) a link utilization (LU) approach, (2) a network cost (NC) approach, and (3) a combined parametric (CP) approach. The LU approach provides the solution that would result in an optimally balanced link utilization, whereas the NC approach provides the least expensive way to route traffic to destinations. The CP approach, on the other hand, provides multiple solutions that help leverage link utilization and cost. The LU approach has in fact been implemented by a long distance carrier resulting in a considerable efficiency improvement in its international direct services, as summarized.