IEICE TRANSACTIONS on Communications
Open Access
Multicast Routing Model to Minimize Number of Flow Entries in Software-Defined Network
-
Full Text Views
32
- Cite this
- Free PDF (2.7MB)
Summary :
The Software-defined network (SDN) uses a centralized SDN controller to store flow entries in the flow table of each SDN switch; the entries in the switch control packet flows. When a multicast service is provided in an SDN, the SDN controller stores a multicast entry dedicated for a multicast group in each SDN switch. Due to the limited capacity of each flow table, the number of flow entries required to set up a multicast tree must be suppressed. A conventional multicast routing scheme suppresses the number of multicast entries in one multicast tree by replacing some of them with unicast entries. However, since the conventional scheme individually determines a multicast tree for each request, unicast entries dedicated to the same receiver are distributed to various SDN switches if there are multiple multicast service requests. Therefore, further reduction in the number of flow entries is still possible. In this paper, we propose a multicast routing model for multiple multicast requests that minimizes the number of flow entries. This model determines multiple multicast trees simultaneously so that a unicast entry dedicated to the same receiver and stored in the same SDN switch is shared by multicast trees. We formulate the proposed model as an integer linear programming (ILP) problem. In addition, we develop a heuristic algorithm which can be used when the ILP problem cannot be solved in practical time. Numerical results show that the proposed model reduces the required number of flow entries compared to two benchmark models; the maximum reduction ratio is 49.3% when the number of multicast requests is 40.
- Publication
- IEICE TRANSACTIONS on Communications Vol.E104-B No.5 pp.507-518
- Publication Date
- 2021/05/01
- Publicized
- 2020/11/13
- Online ISSN
- 1745-1345
- DOI
- 10.1587/transcom.2020EBP3064
- Type of Manuscript
- PAPER
- Category
- Network
Authors
Seiki KOTACHI
Kyoto University
Takehiro SATO
Kyoto University
Ryoichi SHINKUMA
Kyoto University
Eiji OKI
Kyoto University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Seiki KOTACHI, Takehiro SATO, Ryoichi SHINKUMA, Eiji OKI, "Multicast Routing Model to Minimize Number of Flow Entries in Software-Defined Network" in IEICE TRANSACTIONS on Communications,
vol. E104-B, no. 5, pp. 507-518, May 2021, doi: 10.1587/transcom.2020EBP3064.
Abstract: The Software-defined network (SDN) uses a centralized SDN controller to store flow entries in the flow table of each SDN switch; the entries in the switch control packet flows. When a multicast service is provided in an SDN, the SDN controller stores a multicast entry dedicated for a multicast group in each SDN switch. Due to the limited capacity of each flow table, the number of flow entries required to set up a multicast tree must be suppressed. A conventional multicast routing scheme suppresses the number of multicast entries in one multicast tree by replacing some of them with unicast entries. However, since the conventional scheme individually determines a multicast tree for each request, unicast entries dedicated to the same receiver are distributed to various SDN switches if there are multiple multicast service requests. Therefore, further reduction in the number of flow entries is still possible. In this paper, we propose a multicast routing model for multiple multicast requests that minimizes the number of flow entries. This model determines multiple multicast trees simultaneously so that a unicast entry dedicated to the same receiver and stored in the same SDN switch is shared by multicast trees. We formulate the proposed model as an integer linear programming (ILP) problem. In addition, we develop a heuristic algorithm which can be used when the ILP problem cannot be solved in practical time. Numerical results show that the proposed model reduces the required number of flow entries compared to two benchmark models; the maximum reduction ratio is 49.3% when the number of multicast requests is 40.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.2020EBP3064/_p
Copy
@ARTICLE{e104-b_5_507,
author={Seiki KOTACHI, Takehiro SATO, Ryoichi SHINKUMA, Eiji OKI, },
journal={IEICE TRANSACTIONS on Communications},
title={Multicast Routing Model to Minimize Number of Flow Entries in Software-Defined Network},
year={2021},
volume={E104-B},
number={5},
pages={507-518},
abstract={The Software-defined network (SDN) uses a centralized SDN controller to store flow entries in the flow table of each SDN switch; the entries in the switch control packet flows. When a multicast service is provided in an SDN, the SDN controller stores a multicast entry dedicated for a multicast group in each SDN switch. Due to the limited capacity of each flow table, the number of flow entries required to set up a multicast tree must be suppressed. A conventional multicast routing scheme suppresses the number of multicast entries in one multicast tree by replacing some of them with unicast entries. However, since the conventional scheme individually determines a multicast tree for each request, unicast entries dedicated to the same receiver are distributed to various SDN switches if there are multiple multicast service requests. Therefore, further reduction in the number of flow entries is still possible. In this paper, we propose a multicast routing model for multiple multicast requests that minimizes the number of flow entries. This model determines multiple multicast trees simultaneously so that a unicast entry dedicated to the same receiver and stored in the same SDN switch is shared by multicast trees. We formulate the proposed model as an integer linear programming (ILP) problem. In addition, we develop a heuristic algorithm which can be used when the ILP problem cannot be solved in practical time. Numerical results show that the proposed model reduces the required number of flow entries compared to two benchmark models; the maximum reduction ratio is 49.3% when the number of multicast requests is 40.},
keywords={},
doi={10.1587/transcom.2020EBP3064},
ISSN={1745-1345},
month={May},}
Copy
TY - JOUR
TI - Multicast Routing Model to Minimize Number of Flow Entries in Software-Defined Network
T2 - IEICE TRANSACTIONS on Communications
SP - 507
EP - 518
AU - Seiki KOTACHI
AU - Takehiro SATO
AU - Ryoichi SHINKUMA
AU - Eiji OKI
PY - 2021
DO - 10.1587/transcom.2020EBP3064
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E104-B
IS - 5
JA - IEICE TRANSACTIONS on Communications
Y1 - May 2021
AB - The Software-defined network (SDN) uses a centralized SDN controller to store flow entries in the flow table of each SDN switch; the entries in the switch control packet flows. When a multicast service is provided in an SDN, the SDN controller stores a multicast entry dedicated for a multicast group in each SDN switch. Due to the limited capacity of each flow table, the number of flow entries required to set up a multicast tree must be suppressed. A conventional multicast routing scheme suppresses the number of multicast entries in one multicast tree by replacing some of them with unicast entries. However, since the conventional scheme individually determines a multicast tree for each request, unicast entries dedicated to the same receiver are distributed to various SDN switches if there are multiple multicast service requests. Therefore, further reduction in the number of flow entries is still possible. In this paper, we propose a multicast routing model for multiple multicast requests that minimizes the number of flow entries. This model determines multiple multicast trees simultaneously so that a unicast entry dedicated to the same receiver and stored in the same SDN switch is shared by multicast trees. We formulate the proposed model as an integer linear programming (ILP) problem. In addition, we develop a heuristic algorithm which can be used when the ILP problem cannot be solved in practical time. Numerical results show that the proposed model reduces the required number of flow entries compared to two benchmark models; the maximum reduction ratio is 49.3% when the number of multicast requests is 40.
ER -
English
