Tunnel concentrator placement for traffic optimization in IPv4-IPv6 coexisting networks

A lot of transition mechanisms have been proposed and standardized in Internet Engineering Task Force (IETF), to support the coexistence and interoperability of IPv4 and IPv6. Among them, the 4over6/6over4 edge network tunneling technique has become a particular hot subject recently. To apply this technique into real ISP networks, there is a practical problem: planning the placement of the tunnel concentrators and the routing of the tunneling flows. The problem is essential to the performance and efficiency of data transport in IPv4-IPv6 coexisting network. As the first effort to address this problem, this paper formalizes the problem and builds the optimization model. It proves the problem to be NP-complete and locates the difficulties in the variable diversity and the hub and unsplittable flow features. A novel scheme is then proposed to find an approximate solution. The scheme decomposes the problem and explores the flow routing variability. It eliminates the hub feature by sophisticated topology transformation, and solves the min-cost unsplittable flow problem by shortest path routing of each individual flow along with minimum-interference to other flows. With acceptable time efficiency, the scheme finds better solutions than greedy algorithm and former minimum-interference routing algorithms in most cases.