宮崎 修一

Given the same amount of hardware resource and bandwidth limitation, networks with optimal configurations enable Internet service providers to provide a lower end-to-end latency service for clients to use. In the case of designing VLAN, due to the lack of effective automation tool at present, most configurations are still done manually, hence it becomes hard to ensure the optimum of a designed network especially when the scale of the given network grows larger. In this paper, our goal is to construct an automated procedure for embedding multiple VLANs above the same physical network by first defining the performance criteria and then introducing the Minimum Diameter Multiple Steiner Tree problem as the model of this problem. We propose several greedy algorithms to solve the model problem as well as evaluating the performance results obtained by simulated data. Our result shows that an embedding order of higher bandwidth requirement first has a higher chance to reduce the latency sum of multiple VLANs in a full mesh network.

Given the same amount of hardware resource and bandwidth limitation, networks with optimal configurations enable Internet service providers to provide a lower end-to-end latency service for clients to use. In the case of designing VLAN, due to the lack of effective automation tool at present, most configurations are still done manually, hence it becomes hard to ensure the optimum of a designed network especially when the scale of the given network grows larger. In this paper, our goal is to construct an automated procedure for embedding multiple VLANs above the same physical network by first defining the performance criteria and then introducing the Minimum Diameter Multiple Steiner Tree problem as the model of this problem. We propose several greedy algorithms to solve the model problem as well as evaluating the performance results obtained by simulated data. Our result shows that an embedding order of higher bandwidth requirement first has a higher chance to reduce the latency sum of multiple VLANs in a full mesh network.

Given the same amount of hardware resource and bandwidth limitation, networks with optimal configurations enable Internet service providers to provide a lower end-to-end latency service for clients to use. In the case of designing VLAN, due to the lack of effective automation tool at present, most configurations are still done manually, hence it becomes hard to ensure the optimum of a designed network especially when the scale of the given network grows larger. In this paper, our goal is to construct an automated procedure for embedding multiple VLANs above the same physical network by first defining the performance criteria and then introducing the Minimum Diameter Multiple Steiner Tree problem as the model of this problem. We propose several greedy algorithms to solve the model problem as well as evaluating the performance results obtained by simulated data. Our result shows that an embedding order of higher bandwidth requirement first has a higher chance to reduce the latency sum of multiple VLANs in a full mesh network.Given the same amount of hardware resource and bandwidth limitation, networks with optimal configurations enable Internet service providers to provide a lower end-to-end latency service for clients to use. In the case of designing VLAN, due to the lack of effective automation tool at present, most configurations are still done manually, hence it becomes hard to ensure the optimum of a designed network especially when the scale of the given network grows larger. In this paper, our goal is to construct an automated procedure for embedding multiple VLANs above the same physical network by first defining the performance criteria and then introducing the Minimum Diameter Multiple Steiner Tree problem as the model of this problem. We propose several greedy algorithms to solve the model problem as well as evaluating the performance results obtained by simulated data. Our result shows that an embedding order of higher bandwidth requirement first has a higher chance to reduce the latency sum of multiple VLANs in a full mesh network.

The Hospitals/Residents problem is a many-to-one generalization of the well-known Stable Marriage problem. Its instance consists of a set of residents, a set of hospitals, each resident's preference list, each hospital's preference list, and each hospital's capacity (i.e., the number of available positions). It asks to find a stable matching between residents and hospitals. In this paper, we consider the problem of deciding, given residents' preference lists and a matching, whether there are hospitals' preference lists that make a given matching stable. We call this problem Stable Hospital's Preference List problem (SHPL). It is easy to see that there always exists a solution if we allow arbitrary preference lists of hospitals. Considering more suitable situations, we pose a restricted version, called k-SHPL, in which there are only k kinds of preference lists of hospitals. We show that 1-SHPL is solvable in polynomial time, while k-SHPL is NP-complete for any k such that 2 ≤ k ≤ n1-ε, where n is the number of residents and ε is any positive constant. We also present four heuristics algorithms (first-fit algorithms) for 2-SHPL. We implement these algorithms and present a computational study using random instances.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.23(2015) No.2 (online)------------------------------The Hospitals/Residents problem is a many-to-one generalization of the well-known Stable Marriage problem. Its instance consists of a set of residents, a set of hospitals, each resident's preference list, each hospital's preference list, and each hospital's capacity (i.e., the number of available positions). It asks to find a stable matching between residents and hospitals. In this paper, we consider the problem of deciding, given residents' preference lists and a matching, whether there are hospitals' preference lists that make a given matching stable. We call this problem Stable Hospital's Preference List problem (SHPL). It is easy to see that there always exists a solution if we allow arbitrary preference lists of hospitals. Considering more suitable situations, we pose a restricted version, called k-SHPL, in which there are only k kinds of preference lists of hospitals. We show that 1-SHPL is solvable in polynomial time, while k-SHPL is NP-complete for any k such that 2 ≤ k ≤ n1-ε, where n is the number of residents and ε is any positive constant. We also present four heuristics algorithms (first-fit algorithms) for 2-SHPL. We implement these algorithms and present a computational study using random instances.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.23(2015) No.2 (online)------------------------------

「2015年度 情報処理学会関西支部 支部大会」 2015年9月28日(月) 10：00-16：45 大阪大学中之島センター複数の電力源がある場合に，電力を効率的に使うためには，電力を家電にうまく割り当てる必要がある．この問題は割当制約つき複数ナップサック問題として定式化できる．本研究では，既存の近似アルゴリズムを実装し，実験的な評価をおこなった．また，それらのアルゴリズムを改良することを目指して，いくつかの変更を提案し，それらについても実験をおこなった．最後に，実用的な規模を想定して例題を生成し，各アルゴリズムの性能を比較した．

「2015年度 情報処理学会関西支部 支部大会」 2015年9月28日(月) 10：00-16：45 大阪大学中之島センター本研究では、帯域制限のあるネットワークに複数のシュタイナー木を詰め込む問題を考察する。整数計画問題への定式化を用いた解法を提案及び実装し、その性能を実験により評価する。

本稿では, k個のパケットからなるフレーム転送量最大化問題(k-FTM)と呼ばれる,ネットワーク上におけるスイッチのオンラインバッファ管理問題の一問題について考える.本問題は,大きなフレームがk個のパケットに分割されてインターネット上で転送され,受信者はk個全てのパケットを受信できたときに限りフレームを再構成可能という状況をモデル化したものである. Kesselmanらは本問題に対して, k=2の場合でさえ任意のアルゴリズムの競合比は発散することを示した.そこで,入力に制限を加えたk-FTM (k-OFTM)を考え,任意のバッファの大きさB(≧k)に対して,その競合比が高々(2kB)/([B/k])+kとなるアルゴリズムを考案した.また,彼らは2B≧kかつkが2の冪のとき,任意の決定性アルゴリズムの競合比の下限B/([2B/k])=Ω(k)を示した.本稿において,我々はk-OFTMに対する競合比の上限と下限を改良している.主要な結果として,彼らの上界O(k^2)を(5B+[B/k]-4)/([[B/k]/2])=O(k)へ改良し,下界Ω(k)に漸近的に一致させている.また,任意のk≧2と任意のBに対する,決定性アルゴリズムの競合比の下限2k-1と,任意のk≧3と任意のBに対する,確率アルゴリズムの初めての非自明な競合比の下限k-1を与える.

電子メールが広く普及し，メールが宛先に遅延なく配送されることが望まれてきている．意図しない大量メールが短時間にメール中継システムに送信されることは珍しくない．これらのメールはしばしば，システムの負荷を超過させ，ネットワーク帯域を占有する原因となり，このような状況ではメール配送に重大な遅延をもたらす．本稿ではハシシュテーブルで管理されたエンベロープ From アドレスとエンベロープ To アドレスの組を用いて効率的に大量のメールを検知するメール中継システムを提案する．提案システムではエンベロープ From アドレスとエンベロープ Ｔo アドレスの組数を数え，もし，ある短い期間で特定の組の配送数が事前に設定した閾値を超えた場合，これらのペアが大量メールの原因とみなす．エンベロープ From アドレスとエンベロープ To アドレスを管理するハッシュテーブルの肥大化を低減するために複数のハッシュテーブルを使用し，これらのハッシュテーブルを時間毎に分け，ある決まった間隔でエントリーを空にする．また，事前に大量のメールの判断するためにブロックリストも準備する．最終的にシステムを実装し評価する．With the wide use of e-mail, it has become commonly expected that e-mails are delivered to recipients immediately. It is not rare that a huge amount of e-mails are delivered to a mail transfer system in a very short time unintentionally. Such e-mails sometimes causes excessive load to the system and to increase traffic of network, and e-mails are delivered with serious delay in such situations. We propose a mail transfer system to detect efficiently such e-mail with each pair of envelope-from and envelope-to address managed by a hash table. In proposed system, the number of each pair envelope-from and envelope-to address is counted, and if the number of the delivery including a specific pair (envelope-from, envelope-to address) during a short period exceeds a pre-specified threshold, we regard this pair as a cause of a huge amount of e-mails. We prepare multiple hash tables which managed envelope-from and envelope-to address to prevent an increase in scale of the hash table, and we divide such hash tables every time and empty all entries at fixed intervals. We also prepare for the blocklist to judge a huge amount of e-mails beforehand. We implement the proposed system and evaluate it.

電子メールが広く普及し,メールが宛先に遅延なく配送されることが望まれてきている.意図しない大量メールが短時間にメール中継システムに送信されることは珍しくない.これらのメールはしばしば,システムの負荷を超過させ,ネットワーク帯域を占有する原因となり,このような状況ではメール配送に重大な遅延をもたらす.本稿ではハッシュテーブルで管理されたエンベロープFromアドレスとエンベロープToアドレスの組を用いて効率的に大量のメールを検知するメール中継システムを提案する.提案システムではエンベロープFromアドレスとエンベロープToアドレスの組数を数え,もし,ある短い期間で特定の組の配送数が事前に設定した閾値を超えた場合,これらのペアが大量メールの原因とみなす.エンベロープFromアドレスとエンベロープToアドレスを管理するハッシュテーブルの肥大化を低減するために複数のハッシュテーブルを使用し,これらのハッシュテーブルを時間毎に分け,ある決まった間隔でエントリーを空にする.また,事前に大量のメールの判断するためにブロックリストも準備する.最終的にシステムを実装し評価する.

With the wide use of e-mail, it has become commonly expected that e-mails sent are delivered to recipients immediately. It is not rare that a huge amount of e-mails are posted to a mail transfer system in very short time unintentionally, due to misconfiguration such as an e-mail loop. Such e-mail flood increases the load of the mail transfer system, and causes serious delays in e-mail delivery of the system. We propose a mail transfer system with resiliency against e-mail flood. In the proposed system, the number of each pair of envelope-from and envelope-to is counted. If the number of sessions including a specific pair (envelope-from, envelope-to) during a short period exceeds a pre-specified threshold, we regard this pair as a cause of a huge amount of e-mails, and reject e-mails including this pair after that. In this way, a huge amount of e-mails are selectively restricted without affecting transfer of ordinary e-mails.

座席予約問題では駅s_1から駅s_kまでのk駅に停まるn席の座席を持った列車を考える.各乗客は出発駅s_iから到着駅s_j(1≦i≦j≦k)までのチケットを要求する.オンラインアルゴリズムは,未来の要求を知らずに各乗客をn席の座席の1つに割り当てる必要がある.座席予約問題の目的はチケットの売上合計額を最大化することである.チケットの価格設定により,座席予約問題には2つのモデルがある.一つは単一価格問題であり,もう一つは比例価格問題である.我々は,両方のモデルにおいて,競合比の上下限を改良した.単一価格問題に関しては,上限を8/(k+5)から4/(k-2√<k-1>+4)に改良した.また,Worst-Fitアルゴリズムの上限も4/(k-1)から2/(k-2√<k-1>+2)に改良した.さらに,比例価格問題に関しては,上限を(4+2√<13>)/(k+3+2√<13>)((&sime;11.2/(k+10.2))から(3+√<13>)/(k-1+√<13>)((&sime;6.6/(k+2.6))に改良し,下限を1/(k-1)から2/(k-1)に改良した.

近年,電子メールの重要性の高まりとともに,電子メールが正しく送達したことの証明への需要が高まっている.電子メールでの配達証明は第三者機関を仲介する手法としない手法に分類できるが,後者は前者に比べて運用コストや柔軟性等の点で利点が多い.しかしその研究の多くはプロトコルの提案に留まっており,システムの実運用上の検討を十分に行っている研究は少ない.本研究では,送信者と受信者間で完結する手法に焦点を置き,公開鍵基盤を利用できる仮定で,すべての通信に署名を付与するものとする.その前提の下では,単純に秘密情報をビットごとに送信するだけで配達証明に必要な安全性の要件を十分に満たせることを示した.さらに本プロトコルを利用した配達証明付き電子メールシステムを設計し,実運用上の検討を行った.

オンライン問題の一つにk-Canadian Traveller Problem (k-CTP)がある.k-CTPとは,枝に重みの付いたグラフG=(V,E)上の与えられた頂点sからtまでの最短経路問題である.オンラインアルゴリズムは前もってグラフの構造と全ての枝のコストを知っている.しかし,グラフ上で高々κ個の枝が封鎖されており,枝が封鎖されているか否かはその枝に隣接する頂点に辿り着いた時に初めて分かる.Westphalは任意のグラフに対して,競合比が2k+1になることを示した.本稿では,枝コストに制限をかけた場合のk-CTPの競合比解析を行う.具体的には,完全グラフに対し,枝コストが全て1の場合,枝コストが三角不等式を満たす場合に対して,それぞれ競合比が(k+1)/2,kになることを示す(グラフの連結性を保証するために,全封鎖数kは|V|-2以下とする).

安定結婚問題で不完全希望リストを許すと,同じ例題に対する全ての安定マッチングは同サイズになる.しかし,安定性を無視すると,一般にはそれよりも大きなサイズのマッチングが存在する.Biroらは,最大サイズのマッチングの中で出来るだけブロッキングペア数の少ないマッチングを求める問題を提案した.彼らは,(i)この問題がNP困難であり,任意の正定数εに対してP≠NPの仮定の下でn^<1-ε>-近似アルゴリズムを持たないこと(nは例題中の男性の数),(ii)希望リストの長さを3以下に制限してもNP困難であり,ある定数δ>1が存在しP≠NPの仮定の下でδ-近似アルゴリズムを持たないこと,(iii)片側の性(例えば男性)の希望リストの長さが全て2以下ならば多項式時間で解けること,を示した.本論文では,上記(ii)の近似不可能性を,定数δからn^<1-ε>(εは任意の正定数)へと改良した.

安定マッチング問題とは,男女の集合と,各人の異性に対する希望リストが与えられたとき,「安定性」と呼ばれる性質を満たす男女間のマッチングを求める問題である.本問題は,研修医の病院配属や生徒の学校への配属,大学における学生の研究室配属等,応用の広い問題である.本講演では,本問題の紹介を行うと共に,関連するいくつかの問題に対する最近の話題を,著者の研究グループが得た成果を中心に紹介する.

社会の電子メールへの依存の高まりから,メールの配達内容証明を行うことができるプロトコルの需要が高まっている.郵便局のような仲介者の役割を果たすサービスの提供が始まっているが,コストや信頼性の点から一般への普及には至っていない.本研究では1対1で仲介者無しに秘密開示を行うと同時にReceiptを受け取ることができるプロトコルを,岡本らが提案する段階的秘密交換手法を用いて設計し,システムとして実装するための検討を行った.

オンラインバッファ管理問題は,近年のネットワークにおける主要な論点となっているQoS (Quality of Service)保証実現のための,スイッチのキュー管理をオンライン問題として定式化した問題であり,様々なモデルが考案されている。本論文ではAzarらによって考案されたQoSネットワーク上のマルチキュースイッチを扱ったモデルを取り上げる.Azarらは本モデルの競合比の上限を得るために,"the relaxed model"というモデルを導入している.我々はrelaxed modelに対するオンラインアルゴリズムDSを提案することにより競合比を改良し,その結果としてマルチキュースイッチモデルの競合比の改良を行った.以下は本論文におけるマルチキュースイッチモデルの競合比の改良の一例である.(i)プリエンプション不可能,かつパケットの価値が2値であるモデルにおいて,十分大きなBに対して,決定性アルゴリズムの競合比の上限を4から3.177に改良した.Bは各キューが同時に保持できるパケットの最大数である.(ii)プリエンプション不可能,かつパケットの価値が2値であるモデルにおいて,十分大きなBに対して,乱択アルゴリズムの競合比の上限が高々(17)/2-√<30>&sime;3.023であることを示した.

安定結婚問題は,GaleとShapleyによって提案されたマッチングの問題である.任意の例題について,解が存在し,それを見つける多項式時間が存在することが知られている.しかし,このアルゴリズムによって得られるマッチングは「男性最適」,つまり,男性にとっては好ましいが女性にとっては好ましくないマッチングである(逆に,男女の役割を入れ替えれば,女性最適なマッチングになる).GusfieldとIrvingによって提案された男女平等安定マッチング問題は,男女両者にとって「公平な」安定マッチングを求める,つまり,男性側の不満足度の和が女性側の不満足度の和になるべく近づくような安定マッチングを求める問題である.この問題は,強NP困難であることが知られている.本稿では,男女平等安定マッチング問題に対して,ほぼ最適な解を求める多項式時間アルゴリズムを与える.さらに,評価指標を一つ増やして,男女平等(sex-equality)の観点でほぼ最適なもののうち,全体の公平さ(egalitarian)が最小の安定マッチングを求める問題を考える.我々は,この問題がNP困難であることを示し,この問題に対して近似度が2より良い多項式時間アルゴリズムを構築した.

安定ルームメイト問題は,希望リストに基づいて「安定性」を満たすように,2N人の人間をN組のペアに分割する問題である.安定ルームメイト問題は解を持たない場合もあるが,解を持つか否かを判定し,持つ場合には解を見つける多項式時間アルゴリズムが知られている.本研究ではこの問題を拡張し,3N人の人間をN組のトリプルに分割する問題を提案する.そして,この問題において解の存在を判定する問題がNP完全であることを示す.

オンライングラフ探索問題における目的は,探索者が未知のグラフの全ての頂点を訪問することによりグラフ構造を調査し,最後に出発点に戻ることである.ある辺の存在ならびにその長さは,探索者がその端点を訪れるまで未知である.目的達成に要した総移動距離を探索者のコストとして定める.探索対象を平面グラフとする場合,16競合のアルゴリズムが知られている.朝廣らは,探索対象をサイクルグラフとする場合において,1.5競合のアルゴリズムを与えるとともに,(1.25-ε)競合のアルゴリズムは存在しないことを示した(ここでeは任意の正定数である).本稿では,サイクルグラフに対する 最適なオンラインアルゴリズムを与える.すなわち,1+√<3>/2(&sime;1.366)競合のアルゴリズムを与えるとともに,(1+√<3>/2-ε)競合のアルゴリズムは存在しないことを証明する(上記と同様,εは任意の正定数である)

グラフ上での地図作成問題とは,探索者が未知のグラフの全ての頂点を訪問することによりグラフ構造を調査する問題である.探索者は辺の存在とその長さをその端点を訪れるまで判らないとする.探索者は,できるだけ短い経路を通ることにより全ての頂点と辺を調査して,出発点まで戻って来なければならない.本問題に対する最も単純な方法の一つは,最近傍アルゴリズム(NN)であり,まだ訪れていない頂点の中で探索者の現在の場所から最も近い場所に移動する戦略である.重み付き最近傍アルゴリズム(WNN)は,NNの拡張であり,ある重み付きの距離により次の移動場所を決める.平面グラフにおいては,重み3であるWNNが16競合であることが知られている.本稿ではサイクルグラフについては,NNの競合比が1.5となること,その解析が厳密であることを示す.また,サイクルグラフに対してはWNNの中でNNが最適であることを示す.さらに,本問題に対しては,1.25競合よりも良いアルゴリズムが存在しないことを示す.