China Communications • July 2015
49
ordinates on the subtree rooted at the node are
also updated.
Cvetkovski et al. [9] extended Kleinberg’s
work to dynamic topologies. They adopted the
idea of the dichotomy (Figure 1(1)) to achieve
online embedding. Each time the parent node
assigns half of an undivided region to a child.
Thus, there will always be an undivided re-
gion for the new joining node. In this paper,
we propose a novel strategy from another per-
spective. As shown in Figure 1(2), we make
the region innite by extending the dimension
of metric space, so that the region is large
enough for new nodes.
However, both [9] and [17] need a linear
description complexity. PIE [18] proposed an
isometric embedding in the normed space and
the description complexity is polylogarithmic.
It does not focus on dynamic topologies.
The greedy embedding guarantees 100%
of routing success with coordinates of neigh-
bors and provides scalable and efficient
routing. Based on the above geometric rout-
ing schemes, some geometric name routing
schemes have been proposed for ICN.
MobiCCN [5] adopted a greedy embed-
ding scheme on hyperbolic space for GNR to
support producer mobility. However, the co-
ordinate needs O(n) bits. Prex [6] proposed a
concise prex embedding to achieve the GNR.
Content names are simply hashed, but the dis-
tribution of content coordinates is inconsistent
with the topology, which brings imbalance
for the distribution of resolution entries. To
solve the problem, Prefix-S [7] adopted pre-
x-s embedding and topology-aware hashing.
Though it provides load balancing, each node
needs to store the global topology informa-
tion. The embedding schemes of [6] and [7]
are not greedy. Both of them need additional
strategies for greedy routing. Most of all, all
the three schemes do not take weighted graphs
and dynamic topologies into account.
DD-
We rst propose the framework of D-Grifn,
then detail the geometric routing scheme,
Section IV and Section V provide theoretical
analyses and experimental evaluations, respec-
tively. Finally, SectionVI concludes the paper.
RORK
The routing scheme of CCN[11]/NDN[12] is
similar to the IP routing, where IP addresses
are replaced by hierarchical content names.
The routing table stores the routes to all con-
tents. CCN inherently supports receiver mobil-
ity, but for producer mobility, some additional
mechanisms are needed. The GNR scheme is a
promising solution for producer mobility [5].
The routing schemes using name resolu-
tion, such as MDHT [13], SVMDHT [14]
and HDHT[15], adopt hierarchical DHTs to
provide scalable routing on flat names with
different details in hierarchical domains. In
the domains, they rely on overlay DHTs for
name resolution. αRoute [16] proposed a
name based DHT via a partitioning strategy.
The DHT is an overlay design, and demands
a mapping from the overlay to the under-
lay. These overlay designs cannot guarantee
a tradeoff between scalability and efciency.
A new direction is the geometric routing
to solve the above problems. Some geometric
routing schemes based on greedy embedding
have been developed. Kleinberg [17] proposed
a universal greedy embedding approach for
arbitrary graphs via the greedy embedding of
a spanning tree. The greedy embedding of the
spanning tree into a metric space is viewed
as a division of the metric space. Each node
is responsible for a non-overlapping region
assigned by its parent. When a node joins, its
parent re-divides one of the children’s regions.
If the region of a node is changed, the node
coordinate should be updated, and all node co-
Fig.1 Online strategies
(1) Dichotomy (2) Dimensional expanding