平成 12 年度
学士学位論文ネット ワークト ランスファ性能評価とその高機能化に関する研究

A study on the high speed network transfer based on
Packet Assembly method and its performance
evaluation

1010373

浦西

慶規

指導教員

島村

和典

2001 年 2 月 5 日
高知工科大学 情報システム工学科

要 旨ネットワークトランスファ性能評価とその高機能化に関する研究
浦西慶規

大容量高速ネットワークの発展に伴い, ネットワークアプリケーションによるサービ スは量だけでなくその種類も急激に増加している. さらに多くのサービ スが考え出され , ネット
ワークに対する期待は非常に大きくなっている.
しかし IP はベストエフォート型の転送制御なので , 大容量高速ネットワークとして回線容量を増加させるだけでは, アプリケーションごとに必要な Quality of Service を十分に満たすことができなくなってきた. QoS パラメータには Throughput や LossRate, Hop 数, Delay,

Delay Jitter などがある.
本論文ではまず , 行き先が同じであるパケットをルータでまとめて一つのパケットにし 転送する方式を提案する. これによりネットワークを流れるパケット数を減らせることから, ト
ラヒック転送時にルータのヘッダ 処理の負荷軽減が可能となりより効率良くデータを転送することが可能になる. その具体的な方法とし てルータによるパケットの組み立て (Packet

Assembly) を提案した.
パケットをアセンブ リすることにより発生する Delay は , リアルタイム系のトラヒックにかえって悪影響を与える懸念があるが , それに対する方策として, リアルタイム系トラヒッ
クは優先的に転送する Priority Queuing と PacketAssemlby を組合せた Priority Queuingwith Assemlby について述べる. 本論文ではシミュレーションを行い, Packet Assembly がどのように QoS 向上につながるかを明らかにしている.

{i{キーワードパケットアセンブリ, プライオリティキューイング , 実時間トラヒック, 負荷軽減, ルータ, 最大転送単位{ ii {

Abstract
A study on the high speed network transfer based on Packet
Assembly method and its performance evaluation
Yoshiki Uranishi

The networks are getting expanded and higher throughput transferable. And the
Network Application Services have increased rapidly not only in quantity but also theirtypes. Many network applications are being added, but carrent network technologies
couldn't respond their requirements at all. But it is very dicult to build high capacity
networks under satisfying the parameter of QoS using IP network technologies basedon best e ort policy. There are same QoS paramaters of Throughput and LossRate,the number of Hop, Delay, DelayJitter, and so on. In this study, the packets which
destinations are same are collected with a router connected into one packet and transfered. It becomes possible that data is transferred more eciently because the load
for the header processing in routers are reduced by decreasing the number of packets.
Assembling of the packets on the router is proposed concretely. But the Delay producedby assembling packets can in uence on delay sensitive trac such as by real time applications. Priority Queueing with Packet Assembly is proposed for the concern. It issimulated and mentioned in this thesis how QoS is improved by PacketAssembly.
key words

PacketAssembly PriorityQueuing RealtimeTrac LoadReduction Router

MTU{ iii {

目次
第1章

1.1
1.2

1.3

1.4
第2章

2.1
2.2
2.3
2.4
2.5

第3章

3.1
3.2

1

はじめに
研究の背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
既存の技術, 研究 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.2.1 MPLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Fragmentation を使ったパケット合成 . . . . . . . . . . . . . . . . . 2
課題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.3.1 パケット毎のヘッダ 処理によるルータの負荷 . . . . . . . . . . . . . 3
1.3.2 MTU より遥かに小さいパケット . . . . . . . . . . . . . . . . . . . 4
研究の目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56パケット アセンブリ....................... 6
パケットアセンブリの IP ヘッダ 操作 . . . . . . . . . . . . . . . . . . . . . 7
アセンブリパケットフォーマットの考察 . . . . . . . . . . . . . . . . . . .
9Priority Queuing with Assemlby 方式 . . . . . . . . . . . . . . . . . . . 10
パケットアセンブリの手順 . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.5.1 アセンブリキューイング . . . . . . . . . . . . . . . . . . . . . . . 11
2.5.2 Priority Queuing with Assembly . . . . . . . . . . . . . . . . . . 11
2.5.3 アセンブリパケットの分離 . . . . . . . . . . . . . . . . . . . . . . 12
パケットアセンブリのシステム

14

シミュレーション実験と結果

ns によるシミュレーションの条件 . . . . . . . . . . . . . . . . . . . . . . . 14
パケットサイズと帯域による遅延時間の違いのシミュレーション . . . . .
15
3.2.1 シミュレーション実験 . . . . . . . . . . . . . . . . . . . . . . . . . 15

{ iv {

目次

3.2.2
3.2.3
3.3

3.4

3.5
第4章

4.1
4.2
4.3
4.4
4.5
第5章

5.1
5.2
5.3
5.4

シミュレーション結果 . . . . . . . . . . . . . . . . . . . . . . . . .

..................................
パケットアセンブリシミュレーション . . . . . . . . . . . . . . . . . . . .
3.3.1 シミュレーション実験 . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2 シミュレーション結果 . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.3 考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Priority Queuing with Assembly シミュレーション . . . . . . . . . . . .
3.4.1 シミュレーション実験 . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.2 シミュレーション結果 . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.3 考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
むすび . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16
17
17
17
18
19
19
19
20
20
21

考察

23

考察

. . . . . . . . . . . . . . . . . . . . . . . . 23
アセンブリするパケット . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
パケットアセンブリ時にエッジルータにかかる負荷 . . . . . . . . . . . . .
24
アセンブリパケットの Loss . . . . . . . . . . . . . . . . . . . . . . . . . . 24
基幹ネットワークルータの負荷が低い場合 . . . . . . . . . . . . . . . . .
25
パケットアセンブリの必要性

今後の課題

26

.................
マルチフローアセンブリ . . . . . . . . . . . . . . . . . . . . . . . . . . .
パケット転送スケジューラによるパケットアセンブリ . . . . . . . . . . .
ルータ内遅延を含めたシミュレーション . . . . . . . . . . . . . . . . . . .

26
26
27
27

アセンブリのパケットフォーマットと負荷

謝辞

29

参考文献

30

{v{

図目次
1.1 Hop 数 [2] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 パケットサイズの分布 [1] . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

2.1 ネットワーク構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 IP ヘッダの構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 連結の操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 パケットフォーマットの方式 . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.5 PriorityQueueingwithAssemlby . . . . . . . . . . . . . . . . . . . . . . . . 10
2.6 Packet Assemlby . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.7 Priority Queuing with Assemlby . . . . . . . . . . . . . . . . . . . . . . 13
2.8 アセンブリパケットの分離 . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.1 シミュレーション . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 結果 UDP パケット遅延（ 中央値） . . . . . . . . . . . . . . . . . . . . . .
3.3 結果 UDP パケット遅延（ 最大値） . . . . . . . . . . . . . . . . . . . . . .
3.4 シミュレーションモデル . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 パケットアセンブリによる実時間通信パケットへの影響 . . . . . . . . . . .
3.6 シミュレーションモデル . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7 priority Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.8 PriorityQueuing 導入比較 . . . . . . . . . . . . . . . . . . . . . . . . . .

15
16
16
18
18
20
21
22

5.1 scheduler によるアセンブ リ . . . . . . . . . . . . . . . . . . . . . . . . . . 27

{ vi {

表目次
1.1 IP の MTU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.1 フォーマットの考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

{ vii {

第1章

はじめに
1.1

研究の背景

大容量高速ネットワークの発展に伴い, ネットワークアプリケーションサービ スは量だけでなくその種類も急激に増加している. さらに多くのサービ スが考え出され , ネットワーク
に対する期待は非常に大きくなっている.
ただ 大容量高速のネット ワークとし て回線容量を増や すだけでは , アプ リケーションごとに 必要な QoS 条件を十 分に 満たすことができな くなってきた.

QoS パラ メータにはThroughput や LossRate, Hop 数, Delay, Delay Jitter などがある. インターネットユーザの急増によるネットワークへの負荷が大きくなり , これらのパラメータを十分に満たすことはさらに難しくなってきた.
IP トラヒックは今までの音声通信のトラヒックを越え, その増加勢いは爆発的なものである.
次世代ネットワークは IP プロトコルによる統合化か進むと考えられている. 現在の IP は
ベストエフォートポリシーに基づいているのでアプ リケーションに応じたトラヒックの制御（ 優先制御など ）を行なっていない . 限られた帯域の中ですべてのトラヒックを平等に扱っていたのではトラヒックの混雑時に通信の品質は下がってし まう. そこでアプリケーションの特性に応じたトラヒックの制御をするパケット転送方式を提案する.

{1{

1.2 既存の技術, 研究

1.2,

既存の技術 研究1.2.1 MPLS
パケット転送の負荷軽減の技術として MPLS（ Multi-Protocol Label Switch ）がある. これはパケット転送情報として, IP アド レ スより下位レ イヤの情報（ ラベル ）を利用し , ルー
タの負荷を軽減するものである.
欠点としては , 一つずつのパケットの処理の負荷軽減はできても PerPacket で処理負荷がかかっていることに変わりはないことや MPLS に対応するエッジルータ, コアルータが必要なことなどがある.

1.2.2 Fragmentation を使ったパケット 合成
パケットを合成するという意味で PacketAssembly と似た考え方とし て, Transparent or

intra-network fragmentation がある. これは MTU が小さいリンクでフラグ メントを行い,
MTU が 大きいリンクになれば すぐ に合成するという方法である. これによりそれぞれのルータ間で適したパケットサイズに変更し効率の良い転送ができること考えられる.
しかし 繰り返し Fragment, Defragment を行うことによりそのつど Delay が生じたり , その処理によりルータに多くのプロセッサ負荷がかかる. また転送の最初の HOP の MTU より
はパケットサイズが大きくなることができないという欠点がある.
パケットの Defragment については , 経路 MTU 探索により fragment されたパケットがネッ
トワークを流れることはほとんどないため行えないことがわかった.

1.3

課題

ネットワーク QoS の保証をするための方法としては , 一つは限りなく無限に近い帯域を用意して混雑なしのネットワークを構築する方法ともう一つ限られた帯域の中でそれぞれのア
プリケーションの必要に応じたパケット転送法を用いることにより効率よく転送する方法が{2{

1.3 課題
考えられ る.

1.3.1 パケット 毎のヘッダ処理によるルータの負荷
転送したいデ ータの量が多くなるにつれて, 決められたネットワークの帯域の中でいかにIP パケットをより高速に大量に処理するかが今後のネットワークの重要な課題となる. IP
トラヒックをルーティングする際に IP パケットごとにヘッダ を見て処理していたのでは高速に転送できない.
ルーティングの負荷は per-bit よりも per-packet で決まる.per-packet で行われる処理としては , ルーティングの決定, パケットヘッダの処理, チェックサム計算, 入出力キュー間の移動がある. よってルータのスループットは最大サイズのパケットが送られ時に最大となる.
過大なトラヒックによりルータへの負荷が増大すると各ルータ毎でパケット転送が遅れて大きな遅延を与えたりまたは処理しきれずそのまま破棄され るということが 起こる. またホップ数の増加により各ノード 毎のヘッダ処理による負荷がかかると , 各ノード 毎の遅延が積み重なって大きな遅延となってし まう. ホップ数は図 1.1 のようになっており, 平均 16 ホップ
で現在も増加の傾向にある.

Hop Distance Distribution

図 1.1

Hop 数 [2]{3{

1.3 課題

1.3.2 MTU より遥かに小さいパケット
図 1.2 は MCI の vBNS トラヒックの調査によるものである. 1500Bytes 以下のパケット

Logarithmic-scale
packet size histogram

図 1.2 パケットサイズの分布 [1]がほぼ 100%のトラヒックを占めている. また 44Byte 以下のパケットがほぼ 半数である.

MTU（ 最大転送単位）はネットワークの転送方により扱えるパケットの最大サイズを各ネッ
トワークによって定められている. 各ネットワークの MTU は表 1.1 に示す. これらの MTU
より遥かに小さいサイズのパケットがルーティングされて各ノード を次々に経由して流れることは , 効率がよくない .
このようなパケットが転送されている原因として, MTU の小さいネットワークから MTUの大きいネットワークへパケットが転送され るときそのままの小さいパケットで転送されていること , また機器の調整によって MTU より遥かに小さいパケットに分割されてネット
ワークへ転送されていることがある.

{4{

1.4 研究の目的
表 1.1

1.4

IP の MTU

ネットワークMTU(Bytes)

IP の最大 MTU

65535

IP over ATM

9180

トークンバス

8166

トークンリング

4464

FDDI

4352

イーサネット

1500

PPP

1500

IP の最小ＭＴＵ

68

研究の目的

本研究の目的は, 近年のトラヒック増大に対応するため, 限られた帯域の中で , それぞれのアプ リケーションに適応したトラヒック制御を行うことにより, 効率のよい転送を行いネットワーク QoS を向上させることである.
基幹ネットワークにおいては, パケットを個々に処理するのではなく行き先ごとにまとめて転送する. 基幹ネットワークルータの IP パケット処理負荷軽減をのために , MTU の小さい
ネットワークから MTU の大きいネットワークへパケットを転送する際, MTU の大きくなるルータで行き先が同じである複数のパケットを一つにまとめて転送する方式（ パケットア
センブリ）を提案する.[3]
パケットがまとめられた分だけヘッダ 処理の回数を削減でき, 基幹ネットワークではパケッ
ト毎の処理の負荷がなくなり効率良くデータ転送が行える.

{5{

第2章

パケット アセンブリ
2.1 パケット アセンブリのシステム
NetworkD

NetworkC

EdgeRouter
EdgeRouter

EdgeRouter
EdgeRouter
CoreRouterServerServer
CoreRouter

CoreRouter

EdgeRouter

EdgeRouter
EdgeRouter

NetworkA
NetworkB

図 2.1 ネットワーク構成

パケットアセンブ リは基幹ネットワークの端で一度アセンブリすれば , それ 以降の途中のルータでは通常の IP として転送でき, 再びエッジルータへ到着したときに分離すればよい.
よって基幹ネットワークのエッジルータにのみ実装すればパケットアセンブリシステムが構築できる.
アクセスネットワークから基幹ネットワークへパケットが転送される際にエッジルータで行{6{

2.2 パケットアセンブリの IP ヘッダ 操作
き先の同じパケットを一つにまとめるパケットアセンブ リを行う. アセンブ リされたパケッ
トは基幹ネットワークルータを効率良く転送され る. その後, 基幹ネットワークからでるときはエッジルータで分離されアセンブリ前の元の状態にパケットにもど されてから次のネットワークへ転送される.
例として図 2.1 ようにネットワークＡから転送された３つのパケットはエッジルータで一つのパケットにまとめてアセンブリされ , 基幹ネットワークに転送される. このとき基幹ネット
ワーク内のそれぞれのルータではヘッダ処理が３分の１でデータを転送することが可能である. 基幹ネットワークを出てネットワークＤへパケットを転送する際には , ネットワークＤはそのままのアセンブリされたパケットを受け取ることができないので, エッジルータで元ど おりのパケットに分離してからネットワークＤへ転送される.

2.2 パケット アセンブリの IP ヘッダ操作
図 2.2 に IP ヘッダ の構造を示す. ルータの IP 処理部では , 到着した IP パケットの大き
versionIHL Type Of Service
Total Length
Identification Flags
Flagment
OffsetTime To Live Protocol
Header Checksum
Source Address
Destination Address
OptionPadding

図 2.2

IP ヘッダの構造

さは, IP ヘッダの Total Length で見分けられている. よって DestinationAddress が同一である IP パケットを連結し , 先頭の IP パケットのヘッダ部の Total Length を連結した長さ分だけ増加させる. またデ ータが書き変えるられたので , ヘッダにエラーがないかを確かめるための Header Checksum を再計算が必要である. これにより次のホップのルータでは ,後続のパケットは先頭 IP パケットのデータ部になり , 一つのパケットとしてルーティングされる. 図 2.3 を例にすると, まず Destination

Address が同一である 2 つの IP パケットを連結させる . この２つのパケットサイズはそれぞれ 40Bytes であり , 連結させたサイズは{7{

2.2 パケットアセンブリの IP ヘッダ 操作
versionIHL Type Of Service
40ByteIdentification Flags Flagment
OffsetTime To Live Protocol
Header Checksum
Source Address
172.21.33.51

versionIHL Type Of Service
80ByteIdentification Flags Flagment
OffsetTime To Live Protocol
Header Checksum
Source Address
172.21.33.51

DataversionIHL Type Of Service
40ByteIdentification Flags Flagment
OffsetTime To Live Protocol
Header Checksum
Source Address
172.21.33.51

Data

Data

図 2.3 連結の操作

80Bytes である. よって先頭の IP ヘッダの Total Length にサイズ 80Byte という値を代入することで１つのパケットとなる. ここで問題となるのは, 先頭 IP ヘッダの Total Length
を書き換えたことにより元のパケットのサイズを失ったことになる . この場合パケットをどこで分離すれば良いかが分からなくなってしまう. そこで , 先頭 IP ヘッダの後ろにパケット
アセンブ リヘッダを追加するか , IP ヘッダにはオプション 部分を存在させることができる.
この領域に元のヘッダの Total Length の値を代入すれば先頭パケットのサイズを失うことはない . Time To Live は , パケットがネットワークの経路のループのために永久に転送され続けることを防ぐ . アセンブリされたパケットの先頭以外のヘッダは ,Time To Live を減らされることがない. このまま分離してしまうとホップ数が不正な値になってし まう. よって,分離時に基幹ネットワークで Hop した分だけ Time To Live を減算する必要がある.

{8{

2.3 アセンブリパケットフォーマットの考察

2.3

アセンブリパケット フォーマット の考察

パケットアセンブリはヘッダを変更または取り除くことを考えているので , 帯域利用効率が良くなると考えられる. アセンブリパケットのフォーマットとして図 2.4 ４つの方式を例にあげ る.

1
2
3

IP
TCP

4
図 2.4 パケットフォーマットの方式

 方式１; ヘッダの削除は行わずそのままパケットをつなぎ 合わせる方式である. ヘッダの操作は先頭のみで , Length の変更とアセンブ リを行ったことを示す印をつけることである. このためプロセッサ負荷の小さいアセンブ リが可能であると考えられるが , ヘッ
ダの削除を行わないので帯域利用効率の向上はできていない.

 方式２;IP ヘッダを削除してパケットをつなぎ 合わせる方式である. IP ヘッダを削除す
る毎に Length の記憶を行っていく . アセンブ リ時の IP ヘッダの削除や , 分離時の IP
ヘッダ の付与に負荷がかかる. IP ヘッダ を削除した分帯域を有効に使用することができる.

 方式３;IP ヘッダおよび TCP ヘッダを削除してパケットをつなぎ合わせる方式である.
帯域の使用効率は高いが IP ヘッダや TCP ヘッダの削除や, 付与に負荷がかかる. また

TCP ヘッダは, 先頭のヘッダのコピーでは, 元のヘッダの情報を失ってし まう.
 方式４; １の方式と同様にヘッダ削除無であるが , パケットをつなぎ 合わせた後その上からアセンブリヘッダ（ IP ヘッダ ）を追加する方式である. IP ヘッダを付与する分帯域
利用効率は低下するが , アセンブ リ, 分離の負荷はほとんどかからない.
{9{

2.4 Priority Queuing with Assemlby 方式
表 2.1 フォーマットの考察/

プロセッサ負荷

データ量

ヘッダの再現性

適用範囲

方式１

低い

変化無し

容易

すべての IP パケット

方式２

高い

IP ヘッダ 削除

容易

すべての IP

方式３

高い

IP,TCP ヘッダ削除

難（もど せない）

TCP パケットのみ

方式４

低い

IP ヘッダ 追加

容易

すべての IP パケット

表 2.1 のフォーマットについては考察の段階である. これ 以降に出てくるパケットアセンブ
リシミュレーションについては , 方式１のフォーマットによるシミュレーションである.

2.4 Priority Queuing with Assemlby 方式
本方式は 図 2.5 のよ うにアセンブ リを行わない優先キューとアセンブ リを行う非優先
キューの２つのキューを用いる. Queuing 時に Delay センシティブなパケットは優先キューに入れることにより低遅延な転送が可能となる.
それに対して Delay ロバストなパケットは非優先キューでキューイングの待ち時間を利用してアセンブリを行う. これを Priority Queuing with Assembly(PQwA) と呼ぶ.
Priority Queue

Classify

Control of Priority

Non-Priority Queue(Assembly Queue)

図 2.5

PriorityQueueingwithAssemlby{ 10 {

2.5 パケットアセンブリの手順

2.5 パケット アセンブリの手順
パケットアセンブリはキューイング時に行う. その手順を以下に示す. リアルタイムパケッ
ト , ノンリアルタイムパケットの例としてそれぞれ UDP パケット , TCP パケットを用いる.

2.5.1 アセンブリキューイング
アクセスネットワークから基幹ネットワークへパケットが転送される時でキューイングされる際, 以下の手順で行う. また図 2.6 にそのフローを示す.

1. 到着したパケットはヘッダの PacketType を見る.UDP パケットであった場合は通常ど う
りのキューイングを行う.
2.TCP パケットであった場合そのパケットのアド レスと, それまでにキューイングされていたパケットの中で , 同一のアド レ スのパケットがあるかど うかを検索する. 同一のアド レスのパケットが無ければそのままキューイングする.
3. 同一のアド レ スのパケットがあった場合, そのパケットが６回以上アセンブ リされたパケットならばアセンブリは行えないのでそのままキューイングする.
4. ５回以下であればヘッダにアセンブリの印をつける.
5. アセンブリ回数を１増加させる.
6. アセンブリした分のパケットの長さを変更しキューイングする.

2.5.2 Priority Queuing with Assembly
Priority Queuing with Assembly の場合は, 優先パケット (UDP パケット ) が到着したとき同じキューにキューイングするのではなく優先キューにキューイングする. これにより優
先パケットの遅延を抑えることができる. 図 2.7 にそのフローを示す.

{ 11 {

2.5 パケットアセンブリの手順
packetarrive

UDP

Packet Typequeuing

TCP
Pakcetreference in
Queue(IP Address)

Different queuingsame

Assembly(Within 5 times)

Impossible
Possible

PacketAssembly*Give the mark of assemblyto the header*Assembly number of times + 1*The change of the packet
lengthqueuing

図 2.6

Packet Assemlby

2.5.3 アセンブリパケット の分離
基幹ネットワークからアクセスネットワークへパケットが転送される時でキューから取り出される際, 以下の手順で行う. また図 2.8 にそのフローを示す.

1. 到着したパケットがアセンブリされたパケットかど うかを判別する.
2. アセンブリされたパケットならば何回アセンブリされたパケットかを調べる.
3. アセンブリ回数を１減らす.
4. パケットを分割する.
5. パケットの Length を変更する.
6. 分割されたパケットをキューイングする.

{ 12 {

2.5 パケットアセンブリの手順
packetarrivePriorityqueuing

UDP

Packet TypeTCP
Pakcetreference in
Queue(IP Address)

Different queuingsame

Assembly(Within 5 times)

Impossible
Possible

PacketAssembly*Give the mark of assemblyto the header*Assembly number of times + 1*The change of the packet
lengthqueuing

図 2.7

Priority Queuing with Assemlby
PacketArriveAssembled
PacketNo

queuing

Yes
Assembly
number oftimes

rest is 0

queuing

Assembly
number oftime - 1

PacketSeparate

Change ofpacket length

Queuing
separatedpacket

図 2.8 アセンブ リパケットの分離{ 13 {

第3章

シミュレーション実験と結果
2 章の提案方式につき, その有効性についての基本検証を行った. その検証は ns(Network
Simulator[7]) によるシミュレーション実験とした.

3.1 ns によるシミュレーションの条件
ns のルータ内遅延はキューイングとフォワーディングによってのみ起こる. ルータ内遅延の以外の遅延要素としては ノード ノード 間の LinkDelay がありこれは固定値である. ルー
ティングのヘッダ処理の遅延時間はその測定機能がない.
今回はヘッダ 処理にかかる負荷や遅延時間は , 他のフォワーディングやキューイングなどの遅延に比べて, 極めて小さい値であると考えてそれらの遅延時間については , 測定結果に影響しないことを前提とする. また ns のシミュレーションでは, パケットのデータ部の値はシミュレートされていないので , パケットアセンブリでパケットを合成する際, パケットをつなぎ合わせるのではなく先頭のパケットのサイズを変更し , 他のパケットが一つのパケットにまとめられたことにしている. よって後続のアセンブリされ るパケットのデータは基幹ネッ
トワーク転送時には , 転送されていない. 分離時には元ど おりにしているためデ ータ損失による通信上の影響は無い. ns は , パケットアセンブ リをすることによるパケット転送の順序の入れ替わりによる遅延の{ 14 {

3.2 パケットサイズと帯域による遅延時間の違いのシミュレーション

3.2 パケット サイズと帯域による遅延時間の違いのシミュレー
ション

3.2.1 シミュレーション実験
MTU の許す範囲でアセンブルを行うが, 遅延時間や揺らぎの値に厳しいパケットには, ア
センブ リの処理は行わずに転送する. アセンブ リによりパケット転送は効率化できるが , ア
センブ リされて長くなったパケットの転送に時間がかかることで短いパケットに遅延や揺らぎを起こす可能性がある. この遅延や揺らぎへの影響はバンド 幅にも依存する.
そこで提案するパケットのアセンブ リが行われる基幹ネットワークでは , 長いパケットによる短いパケットの遅延や揺らぎは , バンド 幅の広い場合, 少ないことをシミュレーションで確かめた.[4]
Node1

BandWidth:10,100,1000Mbps
LinkDelay:5ms

UDP:100Bytes
0.4ms/packet

Source

Node3

Node4

Destination
TCP:44,100,1500,8000Bytes

Node2

図 3.1 シミュレーション

図 3.1 のネットワークで Node1 から（ VoIP パケットを想定して ）UDP のパケットサイ
ズ 44 バイトを等間隔で 0.4ms ごとに , Node2 から TCP のパケットサイズを 44, 100, 1500,

8000 バイトと変化させそれぞれ Node3 を通って Node4 ノード まで送信する.
各 TCP パケットサイズでネットワークのバンド 幅を 10 , 100, 1000Mbps と変化させた場
合の UDP パケットの遅延をシミュレータで測定した.

{ 15 {

18

16

14

12

UDP Packet Delay(msec)

3.2 パケットサイズと帯域による遅延時間の違いのシミュレーション
10Mbps100Mbps
1000Mbps
LinkDelay:10msec

10
44

100

1500

8000

TCP Pakcet Size(Bytes)

30

20

UDP Packet Delay(msec)

図 3.2 結果 UDP パケット遅延（中央値）

1044

10Mbps100Mbps
1000Mbps
LinkDelay:10msec

100
1500
TCP Packet Size(Bytes)

8000

図 3.3 結果 UDP パケット遅延（最大値）

3.2.2 シミュレーション結果
バンド 幅 10Mbps, 100Mbps, 1000Mbps での UDP パケットの遅延の中央値を図 3.2 に ,遅延の最大値の比較を図 3.3 に示す. いずれの図も縦軸に UDP パケットの遅延時間, 横軸
は TCP パケットサイズをとっている. アセンブリされた長いパケット（ TCP パケット ）が流れていてもバンド 幅が広くなるに従いその影響が小さくなっていくことがわかる.

TCP パケットサイズが 8000 バイトの長いときでもバンド 幅が 1000Mbps になると UDP
パケットの遅延は 10.001ms 〜 10.065ms （このうち 10ms は Link Delay ）で , そのときの揺らぎは最大でも 64 μ s と小さい.
{ 16 {

3.3 パケットアセンブリシミュレーション

3.2.3

考察

パケットのアセンブ リを行う上で短いパケット 疎通への悪影響が考えられたのでシミュレーションにより検証した . この実験によりバンド 幅の広い基幹ネットワークではアセンブリした長いパケットを流しても, Delay センシティブなパケットに与える悪影響は軽微である. 1 パケットのフォーワーディング遅延時間と帯域の関係は ,PacketSize
Delay = BandWidth(3.1)

であり例えば狭帯域（ 10Mbps ）の場合は ,PacketSize = 8000Bytes  8bit = 0:0064 = 6:4ms
BandWidth
10Mbps
広帯域 (1000Mbps) の場合はPacketSize = 8000Bytes  8bit = 0:000064 = 0:064ms = 64 μ s
BandWidth
1000Mbpsとなり帯域によって遅延時間は大きく変わことがわかる.

(3.2)
(3.3)

3.3 パケット アセンブリシミュレーション
3.3.1 シミュレーション実験
図 3.4 のモデルにおいて, 送信端末 10 端末のうち一つの端末から UDP パケットをアセン
ブ リなし , PacketSize 44Bytes, 送出間隔

5ms で転送, また残りの 9 端末からは TCP パ
ケットをアセンブリあり, PacketSize 1500Bytes で転送する.
9 端末からそれぞれ転送された TCP パケットは, E1 ノード においてアセンブリされいくつかのノード を経由して E2 ノード で分離された後, それぞれの受信端末へパケットが転送される. 残りの１端末から転送された UDP パケットは E1 ノード においてアセンブリされな
い.
9 端末からの TCP パケット送信によってエッジノード にかかる負荷は平均約 48Mbps である. またアセンブリ時にはキューの中に 30 から 40 パケットがエッジノード でスタックされている状態である.
{ 17 {

3.3 パケットアセンブリシミュレーション

Node1

Node11DisAssembly

Assembly
Node2

Node1250Mbps
10Mbps

Node3

EdgeRouter(E1)

EdgeRouter(E2)

Node13

TotalLinkDelay:17ms

Node10Node20

図 3.4 シミュレーションモデルMaximum Delay Time(msec)

3.3.2 シミュレーション結果
30
LinkDelay:17msec
28
TCP
UDP

26
24
22
20
1500

3000

4500

6000

7500

9000

The maximum size of the TCP packet
after Packet Assembly(Bytes)
図 3.5 パケットアセンブリによる実時間通信パケットへの影響

図 3.5 にパケットアセンブ リを行ったときの TCP, UDP パケットのそれぞれの遅延を示す. 縦軸は UDP パケットの最大遅延時間, 横軸は TCP のアセンブリ最大パケットサイズを示す.

{ 18 {

3.4 Priority Queuing with Assembly シミュレーション
パケットをアセンブ リするたびにキューの最後尾にキューイング する仕組みから , TCP パ
ケットの最大アセンブリサイズを大きくするほど , TCP パケットはキューイングされる時間が長くなるため遅延が大きくなる. 逆に UDP パケットは , TCP パケットのアセンブリによる順序の入れ替えで優先されることになった. よって TCP パケットの最大サイズを大きくするほど UDP の遅延は小さくなっていく.

3.3.3

考察

TCP パケットの遅延は , パケットアセンブ リを行わないときと比べて , 最大アセンブリサ
イズを 9000Bytes まで上げ たときでも, その差は約 3ms である. これは TCP の通信の許容範囲内であると考えられ る. し かし TCP パケットのアセンブ リの最大サイズを大きくすれば すればするほど UDP パケットの遅延が小さくなっているが , これは UDP パケットの転送され る割合が 少なかったためであることが考えられる. よって UDP パケットの割合が 多くなれば 大きな遅延を引き起こす可能性は否定できない . また負荷のかかり具合によって TCP パケットのアセンブ リが大きくなっていっているので , アセンブ リ最大サイズ
を 9000Bytes 以上に上げてシミュレーションしてみる必要もある.

3.4 Priority Queuing with Assembly シミュレーション
3.4.1 シミュレーション実験
Priority Queuing を用いることにより, UDP パケットのトラヒックを他のトラヒックよりＥ１ノード で優先制御する Priority Queuing with Assembly のシミュレーションを行った. 3.3 章の図 3.4 のパケットアセンブリシミュレーションと同様のモデルである図 3.6 において実験を行った.[5]{ 19 {

3.4 Priority Queuing with Assembly シミュレーション

Node1

Node11
Priority Queuingwith
Assembly

DisAssembly

Node2

Node1250Mbps
10Mbps

Node3

EdgeRouter(E1)

EdgeRouter(E2)

Node13

TotalLinkDelay:17ms

Node10Node20

図 3.6 シミュレーションモデル

3.4.2 シミュレーション結果
図 3.7 に Priority Queuing with Assembly を行ったときの TCP, UDP パケットのそれ
ぞれの遅延を示す. また図 3.8 に Priority Queuing with Assembly の導入前後の比較を示す. それぞれ , 縦軸は UDP パケットの最大遅延時間, 横軸は TCP のアセンブ リ最大パケッ
トサイズを示す.

E1 ノード でのアセンブ リの際に, Priority Queuing with Assemlby(PQwA) の導入前後
で比較の実験を行った. 図３の結果はアセンブリ後のサイズの最大値をパラメータに UDP,
TCP の遅延を示す. TCP パケットは PQwA を導入前後でほぼ同一で, 最大アセンブリサイ
ズが大きくなるほど 遅延も大きくなる結果となった. UDP パケットは PQwA を導入した時はしなかった時より遅延が抑えられ , 9000Bytes まで TCP パケットをアセンブ リした時でも最大で約 18ms の遅延にとどめられていることがわかった.

3.4.3

考察

Priority Queuing を導入すれば ,TCP パケットの遅延についてはほとんど 変化が無いが ,UDP パケットの遅延の値がかなり低くすることができる. また最大アセンブ リサイズを変{ 20 {

3.5 むすび

Maximum Delay Time(msec)

32
LinkDelay:17msec
28

TCP
UDP(PQ)

24

20

16
1500

3000
4500
6000
7500
8000
The maximum size of the TCP Packet
after Priority Queuing with Packet Assembly (Bytes)
図 3.7

priority Queuing

化させていっても,Priority Queuing 導入前では約 4ms の遅延の変動があったが , その変動が約 1ms とほとんど 無く安定させることができた.

3.5 むすび
今回のパケットアセンブ リは , パケットの転送待ちによるキューイング時間を利用してアセンブリを行った. よってある程度の高い負荷がかからなければキューの中に同一の行き先のパケットがあることがなくなりアセンブリができない . アセンブリするエッジノード では ,大きな負荷がかかるとは考えにくい. 大きな負荷がかかるとした場合, アセンブリを行っていたのでは逆にエッジノード でのプロセッサ負荷が大きくなりそこがボトルネックになってしまう.
またパケットアセンブ リノード にパケットが 到着し たときに , そのノード にキューイング
されているすべてのパケットの中から一致しているアド レ スを検索する方式をとっていた.
ルータ内遅延をシミュレーションしなかったことからこれについての影響は結果として出てこなかったが , パケットアセンブ リを実装するためには効率のパケット検索法を用いること{ 21 {

3.5 むすび

Maximum Delay Time(msec)

32

28
TCP(PQwA)
UDP(PQwA)
TCP
UDP

24

20

16
1500

3000

4500

6000

7500

8000

The maximam size of the TCP Packet after Packet Assemblyand Priority Queuing with Assembly(Bytes)
図 3.8

PriorityQueuing 導入比較は重要である.
アセンブ リシミュレーションで転送したトラヒックについては , パケットサイズや転送タイ
ミング , 負荷が一定であった. パケットアセンブ リはトラヒックによる影響を大きく受けると考えられるので , これらの値を変化させた時のアセンブリされた回数やそれによる Delayについて考える必要がある.

{ 22 {

第4章

考察
4.1 パケット アセンブリの必要性
エラー率の違いは , MTU の異なるネットワークが存在する一つの理由である. パケット
アセンブリは, MTU の大きいネットワークで MTU よりも遥かに小さいパケットが流れそれによって起こる負荷を軽減するものである. 光ファ イバが普及して端末間でエラーがほとんど 起こらないことが保証されれば , すべてのネットワークで MTU が大きくなれば , MTU
サイズに着目したパケットアセンブリができなくなる.
しかし転送速度の面から考えると, 基幹ネットワークと比較して, 低速なアクセスネットワー
クで大きなパケットを投げることは , 短パケットに分割して通信しているリアルタイムアプ
リケーションに大きな影響を与えてし まう. 大容量化が進んでアクセスネットワークの転送が高速になっても, リアルタイムパケットの Delay は可能な限り小さいほうが良い.
転送速度の低いアクセスネットワークでは , 制限されたパケットサイズで転送して Delay を
防ぎ , 高速の基幹ネットワークでは , 大きなパケットを投げて負荷軽減を行う必要がある. この機能を実現できるのがパケットアセンブリである.
またモバイル端末による通信が発達することを考えると, 電波を使った通信ではエラー率が高くデータを確実に伝えることが保証できないので , MTU は小さく設定される. 無線から有線に変わるポ イントでパケットアセンブリを行う必要が出てくる.

{ 23 {

4.2 アセンブリするパケット

4.2

アセンブリするパケット

現在のトラヒックの種類で , TCP パケットの数は約 8 割を占めている. これらすべてのパケットをアセンブリすることになれば , ルータの負荷問題の大きな改善が可能である.
しかし近年のリアルタイムパケットを使った通信の発達により , アセンブ リが可能であるパケットの比率が低くなってくることも考えられる. リアルタイムパケットでもその度合いにより, アセンブリを行っていく方向で考えることも必要になる可能性がある.

4.3 パケット アセンブリ時にエッジルータにかかる負荷
エッジルータにパケットアセンブリの処理を持たせることは, そのルータに負荷がかかりそこをボトルネックになる危険がある. 特にアセンブ リパケットの分離時には , ルータ到着した一つのアセンブ リパケットの入力に対して, 分離後複数のパケットを出力するのでアセンブリした回数分だけ負荷がかかる.
これにはまず, エッジルータでの負荷は , トラヒックが集まってくるコアルータの負荷よりも小さいので , アセンブ リによってエッジルータが過負荷になることはないと考えることができる. 次にパケットアセンブ リのフォーマットを選ぶ際, できるだけ処理のステップ 数が少なくアセンブ リ, 分離のできる負荷のかからないフォーマットを選ぶことが考えられる. またアセンブリパケットの検索やパケット合成のアルゴ リズムについての最適化することがある. さらにハード ウエアでパケットアセンブリの処理を行うことにより高速化を図っていく.
エッジルータだけを高機能化すれば 良いので , 残りの基幹ネットワークルータにネットワー
ク構築時に大きな負担がかからなくてすむという考え方もある.

4.4

アセンブリパケット のLoss

パケットをアセンブリして長いパケットにすると , そのパケットにエラーが 起こったときに影響が大きくなってし まうということが考えられる.
これに対してはまずパケットアセンブ リを行う基幹ネットワークの光ファ イバでのエラー{ 24 {

4.5 基幹ネットワークルータの負荷が低い場合
レートはほとんど 無いといえる . またパケットアセンブ リを行わないときにルータの処理能力の不足でパケットが破棄されてロスが起こる場合でも, パケットアセンブリを行っていれば逆にロスが防げるという結果になる.

4.5

基幹ネット ワークルータの負荷が低い場合

ネットワークトラヒックは時間帯によって大きく変化する. 基幹ネットワークのトラヒッ
クの負荷が高いときには , パケットアセンブリを行うことによって次のホップから基幹ネットワークルータの負荷が軽減されることになり, エッジルータで多少の手間をかける意味が出てくる. しかし , トラヒックが少ないときにアセンブリを行うのは意味がない. エッジルー
タでアセンブリを行う時間や負荷が無駄になる. そこでエッジルータにトラヒックを監視させアセンブリを行うかを判断することが考えられる.
現在のデータ転送では , ネットワーク経路のど こで負荷がかかっているのかを特定し , それを避けることは難しい. トラヒックの混雑を制御用のパケットでルータ同士が通信し , その情報を交換することで負荷を回避することが 可能であるが , 制御信号を転送することでさらにネットワークに負荷がかかってし まう.
そこでエッジルータで delay や throughput を観測することにより, それらの値が悪化した
ときにパケットアセンブリを行うようにすればよい . これは負荷のかかっている場所を特定する必要がなく, ネットワークの負荷に対応できる. しかし Delay や Throughput の値は頻繁に変化するものであるため, 切り替えの閾値の調節が重要である.

{ 25 {

第5章

今後の課題
5.1

アセンブリのパケット フォーマット と負荷

今回のパケットアセンブリは ns のシミュレーション条件よりヘッダ削除なしでシミュレー
ションを行った. オーバヘッド の大きいパケットについてはヘッダも削除してアセンブリす
るほうがより効率の良い転送を行うことができる. しかし削除し すぎても, 削除や復元にかかる負荷が大きくなりすぎてエッジルータがボトルネックとなってし まう. 今後はパケット
フォーマットの違いによるヘッダ処理を考えたシミュレーションを行っていく.

5.2

マルチフローアセンブリ

今回はアドレスが完全に一致したパケット同士でアセンブリを行った. しかし 基幹ネット
ワークでのアセンブリを行う際に , アドレスが完全に一致していなくても行き先が同一のドメインであれば（ アド レ スの途中までが同じ ）基幹ネットワーク内のルートは同じである.
これを考えると別のフローのパケット同士でのアセンブリが可能となる.

TCP の Ack パケットはバースト的に流れてこないためアセンブリできなかったが , 小さい
パケットの中で Ack パケットはトラヒックのかなりの部分を占めるのでアセンブ リの効果が . マルチフローアセンブリを行えば TCP の Ack をアセンブリできると考えられる. Ack
パケットのオーバヘッド はパケットの約半分と大きいため IP ヘッダを削除する方式と組み合わせることができれば , 帯域利用効率の大幅な向上にもなる.

{ 26 {

5.3 パケット転送スケジューラによるパケットアセンブリ

5.3 パケット 転送スケジューラによるパケット アセンブリ
今回のアセンブリではエッジルータにある程度負荷がかからなければアセンブ リが行われなかった. エッジルータで負荷がかかっていなくても基幹ネットワーク内のルータで大きな負荷がかかっていることも考えられる. よってエッジルータで負荷がかからなくてもアセンブリできるようにキューで一定期間パケットを待機させてアセンブリを行う方法についての研究を進めていく. 図 5.1 にその構造を示す.
PacketArrivepriority

addressscheduler

図 5.1

5.4

scheduler によるアセンブ リ

ルータ内遅延を含めたシミュレーション

今回はヘッダ 処理にかかる負荷や遅延時間は , 他のフォワーディングやキューイングなどの遅延に比べて, 極めて小さい値であると考えてシミュレーションを行ってきた. しかしパケットアセンブ リはルータのヘッダ 処理の負荷軽減を目的としているため, ルータ内遅延を含めずにシミュレーションを行ってもパケットアセンブリによってど の程度 QoS が改善さ

{ 27 {

5.4 ルータ内遅延を含めたシミュレーション
れたかを値として出すことができなかった.
しかし 商用のシミュレータである OPNET ではルータ内遅延をシミュレーションしているので , 負荷を考えた測定ができればパケットアセンブリによる QoS の改善について調査することができると考えられる.

{ 28 {

謝辞
本研究を行うに際し , 貴重な御助言や多大なる御指導を頂いた高知工科大学工学部情報シ
ステム工学科の島村の神田和典

教授, ならびに通信・放送機構高知トラヒックリサーチセンタ

敏克氏に深く感謝いたします. また, 本研究室院生

中平

拓司氏ならびに本研究室学部生の皆様に感謝いたし ます. さらに在学中, 親切なる御助言を頂いた岩田授,

福本 昌弘 講師をはじめ諸先生方に心より感謝いたし ます.

{ 29 {

誠

助教

参考文献
[1] http://www.vbns.net:8080/presentations/papers/MCItrac.pdf[2] http://www.darpa.mil/ito/research/ngi/supernet.html[3] 神田, 島村; パケットサイズ制御によるルータでのデータ転送効率向上に関する考察, 信
学技報,SSE2000-114,IN2000-65,CS2000-45(2000)[4] 浦西, 神田, 島村; パケットアセンブリによるトラヒックへの影響に関する一考察, 電子
情報通信学会通信ソサイエティ大会,B-11-19, 一般講演 (2000)[5] 浦西, 神田, 島村; パケットアセンブリにおけるプライオリティキューイングを利用した
実時間トラヒックの性能向上, 電子情報通信学会総合大会, 一般講演 (投稿中)2001[6] GLOBECOM
IEEE
GlobalCommunications
Conference;
http://www.comsoc.org/confs/globecom/index.html(2001/2/5 現在)[7] ns;http://www.isi.edu/nsnam/ns/(2001/2/5 現在){ 30 {