Large-scale layer-2 Ethernet networks are needed for important future and current applications and services including: metro Ethernet, wide area Ethernet, data center networks, cyber-physical systems, and large data processing. However Ethernet bridging was designed for small local area networks and suffers scalability and resiliency problems for large networks. I will present the architecture and protocols of ROME, a layer-2 network designed to be backwards compatible with Ethernet and scalable to tens of thousands of switches and millions of end hosts. We first design a scalable greedy routing protocol, Multi-hop Delaunay Triangulation (MDT) routing, for delivery guarantee on any connectivity graph with arbitrary node coordinates. To achieve near-optimal routing path for greedy routing, we then present the first layer-2 virtual positioning protocol, Virtual Position on Delaunay (VPoD). We then design a stateless multicast protocol, to support group communication such as VLAN while improving switch memory scalability. To achieve efficient host discovery, we present a novel distributed hash table, Delaunay DHT (D²HT). ROME also includes routing and host discovery protocols for a hierarchical network. ROME protocols completely eliminate broadcast. Extensive experimental results show that ROME protocols are efficient and scalable to metropolitan size. Furthermore, ROME protocols are highly resilient to network dynamics. The routing latency of ROME is only slightly higher than shortest-path latency. / text

No description available.

In dynamic P2P networks, nodes join and depart from the system frequently, which partially damages the predefined P2P structure, and impairs the system performance such as basic lookup functionality. Therefore stabilization process has to be done to restore the logical topology. This paper presents an approach to relax the requirement on routing tables to provide provably better stability than fixed structured P2P systems. We propose a relaxed Chord that keeps the O(logN) number of hops for greedy lookup, but it requires less stabilization overhead. It allows a tradeoff between lookup efficiency and structure flexibility without adding any overhead to the system. In the relaxed routing structure, each routing entry ("finger") of the node is allowed to vary within a set of values. Each node only needs to keep a certain number of fingers that point to nodes in its anchor set. This relaxation reduces the burden of state management of the node. The relaxed routing scheme provides an alternative structure other than randomized P2P and deterministic P2P, by relaxing on finger selection. It provides good flexibility and therefore extends the system functioning time. / Singapore-MIT Alliance (SMA)

Doctor of Philosophy / Department of Mathematics / Nathan Albin / The concept of discrete $p$-modulus provides a general framework for understanding arbitrary families of objects on a graph. The $p$-modulus provides a sense of ``structure'' of the underlying graph, with different families of objects leading to different insight into the graph's structure. This dissertation builds on this idea, with an emphasis on the family of spanning trees and the underlying graph structure that spanning tree modulus exposes. This dissertation provides a review of the probabilistic interpretation of modulus. In the context of spanning trees, this interpretation rephrases modulus as the problem of choosing a probability mass function on the spanning trees so that two independent, identically distributed random spanning trees have expected overlap as small as possible. A theoretical lower bound on the expected overlap is shown. Graphs that attain this lower bound are called homogeneous and have the property that there exists a probability mass function that gives every edge equal likelihood to appear in a random tree. Moreover, any nonhomogeneous graph necessarily has a homogeneous subgraph (called a homogeneous core), which is shown to split the modulus problem into two smaller subproblems through a process called deflation. Spanning tree modulus and the process of deflation establish a type of hierarchical structure in the underlying graph that is similar to the concept of core-periphery structure found in the literature. Using this, one can see an alternative way of decomposing a graph into its hierarchical community components using homogeneous cores and a related concept: minimum feasible partitions. This dissertation also introduces a simple greedy algorithm for computing the spanning tree modulus that utilizes any efficient algorithm for finding minimum spanning trees. A theoretical proof of the convergence rate is provided, along with computational examples.

Automated Guided Vehicles hav gained much attention in the industry especially with relevance to container handling at the seaports.

In this thesis, I survey 11 approximation algorithms for unweighted set cover problem. I have also implemented the three algorithms and created a software library that stores the code I have written. The algorithms I survey are: 1. Johnson's standard greedy; 2. f-frequency greedy; 3. Goldsmidt, Hochbaum and Yu's modified greedy; 4. Halldorsson's local optimization; 5. Dur and Furer semi local optimization; 6. Asaf Levin's improvement to Dur and Furer; 7. Simple rounding; 8. Randomized rounding; 9. LP duality; 10. Primal-dual schema; and 11. Network flow technique. Most of the algorithms surveyed are refinements of standard greedy algorithm.

Indiana University-Purdue University Indianapolis (IUPUI) / This thesis presents a method to accurately determine the location and amount of pedestrians detected by different vehicles equipped with a Pedestrian Autonomous Emergency Braking (PAEB) system, taking into consideration the inherent inaccuracy of the pedestrian sensing from these vehicles. In the thesis, a mathematical model of the pedestrian information generated by the PAEB system in the V2V network is developed. The Greedy-Medoids clustering algorithm and constrained hierarchical clustering are applied to recognize and reconstruct actual pedestrians, which enables a subject vehicle to approximate the number of the pedestrians and their estimated locations from a larger number of pedestrian alert messages received from many nearby vehicles through the V2V network and the subject vehicle itself. The proposed methods determines the possible number of actual pedestrians by grouping the nearby pedestrians information broadcasted by different vehicles and considers them as one pedestrian. Computer simulations illustrate the effectiveness and applicability of the proposed methods. The results are more integrated and accurate information for vehicle Autonomous Emergency Braking (AEB) systems to make better decisions earlier to avoid crashing into pedestrians.

No description available.

No description available.

No description available.