Letters

Traffic Engineering Using Overlay Network

Ryoichi Kawahara†, Noriaki Kamiyama, Tatsuya Mori,
and Haruhisa Hasegawa

Abstract

We present a method of controlling the traffic of individual services by using an overlay network,
which lets us flexibly add various functionalities. The overlay network provides control functionalities
such as for constructing an overlay network topology for each service, calculating the optimal route for
its quality of service (QoS), and caching content to reduce the amount of traffic. By applying traffic
engineering taking into account each service’s QoS requirements, this overlay network can overcome the
problem of indiscriminate QoS degradation when the network becomes congested due to a sudden
increase in traffic for a particular service.

1. Introduction
Network integration based on Internet protocol (IP)
technologies is progressing, and various types of services
are accordingly being aggregated into networks.
However, network usage patterns and applications,
e.g., peer-to-peer file sharing, consumer generated
media, video content sharing, and streaming, are
becoming more diverse. Access networks and end
host terminals are also becoming more diverse, and
their bandwidth and/or processing capacities are
increasing. In addition, with the various types of rich
content delivery expected in the future, it is becoming
harder to tame traffic patterns in the space domain,
e.g., the traffic matrix is less controllable, as well as
in the time domain, e.g., temporal cyclic patterns of
traffic are now less predictable than ever.

Under such circumstances, because the network
resources are shared by the traffic of individual services
in an integrated network, the quality of service
(QoS) for all the services may become degraded
indiscriminately when the network becomes congested
due to a sudden increase in traffic for a particular
service. This may occur if we do not perform
any traffic engineering taking into account each ser


† NTT Service Integration Laboratories
Musashino-shi, 80-8585 Japan
vice’s QoS requirements. To resolve this problem, we
need a traffic engineering method that takes those
requirements into account.

To establish such a method that can cope with various
QoS requirements, we are focusing on overlay
network technology. An overlay network is defined as
a logical network constructed to achieve some functionalities
over a physical network, such as an IP
network (Fig. 1(a)). Specifically, the overlay network
has been attracting attention as a way of adding new
functionalities to any network that are hard to implement
in a physical network.

As an example, consider the case where the QoS of
the path from host a to host c is degraded in the
physical network in Fig. (a). In this case, we prepare
server b as an overlay node to construct an overlay
network by connecting it logically to other nodes, i.e.,
hosts a and c, where node a is logically connected to
node b means that node a knows the IP address of
node b and can communicate with node b. Then, we
establish route a-b-c to avoid the congestion and
improve the QoS.

Another example is shown in Fig. 1(b), where the
physical network consists of nodes to 6. The delay
increases on the link between nodes and 2 while the
throughput simultaneously decreases on the link
between nodes 3 and 5. In this case, we construct two
overlay networks: one for service X, which is sensi


NTT Technical Review


Letters

Letters

QoS
degradation
Host c
Overlay network
Physical
network
(a) Quality deterioration avoidance by using overlay
network
Host a
Route control according to QoS
Service Y
Service X
4
6
Delay
increase
Throughput
decrease
Cache control
(b) Path control adjusted to various quality metrics
1
2
3 5
Fig. 1. Traffic engineering using overlay network.

tive to the delay metric, and the other for service Y,
which is sensitive to the throughput metric. For each
service overlay network, we calculate the optimal
route in terms of the corresponding metric.

As shown in Fig. , by achieving functionalities for
QoS measurement, logical network construction, and
route calculation through the use of an overlay network,
we expect to be able to control the traffic of an
individual service according to its QoS requirements.
In addition, if the same content is delivered to many
users, we can reduce the traffic generated by the content
by caching the content in the network. That is, if
we add a caching functionality to the overlay node
and the content of service Y is cached, as shown in
Fig. (b), the content can be delivered from the nearby
caching overlay node to the requesting node. This
makes it possible to reduce the traffic compared with the
case where the content is delivered along the multihop
path from the original server to the requesting node.

This article is organized as follows. Section 2 presents
an overlay-network-based traffic control architecture
and the functionalities needed at individual
items of network equipment in the architecture. Section
3 presents a method of constructing an overlay
network topology on the architecture. Section 4
describes our method of calculating the overlay route
on the overlay topology. Finally, section 5 summarizes
the article.

2. Overlay-network-based
traffic control architecture
We propose that a network provider, such as an
Internet service provider or a carrier, constructs an
overlay network with functionalities for controlling
the traffic of individual services. An overlay network
consists of overlay nodes prepared by a network provider
(nOL nodes), end host overlay nodes (eOL
nodes), and a controller managed by the network
provider, as shown in Fig. 2. The nOL node and the
controller are prepared by the network provider,
while an eOL node is an end-host that receives a service.


The geographically distributed nOL nodes cooperate
with the controller to control the service overlay
network and the routes. Here, a service corresponds
to a file-sharing, streaming, or voice over IP service,
for example.

Specifically, the controller manages the traffic/QoS
information in an underlay network, e.g., network
topology, link utilization, and QoS metrics such as
delay, packet loss ratio, and throughput. This kind of
information is obtained through active measurements
among overlay nodes, or traffic data measured in the
physical network [ ]. The information is used in common
for all the services.

The traffic/QoS information in the underlay network

Vol. 8 No. 9 Sep. 2010


Letters

Letters

Physical network
Controller
nOL node
eOL node
Overlay network- Packet relaying
- Content caching
Traffic/QoS
information
- Topology control
- Route control
Fig. 2. Functionalities of overlay-network-based traffic engineering.

is used by nOL nodes to construct each service overlay
network topology, e.g., for services A and B
shown in Fig. 2. These nodes then calculate the optimal
routes for the service, taking into account the
QoS requirements. To relay packets between end
hosts along a designated route, we use nOL nodes as
relay nodes.

If the traffic is cacheable, i.e., the same content is
delivered to many users, we can reduce the content
traffic by caching the content at the nOL nodes. That
is, we can deliver the content from a nearby caching
nOL node to the requesting user, which makes it possible
to reduce the traffic compared with the case
where the content is delivered along the multihop
path from the original server.

In the case of applications where eOL nodes can
relay and/or cache packets, the eOL nodes cache the
received pieces of content and forward them to their
neighbors, determined by the nOL nodes. This makes
it possible to localize the traffic, i.e., to reduce the
traffic exchanged between different areas.

3. Overlay topology construction method
If we construct a full-mesh topology, we can find an
optimal overlay route by examining all the possible
overlay routes. However, this requires both measuring
the QoS between all node pairs and investigating

all the routes in the full-mesh overlay topology,
which poses a scalability problem in terms of both
measurement cost and route calculation and dissemination
cost.

Thus, we need to develop a method of constructing
a cost-effective overlay topology. To achieve this, we
investigated the structure of an overlay topology that
can provide the optimal QoS routes for all node pairs.
We used round trip time (RTT) measurement data
between individual pairs of hundreds of nodes
obtained in PlanetLab, which is the global overlay
network testbed [2]. Specifically, we examined the
shortest routes between individual node pairs in the
full-mesh topology. We found that some nodes have
extremely high betweenness centrality [3]. That is, a
small number of nodes are frequently included in the
optimal QoS routes for a large number of node pairs.
We also found the same characteristics in Japanese
traffic data [4].

On the basis of this observation, we present a
method of constructing a two-layer network where
the upper layer consists of a small number of overlay
nodes with high betweenness centrality while the
lower layer consists of the other overlay nodes
(Fig. 3(a)). The number of upper-layer nodes is
set to about 5% of the total number of nodes.
Figures 3(b) and (c) show the performance evaluation
results in terms of the delay metric and available

NTT Technical Review


Letters

Letters
Overlay topology construction
Nodes with
high betweenness centrality
Upper layer
Lower layer
1
0.8
0.6
0.4
0.2
Cumulative distribution

Optimal
NoControl
New
0

0 100 200 300 400 500
Delay (ms)


(b) Delay (c) Bandwidth
1
0.8
0.6
0.4
0.2
Optimal
NoControl
New
0

1 10 100 1000


Cumulative distribution

Available bandwidth (Mbit/s)

Fig. 3. Overlay topology construction method and evaluation results.

bandwidth metric, respectively. Each figure shows
the cumulative distribution of end-to-end QoS
between all node-pairs when shortest routes are calculated
on our overlay network where the top 20
nodes in terms of betweenness centrality are used as
upper-layer nodes (“New”), or on the full-mesh network
(“Optimal”), or when no overlay routing is
performed (“NoControl”). The total number of nodes
is 46 for the delay metric and 423 for the bandwidth
metric.

Figures 3(b) and (c) show that our new method can
provide much better performance than NoControl
and achieves almost the same performance as the
optimal routes.

4. Overlay routing control method
As explained in section 2, in our architecture, each
service has its own service overlay network topology

and controls the traffic in the topology. Specifically,
each service overlay network performs routing control
to improve its own QoS, such as delay, packet
loss ratio, and throughput. In this case, because many
service overlay networks share the network resources,
such as underlay network bandwidth, the traffic
from multiple service overlays may concentrate on
one or more particular nodes and/or links. This causes
performance degradation for the service overlay networks.
That is, if individual overlay networks determine
the overlay routes selfishly to improve their own
performances, the resulting performances may worsen
because the traffic from the individual overlay
networks is routed to the same link and causes congestion.


In response, we have developed a route selection
method that can avoid performance degradation
caused by selfish routing. It learns the better routes
using combinations of past route selection and the

Vol. 8 No. 9 Sep. 2010


Letters

Letters
Route selection using online algorithm
Controller
nOL node
- For each service, choose route i with probability w(i)/Σiw(i), where w(i) is the weight for route i.
- Update w(i) as w(i)=w(i)βr(i), where r(i) is the QoS metric measured at the latest measurement
point and 0<β<1.
Service A Service B
(b) Throughput (c) Link utilization
10

Selfish
New
NoControl
0.6

New
Selfish
Optimal
Throughput (Mbit/s)

8

6
4
2

Link utilization

0.4

0.2

0

0
Topology (1) (2) (3) (4) Topology (1) (2) (3) (4)

Fig. 4. Overlay routing control method and performance evaluation results.

resulting traffic/QoS states according to the procedure
shown in Fig. 4(a). This algorithm can provide
better routes for individual service traffic with high
probability without assuming traffic patterns for all
services in advance [5].

We evaluated the performance of our routing method
under various underlay network topologies. We
chose four of the physical network topologies available
at a web page [6]. Because we wanted to evaluate
the fundamental characteristics of overlay routing,
we assumed that an nOL node is allocated to each
physical node of a topology and that the nOL nodes
are connected in a full-mesh overlay topology. A performance
evaluation of the combination with the
overlay topology construction method is for further
study.

In our simulation, each nOL node had eOL nodes
generating flows. Each flow requested a file with an

access link speed of 0 Mbit/s, and the bandwidth of
a physical link was allocated to each flow according
to the number of active flows on the link. We evaluated
the end-to-end throughput as the QoS metric.
The 5th percentile of the throughputs of flows under
our method is shown in Fig. 4(b). For comparison, we
also show the result for “Selfish”, which corresponds
to each overlay node using the average throughput
measured between the overlay nodes and determining
the best route, and that of “NoControl”, which corresponds
to no overlay routing being performed.
Figure 4(b) shows that our method can achieve almost
the same high throughput as the access link speed. In
contrast, Selfish and NoControl had degraded
throughput due to some links becoming bottlenecked.
In NoControl, this was because the route was determined
by the minimum hop route in the physical
network. In Selfish, flows were routed to the same

NTT Technical Review


Letters

Letters

As an example of network resource utilization, we
show the average link utilization in Fig. 4(c). For
comparison, we also show the result for “Optimal”,
which is the case where we solve an optimization
problem called the minimum cost flow problem when
the traffic matrix is given. Figure 4(c) shows that our
method can reduce the offered traffic compared with
Selfish and achieve almost the same good performance
as Optimal.

5. Conclusion
We have developed an overlay-network-based traffic
engineering method to cope with various types of
QoS requirements. Our future work will focus on an
extensive simulation evaluation using actual traffic
trace data and also an experimental analysis using a

testbed environment.

References

[ ]
R. Kawahara, K. Ishibashi, T. Mori, N. Kamiyama, and H. Hasegawa,
“A method of estimating QoS using flow sampling,” IEICE Society
Conference 2009, B-7- (in Japanese).

[2]
http://www.planet-lab.org/
[3]
R. Kawahara, S. Kamei, N. Kamiyama, H. Hasegawa, H. Yoshino, E.
K. Lua, and A. Nakao, “A method of constructing QoS overlay network
and its evaluation,” IEEE GLOBECOM 2009, Honolulu, HI,
USA, Dec. 2009.
[4]
R. Kawahara, E. K. Lua, M. Uchida, S. Kamei, and H. Yoshino, “On
the quality of triangle inequality violation aware routing overlay
architecture,” IEEE INFOCOM 2009 Mini-conference, pp. 276 .
2765, Rio de Janeiro, Brazil, Apr. 2009.
[5]
R. Kawahara, S. Harada, N. Kamiyama, T. Mori, H. Hasegawa, and A.
Nakao, “Controlling overlays with overlay: Traffic engineering
through cooperation between overlay and underlay,” IEICE General
Conference, BS-3- 5, 20 0.
[6]
http://www.caida.org/tools/visualization/mapnet/Data/
Ryoichi Kawahara

Distinguished Technical Member, Senior
Research Engineer, Supervisor, Communication
Traffic & Service Quality Project, NTT Service
Integration Laboratories.

He received the B.E. and M.E. degrees in automatic
control and Ph.D. degree in telecommunication
engineering from Waseda University,
Tokyo, in 990, 992, and 200 , respectively.
Since joining NTT in 992, he has been engaged
in research on traffic control for telecommunication
networks. He is currently working on teletraffic
issues in IP networks in NTT Service
Integration Laboratories. He is a member of the
Institute of Electronics, Information and Communication
Engineers (IEICE) of Japan and the
Operations Research Society of Japan. He
received IEICE’s Young Researcher’s Award in
999 and Best Paper Awards in 2003 and 2009.

Noriaki Kamiyama

Distinguished Technical Member, Senior
Research Engineer, Communication Traffic &
Service Quality Project, NTT Service Integration
Laboratories.

He received the M.E. and Ph.D. degrees in
communications engineering from Osaka University
in 994 and 996, respectively. From
996 to 997, he was with the University of
Southern California as a visiting researcher. He
joined NTT Multimedia Networks Laboratories
in 997. Since then, he has been engaged in
research concerning pricing methods for IP networks,
content-distribution systems, optical networks,
IP traffic measurement, and network
design.


Tatsuya Mori

Research Engineer, Communication Traffic &
Service Quality Project, NTT Service Integration
Laboratories.

He received the M.E. degree in applied physics
and Ph.D. degree in information science from
Waseda University, Tokyo, in 999 and 2005,
respectively. Since joining NTT in 999, he has
been engaged in research on network traffic
characterization, high-speed network monitoring,
network security, and future network architecture.
From March 2007 to March 2008, he was
a visiting researcher at the University of Wisconsin-
Madison, USA.

Haruhisa Hasegawa

Senior Research Engineer, Supervisor, Group
Leader, Traffic Solution Group, Communication
Traffic & Service Quality Project, NTT Service
Integration Laboratories.

He received the B.E., M.E., and Ph.D. degrees
in information and computer science from
Waseda University, Tokyo, in 988, 990, and
200 , respectively. He joined NTT in 990 and
has been researching traffic engineering and
management in telecommunications networks.
From 2000 to 2003, he was engaged in network
management at the network operation center of
NTT EAST. He is a member of the IEEE Communications
Society and IEICE.

Vol. 8 No. 9 Sep. 2010