Multiple transmission point (TP) coordination is an effective tool for managing interference in heterogeneous networks. Using network-level MIMO coordination among TPs, multiple TPs can transmit independent data streams to a single user. We formulate our scheduling problem as a utility optimization problem over the set of user-TP pairs in each subframe, in which each user can be served by multiple TPs. We first prove that this optimization problem is NP-hard. Then, we propose a new scheme based on the difference-of-submodular-function optimization approach. We evaluate our scheme using detailed simulation and demonstrate that it performs on par with a more computationally demanding successive convex approximation optimization scheme. Moreover, the proposed scheme performs within a reasonable percentage of the optimal solution (Table IV). We also study its performance with varying network topology and parameters.

Deployment of low power pico basestations within cellular networks can potentially increase both capacity and coverage. However, such deployments require efficient frequency allocation schemes for managing interference from the pico and macro basestations that are located within each other's transmission range. Partitioning the available frequencies between the various basestations avoids the problem of interference, but can lead to inefficient spectrum usage. In this paper, we introduce a distributed frequency allocation scheme that shares frequencies between macro and pico basestations, and guarantees a minimum average throughput to users. The scheme seeks to minimize the total number of frequencies needed to honor the minimum throughput requirements. We evaluate our scheme using detailed simulations and show that it performs on par with the centralized optimum allocation. Moreover, our proposed scheme outperforms a static frequency reuse scheme and the centralized optimal partitioning between the macro and pico basestations.

Current IP geoloation techniques can geolocate an IP address to a region approximately 700 square miles, roughly the size of a metropolitan area. We model geolocation as a pattern-recognition problem, and introduce techniques that geolocate addresses to within 5 miles inside a metropolitan area. We propose two complementary algorithms: The first algorithm, Pattern Based Geolocation (PBG), models the distribution of latencies to the target and compares it to those of the reference landmarks to resolve an address to within 5 miles in a metropolitan area. The second approach, Perturbation Augmented PBG (PAPBG), provides higher resolution by sending extra traffic in the network. While sending an aggregate of 600 Kbps extra traffic to 20 nodes for approximately 2 minutes, PAPBG geolocates addresses to within 3 miles.

In a sensor network with information sources and a sink, we assume a single path between every location in the network and the destination. These abstract information paths represent the desired paths for transmission of information. If the number of sensor nodes is large enough to approximate information paths with a certain precision, we call the network implementable. In this paper, we investigate the relation between density of nodes and implementability of information paths. We show that a quadratic relation between the density of nodes and the magnitude of information flow does not guarantee implementability. On the other hand, we show that in a rectangular geometry with a line source and a line sink, and a total load of ¿ bps, N = O(¿2log ¿) number of nodes is sufficient for implementing the information paths. Furthermore, we show via simulation that adding the log factor is also a necessity for implementing the paths.

We study the problem of assigning wavelengths to a given set of multicast traffic requests with the objective of minimizing the number of wavelengths used per fiber. We assume that the underlying optical network is a tree and that all-optical networking paradigm is employed. First, we prove that the problem is NP hard even when the underlying network is a simple star or path. Since assigning wavelengths to a given set of unicast traffic requests on star and path networks is easy, this shows that the the multicast wavelength assignment problem is fundamentally harder than the unicast scenario. Next we present GREEDY and SUBTREE-BASED: two simple deterministic algorithms for assigning wavelengths to a given set of multicast traffic requests when the underlying network is a tree with maximum node degree 3 and 4 respectively. Of the two wavelength assignment schemes, GREEDY is a 5/2-approximation algorithm, and SUBTREE-BASED is an approximation algorithm with approximation ratio 10/3, 3 and 2 for the cases when the underlying network is a tree with degree 4, 3 and 2, respectively.

We use a vector field model to formulate flow of information at every point of a dense wireless sensor network. The magnitude of this vector field represents the density of communication activity and its direction is toward the flow of information at each point. We present a general method for flow optimization in a wireless sensor network by minimizing thep-normof the information flow vector field subject to the basic flow constraints, that is the flow conservation law and boundary constraints. We have called this problem thep-normflow optimization, and use Sequential Quadratic Programming to solve it. Thep-normflow optimization shows interesting properties for different values ofp. Forpclose to 1, the information routes resemble the geometric shortest paths while as p gets larger, there will be more load balancing effects in the flow. In this work we focus on the numerical analysis of thep-normflow problem. For this we have to approximate the continuous flow problem by a discrete problem which adds some inaccuracy to the solutions. Therefore, we propose an algorithm to continuously compensate the error in the information flow vector field and avoid error accumulation in the system. We also discuss ways with which we can support different network geometries in the numerical analysis.

We present an asynchronous wakeup policy for wireless sensor networks that exploits the available path diversity for maximizing the expected network lifetime. We assume a random traffic generation model such that the rate is constant in time. Each node is assumed to have a set of forwarding neighbors, any of which may be used for forwarding its traffic to the sink. A node having data packet to send, transmits the packet to the first available node in its forwarding set. In order to maximize the network lifetime, we balance the power dissipation at the network nodes by adjusting the wakeup parameters at various nodes. Allowing different nodes to wakeup with different rates makes the scheme asymmetric. For ease of analysis, we restrict ourselves to static, open-loop policies. We show that the optimization problem is a Signomial Program (SP), that can be well approximated as a Geometric Program (GP). By extensive simulations, we compare the asymmetric policy thus obtained to the best possible symmetric policy obtained from the same optimization setup but ensuring additionally that the wakeup rates at all the nodes are the same (in which case the optimization problem is shown to be exactly a GP). The simulations show that allowing asymmetry can extend the network lifetime by effectively exploiting the available path diversity. Moreover, we also prove that, in case of symmetric policies, no piecewise static policy can beat the simple static policy that we use for comparison in our results. This shows that in the space of open-loop, asynchronous wakeup policies, employing the static, asymmetric policy presented in this paper is much more profitable than even the best piecewise static, symmetric policy.

In a network with a high density of wireless nodes, we model flow of information by a continuous vector field known as the information flow vector field. We use a mathematical model that translates a communication network composed of a large but finite number of sensors into a continuum of nodes on which information flow is formulated by a vector field. The magnitude of this vector field is the intensity of the communication activity, and its orientation is the direction in which the traffic is forwarded. The information flow vector field satisfies a set of Neumann boundary conditions and a partial differential equation (PDE) involving the divergence of information, but the divergence constraint and Neumann boundary conditions do not specify the information flow vector field uniquely, and leave us freedom to optimize certain measures within their feasible set. Therefore, we introduce ap-normflow optimization problem in which we minimize thep-normof information flow vector field over the area of the network. This problem is a convex optimization problem, and we use sequential quadratic programming (SQP) to solve it. SQP is known for numerical stability and fast convergence to the optimal solution in convex optimization problems. By using standard SQP onp-normflow optimization, we prove that the solution of each iteration of SQP is uniquely specified by an elliptic PDE with generalized Neumann boundary conditions. Thep-normflow optimization shows interesting properties for different values ofp. For example, if p is close to one, the information routes resemble the geometric shortest paths of the sources and sinks, and forp= 2, the information flow shows an analogy to electrostatics. For infinitely large values ofp, the problem minimizes the maximum magnitude of the information vector field over the network, and hence it achieves maximum load balancing.

Abstract Poison message failure is a mechanism that has been responsible for large‐scale failures in both telecommunications and IP networks. We design a fault management framework that integrates passive diagnosis and active diagnosis to identify the poison message and prevent network instability. Passive diagnosis uses real‐time inference and reasoning techniques to analyze network information and generates a probability distribution of the poison message, and the probability distribution is used in active diagnosis for further failure identification. In active diagnosis, message filtering is used to block suspect message types. Blocking messages affects network performance and service. The tradeoff of message filtering is formulated as a Markov Decision Process (MDP). The large size of the state space makes it impractical to use traditional techniques to solve the MDP. Con sequently, we use a combination of reinforcement learning and feature‐based function approximation to obtain a suboptimal policy. Extensive simulations demonstrate the effectiveness of passive diagnosis, and show that the suboptimal policy performs significantly better than a well‐known heuristic policy. Copyright © 2008 John Wiley & Sons, Ltd.

In this paper we use an information flow model for placement of traffic sinks in a wireless sensor network. Our mathematical model translates a communication network composed of countably many sensors into a continuum model described by a continuous vector field. This vector field models flow of information in a sensor network, and its magnitude is the intensity of the communication activity, and its orientation is the direction in which the traffic is forwarded. We use this formulation for design of a sensor network in which the traffic generated by the wireless sensors needs to be routed to one of the multiple traffic sinks in different locations of the network. We show that the optimal vector field satisfies a set of PDEs similar to Maxwell's equations in electrostatics, with Neumann boundary conditions. We prove that the orientation of the vector field at the location of each sink is the direction of the steepest descent of the total communication cost function of the network. This direction corresponds to the direction of force in an analogous electrostatics problem. We use this result in order to introduce iterations that relocate sinks and show that in the optimal placement of sinks, the value of the vector field is zero at the location of each sinks.

In this paper, we present an algorithm for intra-domain traffic engineering. We assume that the traffic matrix, which specifies traffic load between every source-destination pair in the network, is unknown and varies with time, but that always lies inside an explicitly defined region. Our goal is to compute a fixed robust routing with best worst case performance for all traffic matrices inside the bounding region. We formulate this problem as a semi-infinite programming problem. Then, we focus on a special case with practical merits, where (1) the traffic matrix region is assumed to be a polytope specified by a finite set of linear inequalities, and (2) our objective is to find the routing that minimizes the maximum link utilization. Under these assumptions, the problem can be formulated as a polynomial size linear programming (LP) problem with finite number of constraints. We further consider two specific set of constraints for the traffic matrix region. The first set is based on the hose model and limits the total traffic rate of network point of presence (PoP) nodes. The second set is based on the pipe model and limits the traffic between source-destination pairs. We study the effectiveness of each set of constraints using extensive simulations.

In this paper we study the problem of efficient grooming of given non-uniform multicast traffic demands on a unidirectional SONET/WDM ring. The goal is to try to minimize the network cost as given by (i) the number of wavelengths required per fiber and (ii) the number of electronic add-drop multiplexers (ADMs) required on the ring. The problem is NP hard for both the cost functions. We observe that the problem with cost function (i) can be reduced to a corresponding traffic grooming problem for unicast traffic which can then be modelled as a standard circular-arc graph coloring problem. For cost function (ii), we construct a graph based heuristic and compare it against the multicast extension of the best known unicast traffic grooming heuristic (Zhang, 2000). We observe that our heuristic requires fewer ADMs than required by the multicast extension of the unicast heuristic given in (Zhang, 2000). We also develop a lower bound and compare it against some upper bounds to study the maximum penalty of not employing intelligent wavelength assignment and/or traffic grooming under the unidirectional SONET/WDM ring scenario.

We consider the problem of finding a single-path intra-domain routing for time-varying traffic. We characterize the traffic variations by a finite set of traffic profiles with given non-zero fractions of occurrence. Our goal is to optimize the average performance over all of these traffic profiles. We solve the optimal multi-path version of this problem using linear programming and develop heuristic single-path solutions using randomized rounding and iterated rounding. We analyze our single-path heuristic (finding the optimal single-path routing is NP-hard), and prove that the randomized rounding algorithm has a worst case performance bound of O(log(KN)/log(log(KN))) compared to the optimal multi-path routing with a high probability, where K is the number of traffic profiles, and N the number of nodes in the network. Further, our simulations show the iterated rounding heuristics perform close to the optimal multi-path routing on a wide range of measured ISP topologies, in both the average and the worst-case. Overall, these results are extremely positive since they show that in a wide-range of practical situations, it is not necessary to deploy multi-path routing; instead, an appropriately computed single-path routing is sufficient to provide good performance.

We propose a framework for providing instantaneous backup to traffic in a hybrid RF/FSO mesh network. Free space optical (FSO) links have high bandwidth and security, making them suitable for use in backbone networks. RF links have low bandwidth, but offer high reliability in conditions where FSO links are obscured. Thus, RF links are primarily used to provide instantaneous backup to traffic flowing on FSO links. We propose a framework to model FSO link failures due to obscuration, and propose algorithms for integrated topology control of RF links and routing for maximizing the backup provided. We do extensive simulations to demonstrate that the performance of RF topology and routing computed using our algorithms is much better than the case of having the same RF and FSO topologies and routes.

rdquoWe present a novel group-based mechanism to reconfigure the virtual topology of survivable MPLS/WDM networks by using the existing shared protection backup resource. With this mechanism, lightpaths are divided into groups and those in the same group can be reconfigured simultaneously at one step. Ideally, this mechanism won't incur any service disruption during the reconfiguration process. The optimal reconfiguration policy is obtained through solving following two problems: the Grouping problem which minimizes the reconfiguration steps, and the Sequencing problem which minimizes the network resource used during the reconfiguration process. We prove these two problems to be NP-hard and present efficient heuristic algorithms. A general mathematical method of rollout is applied to the heuristics to improve the solution quality. Numerical results are presented to show the optimal tradeoff between the reconfiguration duration and the required redundant capacity.

In a sensor network, usually a large number of sensors transport data messages to a limited number of sinks. Due to this multipoint-to-point communications pattern in general homogeneous sensor networks, the closer a sensor to the sink, the quicker it will deplete its battery. This unbalanced energy depletion phenomenon has become the bottleneck problem to elongate the lifetime of sensor networks. In this paper, we consider the effects of joint relay node deployment and transmission power control on network lifetime. Contrary to the intuition the relay nodes considered are even simpler devices than the sensor nodes with limited capabilities. We show that the network lifetime can be extended significantly with the addition of relay nodes to the network. In addition, for the same expected network lifetime goal, the number of relay nodes required can be reduced by employing efficient transmission power control while leaving the network connectivity level unchanged. The solution suggests that it is sufficient to deploy relay nodes only with a specific probabilistic distribution rather than the specifying the exact places. Furthermore, the solution does not require any change on the protocols (such as routing) used in the network.

Abstract — We propose a measurement-based routing algorithm to load balance intradomain traffic along multiple paths for multiple multicast sources. Multiple paths are established using application-layer overlaying. The proposed algorithm is able to converge under different network models, where each model reflects a different set of assumptions about the multicasting capabilities of the network. The algorithm is derived from simultaneous perturbation stochastic approximation and relies only on noisy estimates from measurements. Simulation results are presented to demonstrate the additional benefits obtained by incrementally increasing the multicasting capabilities. I.

Sensors typically use wireless transmitters to communicate with each other. However, sensors may be located in a way that they cannot even form a connected network (e.g, due to failures of some sensors, or loss of battery power). In this paper we consider the problem of adding the smallest number of additional (relay) nodes so that the induced communication graph is 2-connected. The problem is NP -hard. In this paper we develop O(1)-approximation algorithms that find close to optimal solutions in time O((kn)) for achieving k-edge connectivity of n nodes. The worst case approximation guarantee is 10, but the algorithm produces solutions that are far better than this bound suggests. We also consider extensions to higher dimensions, and the scheme that we develop for points in the plane, yields a bound of 2dMST where dMST is the maximum degree of a minimum-degree Minimum Spanning Tree in d dimensions using Euclidean metrics. In addition, our methods extend with the same approximation guarantees to a generalization when the locations of relays are required to avoid certain polygonal regions (obstacles). We also prove that if the sensors are uniformly and identically distributed in a unit square, the expected number of relay nodes required goes to zero as the number of sensors goes to infinity.

In this work we introduce a new mathematical tool for optimization of routes, and topology design in wireless sensor networks. We introduce a vector field formulation that models communication in the network, and routing is performed in the direction of this vector field at every location of the network. The magnitude of the vector field at every location represents the density of amount of data that is being transited through that location. We define the total communication cost in the network as the integral of a quadratic form of the vector field over the network area. Our mathematical machinery is based on partial differential equations analogous to the Maxwell's equations in electrostatic theory. We use our vector field model to solve the optimization problem for the case in which there are multiple destinations (sinks) in the network. In order to optimally determine the destination for each sensor, we partition the network into areas, each corresponding to one of the destinations. We define a vector field, which is conservative, and hence it can be written as the gradient of a scalar function (also known as a potential function). Then we show that in the optimal assignment of the communication load of the network to the destinations, the value of that potential function should be equal at the locations of all the destinations. Also, we show that such an optimal partitioning of the network load among the destination is unique, and we give iterations to find the optimal solution

Wireless optical networks are being increasingly used in the backbone of hierarchical ad hoc networks. We consider the problem of minimizing the congestion in wireless optical (FSO) backbone networks by placing controllable relay nodes. We propose algorithms for placement of relays in the network under node interface constraints. The interfaces at each backbone node are limited, thus limiting the number of neighbors a node can have. We come up with algorithms to formulate the problem as a constrained knapsack problem, and propose algorithms to solve it. We use the mathematical technique of rollout to achieve better performance than the heuristics. We show by simulations that our algorithms significantly outperform some greedy algorithms, and a small number of relay nodes (when placed using our algorithms) can lead to a significant reduction in the congestion in the network

In this paper we consider the logical topology design and traffic grooming problem in multihop WDM networks. Usually, this problem is defined as an integer linear program (ILP) which is NP-complete. This justifies the use of heuristic algorithms. Many heuristic algorithms differ in the order of traffic demands considered for lightpath provisioning. We apply the technique of 'rollout' to systematically improve the performance of various heuristic algorithms by approximately optimizing the order in which traffic demands are considered. Through simulation experiments, we show that the performance of the rollout algorithms we derive are clearly superior not only to that of the initial heuristic algorithms on which they are based, but also to that of other well-known heuristic algorithms.

A new metric -average pairwise connectivity- is proposed to measure the fault tolerance of wireless multihop networks. Two types of random graphs, Poisson random graph and geometric random graph, are adopted to model wireless multihop networks and are used in experimental studies. By investigating the upper bound and lower bound of the average pairwise connectivity for different types of random graphs and the distribution of the difference between the upper bounds and lower bounds, we conclude that the average pairwise connectivity of wireless multihop networks can be very well approximated by its upper bound, a quantity that is easily computed.

In this paper, we propose a protection scheme to improve quality of service in a mobile backbone network with free space optical point-to-point links. We assume that the backbone nodes are mobile and with unpredictable movements, and the traffic from an ingress node is routed to its corresponding egress nodes in a multi-hop way. The QoS demanding applications are vulnerable to mobility imposed link failures in such networks. The first contribution of this work is to introduce a scheme in which a set of controllable protection agents are deployed to provide protection of the paths in the critical points of the network. The second contribution is using a Markov chain model to evaluate potential risk or potential reward of placing a protection agent in a specific place of the network. Our simulation experiments show that by using our scheme to strategically place a limited number of protection agents, a significant improvement in network performance is achieved.

We provide a routing framework for hybrid RF/FSO backbone networks, utilizing the characteristics of RF and free space optical (FSO) links. FSO links offer higher bandwidth and security, while RF links offer more reliability. We propose the concept of criticality index for different classes of traffic and providing obscuration-tolerant paths to the traffic in a weighted max-min fair way. We provide an optimal algorithm for the case where a traffic demand can be routed along multiple paths. The problem of routing unsplittable traffic is NP-hard, so we propose efficient heuristics for routing them. We do extensive simulations to demonstrate that our algorithms outperform the algorithms currently in use.

We consider a mobile backbone network with free space optical point-to-point links. Requests for aggregate bandwidth between pairs of backbone nodes arrive one-by-one, and a bandwidth guaranteed connection is established if there are sufficient network resources; otherwise, the request is rejected. In addition to the ordinary backbone nodes, there are a limited number of controllable mobile agents; these are nodes that may be located as desired to optimize the performance of the network. The specific problem we consider is that of determining the positions for the mobile agents to maximize the minimum max How over all source-destination pairs. We show that this problem is NP-hard. We then develop a heuristic algorithm to locate the agents based on the current network state. It is shown that by using the algorithm to strategically place a limited number of agents, a significant improvement in network performance can be achieved.

We propose a measurement-based routing algorithm to load balance intradomain traffic along multiple paths for multiple multicast sources. Multiple paths are established using application-layer overlaying. The proposed algorithm is able to converge under different network models, where each model reflects a different set of assumptions about the multicasting capabilities of the network. The algorithm is derived from simultaneous perturbation stochastic approximation and relies only on noisy estimates from measurements. Simulation results are presented to demonstrate the additional benefits obtained by incrementally increasing the multicasting capabilities.

We introduce a new approach for QoS provisioning in packet networks based on the notion of differentiated traffic engineering (DTE). We consider a single AS network capable of source based multi-path routing. We do not require sophisticated queuing or per-class scheduling at individual routers; instead, if a link is used to forward QoS sensitive packets, we maintain its utilization below a threshold. As a consequence, DTE eliminates the need for per-flow (IntServ) or per-class (DiffServ) packet processing tasks such as traffic classification, queueing, shaping, policing and scheduling in the core and hence poses a lower burden on the network management unit. Conversely, DTE utilizes network bandwidth much more efficiently than simple over-provisioning. In this paper, we propose a complete architecture and an algorithmic structure for DTE. We show that our scheme can be formulated as a non-convex optimization problem, and we present an optimal solution framework based on simulated annealing. We present a simulation-based performance evaluation of DTE, and compare our scheme to existing (gradient projection) methods.

We consider a mobile backbone network with free space optical point-to-point links. Each backbone node moves randomly but with low mobility, and future movement is not predictable. Requests for aggregate bandwidth between pairs of backbone nodes arrive one-by-one, and a bandwidth guaranteed connection is established if there are sufficient network resources (link bandwidth and node transceivers); otherwise, the request is rejected. Each request has a finite duration after which the bandwidth guaranteed connection is released. The connection may break due to the movement of the backbone nodes, thus necessitating a mechanism for connection restoration. We introduce a new type of mobile node, referred to as a controllable restoration agent, that may be used to restore broken connections. An online algorithm is developed to determine where to position the agents to provide maximum protection, given the locations of the nodes and the set of existing connections. It is shown that by using the algorithm to place a limited number of agents strategically, a significant improvement in network performance can be achieved.

In this paper, we introduce the notion of responsiveness for TCP aggregates and define it as the degree to which a TCP aggregate reduces its sending rate to the network as a response to packet drops. We define metrics that describe the responsiveness of TCP aggregates, and then we suggest two methods for determining the values of these quantities. The first method is based on a test in which we drop a few packets from the aggregate intentionally and measure the resulting rate decrease of that aggregate. This kind of test is not robust to multiple simultaneous tests performed at different routers. Extensions are done to make the test robust to multiple simultaneous tests by using ideas from the CDMA approach to multiple access channels in communication theory. Then we use these methods to perform congestion control. A distinguishing feature of our congestion control scheme is that it maintains a degree of fairness among different aggregates.

In this paper we introduce a novel approach for the routing problem in wireless ad hoc networks. Our approach is based on the analogy of the routing problem to the distribution of electric field in a physical media with a given density of charges. We show that the throughput can be significantly increased by choosing routes in such a way that the traffic is spread as uniformly as possible throughout the network. Achieving this uniform spreading requires solution of a set of partial differential equations similar to Maxwell's equations in the electrostatic theory. While the main focus in the paper is on the case in which many sources communicate with a single destination, extension to the case of multiple destinations is also described.

We consider a wireless backbone network with free space optical point-to-point links. Each backbone node has a limited number of transceivers with which to establish links to neighbors. Requests for aggregate bandwidth between pairs of backbone nodes arrive one-by-one and future demands are unknown. When a demand arrives, a bandwidth guaranteed path is established between the source and destination backbone nodes. Each time a path is established, it appropriates resources-link bandwidth and transceivers-that might be needed for future demands. The problem we consider is that of determining how to choose the bandwidth guaranteed paths in order to minimize the likelihood that future demands will be rejected due to lack of resources. The algorithm we propose is distinguished by its taking into account the potential interference with future demands caused by the reduction of the number of available transceivers when new links are established. Through simulations, we demonstrate that the performance of the new algorithm is superior to existing alternatives.

We consider algorithms for the logical topology design and traffic grooming problem in WDM networks with router interface constraints as well as optical constraints. The optical constraints include restricted transmission range due to optical impairments as well as limits on the number of available wavelengths. We formulate this problem as an integer linear program which is NP-complete. We then introduce heuristic algorithms which use a graphical modeling tool called the virtual neighbor graph and add lightpaths sequentially. The best performing heuristic uses a so-called resource efficiency factor to determine the order in which paths are provisioned for the traffic demands. By giving priority to demands that can be routed over paths that make efficient use of network resources, it is able to achieve good performance both in terms of weighted hop count and network throughput. For finding optimal multi-hop paths sequentially, we introduce interface constraint shortest path problem and solve it using minimum weight perfect matching.

We propose a new architecture for efficient network monitoring and measurements in a traditional IP network. This new architecture enables establishment of multiple paths (tunnels) between source-destination pairs without having to modify the underlying routing protocol(s). Based on the proposed architecture we propose a measurement-based multipath routing algorithm derived from simultaneous perturbation stochastic approximation. The proposed algorithm does not assume that the gradient of analytical cost function is known to the algorithm, but rather relies on noisy estimates from measurements. Using the analytical model presented in the paper we prove the convergence of the algorithm to the optimal solution. Simulation results are presented to demonstrate the advantages of the proposed algorithm under a variety of network scenarios. A comparative study with an existing optimal routing algorithm, MATE, is also provided.

In this work, we investigate flow migration as a mechanism to sustain QoS to network users during short-term overloads in the context of an MPLS IP network. We experiment with three different control techniques: static long-term optimal mapping of flows to LSPs; on-line locally optimal mapping of flows to LSPs at flow set-up time; and dynamic flow migration in response to transient congestion. These techniques are applicable over different timescales, have different run-time overheads, and require different levels of monitoring and control software inside the network. We present results both from detailed simulations and a complete implementation using software IP routers. We use voice-over-IP as our test application, and show that if end-to-end quality is to be maintained during short unpredictable bursts of high load, then a fast-timescale control such as migration is required.

In this paper we investigate single- and multipath logical topology design and traffic grooming algorithms. Since the problem of the optimal logical topology design for all traffic demands is NP-complete, we design a logical topology by sequentially constructing the shortest path for one source-destination pair at a time. In the single path case, the demand for each source-destination pair must be routed on a single path. In the multipath case, if it is not feasible to route a demand on a single path, the traffic demand is divided into multiple subdemands and a path is provided for each subdemand. Each path is a locally optimized path in the sense that there are no other paths with less hop count that may be constructed from existing links and newly created links. We propose heuristic algorithms for logical topology design and traffic grooming in both the single path and multipath cases. The performance of these algorithms in terms of weighted hop count and throughput is evaluated using the GLASS/SSF simulator. The results indicate that a proposed single path algorithm outperforms other known algorithms in terms of weighted hop count and throughput. Also, we observed that multipath algorithms improve network throughput and a multipath algorithm with widest-shortest paths reduces the weighted hop count compared to single path algorithms.

Large networks relying on real-time processing can be driven into unstable modes of operation (e.g., routing system failures, routing flaps, congestion and deadlock scenarios, system crash chain reactions, etc.). In the past, unintentional system faults have led to frame relay networks, SS7 signaling networks, and PSTNs going into unstable modes that have led to major service disruptions. A serious concern is that a malicious party could induce similar instabilities. The vulnerability of a network to instabilities may be due to unrecognized design flaws or hidden software bugs. Since these details are not known in advance, effective control mechanisms tailored to the specifics of the vulnerability are virtually impossible to achieve. However, it is our contention that there are a limited number of "generic propagation mechanisms" that enable these network instabilities to occur. By enumerating these propagation mechanisms and designing network management and control mechanisms to mitigate them, it would be possible to stabilize networks against malicious attack even when the details of the network vulnerability being exploited are unknown. We focus on a single example of a generic propagation mechanism that can occur in IP and ATM networks using link state routing protocols. The propagation mechanism is overload propagation in the control plane caused by excessive route updates. Network management and control mechanisms for mitigating this propagation mechanism are developed and validated through simulation of both the control and data planes.

There is great interest in exploring SNMP/TCP in addition to the current use of SNMP/UDP due to performance benefits for bulk transfer as well as to simplify management applications. If SNMP is implemented over TCP, then TLS is a natural choice for security. However, it must be demonstrated that the additional overhead associated with TLS is not excessive. We show this by implementing SNMP on a TLS/TCP base and measuring its performance experimentally. The results indicate that the overhead is not excessive; consequently SNMP/TLS/TCP appears to be a viable option for network management.

A method is presented in order to construct a smooth obstacle-free path amidst a finite number of disjoint disk-shaped obstacles for mobile robot navigation. The first step is to assign artificial potential functions to each obstacle and the goal. Then, the gradient flow associated with the weighted sum of the above functions generates the desired path. The procedure does not require complete prior knowledge of the positions of the obstacles, as long as they can be detected and approximated by disjoint disks. The algorithm presented represents a computationally simple way to construct paths and a systematic method of encoding the geometric data about the environment into a smooth vector field, which is used for mobile robot navigation.>