RFC815 日本語訳

RFC:  815

RFC: 815

                   IP DATAGRAM REASSEMBLY ALGORITHMS

IPデータグラムREASSEMBLYアルゴリズム

                             David D. Clark
                  MIT Laboratory for Computer Science
               Computer Systems and Communications Group
                               July, 1982

デヴィッドD.クラークMITコンピュータサイエンス研究所コンピュータシステムズとコミュニケーションは1982年7月に分類されます。

     1.  Introduction

1. 序論

     One of the mechanisms of IP is fragmentation and reassembly.  Under

IPのメカニズムの1つは再アセンブリに断片化です。 下

certain  circumstances,  a  datagram  originally transmitted as a single

ある事情、元々シングルとして送られたデータグラム

unit will arrive at its final destination broken into several fragments.

ユニットは最終的な数個の断片が細かく分けられた目的地に到着するでしょう。

The IP layer at the receiving host must accumulate these fragments until

受信ホストにおけるIP層はこれらの断片を蓄積しなければなりません。

enough have arrived to completely reconstitute  the  original  datagram.

十分は、オリジナルのデータグラムを完全に再編成するために到着しました。

The  specification  document  for IP gives a complete description of the

IPのための仕様ドキュメントは完全な記述を与えます。

reassembly mechanism, and contains several examples.  It  also  provides

メカニズムを再アセンブリして、いくつかの例を含んでいます。 また、それは提供されます。

one  possible  algorithm  for  reassembly,  based  on  keeping  track of

1つの動向をおさえることに基づいた再アセンブリに、可能なアルゴリズム

arriving fragments in a vector of bits.    This  document  describes  an

到着はビットのベクトルで断片化します。 このドキュメントは説明します。

alternate approach which should prove more suitable in some machines.

いくつかのマシンでは、より適当であると判明するべきであるアプローチを交替してください。

     A  superficial  examination  of  the reassembly process may suggest

再アセンブリすることの過程の浅薄な試験は示されるかもしれません。

that it is rather complicated.  First, it is necessary to keep track  of

それはかなり複雑です。 まず最初に、動向をおさえるのが必要です。

all the fragments, which suggests a small bookkeeping job.  Second, when

すべての断片。(その断片は小さい簿記仕事を示します)。 2番目、いつ

a  new fragment arrives, it may combine with the existing fragments in a

新しい断片は届いて、それはaの既存の断片に結合するかもしれません。

number of different ways.  It may precisely fill the space  between  two

異なった方法の数。 それは正確に2の間のスペースをいっぱいにするかもしれません。

fragments,  or  it  may  overlap  with existing fragments, or completely

                                   2

断片、それは既存の断片、または完全に2に重なるかもしれません。

duplicate  existing  fragments,  or  partially  fill a space between two

既存の断片をコピーするか、または2の間のスペースを部分的にいっぱいにしてください。

fragments without abutting either of them.  Thus, it might seem that the

いずれか一方を隣接させることのない断片。 したがって、それはそれに見えるかもしれません。

reassembly  process  might  involve  designing  a   fairly   complicated

再アセンブリすることの過程は、公正に複雑にされたaを設計することを伴うかもしれません。

algorithm that tests for a number of different options.

多くの異なったオプションがないかどうかテストされるアルゴリズム。

     In  fact,  the  process  of  reassembly  is  extremely simple. This

事実上、再アセンブリの過程は非常に簡単です。 これ

document describes a way of dealing with reassembly  which  reduces  the

ドキュメントは減少する再アセンブリに対処する方法を述べます。

bookkeeping  problem  to  a minimum, which requires for storage only one

最小限への簿記問題。(それは、格納だけに1を必要とします)。

buffer equal in size to the final datagram being reassembled, which  can

サイズにおいて組み立て直される最終的なデータグラムと等しいバッファ。(そのバッファはそうすることができます)。

reassemble a datagram from any number of fragments arriving in any order

順不同に届くいろいろな断片からデータグラムを組み立て直してください。

with  any  possible  pattern  of  overlap  and duplication, and which is

何かオーバラップと複製の可能なパターンとどれがありますか。

appropriate for almost any sort of operating system.

ほとんどどんな種類のオペレーティングシステムにおいても、適切です。

     The reader should consult the IP specification document to be  sure

読者はIP仕様ドキュメントをいかにも参照するべきです。

that  he  is completely familiar with the general concept of reassembly,

彼は再アセンブリに関する一般概念に完全に詳しいです。

and the particular header fields and vocabulary  used  to  describe  the

説明するのにおいて中古の特定のヘッダーフィールドとボキャブラリー

process.

処理してください。

     2.  The Algorithm

2. アルゴリズム

     In  order  to  define this reassembly algorithm, it is necessary to

この再アセンブリアルゴリズムを定義するために、それが必要です。

define some terms.  A partially reassembled datagram consists of certain

いくつかの用語を定義してください。部分的に組み立て直されたデータグラムはある成ります。

sequences of octets that have already arrived, and certain  areas  still

まだ既に到着して、ある一定の領域を持っている八重奏の系列

to  come.    We will refer to these missing areas as "holes".  Each hole

来るために。 私たちは「穴」としてのこれらのなくなった領域について言及するつもりです。 各穴

can be characterized by two numbers, hole.first, the number of the first

穴2つの番号、最初に、1つの番目ものの数で特徴付けることができます。

octet in the hole, and hole.last, the number of the last  octet  in  the

中の最後の八重奏の穴、およびhole.last、数における八重奏

hole.    This pair of numbers we will call the "hole descriptor", and we

掘ってください。 私たちが「穴の記述子」に電話をするつもりである数のこの組、および私たち

will assume that all of the hole descriptors for a  particular  datagram

それが特定のデータグラムのための穴の記述子のすべてであると仮定するでしょう。

are gathered together in the "hole descriptor list".

                                   3

「穴の記述子リスト」では、集められます。 3

     The  general  form  of  the  algorithm  is  as follows.  When a new

アルゴリズムの一般的なフォームは以下の通りです。 a新しいです。

fragment of the datagram arrives, it will possibly fill in one  or  more

データグラムの断片は届いて、それはことによると1以上でいっぱいになるでしょう。

of  the existing holes.  We will examine each of the entries in the hole

既存の穴について。 私たちは穴でそれぞれのエントリーを調べるつもりです。

descriptor list to see whether the hole in  question  is  eliminated  by

問題の穴によって排泄されるか否かに関係なく、見る記述子リスト

this incoming fragment.  If so, we will delete that entry from the list.

この入って来る断片。 そうだとすれば、私たちはリストからそのエントリーを削除するつもりです。

Eventually, a fragment will arrive which eliminates every entry from the

結局、あらゆるエントリーを排除する断片は届くでしょう。

list.    At this point, the datagram has been completely reassembled and

記載してください。 そしてここにデータグラムが完全に組み立て直された。

can be passed to higher protocol levels for further processing.

さらなる処理のために、より高いプロトコルレベルに通ることができます。

     The algorithm will be described in two phases. In the  first  part,

アルゴリズムは二相で説明されるでしょう。 1番目では、離れてください。

we  will  show  the  sequence  of  steps  which  are executed when a new

私たちは、aであるときに、どれが実行されるかをステップの系列に新しく示すつもりです。

fragment arrives, in order to  determine  whether  or  not  any  of  the

断片が届く、決定、いくらか。

existing  holes  are  filled by the new fragment.  In the second part of

既存の穴は新しい断片によってふさがれます。 第二部

this description, we will  show  a  ridiculously  simple  algorithm  for

この記述であり、私たちはばかばかしく簡単なアルゴリズムを示すつもりです。

management of the hole descriptor list.

穴の記述子の管理は記載します。

     3.  Fragment Processing Algorithm

3. 断片処理アルゴリズム

     An arriving fragment can fill any of the existing holes in a number

受信フラグメントは数の既存の穴のいずれもふさぐことができます。

of ways.  Most simply, it can completely fill a hole.  Alternatively, it

方法について。 最も単に、それは完全に穴を塞ぐことができます。 あるいはまた、それ

may  leave some remaining space at either the beginning or the end of an

どちらかの何らかの残っているスペースを始めか終わりに出るかもしれません。

existing hole.  Or finally, it can lie in  the  middle  of  an  existing

既存の穴。 または、最終的に、それは存在の中央に横たわることができます。

hole,  breaking the hole in half and leaving a smaller hole at each end.

半分に穴を壊して、各端のときに、よりわずかなホールを出て、掘ってください。

Because of these possibilities, it might seem that  a  number  of  tests

これらの可能性のために、それはそのa番号のテストに見えるかもしれません。

must  be  made  when  a  new  fragment  arrives,  leading  to  a  rather

新しい断片が届くと作らなければならなくて、むしろaに通じます。

complicated algorithm.  In fact, if properly  expressed,  the  algorithm

複雑なアルゴリズム。 事実上、アルゴリズム適切に言い表されるなら

can compare each hole to the arriving fragment in only four tests.

                                   4

4つのテストだけで各穴を受信フラグメントにたとえることができます。 4

     We  start  the algorithm when the earliest fragment of the datagram

データグラムの最も前の断片であるときに、私たちはアルゴリズムを始めます。

arrives.  We begin by creating an empty data buffer area and putting one

到着します。 私たちは、人影のないデータ緩衝地帯を作成して、1を置くことによって、始めます。

entry in its  hole  descriptor  list,  the  entry  which  describes  the

穴の記述子リストにおけるエントリー、エントリー、どれ、説明

datagram  as  being completely missing.  In this case, hole.first equals

完全に外れているとしてのデータグラム。 穴この場合最初に、同輩

zero, and hole.last equals infinity. (Infinity is presumably implemented

ゼロ、およびhole.last同輩無限。 (おそらく、無限は実行されます。

by a very large integer, greater than 576, of the implementor's choice.)

非常に大きい整数に従って、576人以上の作成者が特選しています。)

The following eight steps are then used to insert each of  the  arriving

そして、以下の8ステップは、それぞれの到着を挿入するのに使用されます。

fragments  into  the  buffer  area  where the complete datagram is being

完全なデータグラムが存在である緩衝地帯への断片

built up.  The arriving fragment is  described  by  fragment.first,  the

確立されます。 受信フラグメントは断片1番目までに説明されます。

first  octet  of  the fragment, and fragment.last, the last octet of the

断片、およびfragment.last、最後の八重奏の最初の八重奏

fragment.

断片化してください。

   1. Select the next hole  descriptor  from  the  hole  descriptor
      list.  If there are no more entries, go to step eight.

1. 穴の記述子リストからの次の穴の記述子を選択してください。 それ以上のエントリーが全くなければ、ステップeightに行ってください。

   2. If fragment.first is greater than hole.last, go to step one.

2. 断片第1がhole.lastより大きいなら、ステップ1に行ってください。

   3. If fragment.last is less than hole.first, go to step one.

3. fragment.lastが. 1番目を掘るより少ないなら、ステップ1に行ってください。

         - (If  either  step  two  or  step three is true, then the
           newly arrived fragment does not overlap with the hole in
           any way, so we need pay no  further  attention  to  this
           hole.  We return to the beginning of the algorithm where
           we select the next hole for examination.)

- (ステップtwoかステップthreeのどちらかが本当であるなら新たに到着した断片が何らかの方法で穴に重ならないので、私たちはこれ以上この穴に注意を向ける必要はありません。 私たちは私たちが試験のために次の穴を選択するアルゴリズムの始まりまで戻ります。)

   4. Delete the current entry from the hole descriptor list.

4. 穴の記述子リストから現在のエントリーを削除してください。

         - (Since  neither  step  two  nor step three was true, the
           newly arrived fragment does interact with this  hole  in
           some  way.    Therefore,  the current descriptor will no
           longer be valid.  We will destroy it, and  in  the  next
           two  steps  we  will  determine  whether  or  not  it is
           necessary to create any new hole descriptors.)

- (ステップtwoもステップthreeも本当でなかったので、新たに到着した断片は何らかの方法でこの穴と対話します。 したがって、現在の記述子はもう有効にならないでしょう。 私たちはそれを破壊するつもりです、そして、次の2ステップでは、何か新しい穴の記述子を作成するのが必要であるかどうかと決心するつもりです。)

   5. If fragment.first is greater than hole.first, then  create  a
      new  hole  descriptor "new_hole" with new_hole.first equal to
      hole.first, and new_hole.last equal to  fragment.first  minus
      one.

                                   5

5. 断片第1が穴1番目より大きいなら、掘るために等しい状態で「新しい_穴」という新しい_穴1番目がある新しい穴の記述子を作成してください。1番目の、そして、新しい_hole.lastは断片1番目とマイナス1つと等しいです。 5

         - (If  the  test in step five is true, then the first part
           of the original hole is not filled by this fragment.  We
           create a new descriptor for this smaller hole.)

- (ステップfiveにおけるテストが本当であるなら、元の穴の最初の地域はこの断片によっていっぱいにされません。 私たちはこのよりわずかなホールのための新しい記述子を作成します。)

   6. If fragment.last is less  than  hole.last  and  fragment.more
      fragments   is  true,  then  create  a  new  hole  descriptor
      "new_hole", with new_hole.first equal to  fragment.last  plus
      one and new_hole.last equal to hole.last.

6. fragment.lastがhole.last以下であり、fragment.more断片が本当であるなら、「新しい_穴」という新しい_穴1番目がある新しい穴の記述子をfragment.lastと1つと等しく作成して、hole.lastと等しい状態で新しい_hole.lastを作成してください。

         - (This   test  is  the  mirror  of  step  five  with  one
           additional feature.  Initially, we did not know how long
           the reassembled datagram  would  be,  and  therefore  we
           created   a   hole   reaching  from  zero  to  infinity.
           Eventually, we will receive the  last  fragment  of  the
           datagram.    At  this  point, that hole descriptor which
           reaches from the last octet of the  buffer  to  infinity
           can  be discarded.  The fragment which contains the last
           fragment indicates this fact by a flag in  the  internet
           header called "more fragments".  The test of this bit in
           this  statement  prevents  us from creating a descriptor
           for the unneeded hole which describes the space from the
           end of the datagram to infinity.)

- (このテストは1つの付加的な機能があるステップfiveの鏡です。 初めは、私たちは、組み立て直されたデータグラムがどれくらい長いかを知りませんでした、そして、したがって、ゼロから無限で達する穴を作成しました。 結局、私たちはデータグラムの最後の断片を受け取るつもりです。 ここに、バッファの最後の八重奏から無限で達するその穴の記述子は捨てることができます。 最後の断片を含む断片は「より多くの断片」と呼ばれるインターネットヘッダーで旗でこの事実を示します。この声明における、このビットのテストによって、私たちはデータグラムの端からスペースについて無限で説明する不要な穴のための記述子を作成できません。)

   7. Go to step one.

7. ステップ1に行ってください。

   8. If the hole descriptor list is now empty, the datagram is now
      complete.  Pass it on to the higher level protocol  processor
      for further handling.  Otherwise, return.

8. 穴の記述子リストが現在空であるなら、データグラムは現在、完全です。 さらなる取り扱いのための、より高い平らなプロトコルプロセッサにそれを通過してください。 さもなければ、戻ってください。

     4.  Part Two:  Managing the Hole Descriptor List

4. パートTwo: 穴の記述子リストを管理します。

     The  main  complexity  in  the  eight  step  algorithm above is not

上の8ステップアルゴリズムにおける主な複雑さはそうではありません。

performing the arithmetical tests, but in adding  and  deleting  entries

算術テストを実行しますがエントリーを加えて、削除する際に

from  the  hole descriptor list.  One could imagine an implementation in

穴の記述子から、記載してください。 人は中で実現を想像できました。

which the storage management package was  many  times  more  complicated

保管管理がパッケージするどちらが多くの倍より複雑であったか。

than  the rest of the algorithm, since there is no specified upper limit

指定された上限が全くなくて以来のアルゴリズムの残りより

on the number of hole descriptors which will exist for a datagram during

意志がデータグラムのために存在する穴の記述子の数に関して

reassembly.   There  is  a  very  simple  way  to  deal  with  the  hole

再アセンブリ。 穴に対処する非常に簡単な方法があります。

descriptors, however.  Just put each hole descriptor in the first octets

                                   6

しかしながら、記述子、ただそれぞれの穴の記述子を最初の八重奏に入れてください、6

of  the  hole  itself.    Note  that by the definition of the reassembly

穴自体について。 再アセンブリの定義でそれに注意してください。

algorithm, the minimum size of  a  hole  is  eight  octets.    To  store

アルゴリズム、穴の最小規模は8つの八重奏です。 店に

hole.first  and  hole.last  will presumably require two octets each.  An

穴おそらく、1番目とhole.last willはそれぞれ2つの八重奏を必要とします。 1

additional two octets will be required to thread together the entries on

八重奏がエントリーに一緒に糸を通すのに必要であるために望んでいる追加2

the hole descriptor list.  This leaves at least two more octets to  deal

穴の記述子リスト。 これは取扱う少なくとももう2つの八重奏を残します。

with implementation idiosyncrasies.

実現特異性で。

     There  is  only  one obvious pitfall to this storage strategy.  One

この格納戦略への1つの明白な落とし穴しかありません。 1つ

must execute the eight step algorithm above before copying the data from

データをコピーする前の8ステップアルゴリズム上を実行しなければなりません。

the fragment into the reassembly buffer.  If one were to copy  the  data

再アセンブリバッファの中への断片。 1つがデータをコピーするつもりであったなら

first,  it might smash one or more hole descriptors.  Once the algorithm

まず最初に、それは1つ以上の穴の記述子をつぶすかもしれません。 かつてのアルゴリズム

above has been run, any hole descriptors which are about to  be  smashed

走行、つぶされようとしているどんな穴の記述子も上に行ったことがあります。

have already been rendered obsolete.

既に時代遅れであることへレンダリングされてください、そうした。

     5.  Loose Ends

5. 未処理事項

     Scattering  the  hole  descriptors throughout the reassembly buffer

再アセンブリバッファに穴の記述子を点在させます。

itself requires that they be threaded onto some sort  of  list  so  that

それ自体、それらがそのようにある種のリストに糸を通されるのが必要である、それ

they can be found.  This in turn implies that there must be a pointer to

それらを見つけることができます。 これは、ポインタがあるに違いないのを順番に含意します。

the head of the list.  In many cases, this pointer can be stored in some

リストのヘッド。 多くの場合、いくつかにこのポインタを収納できます。

sort  of  descriptor block which the implementation associates with each

実現がそれぞれに関連づける記述子ブロックの種類

reassembly buffer.  If  no  such  storage  is  available,  a  dirty  but

再アセンブリに、バッファリングします。 しかし、aが、そのようなどんな格納も有効でないことを汚すなら

effective  trick  is  to  store  the  head  of the list in a part of the

効果的なトリックはa部分のリストのヘッドを格納することになっています。

internet header in the reassembly buffer which is no longer needed.   An

もう必要でない再アセンブリバッファのインターネットヘッダー。 1

obvious location is the checksum field.

明白な位置はチェックサム分野です。

     When  the final fragment of the datagram arrives, the packet length

決勝であるときに、データグラムの断片は届いて、パケットは長さです。

field in the internet header should be filled in.

                                   7

インターネットヘッダーの分野は記入されるべきです。 7

     6.  Options

6. オプション

     The preceding description made one unacceptable simplification.  It

前の記述は1つの容認できない簡素化をしました。 それ

assumed that there were no internet options associated with the datagram

インターネットオプションが全くデータグラムに関連づけられなかったなら、そこでそれであると仮定します。

being  reassembled.    The  difficulty  with  options  is that until one

組み立て直されること。 オプションにおける困難は1時までそれです。

receives the first fragment of the datagram, one cannot tell how big the

受信、データグラムの最初の断片であり、人はどれくらい大きく言うことができないか。

internet header will be.  This is because,  while  certain  options  are

インターネットヘッダーはそうでしょう。 これがそうである、あるオプションはそうです。

copied  identically  into  every  fragment of a datagram, other options,

同様にデータグラム、別の選択肢のあらゆる断片にコピーされます。

such as "record route", are put in the first fragment only.  (The "first

最初の断片だけに入れられた状態で「ルートを記録します」。 (「最初に」

fragment"  is  the  fragment  containing  octet  zero  of  the  original

「断片」はオリジナルの八重奏ゼロを含む断片です。

datagram.)

データグラム。)

     Until  one  knows how big the internet header is, one does not know

人が、インターネットヘッダーがどれくらい大きいかを知るまで、人は知りません。

where to copy the data from each fragment into  the  reassembly  buffer.

どこに、再アセンブリバッファの中に各断片からのデータをコピーしますか?

If  the  earliest  fragment  to arrive happens to be the first fragment,

到着する最も前の断片がたまたま1日であるなら、断片化してください。

then this is no problem.  Otherwise, there are two  solutions.    First,

そして、これは問題ではありません。 さもなければ、2つの解決策があります。 最初に

one  can  leave  space in the reassembly buffer for the maximum possible

1つは可能な最大のための再アセンブリバッファで間隔を取ることができます。

internet header.  In fact, the  maximum  size  is  not  very  large,  64

インターネットヘッダー。 事実上、最大サイズはまさしくその多大、64ではありません。

octets.    Alternatively,  one can simply gamble that the first fragment

八重奏。 あるいはまた、1つは、1番目が断片化するのを単に賭けることができます。

will contain no options.  If, when the first fragment  finally  arrives,

オプションを全く含まないでしょう。 最初の断片が最終的に届くと

there  are  options,  one  can  then  shift  the  data  in  the buffer a

オプションがあって、次に、1つは、よりもみ皮製のaでデータを移行させることができます。

sufficient distance for allow for them.  The only peril in  copying  the

十分な距離、それらを考慮してください。 コピーにおける唯一の危険

data  is  that  one  will  trash  the  pointers  that  thread  the  hole

データは1つが穴に糸を通すポインタを破壊するということです。

descriptors together.  It is easy to see how to untrash the pointers.

一緒に記述子。 ポインタを非破壊する方法がわかるのは簡単です。

     The source and record route options have  the  interesting  feature

ソースと記録的なルートオプションには、おもしろい特徴があります。

that,  since  different  fragments  can follow different paths, they may

異なった断片が異なった経路に続くことができるので、それらはそうするかもしれません。

arrive with different return routes  recorded  in  different  fragments.

                                   8

異なった戻り経路が異なった断片に記録されている状態で、到着してください。 8

Normally,  this  is  more information than the receiving Internet module

通常、これは受信インターネット・モジュールより多くの情報です。

needs.  The specified procedure is to take the return route recorded  in

必要です。 指定された手順は記録された戻り経路を見て取ることです。

the first fragment and ignore the other versions.

1番目は、他のバージョンを断片化して、無視します。

     7.  The Complete Algorithm

7. 完全なアルゴリズム

     In addition to the algorithm described above there are two parts to

上で説明されたアルゴリズムに加えて、2つの部品があります。

the reassembly process.  First, when a fragment arrives, it is necessary

再アセンブリすることの過程。 断片が届くとき、まず最初に、それが必要です。

to  find  the  reassembly  buffer  associated  with that fragment.  This

再アセンブリバッファがそれに関連しているのがわかるには、断片化してください。 これ

requires some  mechanism  for  searching  all  the  existing  reassembly

再アセンブリにすべての存在を捜すために何らかのメカニズムを必要とします。

buffers.   The correct reassembly buffer is identified by an equality of

バッファ。 正しい再アセンブリバッファが平等によって特定されるのを

the following fields:  the  foreign  and  local  internet  address,  the

以下の分野: 外国の、そして、ローカルのインターネットアドレス

protocol ID, and the identification field.

ID、および識別分野について議定書の中で述べてください。

     The  final  part  of  the  algorithm  is  some  sort of timer based

アルゴリズムの最終部分はベースのある種のタイマです。

mechanism which decrements the time to  live  field  of  each  partially

それぞれのライブ分野に時間を部分的に減少させるメカニズム

reassembled  datagram,  so that incomplete datagrams which have outlived

長生きしていて、データグラムの、そして、したがって、そんなに不完全なそうしたデータグラムを組み立て直します。

their usefulness can be detected and deleted.  One can either  create  a

それらの有用性を検出して、削除できます。 1つはaを作成できます。

demon  which  comes alive once a second and decrements the field in each

1秒に一度本物に見えて、それぞれで分野を減少させる悪霊

datagram by one, or one can read the  clock  when  each  first  fragment

各1番目が断片化する1、または1のデータグラムは時計の時間を読むことができます。

arrives,  and  queue  some  sort  of  timer  call, using whatever system

到着して、ある種のタイマ呼び出しを列に並ばせて、どんなシステムも使用します。

mechanism is appropriate, to reap the datagram when its time has come.

メカニズムは、時間が来たとき、データグラムを刈り取るために適切です。

     An implementation of the complete algorithm  comprising  all  these

これらを包括する完全なアルゴリズムの実現

parts  was  constructed  in BCPL as a test.  The complete algorithm took

部品はテストとしてBCPLで組み立てられました。 完全なアルゴリズムは取りました。

less than one and one-half pages of listing, and generated approximately

記載されて、ほとんど発生することの1未満と2分の1ページ

400 nova machine instructions.  That portion of the  algorithm  actually

400 新星機械語命令。 それは実際にアルゴリズムを分配します。

involved with management of hole descriptors is about 20 lines of code.

                                   9

穴の記述子の管理にかかわっているのは、コードのおよそ20の行です。 9

     The   version  of  the  algorithm  described  here  is  actually  a

ここで説明されたアルゴリズムのバージョンは実際にaです。

simplification of the author's original version, thanks to an insightful

おかげの作者のオリジナルバージョンの簡素化、洞察に満ちた

observation by Elizabeth Martin at MIT.

MITのエリザベス・マーチンによる観測。