Effect of Modeling Uncertainty on Some Routing Problems

In this paper, we consider the routing problem described in Mohanty and Cassandras (Ref. 1). As in Ref. 1, we show that the optimal Bernoulli split to minimize mean time in the system is asymptotically independent of the variance of the service time. We give simple proofs of the results in that paper. We exploit the fact that the optimal split to minimize the mean queueing time is variance independent and the special structure of the Karush–Kuhn–Tucker optimality conditions to derive the optimal solution. Apart from being very straightforward, the proofs also give insight into the reason for the existence of the variance-independent asymptotically optimal routing policy.     

Routing restorable bandwidth guaranteed connections using maximum 2-route flows

Routing with service restorability is of much importance in Multi-Protocol Label Switched (MPLS) networks, and is a necessity in optical networks. For restoration, each connection has an active path and a link-disjoint backup path. The backup path enables service restoration upon active path failure. For bandwidth efficiency, backups may be shared. This requires that at least the aggregate backup bandwidth used on each link be distributed to nodes performing route computations. If this information is not available, sharing is not possible. Also, one scheme in use for restorability in optical networks is for the sender to transmit simultaneously on the two disjoint paths and for the receiver to choose data from the path with stronger signal. This has the advantage of fast receiver-initiated recovery upon failure but it does not allow backup sharing. In this paper, we consider the problem of efficient dynamic routing of restorable connections when backup sharing is not allowed. Our objective is to be able to route as many connections as possible for one-at-a-time arrivals and no knowledge of future arrivals. Since sharing cannot be used for achieving efficiency, the goal is to achieve efficiency by improved path selection. We show that by using the minimum-interference ideas used for nonrestorable routing, we can develop efficient algorithms that outperform previously proposed algorithms for restorable routing such as routing with the min-hop like objective of finding two disjoint paths with minimum total hop-count. We present two new and efficient algorithms for restorable routing without sharing, and one of them requires only shortest path computations. We demonstrate that both algorithms perform very well in comparison to previously proposed algorithms.     

RATES: a server for MPLS traffic engineering

It has been suggested that one of the most significant reasons for multiprotocol label switching (MPLS) network deployment is network traffic engineering. The goal of traffic engineering is to make the best use of the network infrastructure, and this is facilitates by the explicit routing feature of MPLS, which allows many of the shortcomings associated with current IP routing schemes to be addressed. This article describes a software system called Routing and Traffic Engineering Server (RATES) developed for MPLS traffic engineering. It also describes some new routing ideas incorporated in RATES for MPLS explicit path selection. The RATES implementation consists of a policy and flow database, a browser-based interface for policy definition and entering resource provisioning requests, and a Common Open Policy Service protocol server-client implementation for communicating paths and resource information to edge routers. RATES also uses the OSPF topology database for dynamically obtaining link state information. RATES can set up bandwidth-guaranteed label-switched (LSPs) between specified ingress-egress pairs. The path selection for LSPs is on a new minimum-interference routing algorithm aimed at making the best use of network infrastructure in an online environment where LSP requests arrive one by one with no a priori information about future requests. Although developed for an MPLS application, the RATES implementation has many similarities in components to an intradomain differentiated services bandwidth broker     

Performance analysis of call assignment and carrier packing schemes for TDMA systems

In IS-136 and GSM time-division multiple-access (TDMA) systems that employ dynamic channel allocation, it is important to minimize the number of active carriers for a given load. This paper studies the carrier packing properties of both call assignment and carrier repacking schemes, where the average number of active carriers and the average number of intra-sector (repack induced) handoffs per call are the relevant metrics. We show that the simple to implement sequential trunk hunt (STH) call assignment scheme is almost as good as the optimal intelligent channel assignment (ICA) scheme and that the MaxPack repacking scheme is optimal for both of these TDMA standards among all call assignment and repacking schemes. The call assignment and repacking schemes considered are shown to have either closed-form or efficient numerical recursive solutions for the North American IS-136 standard, and in most cases we obtain the underlying state space distributions. A mixture of analytic and simulation results is also presented for the GSM standard. Numerical results show that most of the packing efficiency can be achieved simply by a good call assignment scheme such as ICA and that the additional gain from optimal repacking is generally in the 10-15% range for typical IS-136 and GSM configurations.     

Fast, Memory Efficient Flow Rate Estimation Using Runs

Per-flow network traffic measurements are needed for effective network traffic management, network performance assessment, and detection of anomalous network events such as incipient denial-of-service (DoS) attacks. Explicit measurement of per-flow traffic statistics is difficult in backbone networks because tracking the possibly hundreds of thousands of flows needs correspondingly large high-speed memories. To reduce the measurement overhead, many previous papers have proposed the use of random sampling and this is also used in commercial routers (Cisco's NetFlow). Our goal is to develop a new scheme that has very low memory requirements and has quick convergence to within a pre-specified accuracy. We achieve this by use of a novel approach based on sampling two-runs to estimate per-flow traffic. (A flow has a two-run when two consecutive samples belong to the same flow). Sampling two-runs automatically biases the samples towards the larger flows thereby making the estimation of these sources more accurate. This biased sampling leads to significantly smaller memory requirement compared to random sampling schemes. The scheme is very simple to implement and performs extremely well.     

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.     

Narrowband and broadband infrastructure design for wirelessnetworks

There has been an explosion in the number of wireless subscribers. A number of air interface technologies, such as GSM, TDMA and CDMA, are available to wireless service providers for offering wireless services. In addition, a variety of networking technologies, such as STM, ATM and frame relay, are available to the wireless services provider for designing their infrastructure networks. The abundant choice of technologies, and their associated capabilities and costs, creates a need for network design tools which can help vendors and wireless service providers to understand the economics of investing in different technologies. This article is concerned with the design of narrowband and broadband infrastructure networks for wireless access. The article first describes the different technology alternatives and tariff structures and their impact on wireless infrastructure network design. The general infrastructure design problem is then stated and a solution methodology outlined. Examples of the economic trade-offs involved in narrowband and broadband networking technologies are also presented     

Traffic-Oblivious Routing for Guaranteed Bandwidth Performance

A virtual private network provides network connectivity among the different sites of an enterprise. The bandwidth requirement of a VPN is typically specified by peak ingress-egress traffic volumes for each site. The actual distribution of traffic from each site to other sites in the VPN is not known a priori and could vary over time (e.g., at an intra-day or daily level or due to special activities). This is captured by the hose traffic model. It is the responsibility of the Internet service provider to provision the VPN so that variable traffic subject to aggregate ingress-egress constraints can be transported with bandwidth guarantees. We describe a capacity-efficient, robust, and traffic-oblivious routing strategy, called two-phase routing, that allows preconfiguration of the VPN such that all traffic patterns permissible within the network's natural ingress-egress capacity constraints can be routed with bandwidth guarantees. The scheme routes traffic in two phases: traffic entering the VPN is sent from the source to a set of intermediate nodes in predetermined split ratios that depend on the intermediate nodes, and then from the intermediate nodes to the final destination. (The traffic split ratios can also be generalized to depend on the source and/or destination of traffic.) A significant benefit of the described schemes is that the network can be configured for completely static operation while providing service-level guarantees to widely varying VPN traffic. This is unlike previous approaches based on direct source-destination routing, which need dynamic adaptation to changing traffic conditions in order to provide service-level guarantees