ネットワークワーキンググループ
Request for Comments: 2395
分類: 情報提供
R. Friend
R. Monsour
Hi/fn, Inc.
1998 年 12 月

 

LZS を用いた IP ペイロード圧縮
(IP Payload Compression Using LZS)

このメモの位置付け 
このメモは、インターネットコミュニティに対して情報を提供するものである。
このメモは、何らインターネットの標準を規定するものではない。
このメモの配布に制限はない。
著作権表示
Copyright (C) The Internet Society (1998). All Rights Reserved.
要旨 
この文書は、LZS 圧縮アルゴリズムを基にした圧縮方式について記述したものである。
この文書では、IP ペイロード圧縮プロトコル [IPCOMP] への LZS アルゴリズムの適用について定義する。
[IPCOMP] では、インターネットプロトコルデータグラムのペイロードに対する無損失圧縮の適用について定義されている。
目次 
1. はじめに
1.1 一般
1.2 LZS 圧縮の背景
1.3 ライセンス
1.4 要求仕様
2. 圧縮処理
2.1 圧縮履歴
2.2 圧縮符号化フォーマット
2.3 パディング
3. 復元処理

4. IPComp アソシエーション(IPCA)パラメータ

4.1 ISAKMP トランスフォーム ID
4.2 ISAKMP セキュリティアソシエーション属性
4.3 手動設定
4.4 最小パケットサイズスレッショルド
4.5 圧縮可能性試験

5. セキュリティに関する考慮事項

6. 謝辞

7. 参考文献

8. 著者の連絡先

9. 付録:圧縮効率とデータグラムサイズの関係

10. 著作権表示全文

1. はじめに 
1.1 一般 
この文書では、IP データグラムペイロードに対する、無損失圧縮アルゴリズムである LZS 圧縮の適用について指定する。
この文書は、IP ペイロード圧縮プロトコル [IPCOMP] の仕様とともに使用される。
この文書では、IPComp プロトコルの全体を理解していると想定している。
1.2 LZS 圧縮の背景 
[LZ1] と同様に、スライディングウィンドウ圧縮の歴史から始めると、Hi/fn は、LZS として識別される新しい、強化された圧縮アルゴリズムを開発した。
LZS アルゴリズムは、様々なデータタイプに使用できる汎用的な無損失圧縮アルゴリズムである。
その符号化方式は、長さが 2 オクテット程度の文字に対する圧縮を提供する非常に効率的な方式である。

LZS アルゴリズムは、2,048 バイトのスライディングウィンドウを使用する。
圧縮では、冗長なデータのシーケンスは、そのシーケンスを表すトークンと置き換えられる。
復元では、オリジナルのシーケンスは、オリジナルのデータが正確に復元されるように、トークンと置き換えられる。
LZS は、しばしばビデオの圧縮で利用されるような、オリジナルのデータを正確に再生できない有損失圧縮とは異なる。

LZS 圧縮の詳細は、[ANSI94] で記述されている。

LZS アルゴリズムの効率は、オリジナルデータの冗長性に依存している。
[Calgary] Corpus のファイルセットにおける圧縮率の表を 7 章の付録として提供する。

1.3 ライセンス 
Hi/fn, Inc. は、LZS アルゴリズムの特許を保有している。
参照実装のライセンスは、IPPCP, IPSec, TLS, PPP アプリケーションでの利用に関しては、無料で利用可能である。
ソースおよびオブジェクトライセンスは、非差別ベースで利用可能である。
ハードウェアでの実装も利用可能である。
詳しくは、著者の連絡先に示した連絡先によって Hi/fn にコンタクトすること。
1.4 要求仕様 
この文書における "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", "OPTIONAL" というキーワードは、[RFC-2119] に記述されているように解釈されるものとする。
2. 圧縮処理 
2.1 圧縮履歴 
送信者は、各データグラムのペイロードの処理の前に、圧縮履歴をリセットしなければならない (MUST)
これにより、各データグラムのペイロードが他と独立して復元できることが保証され、これは、データグラムが順序通りに受信できなかった場合に必要となる。

送信者は、圧縮されたデータグラムを送信する度に、圧縮器をフラッシュしなければならない (MUST)
フラッシュとは、圧縮器に入力されるすべてのデータが出力に含まれること、つまり、さらに良い圧縮を実現する目的で、後に残されるデータは存在しないということを意味する。
フラッシュは、データグラムのデータが後のデータグラムに溢れ出るのを防ぐために必要である。

2.2 圧縮符号化フォーマット 
ペイロード圧縮アルゴリズムへの入力は、IP データグラムのペイロードである。
アルゴリズムの出力は、新しい(そして、できればより小さい)ペイロードとなる。
出力ペイロードには、圧縮形式か圧縮されていない形式のどちらかで、入力ペイロードのデータが含まれる。
入力および出力ペイロードは、それぞれ、整数バイトの長さである。

圧縮されていない形式が使用される場合は、出力ペイロードは入力ペイロードと同一であり、IPComp ヘッダーは省略される。
圧縮形式が使用される場合は、出力ペイロードの前に IPComp ヘッダが付与され、[ANSI94] に定義されているように符号化される(これを情報提供という目的で、ここで繰り返す)。

<Compressed Stream> := [<Compressed String>] <End Marker>
<Compressed String> := 0 <Raw Byte> | 1 <Compressed Bytes>
<Raw Byte> := <b><b><b><b><b><b><b><b>          (8-bit byte)
<Compressed Bytes> := <Offset> <Length>
<Offset> := 1 <b><b><b><b><b><b><b> |           (7-bit offset)
            0 <b><b><b><b><b><b><b><b><b><b><b> (11-bit offset)
<End Marker> := 110000000

<b> := 1 | 0

<Length> :=
00        = 2     1111 0110      = 14
01        = 3     1111 0111      = 15
10        = 4     1111 1000      = 16
1100      = 5     1111 1001      = 17
1101      = 6     1111 1010      = 18
1110      = 7     1111 1011      = 19
1111 0000 = 8     1111 1100      = 20
1111 0001 = 9     1111 1101      = 21
1111 0010 = 10    1111 1110      = 22
1111 0011 = 11    1111 1111 0000 = 23
1111 0100 = 12    1111 1111 0001 = 24
1111 0101 = 13     ...
2.3 パディング 
LZS を使用して圧縮されたデータグラムペイロードは、常に最後に圧縮したデータバイト(「終了マーカ」として知られている)で終了し、これはパディングを明確にするために使用される。
これにより、バイトと同様に、最後に続くビットをパディングと考えることが可能となる。

圧縮されたペイロードのサイズは、全体でオクテット単位でなければならない (MUST)

3. 復元処理 
受信したデータグラムが圧縮されている場合、受信者は、データグラムを処理する前に、圧縮履歴をリセットしなければならない (MUST)
これにより、各データグラムが他と独立して復元できることが保証され、これは、データグラムが順序通りに受信できなかった場合に必要となる。
圧縮履歴のリセットに続いて、受信者は、[ANSI94] の 3.2 章で指定された符号化に従ってペイロードデータフィールドを復元する。

受信したデータグラムが圧縮されていない場合、受信は、復元処理を実行する必要がなく、データグラムのペイロードデータフィールドは次のプロトコル層による処理が行える状態となる。

4. IPComp アソシエーション(IPCA)パラメータ 
[IPCOMP] で定義されているように、IPCA を確立するために、ISAKMP を使用して LZS 圧縮方式の使用を折衝しても良い (MAY)
4.1 ISAKMP トランスフォーム ID 
インターネット IP セキュリティ翻訳ドメイン [SECDOI] で指定されているように、LZS トランスフォーム ID としてIPCOMP_LZS が使用される。
この値は、ISAKMP プロトコルにおいて LZS 圧縮アルゴリズムを折衝するために使用される。
4.2 ISAKMP セキュリティアソシエーション属性 
ISAKMP において折衝される LZS 圧縮のために必要なその他のパラメータは存在しない。
4.3 手動設定 
CPI 値として IPCOMP_LZS が、手動で設定される IPComp 圧縮アソシエーションで使用される。
4.4 最小パケットサイズスレッショルド 
[IPCOMP] で述べられているように、小さいパケットはうまく圧縮できない可能性がある。
Calgary Corpus のデータセットに対して、LZS をアルゴリズムを用いて行われた非公式の試験では、より大きいデータを生成した平均ペイロードサイズは、約 90 バイトであった。
このため、実装は、90 バイトより小さいペイロードに対して圧縮を試みないほうが良い。
4.5 圧縮可能性試験 
[IPCOMP] で述べられているような、圧縮可能性試験に適用されるアルゴリズムは、LZS アルゴリズムには含まれていない。
5. セキュリティに関する考慮事項 
この文書では、[IPCOMP] と [Deutsch96] において既に述べられているセキュリティに関する考慮事項に対して、さらなる事項を追加しない。
6. 謝辞 
ここで述べられている LZS の詳細は、PPP LZS-DCP 圧縮プロトコル(LZS-DCP)[RFC-1967] における記述と同じである。

著者は、現在アクティブな議論を行い、IP に圧縮を統合するプロトコル仕様を作成している IPPCP ワーキンググループのメーリングリストの参加者に感謝する。

7. 参考文献 

[AH] Kent, S., and R., Atkinson, "IP Authentication Header", RFC 2402, November 1998.

[ANSI94] American National Standards Institute, Inc., "Data Compression Method for Information Systems," ANSI X3.241-1994, August 1994.

[Calgary] Text Compression Corpus, University of Calgary, available at ftp://ftp.cpsc.ucalgary.ca/pub/projects/text.compression.corpus.

[IPCOMP] Shacham, A., "IP Payload Compression Protocol (IPComp)", RFC 2393, December 1998.

[LZ1] Lempel, A., and Ziv, J., "A Universal Algorithm for Sequential Data Compression", IEEE Transactions On Information Theory, Vol. IT-23, No. 3, May 1977.

[RFC-1962] Rand, D., "The PPP Compression Control Protocol (CCP)", RFC 1962, June 1996.

[RFC-1967] Schneider, K., and R. Friend, "PPP LZS-DCP Compression Protocol (LZS-DCP)", RFC 1967, August 1996.

[RFC-2003] Perkins, C., "IP Encapsulation within IP", RFC 2003, October 1996.

[RFC-2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.

[SECDOI] Piper, D., "The Internet IP Security Domain of Interpretation for ISAKMP", RFC 2407, November 1998.

8. 著者の連絡先 
Robert Friend
Hi/fn Inc.
5973 Avenida Encinas
Suite 110
Carlsbad, CA 92008

EMail: rfriend@hifn.com
 

Robert Monsour
Hi/fn Inc.
2105 Hamilton Avenue
Suite 230
San Jose, CA 95125

EMail: rmonsour@hifn.com
 

翻訳者

東京都中央区新川1-21-2 茅場町タワー
株式会社 NTTデータ
技術開発本部
馬場 達也

EMail: babatt@nttdata.co.jp

9. 付録:圧縮効率とデータグラムサイズの関係 
次の表では、データグラムサイズを与えることにより得られた圧縮効率についてのいくつかの参考となるデータを提供する。
表中の各エントリは、指定したサイズのデータグラムを使用している試験ファイルに LZS を適用して得られた圧縮比を示している。

試験ファイルはカルガリー大学テキスト圧縮コーパス [Calgary] である。カルガリーコーパスは、全体で(すべてのファイルで)3.278MB のサイズを持つ 18 のファイルから構成されている。

Datagram size,|
bytes         |  64   128   256   512  1024  2048  4096  8192 16384
--------------|----------------------------------------------------
Compression   |1.18  1.28  1.43  1.58  1.74  1.91  2.04  2.11  2.14
ratio         |
10. 著作権表示全文 
Copyright (C) The Internet Society (1998). All Rights Reserved.

本文書とその翻訳は、複製および他に提供することができる。
また、この文書に論評や説明を加えたり、その実装を補助するものは、上記の著作権表示およびこの節を付加していれば、全体あるいは一部であっても一切の制約を課されることなく作成、複製、発表、配布できる。
ただし、この文書自体に対して、著作権表示やインターネットソサエティもしくは他のインターネット関連団体への参照を取り除くなどの変更を加えてはならない。
インターネット標準化過程で定義されている著作権のための手続きに従って、インターネット標準を開発するために必要な場合や、RFC を英語以外の言語に翻訳する必要がある場合はそのかぎりでない。

上記の制限は永続的なものであり、インターネットソサエティもしくはその継承者や譲渡者によって取り消されることはない。

本文書とここに含まれた情報は「無保証」で提供され、インターネットソサエティおよび IETF はすべての保証を明示的にも暗黙的にもおこなわない。
その中には、この情報がいかなる権利も侵害していないという保証や、商用利用および特定目的における適合性への保証が含まれる。