Decoupling the permanent identifier of a node from the node's topology-dependent address is a promising approach toward completely scalable self-organizing networks. A group of proposals that have adopted such an approach use the same structure to: address nodes, perform routing, and implement location service. In this way, the consistency of the routing protocol relies on the coherent sharing of the addressing space among all nodes in the network. Such proposals use a logical tree-like structure where routes in this space correspond to routes in the physical level. The advantage of tree-like spaces is that it allows for simple address assignment and management. Nevertheless, it has low route selection flexibility, which results in low routing performance and poor resilience to failures. In this paper, we propose to increase the number of paths using incomplete hypercubes. The design of more complex structures, like multi-dimensional Cartesian spaces, improves the resilience and routing performance due to the flexibility in route selection. We present a framework for using hypercubes to implement indirect routing. This framework allows to give a solution adapted to the dynamics of the network, providing a proactive and reactive routing protocols, our major contributions. We show that, contrary to traditional approaches, our proposal supports more dynamic networks and is more robust to node failures.
Similarly to Tribe, PeerNet @cite_6 is a peer-to-peer based network layer for dynamic and large networks. The address reflects the node's location in the network and is registered with the respective identifier in the distributed node lookup service. In PeerNet, the addresses are organized as leaves of a binary tree -- the address tree. PeerNet routing is a recursive procedure descending through the address tree. Thus, in contrast to Tribe, PeerNet routing disseminates information about the global state of the network, and nodes maintain a routing table that has @math entries, i.e. @math per-node state (where @math is a number of nodes in the network). Because of the address tree organization, a node movement may require the assignment of new addresses to several nodes in PeerNet infrastructure, which implicitly generates many updates in lookup entries.
@cite_6
1588448334 2160405192 1492552531 2024259126
An unwritten principle of the Internet Protocol is that the IP address of a node also serves as its identifier. We observe that many scalability problems result from this principle, especially when we consider mobile networks. In this work, we examine how we would design a network with a separation between address and identity. We develop PeerNet, a peer-to-peer-based network layer for large networks. PeerNet is not an overlay on top of IP, it is an alternative to the IP layer. In PeerNet, the address reflects the node’s current location in the network. This simplifies routing significantly but creates two new challenges: the need for consistent address allocation and an efficient node lookup service. We develop fully distributed solutions to address these and other issues using a per-node state of O(log N), where N is the number of nodes in the network. PeerNet is a radically different alternative to current network layers, and our initial design suggests that the PeerNet approach is promising and worth further examination. Several peer-to-peer networks are based upon randomized graph topologies that permit efficient greedy routing, e. g., randomized hypercubes, randomized Chord, skip-graphs and constructions based upon small-world percolation networks. In each of these networks, a node has out-degree Θ(log n), where n denotes the total number of nodes, and greedy routing is known to take O(log n) hops on average. We establish lower-bounds for greedy routing for these networks, and analyze Neighbor-of-Neighbor (NoN)- greedy routing. The idea behind NoN, as the name suggests, is to take a neighbor's neighbors into account for making better routing decisions.The following picture emerges: Deterministic routing networks like hypercubes and Chord have diameter Θ(log n) and greedy routing is optimal. Randomized routing networks like randomized hypercubes, randomized Chord, and constructions based on small-world percolation networks, have diameter Θ(log n log log n) with high probability. The expected diameter of Skip graphs is also Θ(log n log log n). In all of these networks, greedy routing fails to find short routes, requiring Ω(log n) hops with high probability. Surprisingly, the NoN- greedy routing algorithm is able to diminish route-lengths to Θ(log n log log n) hops, which is asymptotically optimal. Scalable overlay networks such as Chord, CAN, Pastry, and Tapestry have recently emerged as flexible infrastructure for building large peer-to-peer systems. In practice, such systems have two disadvantages: They provide no control over where data is stored and no guarantee that routing paths remain within an administrative domain whenever possible. SkipNet is a scalable overlay network that provides controlled data placement and guaranteed routing locality by organizing data primarily by string names. SkipNet allows for both fine-grained and coarse-grained control over data placement: Content can be placed either on a pre-determined node or distributed uniformly across the nodes of a hierarchical naming sub-tree. An additional useful consequence of SkipNet's locality properties is that partition failures, in which an entire organization disconnects from the rest of the system, can result in two disjoint, but well-connected overlay networks. In this work we present a middleware architecture for a mobile peer-to-peer content distribution system. Our architecture allows wireless content dissemination between mobile nodes without relying on infrastructure support. Contents are exchanged opportunistically when nodes are within communication range. Applications access the service of our platform through a publish subscribe interface and therefore do not have to deal with low-level opportunistic networking issues or matching and soliciting of contents. Our architecture consists of three key components. A content structure that facilitates dividing contents into logical topics and allows for efficient matching of content lookups and downloading under sporadic node connectivity. A solicitation protocol that allows nodes to solicit content meta-information in order to discover contents available at a neighboring node and to download content entries disjointedly from different nodes. An API that allows applications to access the system services through a publish subscribe interface. In this work we describe the design and implementation of our architecture. We also discuss potential applications and present evaluation results from profiling of our system.