Best Paper Award

Multicast Routing Model to Minimize Number of Flow Entries in Software-Defined Network[IEICE TRANS. COMMUN., Vol.E104-B, No.5 MAY 2021]

Seiki KOTACHI
Seiki KOTACHI
Takehiro SATO
Takehiro SATO
Ryoichi SHINKUMA
Ryoichi SHINKUMA
Eiji OKI
Eiji OKI

Multicast communication supports services that send the same information to multiple receivers, such as for web conferencing and video streaming. A software-defined network (SDN) based multicast system which enables a sender to flexibly control packet transfer routes and multicast groups has been studied. In this system, flow entries are stored in a flow table of each SDN switch so that packets are transferred along pre-calculated routes.

SDN switches have limited flow table capacity and it is necessary to efficiently use the capacity by suppressing the number of flow entries. In the case of providing a single multicast service on an SDN, the number of required flow entries can be reduced by using multicast entries (i.e., flow entries which use multicast Internet protocol (IP) addresses as matching rules) compared to adopting unicast communication for each receiver. On the other hand, when providing multiple multicast services at the same time, there is a chance of reducing the number of required flow entries by the combined use of unicast entries (i.e., flow entries which use the receivers’ IP addresses as matching rules) and multicast entries.

This paper proposes a routing model for SDN where multiple multicast services are provided. This paper formulates an optimization problem that minimizes the number of required flow entries and proves the NP-completeness of the decision version of the problem. A heuristic algorithm for the proposed model has been developed to deal with large-scale problems. The numerical results show that the proposed model reduces the total number of flow entries by enabling the sharing of unicast entries among multicast services. This paper contributes to the realization of efficient network operation under the recent situation where the demand for multicast services has been growing, and it is expected that the proposed model will be introduced into actual network systems. Therefore, for the above reasons, this paper can be evaluated as a paper worthy of this award.