Transcript An Overlay Network for Forwarding Symbolically Addressed

This paper appears in: Computer Communications
and Networks, 2006. ICCCN 2006. Proceedings.15th
International Conference on
指導教授:許子衡
報告者:黃群凱
1


With geocast, messages can be sent to all
mobile and stationary hosts currently located
in a geographic target area.
Geocast messages can be addressed either by
geometric figures, or by symbolic names.
2


Symbolic addressing is an important
alternative to geometric addressing.
We need a complex location model including
geometric descriptions of every symbolically
addressable location.
3


Forwarding decisions are made based on
comparisons of symbolic or geometric target
and service areas.
we propose a heuristics to improve
hierarchical routing by adding shortcuts to
the routing hierarchy.
4


Since multiple a priori unknown senders may
send messages to a given location, either a
source-based tree or shared tree protocol can
be applied, which both have their limitations.
In the worst case, each message may cause a
new tree to be established in the network.
5


we will propose an optimization of our
approach which sends the first messages of a
sender over the overlay and then switches to
a Source-Specific Multicast (SSM [8]) protocol.
The combination of our overlay network and
SSM reduces the overhead to set up sourcebased trees.
6

The three components of our architecture are
hosts, message servers, and routers
7


Geocast Routers (GR) are responsible for
forwarding geocast messages from the
sender to the GMSs whose service areas
overlap with the target area of the message.
GRs are arranged in an overlay network and
exchange messages using the UDP service
offered by the underlying IP-based Internet
infrastructure.
8



For two locations 11 and 12 it holds 11 < 12,
if 12 spatially contains 11.
11 is called a descendant of location 12, and
12 is an ancestor of 11.
A direct descendant of location I is called a
child location and a direct ancestor a parent
location.
9



Ancestors(l), children(l) and parent(l) denote
the set of ancestor locations, child locations,
and the parent location, respectively.
Locations of the location model are used to
define host positions, and service areas of
GRs and GMSs.
A benefit of using an overlay network is that
our location address space is not restricted
by the length limitation of IP addresses.
10

Overlay Network Nodes
◦ GRs constitute the nodes of the overlay network.
Each location I is associated with one designated
Geocast Router, say r.

Overlay Network Links
11

This reduces the load of by-passed GRs and
leads to shorter message paths.
12

Consider for instance the New York City GR (r
new) that wants to join the overlay network.
The following steps are executed to integrate
r new into the overlay network:
13

Our approach uses three phases to forward
messages from the sending host to all hosts
in the target area, t, of the message.
◦ The message is forwarded to the designated GR, rt,
of the target area.
◦ The message is distributed among all routers in the
target area by forwarding it down the router
hierarchy starting at rt.
◦ These GMSs finally forward the message to the
hosts in their access networks that are located in
the target area.
14

Forwarding to Access Networks in Target
Area
15

Optimized Message Forwarding
◦ The basic idea is to start delivering messages to
GMSs via the overlay network and then switch to
layer 3 multicast.
◦ Such an optimization is especially useful if several
messages are sent frequently to the same target
area rather than only single messages that are sent
sporadically.
◦ The class of source-specific multicast (SSM [15])
protocols is well suited for our requirements.
16
17

The whole topology consists of the
backbones of 8 major Internet service
providers in the USA.
18
19



We presented a geocast protocol for the
efficient distribution of symbolically
addressed geocast messages.
Our approach leads to short message paths
and low overlay network router load and thus
high scalability.
In future work, we are going to investigate
how to further improve routing in the overlay
network.
20