Analysis of rerouting in circuit-switched networks

Dynamic routing has been adopted in circuit-switched networks in many parts of the world. Most of the routing algorithms used are least loaded routing (LLR) based for its simplicity and efficiency. Rerouting is the practice of routing calls on alternate paths back to direct paths or to other less congested alternate paths. It allows the continuous redistribution of network loads for the relief of the congestion on direct paths. In this paper, we present an original analysis of an LLR-based rerouting scheme. Through numerical examples and confirmation by computer simulation, the throughput gain of rerouting is established     

Call queueing in circuit-switched networks

Consider a circuit-switched network whereC source switches are connected to a destination switch via a tandem switch. Circuit-switched networks traditionally employ a Blocked Calls Lost (BCL) call admission control: a call is rejected if all access circuits from the originating switch to the tandem switch are busy, or if allB outgoing circuits from the tandem switch to the destination switch are busy. This paper investigates a simple extension to the BCL control. Rather than reject all blocked calls, the Blocked Calls Queued (BCQ) control holds some blocked calls by storing their call signalling information in a buffer at the tandem switch. These calls will later be connected when circuits become available. The BCQ model is solved using standard methods requiring O(BC) storage locations and O(B ² C) arithmetic operations. We show that the BCQ control becomes effective if calls are rejected (source rejection) when all access circuits are busy. We demonstrate that the BCQ control with source rejection achieves a substantial reduction in the loss probability at the expense of a small connection delay.This work was supported by a grant from the Foundation for Research Development Communications Systems Programme.     

A mutual alternative routing model for circuit-switched networks

Security measures are being applied in the Telecom Eireann trunk telephone network to minimise disruption due to excess traffic or system failure. Dynamic measures, such as network management, will be deployed in the very near future, but in the meantime static measures are being applied. Geographically separate exchanges of the same status are provided at major nodes with traffic shared equally between them on separate transmission links. Rerouting is provided automatically when a system fails, but at a reduced grade of service. The paper presents a model which simulates this concept of mutual alternative routing using the UNIX-based OPNET (Optimised Network Engineering Tools) package     

Path selection in user-controlled circuit-switched optical networks

User-controlled circuit-switched optical networks are gaining popularity in an effort to fulfill the insatiable data transport needs of the online community. In this paper we consider the resource allocation challenges that arise in such networks, in particular problems related to construction of end-to-end lightpaths for carrying large multimedia streams. Specifically, we discuss variations of the least cost and widest path problems that address two unique aspects of the user-controlled environment. First, since network resources are exposed for user-control using a service-oriented software control plane, each lightpath is subject to an expiry time. Second, because Wavelength Division Multiplexing (WDM) and resource partitioning introduces multiple redundant paths, classic least cost path computations tend to yield multiple optimal solutions, and so it is useful to break ties among these in a judicious manner. We present polynomial-time path selection techniques that address these issues using efficient data structures. We also show the benefit of breaking ties in shortest path computations in a manner that reduces harmful fragmentation of capacity.     

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     

Behaviour of circuit-switched multistage networks in presence of memory hot spot

Addresses the important problem of evaluating the performance of tightly coupled multiprocessor systems under memory hot spot traffic by presenting an interference analysis of multistage interconnection networks (MINs) for such systems. It is shown that the tree saturation effect does not occur in nonblocking circuit-switched MINs.<>     

A time optimal wavelength rerouting algorithm for dynamic trafficin WDM networks

In this paper, we consider wavelength rerouting in wavelength routed wavelength division multiplexed (WDM) networks with circuit switching, wherein lightpaths between source-destination pairs are dynamically established and released in response to a random pattern of arriving connection requests and connection holding times. The wavelength continuity constraint imposed by WDM networks leads to poor blocking performance. Wavelength rerouting is a viable and cost effective mechanism that ran improve the blocking performance by rearranging certain existing lightpaths to accommodate a new request. Recently, a rerouting scheme called “parallel move-to-vacant wavelength retuning (MTV-WR)” with many attractive features such as shorter disruption period and simple switching control, and a polynomial time rerouting algorithm, for this scheme, to minimize the weighted number of rerouted lightpaths have been proposed. This paper presents a time optimal rerouting algorithm for wavelength-routed WDM networks with parallel MTV-WR rerouting scheme. The algorithm requires only O(N²W) time units to minimize the weighted number of existing lightpaths to be rerouted, where N is the number of nodes in the network and W is the number of wavelength channels available on a fiber link. Our algorithm is an improvement over the earlier algorithm proposed in that it requires O(N³W+N²W²) time units, which is not time optimal. The simulation results show that our algorithm improves the blocking performance considerably and only very few lightpaths are required to be rerouted per rerouting. It is also established through simulation that our algorithm is faster than the earlier rerouting algorithm by measuring the time required for processing connection requests for different networks     

General criterion for decomposition of exact blocking computationin circuit-switched networks

The criterion for the decomposition of the computation of blocking probabilities in circuit-switched networks is given. As the criterion does not depend on the network topology or the traffic distribution, more efficient decomposition can be obtained accordingly     

Comparative evaluations of randomized and dynamic routingstrategies for circuit-switched networks

The performances of two classes of routing algorithms, randomized and deterministic, are evaluated and compared in terms of revenue generated and link failures. The randomized algorithm evaluated is dynamic alternate routing, and for the deterministic algorithm, attempts to carry a call are made in a specific precomputed order. The design of the routing sequences depends upon analytic approximations based on fixed-point equations to evaluate network performance and heuristics for the complicated problem of network revenue maximization. The control mechanism of trunk reservations is shown to play an important role in all cases. The performances of the algorithms were evaluated on a fully connected six-node network, the data for which were extracted from a realistic network. The design tools, time constants of various algorithms, and hybrid algorithms developed using the evaluation results are described     

Performance evaluation of connection rerouting schemes forATM-based wireless networks

Supporting mobility in asynchronous transfer mode (ATM)-based broad-band networks with wireless access links poses many technical challenges. One of the most important of these challenges is the need to reroute ongoing connections to/from mobile users as these users move among base stations. Connection rerouting schemes must exhibit low handoff latency, maintain efficient routes, and limit disruption to continuous media traffic while minimizing reroute updates to the network switches. In this paper we propose, describe an implementation for, and experimentally evaluate the performance of five different connection rerouting schemes. We show that one of these schemes, which operates in two phases, executes very fast reroutes (with a measured latency of 6.5 ms) in a real-time phase and, if necessary, reroutes again in a nonreal-time phase to maintain efficient routing. The scheme also results in negligible disruption to both audio (e.g., a 1-in-100 chance of a single packet loss at CD-quality audio rates of 128 kb/s) and low-bit-rate video (e.g., a 2-in-100 chance of a single packet loss for 1-Mb/s video) traffic during connection rerouting. Based on these results, we conclude that simple handoff schemes coupled with a connection management architecture are sufficient for supporting low-bit-rate continuous media applications over ATM-based wireless networks     

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.     

Footprint handover rerouting protocol for low Earth orbit satellite networks

Low Earth Orbit (LEO) satellite networks will be an integral part of the next generation telecommunications infrastructures. In a LEO satellite network, satellites and their individual coverage areas move relative to a fixed observer on Earth. To ensure that ongoing calls are not disrupted as a result of satellite movement, calls should be transferred or handed over to new satellites. Since two satellites are involved in a satellite handover, connection route should be modified to include the new satellite into the connection route. The route change can be achieved by augmenting the existing route with the new satellite or by completely rerouting the connection. Route augmentation is simple to implement, however the resulting route is not optimal. Complete rerouting achieves optimal routes at the expense of signaling overhead. In this paper, we introduce a handover rerouting protocol that maintains the optimality of the initial route without performing a routing algorithm after intersatellite handovers. The FHRP makes use of the footprints of the satellites in the initial route as the reference for rerouting. More specifically, after an optimum route has been determined during the call establishment process, the FHRP ensures that the new route due to handover is also optimum. The FHRP demands easy processing, signaling, and storage costs. The performance results show that the FHRP performs similar to a network without any handovers in terms of call blocking probability.     

Performance analysis of path rerouting algorithms for handoffcontrol in mobile ATM networks

This paper studies the effects of user mobility and handoff path rerouting on the traffic distributions in a mobile network environment. In mobile ATM networks, extra traffic load may be added to network links due to user mobility and handoff path rerouting. This requires higher network link capacity and possible topology reengineering in order to support the same quality of service (QoS) for mobile services. To capture the dynamic variations in mobile ATM networks, we propose to use a flow model. The model represents the mobile-generated traffic as a set of stochastic flows over a set of origin-destination (OD) pairs. The user mobility is defined by transfer probabilities of the flows and the handoff path rerouting algorithm is modeled by a transformation between the routing functions for traffic flows. The analysis shows that user mobility may cause temporal variations as well as smoothing effects on the network traffic. Using the flow network model, typical handoff path rerouting algorithms are evaluated through both analytical and experimental approaches. The evaluation methodology can be used for either redesigning the network topology for a given path rerouting algorithm or selecting a path rerouting algorithm for a given network topology under a specific mobile service scenario     

A hybrid rerouting scheme

In this work we study a routing scheme combined with an end-to-end rerouting procedure. We focus in particular on a new rerouting strategy called Shared Robust Rerouting (ShRR). This strategy combines three other restoration techniques, namely path diversity, end-to-end rerouting with stub release and global rerouting, in order to achieve cost-effectiveness. Computational results on the bandwidth overhead required by the proposed scheme are provided, as well as a comparison with some conventional restoration schemes.     

Quantifying the benefit of configurability in circuit-switched WDMring networks with limited ports per node

In a reconfigurable network, lightpath connections can be dynamically changed to reflect changes in traffic conditions. This paper characterizes the gain in traffic capacity that a reconfigurable wavelength division multiplexed (WDM) network offers over a fixed topology network where lightpath connections are fixed and cannot be changed. We define the gain as the ratio of the maximum offered loads that the two systems can support for a given blocking probability. We develop a system model to approximate the blocking probability for both the fixed and reconfigurable systems. This model is different from previous models developed to analyze the blocking probability in WDM networks in that it accounts for a port limitation at the nodes. We validate our model via simulation and find that it agrees strongly with simulation results. We study high-bandwidth calls, where each call requires an entire wavelength and find that reconfigurability offers a substantial performance improvement, particularly when the number of available wavelengths significantly exceeds the number of ports per node. In this case, in a ring with N nodes, the gain approaches a factor of N/2 over a fixed topology unidirectional ring, and N/4 over a fixed topology bidirectional ring. Hence, a reconfigurable unidirectional (bidirectional) ring can support N/2(N/4) times the load of a fixed topology unidirectional (bidirectional) ring. We also show that for a given traffic load, a configurable system requires far fewer ports per node than a fixed topology system. These port savings can potentially result in a significant reduction in overall system costs     

Improving the efficiency of circuit-switched satellite networks bymeans of dynamic bandwidth allocation capabilities

Current satellite systems operate according to circuit switching transfer modes. To improve flexibility and efficiency, several kinds of packet switching systems have been proposed. However, it appears that full packet switches are still too complex and expensive to be implemented on board the satellites in the near future. For the time being, dynamic bandwidth allocation capabilities (DBAC) provide a compromise solution when satellite systems are based on classical circuit switches, since the DBAC payload allows changing dynamically the capacity of each connection, without teardown and setup. We consider a DBAC satellite system, and define algorithms to allocate the bandwidth so as to provide deterministic and statistical QoS guarantees. Standard dual leaky buckets (DLBs) regulate the traffic sources. We define bandwidth-handling policies, design connection admission control rules, and evaluate the system performance analytically. Results show a significant increase in bandwidth utilization of our system, when compared to a plain circuit switching solution     

A taxonomy for medium access control protocols in wireless sensor networks

Wireless sensor networks (Wsns) tend to be highly optimized due to severely restricted constraints. Various medium access control (Mac) protocols forWsns have been proposed, being specially tailored to a target application. This paper proposes a taxonomy for the different mechanisms employed in those protocols. The taxonomy characterizes the protocols according to the methods implemented to handle energy consumption, quality of service and adaptability requirements. We also present an overview of the transceptors found inWsns, identifying how events on communication affect the energy consumption. Based on the taxonomy, we classify existingMac protocols. Finally, we discuss challenging trends inMac protocols forWsns, such as security issues and software radios.     

New preemption policies for DiffServ-aware traffic engineering to minimize rerouting in MPLS networks

The preemption policy currently in use in MPLS-enabled commercial routers selects LSPs for preemption based only on their priority and holding time. This can lead to waste of resources and excessive number of rerouting decisions. In this paper, a new preemption policy is proposed and complemented with an adaptive scheme that aims to minimize rerouting. The new policy combines the three main preemption optimization criteria: number of LSPs to be preempted, priority of the LSPs, and preempted bandwidth. Weights can be configured to stress the desired criteria. The new policy is complemented by an adaptive scheme that selects lower priority LSPs that can afford to have their rate reduced. The selected LSPs will fairly reduce their rate in order to accommodate the new high-priority LSP setup request. Performance comparisons of a nonpreemptive approach, a policy currently in use by commercial routers, and our policies are also investigated.