# 概要考案用メモ

###### tags: `研究まとめ`

## 題目
分流型2リンクモデルにおける準最適HBHファイル配送スケジューリング

## 100字概要
最下層が複数ノードへ分岐する分流型モデルにおいて，分岐なしでの既存準最適方式を基に，準最適方式を提案する．さらに，リンク帯域を変化させて計算機実験を行い，準最適性，及び，従来手法に対する向上性能を，定量的に示す．(106文字)

### 変遷
<details>

#### 字数制限なしver
2リンクモデルHBHファイル配送システムにおいて，コンテンツに関するリクエスト数と，リクエストから配送完了までに生じる時間の，積の総和である延べサービス時間低減スケジューリングに関して，準最適アルゴリズムが提案されている．
　本研究では，2リンクモデルにおいて想定されていなかった，最下層が複数ノードへ分岐する形態を，分流型モデルと定義し，適用領域の拡張に取り組む．そこで，分岐なしでの既存準最適アルゴリズムに，分岐された複数ノードからのリクエスト及びリンク帯域比を考慮した重みを追加拡張した，分流型モデルにおける準最適アルゴリズムを提案する．さらに，リンク帯域をパラメータとして変化させた計算機実験を行い，提案手法により得られる準最適性能，および，提案手法とFIFOやSRPTといった従来アルゴリズムとの延べサービス時間低減性能比較による，提案手法による向上性能を，定量的に示す．(391文字)

1. 2リンクモデルHBHファイル配送システムにおける，延べサービス時間低減スケジューリングに関して，準最適アルゴリズムが提案されている．
　本研究では，最下層が複数ノードへ分岐する形態を，分流型モデルと定義し，適用領域の拡張に取り組む．そこで，分岐なしでの既存準最適アルゴリズムに，分岐された複数ノードからのリクエスト及びリンク帯域比を考慮した重みを追加拡張した，準最適アルゴリズムを提案する．さらに，リンク帯域をパラメータとして変化させた計算機実験を行い，提案手法の準最適性および，提案手法と従来アルゴリズムとの延べサービス時間低減性能比較による，提案手法による向上性能を，定量的に示す．

2. 2リンクモデルHBHファイル配送システムにおける，延べサービス時間低減スケジューリングに関して，準最適アルゴリズムが提案されている．
　本研究では，最下層が複数ノードへ分岐する分流型モデルにおいて，分岐なしでの既存準最適アルゴリズムに，分岐された複数ノードからのリクエスト及びリンク帯域比を考慮した重みを追加拡張した，準最適アルゴリズムを提案する．さらに，リンク帯域をパラメータとして変化させた計算機実験を行い，提案手法の準最適性，および，従来アルゴリズムとの延べサービス時間低減性能の比較をもって，提案手法による向上性能を，定量的に示す．

3. 最下層が複数ノードへ分岐する分流型モデルにおいて，分岐なしでの既存準最適アルゴリズムに，分岐された複数ノードからのリクエスト及びリンク帯域比を考慮した重みを追加した，準最適アルゴリズムを提案する．さらに，リンク帯域を変化させて計算機実験を行い，提案手法の準最適性と，従来アルゴリズムとの延べサービス時間低減性能の比較し，提案手法による向上性能を，定量的に示す．

4. 最下層が複数ノードへ分岐する分流型モデルにおいて，分岐なしでの既存準最適方式を基に，準最適方式を提案する．さらに，リンク帯域を変化させて計算機実験を行い，提案手法の準最適性と，従来アルゴリズムとの延べサービス時間低減性能を比較し，提案手法による向上性能を，定量的に示す．

</details>

<details><summary>没案</summary>

1. HBHファイル配送システムに関して、コンテンツに関するリクエスト数と配送にかかる時間の積の総和である延べサービス時間を低減するためのスケジューリングが求められている。2リンクモデルにおいては、中間ノードでの待ち時間を近似したアルゴリズムが提案されており、これを分岐ありモデルへ拡張することを検討する。今回扱う、最下層ノードが複数ある分流型モデルでは、分岐なしモデルにおける近似アルゴリズムに追加ノード分を考慮したパラメータを加算することで近似できることを示す。また、リンクごとの帯域の変動による近似精度を算出し、帯域変動によるスケジューリングへの影響と単純2リンクモデルとの差異を評価する。(231文字)

2. HBHファイル配送に関し、分岐あり2リンクモデルでの延べサービス時間を低減するスケジューリングを検討する。今回扱う最下層ノードが複数ある分流型モデルでは、分岐なしでの場合に追加ノード分を追加することで拡張できることを示す。(112文字)

3. HBHファイル配送に関し、分岐あり2リンクモデルで延べサービス時間を低減するスケジューリングを検討する。今回扱う最下層ノードが複数ある分流型モデルの近似アルゴリズムは、分岐なしモデルにノードを追加した式で近似出来る事を示す。(112文字)

4. HBHファイル配送システムに関して、コンテンツに関するリクエスト数と配送にかかる時間の積の総和である延べサービス時間を低減するスケジューリングが求められている。2リンクモデルにおいては、中間ノードでの待ち時間を近似したアルゴリズムが提案されており、これを分岐ありモデルへ拡張することを検討する。今回扱う、最下層ノードが複数ある分流型モデルでは、分岐なしの場合における近似アルゴリズムに複数ノードであることを考慮したパラメータを追加することで同様に近似できることを示す。また、リンク帯域の条件を変化させたシミュレーションで近似アルゴリズムを精査し、帯域変動によるスケジューリングへの影響と単純2リンクモデルとの差異を評価する。(312文字)

5. 2リンクモデルHBHファイル配送システムに関して、コンテンツに関するリクエスト数と配送にかかる時間の積の総和である，延べサービス時間低減スケジューリングの準最適アルゴリズムが提案されている．これは、各ノード間のリンク帯域で重みづけされた単位ファイルサイズ当たりのリクエスト数の降順に送るというものである。
本研究では，分岐あり2リンクモデル拡張のうち，最下層ノードの複数分流型モデルに関して，分岐なしでの準最適アルゴリズムに，**分岐なしのモデルと比較して増加したノードのファイルサイズ当たりのリクエスト数を考慮することにより**，同様の準最適アルゴリズムが実現可能であることを理論的に示す。また，**リンク帯域やファイル数などの条件を変化させながら**，提案準最適アルゴリズムと単純2リンクモデルとの差異を評価し，**分流型が単純2リンクに拡張可能なことをシミュレーションの面からも示す**．(313文字)

6. 2リンクHBHファイル配送に関し，最下層が複数ノードへ分岐する分流型モデルでのスケジューリングを，既存手法を拡張した準最適アルゴリズムで実現する．また，リンク帯域を変化させた計算機実験で評価し，提案手法による延べサービス時間の低減性能が準最適であると示す．(128文字)

</details>

<details><summary>参考(赤岡さん)</summary>

題目
HBH最適ファイル配送方式の中間ノードにおける配送順序変更の可能性

概要
HBH最適ファイル配送方式における配送順序変更に関して，2リンクモデル及び
2コンテンツを対象とし，延べサービス時間低減の成立条件および上限値を示
す．さらに，その条件を満足する実環境は限られ，低減効果も小さいことを示す．

</details>

## 主張内容(原稿用メモ)
- 提案しているのは"分流型モデルにおけるスケジューリングを行うための準最適アルゴリズム"であること
- そのアルゴリズムは"分岐なしモデルに比べ、複数の最下層ノード分のリクエスト及びリンク帯域比"を考慮したものであること
- 評価は提案手法の"延べサービス時間の低減に関わる有効性"を示すために行っていること

### 原稿のポイント
1. 章立て