IV. The NCP
We view the NCP as having five component programs, three associative tables, some queues and buffers, and a link assignment table. Each site will of course, vary this design to meet its needs, so our design is only illustrative.
The Component Programs
1. The Input Handler
This is an interrupt driven input routine. It initiates Imp-to-Host transmission into a resident buffer and wakes up the Input Interpreter when transmission is complete.
2. The Output Handler
This is an interrupt driven output routine. It initiates Host-to-Imp transmission out of a resident buffer and wakes up the Output Scheduler when transmission is complete.
3. The Input Interpreter
This program decides whether the input is a regular message intended for a user, a control message, an Imp-to-Host message, or an error. For each class of message, this program takes the appropriate action.
4. The Output Scheduler
Three classes of message are sent to the Imp
-
Host-to-Imp messages
-
Control messages
-
Regular messages
We believe that a priority should be imposed among these classes. The priority we suggest is the ordering above. The Output Scheduler selects the highest priority message and gives it to the Output Handler.
5. The System Call Interpreter
This program interprets requests from the user.
The two interesting components are the Input Interpreter and the System Call Interpreter. These are similar in that the Input Interpreter services foreign requests and the System Call Interpreter services local requests.
Associative Tables
We envision that the bulk of the NCP's data base is in three associative tables. By "associative", we mean that there is some lookup routine which is presented with a key and either returns successfully with a pointer to the corresponding entry, or fails if no entry corresponds to the key.
1. The Rendezvous Table
"Requests-for-connection" and other attributes of a connection are held in this table. This table is accessed by local socket, but other tables have pointers to existing entries.
The components of an entry are:
-
local socket (key)
-
foreign socket
-
link
-
queue of callers
-
text queue
-
connection state
-
flow state
-
pointer to attached port
An entry is created when a user executes either an Init or a Listen system call or when a <RFC> is received. Some fields are unused until the connection is established, e.g. the foreign socket is not known until a <RFC> arrives if the user did a Listen.
2. The Input Link Table
The Input Interpreter uses the foreign host and link as a key to get a pointer to the entry in the rendezvous table for the connection using the incoming link.
3. The Output Link Table
In order to interpret RFNM's, the Input Interpreter needs a table in the same form as the Input Link Table but using outgoing links.
Link Assignment Table
This is a very simple structure which keeps track of which links are in use for each host. One word per host probably suffices.
The following diagram is our conception of the Network Control Program. Boxes represent tables and Buffers, boxes with angled corners and a double bottom represent Queues, and jagged boxes represent component programs, the arrows represent data paths.
The abbreviated names have the following meanings.
-
ILT: Input Link Table
-
OLT: Output Link Table
-
LAT: Link Assignment Table
-
RT: Rendezvous Table
-
HIQ: Host to Imp Queue
-
OCCQ: Output Control Command Queue
-
ORMQ: Output Regular Message Queue
-
IHBuf: Buffer filled by the Input Handler from the IMP and emptied by the Input Interpreter
-
OHBuf: Buffer of outgoing messages filled from the Queues by the Output Scheduler and emptied by the Output Handler.
+---------+
| I M P |
+---------+
v ^
| |
+---------------------------|-----|------------------------------+
| | | |
| /\/\/\/\/\/\/\ | | /\/\/\/\/\/\/\ |
| \ / <--------+ +---< \ / |
| / Input \ / Output \ |
| \ Handler / \ Handler / <----+ |
| / \ >------+ / \ | |
| \/\/\/\/\/\/\/ | \/\/\/\/\/\/\/ ^ |
| v +-----+ |
| +-----+ | OH | |
| | IM | | Buf | |
| | Buf | +-----+ |
| +-----+ /\/\/\/\/\/\/\/\ ^ |
| /\/\/\/\/\/\/\/\ v +----> \ / | |
| \ / | | / Output \ >--+ |
| / \ <------+ ^ \ / |
| \ Input / /-----\ / Scheduler \ |
| / \ >-------->| HIQ | \ / |
| \ Interpreter / |_____| / \ |
| / \ >----+ \_____/ \/\/\/\/\/\/\/\/ |
| \/\/\/\/\/\/\/\/ | ^ v ^ |
| ^ ^ ^ \ | /-----\ | | | /-----\ |
| | \ \ \ | | O | | | | | O | |
| | \ \ \ +--->| C |>----+ | +---<| R | |
| v v v \ | C | | | M | |
| +---+ +---+ +---+ \ | Q | v | Q | |
| | | | | | | \ |_____| +---------+ |_____| |
| |ILT| |LAT| |OLT| \ \_____/ | | \_____/ |
| | | | | | | \ ^ | R T | ^ |
| +---+ +---+ +---+ +------|-------->| | | |
| v | +---------+ | |
| | ^ ^ | |
| | /\/\/\/\/\/\/\/\ | | |
| | \ / | | |
| +----------->/ System \<-------+ | |
| \ Call / | |
| / Interpreter \>--------------------+ |
| \ / |
| +-->/ \>--+ |
| | \/\/\/\/\/\/\/\/ | |
+------------------|----------------------|----------------------+
| |
+---< system calls <---+
Note: This RFC was put into machine readable form for entry into the online RFC archives by Donald and Jill Eastlake 1999.
[Editor's note: The original hand-drawn diagram represented Queues by cylinders and component programs by "squishy ameoba like things".]