Between Dec 19, 2024 and Jan 2, 2025, datasets can be submitted to DRUM but will not be processed until after the break. Staff will not be available to answer email during this period, and will not be able to provide DOIs until after Jan 2. If you are in need of a DOI during this period, consider Dryad or OpenICPSR. Submission responses to the UDC may also be delayed during this time.

Browsing by Author "Yu, Yinzhe"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Enhancing location service scalability with HIGH-GRADE
    (2004-01-12) Yu, Yinzhe; Lu, Guor-Huar; Zhang, Zhi-Li
    Location-based routing significantly reduces routing overheads in ad hoc networks by utilizing position information of mobile nodes in making forwarding decisions. Location service is therefore critical to location-based routing, the scalability of which hinges largely on the location query and update overheads of such service. Although several location service schemes have been proposed, most of them focus only on one or two aspects of the scalability in their performance evaluation, and a comprehensive comparative study is missing. In this paper, we first explore the design space of location service for location-based ad hoc routing and discuss the tradeoffs involved in various design choices. We then propose HIGH-GRADE, a new location service scheme that employs a multilevel hierarchical location server structure and a multi-grained location information organization. We develop a uniform theoretical framework to analyze HIGH-GRADE and four other existing schemes in terms of three metrics: location maintenance cost, location query cost, and storage requirement cost. With both theoretical analysis and simulation experiments, we show that HIGH-GRADE demonstrates superior scalability, especially when a localized data traffic pattern is assumed, in which case all the three scalability metrics are bound byO(v log N).
  • Thumbnail Image
    Item
    Leopard: A Location-Aware Peer-To-Peer System With No Hot Spot
    (2004-07-27) Yu, Yinzhe; Lee, Sanghwan; Zhang, Zhi-Li
    We propose an alternative approach for building structured peer-to-peer systems. The major design objectives are i) to explicitly incorporate locality information into the system to minimize routing stretch in object look-up service, and ii) to inherently better cope with the ``flash crowd'' problem. Unlike the standard DHT-based approach, where both objects and nodes are assigned a randomly hashed id in the same id space, we separate the object id space from the node space. More specifically, each object is assigned an id in an object id space, whereas each node is assigned a coordinate in a coordinate system (referred to as the node geo space) reflects the ``geographical proximity'' of nodes. The object id space and the node geo space are ``weaved'' together via a novel hashing technique called {em geographically-scoped hashing}. Using this approach, we develop a structured P2P look-up system called Leopard. Through analysis and simulations, we demonstrate that i) in Leopard object look-up latency is proportional to the distance between a requesting node and the target object; ii) in case multiple copies of an object exist, Leopard always locates a near-by copy; and iii) Leopard can effectively handle ``flash crowd'' traffic with near optimal load balancing.
  • Thumbnail Image
    Item
    Proactive vs Reactive Approaches to Failure Resilient Routing
    (2003-08-06) Lee, Sanghwan; Yu, Yinzhe; Nelakuditi, Srihari; Zhang, Zhi-Li; Chuah, Chen-nee
    Dealing with network failures effectively is a major operational challenge for Internet Service Providers. Commonly deployed link state routing protocols such as OSPF react to link failures through global (i.e., network wide) link state advertisements and routing table recomputations, causing significant forwarding discontinuity after a failure. The drawback with these protocols is that they need to trade off routing stability and forwarding continuity. To improve failure resiliency without jeopardizing routing stability, we propose a proactive local rerouting based approach called failure insensitive routing. The proposed approach prepares for failures using interface-specific forwarding, and upon a failure, suppresses the link state advertisement and instead triggers local rerouting using a backwarding table. In this paper, we formally analyze routing stability and network availability under both proactive and reactive approaches, and show that FIR provides better stability and availability than OSPF.