---
# System prepended metadata

title: 質問まとめ
tags: [研究まとめ]

---

# 質問まとめ

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

## 10/12の輪講を受けて
<details>

- 並列配送の方もよさそうだけど、なぜ延べサービス時間が短くなる直列を使うのか    
     
:arrow_right:延べサービス時間はリクエスト数(需要)を反映したものだから
![](https://i.imgur.com/vwxCabU.png)
    - **リクエスト数に大きな差があると…？**
    輪講中の例ではA,Bのファイル2種のリクエスト数が1,1であった場合だったが、例えばこれが100:1だった場合を考える。Aの方が100倍需要があるのに、並列配送だと回線帯域を等分しなければならない。そう考えると、全体として考えたときは"より需要が大きい方"を優先することが重要となる。

||ファイルA|ファイルB|延べサービス時間(直列)|延べサービス時間(並列)|
|--|--|--|--|--|
|リクエスト数|1|1|3t|4t|
|リクエスト数|100|1|102t|202t|

---

- ファイルサイズ同一の場合は$\sigma_i$などで配送順のパラメータが存在したが、可変環境でのwの式にはそれがなかった。配送順序は式のどことかかわるのか？
![](https://i.imgur.com/J2cWFAU.png)
数式を考える上での前提条件の記載を忘れていたが、そもそも今回の輪講で紹介した式は"**ファイル1,2…nの順に配送を行う場合の延べサービス時間**"を表すものである。
この前提のもと上の式(12)を見る。第2項はリクエスト数×ファイル配送時間であるから定数となる。一方、第1項の$\sum^{n}_{p=1}(r_{1,p}+r_{2,p})\sum^{p}_{q=1}s_q$はファイル配送順によって大小が左右される。

注釈:以下の考察は書き換えの可能性あり

<details><summary>第1項の最小化について</summary>

- リクエスト数に関して
$r_{1,p}+r_{2,p}=R_p$とする。これが降順のときに第1項のうち、配送順で大小が変化する$\sum^{n}_{p=1}R_p$が最小になることを示す。
以下の証明では、配送順序を表すパラメータとして$i_{(m)} \in\{1,2,…,n\}$をおく。
ここでは
$\forall m,i_{(m)} \in \{1,2,…,n\},m_1\neq m_2 \Rightarrow i_{(m_1)} \neq i_{(m_2)}$
$\sum^{n}_{p=1}i_{(m)}R_p\geq \sum^{k}_{m=1}mR_{m}$ となることを示す。

    (1)$n=1$のとき、(左辺)=(右辺)より自明。
(2)$n=k-1(1<k\leq n)$で成り立つとすると、次式が成り立つ。
    $\sum^{k−1}_{m=1}i_{(m)}R_m \geq \sum^{k−1}_{m=1}mR_{m}$

    ここで $n=k−1$ のとき $\forall i_{(m)} \in \{1,2,…,k−1\}$とし $n=k$ のとき，$\forall i_{(m)} \in \{1,2,…,k\}$とし、成り立つことを示す。

    $\sum^{k}_{m=1}\hat{i}_{(m)}R_m \geq\sum^{k−1}_{m=1}\hat{i}_{(m)}R_m+\hat{i}_{(k)}R_k$

    (a) $\hat{i}_{(k)}=k$ のとき
$\sum^{k}_{m=1}\hat{i}_{(m)}R_m \geq \sum^{k−1}_{m=1}\hat{i}_{(m)}R_m+kR_k=\sum^{k}_{m=1}mR_m$
したがって $n=k$ のときも成り立つ。

    (b) $\hat{i}_{(k)} \neq k \, (\hat{i}_{(k)} < k)$のとき$\hat{i}_{(s)}=k$ なる $s \in \{1,2,…,k−1\}$ が存在し、

    $\sum^{k−1}_{m=1}\hat{i}_{(m)}R_m+\hat{i}_{(k)}R_k\\
=\sum^{k−1}_{m=1,m \neq s}\hat{i}_{(m)}R_m+\hat{i}_{(s)}R_s+\hat{i}_{(k)}R_k\\
=\sum^{k−1}_{m=1,m \neq s}\hat{i}_{(m)}R_m+kR_s+\hat{i}_{(k)}R_k\\
\geq\sum^{k−1}_{m=1,m \neq s}\hat{i}_{(m)}R_m+\hat{i}_{(k)}R_s+kR_k$

    ここで
$\hat{i}_{(m)}=
\begin{cases}
\hat{i}_{(k)} (m=s) \\
\hat{i}_{(m)} (m\neq s)
\end{cases}$
とおくと、
$\sum^{k−1}_{m=1,m \neq s}\hat{i}_{(m)}R_m+\hat{i}_{(k)}R_s+kR_k \\
=\sum^{k−1}_{m=1}\hat{i}_{(m)}R_m+kR_k \\ 
\geq \sum^{k−1}_{m=1}mR_m+kR_k \\
= \sum^{k}_{m=1}mR_m$

    よって$n=k$のときも成り立つ。
以上から、$\sum^{k}_{m=1}i_{(m)}R_m \geq \sum^{k}_{m=1}mR_{m}$となる。

    これは、ファイルリクエストが$r_{1,p}+r_{2,p}=R_p$が降順になっている場合、この順番通りに配送を行うと$\sum^{n}_{p=1}R_p\sum^{p}_{q=1}s_q$が最小になることを示している。

- ファイルサイズについて
(執筆中)

</details>

---

- 添え字が見づらい
とりあえず、リンクを表す文字dは$d_{1-2}$などとし、どことどこのノードをつないでいるかを分かるようにする。また、リクエストがぶら下がらない配信ノード(ノード1とか)をノード$S_1$などとして差別化する。(以下の図はイメージ)

![](https://i.imgur.com/gLO3HQI.png)

--- 

- ファイルサイズ等に関しての想定はあるのか？
先行研究である赤岡さんの研究では、以下の条件のもとでシミュレーションを行っていた。

|ネットワークモデル|リクエスト数|ファイル数|ファイルサイズ平均|
|--|--|--|--|
|2リンク|100|8|1.2[MB,GB]|

</details>
    
## 11/30の輪講を受けて
<details><summary>執筆中</summary>

- ファイルサイズの決定に対数正規分布を利用するのはなぜか？
> この対数正規分布の特色は、規模の大きい個体は数が少なく、規模の小さい例は数が多いということであり、また、それにもかかわらず大きい方からある程度の数の個体の規模を合計すると全体合計規模の大部分のシェアを占めるということである。
リクエスト数にはZipf分布が適切だが、
    
</details>

## 12/1構想発表で受けた質問
- HBHファイル配送方式に関して、実際に用いることができる状況として思いつくものはあるか？
コンテンツを配送経路上に順次キャッシュするシステムで実用化されているものは今すぐ思い当たりませんが、例えば"CDNにおいて、エッジキャッシュに存在するコンテンツを更新する"ときに、そのコンテンツの需要を考慮したスケジューリングとして用いられると考えています。

- (スケジューリングに関して)延べサービス時間の最適化を目標としているが、ほかに性能評価の指標となるものは存在するのか？
例えばファイル転送の時間のみを見て、それを最小化することが延べサービス時間以外の指標として考えうると思います。

- 比較対象とするスケジューリング方式にはどのようなものがあるのか？
比較対象としてシミュレーション上で利用しているスケジューリング方式は、ランダム生成したファイルをファイルインデックスそのままに配送するFIFOともいえる方式や、待ち時間の発生しにくいSRPT(本研究ではファイルサイズの降順)を比較対象として検討しています。

- 3リンク以上に拡張することは検討していないのか？
2リンクの時点で厳密な最適解を求めることが難しくなっているため、縦にリンクを増やす検討よりも2リンクを保ったままノードを横に増やす検討を行っております。

## 12/18冬ゼミで受けた質問
[](
リンク帯域が変化するような環境ではどうなるのかが気になりました。
)

1. ファイルサイズの決定に対数正規分布を利用するのはなぜか？
> この対数正規分布の特色は、規模の大きい個体は数が少なく、規模の小さい例は数が多いということであり、また、それにもかかわらず大きい方からある程度の数の個体の規模を合計すると全体合計規模の大部分のシェアを占めるということである。
    
ファイルサイズ、もとい各コンテンツは、配送する段階では極端にサイズが大きいものをそのまま1つとして送信することを考えにくい。例えばイーサネットのMTUが1500バイトであるように。また、極端にファイルサイズが小さいものもそこまで多いとは考えにくい。そのため、正規分布とどうようにある数値で平均をとりつつ、極端に大きいものが少ないという特徴をもつ対数正規分布を利用しました。
![](https://i.imgur.com/dRfG84x.png)
(Zipf分布の分布図)
![](https://i.imgur.com/Ku9AAyB.png)

## ICN/CCNについてのまとめ
[NIST](chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/viewer.html?pdfurl=https%3A%2F%2Fwww.nict.go.jp%2Fpublication%2Fshuppan%2Fkihou-journal%2Fhoukoku-vol61no2%2FK2015N-06-01.pdf&clen=1573711&chunk=true)資料より
![](https://i.imgur.com/6clBZfx.png)
![](https://i.imgur.com/bQnqlWQ.png)

日本語では情報指向ネットワークなどと呼ばれる。既存のIPアドレスによる通信、いわゆる"どこのサーバにコンテンツAがあってそのIPアドレスは〇〇です"となってサーバと通信を行う。一方こっちでは、"ほしいコンテンツ名はこれこれです、あなたは持ってますか？"というコンテンツ名ベースで通信が行われる。問われた側がキャッシュ内に該当コンテンツを持っていれば、その2者間で通信を行う。