Given a geometric graph G = (V,E), where V is the set of vertices and E is the set of edges and a source-target pair {s,t} is a subset of V, a local geometric routing algorithm seeks a route from s to t using only local neighborhood relationships. This thesis proposes a local geometric routing algorithm that uses only a single state bit as message overhead and guarantees delivery of messages in three different classes of edge-augmented planar graphs: convex subdivisions, quasi planar convex subdivisions (allow some augmented edges on a spanning convex subdivision) and 2-augmented triangulations (allow some augmented edges on a spanning triangulation). The proposed algorithm is origin oblivious (does not require the knowledge of the origin vertex s) and predecessor oblivious (does not require the knowledge of the predecessor vertex).

Given a geometric graph G = (V,E), where V is the set of vertices and E is the set of edges and a source-target pair {s,t} is a subset of V, a local geometric routing algorithm seeks a route from s to t using only local neighborhood relationships. This thesis proposes a local geometric routing algorithm that uses only a single state bit as message overhead and guarantees delivery of messages in three different classes of edge-augmented planar graphs: convex subdivisions, quasi planar convex subdivisions (allow some augmented edges on a spanning convex subdivision) and 2-augmented triangulations (allow some augmented edges on a spanning triangulation). The proposed algorithm is origin oblivious (does not require the knowledge of the origin vertex s) and predecessor oblivious (does not require the knowledge of the predecessor vertex).

In this article, we study the school bus routing and scheduling problem with transfers arising in the field of nonperiodic public transportation systems. It deals with the transportation of pupils from home to their school in the morning taking the possibility that pupils may change buses into account. Allowing transfers has several consequences. On the one hand, it allows more flexibility in the bus network structure and can, therefore, help to reduce operating costs. On the other hand, transfers have an impact on the service level: the perceived service quality is lower due to the existence of transfers; however, at the same time, user ride times may be reduced and, thus, transfers may also have a positive impact on service quality. The main objective is the minimization of the total operating costs. We develop a heuristic solution framework to solve this problem and compare it with two solution concepts that do not consider transfers. The impact of transfers on the service level in terms of time loss (or user ride time) and the number of transfers is analyzed. Our results show that allowing transfers reduces total operating costs significantly while average and maximum user ride times are comparable to solutions without transfers. (authors' abstract)

Routing metrics are important mechanisms to adjust routing protocols' path selection according to the needs of a network system. However, if a routing metric design does not correctly match a particular routing protocol, the protocol may not be able to find an optimal path; routing loops can be produced as well. Thus, the compatibility between routing metrics and routing protocols is increasingly significant with the widespread deployment of wired and wireless networks. However, it is usually difficult to tell whether a routing metric can be perfectly applied to a particular routing protocol. Manually enumerating all possible test cases is very challenging and often infeasible. Therefore, it is highly desirable to have an automatic solution so that one can avoid putting an incompatible combination of routing metric and protocol into use. In this thesis, the above issue has been addressed by developing two automated checking systems for examining the compatibility between real world routing metric and protocol implementations. The automatic routing protocol checking system assumes that some properties of routing metrics are given and the system's job is to check if a new routing protocol is able to achieve optimal, consistent and loop- free routing when it is combined with metrics that hold the given metric properties. In contrast to the protocol checking system, the automatic routing metric checking system assumes that a routing protocol is given and the checking system needs to verify if a new metric implementation will be able to work with this protocol. Experiments have been conducted to verify the correctness of both protocol and metric checking systems. / Master of Science

In semiconductor manufacturing, automated material handling systems (AMHSs) transport wafers through a complex re-entrant manufacturing process. In some systems, Overhead Hoist Transport (OHT) vehicles move throughout the facility on a ceiling-mounted track system, delivering wafers to machines and storage locations. To improve efficiency in such systems, this thesis proposes an adaptive dynamic routing approach that allows the system to self-regulate, reducing steady-state travel times by 4-6% and avoiding excessive congestion and deadlock. Our approach allows vehicles to be rerouted while in progress in response to changes in the location and severity of congestion as measured by edge traversal time estimates updated via exponential smoothing. Our proposed method is efficient enough to be used in a large system where several routing decisions are made each second. We also consider how the effectiveness of a AMHS layout differs between static and dynamic routing. We demonstrate that dynamic routing significantly reduces sensitivity to shortcut placement and allows an eight-fold increase in the number of shortcuts along the center loop. This reduces travel times by an additional 24%. To demonstrate the effectiveness of our proposed routing approach, we use a high-fidelity simulation of vehicle movement. To test the impact of routing methods on layout effectiveness, we developed an associated Excel-based automated layout generation tool that allows the efficient generation of thousands of candidate layouts. The user selects from among a set of modular templates to create a design and all simulation files are generated with the click of a button.

ITC/USA 2015 Conference Proceedings / The Fifty-First Annual International Telemetering Conference and Technical Exhibition / October 26-29, 2015 / Bally's Hotel & Convention Center, Las Vegas, NV / IP-telemetry radios are being connected to existing ground networks, thereby integrating the air and ground. While this provides full connection to Test Article (TA) networks, the mobility of TAs and the transient nature of test missions leave the overall experience feeling less than "real" networks. We describe a toolset that extends the capabilities of integrated IP-telemetry and range networks through specialized routing techniques focused on mission-based data delivery needs. The toolset provides a configurable capability enabling packet-based best source selection, firewalling, multicasting, and QoS enforcement across the range on a per program basis. The building blocks of the toolset allow for the creation of virtualized network components that are mission-based rather than infrastructure and enables seamless network operation with network telemetry, giving mission personnel the ability to specialize the network for their needs without depending upon the range IT department.

ITC/USA 2011 Conference Proceedings / The Forty-Seventh Annual International Telemetering Conference and Technical Exhibition / October 24-27, 2011 / Bally's Las Vegas, Las Vegas, Nevada / One of the core philosophies of the integrated Network Enhanced Telemetry (iNET) project is to leverage standard networking technologies whenever possible to both reduce development cost and to allow standard networking applications to function. This also provides the best long-term scalability to new unforeseen applications, much as the Internet has grown through its open standards. Unfortunately, the radio frequency (RF) channel characteristics do not fully lend themselves to the typical physical layer approaches utilized by IP technologies. As such, the iNET program has developed a specialized communication link management control. But, combining this specialized link management approach with the standardized IP infrastructure on the range and test article provides some challenges. The program has chosen a method to encapsulate the special concepts within a set of components that together (at their boundaries) form a classic router. Construction of this router is quite unique in that portions of it are geographically separate: antenna sites, test article, and mission control room. This paper describes the construction of what the program calls a "virtual router" and explains the performance issues that required it.

No description available.

No description available.

The United States Navy Meteorology and Oceanography (METOC) community routes ships for weather evasion using advanced meteorological modeling and satellite data, but lacks a tool to enable fewer ship routers to make better routing decisions faster. Limited resources and rising costs are impacting the frequency and duration of current naval operations. The Commander, Naval Meteorology and Oceanography Command has ordered the community to find efficiencies and automation possibilities in order to meet lower manning levels, reduce waste, and increase savings. Outside of the Navy, Ocean Systems Incorporated in Alameda, CA developed the Ship Tracking and Routing System (STARS) software package to calculate optimum sea routes based on weather model data. However, METOC ship routers are reluctant to adopt this complex software. To help solve this, we modeled Optimum Track Ship Routing (OTSR) for U.S. Navy warships using a network graph of the Western Pacific Ocean. A binary heap version of Dijkstra's algorithm determines the optimum route given model generated wind and seas input. We test the model against recent weather data to verify the model's performance, and to historical divert route recommendations in order to validate against routes developed by OTSR personnel.