Web アプリケーションの応答時間を向上させるパケット

by user

on 28 марта 2017

Category: Documents

>> Downloads: 1

views

Report

Comments

Description

Download Web アプリケーションの応答時間を向上させるパケット

Transcript

Web アプリケーションの応答時間を向上させるパケット

平成 21 年度
修士学位論文
Web アプリケーションの応答時間を
向上させるパケットスケジューリング
アルゴリズム
A packet scheduling algorithm to improve
the latency of web application
1125088
島上洋一
指導教員
島村和典
2010 年 3 月 1 日
高知工科大学大学院工学研究科基盤工学専攻
情報システム工学コース
要旨
Web アプリケーションの応答時間を
向上させるパケットスケジューリング
アルゴリズム
島上洋一
近年, 一般的な Web アプリケーションよりもフローサイズが大きい映像コンテンツ配信
サービスや P2P 型ファイル共有アプリケーションのトラフィックが, インターネットトラ
フィックの半分以上を占めている. それらのフローが先行してルータに到着している状況で
は, 後からルータへ到着したフローは初期フェーズの RTT やパケット廃棄が増大するとい
う問題がある. 特に, TCP フローの場合は一般的に FIFO で送出される. そのため, フロー
サイズは小さいが多数存在する Web ユーザは帯域を確保することが困難になっている.
Ethernet においては, TCP における SYN や ACK といった制御信号も, データパケット
と同一の通信網上で送受信される. しかし, 廃棄や遅延の影響の小さいデータパケットとは
異なり, コネクションの確立に用いられる制御信号が損失や遅延すると, そのフローは適切
に帯域を確保することが困難になる. また, Web アプリケーションにおける通信の大部分は
スロースタートフェーズで行われる. そのため, スロースタートフェーズにおいて通信品質
が劣化すると, Web アプリケーションの応答時間が低下する.
本論文では, スリーウェイハンドシェイクパケットとスロースタートフェーズのフロー
を優先して送出するパケットスケジューリングアルゴリズムを提案した. 本提案方式は,
到着したパケットを分類するクラシファイア, スロースタートフェーズのフローの識別 ID
とシーケンス番号を記憶するフローテーブル, クラシファイアが分類したパケットをスケ
ジューリングして送出するスケジューラにより構成される.
–i–
検証実験より, ボトルネックリンクに提案方式を適用することで, スリーウェイハンド
シェイクパケットの廃棄が無くなったことを確認した. その結果, TCP の初期フェーズにお
いて適切に帯域を確保できるようになり, サイズの大きいフローが先行してルータへ到着し
ている場合でも, FIFO を適用した場合と比較して 6Mbps 程度スループットを向上するこ
とができた. また, Web ファイル転送に要する時間も 0.4 秒程度短縮できたため, 提案方式
が Web アプリケーションの応答時間を向上させる方式として有効であることを示した.
キーワード
パケットスケジューリングアルゴリズム, QoS, スリーウェイハンドシェイク
パケット
– ii –
Abstract
A packet scheduling algorithm to improve
the latency of web application
Yoichi Shimakami
In recent years, the traﬃc of the video contents delivery service and the P2P type
ﬁle sharing application whose ﬂow size is larger than the general Web application are
increasing. When those ﬂows precede the other ﬂows at the router, the ﬂow which
arrives to the router afterwards causes the problems so that the RTT and the packet
loss during the initial phase increase. Generally, the TCP ﬂow is sent based on FIFO.
So, it is diﬃcult for the Web user to get the suﬃcient bandwidth, while the ﬂow size is
small.
In Ethernet, the control signals named SYN and ACK in TCP are also transferred
on the same communication network as the data packets. There control signals are
used to establish the connection. Therefore, when there control signal is lost or delayed,
a ﬂow will become diﬃcult to get the suﬃcient bandwidth. Moreover, while the Web
application transfers the majority during the slow start phase, the response time of the
Web application would decrease so that the communication quality is deteriorated in
the slow start phase append in the initial communication period.
In this paper, propose the packet scheduling algorithm which give high priority
to the datagrams of the slow start phase and the three-way handshake packet. This
proposal method is composed by the classiﬁer that classiﬁes received packets, the ﬂow
table which memorizes the identiﬁcation number and the sequence number of the slow
– iii –
start phase ﬂow, and the scheduler to schedule the sending priority of the packets which
the classiﬁer classiﬁes.
Through the veriﬁcation experiment, it is conﬁrmed that loss of three-way handshake packet is able to be controlled by applying the proposed method to the bottleneck
link node. As the result, when the proposed method applied to the bottleneck link node,
it is able to get the bandwidth appropriately even in an initial phase of TCP. And, the
throughput higher than the case that FIFO is applied to a bottleneck link node is assured. Consequently, the proposal method shortens the required time to the Web ﬁle
transfer, and it is shown the eﬀectiveness to improve the response time of the Web
applications.
key words
Packet Scheduling Algorithm, QoS, Three-way Hand-shake Packets
– iv –
目次
第1章
序論
1
第2章
Web アプリケーションに対する優先転送方式
7
2.1
諸言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.2
QoS の技術要素 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.3
キューイングの仕組み . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.4
一般的なパケットスケジューリングアルゴリズム . . . . . . . . . . . . . .
11
2.4.1
FIFO (First In First Out) . . . . . . . . . . . . . . . . . . . . . .
11
2.4.2
PQ (Priority Queuing) . . . . . . . . . . . . . . . . . . . . . . . .
12
2.4.3
RR (Round Robin scheduling) . . . . . . . . . . . . . . . . . . .
13
2.4.4
WFQ (Weighted Fair Queuing) . . . . . . . . . . . . . . . . . . .
14
2.4.5
CBQ (Class-Based Queuing) . . . . . . . . . . . . . . . . . . . .
15
2.5
提案方式の構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.6
クラシファイア . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.7
2.6.1
スリーウェイハンドシェイク . . . . . . . . . . . . . . . . . . . . .
18
2.6.2
スロースタートフェーズ
. . . . . . . . . . . . . . . . . . . . . . .
20
2.6.3
クラシファイアの分類方法 . . . . . . . . . . . . . . . . . . . . . .
22
2.6.4
DNS 問い合わせ時のパケット . . . . . . . . . . . . . . . . . . . .
23
フローテーブル . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.7.1
フローテーブルが管理する情報 . . . . . . . . . . . . . . . . . . . .
26
2.8
キュー . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
2.9
スケジューラ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
2.10
結言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
–v–
目次
第3章
NS-2 による検証実験
31
3.1
緒言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.2
シミュレーション環境 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.2.1
一般的なネットワークトラフィックにおけるシミュレーション結果 .
33
ユーザごとの平均スループット . . . . . . . . . . . . . . . . . . . .
33
ユーザごとのパケット廃棄数 . . . . . . . . . . . . . . . . . . . . .
38
サイズの大きいフローが先行してルータへ到着している状態におけ
る各ユーザのスループット . . . . . . . . . . . . . . . . .
3.2.2
40
80 番ポートを使用するネットワークトラフィックにおけるシミュ
レーション結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
ユーザごとの平均スループット . . . . . . . . . . . . . . . . . . . .
45
ユーザごとのパケット廃棄数 . . . . . . . . . . . . . . . . . . . . .
46
サイズの大きいフローが先行してルータへ到着している状態におけ
3.3
第4章
4.1
る各ユーザのスループット . . . . . . . . . . . . . . . . .
48
結言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
結論
51
今後の展望 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
謝辞
53
参考文献
55
– vi –
図目次
1.1
IntServ の概念図 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.2
DiﬀServ の概念図 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2.1
キューイング機構の一般的な構成 . . . . . . . . . . . . . . . . . . . . . . .
10
2.2
FIFO の概念図 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.3
PQ の概念図 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
2.4
RR の概念図 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.5
WFQ の概念図 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.6
CBQ の概念図 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.7
提案方式の概念図 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.8
スリーウェイハンドシェイクの概念図
. . . . . . . . . . . . . . . . . . . .
19
2.9
スロースタートフェーズと輻輳回避フェーズの概念図 . . . . . . . . . . . .
20
2.10 クラシファイアにおける処理の流れ . . . . . . . . . . . . . . . . . . . . . .
22
2.11 DNS による名前解決処理の流れ . . . . . . . . . . . . . . . . . . . . . . .
25
2.12 フローの識別に用いる情報 . . . . . . . . . . . . . . . . . . . . . . . . . .
26
2.13 フローテーブルおける処理の流れ . . . . . . . . . . . . . . . . . . . . . . .
27
2.14 提案方式におけるキューの概念図 . . . . . . . . . . . . . . . . . . . . . . .
28
2.15 スケジューリングの流れ . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
3.1
ネットワークモデル . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
3.2
ユーザごとの平均スループット . . . . . . . . . . . . . . . . . . . . . . . .
34
3.3
Web ユーザのスループット遷移 . . . . . . . . . . . . . . . . . . . . . . . .
36
3.4
P2P ユーザのスループット遷移 . . . . . . . . . . . . . . . . . . . . . . . .
36
3.5
Video(TCP) ユーザのスループット遷移 . . . . . . . . . . . . . . . . . . .
37
– vii –
図目次
3.6
Video(UDP) ユーザのスループット遷移 . . . . . . . . . . . . . . . . . . .
37
3.7
各ユーザのパケット廃棄数 . . . . . . . . . . . . . . . . . . . . . . . . . .
39
3.8
スリーウェイハンドシェイクパケット廃棄数 . . . . . . . . . . . . . . . . .
39
3.9
先行してルータに到着しているトラフィック . . . . . . . . . . . . . . . . .
42
3.10 サイズの大きいフローが先行してルータに到着している状態で Web フロー
を発生 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
3.11 Web ファイルの転送に要する時間 . . . . . . . . . . . . . . . . . . . . . .
43
3.12 提案方式および FIFO におけるユーザごとの平均スループット . . . . . . .
45
3.13 各ユーザのパケット廃棄数 . . . . . . . . . . . . . . . . . . . . . . . . . .
47
3.14 スリーウェイハンドシェイクパケット廃棄数 . . . . . . . . . . . . . . . . .
47
3.15 先行してルータに到着しているビデオトラフィック . . . . . . . . . . . . .
49
3.16 ビデオフローが先行してルータに到着している状態で Web フローを発生 . .
49
3.17 Web ファイルの転送に要する時間 . . . . . . . . . . . . . . . . . . . . . .
50
– viii –
表目次
3.1
シミュレーションにおける基本パラメータ値 . . . . . . . . . . . . . . . . .
– ix –
32
第1章
序論
近年, ネットワークの広帯域化やインターネット関連技術の発展によって, 様々な種類の
アプリケーションがインターネット上で利用されている. それにともない, Web アプリケー
ショントラフィックが通信の大部分を占めていた頃と比較して, インターネットにおける
トラフィック特性が大幅に変化してきた. これは, 膨大なトラフィックを発生させる動画像
配信サービスや P2P(Peer to Peer) 型ファイル共有アプリケーションの登場が要因である.
そして, それらのアプリケーションが発生させる膨大な量のトラフィックによる, インター
ネットトラフィックの急激な増加が問題視されている.
動画配信サービスのトラフィックは, コーデックの発達による動画コンテンツの容量増加
や, Youtube に代表される動画共有サイトの普およを背景に急激に増加してきた [1]. 一方,
P2P 型ファイル共有アプリケーションでは一般的にマルチメディアファイルの共有が行わ
れるため, 発生させるトラフィック量も膨大である. 現在のインターネットにおいて, 動画配
信サービスにより発生するトラフィック量は, インターネットトラフィックの約半分を占め
る P2P 型ファイル共有アプリケーションのトラフィック量よりも少ない. しかし, 動画配信
サービスによるトラフィック量がこのままの速度で増加し続ければ, P2P 型ファイル共有ア
プリケーションのトラフィック量を上回ると予想されている [2].
その結果として生じる問題は, インターネットトラフィックの急激な増加だけではない.
P2P 型ファイル共有アプリケーションや動画配信サービスのトラフィックは, 最も多くユー
ザがいる Web アプリケーションのトラフィックと比較して, フローサイズが圧倒的に大き
いという特徴がある [3]. そのため, P2P 型のファイル共有アプリケーションや動画配信サー
ビスによって発生するサイズの大きいフローが, 多くの帯域を占有することになる. 一方,
–1–
第 1 章序論
フローサイズは小さいが多数存在する Web ユーザは, サイズの大きいフローによる帯域圧
迫の影響により初期フェーズの RTT (Round Trip Time) やパケット廃棄が増加し, 帯域
を確保することが困難になる. その結果, Web アプリケーションの応答時間が増大し, Web
アプリケーションのユーザビリティが低下という事態を招くと考えられる. そこで, 現在で
はサイズの小さいフローを含めた全てのユーザに一定のサービス品質を提供するため, QoS
(Quality of Service) 保証の重要性が益々増加している [4].
一般的な QoS を保証する技術として, IntServ(Integrated Services) や DiﬀServ (Diﬀer-
entiated Services) といった QoS アーキテクチャや, ルータにおけるパケットスケジュー
リングが挙げられる [5]. まず, IntServ の概念図を図 1.1 に, DiﬀServ の概念図を図 1.2 に
示す.
アプリケーションがRSVPによってQoS要件を伝える
アプリケーション
アプリケーション
IntServに対応しないノードがある場合, トラフィックは転送されない
図 1.1 IntServ の概念図
それぞれのデバイスがパケットの優先順位に従って独自のQoS処理を行う
アプリケーションA
アプリケーションB
アプリケーションA
アプリケーションB
DiffServに対応していないノードは何もせずに転送する
図 1.2 DiﬀServ の概念図
–2–
IntServ は, アプリケーションフローを識別し, フロー単位に QoS を提供する QoS アーキ
テクチャである. ルータ, RSVP (Resource reSerVation Protocol) を用いて QoS 保証に必
要なネットワークリソースの予約を行う. これにより, フローの最小遅延を保証することが
できる. しかし, ネットワークが大規模化しインターネットを利用するユーザやアプリケー
ションも膨大に増加した現在では同時に存在するフローの数も膨大になり, 全てのアプリ
ケーションフローを個別に認識して帯域幅を予約することが困難になった. また, パラメー
タチューニングの複雑さも増加したため, スケーラビリティに乏しく, 大規模ネットワーク
では使用されていない.
次に, DiﬀServ は IntServ の複雑さやスケーラビリティを克服するために提案された仕
組みで, 性能と拡張性が重視されている. DiﬀServ では, パケットヘッダの TOS (Type Of
Service) フィールドを利用してアプリケーションごとに分類, グループ化したのち, そのグ
ループに対して優先度を定義する. そして, そのグループに対して優先度を定義し, 優先度に
応じた転送を行う. このとき, パケットをグループ化する基準は自由に決定することができ
るうえ, IntServ のようにエンドツーエンドのサービスを規定する必要がないため, IntServ
よりもスケーラビリティが高いといえる. しかし, 具体的なサービスは実装や運用環境に依
存するため, 全ての通信経路において共通のポリシを適用することは困難であるといえる.
最後に, ルータにおけるパケットスケジューリングは, 最も基本的な QoS を保証する技術
である. 現在, 最も一般的に利用されているスケジューリングアルゴリズムとしては, FIFO
(First In First Out) が挙げられる. FIFO は, ルータに到着した順にパケットを転送する.
そのため, サイズの大きいフローがサイズの小さいフローに先行してルータへ到着してい
る状況下では, サイズの大きいフローが多くの帯域を占有し, サイズの小さいフローが帯域
を確保することが困難になる. FIFO 以外に, パケットの種類によって優先転送を行うスケ
ジューリングアルゴリズムも提案されているが, ルータにおける処理が複雑であるため, 多
数のフローが多重している場合にはルータにおいてフロー分類による負荷が増大するとい
う問題がある. また, 特定のプロトコルを優先制御したとしても, 分類したトラフィックは
FIFO で転送されるため, サイズの大きいフローが帯域を圧迫する問題の解決には至らない.
–3–
第 1 章序論
Web トラフィックにおいては, サイズの大きいビデオフローがサイズの小さい Web アプリ
ケーションフローの帯域を圧迫するためである.
DiﬀServ や IntServ といった QoS アーキテクチャを用いることによってパケットごとに
帯域を確保することが可能になり, 特定のフローが帯域を占有することを回避できる. し
かし, 両方式共に実装上の問題を抱えるため, 一般的にインターネットにおいてはベストエ
フォートが採用される場合が多い. また, これらの QoS アーキテクチャを導入しただけで
は, 特定のフローによる帯域の占有を回避することはできても, サイズの大きいフローが帯
域を占有する問題の解決には至らない. パケットスケジューリングアルゴリズムによるアプ
ローチを用いることで, 特定のフローによる帯域の占有を回避することができる. しかし, や
はり特定のトラフィックによる帯域圧迫を回避することはできても, 分類したトラフィック
内でサイズの大きいフローが帯域を占有することに変わりはない. だが, サイズの大きいフ
ローによる帯域の占有を抑制でき, パラメータチューニングも容易なスケジューリングアル
ゴリズムを考案することで, サイズの小さいフローの品質を改善することが可能になると考
える.
そこで, 本論文ではサイズの大きいフローによる帯域圧迫を抑制することで, Web アプリ
ケーションの応答時間を短縮し, ユーザビリティを向上させることができるスケジューリン
グアルゴリズムを提案する [6]. Ethernet においては, TCP における SYN や ACK といっ
た制御信号も, データパケットと同一の通信網上で送受信される. しかし, 廃棄や遅延の影
響の小さいデータパケットとは異なり, コネクションの確立に用いられる制御信号が損失や
遅延すると, そのフローは適切に帯域を確保することが困難になる. また, Web アプリケー
ションにおける通信の大部分はスロースタートフェーズで行われる. そのため, スロース
タートフェーズにおいて通信品質が劣化すると, Web アプリケーションの応答時間が低下す
るといえる.
そのため, 提案方式ではスロースタートフェーズのフロー, 特にスリーウェイハンドシェ
イク時のパケットを優先的に転送することで, フローサイズの小さい Web アプリケーショ
ンに対する優先的な帯域割り当てを実現する. 検証実験では, ネットワークシミュレータ
–4–
上に提案方式を実装し, 実ネットワークを想定したトラフィックを転送することで評価を
行った. そして, ルータにおいて提案するスケジューリングアルゴリズムを適用した場合と,
FIFO を適用した場合における各ユーザのスループットを比較して評価することで有効性
を示した. その結果, 提案方式をボトルネックリンクに適用することでスリーウェイハンド
シェイクパケットの廃棄が無くなり, Web アプリケーションの応答時間が向上したことを確
認した.
本論文は, 本章を含めて 4 章から構成される. 第 2 章では, 従来方式の説明と, 提案するス
ケジューリングアルゴリズムの詳細について述べる. 第 3 章では, ネットワークシミュレー
タに本提案方式を適用することで行った検証実験の実験環境と実験結果について述べる. 最
後に, 第 4 章では本研究の有効性を考察し, 結論を述べる.
–5–
第2章
Web アプリケーションに対する優
先転送方式
2.1
諸言
本章では, まず本研究で着目する QoS 制御である, パケットスケジューリングアルゴリズ
ムについて説明する. そして, 提案するスケジューリングアルゴリズムの構成と特徴につい
て述べる.
2.2
QoS の技術要素
現在, 一般的に利用されている QoS の技術的要素として, 大きく分けて次の 4 つがある.
• アドミッション制御 (Admission Control)
• クラシファイア (Classiﬁer)
• パケットスケジューラ (Packet Scheduler)
• シェーパ (Shaper)
アドミッション制御は, セッションごとにリソースの予約を制御して, 通信を確立するか
を決定する方法である. アドミッション制御を行う技術としては, IntServ が挙げられる.
IntServ は, RSVP を使用してエンドツーエンドでのサービス保証が得られる場合のみ通信
を行う厳格な QoS モデルである. 通信経路の全てのルータで IntServ に同意する必要があ
るため, 途中のルータが 1 つでも IntServ に対応していない場合やリソースが不足している
–7–
第 2 章 Web アプリケーションに対する優先転送方式
場合は, 通信を確立しない. つまり, アドミッション制御の主な処理内容としては, セッショ
ンの開始時に RSVP といったセットアッププロトコルによってパス上のリソースを確保し,
確保に失敗するとセッションを開始しない. アドミッション制御においては, 特に故障時に
リソースを解放する方法が重要であり, 優先的にリソースを割り当てるポリシ, 代替経路を
利用するためのルーティング, リソースに対する課金といったことを考慮する必要がある.
クラシファイアは, ルータに到着したパケットをグループに分類する方法である. IP にお
いては, 送信元 IP アドレス, あて先 IP アドレス, 送信元ポート番号, あて先ポート番号, プ
ロトコルといった情報を用いてパケットを識別することで, 特定のホスト向けのサービスを
抜き出す. そして, DiﬀServ におけるクラシファイアは IP ヘッダの TOS フィールドを用い
ることで簡素化されている.
パケットスケジューラは, グループに分類されたパケットを送出するスケジュールを, 調
整する方法である. パケットスケジューラは, キューイングとバッファ管理の両方に多くの
方法がある. 一般的なパケットの送出方法には, 送出パケット数を管理する方法や帯域を管
理する方法があり, バッファ管理方法には, 特定のパケットを廃棄する方法や特定の順番で
パケットを廃棄する方法がある. パケットスケジューラにおいては, トラフィックの特性に
合わせてそれらの組み合わせを変更することで, ポリシに適した制御を実現する.
シェーパは, 事前に設定した閾値を超過したパケットをバッファに一時的に格納する方法
である. そして, 超過レートが下がった時点でバッファから出力キューに配置して転送する.
これにより, 特定フローの利用帯域を調整し, バーストトラフィックによる影響を抑制する.
上述した 4 つの技術的要素は, それぞれが個別に動作するのではなく, それぞれを組み合
わせて動作することで QoS 制御を実現している.
提案方式は, フローサイズの小さい Web フロー優先的に帯域を割り当てることで, フロー
サイズの小さい Web アプリケーションの応答時間を向上させる. しかし, 現在のインター
ネットにおいては莫大な種類のフローが混在しているため, クラシファイアにおいて詳細に
分類することは困難である. 特に, P2P アプリケーションのトラフィックは, Web を初めと
するクライアント・サーバ型アプリケーションのトラフィックとは性質が大きく異なる [7].
–8–
2.3 キューイングの仕組み
P2P ネットワークにおいては, クライアントノードが自律的にネットワークへの参加や離脱
を繰り返すため, P2P アプリケーションの識別や分類が難しいという問題がある. P2P ト
ラフィックを識別する方法としては, ポート番号を用いた一般的な識別方法の他, セッショ
ン追跡による識別方法やシグネチャ方式による識別方法などが考案されているが, 現時点で
はいずれの方法も P2P トラフィックを識別する手法としては不十分であるといえる. そし
て, サイズの大きいフローがサイズの小さいフローの帯域を圧迫する問題を考えても, クラ
シファイアによる分類とパケットスケジューラによる優先スケジュールだけでは問題の解
決は難しいといえる. そこで, 提案方式はパケットスケジューラがフローの種類ではなくフ
ローの状態を考慮して優先制御を行う. これにより, クラシファイアによる P2P トラフィッ
クの識別を必要としないパケットスケジューリングを実現する.
2.3
キューイングの仕組み
入力フローが複数の場合, ルータはパケットを一本または複数のキューに待機させ, 一定
のアルゴリズムに従って転送していく. キューイングは, 主に出力インタフェースで行われ
る. キューイング機構の一般的な構成を, 図 2.1 に示す.
そして, キューイング処理は主に次の 4 つの要素から構成される.
• キュー構造
• クラシファイア
• ドロッパ
• スケジューラ
キュー構造は, 複数の内部キューの組み合わせにより構成される. クラシファイアは, 受信
したパケットのヘッダ情報をもとに識別を行い, 内部キューへ格納する. 一般的に, パケット
の識別には送信元 IP アドレス, あて先 IP アドレス, 送信元ポート番号, あて先ポート番号
が用いられる. そして, これらの値が共通する一連のパケットをフローと呼ぶ. ドロッパは,
選択的にパケットを廃棄する仕組みであり, 内部キューがオーバーフローする際に利用され
–9–
第 2 章 Web アプリケーションに対する優先転送方式
Outgoing Interface
Queue Structure
Incoming
Packets
Outgoing
Packets
Classifier
Scheduler
Dropper
図 2.1
キューイング機構の一般的な構成
る. スケジューラは, スケジューリングアルゴリズムに従って, 次にパケットを送出すべき内
部キューを選択し, 送出順序を操作する仕組みである. それぞれの要素に工夫を加え, 適切に
組み合わせることによって, 効果的なスケジューリング手法が実現できる.
– 10 –
2.4 一般的なパケットスケジューリングアルゴリズム
一般的なパケットスケジューリングアルゴリズム
2.4
これまで, QoS 制御を実現するパケットスケジューリングアルゴリズムとして, 数多く方
式が考案されてきた. ここでｈ, その中から今現在一般的に利用されている方式を次に示し
説明する.
2.4.1
FIFO (First In First Out)
FIFO は, 最も一般的で単純なスケジューリングアルゴリズムであるため, ネットワークの
各所で用いられている. FIFO の概念図を, 図 2.2 に示す. FIFO は, 全てのフローのパケッ
トを到着順に 1 本のキューに格納し, 先に格納されたパケットから順番に転送するメカニズ
ムである. FIFO では転送量の多いフローほどより多くの帯域を確保するため, 音声フロー
といった遅延に敏感なフローであったとしても他のフローと同様に扱われることになる. こ
のため, VoIP 利用時における音声パケットの到着遅延やジッタの増加, さらにパケット廃棄
が発生して音声品質の低下を招く場合がある. 統合型ネットワークにおいては, 音声フロー
やミッションクリティカルなフローには保護を行い, それ以外のフローからの影響を回避す
る手法が一般的には用いられる.
Incoming
Packets
3
2
Outgoing
Packets
Bulk Traffic
3
2
FIFO Queue
1
3
3
2
1
VoIP Traffic
図 2.2 FIFO の概念図
– 11 –
2
1
1
第 2 章 Web アプリケーションに対する優先転送方式
2.4.2
PQ (Priority Queuing)
PQ は, 定義した複数のキューに対して絶対的な優先度を設定し, 高優先度のキューに格納
されたパケットから転送を行うメカニズムである. PQ の概念図を, 図 2.3 に示す. 高優先度
のキューが空になると, 次に優先度の高いキューを処理するといった単純な機構であるため,
リアルタイム性を保証することができる. その特性上, 帯域幅が狭ければ狭いほど効果のあ
るメカニズムであり, 1Mbps 以下の帯域であれば効果的な QoS が期待できる.
しかし, PQ には高優先度フローの出力レート総計が大きくなると, 低優先度フローの出力
レートが減少するという問題がある. これは, バースト的に多くの高優先度フローのパケッ
トを受信した際に, 高優先度フローの処理に時間がかかり, 低優先度フローを処理すること
ができなくなるためである. そのため, 輻輳時においては低優先度のキューに分類されたア
プリケーションにおける遅延が増大し, 通信品質が大幅に劣化する.
Outgoing Interface
High
4
3
Incoming
Packets
2
1
Outgoing
Packets
Medium
6
Classifier
5
Scheduler
Normal
12
9
8
7
Low
12
11
10
図 2.3 PQ の概念図
– 12 –
…
1
2.4 一般的なパケットスケジューリングアルゴリズム
2.4.3
RR (Round Robin scheduling)
RR は, 複数のキューを作成して, 各キューからパケットを 1 つずつ順番に転送するメカ
ニズムである. RR の概念図を, 図 2.4 に示す. 各キューを順番に処理するため, FIFO や
PQ と比較して公平性の高いメカニズムであるといえる.
しかし, 特定のキューに優先度を持たせることができないため, 遅延に敏感なフローの
QoS を保証することが困難であるといえる. そのため, 一般的にはキューごとに優先度を持
たせることができる WRR (Weighted Round Robin) を使用する. 統合ネットワークでは,
RR ではなく WRR を用いて遅延に敏感なフローの QoS を保証する. また, RR はその特性
上パケットスケジューリングだけではなく, DNS サーバの不可分散やプロセスの並列処理
においても幅広く利用されている.
Outgoing Interface
6
1
2
Incoming
Packets
Classifier
10
7
3
8
4
9
5
Outgoing
Packets
Scheduler
12
12
11
図 2.4 RR の概念図
– 13 –
…
1
第 2 章 Web アプリケーションに対する優先転送方式
2.4.4
WFQ (Weighted Fair Queuing)
WFQ は, フローごとに独立したキューを動的に作成し, 他フローによる影響を一定以下
に抑制することで公平性を実現するメカニズムである. WFQ の概念図を, 図 2.5 に示す.
WFQ では, 格納しているパケット数の最も少ないキューから順番に処理を行う. そのため,
フローの数が多くなるほど 1 つのキューに割り当てられる帯域が狭くなり, 優先制御の効果
が低下する. また, フローの数だけキューを作成することはリソース消費の面から現実的で
はないため, 実装上はハッシュによって格納するフローを選択するといった近似法が用いら
れる. このため, WFQ では広帯域に対応することが困難であり, 低速な回線向けのパケット
スケジューリングアルゴリズムであるといえる.
Outgoing Interface
9
Incoming
Packets
11
3
10
2
1
5
Outgoing
Packets
4
Classifier
Scheduler
12
13
6
8
13
7
図 2.5 WFQ の概念図
– 14 –
…
1
2.4 一般的なパケットスケジューリングアルゴリズム
2.4.5
CBQ (Class-Based Queuing)
CBQ は, クラスごとに独立したキューを作成し, 設定した帯域幅に応じて重み付けラウン
ドロビンで転送するメカニズムである. CBQ の概念図を, 図 2.6 に示す. スケジューラは,
設定した帯域幅を上回るトラフィックを受信したキューをスキップしてスケジューリングす
る. WFQ と CBQ では, どのフローにも公平に送信機会が与えられるため, 特定のフローの
帯域が圧迫されることはない. つまり, クラスごとに定められた最少予約帯域を定量的に確
保できるため, 多くの種類のフローを受信する場合に効果的である. しかし, リソースには限
りがあるため, あまりに多くの種類のサイズの小さいフローを受信したときは, 最少予約帯
域を保証することが困難になる場合がある. また, フローやクラスごとの優先度や転送レー
トをこと前に設定しなければならないため, 状況に応じて適切にパラメータを設定する必要
がある. そのため, パラメータチューニングが非常に複雑な方式であるといえる.
Outgoing Interface
Default Class
Incoming
Packets
Waited
Round Robin
Outgoing
Packets
Class 1 (Voice)
Classifier
Scheduler
Class 2 (Video)
Set
Overlimit
図 2.6 CBQ の概念図
– 15 –
Estimator
第 2 章 Web アプリケーションに対する優先転送方式
CBQ は最小予約帯域を保証するが, それだけでは音声トラフィックといった遅延に敏感
なトラフィックは満足する品質を得ることができない. そこで, 遅延に敏感なトラフィック
の品質を保証するために, PQ と CBQ の 2 つの要素を組み合わせた LLQ (Low Latency
Queuing) というメカニズムがある [8]. LLQ では, CBQ で作成した 1 つのクラスを PQ に
することで, 遅延に敏感なトラフィックを最優先処理する. この処理は, PQ を空にしてから
その他のキューを処理することで実現されている. これにより, 遅延に敏感なトラフィック
を遅延やジッタから保護することが可能になる.
2.5
提案方式の構成
現在のインターネットにおける Web アプリケーションの多くが, トランスポート層プロ
トコルとして TCP を用いており, TCP トラフィックは現在のインターネットトラフィック
の大部分を占めている [9]. 提案方式は, TCP における初期フェーズのフローほど優先して
送出することで Web アプリケーションの応答時間を向上させるスケジューリングアルゴリ
ズムである. そのため, 提案方式が満たす必要のある優先制御のポリシと優先制御手法の要
件を示す. まず, 提案方式が満たす必要のある優先制御のポリシを示す.
• サイズの小さい Web アプリケーションフローの QoS を保証する
次に, 提案方式が満たす必要のある優先制御手法の要件を示す.
• P2P アプリケーションフローの識別を必要としない
• 実装時の複雑なパラメータチューニングを必要としない
これらの要件を満たすスケジューリングアルゴリズムの概念を図 2.7 に示す. 本提案方式
は, 受信したパケットを識別するクラシファイア, スロースタートフェーズのパケットの識
別 ID (送信元およびあて先 IP アドレス, 送信元およびあて先ポート番号), 送出するパケッ
トを選択するスケジューラ, パケットのオーバーフローを回避するドロッパから構成される.
スロースタートフェーズのパケットをその他のフローよりも優先的に送出するため, クラシ
– 16 –
2.5 提案方式の構成
Outgoing Interface
Incoming
Packets
Outgoing
Packets
High
3
Classifier
2
1
Medium
Search
Write
8
6
Scheduler
7
…
1
4
Read
Normal
7
5
Flow Table
ID 1 SEQ
ID 2 SEQ
・
・
・
・
・
・
Dropper
図 2.7
提案方式の概念図
ファイアにおいて適切なキューへ分類する必要がある. クラシファイアは, TCP パケット
のフラグフィールドの値とシーケンス番号, さらにフローテーブルに記憶されている情報を
もとにスロースタートフェーズのフローであるかを識別しキューへ格納する. このとき, ス
リーウェイハンドシェイクのパケット, スロースタートフェーズのフロー, その他のフロー
で分類する. フローテーブルは, フローの送信元およびあて先 IP アドレス, 送信元およびあ
て先ポート番号, シーケンス番号を記憶する. スケジューラは, 通信品質劣化の影響が大きい
パケットほど高い優先度を与えるようスケジューリングを行う. つまり, TCP における初期
フェーズのフローほど優先して転送する. 最後に, ドロッパはキューがバッファオーバーフ
ローを起こすことを防ぐ.
– 17 –
第 2 章 Web アプリケーションに対する優先転送方式
2.6
クラシファイア
提案方式では, Web アプリケーションフローの通信品質を保証するため, TCP における
初期フェーズのフローほど優先して帯域を割り当てる. そのため, クラシファイアにおいて
最優先で帯域を割り当てるスリーウェイハンドシェイクのパケットと, その他のフローと比
較して高い割合を割り当てるスロースタートフェーズのパケット, その他のフローのパケッ
トをクラシファイアにおいて識別する必要がある. 本項では, 提案方式のクラシファイアに
おける内部キューの分割方法とフローの識別方法について述べる.
2.6.1
スリーウェイハンドシェイク
Ethernet では, TCP における SYN や ACK といった制御信号も, データパケットと同一
の通信網上で送受信される. しかし, 廃棄や遅延の影響の小さいデータパケットとは異なり,
コネクションの確立に用いられる制御信号が遅延や廃棄すると, そのフローは適切に帯域を
確保することが困難になる.
そして, TCP では SYN や ACK を用いて, スリーウェイハンドシェイクいう手法を用い
てコネクションを確立する. スリーウェイハンドシェイクの概念図を図 2.8 に示し, その手
順を次に示す.
1. クライアントが, シーケンス番号の初期値を指定した SYN セグメントを送信する.
2. サーバが, SYN フラグと ACK フラグを立てたセグメントで応答する. SYN セグメ
ントはサーバのシーケンス番号の初期値を通知し, ACK セグメントはクライアントの
シーケンス番号に 1 を加えた値を確認応答番号として通知する.
3. クライアントが, サーバから送られてきた SYN セグメントのシーケンス番号に 1 を加
えた値を確認応答番号とした ACK セグメントを送信する.
このように, スリーウェイハンドシェイクのパケットは 1 パケットずつ送信されることが
わかる. そのため, スリーウェイハンドシェイクのパケットは RTT の増加やパケット廃棄
– 18 –
2.6 クラシファイア
の影響が最も大きく, このフェーズで通信品質が劣化したフローは, 帯域を確保することが
困難になるため, 最も高い優先度を与えるキューに格納する必要がある.
Client
CLOSED
Server
LISTEN
SEQ =
J,
SYN_CENT
J
, ACK=
K
=
SEQ
SEQ =
J
Established
図 2.8
FLAG
= SYN
SYN_RCVD
K
N, AC
Y
S
=
AG
+ 1, FL
+ 1, A
CK = K
+ 1, FL
AG = A
CK
スリーウェイハンドシェイクの概念図
– 19 –
Established
第 2 章 Web アプリケーションに対する優先転送方式
2.6.2
スロースタートフェーズ
TCP では, スロースタートという輻輳制御アルゴリズムを用いて, 輻輳の発生を回避して
いる. 現在, 多くの OS では TCP 実装のベースとして Reno が用いられている [10]. Reno
の輻輳制御方式は, スロースタートフェーズと輻輳回避フェーズという 2 つのフェーズで構
成され, それぞれのフェーズで輻輳制御用のウインドウサイズ (cwnd : congestion window)
を制御している. ここで, スロースタートフェーズと輻輳回避フェーズの概念図を図 2.9 に
グラフで示す.
20
Slow Start
Phase
19
Congestion Avoidance
Phase
18
17
16
ssthresh
14
12
cwnd
10
(mss)
8
ssthresh
6
ssthresh
4
2
0
0
1
図 2.9
2
3
4
5
6
7
8
RTT
9
10
11
12
13
14
15
16
スロースタートフェーズと輻輳回避フェーズの概念図
スロースタートフェーズでは, ACK パケットを受信するごとに輻輳ウインドウサイズを 1
パケット分増加させる. その結果, 短時間に利用可能な帯域以上のフローを発生し, 輻輳が発
生する.
一方, 輻輳回避フェーズでは ACK パケットを受信するごとに輻輳ウインドウサイズを輻
輳ウインドウサイズの逆数分増加させる. そのため, スロースタートフェーズよりも輻輳ウ
– 20 –
2.6 クラシファイア
インドウの増加速度が小さく, 輻輳が発生するまでの時間が長い. しかし, 輻輳ウインドウは
増加する一方であるため, 輻輳回避フェーズにおいても最終的には輻輳が発生する. ここで,
それぞれのフェーズにおける輻輳ウインドウサイズの更新アルゴリズムは次のように表すこ
とができる.
{
cwnd ←
cwnd + 1
cwnd +
(cwnd < ssthresh)
1
cwnd
(cwnd ≥ ssthresh)
(2.1)
ssthresh は, Reno がスロースタートフェーズから輻輳回避フェーズに移行する際の閾値
である. そして, パケット廃棄を確認した際は次式のように輻輳ウインドウサイズを減少さ
せる.
{
cwnd ←
cwnd +
cwnd
2
cwnd + 1
(重複 ACK による検出)
(タイムアウトによる検出)
(2.2)
輻輳ウインドウサイズは, パケット廃棄を検出するまで増加し続け, パケット廃棄を検出
すると減少を始める. これは, Reno がパケット廃棄の発生を輻輳発生の指標とみなしている
ためである.
これらより, スロースタートフェーズの間は輻輳ウインドウサイズが大きく増加していく
が, 輻輳回避フェーズではウインドウサイズの増加量が小さいことがわかる. そのため, ス
ロースタートフェーズで十分な帯域を確保することができなければ, スループットが大幅に
低下してしまうといえる. Web アプリケーションにおけるファイル転送の大部分がスロース
タートフェーズで行われることを考慮すると, Web アプリケーションの応答時間を向上する
ためにはスロースタートフェーズのフローの扱いが重要であるといえる. そのため, スロー
スタートフェーズのフローに対する RTT の増大やパケット廃棄による通信品質劣化の影響
を抑制するために, スロースタートフェーズのフローをクラシファイアにおいて識別し, 高
い優先度を与えるキューに格納するする必要がある.
– 21 –
第 2 章 Web アプリケーションに対する優先転送方式
2.6.3
クラシファイアの分類方法
提案方式では, これまでに記したようにスリーウェイハンドシェイクのパケットとスロー
スタートフェーズのフローに, それぞれ高い優先度を与える. そのため, クラシファイアにお
いては, それらのパケットを高い優先度を与えることができるキューに分類する必要がある.
クラシファイアにおける識別のフローチャートを図 2.10 に示す.
パケットを受信
No
TCP
Yes
Yes
3-way
handshake
No
フローテーブルを
検索
Yes
High Queue
図 2.10
Slow start
phase
No
Medium Queue
Normal Queue
クラシファイアにおける処理の流れ
まず, スリーウェイハンドシェイクのパケットについて述べる. スリーウェイハンドシェ
イクのパケットは, 最優先で QoS を保証する必要があるので, TCP ヘッダにおけるフラグ
フィールドの値からスリーウェイハンドシェイクのパケットであると判断した場合は, 最も
高い優先度を割り当てることができる High キューへ格納する. このとき, 受信したパケッ
トのフロー ID とシーケンス番号をフローテーブルに記憶する. フロー ID とは, 送信元およ
– 22 –
2.6 クラシファイア
びあて先 IP アドレスと送信元およびあて先ポート番号を指す. 以前受信したパケットの情
報が記憶されている場合は, それらの値を上書きして更新する.
次に, スロースタートフェーズのパケットについて述べる. スロースタートフェーズを識
別する方法として, パケット廃棄を輻輳の指標として用いる Loss-based 手法や, RTT の増
大を輻輳の指標として用いる Delay-based 手法がある [11]. 本提案方式では, TCP パケッ
トのヘッダ情報を用いて識別が可能な Loss-based 手法を, クラシファイアに適用すること
で識別を行う. このとき, フローテーブルに記憶されているフロー ID とシーケンス番号を
用いることで, Loss-based 手法による識別を実現する.
初めに, 受信した TCP パケットがスリーウェイハンドシェイクのパケットでなければ, 受
信したパケットのフロー ID がフローテーブルに記憶されているか照合を行う. 一致するフ
ロー ID が見つかった場合は, 受信したパケットのシーケンス番号とフローテーブルに記憶
されているシーケンス番号を比較する. 受信したパケットのシーケンス番号が, フローテー
ブルに記憶されているシーケンス番号に 1 を加えた値であれば, スロースタートフェーズの
フローであると判断して Medium キューに格納する. このとき, フローテーブルに記憶され
ているシーケンス番号を, 受信したパケットのシーケンス番号に更新する. そして, 受信した
パケットのシーケンス番号がフローテーブルに記憶されているシーケンス番号に 1 を加え
た値でない場合は, RTT の増大によるパケット到着順番の入れ替わりやパケット廃棄が発
生していると判断する. この場合, そのフローはスロースタートフェーズではなく輻輳回避
フェーズに移行していると判断して Normal キューへ格納する. また, スリーウェイハンド
シェイクとスロースタートフェーズ以外のパケットは, 全て Normal キューへ格納する.
2.6.4
DNS 問い合わせ時のパケット
提案方式では, スリーウェイハンドシェイクパケットとスロースタートフェーズのフロー
を高い QoS を保証可能なキューへ分類する. これは, 本提案方式が Web アプリケーション
の応答時間を短縮することで, Web アプリケーションのユーザビリティ向上を目的としてい
るためである. しかし, Web アプリケーションの応答時間を短縮するための要素として, ま
– 23 –
第 2 章 Web アプリケーションに対する優先転送方式
だ検討すべき問題が残る. それは, Web アプリケーションの TCP 通信に先立って行われる,
DNS による名前解決の遅延である.
一般的な Web アプリケーションである Web ブラウザを用いて, Web サーバへアクセス
する場合の流れについて考える. Web ブラウザが Web サーバへアクセスするときの DNS
による名前解決処理の流れを図 2.11 に示す. このとき, 一般的には HTTP と DNS を用い
て通信が行われる [12],[13],[14]. HTTP は通信時に TCP を用いるため, 提案方式において
は優先制御されるが, DNS は通信時に UDP を用いるため, 提案方式では優先制御されない
点に着目する.
まず, クライアントのリゾルバがローカル DNS サーバに対して DNS 問い合わせを行う.
ローカル DNS サーバは, クライアントから IP アドレスの問い合わせを受信すると, 問い合
わせのあったアドレスに対応するレコードがローカル DNS サーバにキャッシュされていな
ければは上位の DNS サーバに問い合わせを行う. クライアントから問い合わせに対応する
レコードがローカル DNS サーバにキャッシュされている場合, ローカル DNS サーバはそ
の情報をクライアントへ応答する. また, クライアント自身にキャッシュされている場合も
同様に, DNS サーバへ問い合わせる必要がないため, UDP パケットのスケジューリングに
関する問題は発生しない. そのため, この場合は外部の DNS サーバと通信を行う必要がな
いため, DNS 問い合わせによるスケジューリング遅延は増大しない.
一方, 問い合わせに対応するレコードがローカル DNS サーバにキャッシュされていない
場合は, ルート DNS サーバから下位 DNS サーバへ反復的に問い合わせることで, 対応する
IP アドレスを取得する. この場合は, 外部の DNS サーバと通信を行うため, スケジューリン
グによる遅延が起こりうる. しかし, DNS で用いられる UDP パケットは最大でも 512Byte
であるため, スケジューリングによる遅延の影響は少ないといえる. その後, クライアント
はローカル DNS サーバより得た IP アドレスを用いて, Web サーバへアクセスする. Web
サーバへのアクセスは HTTP を用いて行われるため, 提案方式によって優先制御される.
– 24 –
2.7 フローテーブル
DNS Server
( Root, ... )
DNS Server
( Local )
2. Iterative inquiry
( DNS )
1. Recursive inquiry
( DNS )
3. Web access
( HTTP )
Client PC
Web Server
図 2.11 DNS による名前解決処理の流れ
多くのレコードがローカル DNS サーバやクライアント自身にキャッシュされることと,
DNS で用いられる UDP パケットの最大サイズが 512Byte であることを考慮すると, 提案
方式の複雑化は避ける必要がある点からも, DNS 問い合わせ時のパケットを優先制御する
必要は無いと判断する.
2.7
フローテーブル
提案方式では, フローテーブルというフロー情報を記憶する領域を用いて, フロー情報を
管理する. そして, フローテーブルの情報をもとに, クラシファイアがフローの識別を行う.
本項では, フローテーブルにおけるフロー情報の管理方法とフロー情報が更新されるタイミ
ングについて述べる.
– 25 –
第 2 章 Web アプリケーションに対する優先転送方式
2.7.1
フローテーブルが管理する情報
フローテーブルは, フローを識別するための ID と, フローのシーケンス番号を記憶する.
このとき, 受信したパケットヘッダから抽出する情報を図 2.12 に示す. フローを識別するた
めのフロー ID として記憶する情報は, IP ヘッダから抽出した送信元およびあて先 IP アド
レスと, TCP ヘッダから抽出した送信元およびあて先ポート番号である. これらの値は, ス
リーウェイハンドシェイクのパケットを受信した際に記憶する.
次に, クラシファイアがスロースタートフェーズのフローであるか, 輻輳回避フェーズの
フローであるかを判断する際に用いる指標として, TCP ヘッダからシーケンス番号を抽出
して記憶する. シーケンス番号は, フローテーブルに記憶されているフロー ID のパケット
を受信する度に更新する. このとき, 受信したパケットのシーケンス番号が, フローテーブ
ルに記憶されているシーケンス番号に 1 を加えた値でなければ, フローテーブルからそのフ
ローのフロー ID とシーケンス番号を削除する. フローテーブルにおけるの処理の流れを, 図
2.13 に示す.
IP Header
0
31
・・
・
Source Address
Destination Address
・
・・
TCP Header
0
15 16
31
Destination Port
Source Port
Sequence Number
・
・・
図 2.12
フローの識別に用いる情報
– 26 –
2.8 キュー
クラシファイアが
クラシファイアがパケットを
パケットを
受信
フローテーブルから
フローテーブルから
フローIDを検索
パケットの
パケットのシーケンス番号を
番号を
記憶されている
記憶されている値
されている値と比較
Yes
フローテーブルに
フローテーブルに記憶
されている値
されている値+1
No
フローテーブルが
フローテーブルが記憶して
記憶して
いるシーケンス
いるシーケンス番号を
番号を更新
フローテーブルから
フローテーブルから
シーケンス番号
番号を
シーケンス
番号を削除
図 2.13 フローテーブルおける処理の流れ
2.8
キュー
提案方式では, それぞれのキューに滞留しているパケット量に応じたキュー長が, 最大
キュー長から動的に分割して与えられる. 提案方式におけるキューの概念図を図 2.14 に
示す.
図 2.14 のように物理キューを動的に仮想キューに分割することにより, フローごとに
キュー長を手動で設定する必要が無いためパラメータチューニングが容易になる. また, 提
案方式における全ての仮想キューは, 最低でも 1 パケット分のパケット長を確保するように
実装する. これにより, スリーウェイハンドシェイクパケットの廃棄を抑制する.
– 27 –
第 2 章 Web アプリケーションに対する優先転送方式
FIFO
Enqueue
Dequeue
Proposal method
Enqueue
Dequeue
3-way handshake
Slow start phase
Other flow
図 2.14 提案方式におけるキューの概念図
2.9
スケジューラ
提案方式では, TCP における初期フェーズのフローであるスリーウェイハンドシェイク
パケットを最優先で処理し, スロースタートフェーズのフローを優先して処理する. そのた
め, クラシファイアが 3 つのキューに分類したフローを, スケジューリングする際のアルゴ
リズムが重要になる. 提案方式のスケジューラによるスケジューリングの流れを図 2.15 に
示す.
図 2.15 に示すように, まず High キューに格納されているパケットを送出する. High
キューは最優先で処理する必要があるため, いずれかのキューを処理した後は High キュー
にパケットが格納されていないか確認する. High キューに格納されているパケットの送出
が終わり, High キューが空になったことを確認してから, その他のキューの処理へ移行す
る. 他のキューの処理をしている際であっても, High キューにパケットが格納された場合は
High キューの処理に移行する. これらにより, High キューに最も高い優先度を与えること
ができる.
– 28 –
2.9 スケジューラ
High キューから
キューから送出
から送出
No
Yes
Highキューが
キューが空
No
deq_turn_ mod 2 = 0
Yes
Midiumキューから
キューから送出
から送出
Normalキューから
キューから送出
から送出
deq_turn_ = deq_turn + 1
deq_turn_ = deq_turn + 1
図 2.15 スケジューリングの流れ
次に, Medium キューと Normal キューの処理について述べる.
Medium キューと
Normal キューはラウンドロビンで交互にパケットを送出するキューを入れ替える. このと
き, deq turn という変数を用いてラウンドロビン処理を実現する.
– 29 –
第 2 章 Web アプリケーションに対する優先転送方式
deq turn mod 2 = 0
(2.3)
式 2.3 を満たすときは, Medium キューから 1 パケットを送出する.
deq turn mod 2 = 1
(2.4)
式 2.4 を満たすときは, Normal キューから 1 パケットを送出する. Medium キューまた
は Normal キューから 1 パケットを送出すると, deq turn に 1 を加算することで次に処理
するキューを変更する. また, Medium キューまたは Normal キューが空であった場合も,
deq turn に 1 を加算して次に処理するキューを変更する. これらの処理を, High キューに
パケットが格納されるか, Medium キューと Normal キューが空になるまで繰り返す.
ラウンドロビンで処理を行うため, Medium キューと Normal キューの優先度は同じであ
ると考えられるが, それぞれのキューに格納されるフローの量を考えると Medium キューの
方が優先度が高いといえる. Medium キューに格納されるフローはスロースタートフェーズ
のフローのみであるため, スリーウェイハンドシェイクのパケットとスロースタートフェー
ズのフロー以外の全てのフローのパケットが格納される Normal キューよりも格納される
パケット数が少なくなり, 送出までの待ち時間が少なくなるためである. このようにスケ
ジューリングすることにより, TCP における初期フェーズのフローほど優先してパケット
が送出されるようになり, Web アプリケーションのスループット向上につながる.
2.10
結言
本章では, 提案方式の満たすべき要件について述べ, その要件に対するアプローチ方法を
示した. 提案方式では, クラシファイアがフローテーブルの情報を用いてフローを識別する
ことによって, P2P アプリケーションフローの識別や複雑なパラメータチューニングを必
要としない. さらに, TCP 初期フェーズのフローが優先的に帯域を確保できるようにスケ
ジューラがスケジューリングすることによって, サイズの小さいフローの QoS を保証する.
次章では, 提案するパケットスケジューリングアルゴリズムの効果を検証する.
– 30 –
第3章
NS-2 による検証実験
3.1
緒言
本章では, 前章で述べたパケットスケジューリングアルゴリズムの検証実験の結果につい
て述べ, 有効性を検証する.
3.2
シミュレーション環境
シミュレーションには, ネットワークシミュレータ NS-2 を用いた [15]. このとき用いた
ネットワークモデルを, 図 3.1 に示す. 各フローはサーバノード群から送出され, ルータ 1
およびルータ 2 を経由してからクライアントノード群へ到着する. スケジューリングアル
ゴリズムとして, 提案方式と比較対象とする FIFO をルータに適用してシミュレーションを
行った.
シミュレーションにおける基本パラメータ値を表 3.1 に示す. これらのパラメータに関
しては, 一般的なアプリケーションやネットワークで用いられる値を適用した. リンク容量
に関しては, Web ファイルの容量とは異なり, その大小がシミュレーション結果には影響し
ないと考え, シミュレーション時間短縮のため 100Mbit/s とした. そして, トランスポート
プロトコルには TCP Reno を適用した. また, 各フローのパラメータ設定については後述
する.
本論文のシミュレーションで用いる評価尺度は, 平均スループット, パケット廃棄数, ス
リーウェイハンドシェイクパケット廃棄数, Web ファイル転送に要する時間である. 定常的
– 31 –
第3章
表 3.1
NS-2 による検証実験
シミュレーションにおける基本パラメータ値
パラメータ
値
パケット長
1500Byte
TCP ヘッダ長
40Byte
最大ウィンドウサイズ
64KByte
ボトルネックリンク伝搬遅延
10ms
ボトルネックリンク容量
100Mbit/s
アクセスリンク伝搬遅延
1ms
アクセスリンク容量
100Mbit/s
キューのバッファサイズ
1000packet
にトラフィックが発生している状態と先行してサイズの大きいフローがルータに到着して
いる状態において, これらの項目をボトルネックリンクに提案方式を適用した場合と FIFO
を適用した場合で比較して評価した. FIFO 以外にも, 様々なパケットスケジューリングア
ルゴリズムについても前章で述べてきたが, それらの方式はフローやクラスごとの優先度や
Server nodes
Client nodes
Router1
Bottleneck link
Access link
図 3.1
Router2
Access link
ネットワークモデル
– 32 –
3.2 シミュレーション環境
転送レートを事前に設定する必要がある. つまり, ネットワークの状況に応じたパラメータ
チューニングが必要であるため, 方式としては複雑であるといえる. 提案方式は, パラメータ
チューニングが不要である FIFO の様な実ネットワークにおいて適用が容易な方式を目標
としているため, 評価時の比較対象として FIFO を選択した. また, その他のパケットスケ
ジューリングアルゴリズムが, クラスごとに別のキューへフローを分類した後は FIFO で処
理する事も, 比較対象に FIFO を選択した理由である.
3.2.1
一般的なネットワークトラフィックにおけるシミュレーション結果
ユーザごとの平均スループット
まず, 提案方式および FIFO を適用した場合における, 各ユーザの平均スループットを測
定する. 本シミュレーションでは, 実ネットワークのトラフィックを模した一般的なバック
ボーントラフィックを定常的に発生させる [16]. Web ユーザのフローは 0.03 秒間隔で発生
し, フローサイズは 80Kbyte とする. P2P ユーザのフローは 1.7 秒間隔で発生し, フローサ
イズは 20MByte とする. Video(TCP) ユーザのフローは 1.2 秒間隔で発生し, フローサイ
ズは 4MByte とする. これらのユーザは, フローを異なるサーバノードから発生させること
で, アクセスリンクにおける輻輳の発生を抑制した. 最後に, Video(UDP) ユーザにおいて
は, 4 つのサーバノードからそれぞれ 2Mbps のフローを発生させることで, 合計 8Mbps の
フローを発生させる. これらのフローに両方式を適用した際の, ユーザごとの 10 秒間の平均
スループットを図 3.2 に示す.
ボトルネックリンクに FIFO を適用した結果である図 3.2 では, バックボーントラフィッ
クが一般的なトラフィックモデルになっていることがわかる. そして, ボトルネックリン
クに提案方式を適用した場合は, Web フローのスループットが 10 ％程度, Video(TCP) フ
ローが 7 ％程度向上していることがわかる. 一方, P2P フローのスループットは 20 ％程度
低下している. 提案方式は, 初期フェーズの TCP フローほど優先して送出するため, 多く
のパケットがスロースタートフェーズで転送される Web フローは, スループットが向上し
– 33 –
第3章
60
NS-2 による検証実験
FIFO
Proposed Method
50
)s 40
pb
M
(t
up
hg 30
uo
rh
Te
ga 20
re
v
A
10
0
Web
P2P
User
Video (TCP)
Video (UDP)
図 3.2 ユーザごとの平均スループット
たと考えられる. また, スロースタートフェーズのフローとその他のフローの処理をラウン
ドロビンで交互に行うため, 多くのパケットを輻輳回避フェーズで転送する P2P フローは
送出頻度が下がりスループットが低下した. P2P フローのスループットが低下した影響で,
Video(TCP) フローが帯域を確保しやすくなったため, Video(TCP) フローのスループット
も多少増加したといえる. しかし, これに関しては Video(TCP) フローのスループットが下
がり, P2P フローのスループットが向上する場合もあると考えられる. そして, Video(UDP)
フローはどちらの方式を用いた場合においても, スループットはほとんど変化しないという
結果を得た. これらから, 現在の一般的なトラフィックモデルに提案方式を適用することで,
Web ユーザのスループットを向上させることができた. そのため, Web ユーザのスループッ
トを向上させるパケットスケジューリングアルゴリズムとして, 提案方式の有効性を確認で
– 34 –
3.2 シミュレーション環境
きたといえる. また, P2P フローのスループットを低下させることで, P2P ユーザが帯域の
多くを占有する状況を緩和することができるため, インターネットトラフィックの公平性確
保にも繋がるといえる.
次に, 各フローにおけるユーザのスループットの遷移を図 3.3 から図 3.6 に示す. これは,
バックボーントラフィックを発生させて 10 秒後から 10 秒間の遷移図である. Web ユーザ
のスループットに関しては, 提案方式ではスループットの振れ幅が FIFO と比較すると多
少改善されているように見られるが, その他のユーザのフローに関しては提案方式および
FIFO 共に特徴的な点は見られない. また, スループットは測定する時間によって大きく変
化するため, スループットの遷移図からは提案方式の有効性や問題点を評価することが難し
いといえる. だが, 図 3.4 に関しては, ボトルネックリンクに FIFO を適用した場合と比較
して P2P フローのスループットが劣化していることがわかる. そのため, 提案方式をボトル
ネックリンクに適用することにより, 今現在問題となっている P2P フローの増大によるブ
ロードバンドトラフィックの公平性問題を緩和することができるといえる.
– 35 –
第3章
35
NS-2 による検証実験
FIFO
Proposed Method
30
25
)s
pb20
(M
tu
ph15
gu
or
hT
10
5
0
10
11
12
13
14
15
16
17
18
19
Time (Sec)
図 3.3 Web ユーザのスループット遷移
80
FIFO
Proposed Method
70
60
50
s)p
b
M
(t 40
up
hg
uo 30
rh
T
20
10
0
10
11
12
13
14
15
16
17
Time (Sec)
図 3.4 P2P ユーザのスループット遷移
– 36 –
18
19
3.2 シミュレーション環境
60
FIFO
Proposed Method
50
40
)s
pb
(M
tu30
ph
gu
or
hT20
10
0
10
11
図 3.5
12
13
14
Time (Sec)
15
16
17
18
19
Video(TCP) ユーザのスループット遷移
10
FIFO
Proposed Method
8
)s 6
pb
M
(t
up
hg 4
uo
rh
T
2
0
10
11
図 3.6
12
13
14
Time (Sec)
15
16
17
18
Video(UDP) ユーザのスループット遷移
– 37 –
19
第3章
NS-2 による検証実験
ユーザごとのパケット廃棄数
ここでは, ユーザごとの平均スループットを測定した際の廃棄パケット数を, ボトルネッ
クリンクに提案方式および FIFO を適用した場合で比較して評価した. まず, 各ユーザのパ
ケット廃棄数を図 3.7 に示す. 提案方式をボトルネックリンクに適用した場合は, FIFO と
比較して Web ユーザのパケット廃棄数が減少していることがわかる. これは, 初期の TCP
フローに高い優先度を与えていることと P2P フローによる帯域圧迫が緩和されたことが要
因であると考えられる. 一方, P2P ユーザのパケット廃棄数が減少して Video(TCP) ユー
ザと Video(UDP) ユーザのパケット廃棄数が増加している. これらのユーザのフローは, フ
ローサイズが大きいため Normal キューで処理されることが多い. つまり, この時間帯にお
いては P2P ユーザが多くの帯域を確保していたため, Video(TCP) ユーザと Video(UDP)
ユーザが帯域を確保することができずパケット廃棄数が増加したと考えられる. しかし, 提
案方式の仕様から P2P ユーザのパケット廃棄数と Video ユーザのパケット廃棄数は, 平均
スループットを算出する時間によって異なるといえる.
次に, ユーザごとのスリーウェイハンドシェイクパケット廃棄数をボトルネックリンク
に提案方式および FIFO を適用した場合で比較して評価する. 各ユーザのスリーウェイ
ハンドシェイクパケット廃棄数を図 3.8 に示す. FIFO を適用した場合に Web ユーザと
Video(TCP) ユーザでスリーウェイハンドシェイクパケットが廃棄されていることが図 3.8
からわかる. まず, 提案方式をボトルネックリンクに適用した場合はスリーウェイハンド
シェイクパケットが廃棄されず, FIFO を適用した場合はスリーウェイハンドシェイクパ
ケットが廃棄されている要因を考察する.
– 38 –
3.2 シミュレーション環境
3000
FIFO
Propoed Method
2500
2000
st
ek
ca1500
P
de
pp
ro1000
D
500
0
Web
P2P
User
Video (TCP)
Video (UDP)
図 3.7 各ユーザのパケット廃棄数
40
FIFO
Proposed Method
35
30
25
tse
kc
aP20
de
pp
or 15
D
10
5
0
Web
図 3.8
P2P
User
Video (TCP)
Video (UDP)
スリーウェイハンドシェイクパケット廃棄数
– 39 –
第3章
NS-2 による検証実験
提案方式は, 物理キューを 3 つの仮想キューに分割するが, それぞれのキューにおいて 1
パケットは確実に格納できるようシミュレータに実装している. つまり, Normal キューにお
いて物理キューのパケットバッファの限界までパケットが格納されている状態であっても,
High キューと Medium キューは 1 パケットであれば格納することができる. High キューに
スリーウェイハンドシェイクパケットが格納された場合, Medium キューや Normal キュー
を処理していたとしても最優先でキューから送出されるため, High キューにおいてはパケッ
ト廃棄が生じなかったと考えられる. これは, トレースファイルより High キューに滞留す
るパケット数が, 最大でも 2 パケットであったと確認できたことにより裏付けることができ
る. 一方, 他のパケットスケジューリングアルゴリズムはスリーウェイハンドシェイクのパ
ケットを区別しないため, その他のパケットと同様に扱われる. そのため, 他のパケットスケ
ジューリングアルゴリズムをルータに適用した場合は, スリーウェイハンドシェイクパケッ
トがその他のパケットと同様に廃棄される.
また, FIFO において Web ユーザのスリーウェイハンドシェイクパケット廃棄数が
Video(TCP) ユーザよりも多い理由は, Web フローの送出間隔が Video(TCP) フローより
も大幅に短いためである. そのため, 送出されるスリーウェイハンドシェイクパケットが数
も増加し, それに比例して廃棄されるスリーウェイハンドシェイクパケットの数も増加した
と考えられる.
これらの結果より, スリーウェイハンドシェイクパケットの廃棄数を抑制し, 再送や RTT
の増大によるスループットの低下を抑制する方式として提案方式は有効であるといえる.
サイズの大きいフローが先行してルータへ到着している状態における各ユーザのスルー
プット
ここでは, P2P やビデオといったサイズの大きいフローが先行してルータへ到着している
状況で, Web フローを発生させた場合における各ユーザのスループットを測定し評価する.
まず, 先行してルータへ到着しているフローのスループットを図 3.9 に示す. これは, 各フ
– 40 –
3.2 シミュレーション環境
ローを発生させて 10 秒後の, 各ユーザのスループットである. 提案方式をボトルネックリン
クに適用した場合と FIFO をボトルネックリンクに適用した場合で, 各ユーザのスループッ
トが異なることが図 3.9 からわかる.
提案方式および FIFO 共に公平な状況で評価するために事前のトラフィック状況を均一に
するべきではるが, 提案方式と FIFO では処理内容が異なりトラフィック状況を均一にする
ことは困難であるため図 3.9 のトラフィック状況を用いる. 図 3.9 においては, ボトルネッ
クリンクに提案方式を適用した場合の総スループットは 100Mbps, FIFO の場合は 97Mbps
であった. そのため, 提案方式および FIFO で各ユーザのスループットに多少の違いはあ
るものの, 総スループットはほぼ等しい. 図 3.9 に示すトラフィック状況のときに, Web フ
ローを発生させた.
Web フローのパラメータは, これまでの実験と同じパラメータを用いた. Web フローを発
生させた 1 秒間の, 各ユーザのスループットを図 3.10 に示す. ボトルネックリンクに FIFO
を適用した場合における Web フローのスループットは 5.79Mbps であり, ボトルネックリ
ンクに提案方式を適用した場合における Web フローのスループットは 12.82Mbps であっ
た. これより, 提案方式をボトルネックリンクに適用した場合は, サイズの大きいフローが先
行してルータへ到着している状況においても, ボトルネックリンクに FIFO を適用した場合
と比較して 2 倍以上のスループットを得ることができることを確認した.
– 41 –
第3章
70
NS-2 による検証実験
FIFO
Proposed Method
60
50
)s
pb
40
(M
tu
ph
gu 30
or
hT
20
10
0
P2P
図 3.9
Video (TCP)
User
Video (UDP)
先行してルータに到着しているトラフィック
70
FIFO
Proposed Method
60
50
)s
pb 40
(M
tu
ph30
gu
or
hT20
10
0
Web
P2P
User
Video (TCP)
Video (UDP)
図 3.10 サイズの大きいフローが先行してルータに到着している状態で Web フローを発生
– 42 –
3.2 シミュレーション環境
次に, 図 3.10 のデータを取得した際の, Web ファイルの転送に要した時間を図 3.11 に示
す. 図 3.11 より, ボトルネックリンクに提案方式を適用した場合における Web ファイルの
転送時間が, ボトルネックリンクに FIFO を適用した場合と比較して大幅に短縮されている
ことがわかる. 転送された Web ファイルが 6 つであるのは, FIFO では 1 秒間に 6 ファイル
しか転送することができなかったためである.
これらから, ボトルネックリンクに提案方式を適用することにより, サイズの大きいフ
ローが先行してルータへ到着している状況においても, それらによる帯域圧迫の影響を抑制
し短時間で Web ファイルの転送を終えることができることを確認した. そのため, サイズの
大きいフローが先行してルータに到着している状況において, ボトルネックリンクに適用す
る方式としては提案方式の方が FIFO と比較して有効であるといえる.
0.8
FIFO
Proposed Method
0.6
)c
eS 0.4
(
e
m
iT
0.2
0
1
2
3
Number
4
図 3.11 Web ファイルの転送に要する時間
– 43 –
5
6
第3章
3.2.2
NS-2 による検証実験
80 番ポートを使用するネットワークトラフィックにおけるシミュ
レーション結果
提案方式は, TCP 初期フェーズのフローに優先的に帯域を割り当てる. そのため, リアル
タイム性が要求される音声トラフィックやビデオトラフィックといったフローの扱いが問
題となる [17]. 音声トラフィックやビデオトラフィックのようなストリーミングで通信され
るフローは, 遅延やジッタの増大による通信品質の劣化が大きい. そのため, それらのトラ
フィックの QoS 保証は, その他のトラフィックよりも優先的に行う必要があるので, それら
が混在するネットワークにおいては CBQ や LLQ といったパケットスケジューリングアル
ゴリズムが用いられる場合が多い.
CBQ や LLQ においてトラフィックを分類する際, 80 番ポートのトラフィックとして
HTML ファイルなどを扱う Web トラフィックと, Youtube のようなビデオトラフィックが
同一に扱われる. このとき, ビデオトラフィックのフローサイズは P2P トラフィックほど
大きくないが, 一般的な Web フローと比較すると十分に大きいといえるため, 全てのトラ
フィックが混在する状況と同様にビデオフローが先行してルータに到着している際は Web
フローの帯域が圧迫されることが考えられる. そこで, 80 番ポートを想定したトラフィック
においてこれまでと同様の実験を行うことで, 提案方式が 80 番ポートを分類するキューへ
の適用に適しているか評価を行った.
評価を行う際, 一般的な IP ネットワークにおいて 80 番ポートを扱うキューに割り当てら
れる帯域幅を考慮し, ボトルネックリンクの容量を 50Mbps と変更した.
– 44 –
3.2 シミュレーション環境
ユーザごとの平均スループット
ボトルネックリンクに提案方式および FIFO を適用した場合における, 各ユーザの平均ス
ループットを図 3.12 に示す. これは, 全てのトラフィックを対象とした際の実験と同様に,
トラフィックを発生させて 10 秒後から 10 秒間の平均スループットである. ボトルネックリ
ンクに提案方式を適用した場合の Web フローのスループットは 20.43Mbps であり, FIFO
を適用した場合は 22.35Mbps であった. そして, ボトルネックリンクに提案方式を適用した
場合の Video(TCP) フローのスループットは 25.23Mbps であり, FIFO を適用した場合は
23.14Mbps であった. そのため, 80 番ポートのトラフィックを想定したネットワーク環境
においても, 提案方式では Web フローのスループットを 2Mbps 程度向上することができ,
Web フローのスループットを向上させる手段として有効であることを確認した.
30
FIFO
Proposed Method
25
)s 20
pb
M
(t
up
hg 15
uo
rh
T
eg 10
ar
ev
A
5
0
Web
図 3.12
User
Video (TCP)
提案方式および FIFO におけるユーザごとの平均スループット
– 45 –
第3章
NS-2 による検証実験
ユーザごとのパケット廃棄数
次に, ユーザごとの平均スループットを測定した際の廃棄パケット数を, ボトルネックリ
ンクに提案方式および FIFO を適用した場合で比較して評価する. まず, 各ユーザのパケッ
ト廃棄数を図 3.13 に示す. 提案方式をボトルネックリンクに適用した場合は, Video(TCP)
パケットの廃棄数が 700 パケット程度増加していることが図 3.13 からわかる. しかし, これ
はデータを取得する時間によって異なるため提案方式の特性が表れたためではなく, この値
が直接 Web フローのスループット向上に繋がったとは考えにくい.
次に, 図ボトルネックリンクに提案方式および FIFO を適用した場合における, スリー
ウェイハンドシェイクパケットの廃棄数を 3.14 に示す. ボトルネックリンクに提案方式を適
用した場合は, Web と Video(TCP) のスリーウェイハンドシェイクパケットが廃棄されて
いないことが図 3.14 からわかる. パケット廃棄により生じる遅延が最も大きいスリーウェ
イハンドシェイクパケットの廃棄を抑制できたため, Web ユーザはスロースタートフェーズ
で適切に帯域が確保できたと考えられる. その結果, Web ユーザのスループットが向上した
といえる.
これらより, 80 番ポートを使用するトラフィックに適用するスケジューリングアルゴリズ
ムとして, 提案方式は Web ユーザのスループットを向上させるという観点において有効で
あるといえる.
– 46 –
3.2 シミュレーション環境
4500
FIFO
Proposed Method
4000
3500
3000
st
ek2500
ca
Pd
ep2000
po
rD1500
1000
500
0
Web
図 3.13
User
Video (TCP)
各ユーザのパケット廃棄数
35
FIFO
Proposed Method
30
25
st 20
ek
ca
P
de 15
pp
or
D10
5
0
Web
User
Video (TCP)
図 3.14 スリーウェイハンドシェイクパケット廃棄数
– 47 –
第3章
NS-2 による検証実験
サイズの大きいフローが先行してルータへ到着している状態における各ユーザのスルー
プット
ここでは, ビデオフローが先行してルータへ到着している状況で, Web フローを発生させ
た場合における各ユーザのスループットを測定し評価する. まず, 先行してルータへ到着し
ているビデオフローのスループットを図 3.15 に示す. ここに, Web フローを発生させた際
のスループットが図 3.16 である. 先行しているビデオフローのスループットは 25Mbps 程
度であり, ボトルネックリンクの帯域の約半分を占めるに過ぎない. そのため, 帯域にかな
り余裕がある状態で Web フローを発生させることができる. その結果, ボトルネックリン
クに FIFO を適用した場合においても, ボトルネックリンクに提案方式を適用した場合と同
程度のスループットを確保することができている. しかしながら, 提案方式をボトルネック
リンクに適用した方が, 1.28Mbps 程度スループットを向上することができた. そして, Web
ファイルの転送に要する時間は, 3.17 に示すように提案方式をボトルネックリンクに適用し
た場合の方が 0.026 秒短縮されている.
これらより, 全てのトラフィックを使用してシミュレーションを行った場合と比べ, 80 番
ポートのトラフィックのみを用いてシミュレーションを行った場合に得られた効果は低かっ
たものの, FIFO と比較して提案方式が Web アプリケーションの応答時間の向上に効果的
であることを確認した.
– 48 –
3.2 シミュレーション環境
30
FIFO
Proposed Method
25
20
)s
pb
M
(t 15
up
hg
uo
rh 10
T
5
0
図 3.15
Video (TCP)
User
先行してルータに到着しているビデオトラフィック
30
FIFO
Proposed Method
25
20
)s
pb
M
(t 15
up
hg
uo
rh 10
T
5
0
Web
User
Video (TCP)
図 3.16 ビデオフローが先行してルータに到着している状態で Web フローを発生
– 49 –
第3章
0.3
NS-2 による検証実験
FIFO
Proposed Method
0.25
0.2
)c
eS0.15
(
e
m
iT
0.1
0.05
0
1
2
3
4
5
6
7
8
9
10
Number
図 3.17 Web ファイルの転送に要する時間
3.3
結言
本章では, 提案したパケットスケジューリンアルゴリズムの効果を検証するため, 実ネッ
トワークのトラフィックを想定したネットワーク環境において評価実験を行った. そして,
CBQ や LLQ への適用を想定して 80 番ポートのトラフィックを想定したネットワーク環境
においても実験を行った. 実験結果より, 提案方式をボトルネックリンクに適用することに
より, どちらの場合においても Web アプリケーションの応答時間を短縮できることを確認
した.
– 50 –
第4章
結論
本論文では, サイズの大きいフローがルータへ到着している状況においても, サイズの小
さいフローを扱う Web アプリケーションが帯域を確保することが出来る方式を考案した.
本提案方式は, スリーウェイハンドシェイクのパケットとスロースタートフェーズのパケッ
トを優先して処理する事で, それらのフローに対する優先帯域割り当てを実現した. これは,
到着したパケットを分類するクラシファイア, スロースタートフェーズのフローの識別 ID
とシーケンス番号を記憶するフローテーブル, クラシファイアが分類されたパケットをスケ
ジューリングして送出するスケジューラにより構成される.
ボトルネックリンクに提案方式を適用する実験より, スリーウェイハンドシェイクパケッ
トの廃棄を抑制できることを確認した. スリーウェイハンドシェイクパケットの廃棄が無く
なることで, Web アプリケーションが初期フェーズで適切に帯域を確保できるようになり,
ボトルネックリンクに FIFO を適用した場合と比較して高いスループットを得ることがで
きた. その結果, Web ファイル転送に要する時間が短縮できたため, Web アプリケーション
の応答時間を向上させるスケジューリングアルゴリズムとして提案方式は有効であるとい
える.
– 51 –
第 4 章結論
4.1
今後の展望
今後の展望として, 以下の点が挙げられる.
• 実ネットワークで検証
本論文では, 提案方式の有効性をネットワークシミュレータを用いて検証した. その結
果, 本提案方式をボトルネックリンクに適用することで, 今後サイズの大きいフローの
割合が増加したとしても, それらのフローによる帯域圧迫から Web アプリケーション
フローを保護することが可能になったと考えられる. しかしながら, 本論文においては
提案方式の評価指標として RTT を用いていない. これは, パケットの送信時間及び受
信時間といった出力結果から, 各フローの RTT を算出することが困難であったためで
ある. だが, RTT の値から Web アプリケーションの応答時間短縮を確認することで,
提案方式の有効性をより詳細に示すことができるといえる. そのため, 今後はルータに
実装を行い, 様々なネットワーク環境で RTT を含めた更なる検証を進めていく必要が
ある. これにより, 実ネットワークへの適用が実現可能になるといえる.
• パケットバッファの管理方法
本提案方式では, パケットバッファの管理方法として Drop-Tail を適用した. これは,
提案方式はパケットスケジューリングアルゴリズムであるため, パケットバッファの
管理方法は実装時にユーザが選択するべきであると考えていたためである. しかし, 提
案方式の拡張性を考えた場合, RED(Random Early Detection) や WRED(Weighted
Random Early Detection) といった輻輳回避手法を適用することで, どの様な効果が得
られるか検証することも有効であると考えられる.
– 52 –
謝辞
本研究を行うにあたり, 多くの御指導, ご鞭撻を賜りました, 情報システム工学科島村和
典教授には, 心より感謝の意を表すと共に, 厚く御礼申し上げます. 島村先生から頂いた数多
くの御助言によって, 研究者としても, 一人の人間としても成長できたと思います. これから
先の人生, 厄年を侮ることなく生きていきます. 数多く御迷惑をかけ申し訳ありませんでし
た. ありがとうございました.
情報システム工学科福本昌弘教授には, 本研究論文の副査をお引き受け頂き, 貴重な御意
見を頂きました. 心より御礼申し上げます. 私が未熟なばかりに多くの御迷惑をおかけして,
申し訳ありませんでした. 本当にお世話になりました.
情報システム工学科吉田真一講師には, 本研究論文の副査をお引き受け頂き, 貴重な御意
見を頂きました. 心より御礼申し上げます. 実験などで接する機会が多かったため, 普段か
ら数多く御助言を頂きました. 本当にお世話になりました.
実験 3A・4A の TA を通して得た知識や経験は, 今後どんな新しい技術が開発されたとし
ても, それを習得するための土台となってくれると思います. ありがとうございました.
本研究を進めるにあたり, 多くの御助言, 御指導を賜った高知工科大学情報システム工学
科の教員およびスタッフの方々, 心より御礼申し上げます.
研究室の同輩として, 常日頃から御意見, 御協力を頂きました当大学院修士課程井上健志
氏, 徳弘裕人氏に心より感謝致します.
研究室の後輩として, 多くの御支援を頂いた当研究室の方々に心より感謝致します. 特に
岩城, 君が焼き肉に連れて行ってくれる日が来ることをこれから先も心待ちにしています.
最後に, 大学院まで進学させて頂いた両親に, 心より感謝致します. ありがとうございま
した.
– 53 –
参考文献
[1] Youtube, http://www.youtube.com/, January 2010.
[2] Cisco Systems, Inc.“Hyperconnectivity and the Approaching Zettabyte Era,”June
2009.
[3] N.Basher, A.Mahanti, C. Williamson, and M. Arlitt,“A comparative analysis of
Web and peer-to-peer traﬃc,”WWW, pp.287-296, April 2008.
[4] 戸田巌, “詳解ネットワーク QoS 技術,”オーム社, 2001.
[5] 長健二朗,“QoS 制御技術 Intserv と Diﬀserv,”Internet Week, December 1998.
[6] 島上洋一, 島村和典,“WEB アプリケーションの応答時間を向上するスケジューリン
グ方式の提案,”平成 21 年度電気関係学会四国支部連合大会講演論文集, pp169.
[7] S.Sen and J. Wang,“Analyzing peer-to-peer traﬃc across large networks,”
IEEE/ACM Trans. Netw., vol.12, no.2, pp.219-232, April 2004.
[8] Cisco Systems, Inc.“Congestion Management Overview,”
[9] 長健二朗, 福田健介, 江崎浩, 加藤朗, 村井純,“ISP から見たブロードバンドトラ
フィックの現状,”Internet Week, November 2008.
[10] W.R. Stevens, “TCP/IP Illustrated, vol.1 The Protocols,”Addison-Wesley, 1994.
[11] 長谷川剛, 村田正幸, “高速・高遅延ネットワークのためのトランスポート層プロトコ
ル,”信学技報, IN2006-169, June 2006.
[12] R. Fielding, J. Gettys, J. Mogul, H. Frystyk, and T. Berners-Lee,“Hypertext Transfer Protocol – HTTP/1.1,”RFC 2068, January 1997.
[13] P. Mockapetris,“Domain Names - Concepts and Facilities,” RFC 1035, January
1997.
[14] P. Mockapetris,“Domain Names - Implementation and Speciﬁcation,”RFC 1035,
November 1987.
– 55 –
参考文献
[15] The Network Simulator - NS2, http://www.isi.edu/nsnam/ns/, January 2010
[16] H. Schulzrinne, S. Casner, R. Frederick, and V. Jacobson,“RTP: A Transport
Protocol for Real-Time Applications,” RFC 1889, January 1996.
[17] S. Floyd and V. Jacobson, Random early detection gateways for congestion avoidance,”IEEE/ACM Transactions on Networking, vol.1, pp.397-413, August 1993.
– 56 –

Web アプリケーションの応答時間を 向上させるパケット

Comments

Description

Transcript

Web アプリケーションの応答時間を向上させるパケット