This thesis develops quantitative methods which incorporate transportation modeling for tactical and operational home health logistics planning problems. We define home health nurse routing and scheduling (HHNRS) problems, which are dynamic periodic routing and scheduling problems with fixed appointment times, where a set of patients must be visited by a home health nurse according to a prescribed weekly frequency for a prescribed number of consecutive weeks during a planning horizon, and each patient visit must be assigned an appointment time belonging to an allowable menu of equally-spaced times. Patient requests are revealed incrementally, and appointment time selections must be made without knowledge of future requests. First, a static problem variant is studied to understand the impact of fixed appointment times on routing and scheduling decisions, independent of other complicating factors in the HHNRS problem. The costs of offering fixed appointment times are quantified, and purely distance-based heuristics are shown to have potential limitations for appointment time problems unless proposed arc cost transformations are used. Building on this result, a new rolling horizon capacity-based heuristic is developed for HHNRS problems. The heuristic considers interactions between travel times, service times, and the fixed appointment time menu when inserting appointments for currently revealed patient requests into partial nurse schedules. The heuristic is shown to outperform a distance-based heuristic on metrics which emphasize meeting as much patient demand as possible. The home health nurse districting (HHND) problem is a tactical planning problem which influences HHNRS problem solution quality. A set of geographic zones must be partitioned into districts to be served by home health nurses, such that workload is balanced across districts and nurse travel is minimized. A set partitioning model for HHND is formulated and a column generation heuristic is developed which integrates ideas from optimization and local search. Methods for estimating district travel and workload are developed and implemented within the heuristic, which outperforms local search on test instances.

Traditional routing protocols select paths based on static link weights and converge to new paths only when there is an outright reachability failure (such as a link or router failure). This design allows routing scale to hundreds of thousands of nodes, but it comes at the cost of functionality: routing provides only simple, single path connectivity. Networked applications in the wide-area, enterprise, and data center can all benefit from network protocols that allow traffic to be sent over multiple routes en route to a destination. This ability, also called multipath routing, has other significant benefits over single-path routing, such as more efficiently using network resources and recovering more quickly from network disruptions. This dissertation explores the design of an architecture for path selection in the network and proposes a "narrow waist" interface for networks to expose choice in routing traffic to end systems. Because most networks are also business entities, and are sensitive to the cost of routing traffic in their network, this dissertation also develops a framework for exposing paths based on their cost. For this purpose, this dissertation develops a cost model for routing traffic in a network. In particular, this dissertation presents the following contributions: * Design of path bits, a "narrow waist" for multipath routing. Our work ties a large number of multipath routing proposals by creating an interface (path bits) for decoupling the multipath routing protocols implemented by the network and end systems (or other network elements) making a choice for path selection. Path bits permit simple, scalable, and efficient implementations of multipath routing protocols in the network that still provide enough expressiveness for end systems to select alternate paths. We demonstrate that our interface is flexible and leads to efficient network implementations by building prototype implementations on different hardware and software platforms. * Design of path splicing, a multipath routing scheme. We develop, path splicing, a multipath routing technique, which uses random perturbations from the shortest path to create exponentially large number of paths with only a linear increase in state in a network. We also develop a simple interface to enable end systems to make path selection decisions. We present various deployment paths for implementing path splicing in both intradomain and interdomain routing on the Internet. * Design of low cost path-selection framework for a network. Network operators and end systems can have conflicting goals, where the network operators are concerned with saving cost and reducing traffic uncertainty; and end systems favor better performing paths. Exposing choice of routing in the network can thus, create a tension between the network operators and the end systems. We propose a path-selection framework where end systems make path selection decisions based on path performance and networks expose paths to end systems based on their cost to the network. This thesis presents a cost model for routing traffic in a network to enable network operators to reason about "what-if " scenarios and routing traffic on their network.

In the wake of major disasters, the failure of existing communications infrastructure and the subsequent lack of an effective communication solution results in increased risks, inefficiencies, damage and casualties. Currently available options such as satellite communication are expensive and have limited functionality. A robust communication solution should be affordable, easy to deploy, require little infrastructure, consume little power and facilitate Internet access. Researchers have long proposed the use of ad hoc wireless networks for such scenarios. However such networks have so far failed to create any impact, primarily because they are unable to handle network transience and have usability constraints such as static topologies and dependence on specific platforms. LifeNet is a WiFi-based ad hoc data communication solution designed for use in highly transient environments. After presenting the motivation, design principles and key insights from prior literature, the dissertation introduces a new routing metric called Reachability and a new routing protocol based on it, called Flexible Routing. Roughly speaking, reachability measures the end-to-end multi-path probability that a packet transmitted by a source reaches its final destination. Using experimental results, it is shown that even with high transience, the reachability metric - (1) accurately captures the effects of transience (2) provides a compact and eventually consistent global network view at individual nodes, (3) is easy to calculate and maintain and (4) captures availability. Flexible Routing trades throughput for availability and fault-tolerance and ensures successful packet delivery under varying degrees of transience. With the intent of deploying LifeNet on field we have been continuously interacting with field partners, one of which is Tata Institute of Social Sciences India. We have refined LifeNet iteratively refined base on their feedback. I conclude the thesis with lessons learned from our field trips so far and deployment plans for the near future.

<p>Network on Chip (NoC) has emerged as a competitive and efficient communication infrastructure for the core based design of System on Chip. Resource (core), router and interface between router and core are the three main parts of a NoC. Each core communicates with the network through the interface, also called Resource Network Interface (RNI). One approach to speed up the design at NoC based systems is to develop standardized RNI. Design of RNI depends to some extent on the type of routing technique used in NoC. Control of route decision base the categorization of source and distributed routing algorithms. In source routing a complete path to the destination is provided in the packet header at the source, whereas in distributed routing, the path is dynamically computed in routers as the packet moves through the network. Buffering, flitization, deflitization and transfer of data from core to router and vice versa, are common responsibilities of RNI in both types of routing. In source routing, RNI has an extra functionality of storing complete paths to all destinations in tables, extracting path to reach a desired destination and adding it in the header flit. In this thesis, we have made an effort towards designing and prototyping a standardized and efficient RNI for both source and distributed routing. VHDL is used as a design language and prototyping of both types RNI has been carried out on Altera DE2 FPGA board. Testing of RNI was conducted by using Nios II soft core. Simulation results show that the best case flit latency, for both types RNI is 4 clock cycles. RNI design is also resource efficient because it consumes only 2% of the available resources on the target platform.</p>

No description available.

Wireless Mesh Network (WMN) is an emerging technology that is gaining importance among traditional wireless communication systems. However, WMNs are particularly vulnerable to external and insider attacks due to their inherent attributes such as open communication medium and decentralized architecture. In this research, we propose a complete distributed and cooperative intrusion detection system for efficient and effective detection of WMN attacks in real-time. Our intrusion detection mechanism is based on reliable exchange of network events and active cooperation between the participating nodes. In our distributed approach, Intrusion Detection Systems (IDSs) are independently placed at each mesh node to passively monitor the node routing behavior and concurrently monitor the neighborhood behavior. Based on that, we first implement a Routing Protocol Analyzer (RPA) that accuracy generates Routing Events from the observed traffic, which are then processed by the own node and exchanged between neighboring nodes. Second, we propose a practical Distributed Intrusion Detection Engine (DIDE) component, which periodically calculates accurate Misbehaving Metrics by making use of the generated Routing Events and pre-defined Routing Constraints that are extracted from the protocol behavior. Third, we propose a Cooperative Consensus Mechanism (CCM), which is triggered among the neighboring nodes if any malicious behavior is detected. The CCM module analyzes the Misbehaving Metrics and shares Intrusion Detection Results among the neighbors to track down the source of intrusion. To validate our research, we implemented the distributed intrusion detection solution using a virtualized mesh network platform composed of virtual machines (VMs) interconnected. We also implemented several routing attacks to evaluate the performance of the intrusion detection mechanisms

The popularity of ubiquitous Internet services has spurred the fast growth of wireless communications by launching data hungry multimedia applications to mobile devices. Powered by spectrum agile cognitive radios, the newly emerged cognitive radio networks (CRN) are proposed to provision the efficient spectrum reuse to improve spectrum utilization. Unlicensed users in CRN, or secondary users (SUs), access the temporarily idle channels in a secondary and opportunistic fashion while preventing harmful interference to licensed primary users (PUs). To effectively detect and exploit the spectrum access opportunities released from a wide spectrum, the heterogeneous wireless channel characteristics and the underlying prioritized spectrum reuse features need to be considered in the protocol design and resource management schemes in CRN, which plays a critical role in unlicensed spectrum sharing among multiple users. The purpose of this dissertation is to address the challenges of utilizing heterogeneous wireless channels in CRN by its intrinsic dynamic and diverse natures, and build the efficient, scalable and, more importantly, practical dynamic spectrum access mechanisms to enable the cost-effective transmissions for unlicensed users. Note that the spectrum access opportunities exhibit the diversity in the time/frequency/space domain, secondary transmission schemes typically follow three design principles including 1) utilizing local free channels within short transmission range, 2) cooperative and opportunistic transmissions, and 3) effectively coordinating transmissions in varying bandwidth. The entire research work in this dissertation casts a systematic view to address these principles in the design of the routing protocols, medium access control (MAC) protocols and radio resource management schemes in CRN. Specifically, as spectrum access opportunities usually have small spatial footprints, SUs only communicate with the nearby nodes in a small area. Thus, multi-hop transmissions in CRN are considered in this dissertation to enable the connections between any unlicensed users in the network. CRN typically consist of intermittent links of varying bandwidth so that the decision of routing is closely related with the spectrum sensing and sharing operations in the lower layers. An efficient opportunistic cognitive routing (OCR) scheme is proposed in which the forwarding decision at each hop is made by jointly considering physical characteristics of spectrum bands and diverse activities of PUs in each single band. Such discussion on spectrum aware routing continues coupled with the sensing selection and contention among multiple relay candidates in a multi-channel multi-hop scenario. An SU selects the next hop relay and the working channel based upon location information and channel usage statistics with instant link quality feedbacks. By evaluating the performance of the routing protocol and the joint channel and route selection algorithm with extensive simulations, we determine the optimal channel and relay combination with reduced searching complexity and improved spectrum utilization. Besides, we investigate the medium access control (MAC) protocol design in support of multimedia applications in CRN. To satisfy the quality of service (QoS) requirements of heterogeneous applications for SUs, such as voice, video, and data, channels are selected to probe for appropriate spectrum opportunities based on the characteristics and QoS demands of the traffic along with the statistics of channel usage patterns. We propose a QoS-aware MAC protocol for multi-channel single hop scenario where each single SU distributedly determines a set of channels for sensing and data transmission to satisfy QoS requirements. By analytical model and simulations, we determine the service differentiation parameters to provision multiple levels of QoS. We further extend our discussion of dynamic resource management to a more practical deployment case. We apply the experiences and skills learnt from cognitive radio study to cellular communications. In heterogeneous cellular networks, small cells are deployed in macrocells to enhance link quality, extend network coverage and offload traffic. As different cells focus on their own operation utilities, the optimization of the total system performance can be analogue to the game between PUs and SUs in CRN. However, there are unique challenges and operation features in such case. We first present challenging issues including interference management, network coordination, and interworking between cells in a tiered cellular infrastructure. We then propose an adaptive resource management framework to improve spectrum utilization and mitigate the co-channel interference between macrocells and small cells. A game-theory-based approach is introduced to handle power control issues under constrained control bandwidth and limited end user capability. The inter-cell interference is mitigated based upon orthogonal transmissions and strict protection for macrocell users. The research results in the dissertation can provide insightful lights on flexible network deployment and dynamic spectrum access for prioritized spectrum reuse in modern wireless systems. The protocols and algorithms developed in each topic, respectively, have shown practical and efficient solutions to build and optimize CRN.

Within the wide scope of logistics management,transportation plays a central role and is a crucialactivity in both production and service industry.Among others, it allows for the timely distributionof goods and services between suppliers, productionunits, warehouses, retailers, and final customers.More specifically, Vehicle Routing Problems(VRPs) deal with the design of a set of minimal costroutes that serve the demand for goods orservices of a set of geographically spread customers,satisfying a group of operational constraints.While it was traditionally a static problem, recenttechnological advances provide organizations withthe right tools to manage their vehicle fleet in realtime. Nonetheless, these new technologies alsointroduce more complexity in fleet managementtasks, unveiling the need for decision support systemsdedicated to dynamic vehicle routing. In thiscontext, the contributions of this Ph.D. thesis arethreefold : (i) it presents a comprehensive reviewof the literature on dynamic vehicle routing ; (ii)it introduces flexible optimization frameworks thatcan cope with a wide variety of dynamic vehiclerouting problems ; (iii) it defines a new vehicle routingproblem with numerous applications.

The importance of communication is vital in wartime. The capability of having all the position information of the allied and enemy forces in a single Tactical Information Display System (TIDS), maintains a great advantage for deciding what to do before the enemy reacts. A Naval Information Distributing System (NIDS) is developed for building an effective communication infrastructure between the war ships. In the designed network, besides the mobile platforms (ships), some fixed platforms (land stations) are used to transfer the information coming from these mobile platforms to all the other platforms. To demonstrate the performance and effectiveness of the Naval Information Distribution System, a discrete event simulation model is developed on a Geographic Information System. The goal of this thesis is to describe and experimentally evaluate an effective and feasible information sharing and routing system for Navy.

Peer-to-peer (p2p) technology provides an excellent platform for the delivery of rich content and media that scales with the rapid growth of the Internet. This work presents a lookup service design and implementation that provides provable fault tolerance and operates in a cost-conscious manner over the Internet. <br><br> Using a distributed hash table (DHT) as a foundation, we propose a replica placement that improves object availability and reachability to implement a robust lookup service. We present a framework that describes tree-based routing DHTs and formally prove several properties for DHTs of this type. Specifically, we prove that our replica placement, which we call MaxDisjoint, creates a provable number of disjoint routes from any source node to a replica set. We evaluate this technique through simulation and demonstrate that it creates disjoint routes more effectively than existing replica placements. Furthermore, we show that disjoint routes have a marked impact on routing robustness, which we measure as the probability of lookup success. <br><br> To mitigate the costs incurred by multi-hop DHT routing, we develop an organization-based id assignment scheme that bounds the transit costs of prefix-matching routes. To further reduce costs, we use MaxDisjoint placement to create multiple routes of varying costs. This technique helps reduce cost in two ways: (1) replication may create local copies of an object that can be accessed at zero transit cost and (2) MaxDisjoint replication creates multiple, bounded cost, disjoint routes of which the minimal cost route can be used to resolve the lookup. We model the trade-off between the storage cost and routing cost benefit of replication to find the optimal degree to which an object should be replicated. We evaluate our approach using a lookup service implementation and show that it dramatically reduces cost over existing DHT implementations. Furthermore, we show that our technique can be used to manage objects of varying popularity in a manner that is more cost effective than caching. <br><br> By improving its robustness and cost effectiveness, we aim to increase the pervasiveness of p2p in practice and unlock the potential of this powerful technology.