Traffic Engineering Using Overlay Network

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 service’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.

Fig. 1. Traffic engineering using overlay 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. 1(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 1 to 6. The delay increases on the link between nodes 1 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 sensitive 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. 1, 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. 1(b), the content can be delivered from the near-by 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.

Fig. 2. Functionalities of overlay-network-based traffic engineering.

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 [1]. The information is used in common for all the services.

The traffic/QoS information in the underlay network 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 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 461 for the delay metric and 423 for the bandwidth metric.

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

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 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].

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

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 10 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 link, which caused the congestion.

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

[1]	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-11 (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. 2761–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-15, 2010.
[6]	http://www.caida.org/tools/visualization/mapnet/Data/

↑ TOP