IEN: 168
Robert F. Gurwitz
Computer Systems Division
Bolt Beranek and Newman, Inc.
Cambridge, MA 02138
January, 1981
Table of Contents
1 Introduction.......................................... 1
2 Features of the Implementation........................ 1
2.1 Protocol Dependent Features......................... 1
2.1.1 Separation of Protocol Layers..................... 1
2.1.2 Protocol Functions................................ 2
2.2 Operation System Dependent Features................. 2
2.2.1 Kernel Resident Networking Software............... 2
2.2.2 User Interface.................................... 3
3 Design Goals.......................................... 4
4 Organization.......................................... 4
4.1 Control Flow........................................ 4
4.1.1 Local Network Interface........................... 5
4.1.2 Internet Protocol................................. 6
4.1.3 TCP Level......................................... 6
4.2 Buffering Strategy.................................. 8
4.3 Data Structures.................................... 10
5 References........................................... 12
The purpose of this report is to describe the implementation
of network software for the VAX-11/780 † running UNIX. ‡
This is being done as part of the VAX-UNIX Networking Support Project.
The overall purpose of this effort is
to provide the capability for the VAX to communicate with other computers
via packet-switching networks, such as the ARPANET.
Specifically, the project centers around an implementation of
the DoD standard host-host protocol,
the Transmission Control Protocol (TCP) [4].
TCP allows communication with ARPANET hosts,
as well as hosts on networks outside the ARPANET,
by its use of the DoD standard
Internet Protocol (IP) [3].
The implementation is designed for the VAX,
running VM/UNIX, the modified version of UNIX 32/V
developed at the University of California, Berkeley [1].
This version of UNIX includes virtual paging capabilities.
この報告書の目的は UNIX ‡ が動作する VAX-11/780 † のための
ネットワーク・ソフトウェアのインプリメンテーションについて解説することです。
これは VAX-UNIX ネットワーキング・サポート・プロジェクトの
一環として行われています。
この努力の最終的な目的は、
VAX が ARPANET のようなパケット交換ネットワークによって、
他のコンピューターと通信する能力を提供することです。
特に、プロジェクトは DoD 標準のホスト−ホスト・プロトコルの
インプリメンテーションである
Transmission Control Protocol (TCP) [4]
に集中します。
TCP は ARPANET の外側のネットワーク上のホストと同様に、
DoD 標準の
Internet Protocol (IP) [3]
を使用して、ARPANET ホストとのコミュニケーションを許します。
そのインプリメンテーションは、
カリフォルニア大学バークレー校[1]で開発されていたUNIX/V 32の修正版である、
VM/UNIX が動作する VAX のために設計されています。
UNIX のこのバージョンは仮想ページの能力を持っています。
† VAX is a trademark of Digital Equipment Corporation.
†VAXはデジタル・イクイップメントの商標です。
‡ UNIX is a trademark of Bell Laboratories.
(1) In this context, the terms application and user refer to any
software that is a user of lower level networking services. Thus,
programs such as FTP and TELNET can be considered applications
when viewed from the TCP level, and TCP itself may be viewed as
an application from the IP level.
‡UNIXはベル研究所の商標です。(1) この情況では、より低いレベル・ネットワーキング・サービスのユーザであるすべてのソフトウェアを指します(適用、ユーザという)。したがって、TCPレベルから見られた時、FTPとTELNETのようなプログラムは適用と考えることができます。また、TCPはそれ自身IPレベルから適用として見られるかもしれません。
In the following paragraphs,
we will discuss some features
and design goals of the implementation, and its organization.
次のパラグラフでは、私たちが、インプリメンテーションおよびその構成のいくつかの特徴および設計ゴールについて議論するでしょう。
The TCP software that we are developing for the VAX
incorporates several important features. First, the
implementation provides for separation of the various protocol
layers so that they can be accessed independently by various
applications. (1) Thus, there is a capability for access to the
TCP level, which will provide complete, reliable, multiplexed,
host-host communications connections. In addition, the IP level
is also accessible for applications other than TCP, which require
its internet addressing and data fragmentation/reassembly
services. Finally, the implementation also allows independent
access to the local network interface (in this case, to the
ARPANET, whose host interface is defined in BBN Report No. 1822
[2]) in a "raw" fashion, for software which wishes to
communicate with hosts on the local network and do its own higher
level protocol processing.
私たちがVAXのために開発しているTCPソフトウェアはいくつかの重要な特徴を組込みます。最初に、様々な適用がそれらに独立してアクセスすることができるように、そのインプリメンテーションは、様々なプロトコル層の分離に備えます。(1) したがって、TCPレベルへのアクセスに対する適応性(それは完全で信頼できて、多重化され、ホストホストコミュニケーション接続を提供するだろう)があります。さらに、IPレベルは、さらに、TCP以外の?K用(それらはそのインターネット・アドレシングおよびデータ分割/リアセンブリサービスを要求する)にはアクセス可能です。最後に、インプリメンテーションは、さらにローカル・ネットワーク上のホストと通信したく行い?ｽいソフトウェアのために、「生の」方法の中でローカル・ネットワーク・インターフェース(ARPANET(BBN報告書1822番の中でそのホスト・インターフェースは定義される)に、この場合[2])への独立したアクセスを許可します、その、自分自身のもの、より高いレベル・プロトコル処理。
Another feature of the implementation is to provide the full
functionality of each level of protocol (TCP and IP), as
described in their specifications [3,4]. Thus, on the TCP level,
features such as the flow control mechanism (windows),
precedence, and security levels will be supported. On the IP
level, datagram fragmentation and reassembly will be supported,
as well as IP option processing, gateway-host flow control
(source-quenching) and routing updates. However, it is
anticipated that some of these features (such as handling IP
gateway-host routing updates, and IP option processing) will be
implemented in later stages of development, after more basic
features (such as TCP flow control and IP
fragmentation/reassembly) are debugged.
それらの仕様書に記述されるように、インプリメンテーションの別の特徴はプロトコル(TCPとIP)の各レベルの十分な機能性を提供することです[3、4].したがって、TCPレベルで、フロー制御メカニズム(ウィンドウ)、先行およびセキュリティ・レベルのような特徴は支援されるでしょう。IPレベルで、データグラム分割およびリアセンブリは、IPオプション処理(ゲートウェイ・ホストフロー制御およびルーティング・アップデート(出所焼入れ))と同様に支援されるでしょう。しかしながら、より基礎的な特徴(TCPフロー制御およびIP分割/リアセンブリのような)がデバッグされた後、これらの特徴(IPゲートウェイ・ホスト・ルーティング・アップデートを扱い、IPオプション処理ように)のうちのいくつかが、開発の後の段階の中でインプリメントされるだろうことは予想されます。
There are several features of the implementation which are
operating system dependent. The most important of these is the
fact that the networking software is being implemented in the
UNIX kernel as a permanently resident system process, rather than
a swappable user level process.
オペレーティング・システムであるインプリメンテーションのいくつかの特徴があります、依存する最も重要なもの(これらに)は交換することができるユーザ・レベル・プロセスではなく、永久に駐在のシステムプロセスとしてUNIXカーネル中でネットワークのソフトウェアがインプリメントされているという事実です。
This organization has several implications which bear on
performance. The most obvious effect is that since the
networking software is always resident, it can more efficiently
respond to network and user initiated events, as it is always
available to service such events and need not be swapped in. In
addition, residence in the kernel removes the burden of the use
of potentially inefficient interprocess communication mechanisms,
such as pipes and ports, since simpler data structures, such as
globally available queues, can be used to transmit data between
the network and user processes. Kernel provided services, (e.g.,
timers and memory allocation) also become much easier and more
efficient to use.
この構成は、実行に影響するいくつかの意味合いを持ちます。最多の明白な結果は、ネットワークのソフトウェアが常に駐在である(以来)ということです。それはより効率的にネットワークに応答することができます。また、そのような出来事をサービスすることが常に利用可能なように、ユーザは出来事を始めて、交換される必要がありません。さらに、ネットワークとユーザープロセスの間のデータを送信するために全体的に利用可能なキューのようなより単純なデータ構造を使用することができるので、核の中の住宅は、笛とポートのような潜在的に非能率的な相互プロセスコミュニケーション・メカニズムの使用の負担を削除します。核はサービス(例えばタイマーおよびメモリ割付け)を提供しました、さらに使用することがはるかに容易でより効率的になります。
The large address space of the VAX makes this organization
practical and allows the avoidance of expedients like the NCP
split kernel/user process implementation, that have been
necessary in previous UNIX networking software on machines with
limited address space, like the PDP 11/70. It is hoped that the
kernel resident approach will contribute to the speed and
efficiency of this TCP.
VAXの大きなアドレス空間はこの構成を実際的にし、PDP 11/70のようにNCP分裂核/ユーザープロセスインプリメンテーション(それは、制限のあるアドレス空間を備えた機械上の前のUNIXネットワーキング・ソフトウェアにおいて必要だった)のように手段の回避を許可します。核居住者アプローチがこのTCPの速度および効率に寄与するだろうことが望まれます。
Use of the "traditional" UNIX file oriented user interface
is another operating system dependent feature of this
implementation. The user will access the network software by
means of standard system file I/O calls: open, close, read, and
write. This entails modification of certain of these calls to
accommodate the extra information needed to open and maintain a
connection. In addition, the communication of exceptional
conditions to the user (such as the foreign host going down) must
also be accommodated by extension of the standard system calls.
In the case of open, for example, use of the call's mode field
will be extended to accommodate a pointer to a parameter
structure. In the case of exceptional conditions, the return
code for reads and writes will be used to signal the presence of
exceptional conditions, much like an error. An additional status
call (ioctl) will be provided for the user to determine detailed
information about the nature of the condition, and the general
status of the connection.
(UNIX)ファイル指向の「従来の」ユーザ・インターフェースの使用はこのイ?塔vリメンテーションの別のオペレーティング・システム依存する特徴です。ユーザは、本位制度ファイルI/O呼び出しによってネットワーク・ソフトウェアにアクセスするでしょう:開いて、閉じて、読み書きしてください。これは、接続を開始し維持するために必要とされる余分な情報を提供するというこれらの要求にあることの修正を要します。さらに、本位制度呼び出しの拡張も、ユーザ(倒れている外国のホストのような)への例外的な条件のコミュニケーションもを提供しなければなりません。の場合には、例えば、開く、呼び出しのモード・フィールドに使用する、パラメーター構造にポインターを適応させるために拡張されるでしょう。例外的な条件の場合には、読み取りのためのリターン・コード、また書く、例外的な条件の存在を示すために非常にエラーのように使用されるでしょう。
補足ステータス呼び出し(ioctl)はユーザが条件の性質に関する詳細な情報および接続の一般的なステータスを決定するために提供されるでしょう。
In this way, the necessary additional information needed to
maintain network communications will be supported, while still
allowing the use of the functionality that the UNIX file
interface provides, such as the pipe mechanism.
このように、必要な付加的な情報は、パイプ・メカニズムのように、UNIXファイル・インターフェースが提供する機能性の使用をまだ認めている間、ネットワーク・コミュニケーションが支援されるだろうと主張する必要がありました。
In the initial versions, this interface will be the standard
UNIX blocking I/O mechanism. Thus, outstanding reads for data
which has not been accepted from the foreign host, and writes
which exceed the buffering resources of a connection will block.
It is expected that the await/capacity mechanism, currently
available for Version 6 systems, will be added to the VM/UNIX
kernel in the near future. These non-blocking I/O modifications
will be supported by the network software, relieving the blocking
restriction.
初期のバージョンでは、このインターフェースが標準のUNIXブロッキングI/Oメカニズムになるでしょう。したがって、接続のバッファーを用いた資源を超過する、外国のホストから受理されておらず書くデータのための顕著な読み取りは閉鎖するでしょう。近い将来にVM/UNIX核にawait/キャパシティーメカニズム(バージョン6システムに現在利用可能)が加えられるだろうことが期待されます。これらの非ブロッキングI/O修正はブロッキング制限を取り除いて、ネットワーク・ソフトウェアに支援されるでしょう。
Several design goals have been formulated for this
implementation. Among these goals are efficiency and low
operating system overhead, promoted by a kernel resident network
process, which allows for reduced process and interprocess
communication overhead.
いくつかの設計ゴールはこのインプリメンテーションのために公式化されました。これらのゴールの中には、効率および低いオペレーティング・システム・オーバーヘッドが、カーネル居住者ネットワーク・プロセス(それは縮小されたプロセスおよび相互プロセスコミュニケーション・オーバーヘッドを考慮に入れる)によって促進されてあります。
Another goal of the implementation is to reduce the amount
of extraneous data copying in handling network traffic. To
achieve this, a buffer data structure has been adopted which has
the following characteristics: intermediate size (128 bytes);
low overhead (10 bytes of control information per buffer); and
flexibility in data handling through the use of data offset and
length fields, which reduce the amount of data copying required
for operations like IP fragment reassembly and TCP sequence space
manipulations.
インプリメンテーションの別のゴールはネットワーク交通を扱う際に外来のデータ複写の量を減らすことです。これを達成するために、次の特性を持っているバッファー・データ構造は採用されました:中間のサイズ(128バイト);低いオーバーヘッド(1つのバッファー当たり制御情報の10バイト);またデータ・オフセットおよび長さフィールドの使用によるデータ取り扱いでの柔軟性、それはIPフラグメントリアセンブリおよびTCPシーケンス・スペース操作のようなオペレーションのために必要になったデータ複写の量を減らします。
The use of queueing between the various software levels has
been limited in the implementation by processing incoming network
data to the highest level possible as soon as possible. Thus, an
unfragmented message coming from the network is passed to the IP
and TCP levels, with queueing taking place at the device driver
only until the message has been fully read from the network.
Similarly, on the output side, data transmission is only
attempted when the software is reasonably certain that the data
will be accepted by the network.
様々なソフトウェア・レベル間にキューにする使用は、最も高いできるだけ早く可能なレベルへの入って来るネットワーク・データの処理により、インプリメンテーションで制限されています。したがって、ただメッセージがネットワークから完全に読まれるまで、ネットワークから来る破砕していないメッセージは、デバイス・ドライバのキューにするとる場所と共にIPとTCPのレベルに渡されます。同様に、出力側で、データがネットワークによって受理されるとソフトウェアが合理的に確信する場合、データ送信は単に試みられます。
Finally, it is planned that the inclusion of the network
software will entail relatively little modification of the basic
kernel code beyond that provided by Berkeley. The only
modifications to kernel code outside the network software will be
slight changes to the file I/O system calls to support the user
interface described above. In addition, an extension to the
virtual page map data structure in low core will be necessary to
support the memory allocation scheme, which makes use of the
kernel's page frame allocation mechanisms.
最後に、ネットワーク・ソフトウェアの包含?ｪバークレーによって提供されるその向こうの基礎的な核コードの比較的小さな修正を要するだろうことは計画されます。外部の核コードへのただ一つの修正、ネットワーク・ソフトウェアは上に記述されたユーザ・インターフェースを支援するファイルI/Oシステムコールへの少しの変更になるでしょう。さらに、低い芯の中の事実上のページ地図データ構造に対する拡張は、メモリ割付けスキーム(それは核のページ構造割付けメカニズムを利用する)を支援するのに必要になります。
The network software can be viewed as a kernel resident
system process, much like the scheduler and page daemon of
Berkeley VM/UNIX. This process is initiated as part of network
initialization. A diagram of its control and data flow is shown
in Figure 1.
ネットワーク・ソフトウェアは、非常にバークレーVM/UNIXのスケジューラおよびページ悪魔のように核居住者システムプロセスとして見ることができます。このプロセスはネットワーク初期化の一部として始められます。そのコントロールおよびデータ・フローの図形は図1の中で示されます。
| |-----| |-----| |-----| |-----| |
| |LOCAL| |-----| |LOCAL| | | | | |
| | NET | |input| | NET | | IP | | TCP | |
|->|INPUT|->|queue|->|INPUT|->|INPUT|->|INPUT| |
| | I/F | |-----| | | | | | | |
N | |-----|==========>|-----| |-----| |-----| |
| ^ (wakeup) ^ \ (timer) |
E | | | \ / | U
| (input) V \ / |
T | ( int ) |-----| \ / | S
| |frag | |-----| |-----| |
W | |queue| | |=>| |->| E
| |-----| | TCP | |USER | |
O | |-----||-----| |MACH | | I/F | | R
| |unack|| snd |<---->| |<=| |<-|
R | (outpt) |queue||queue| |-----| |-----| |
| ( int ) |-----||-----| / \ / |
K | | / \ / |
| V / \ / |
| |-----| |-----| |-----| |-----| \ / |
| |LOCAL| |-----| |LOCAL| | | | | |-----| |
| | NET | |outpt| | NET | | IP | | TCP | | rcv | |
|<-|OUTPT|<-|queue|<-|OUTPT|<-|OUTPT|<-|OUTPT| |queue| |
| | I/F | |-----| | | | | | | |-----| |
| |-----|<----------|-----| |-----| |-----| |
| |
| |
|<----------TCP PROCESS------------>|
| |
Figure 1 . Network Software Organization
Its main flow of control is an input loop which is activated (via
wakeup) by the network interface device driver when an incoming
message has been completely read from the network. (It can also
be awakened by TCP user or timer events, described below.) The
message is then taken from an input queue and dispatched on the
basis of local network format (e.g., 1822 leader link number).
ARPANET imp-host messages (RFNMs, incompletes, imp/host status)
are handled at this level. For other types of messages, the
local network level input handler calls higher level "message
handlers." The "standard message handler" is the IP input
routine. Handlers for other protocols at this level (such as
UNIX NCP) may be accommodated in either of two ways. First, a
"raw message" service is available which simply queues data on
specified links to/from the local network. By reading or writing
on a connection opened for this service, a user process may
handle its own higher level protocol communication.
Alternatively, for frequently used protocols, a new handler may
be defined in the kernel and called directly.
コントロールのその主要なフローは入って来るメッセージがネットワークから完全に読まれた場合、ネットワークインターフェイス・デバイス・ドライバによって活性化される(wakeupによって)入力されたループです。(さらに、TCPユーザかタイマー出来事はそれを下に記述されて起こすことができます。)その後、メッセージは入力キューから得られ、ローカル・ネットワーク・フォーマット(例えば1822のリーダー・リンク番号)に急送されます。ARPANET悪魔の子ホスト・メッセージ(RFNM、incompletes、悪魔の子/ホストステータス)は、このレベルに扱われます。他のタイプのメッセージについては、ローカル・ネットワーク・レベル入力取扱い人がより高いレベルを「メッセージ取扱い人」と呼びます。「標準のメッセージ取扱い人」はIP入力ルーチンです。このレベル(UNIX NCPのような)に他のプロトコル用の取扱い人は、2つの方法のどちらかに泊まるかもしれません。最初に、ローカル・ネットワークへの/指定されたリンク上のデータを単にキューにする「生のメッセージ」サービスは利用可能です。
読書か記述によってこのサービスのために開かれた接続においては、ユーザープロセスが扱うかもしれません、その、自分自身のもの、より高いレベル・プロトコル・コミュニケーション。二者択一で、頻繁に用いられているプロトコルについては、新しい取扱い人は核に定義され、直接呼ばれるかもしれません。
At the IP level, the fragment reassembly algorithm is
executed. Unfragmented messages with valid IP leaders are passed
to the higher level protocol handler in a manner similar to the
lower level dispatch, but on the basis of IP protocol number.
The "standard handler" is TCP. Another protocol handler
interprets IP gateway-host flow control and routing update
messages.
IPレベルでは、破片リアセンブリ・アルゴリズムが実行されます。有効なIPリーダーとの破砕していないメッセージは、より低いレベル急送に似ているやり方で、より高いレベル・プロトコル取扱い人に、だがIPプロトコル番号に基づいて渡されます。「標準の取扱い人」はTCPです。別のプロトコル取扱い人はIPゲートウェイ・ホスト・フロー制御およびルーティング・アップデート・メッセージを解釈します。
Fragmented messages are placed on a fragment reassembly
queue, where incoming fragments are separated by source and
destination address, protocol number, and IP identification
field. For each "connection" (as defined by these fields), a
linked list of fragments is maintained, tagged by fragment offset
start and end byte numbers. As fragments are received, the
proper list is found (or a new one is created), and the new
fragment is merged in by comparing start and end byte numbers
with those of fragments already on the list. Duplicate data is
thrown away. A timer is associated with this queue, and
incomplete messages which remain after timeout are dropped and
their storage is freed. Completed messages are passed to the
next level.
入って来る破片が、出所および終点アドレス、プロトコル番号およびIP識別フィールドによって分離される場合、破片にされたメッセージは破片リアセンブリ・キューに置かれます。各「接続」(これらのフィールドによって定義されたとともに)については、破片のリンクしたリストが、札が、破片オフセット・スタートおよび終了バイト番号によって付けられて維持されます。破片が受け取られるとともに、適切なリストは見つかります(あるいは、新しいものは作成されます)。また、新しい破片は、既にリスト上の破片のものとスタートと終了のバイト番号を比較することにより、合併されます。複製のデータが投げ捨てられます。タイマーはこのキューに関係しています。また、タイムアウトの後に残る不完全なメッセージは落とされます。また、それらの記憶装置が解放されます。完成したメッセージは、次のレベルに渡されます。
At the TCP level, incoming datagrams are processed via calls
to a "TCP machine." This is the TCP itself, which is organized
as a finite state machine whose states are roughly the various
states of the protocol as defined in [4], and whose inputs
include incoming data from the network, user
open/close/read/write requests, and timer events. Input from the
network is handled directly, passing through the above described
levels. User requests and timer events are handled through a
work queue.
TCPレベルでは、入って来るデータグラムが、「TCP機械」への呼び出しによって処理されます。これはTCP自体(それはその状態が荒く[4]の中で定義されるようなプロトコルの様々な状態で、その入力が、ネットワークからの入って来るデータを含んでいる有限状態機械として組織される)です、ユーザ/終了/読み取り/書き込みを開く、要求する、またタイマー出来事。ネットワークからの入力は上記の記述されたレベルを通り抜けて、直接扱われます。ユーザは要求します。また、タイマー出来事は仕事キューによって扱われます。
When a user process executes a network request via system
call, the relevant data (on a read or write) is copied from user
to kernel space (or vice versa), a work entry is enqueued, and
the network process is awakened. Similarly, when timers
associated with TCP (such as the retransmission timer) go off,
timer work requests are enqueued and the network input process is
awakened. Once awakened, it checks for the presence of completed
messages from the network interface and processes them. After
these inputs are processed, the TCP machine is called to handle
any outstanding requests on the work queue. The network process
then sleeps, waiting for more network input or work requests.
Thus, the TCP machine may be called directly with network input,
or awakened indirectly to check its work queue for user and timer
requests.
ユーザープロセスがシステムコールによってネットワーク・リクエストを実行する場合、適切なデータ(読み取りか書き込みの上の)は、ユーザから核ス?yース(あるいは逆に)にコピーされます。仕事エントリーはキューに入れられます。また、ネットワーク・プロセスが起こされます。同様に、TCP(再送信タイマーのような)に関連したタイマーが出る場合、タイマー仕事リクエストはキューに入れられます。また、ネットワーク入力プロセスが起こされます。以前起こされた、それはネットワークインターフェイスからの完成したメッセージの存在をチェックし、それらを処理します。これらの入力が処理された後、TCP機械は仕事キューに関するどんな顕著なリクエストも扱うために呼ばれます。その後、ネットワーク・プロセスはより多くのネットワーク入力あるいは仕事リクエストを待って眠ります。したがって、TCP機械は、ネットワーク入力で直接呼ばれるかもしれないか、あるいはユーザとタイマーのリクエストを待つその仕事列をチェックするために間接的に起きました。
After reset processing and sequence and acknowledgement
number validation, acceptable received data is sequenced and
placed on the receive queue. This sequencing process is similar
to the IP fragment reassembly algorithm described above. Data
placed on this queue is acknowledged to the foreign host.
Received data whose sequence numbers lie outside the current
receive window are not processed, but are placed on an
unacknowledged message queue. The advertised receive window is
determined on the basis of the remaining amount of buffering
allocated to the connection (see below). When buffering becomes
available, data on the unacknowledged message queue is then
processed and placed on the receive data queue.
リセットされた処理およびシーケンスおよび認識数確認の後に、受理可能な受信データは順番に並べられ、受理キューに置かれます。この配列プロセスは、上に記述されたIPフラグメントリアセンブリ・アルゴリズムに似ています。このキューに置かれたデータは、外国のホストに認められます。そのシーケンス番号が現在の受理ウィンドウの外部で位置する、受信データは処理されないが、不認可のメッセージキューに置かれます。広告された受理ウィンドウは、接続に分配されたバッファーする(残りの量の)方式で決定されます(以下を参照)。その後、バッファーが利用可能になる場合、不認可のメッセージキュー上のデータは処理され、受理データ・キューに置かれます。
On the output side, TCP requests for data transmission
result in calls to the IP level output routine. This routine
does fragmentation, if necessary, and makes calls on the local
network output routine. Outgoing messages are then placed on a
buffering queue, for transmission to the network interface by the
device driver. In data transmission, an attempt is made to
ensure that data moving from the highest level (TCP), will not be
sent unless there is reasonable certainty that the lower levels
will have the necessary resources to accept the message for
transmission to the network.
出力側で、データ送信のTCP要請は、IPレベル出力ルーチンへの呼び出しに帰着します。必要ならば、このルーチンは分割を行い、ローカル・ネットワーク出力ルーチン上の呼び出しを行います。その後、出発のメッセージは、デバイス・ドライバによるネットワークインターフェイスへの送信のためにバッファーを用いたキューに置かれます。データ送信では、最も高いレベル(TCP)から移動するそのデータを保証する試みがなされます、もしネットワークへの送信のためのメッセージを受理するために、より低いレベルが必要な資源を持つだろうという合理的な確実性がなければ、送られないでしょう。
All data to be sent is maintained on a single send queue,
where data is added on user writes, and removed when proper
acknowledgement is received. Whenever the TCP machine sends
data, a retransmission timer is set, and the sequence number of
the first data byte on the queue is saved. After initial
transmission the sequence number of the next data to send is
advanced beyond what was first sent. If the retransmission timer
goes off before that data is acknowledged, the sequence number of
the next data to send is backed up, and the contents of the send
buffer (for the length determined by the current send window) is
retransmitted, with the ACK and window fields set appropriately.
The retransmission timer is set with increasingly higher values
from 3 to 30 seconds, if the saved sequence number does not
advance.
送られるデータはすべて維持されます、1つの、単一、データがユーザに加えられる場合、キューを送る、書く、また適切な認識が受け取られるとき、削除されました。TCP機械がデータを送る場合は常に、再送信タイマーはセットされます。また、キュー上の第1のデータ・バイトのシーケンス番号が保存されます。初期の送信の後に、送る次のデータのシーケンス番号は、最初に送られたものを越えて進められます。そのデータが認められる前に、再送信タイマーが出る場合、送る次のデータのシーケンス番号はバックアップされます、そしてsendバッファー(流れによって決定された長さのための、ウィンドウを送る)の内容、適切にセットされたACKとウィンドウのフィールドと共に再?嵐Bされます。保存されたシーケンス番号が進まない場合、再送信タイマーは、3から30秒に対するますますより高い値で飾られます。
A persistence timer is also set when data is sent. This
allows communication to be maintained if the foreign process
advertises a zero length window. When the persistence timer goes
off, one byte of data is forced out of the TCP.
データが送られる場合、固執タイマーもセットされます。これは、外国のプロセスが0長さウィンドウを広告する場合コミュニケーションが維持されることを可能にします。固執タイマーが出る場合、データの1バイトはTCPから強要されます。
As mentioned earlier, all data is passed from the network to
the various protocol software layers in intermediate sized (128
byte) buffers. The buffers have two chain pointers, a data
offset, and a data length field (see Figure 2). As data is read
from the network or copied from the user, multiple buffers are
chained together. Protocol headers are also held in these
buffers. As messages are passed between the various software
levels, the offset is modified to point at the appropriate
header. The length field gives the end of data in a particular
buffer. This offset/length pair facilitates merging of messages
in IP fragment reassembly and TCP sequencing.
以前に言及されるように、データはすべて中間の分類された(128、バイト)バッファー中のネットワークから様々なプロトコル・ソフトウェア層まで渡されます。バッファーは2つのチェーン・ポインター、データ・オフセットおよびデータ長さフィールドを持っています(図2を参照)。データがネットワークから読まれるか、ユーザからコピーされるとともに、多数のバッファーはともにつながれます。プロトコル・ヘッダーもこれらのバッファーの中に保持されます。メッセージが様々なソフトウェア・レベル間で渡されるとともに、オフセットは適切なヘッダーを指すために修正されます。長さフィールドは、特別のバッファー中のデータの終了を与えます。このオフセット/長さペアはIPフラグメントリアセンブリおよびTCP配列でメッセージを融合することを促進します。
The allocation of these buffers is handled by the network
software. Buffers are obtained by "stealing" page frames from
the kernel's free memory map (CMAP). In VM/UNIX, these page
frames are 1024 bytes long, and thus have room for eight 128 byte
buffers. The advantage of using kernel paging memory as a source
of network buffers is that their allocation can be done totally
dynamically, with little effect on the operation of the overall
system. Buffers are allocated from a cache of free page frames,
maintained on a circular free list by the network memory
allocator. As the demand for buffers increases, new page frames
are stolen from the paging freelist and added to the network
buffer cache. Similarly, as the need for pages decrease, free
pages are returned to the system. To minimize fragmentation in
buffer allocation within the page frames, the free list is
sorted. When no more pages are available for allocation, data on
the IP reassembly and TCP unacknowledged data queues are dropped,
and their buffers are recycled.
これらのバッファーの割付けはネットワーク・ソフトウェアによって扱われます。バッファーは、核の無料のメモリ地図(CMAP)からページ・フレームを「盗む」ことにより得られます。VM/UNIXでは、これらのページ・フレームが長さ1024バイトで、8つの128バイトのバッファーの余地がこのようにあります。ネットワーク・バッファーの源としてメモリにページをつける核を使用するという利点は、全面的なシステムのオペレーションに対するわずかな影響を、それらの割付けが全くダイナミックにやめることができるということです。バッファーは、ネットワーク・メモリ・アロケーターによって循環的な免税品目表上で維持されて、自由なページ・フレームの貯蔵所から割り付けられます。バッファー増加の需要として、新しいページ・フレームはページをつける免税品目表から盗まれ、ネットワーク・バッファー貯蔵所を増しました。同様に、ページ減少の必要として、自由なページはシステムに返されます。ページ・フレーム内のバッファー割付けの中の分割を最小限にするために、免税品目表はソートされます。
これ以上のページが割付けに利用可能でない場合、IPリアセンブリおよびTCPの不認可のデータ・キュー上のデータは落とされます。また、それらのバッファーが再利用されます。
^ |------------------------| ^
| | -> NEXT BUFFER | |
10 |------------------------| |
BYTES | QUEUE LINK | |
| |-----------|------------| |
V | OFFSET | LENGTH | |
|-----------|------------| |
| | 128
| | BYTES
| | |
| D A T A | |
| | |
| | |
| | |
| | |
|------------------------| V
Figure 2 . Layout of a Network Buffer
The number of pages that can be stolen from the system is
limited to a moderate number (in practice 64-256, depending on
network utilization in a particular system). To enforce fairness
of network resource utilization between connections, the number
of buffers that can be dedicated to a particular connection at
any time is limited. This limit can be varied to some small
degree by the user when a connection is opened. Thus, a TELNET
user may open a connection with the minimum 1K bytes of send and
receive buffering; while an FTP user, anticipating larger
transfers, might desire up to 4K of buffering. The effect of
this connection buffering allocation is to place a limit on the
amount of data that the TCP may accept from the user for sending
before blocking, and the amount of input from the network that
the TCP may acknowledge. Note that in receiving, the network
software may allocate available buffers beyond the user's
connection limit for incoming data. However, this data is
considered volatile, and may be dropped when buffer demands go
higher. Incoming data is acknowledged by TCP only until the
user's connection buffer limit is exhausted. The advertised TCP
flow control window for a connection is set on the basis of the
remaining amount of this buffering.
システムから盗むことができるページの数は、適度な数(特別のシステムでのネットワーク利用に依存する実行64-256中の)に制限されています。接続間のネットワーク資源利用の公平を強化するために、特別の接続にいつでも専心的になりうるバッファーの数は制限されています。接続が開かれる場合、ユーザはこの限界をある小さな程度に変えることができます。したがって、TELNETユーザは、最小の1Kバイトとの接続を開始してもよい、バ?bファーして、送り受け取る;より大きなトランスファーを予想するFTPユーザが4Kまでのバッファーを望んでいるかもしれない一方。(割付け)バッファーを用いたこの接続の影響は、TCPがブロッキングの前に送るためにユーザから受理するかもしれないデータの量、およびTCPが認めるかもしれないネットワークからの入力の量に制限を設けることです。
受理では、入って来るデータにネットワーク・ソフトウェアがユーザの接続限界の向こうの利用可能なバッファーを分配するかもしれないことに注意してください。しかしながら、このデータは、揮発性であると考えられ、バッファー要求がより高くなる場??a場合落とされるかもしれません。ただユーザの接続バッファー限界が使い尽くされるまで、入って来るデータはTCPによって認められます。接続用の広告されたTCPフロー制御ウィンドウは、残りの量のバッファーに基づいてセットされます。
Thus, the network software must insure that it has enough
buffering for 1) its own internal use in processing data on the
IP and local network levels; 2) retaining acknowledged TCP data
that have not been copied to user space; and 3) retaining data
accepted by the TCP for transmission which have not yet been
acknowledged by the foreign host TCP. Other data, such as
unacknowledged TCP input from the network and fragments on the IP
reassembly queue are vulnerable to being dropped when demand for
more buffers makes necessary the recycling of buffers on these
queues. Since there is an absolute limit on the number of page
frames that may be stolen from the paging system, and hence the
total number of buffers available, there is a resultant limit on
the total number of simultaneous connections.
したがって、ネットワーク・ソフトウェアは、それが、IPとローカル・ネットワークのレベルでデータを処理する際に1)それ自身の内部使用用の十分にバッファーすることを持っていると保証するに違いありません;2)ユーザ・スペースにコピーされていない定評あるTCPデータを保持すること;そして3)、外国のホストTCPによってまだ認められていない送信用のTCPによって容認されたデータを保持すること。他のデータ、不認可のTCPのように、ネットワークからの入力およびIPリアセンブリ・キュー上の破片は、より多くのバッファーの需要がこれらのキュー上のバッファーの再利用を必要にする場合に、落とされることに弱い。ページをつけるシステムから盗まれるかもしれないページ・フレームの数に絶対的な制限があり、従って、ものの合計が利用可能なバッファーに番号を付けるので、同時の接続の総数に合成の制限があります。
Several data structures are required for stealing page
frames from the kernel and maintaining the buffer free list.
These include enough page table entries for mapping the maximum
number of page frames which can be stolen from the system, an
allocation map for allocating these page table entries, and the
free page list itself. For a 256 page maximum, this requires 2K
bytes of page tables, 1K bytes for page frame allocation mapping,
and another 1K bytes for the network freelist. The maximum page
parameter and others, including the minimum and maximum amount of
buffering that the user may specify are modifiable constants of
the implementation.
Along with the data structures needed to support the buffer
management system, there are several others used in the network
software (see Figure 3). The focus of activity is the user
connection block (UCB), and the TCP control block (TCB). The UCB
is allocated from a table on a per connection basis. It holds
non-protocol specific information to maintain a connection. This
includes a pointer the UNIX process structure of the opener of a
connection, † a pointer to the foreign host entry for the peer
process's host, a pointer to the protocol-specific connection
control block (for TCP, the TCB), pointers to the user's send and
receive data buffer chain, and miscellaneous flags and status
information. When a network connection is opened, an entry in
the user's open file table is allocated, which holds a pointer to
the UCB.
† For details on data structures specific to UNIX, see [5].
For TCP connections, a TCB is allocated. All TCBs are
chained together to facilitate buffer recycling. The TCB
contains a pointer to the corresponding UCB, a block of sequence
number variables and state flags used by the TCP finite state
machine, pointers to the various TCP data queues, and flags and
state variables. Protocols other than TCP would have their own
control blocks instead of the TCB. For the "raw" local network
and IP handlers, all necessary information is kept in the UCB.
Foreign
Host Table
|--------|
Network |------>|Host Adr|
Conn Table | |--------|
|--------| | | #RFNM |
|--->|->Proc |<--+--| |--------|
| |--------| | | | Status |
| |->Host |---| | |--------|
Per User | |--------| |
File Table | | ->TCB |---| | TCB
|--------| | |--------| | | |--------|
| Flags | | |->S Buf | |--+--->| ->next |
|--------| | |--------| | |--------|
| ->UCB |---| |->R Buf | |----| ->UCB |
|--------| |--------| |--------|
| Flags | | FSM |
| and | |Sequence|
| Status | | Vars |
|--------| |--------|
|->Snd Q |
|--------|
|->Rcv Q |
|--------|
|->UnackQ|
|--------|
| Flags |
| and |
| Status |
|--------|
Figure 3 . Network Data Structures
Finally, there is a foreign host table, where entries are
allocated for each host that is part of a connection. The entry
contains the foreign host's internet address, the number of
outstanding RFNM's for 1822 level host-imp communication, and the
status of the foreign host. Entries in this table are hashed on
the foreign host address.
[1] Babaoglu, O., W. Joy, and J. Porcar, "Design and
Implementation of the Berkeley Virtual Memory Extensions to
the UNIX Operating System," Computer Science Division, Dept.
of Electrical Engineering and Computer Science, University
of California, Berkeley, December, 1979.
[2] Bolt Beranek and Newman, "Specification for the
Interconnection of a Host and an IMP," Bolt Beranek and
Newman Inc., Report No. 1822, May 1978 (Revised).
[3] Postel, J. (ed.), "DoD Standard Internet Protocol," Defense
Advanced Research Projects Agency, Information Processing
Techniques Office, RFC 760, IEN 128, January, 1980.
[4] Postel, J. (ed.), "DoD Standard Transmission Control
Protocol," Defense Advanced Research Projects Agency,
Information Processing Techniques Office, RFC 761, IEN 129,
January, 1980.
[5] Thompson, K., "UNIX Implementation," The Bell System
Technical Journal, 57 (6), July-August, 1978, pp. 1931-1946.