SATを用いたSDNルールテーブル分割法の高速化に関する検討

• Item type: SIG Technical Reports(1)
• 公開日: 2019-06-04
• タイトル: SATを用いたSDNルールテーブル分割法の高速化に関する検討
• タイトル / 言語: en
• タイトル: Note on Fast SAT-Based SDN Rule Table Partitioning
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: ストレージ・ネットワーク
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 日本大学大学院生産工学研究科
• 著者所属: 日本大学生産工学部
• 著者所属(英): en
• 著者所属(英): Graduate School of Industrial Technology, Nihon University
• 著者所属(英): en
• 著者所属(英): College of Industrial Technology, Nihon University
• 著者名: 小笠原, 亮太; 新井, 雅之
• 著者名(英): Ryota, Ogasawara; Masayuki, Arai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: SofiWare-DefinedNetwork (SDN) では，ネットワークポリシーはルールテーブルとしてネットワークスイッチに配布される．ルールテーブルを保持するために用いられるメモリ (TCAM) は消費電力の面からサイズに制限が存在する．このためルールテーブルをサブテーブルに分割し，元のルールテーブルとの整合性を保ちつつパス上の複数のスイッチに分散配置する手法について研究が行われている．著者らは，充足可能性問題 (SAT) ソルバを用いた最大サブテーブル分割数探索法について提案した．先行研究のアルゴリズムでは，与えられたサブテーブル数での分割が可能であるか否かを充足可能性問題として定式化し，サブテーブル数を減少させながら SAT ソルバによる探索を繰り返す．本研究では，先行研究のアルゴリズムの高速化を目的として，従来手法である SA アルゴリズムと SAT を組み合わせた手法，およびサブテーブル数を増加させる手法の 2 通りについて検討を行う．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In Software-Defined Networking (SDN), network policies are stored into network switches in the form of rule table. Temaiy content addressable memories (TCAMs), which are often used to store rule table, have limitation on their size due to high power consumption. Then, some research has been conducted in the field of rule table partitioning, where sub-tables are distributed into switches on every network path while maintaining integrity of original rule table. In previous work we proposed maximum sub-table partitioning by applying a satisfiability (SAT) solver. The previous algorithm formulates the problem of determining if partitioning of rule table with a given number of partition is possible or not as a satisfiability problem, and then repeatedly executes SAT solver, decreasing the number of partitions. In this study, aiming at further speed-up of searching, we discuss two algorithms: combination of conventional SA algorithm and SAT-based approach, and incremental search for the number of partitions.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10096105
• 書誌情報: 研究報告システム・アーキテクチャ（ARC）; 巻 2019-ARC-236, 号 6, p. 1-6, 発行日 2019-06-04
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8574
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会