博士学位論文

(1)

博

士

学

位

論

文

Doctoral Dissertation

内容の要旨及び審査結果の要旨

Dissertation Abstract and

Summary of the Dissertation Review Result

第２８号

The Twenty-eighth Issue

平成２８年９月

September, 2016

The University of Aizu

(2)

はしがき

博士の学位を授与したので、学位規則（昭和２８年４月１日文部省令第９号）第８条の規定に基づき、その論文の内容の要旨及び論文審査の結果の要旨をここに公表する。

学位記番号に付した｢甲｣は学位規則第４条第１項（いわゆる課程博士）によるものであることを示す。

Preface

On granting the Doctoral Degree to the individuals mentioned below, abstracts of their theses and the theses review results are herewith publicly announced, in according to the provisions provided for in Article 8 of the Ruling of Degrees (Ministry Of Education Ordinance No.9, enacted on April 1, 1953)

The Chinese character, “甲”, at the beginning of the diploma number represents that an

individual has been granted the degree in accordance with the provisions provided for in

Paragraph 4-1 of the Ruling Of Degrees (what is called “Katei Hakase,” or the Doctoral

Degree granted by the University at which the grantee was enrolled.).

(3)

- 1 -

Abstract

Software-Defined Networking (SDN) is a promising network paradigm that separates the control plane and data plane in the network. It has shown great advantages in simplifying network management such that new functions can be easily supported without physical access to routers or switches. In SDN networks, Ternary Content Addressable Memory (TCAM) is a critical hardware, which is used to store forwarding rules for high-speed packet processing in SDN-enabled devices. However, it can be

supplied to each device with very limited quantity because it is expensive and energy-consuming.

Therefore, this dissertation studies three primary issues for SDN networks on the cost-efficient rule management.

At the first, because rules can be deployed into network switches in a static SDN environment, we study rule placement problem with the objective of minimizing rule consumption for multiple unicast sessions under Quality-of-Service (QoS) constraints. To this aim, we propose a rule multiplexing scheme, in which the same set of forwarding rules deployed on each node apply to the whole flow of a session going through but towards different paths. Based on this scheme, we formulate the rule placement problem jointly considering link bandwidth and rule space constraints under both existing and our rule multiplexing schemes. Via an extensive review of the state-of-the-art work, to the best of our knowledge, we are the first to propose the rule multiplexing problem. Extensive simulations are conducted to show that our proposed approaches significantly outperform existing solutions.

Secondly, in an online environment of SDN networks, each traffic flow is shaped by a set of associated forwarding rules that are maintained by switches in their local TCAM-based flow tables.

Since rules should be deployed or removed depending on varying traffic pattern, it is worth to study the rule caching problem under an online environment. As mentioned, since TCAM is an expensive hardware, each switch has only limited TCAM space and it is inefficient and even infeasible to maintain all rules at local switches. On the other hand, if we eliminate TCAM occupation by forwarding all packets to the centralized controller for processing, it will result in a long delay and heavy processing burden on the controller. Therefore, in the second topic, we are motivated to study the trade-off between local packet processing and remote packet processing. To this end, we formulate a Minimum Weighted Flow Provisioning (MWFP) problem with the objective to minimize the total cost in terms of TCAM occupation and remote packet processing. We propose an efficient offline algorithm if the network traffic is given. Otherwise, we propose two online algorithms with guaranteed competitive ratios. Finally, we conduct extensive trace-driven experiments using real network traffic traces. The evaluation results demonstrate that our proposed algorithms can significantly reduce the total cost, and the solutions obtained are nearly optimal.

Thirdly, SDN brings a number of advantages along with many challenges, one particular concern is on the resilience for the in-band control channels. The existing approaches mainly rely on a local

rerouting policy when performing the routing protection for the target sessions in SDN networks.

(6)

- 4 -

However, such policy would potentially bring congestions in the neighboring links of the failed one.

Therefore, in the third topic, we notice that rules should be updated corresponding to the link failure in an SDN network. Aiming to provide the robust routing protection towards the control plane of SDN networks, we strive to find the cost-efficient rule update solutions by studying a weighted cost minimization problem. In particular, the traffic load balancing and control-channel setup cost are jointly taken into consideration. Since this problem is known as NP-hard, we propose a Markov Approximation (MA) based near-optimal approach to solve it. We then extend our solution to an online case that handles the single-link failure one at a time. The incurred performance fluctuation by the single-link failure is also analyzed with theoretical derivation. Extensive numerical results show that the proposed MA based algorithm illustrates fast convergence and high efficient resource consumption in terms of rule deployment cost and link bandwidth utilization.

Summary of the Dissertation Review Result

SDN has shown great advantages in simplifying network management such that new network functions can be easily deployed without physical access to routers or switches. This dissertation has studied three primary issues for SDN networks on the cost-efficient rule management. Aiming to achieve the cost-efficient rule management for three different scenarios under SDN networks, the contributions of this dissertation are summarized in three aspects.

The first main contribution of the dissertation is presented as the follows. Since rules can be deployed into network switches in a static SDN environment, the candidate studied the rule placement problem with the objective of minimizing rule consumption for multiple unicast sessions under QoS constraints. The candidate then proved such optimization problem NP-hard. When a set of possible candidate paths for each session are given, the candidate formulated the optimization problems under both existing and our rule multiplexing schemes, i.e., the CP-based RM and nonRM optimizations.

Then, the candidate further studied a more challenging scenario, where no candidate paths are provided, with a joint optimizations between routing and rule placement. This study has been written as a paper that has been published in IEEE Transactions on Computers.

The second main contribution is studying a rule caching problem under an online environment, where rules should be deployed or removed depending on varying traffic pattern. For minimizing the total cost over remote processing and local forwarding-table occupation, the candidate proposed an offline algorithm by adopting a greedy strategy if the network traffic is given in advance, and devised two online algorithms with guaranteed competitive ratios. This topic has been written as a paper that has been published in IEEE Transactions on Parallel and Distributed Systems.

The final contribution of this dissertation is investigating the rule update mechanism corresponding to the link failure in an SDN network. Aiming to provide the robust routing protection mechanism towards the control plane of SDN networks, the candidate attempted to find the cost-efficient rule

(7)

- 5 -

update solutions. The proposed approach can be extended to the routing protection in data plane. This part has been written as a paper that has been accepted by IEEE Journal on Selected Areas in Communications.

Besides these journal publications, the candidate also has presented many conference papers in several major international IEEE conferences. The candidate shows strong knowledge and practical skill of topics related to the candidate’s research. The dissertation writing and the oral presentation are also excellent.

(8)

- 6 - Name

氏名

李玉潔

LI, Yujie（リーユージエ）

学位記番号

甲CI博第53号

論文題目

Dictionary learning algorithms for sparse representation of signal with the analysis model 解析的モデルで信号のスパース表現のための辞書学習アルゴリズム

University of Aizu, Prof. DING, S. (Chief Referee)

University of Aizu, Prof. MORI, K

University of Aizu, Senior Associate Prof.

MARKOV, K.

University of Aizu, Associate Prof. PEI, Y.

会津大学教授丁数学（主査）

会津大学教授森和好

会津大学上級准教授ｺﾝｽﾀﾝﾃｨﾝﾏﾙｺﾌ会津大学准教授裴岩

(9)

- 7 -

Abstract

Sparse representation has been proven to be a powerful tool for analysis and processing of signals and images. Different from the synthesis sparse model, in analysis model, the analysis dictionary multiplying the signal can lead to a sparse outcome. The analysis dictionary learning problem has received less attention and only a few algorithms have been proposed recently. There are two stages for dictionary learning with analysis model: analysis dictionary update stage and sparse coding stage.

At first, we consider the dictionary learning in analysis model for nonnegative signal representation.

The algorithms designed for general signals are found not sufficient when applied to the nonnegative signals. So, we focus on the dictionary learning for nonnegative signal representation. For a more efficient dictionary learning, we first propose a novel cost function that is termed as the summation of blocked determinants measure of sparseness (SBDMS). An iterative sparseness maximization scheme is proposed to solve the problem of this model. In the scheme, the analysis sparse representation problem can be cast into row-to-row optimizations with respect to the analysis dictionary, and then the quadratic programming (QP) technique is used to optimize each row. Then, we use ℓ1 norm as the sparsity measure to learn an analysis dictionary from nonnegative signals in analysis sparse model. In addition, we adopt the Euclidean distance as the error measure in the formulation. What is more, we also consider the normal sparse representation with analysis model for general signals containing nonnegative and negative elements. We propose to learn an analysis dictionary from the signals using an optimization formulation with orthogonal constraint. Stiefel manifold is a feasible and efficient method to solve the problems with orthogonal constraint, thus here we introduce this method to the dictionary update stage. In the sparse coding stage, to avoid the adjustment of the parameters of the formulation, we introduce indicator function to this stage. The indicator function is widely used to measure the error approximation in source separation and we first introduce this function to sparse representation. Numerical experiments on recovery of analysis dictionary show the effectiveness of the proposed algorithms.

Summary of the Dissertation Review Result

The research topic of the candidate is mainly on sparse representation of signal or image, which is related also to sparse coding, compressive sensing, information theory, and blind source separation, with many applications. Sparse representation with the analysis model is a new trend of research that has been focused by the candidate.

Her contributions are 3-fold: The first contribution is to the area of dictionary learning for sparse representation of signals. She proposed algorithm utilizes the summation of blocked determinant-type of sparseness measure, which is a novel sparse measure, as the sparse constraint. This new sparseness measure shows some special properties that result in higher accuracy in sparse representation. The research has been published in Digital Signal Processing, a major journal.

(10)

- 8 -

As the second contribution, she proposed algorithm utilizes Euclidean distance as the error measure with the ℓ1 norm as sparse constraint for learning an analysis dictionary with the analysis sparse model, which is novel. For the nonnegative signals, she show that the problem becomes an optimization of a smooth convex function. This was published by journal called Information Engineering Express.

As the third contribution, she addressed the general sparse representation problem for the signal without nonnegative limitation with the analysis model. The problem was cast as an optimization of sparsity-promoting cost function with an orthogonal constraint. Then she proposed the optimization on the Stiefel manifold for the dictionary updating, which is novel. In the sparse coding stage, she introduced indicator function that can lead less model parameters, which is also novel. She also gave some applications. This has been submitted to IEEE Transactions on Signal Processing.

The publications of the candidate satisfy the regulation for PhD. As a highlight, she won the Best Paper Award in 2015 IEEE International Conference on Digital Signal Processing.

(11)

- 9 - Name

氏名

呉一郎

WU, Yilang（ウーイーラン）

学位記番号

甲CI博第54号

論文題目

A Support Platform for Collaborative Workflow based on Seamless Repository

シームレスなリポジトリに基づく共同作業のサポートプラットフォーム

University of Aizu, Prof. TEI, S. (Chief Referee)

University of Aizu, Prof. BHALLA, S.

University of Aizu, Associate Prof. YEN, N.

University of Aizu, Associate Prof. LI, P.

会津大学教授程子学（主査）

会津大学教授ｻﾊﾞｼｭﾊﾞｰﾗ会津大学准教授嚴昱文会津大学准教授李鵬

(12)

- 10 -

Abstract

Teamwork participants are always in demand of better working and collaboration support. The mobile cloud network has empowered the teamwork to be more pervasive by easing the spatial and temporal constrains. SNS and big data enable a verity of support tools or systems for supporting teamwork.

However, the collaborative workflow gaps still commonly exist in working and collaboration among co-workers who are familiar with different support systems.

This dissertation aims at bridging the collaborative workflow gaps by providing support of seamless integration and knowledge correlating. The different but persistent personal preferences of using the support systems require new support of seamless integration. And also the different background knowledge and the different purposes of utilizing knowledge require the support of knowledge correlating. Therefore, a novel support platform is developed through a seamless integration of multiple support systems and knowledge correlating to solve the following issues.

• Seamless Integration using a three-layered architecture – Support of Sharing to reduce the gap of information.

– Support of Interconnection to reduce the gap of communication.

– Support of Visualization to reduce the gap of representation.

• Knowledge Correlating using the terms-frequency and chained links-ratio (TFCLR) measure – Support of Correlation measure to reduce gap of knowledge.

Comparing with other support systems, the seamless integration in this platform has better functionality in sharing, interconnection, and visualization. And comparing with other collaboration measure, the TFCLR measure achieves better performance in information coverage and usability, and also has tolerable performance in speed and feasibility.

Summary of the Dissertation Review Result

This dissertation is for the purpose of bridging the gap in collaborative workflow. It first major contribution is the seamless integration of multiple support systems as seamless repository by providing new supports, including support of sharing to reduce the information gap, support of interconnection to reduce the communication gap, and support of visualization to reduce the representation gap. And its second major contribution is knowledge correlating to reduce the knowledge gap by implementing a new correlation measure, which integrates both the contextual and relational correlations based on terms-frequency and chained links-ratio of knowledge objects.

Furthermore, the proposed support platform has been successfully applied to a variety of case studies to show its usability and significance.

This research is a challenging work, and the issues are clearly defined. The support platform is well

(13)

- 11 -

designed and demonstrated in useful scenarios. The contribution in system integration and correlation measure is significant comparing with other surveyed approaches.

The candidate has very good fundamental knowledge in computer science and computer engineering, and his speaking and listening is very  good to conduct the presentation and Q&A session.

Referees gave comments and asked questions from different professional aspects. The candidate’s response to questions and comments are well presented, and reflected in dissertation. All referees satisfy this work, and agree that this dissertation is qualified for an academic degree.

(14)

- 12 - Name

氏名

油井宏昭

YUI, Hiroaki（ヒロアキユイ）

学位記番号

乙論博第4号

論文題目

Efficient Algorithms for Graph Partitioning and Back Propagation in Numerical Applications

数値解析アプリケーションにおけるグラフ分割とバックプロパゲーションのための効率的なアルゴリズム Dissertation Review Committee Members

論文審査委員

University of Aizu, Prof. BHALLA, S. (Chief Referee)

University of Aizu, Senior Associate Prof.

NISHIMURA, S.

University of Aizu, Prof. PAIK, I.

University of Aizu, Senior Associate Prof.ASAI, N.

University of Aizu, Special Honorary Professor OSANO, M.

会津大学教授ｻﾊﾞｼｭﾊﾞｰﾗ（主査）

会津大学上級准教授西村憲会津大学教授白寅天会津大学教授浅井信吉

会津大学特別栄誉教授小佐野峰忠

(15)

- 13 -

Abstract

Nowadays, the amount of data used in mapping, in mobile devices, and in genomic and astronomic sciences grows day by day in proportion to the spread of computers and mobiles equipped with a variety of sensors. To handle this extraordinary amount of information, it is important to analyze these data not only in the field of computer science but also in other science fields. However, algorithms for analyzing these data have led to considerable operating costs, and have yet to achieve complete accuracy. In data science, research to reduce the operating costs of data analysis using such algorithms, and to improve their accuracy, has already begun. Recently algorithms for analysis of these data are incurring smaller operating costs and offering improved accuracy.

This thesis presents two new algorithms for analyzing data more efficiently. The first algorithm reduces operating cost when the algorithm successively repeats to solve a system of linear equations by substitution. The second algorithm improves the accuracy of a learning algorithm in a neural network (NN).

The algorithm for solving a system of linear equations is used not only in data analysis, but also in other science fields, and so is useful in a wide range of applications. There are two common methods to solve a system of linear equations: a direct method and an iterative method. Direct methods compute the exact solution in a finite number of arithmetic operations, considering numerical rounding errors. Iterative methods, on the other hand, compute a sequence of approximate solutions, which approaches the exact solution.

This thesis treats one direct method, namely nested dissection (ND). ND removes a set of vertices, called a separator, from a graph, thus creating two new subgraphs after a sparse matrix in a system of linear equations has transformed the graph. According to the partitioning of the graph, ND orders rows and columns in matrices. ND solves the system of linear equations. The algorithm can be viewed as a recursive sub-division algorithm.

The first algorithm presents a graph partitioning for solving a system of linear equations more efficiently. The graph partitioning is a method to partition a graph into smaller subgraphs, according to the special features. This thesis presents a new graph-based algorithm. It is called a Minimum-Spanning-Tree Longest Path (MST-LP) algorithm. The algorithm is organized into five phases. The first phase sets a weight on each edge of a graph. The methods to set a weight have three criteria such as maximum-degree criterion, minimum-degree criterion and random-criterion. The second phase constructs a minimum spanning tree. The third phase finds the longest path in the minimum spanning tree. The fourth phase traverses vertices on the longest path, until the operating cost is minimized for solving a system of linear equations.

The last phase optimizes the size of the separator by removing redundant vertices, thus

(16)

- 14 -

reducing the operating cost. The MST-LP algorithm has special features. Compared with previous algorithms, the MST-LP is simple, easy to analyze, and easy to implement. The MST-LP runs in edge size linear time. If the graph is planar, the MST-LP is superior to previous algorithms.

The second algorithm minimizes a mean square error between target values and computed values in a global domain. NN is an important method in computer science, because NN is applicable not only for data analysis but also for demand forecasting. Backpropagation (BP) is one of the statistical learning models in NN, and updates the weights on the connection from the output units to the input unit.

BP usually uses gradient descent as a standard method. This method still has two problems.

The first problem is slow convergence for finding a minimum value if the learning rate is not optimal. The second problem is finding a minimum value in a global domain. Solving these problems, the second algorithm proposes a new hybrid algorithm for BP in NN. It is called a Hybrid quasi-Newton method Simulated Annealing (Hybrid QNSA). It combines the quasi-Newton method with the simulated annealing algorithm. The QNSA hybrid algorithm takes full advantage of the quasi-Newton method and simulated annealing, because the algorithm can find a minimum error in a global domain with a fast convergence, unlike a standard method. When the Hybrid algorithm identifies a minimum value, the algorithm must find a root in a derivative of an error. The first phase finds a root of a derivative of error by the quasi-Newton method. The second phase finds another root of a derivative of error, starting from another point by simulated annealing. The algorithm finds a minimum value, substituting both values into an error function. The algorithm repeats this process for finding a minimum value in a global domain.

In the future, there still remains research on taking full advantage of the quasi-Newton method. We would like to apply graph partitioning for the network of other neural networks.

Summary of the Dissertation Review Result

The candidate has made contributions to two different research fields in computer science.

One is the development of a novel graph-partitioning algorithm and the other is the proposal of a new learning method for neural networks. Both of the topics are important in the applications of big-data analysis.

The graph-partitioning algorithm described in the dissertation is called a

Minimum-Spanning-Tree Longest Path (MST-LP) algorithm. It is intended for use in solving

a system of linear equations efficiently with a divide-and-conquer strategy. Compared with

previous algorithms, the algorithm is simpler, easier to analyze and easier to implement. The

(17)

- 15 -

algorithm is evaluated with a sufficient number of graphs from various applications.

Depending on the type of graphs, the algorithm shows superiority to existing algorithms, from which the significance of the work is acknowledged.

The second contribution of the dissertation is a hybrid learning method for neural networks.

The method, called Hybrid QNSA, combines the Quasi-Newton method with and simulated annealing. Unlike common gradient-descent methods, Hybrid QNSA seeks for the global minimum of the loss function. The method is interesting but in order to recognize its importance, further evaluation of the algorithm is needed.

At the preliminary review, one-hour presentation on the dissertation was given by the

candidate. After the presentation, some modifications including the improvement of

explanation style, further comparison with existing methods, and better explanation of the

relation between the two topics are requested by the reviewing committee members. At the

final review, the committee unanimously agreed on passing the candidate because two journal

papers are accepted and because the issues addressed in the preliminary review were

improved to an acceptable level. The committee again requested in the final review some

minor modifications of the dissertation, which are applied in the final revision of the

dissertation.

(18)

- 16 -

博士学位論文 Doctoral Dissertation

内容の要旨及び審査結果の要旨 Dissertation Abstract

and

Summary of the Dissertation Review Result

第28号

The Twenty-eighth Issue

平成２８年９月 September, 2016

発行会津大学

〒965-8580 福島県会津若松市一箕町鶴賀 TEL: 0242-37-2600

FAX: 0242-37-2526 THE UNIVERSITY OF AIZU Tsuruga, Ikki-machi Aizu-Wakamatsu City

Fukushima, 965-8580 Japan

博 士 学 位 論 文

Doctoral Dissertation

Dissertation Abstract and

Summary of the Dissertation Review Result

The Twenty-eighth Issue

September, 2016

The University of Aizu

Preface

The Chinese character, “甲”, at the beginning of the diploma number represents that an

individual has been granted the degree in accordance with the provisions provided for in

Paragraph 4-1 of the Ruling Of Degrees (what is called “Katei Hakase,” or the Doctoral

Degree granted by the University at which the grantee was enrolled.).

Contents

Abstract

Summary of the Dissertation Review Result

Abstract

Summary of the Dissertation Review Result

Abstract

Summary of the Dissertation Review Result

Abstract

The last phase optimizes the size of the separator by removing redundant vertices, thus

reducing the operating cost. The MST-LP algorithm has special features. Compared with previous algorithms, the MST-LP is simple, easy to analyze, and easy to implement. The MST-LP runs in edge size linear time. If the graph is planar, the MST-LP is superior to previous algorithms.

BP usually uses gradient descent as a standard method. This method still has two problems.

In the future, there still remains research on taking full advantage of the quasi-Newton method. We would like to apply graph partitioning for the network of other neural networks.

Summary of the Dissertation Review Result

The candidate has made contributions to two different research fields in computer science.

One is the development of a novel graph-partitioning algorithm and the other is the proposal of a new learning method for neural networks. Both of the topics are important in the applications of big-data analysis.

The graph-partitioning algorithm described in the dissertation is called a

Minimum-Spanning-Tree Longest Path (MST-LP) algorithm. It is intended for use in solving

a system of linear equations efficiently with a divide-and-conquer strategy. Compared with

previous algorithms, the algorithm is simpler, easier to analyze and easier to implement. The

algorithm is evaluated with a sufficient number of graphs from various applications.

Depending on the type of graphs, the algorithm shows superiority to existing algorithms, from which the significance of the work is acknowledged.

The second contribution of the dissertation is a hybrid learning method for neural networks.

At the preliminary review, one-hour presentation on the dissertation was given by the

candidate. After the presentation, some modifications including the improvement of

explanation style, further comparison with existing methods, and better explanation of the

relation between the two topics are requested by the reviewing committee members. At the

final review, the committee unanimously agreed on passing the candidate because two journal

papers are accepted and because the issues addressed in the preliminary review were

improved to an acceptable level. The committee again requested in the final review some

minor modifications of the dissertation, which are applied in the final revision of the

dissertation.

博士学位論文