Packet-Switched Performance with Different Circuit-Switched Routing Procedures in Nonhierarchical Integrated Circuit-Switched and Packet-Switched Networks

It is shown in [13] that different types of routing procedures for circuit-switched traffic in a nonhierarchical network exhibit various performance tradeoffs. It is, however, not clear if the network is also allowed to carried packet-switched traffic, how the packet-switched traffic will be affected by using different routing procedures for the circuit-switched traffic. In this paper, we examine the average time delay of the packet-switched traffic assuming that the network uses a movable boundary scheme to allocate bandwidth dynamically     

Sequencial Routing Optimization for Circuit Switched Networks

Nonhierarchical alternate routing is the simplest extension to the hierarchical routing currently used in telephone networks. In order to evaluate the merits of such a technique, it is necessary to be able to optimize some performance measure over the routing variables. In a first step, a short discussion is presented of the evaluation algorithms used for computing the end-to-end blocking probabilities in networks operating under nonhierarchicai alternate routings. Then the results of a statistical sampling of the routing space for a small network are presented, to illustrate important characteristics of the routing problem. Next, two heuristic optimization techniques are discussed, one based on classical steepest descent and the other inspired from classical routing optimization of traffic flows in transportation and communication networks. Acceleration techniques are discussed in both cases, and the convergences rates of the alorgithms are presented for a number of networks. A brief discussion is finally given of the usefulness of nonhierarchical alternate routing in reducing the blocking probability in already existing networks, and in decreasing the number of trunks required to maintain a prespecified grade of service, both in real and artificially generated networks.     

Economic analysis of robust access network architecture in two-tierdata networks

Recent studies have addressed routing and performance issues of nonhierarchical and hierarchical backbone packet networks in a unified fashion, by adopting an end-to-end mean delay objective and including a variety of practical routing constraints. The authors build on this approach to include the design of robust access networks, and they analyze the economic and robustness-related tradeoffs of several access network architectures in two-tier data packet networks. Two-tier architectures consist of an access network that homes to a high-capacity backbone network through a variety of topological arrangements. The access tier provides protocol handling and traffic concentration. The backbone tier performs high-speed transport and alternate routing under congestion/failure conditions. They identify the fundamental access network parameters that allow them to develop network designs with optimized characteristics. The analysis demonstrates the cost effectiveness of access diversity as well as the enhanced robustness it can provide even though it requires higher switch functionality and cost     

Surveillance strategies for a class of adaptive-routing algorithmsin circuit-switched DNHR communications networks: a simulationstudy

A large, circuit-switched, communications network engineered for historical traffic patterns using dynamic nonhierarchical routing (DNHR) is considered. During overloads, the offered traffic many not follow the historical patterns. In such situations, it is possible to increase network throughput by augmenting the routing tables in near-realtime to utilize instantaneous spare capacity. The surveillance strategy determines how often network data is collected and how frequently additional paths are added to the routing tables. Six surveillance strategies for adaptive routing are examined: (1) 2.5-min surveillance interval; (2) 5-min surveillance interval; (3) 10-min surveillance interval; (4) 15-min surveillance interval; (5) modify the routing every other 5 min; and (6) modify the routing every 5 min with a fixed 10-min lag before the routing tables are changed. Simulation is used to compare the network performance to the baseline performance without adaptive routing for each of the strategies. It is found that the more adaptive strategies, (1), (2), and (6), perform better during periods with variable traffic, and that the less adaptive strategies perform better during periods with stable traffic. During heavy overloads, almost as important as the surveillance strategy is the number of problems, overflowing node pairs, and the algorithm attempts to relieve     

Performance analysis of circuit-switched networks withstate-dependent routing

A novel nonhierarchical dynamic routing technique called state-dependent routing (SDR) is studied. SDR uses traffic measurements and statistics to produce its call by call routing decisions. The SDR scheme has a two-level, two-time scale structure. The algorithm for evaluating the performance of networks using SDR, is based on analytical models for the fast and slow stages that capture the behavior of the network at the link level and the node-pair level, respectively. Very good results were obtained for both small and large networks, especially in the performance range that is useful for design purposes     

Adaptive alternate routing in WDM networks and its performance tradeoffs in the presence of wavelength converters

Routing in wavelength-routed all-optical WDM networks has received much attention in the past decade, for which fixed and dynamic routing methods have been proposed. Taking into account the observation that wavelength-routed all-optical WDM networks are similar to circuit-switched voice networks, except with regard to wavelength conversion, we propose an adaptive alternate routing (AAR) scheme for wavelength-routed all-optical WDM networks. A major benefit of AAR is that it can operate and adapt without requiring an exchange of network status, i.e., it is an information-less adaptive routing scheme. The scope of this work is to understand this scheme in its own right since no other dynamic routing schemes are known to have the information-less property. In this paper, we conduct a systematic study of AAR with regard to factors such as the number of converters, load conditions, traffic patterns, network topologies, and the number of alternate paths considered. We observe that the routing scheme with multiple alternate routes provides more gain at a lower load instead of requiring any nodes to be equipped with wavelength converters. On the other hand, the availability of wavelength converters at some nodes, along with adaptive routing, is beneficial at a moderate to high load without requiring all nodes to be equipped with wavelength converters. We also observed that a small number of alternate routes considered in a network without wavelength converters gives a much better performance than a network with full wavelength converters and fewer alternate routes. Throughout this study, we observed that the proposed adaptive alternate routing scheme adapts well to the network traffic condition.     

Routing and wavelength assignment with multigranularity traffic in optical networks

We propose a novel switching architecture of multigranularity optical cross-connects (MG-OXCs) for dealing with multigranularity traffic in the optical domain. MG-OXCs can cooperate with the generalized multiprotocol label switching (MPLS) control plane, which provides the advantages of cost reduction, better scalability in physical size, and unified traffic management. Detailed discussions are provided on the characteristics and implementation issues for the switching architecture. Based on the proposed MG-OXCs, two routing and wavelength assignment (RWA) with tunnel allocation algorithms are presented: dynamic tunnel allocation (DTA) and capacity-balanced static tunnel allocation (CB-STA). In the former, we use fixed alternate routing with k-shortest paths to inspect network resources along each alternate path for dynamically setting up lightpaths. For the latter, fiber and waveband tunnels are allocated into networks at the planning stage (or off-line) according to weighted network link-state (W-NLS). We will show that with the proposed algorithms, the RWA problem with tunnel allocation in the optical networks containing MG-OXCs can be solved effectively. Simulation is conducted on networks with different percentages of switching capacity and traffic load. The simulation results show that DTA is outperformed by CB-STA in the same network environment due to a well-disciplined approach for allocating tunnels with CB-STA.. We also find that the mix of the two approaches yields the best performance given the same network environment apparatus.     

Dimensioning of adaptively routed networks

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

A novel distributed control protocol in dynamic wavelength-routed optical networks

Path selection has long been one of the most important issues in the network design and management, which is also referred to as routing and wavelength assignment in the optical network domain. In this article we investigate the RWA problem for dynamic wavelength-routed mesh networks in a fully distributed controlled environment. We present a novel routing and signaling protocol called Asynchronous Criticality Avoidance (ACA), which is devised to reduce the mutual interference between lightpaths launched by different source-destination pairs to improve network performance in terms of blocking probability. With the fixed alternate routing architecture, the ACA protocol dynamically marks a set of wavelength channels as critical if the occupancy of the channels causes a bottleneck between an S-D pair with a width equal to or narrower than a predefined threshold. To support a distributed control environment, a suite of signaling processes is devised to realize the criticality avoidance mechanism, with which a two-stage routing and wavelength assignment (or criticality avoidance routing) is performed. The ACA protocol has been shown by simulations to be capable of better performance than existing schemes.     

Buffered fixed routing: a routing protocol for real-time transportin grid networks

We propose a new routing protocol called buffered fixed routing (BFR) for real-time applications on grid networks. While previous routing protocols for grid networks have been designed to improve network throughput, the BFR scheme is proposed to guarantee the end-to-end packet delay and sequencing without loss by using finite buffers at each node. Thus the proposed scheme can satisfy quality-of-service (QoS) requirements of real-time applications. The BFR scheme uses the token on the row ring to provide QoS guarantees. The performance of the BFR scheme is analyzed by using the Geom/Geom/1 queueing system under uniform traffic. In the simulation, the BFR scheme shows the zero-loss, high-throughput performance with the minimum delay variation compared to other routing protocols such as store and forward routing, deflection routing and vertical routing. In addition, it has shown the smallest average delay at intermediate and heavy loads     

An Ant-Based Approach for Dynamic RWA in Optical WDM Networks

In this paper, we propose a new ant-based algorithm for the dynamic routing and wavelength assignment (RWA) problem in optical WDM networks under the wavelength continuity constraint. Unlike conventional approaches, which usually require centralized global network information, our new RWA algorithm constructs the routing solution in a distributed manner by means of cooperative ants. To facilitate the ants’ foraging task, we adopt in our algorithm a probabilistic routing table structure for route selection. The new algorithm is highly adaptive in that it always keeps a suitable number of ants in the network to cooperatively explore the network states and continuously update the routing tables, so that the route for a connection request can be determined promptly by the current states of routing tables with only a small setup delay. Some new schemes for path scoring and path searching are also proposed to enhance the performance of our ant-based algorithm. Extensive simulation results upon three typical network topologies indicate that the proposed algorithm has a very good adaptability to traffic variations and it outperforms both the fixed routing algorithm and the promising fixed–alternate routing algorithm in terms of blocking probability. The ability to guarantee both a low blocking probability and a small setup delay makes the new ant-based routing algorithm very attractive for both the optical circuit switching networks and future optical burst switching networks     

WDM光网络多跳业务量疏导算法

针对具有多跳疏导能力的WDM光网络进行了研究,提出了一种基于固定备选路由的多跳业务量疏导算法（FO-HC-MH）。该算法对备选路由的跳数进行限制,因而可以节约使用网络的收发器资源。仿真实验表明,与FO-MH算法相比,在网络负载较低的情况下该算法节约效果明显。     

Static and dynamic approaches to modeling end-to-end routing in circuit-switched networks

We present two routing strategies, identified herein as static least loaded routing (SLLR) and dynamic least loaded routing (DLLR). Dynamic routing in circuit-switched networks has been an active research topic. The literature to date in this area has focused on how to choose the "best" alternate route for overflow traffic from a direct route, within a network setting referred to as the backbone network. The traffic type considered in the literature has typically been one with a single destination. Least loaded routing (LLR) is an example of a state-dependent routing that selects the least loaded two-link alternate route when traffic overflows from the direct route. Motivated by the development of an emerging traffic type, called multidestination traffic, whose destination is not necessarily limited to a single location, we provide two routing strategies that deal with both the routing of the multiple-destination traffic to the extended network dimension, which is referred to as the destination network, and the routing of the backbone network traffic via LLR. In selecting the destination for multidestination traffic, SLLR employs static information, whereas DLLR employs real-time load status information concerning the destination links. We develop fixed-point models for both DLLR and SLLR. We also validate and compare the models through simulation. The results suggest that DLLR outperforms SLLR in all the scenarios, demonstrating the benefit of state-dependent routing in an end-to-end network. Further, the DLLR scheme improves if an "incident preference" rule is adopted; the rule allows a multidestination call to first choose the incident destination link, if any.     

自相似业务在WDM网络中的动态性能分析

通过在几种颇具代表性的网络拓扑结构上进行仿真,对自相似业务在波分复用（WDM）光网络中的动态路由波长分配（RWA）问题进行了研究,分析了自相似业务在不同波长路由分配策略下的动态性能,并与相同条件下的泊松业务作了对比。     

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.     

Analysis of automatic network management controls

The performance response of circuit-switched networks with stored program control exchanges is analyzed under nonstationary traffic conditions. Models of real time traffic measurements and dynamic flows in such networks are developed. A framework for analysis and design of state-dependent routing and flow control algorithms is provided based on concepts of various traffic measurements and different patterns of traffic nonhomogeneity. It is indicated that global performance objectives can be obtained by means of the state-dependent shortest route algorithms. Issues relevant to an implementation of different traffic control techniques are discussed. An example routing scheme is introduced and compared with known procedures     

Dynamic wavelength routing using congestion and neighborhoodinformation

We present two dynamic routing algorithms based on path and neighborhood link congestion in all-optical networks. In such networks, a connection request encounters higher blocking probability than in circuit-switched networks because of the wavelength-continuity constraint. Much research has focused on the shortest-path routing and alternate shortest-path routing. We consider fixed-paths least-congestion (FPLC) routing in which the shortest path may not be preferred to use. We then extend the algorithm to develop a new routing method: dynamic routing using neighborhood information. It is shown by using both analysis and simulation methods that FPLC routing with the first-fit wavelength-assignment method performs much better than the alternate routing method in mesh-torus networks (regular topology) and in the NSFnet T1 backbone network (irregular topology). Routing using neighborhood information also achieves good performance when compared to alternate shortest-path routing     

Performance analysis under dynamic loading of wavelength continuous and non‐continuous WDM networks with shortest‐path routing

The performance of WDM networks using shortest path routing is studied under wavelength continuous (WC) and non‐continuous (NWC) constraints and dynamic traffic loading. Approximate analytical models are presented for the performance studies of such systems. Results of numerical calculations based on these models and simulations are given for different network topologies for the purposes of comparison. These analytical and simulation results are used to study the performance of these WDM networks under dynamic traffic loading. Copyright © 2001 John Wiley & Sons, Ltd.     

A taxonomy of rerouting in circuit-switched networks

In circuit-switched networks it is well known that dynamic routing can provide significant throughput gain over fixed routing. Rerouting is the practice of routing calls currently on alternate paths to direct paths or other less congested alternate paths. Previous studies have shown that rerouting can not only increase the throughput of dynamic routing, but also maintain network stability without the need for trunk reservation. This article presents a taxonomy of rerouting in circuit-switched networks showing the various ways rerouting can be designed. In addition, a comparative study on a number of rerouting schemes are performed in a uniformly loaded, fully connected circuit-switched network     

Blocking probability evaluation of end-to-end dynamic WDM networks

Two mathematical methods for blocking probability evaluation of end-to-end dynamic WDM networks are proposed. The first method can be applied to networks operating with static (fixed) routes. By diminishing the impact of the link independence assumption, the method proposed improves a recently proposed mathematical procedure that assumes link blocking independency and non-Poisson traffic. To do so, the so-called streamline effect is taken into account in the equations. As a result, values closer to that of simulation are obtained. The second method applies to networks operating with alternate routing. In this case, the method simultaneously relaxes three non-realistic assumptions of previous works: the link blocking independence, the Poisson traffic arrival and the homogeneity of the traffic load offered to the network links. Both methods were applied to different network topologies, and their results were compared to those of simulation. Results show that the match between simulation and the proposed methods is excellent, and better than assuming link blocking independence, in all the topologies studied.