No description available.

No description available.

No description available.

No description available.

No description available.

Interference in ad hoc wireless networks causes the performance of traditional networking protocols to suffer. However, some user applications in ad hoc networks demand high throughput and low end-user delay. In the literature, the backpressure policy, i.e. queue backlog differential-based joint routing and scheduling, is known to be throughput-optimal with robust support for traffic load fluctuations \cite{Tssailus92}. Unfortunately, many backpressure-based algorithms cannot be implemented due to high end-user delay, inaccurate assumptions for interference, and high control overhead in distributed scenarios. We develop new backpressure based approaches to address these issues. We first propose a heuristic packet forwarding scheme that solves the issue of high end-user delay and still provides near-optimal throughput. Next we develop a novel interference model that provides simple yet accurate interference relationships among users. Such a model is helpful in designing a simple backpressure scheduling algorithm that does not violate realistic interference constraints. Finally we develop distributed backpressure algorithms based on our proposed ideas. Our distributed algorithms provide throughput performance close to the optimal and have low control overhead and simple implementation. / Master of Science

The industrial gas industry represents a multi-billion dollar global market and provides essential product to manufacturing and service organizations that drive the global economy. In this dissertation, we focus on improving distribution efficiency in the industrial gas industry by addressing the strategic level problem of bulk tank allocation (BTA) while considering the effects of important operational issues. The BTA problem determines the preferred size of bulk tanks to assign to customer sites to minimize recurring gas distribution costs and initial tank installation costs. The BTA problem has a unique structure which includes a resource allocation problem and an underlying vehicle routing problem with split deliveries. In this dissertation, we provide an exact solution approach that solves the BTA problem to optimality and recommends tank allocations, provides a set of delivery routes, and determines delivery amounts to customers on each delivery route within reasonable computational time. The exact solution approach is based on a branch-and-price algorithm that solves problem instances with up to 40 customers in reasonable computational time. Due to the complexity of the problem and the size of industry representative problems, the solution approaches published in the literature rely on heuristics that require a set of potential routes as input. In this research, we investigate and compare three alternative route generation algorithms using data sets from an industry partner. When comparing the routes generation algorithms, a sweep-based heuristic was the preferred heuristic for the data sets evaluated. The existing BTA solution approaches in the literature also assume a single bulk tank can be allocated at each customer site. While this assumption is valid for some customers due to space limitations, other customer sites may have the capability to accommodate multiple tanks. We propose two alternative mathematical models to explore the possibility and potential benefits of allocating multiple tanks at designated customer site that have the capacity to accommodate more than one tank. In a case study with 20 customers, allowing multiple tank allocation yield 13% reduction in total costs. In practice, industrial gas customer demands frequently vary by time period. Thus, it is important to allocate tanks to effectively accommodate time varying demand. Therefore, we develop a bulk tank allocation model for time varying demand (BTATVD) which captures changing demands by period for each customer. Adding this time dimension increases complexity. Therefore, we present three decomposition-based solution approaches. In the first two approaches, the problem is decomposed and a restricted master problem is solved. For the third approach, a two phase periodically restricting heuristic approach is developed. We evaluate the solution approaches using data sets provided by an industrial partner and solve the problem instances with up to 200 customers. The results yield approximately 10% in total savings and 20% in distribution cost savings over a 7 year time horizon. The results of this research provide effective approaches to address a variety of distribution issues faced by the industrial gas industry. The case study results demonstrate the potential improvements for distribution efficiency. / Ph. D.

Reachability routing is a newly emerging paradigm in networking, where the goal is to determine all paths between a sender and a receiver. It is becoming relevant with the changing dynamics of the Internet and the emergence of low-bandwidth wireless/ad hoc networks. This thesis presents the case for reinforcement learning (RL) as the framework of choice to realize reachability routing, within the confines of the current Internet backbone infrastructure. The setting of the reinforcement learning problem offers several advantages, including loop resolution, multi-path forwarding capability, cost-sensitive routing, and minimizing state overhead, while maintaining the incremental spirit of the current backbone routing algorithms. We present the design and implementation of a new reachability algorithm that uses a model-based approach to achieve cost-sensitive multi-path forwarding. Performance assessment of the algorithm in various troublesome topologies shows consistently superior performance over classical reinforcement learning algorithms. Evaluations of the algorithm based on different criteria on many types of randomly generated networks as well as realistic topologies are presented. / Master of Science

Uncovering the metrics and procedures employed by an autonomous networking system is an important problem with applications in instrumentation, traffic engineering, and game-theoretic studies of multi-agent environments. This thesis presents a method for utilizing inverse reinforcement learning (IRL)techniques for the purpose of discovering a composite metric used by a dynamic routing algorithm on an Internet Protocol (IP) network. The network and routing algorithm are modeled as a reinforcement learning (RL) agent and a Markov decision process (MDP). The problem of routing metric discovery is then posed as a problem of recovering the reward function, given observed optimal behavior. We show that this approach is empirically suited for determining the relative contributions of factors that constitute a composite metric. Experimental results for many classes of randomly generated networks are presented. / Master of Science

We present an online distributed algorithm, the Causation Logging Algorithm (CLA), in which Autonomous Systems (ASes) in the Internet individually report route oscillations/flaps they experience to a central Internet Routing Registry (IRR). The IRR aggregates these reports and may observe what we call causation chains where each node on the chain caused a route flap at the next node along the chain. A chain may also have a causation cycle. The type of an observed causation chain/cycle allows the IRR to infer the underlying policy routing configuration (i.e. the system of economic relationships and constraints on route/path preferences). Our algorithm is based on a formal policy routing model that captures the propagation dynamics of route flaps under arbitrary changes in topology or path preferences. We derive invariant properties of causation chains/cycles for ASes which conform to economic relationships based on the popular Gao-Rexford model. The Gao-Rexford model is known to be safe in the sense that the system always converges to a stable set of paths under static conditions. Our CLA algorithm recovers the type/property of an observed causation chain of an underlying system and determines whether it conforms to the safe economic Gao-Rexford model. Causes for nonconformity can be diagnosed by comparing the properties of the causation chains with those predicted from different variants of the Gao-Rexford model.