File: rfc11.txt

package info (click to toggle)
doc-rfc 20181229-2
  • links: PTS, VCS
  • area: non-free
  • in suites: buster
  • size: 570,944 kB
  • sloc: xml: 285,646; sh: 107; python: 90; perl: 42; makefile: 14
file content (1291 lines) | stat: -rw-r--r-- 46,971 bytes parent folder | download | duplicates (5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291






Network Working Group                                         G. Deloche
Request for Comments: 11                                            UCLA
                                                             August 1969


                   Implementation of the Host - Host
                      Software Procedures in GORDO

TABLE OF CONTENTS

   Chapter                                                        Page
   -------                                                        ----
   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . .   1
   2.  HOST - HOST Procedures . . . . . . . . . . . . . . . . . .   2
       2.1  Generalities  . . . . . . . . . . . . . . . . . . . .   2
       2.2  Connections and Links . . . . . . . . . . . . . . . .   2
            2.2.1  Definitions  . . . . . . . . . . . . . . . . .   2
            2.2.2  Connection types . . . . . . . . . . . . . . .   3
       2.3  Message Structure . . . . . . . . . . . . . . . . . .   5
       2.4  User Transactions . . . . . . . . . . . . . . . . . .   6
            2.4.1  List of transactions   . . . . . . . . . . . .   7
            2.4.2  HOST-HOST protocol and control messages  . . .   8
   3.  Implementation in GORDO  . . . . . . . . . . . . . . . . .  11
       3.1  Introduction to GORDO . . . . . . . . . . . . . . . .  11
            3.1.1  GORDO file system  . . . . . . . . . . . . . .  11
            3.1.2  GORDO process  . . . . . . . . . . . . . . . .  12
       3.2  Software Organization Overview  . . . . . . . . . . .  12
       3.3  Software Description  . . . . . . . . . . . . . . . .  13
            3.3.1  Data structures  . . . . . . . . . . . . . . .  13
                   3.3.1.1  Allocation tables . . . . . . . . . .  13
                   3.3.1.2  Buffer pages  . . . . . . . . . . . .  16
            3.3.2  Programs . . . . . . . . . . . . . . . . . . .  18
                   3.3.2.1  Handler . . . . . . . . . . . . . . .  18
                   3.3.2.2  Network . . . . . . . . . . . . . . .  19
       3.4  Software Procedures . . . . . . . . . . . . . . . . .  20
            3.4.1  Description of some typical sequences  . . . .  20

   Appendix A:  Flowcharts  . . . . . . . . . . . . . . . . . . .  23

   [[RFC Editor Note: [s] represents subscript s]]

1.  INTRODUCTION

   This technical note concentrates upon (1) the HOST-HOST procedures
   and (2) the implementation of the corresponding programs in GORDO
   (Operating System of the UCLA HOST).





Deloche                                                         [Page 1]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


   The first section is closely related to the BBN reports No. 1822 and
   1763[1] and specifies the HOST functions for exchanging messages.  It
   mostly deals with links and connections, message structure,
   transactions, and control messages.

   The second section is software oriented; it explains how the HOST
   functions are implemented and integrated into GORDO.  It is involved
   with data structures, programs, buffers, interrupt processing, etc.

   [1]  Parts of this section are taken from or referred to those
   reports.

2.  HOST-HOST PROCEDURES

2.1  Generalities

   The basic idea is that several users, at a given HOST, should
   simultaneously be able to utilize the network by time-sharing its
   physical facilities.

   This implies that within each HOST operating system, there must exist
   a special program that multiplexes outgoing messages from the users
   into the network and distributes incoming messages to the appropriate
   users.  We will call this special program the Network program.

2.2  Links and Connections  (See figure 1)

   2.2.1  Definitions

   It is convenient to consider the Network as a black box - a system
   whose behavior is known but whose mechanisms are not - for
   communicating messages between remote users rather than between pairs
   of HOST computers.

      (a)  Logical connections

         We define a logical connection as being a communication path
         linking two users at remote HOST[s].

         With that concept, a user (user program) in a HOST computer can
         (1) establish several logical connections to any remote HOST
         users, and (2) send or receive messages over those connections.

         Connections appear to users as full duplex.

         One of the purposes of the Network program is to serve the
         users in establishing, identifying, and maintaining these
         connections.



Deloche                                                         [Page 2]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


      (b)  Logical links

         Each logical connection is made of a pair of directional links:
         one for transmitting, the other for receiving.

         Those links, called logical links, are established by the
         Network programs and used by them.

         Note here that users are only interested in connections and are
         completely unaware of links.  Relationships between links and
         connections are carried out by the Network program.

         One of the advantages to define a connection as a pair of
         directional links is that a HOST will have the capability to
         loop himself through its IMP (it opens a connection to
         himself).  This feature can be useful for debugging purposes.

         Further on through this paper we will not use any more the
         attribute logical when referring either to links or
         connections.

   2.2.2  Connection types

   In order to reach a high flexibility in utilizing the Network there
   is advantage to classify the connections.

   Three types of connections are distinguished:  (a) control
   connection, (b) primary connection, and (c) auxiliary connection.

      (a)  Control connection

      This connection has a special status and is unique between a pair
      of HOST[s], e.g., if the Network includes x HOST[s], there are at
      most x control connections issued from one HOST.

      This connection is used by remote Network programs for passing
      control messages back and forth.  Control messages are basic to
      the establishment/deletion of standard connections.  (See 2.4.2)

      Note here that this control connection is the only connection
      which is not used by the HOST users.

      Let us describe now the standard connections.








Deloche                                                         [Page 3]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


      (b)  Primary connection

      These connections connect remote users.

      A primary connection:

            * Is unique between a pair of users and is the first to be
               established.

            * Is "teletype-like", i.e.:
               - ASCII characters are transmitted;
               - Echoes are generated by the remote HOST;
               - The receiving HOST[s] scan for break characters;
               - The transmission rate is slow (less than 20
               characters/sec).

            * Is mainly used for transmitting control commands, e.g.,
               for log-in into a remote HOST operating system.

      (c) Auxiliary connection

         These connections also connect remote users:

         An auxiliary connection:

            * Is opened in parallel to a primary connection and is not
               unique, i.e., several auxiliary connections can be
               established between users.

            * Is used for transmitting large volumes of data (file
               oriented).

            * Is used either for binary or character transmission.

             [Figure 1 - Links and Connections - see PDF file]
















Deloche                                                         [Page 4]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


2.3  Message Structure

   The HOST[s] communicate with each other via messages.  A message may
   vary in length up to 8095 bits (See down below the structure).
   Larger transmission must therefore be broken up by HOST users into a
   sequence of such messages.

      A message structure is identified on figure 2.

      It includes the following:

      (1) A leader (32 bits): Message type, Source/Destination HOST,
          link number.  (See BBN report No. 1822, pp 13, 17)

      (2) A marketing (32 bits when sent by the Sigma 7) for starting a
          message text on a word boundary.  (See BBN report No. 1822,
          pp. 17, 19)

      (3) The message text (Max: 8015 bits for the Sigma 7).  It mostly
          consists of user's text.  However, it may represent
          information for use by the Network programs.  (Control
          messages, see 2.4.2)

      (4) A checksum (16 bits).  Its purpose is to check, at the HOST
          level, the right transmission of a message.  (Changes in bit
          pattern or packet transposition; packets are defined in BBN
          report No. 1763, p. 13)  See down below for checksum
          calculation.

      (5) A padding for solving word length mismatch problems.  (See BBN
          report No. 1822, p. 17, 19.).  As far as software is
          concerned, padding is only involved at message reception for
          delineating message ends.  (At transmission the hardware takes
          care of the padding.)

   Remark:

      Checksum calculation:

      The last 16 bits of every message sent by a HOST is a checksum.
      This checksum is computed on the whole message including any
      marking, but excluding the 32 bit leader and any padding.  To
      compute the checksum:

      1.  Consider the message to be padded with zeroes to a length of
          8640 bits.

      2.  Section the 8640 bits into six 1440-bit segments, S0, S1...S5.



Deloche                                                         [Page 5]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


      3.  Section each 1440-bit segment S into 90 16-bit elements, T0,
          T1...T89.

      4.  Define a function [(+)], which takes two 16-bit elements as
          inputs and outputs a 16-bit element.  This function is defined
          by

          Tm [(+)] Tn = Tm [(+)] Tn, if Tm + Tn < 2[exp 16]

          Tm [(+)] Tn = Tm [(+)] Tn - 2[exp 16] + 1, if Tm + Tn >= 2[exp
          16]

      5.  For each 1440-bit segment Si compute Ci = K(Si), where

          K(S) = T0 [(+)] T1 + ..... T89

      6.  Computer C =
          C0[(+)]C1[(+)]C1[(+)]C2[(+)]C2[(+)]C2[(+)]C2....[(+)]C5

          (Notice that C1[(+)]C1 is just C1 rotated left one bit)

   The number C is the checksum.  The reason the Ci are rotated by i
   bits is to detect packet transposition.

    [Figure 2 - Format of a message sent by the Sigma 7 - see PDF file]

2.4  User Transactions

   From what has been discussed until here, the Network appears to a
   user as a bunch of connections.  Let us now explain how one can make
   use of these connections.

   First, we are going to describe the set of transactions that a user
   should be able to access for utilizing the connection facilities.

   Then, we are going to explain the role of the Network program for the
   execution of these transactions.  This will cover a HOST-HOST
   protocol in which control messages are exchanged between network
   programs.

   For explanation purposes those transactions are represented, at the
   user level, in the form of subroutine calls and parameters.  However,
   this does not imply at all that the implementation will closely
   follow this pattern.  (We are more involved here with the description
   than the implementation aspect, see chapter 3.)






Deloche                                                         [Page 6]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


   2.4.1  List of transactions

   Listed below are the descriptions of subroutines that could be at
   user's disposal for creating/breaking connections and
   transmitting/receiving data over them.  This set of subroutines can
   be considered as a kind of interface between the user level and the
   network program level.

   (a)  Open primary connection:

        OPENPRIM (CONNECTID, HOSTID, BUFFADDR, [OPT])
        CONNECTID:  Connection identification #
        HOSTID:  Remote HOST identification #
        BUFFADDR:  Buffer address for incoming messages.
        OPT:  Options such as message required after successful
              connection establishment, "full echo" (each message is
              transmitted back by the remote HOST for checking purpose),
              etc.

        Remark: [  ] means optional

   (b) Open auxiliary connection

        OPENAUX (CONNECTID, BUFFADDR, N, [OPT])
        CONNECTID:  Connection identification #, i.e., the
                    identification of the corresponding primary
                    connection (First a user has to open a primary
                    connection).
        BUFFADDR:  Same meaning as above.
        N:  Number of auxiliary connections that should be opened.
        OPT:  Same meaning as above.

   (c)  Transmission over connection

        TRANSM (CONNECTID, NO, BUFFADDR, N, [OPT])
        CONNECTID:  Connection identification #
        NO:  Connection #.  The primary connection is always referred to
             as being NO=0.  An auxiliary connection number corresponds
             to the order in which it has been established.  (The first
             auxiliary opened is referred to by NO=1, the second by
             NO=2, etc.)
        BUFFADDR:  Buffer address of the message to be transmitted.
        N:  Message size (byte number)
        OPT:  Options such as data type (characters vs. binary), trace
              bit, etc.






Deloche                                                         [Page 7]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


   (d)  Close connection

        CLOSE (CONNECTID, [N], [NO])
        CONNECTID: Connection identification #.
        N:  Number of connections to be closed.  If omitted all
            connections in use by the user, included the primary link,
            are closed.
        NO:  In case of N different from zero this number indicates the
             auxiliary connection # to be closed.

   2.4.2  HOST-HOST protocol and control messages

   The HOST-HOST protocol is carried out by the Network programs.  It
   mainly involves the execution of the previous transactions (initiated
   by users) and covers a HOST-HOST dialogue.

   This dialogue fulfills control procedures for opening or breaking
   connections and consists in exchanging control messages over the
   control link.  A control message has a structure identical to that of
   a regular message; it only differs from it by the text which is for
   use by Network programs instead of users.

   Let us insist that this control procedure is completely unrelated to
   transmission control procedures implemented in the IMP computers.  We
   are here at the HOST level (Network programs), and therefore control
   messages, that are going to be described below, are transmitted over
   the IMP[s] like regular messages.

   Consider now the previous transactions and describe for each of them
   which messages are exchanged over which links.  Each case will be
   explained by means of trivial examples.

   We suppose that a HOST(x) user wants to a remote HOST(y) program
   called URSA.

      (a)  Open a primary connection: (OPENPRIM)

      The HOST (x)'s Network program, waken up (See 3.3) by a use for
      opening a primary connection, starts a dialogue with the HOST
      (y)'s Network program.

        (i)  HOST(x) sends the following control message:

             HOST(x)       Control link                      HOST(y)
                         -------------------->
                           ENQ PRIM 0 1 2





Deloche                                                         [Page 8]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


             ENQ:     Enquiry for connection establishment (one ASCII
                      character)
             PRIM:    Connection type: primary (one special character)
             0 1 2:   Outgoing link #.  It is a decimal number (3 ASCII
                      characters), e.g., link #12.

                      This link # has been determined by the HOST(x)
                      Network program (See implementation: 3.3)

        (ii) HOST(y) acknowledges by sending back the following control
                      message:

             HOST(x)        Control link                     HOST(y)
                         <------------------------
                          ACK ENQ PRIM 0 1 2 0 1 5

             ACK:     Positive acknowledgment (one ASCII character)
             ENQ PRIM 0 1 2:  Same meaning as above.  This part of the
                      message is returned for checking purposes.
             0 1 5:   Incoming link #.  It follows the same pattern as
                      the outgoing link #.  This link # has been
                      determined by the HOST(y) Network program.

                      Now the connection is established; it will use
                      links #12 and 15 for exchanging user messages.
                      The connection is said to be in a pre-log-in
                      state, i.e., the remote HOST(y) expects its
                      standard log-in procedures.

      (b)  Transmission over primary connection: (TRANSM)

         By means of TRANSM subroutines referring to the primary
         connection, the HOST(x) user is able to sign-in into the
         HOST(y) operating system and then to call for the URSA program
         (HOST(y) user program).

         The Network programs at both ends will use the link #12 and #15
         for passing along messages.  These messages are standard
         messages whose contents serve for log in sequence.

         A trivial example could be:

             HOST(x)     Prim. Link #12                       HOST(y)
                         ---------------------------->
                         ! S I G N - I N : X X






Deloche                                                         [Page 9]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


             HOST(x)     Prim. Link #15                       HOST(y)
                         <--------------------------
                         ! ! R E A D Y

             HOST(x)     Prim. Link #12                       HOST(y)
                         ---------------------------->
                           ! U R S A

      (c)  Open an auxiliary connection: (OPENAUXI)

         In a very similar manner as (a) an auxiliary connection is
         established between HOST(x) and HOST(y).  For so doing control
         messages are exchanged over the control link.

             HOST(x)           Control link                  HOST(y)
                         ------------------------------>
                               ENQ AUX 0 2 5

             HOST(x)           Control link                  HOST(y)
                         <--------------------------------
                             ACK ENQ AUX 0 2 5 0 2 1

         Now the auxiliary connection is established, it will use links
         #25 and 21 for exchanging standard messages.

      (d)  Transmission over auxiliary connection: (TRANSM)

         By means of TRANSM subroutines referring to the auxiliary
         connection, the users at both ends can exchange data:

             HOST(x)        Aux. Link #25                    HOST(y)
                         -------------------------------->
                               X X ..... X X

             HOST(x)         Aux. Link #21                   HOST(y)
                         <--------------------------------
                             X ......... X

         etc.......

      (e)  Close connections: (CLOSE)

         This is carried out in a similar manner as (a).  The user calls
         a CLOSE subroutine and then the Network programs at both ends
         exchange control messages.






Deloche                                                        [Page 10]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


             HOST(x)           Control Link                  HOST(y)
                         ----------------------------->
                               EOT 0 0 1 0 1 2

             EOT:     End of transmission (one ASCII character)
             0 0 1 :  No. of connections to be closed (3 decimal ASCII
                       characters)
             0 1 2 :  Outgoing link # to be closed.

             Then HOST(y) acknowledges back as in (a).

             HOST(x)           Control Link                  HOST(y)
                         <-----------------------------
                            ACK EOT 0 0 1 0 1 2 0 1 5

         Remark 1 - In (a), (c), and (e) HOST(y) may answer back a
         message including a negative acknowledgement character NAK
         instead of ACK.  This for many various reasons such as: wrong
         sequence, connection already opened, and so forth.  The message
         could be NAK IND, where IND is an alphanumerical character
         indicating, in a coded form, why the previous block has been
         refused.  Upon receiving back such acknowledgments HOST(x) will
         repeat its message until HOST(y) accepts it.  An emergency
         procedure will take place if too many successive "NAK messages"
         occur.

         Remark 2 - On each of the above illustrations (arrows) only the
         message text is represented.  In fact, complete messages (with
         leader, marking, padding...) are exchanged over these links.


3.  IMPLEMENTATION IN GORDO

3.1  Introduction to GORDO

   GORDO is a time-sharing system implemented on SDS Sigma 7.  We
   outline below some of the characteristics relevant to our paper.

   3.1.1  GORDO file system

   The file system is page oriented.  It is composed of files and
   directories.  A file consists of a heading and a number of pages
   which compose the body of the file.  A directory consists of a number
   of entries that point to either files or other directories.







Deloche                                                        [Page 11]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


   3.1.2  GORDO process

   *  A process is a program (procedures and data) plus its logical
      environment.  In other words a process is a program which is known
      and controlled by the GORDO scheduler.

   *  A user (a job) may have several processes as different as
      compiler, loader, editor, application program, etc.  A process is
      created through a system call (FORK).

   *  The space a process can refer to is the Virtual Space of 128k word
      length.  A part (8k) of it is reserved for the operating system,
      the other part (120k) is directly accessed by the user.  This
      later may fill or modify its part of the virtual space upon
      'coupling'.  (See below: service calls) pages taken from different
      files.  Figure 3 illustrates this coupling.

   *  A process can request for services by means of system calls.  The
      system calls relevant to our paper are:

         WAKE    for awaking (set active) a sleeping process
         SLEEP   for putting asleep another process (or itself)
         COUPLE  for coupling a page from the file space to the virtual
                 space.

   *  A process ordinarily runs in slave mode.  However if it is set up
      as an I/O process it can access privileged instructions.

   *  Processes can share data through files attached to "mail box"
      directories.

   Remark:  Through this note the words process and program are used
   inter-changeably.

          [Figure 3 - Virtual Space and Coupling - see PDF file]

3.2  Software Organization Overview

   Figure 4 illustrates the overall organization.

   The system is based upon two main programs: the "Network" and the
   "Handler".

   The Handler is an I/O interrupt routine closely related to the IMP-
   HOST hardware interface.  It serves the Network process in
   transmitting an receiving network messages.

   The Network process carries out most of the work.



Deloche                                                        [Page 12]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


   Its main function is to satisfy the users' requests for opening/
   closing connections and transmitting/receiving network messages.  For
   so doing,

   *  it establishes, identifies, and breaks the links upon using the
      allocation tables (HOST, CONNECT, INPUT LINK; see 3.3.1.1)

   *  it is aware of the presence of new users upon exploring the
      Network mail box directory;

   *  it communicates with active users by means of shared pages through
      which messages and requests are exchanged (connection shared
      pages);


   *  it formats incoming/outgoing messages in a working page.  This
      working page has an extension (emergency ring);

   *  it communicates with the Handler by means of a shared page (I/O
      communication page) which contains the I/O communication buffers.

        [Figure 4 - Software organization overview - see PDF file]

3.3  Software Description

3.3.1  Data Structures

   3.3.1.1  Allocation tables: HOST, CONNECT, INPUT LINK

      The Network program establishes, identifies, and breaks links and
      connections upon using 3 tables:

      A table sorted by remote HOST #.

      A table sorted by connection #.

      A table sorted by input link #.

        (a) HOST table (see figure 5)

            It is a bit table indicating the free outgoing links.  It
            has the following characteristics:

            *  Location: Disc resident

            *  Coupling: Coupled to the Network process virtual space.

            *  Size:  As many slots as remote HOST[s].



Deloche                                                        [Page 13]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


            *  Slot structure: As many bits as possible outgoing links
                               to a remote HOST, i.e., 256.

            *  Access: Indexing.  Each slot is accessed through a remote
                       HOST #.

            *  Specific feature:  Throughout the whole table no more
                                  than 64 bits can be turned on.  This
                                  figure corresponds to the maximum
                                  number of outgoing links that can be
                                  activated at one time (No matter what
                                  is the number of remote HOST[s]).

        (b)  CONNECT table

            This table keeps track of all the connections' environment.

            It has the following characteristics:

            *  Location:  Disc resident

            *  Coupling:  Couples to the Network process virtual space

            *  Size:  As many slots as connections in use.

            *  Slot structure:  See figure 6.  Each slot is 2 word
                                length

            *  Access:  Indexing.  Each slot is accessed through a
                        connection #.  See 3.4 the way it is handled.

            *  Specific feature 1:  The slot structure corresponding to
                                    a primary connection is not
                                    identical to that of an auxiliary
                                    connection (See figure 7).  This
                                    because user identifications and
                                    requests are done through primary
                                    shared pages.

            *  Specific feature 2:  This table is handled in parallel
                                    with the connection pages (See 3.3.2
                                    (b))









Deloche                                                        [Page 14]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


            *  Specific feature 3:  This table is mainly used for
                                    transmitting messages.  (For each
                                    connection it contains the outgoing
                                    link # and remote HOST #, i.e., all
                                    the information required for
                                    transmitting a message.)

        (c)  INPUT LINK table

            This table keeps track of all the incoming (input) links and
            so is closely related to the CONNECT table.

                  [Figure 5 - HOST table - see PDF file]

         [Figure 6 - CONNECT table: Slot structure - see PDF file]

       [Figure 7 - INSERT LINK table: Slot structure - see PDF file]

   It has the following characteristics:

   *  Location:  Disc resident.

   *  Coupling:  Coupled to the Network process virtual space.

            *  Size:  As many slots as incoming links, i.e., as
                      connections

            *  Slot structure:  See figure 7.  Each slot is 1 word
                                length

            *  Access:  Hashing.  The hashed key value is mainly based
                        upon the incoming link # and the remote HOST #.

            *  Specific feature 1:  This table is also used for
                                    momentarily memorizing the
                                    connection number while establishing
                                    the next connection.  See 3.4 the
                                    way it is handled.

            *  Specific feature 2:  This table is primarily used upon
                                    receiving messages.  (For each
                                    incoming link it contains the
                                    corresponding connection #, i.e.,
                                    indirectly the user identification
                                    to which the message should be
                                    passed along)





Deloche                                                        [Page 15]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


      3.3.1.2  Buffer pages

      All the pages that are now to be described contain two buffers
      (input and output).  These buffers are used for either passing
      along or processing messages.

      The size of each of these buffers should at least be equal to that
      of a message, i.e., 8095 bits.  We have chosen a buffer size of
      253 words (8096 bits) so that both of the buffers are included
      within one page (512 words).  The 6 remaining words of the page
      are generally used for control.

      A typical buffer page structure is identified on figure 8.

      (a)  I/O communication page

         See figure 9.

         This I/O communication page is used as an interface between the
         Handler and the Network program.

         In the buffers of this page the messages are assembled (input)
         or de-assembled (output) word by word by the Handler, e.g., a
         "ready to go" message, sorted by the Network program in the
         output buffer, is shipped out word by word by the Handler.

         Main characteristics:

         *  Location:  Resident in core: Locked page
         *  Coupling:  Coupled to the Network process virtual space
         *  Content: * Input buffer (253 words) for incoming messages
                       Output buffer (253 words) for outgoing messages
                     * Input control zone (6 half words)
                     * Output control zone (6 half words)
         *  Structure:  See figure 9.
         *  Specific feature: * The input buffer is filled by the
                                Handler (read from hardware) and emptied
                                by the Network program
                              * Vice versa for the output buffer

      (b)  Connection shared pages (User-Network shared zone)

         General features:

         *  There are as many shared pages as connections.

         *  These pages shared between the network and the user
            processes constitute a communication zone for (1) passing



Deloche                                                        [Page 16]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


            the messages back and forth, and (2) exchanging control
            information, e.g., a request for establishing new
            connections.

         Main characteristics:

         *  Location:  Disc resident
         *  Coupling:  Coupled to both a user process virtual space and
            the
                          network process virtual space.
         *  Content: - Input buffer (253 words) for incoming messages
                      - Output buffer (253 words) for outgoing messages
                      - Input control zone (6 half words)
                      - Output control zone (6 half words)
         *  Structure:  See figure 10.
         *  Specific feature 1: - The input buffer is filled by the
                                  Network and emptied by the user.
                                - Vice versa for the output buffer.
         *  Specific feature 2:  The control zone corresponding to a
                                  primary connection shared page differs
                                  from that of an auxiliary connection.
                                  This because it is via a "primary
                                  connection control zone" that
                                  auxiliary connection establishment
                                  requests are transmitted to the
                                  Network process.

      (c)  Working page

         General feature:

         *  This page allows the Network and the Handler programs to
         work independently on different messages and so contributes to
         an overlapping.  For instance, when the Handler is busy
         transmitting a message to the hardware, the Network program can
         format (leader, marking, etc.) the reset message to be shipped
         out, so that it can reinitiate the Handler as soon as it is
         free.

         Main characteristics:

         *  Location:  Disc resident
         *  Coupling:  Coupled to the Network process virtual space
         *  Content:  - Input buffer (253 words) for incoming messages
                      - Output buffer (253 words) for outgoing messages






Deloche                                                        [Page 17]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


         Remark:

         During reception it may happen that a user program is not ready
         to accept a new message.  In that case, to avoid clogging up
         the system, the Network stores momentarily the incoming message
         in one of the buffer of the emergency ring.  (If this ring is
         full a help routine will be invoked.)

         During emission all operations are synchronized with the
         RFNM[s], therefore such procedures need not be provided.  (The
         Network program allows a user to re-emit only when having
         received the RFNM of the previous transmitted message.)

             [Figure 8 - Typical buffer page - see PDF file]

       [Figure 9 - I/O Communication page structure - see PDF file]

       [Figure 10 - Connection shared page structure - see PDF file]

3.3.2  Programs

   3.3.2.1  Handler program

      General features:

      It is an I/O interrupt routine which drives the IMP/HOST hardware
      interface in order to transmit or receive messages.  Transmission
      and reception are carried out in a full duplex mode.

      Main characteristics:

      *  Location:  Core resident.  The Handler is in the same memory
                    zone as the operating system and can be considered
                    as part of it.

      *  Initiation: By the IMP-HOST hardware interrupt.  This interrupt
                     is triggered either:

                     * during transmission when a message word is
                       completely sent to the IMP

                     * during reception when a message word has been
                       completely received from the IMP

                     * during idle time when the hardware received
                       either a 'start input' or 'start output' order
                       from the Sigma 7 CPU.  Those orders are issued by
                       the Network program for provoking interrupts back



Deloche                                                        [Page 18]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


                       (consequently for indirectly initiating the
                       Handler).

      *  Main functions: * Empties the output buffer upon transmitting
                           its content (outgoing message to the IMP.
                           This operation is carried out word by word
                           (32 bits) and makes use of "Write" orders for
                           driving the HOST-IMP hardware.

                         * Fills the input buffer with data received
                           from HOST-IMP hardware (incoming message).
                           This operation is also carried out word by
                           word and makes use of "Read" orders for
                           driving the HOST-IMP hardware.

                         * Wakes up the Network program when any of the
                           previous operations is complete.

   3.3.2.2  Network program

      General features:

      This program serves the user for opening/closing connections and
      transmitting/receiving messages.  It uses the Handler as an aid
      for inter-facing with the hardware.

      For the GORDO point of view it is a regular process and treated as
      such.

      Main characteristics:

      *  Location:  Disc resident.  More precisely it is on disc when
                    asleep and called in core when awakened by a
                    program.
      *  Initiation:  It is initiated through 'WAKE' service calls
                      issued either by a user process or by the Handler.
      *  Main functions: * Establishes/deletes outgoing connections upon
                           users' requests.  For so doing it sends
                           control messages (see 2.4.2) to remote
                           HOST[s] in order to get links
                           established/released; it then notifies back
                           the users.
                         * Insures the processing of incoming control
                           messages (transmitted over control links),
                           e.g., for contributing to
                           establishments/deletions of connections
                           (those requested by remote HOSTS).




Deloche                                                        [Page 19]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


                         * Prepares transmission of outgoing messages.
                           It picks up text messages from shared pages
                           (the messages are stored there by users),
                           formats them (adds leader, marking,
                           checksum..), and passes them along to the
                           Handler for transmission.
                         * Insures delivery of incoming messages.  It is
                           the opposite of the above operation.  The
                           users to which the messages should be
                           delivered are identified through the leaders.

      *  Virtual space configuration:  See figure 11.

      *  Specific feature:  It is integrated as an I/O process, so that
                            it can access privileged instruction (RD/WD
                            for indirectly initiating the Handler).

        [Figure 11 - Network Process Virtual Space - see PDF file]

3.4  Software Procedures

   The detailed software procedures are given on the flowcharts attached
   with Appendix A.

   However, to get a quick understanding of the implementation we list
   below some typical software procedures.

3.4.1  Description of some typical sequences

   Consider some of the transactions at user's disposal (See 2.4) and
   point out the basic software procedures they imply.  For each case we
   will delineate (i) what the user program does and (ii) what the
   Network program does.

   (a)  Open a primary link (See also 2.4.2)

         (i)  What the user program does[1]:

              *  it stores in the Network mail box directory the name of
                 a file, e.g., DATA;
              *  it couples the first page of this file to its virtual
                 space;
              *  it stores information in this page (its job/process #,
                 the remote HOST #, e.g., (i));
              *  it wakes up the Network process;
              *  it goes to sleep.





Deloche                                                        [Page 20]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


         (ii) What the Network program does:

              *  it explores the Network mail box directory and accesses
                 the file DATA;
              *  it couples the first page of this file to its virtual
                 space (Shared Zone, see 3.3.1.2).  Suppose this page to
                 be kth in the shared zone; k is the internal connection
                 #;
              *  it explores the ith slot of the new HOST table (See
                 3.3.1.1 (a)) and selects the first bit = 0, e.g., the
                 (alpha)th bit; alpha corresponds to the outgoing link
                 #;
              *  it stores information (job/process #, remote HOST #
                 (i), outgoing link # (alpha)) in the kth slot of the
                 CONNECT table (See 3.3.1.2).
              *  it momentarily stores the connection # (k) in the INPUT
                 LINK table.  This is carried out upon creating an entry
                 in this table (Hashing the key value:  "outgoing link #
                 (alpha) + remote HOST # (i) + outgoing flag".);
              *  it prepares the message text ENQ PRIM 0 0 a and formats
                 a complete message in adding leader, marking, checksum,
                 etc.;
              *  it checks the Handler state (bit in I/O locked page).
                 If the Handler is free, it stores the 'ready to go'
                 control message in the output buffer of the I/O locked
                 page, initiates the Handler, and goes to sleep.  Else
                 it goes to sleep.

   After a while the Handler wakes up the Network process because it has
   received a complete message.  We suppose this message be the control
   message sent by the remote HOST for acknowledging the establishment
   of the connection.  The message text should be:

            ACK ENQ PRIM 0 0 alpha 0 0 beta

   where beta is the incoming link #.  (See 2.4.2)

   Let's see now what the Network program does when receiving the above
   control message:

              *  it retrieves the connection # previously stored in the
                 INPUT LINK table upon re-hashing the same key value
                 (See above).  Also it deletes this entry;
              *  it creates an entry in the INPUT LINK table for the
                 incoming link.  For so doing it hashes the key value:
                 "incoming link # (beta]) + remote HOST # (i) +
                 "incoming flag".  In this entry it stores the HOST #
                 (i), the incoming link # (beta), and connection # (k);



Deloche                                                        [Page 21]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


              *  it updates the kth slot of the CONNECT table in storing
                 the incoming link # (beta);
              *  it turns on the 'net-user' bit in the kth shared page
                 (page corresponding to the primary connection that has
                 just been opened) and wakes up the user process;
              *  it goes to sleep.

   (b)  Transmit a message over primary link

         (i)  What the user program does[1].

              *  it stores the message text in the output buffer of the
                 primary connection shared page (see 3.3.1.2);
              *  it turns on the 'user-net' bit of this page and wakes
                 up the Network process;
              *  it goes to sleep.

         (ii) What the Network program does:

              *  it looks for user request, i.e., it explores in
                 sequence the connection shared pages and selects the
                 one that has its 'user-net' bit turned on.  Suppose k
                 be the selected page # on the shared list, K is the
                 connection #;
              *  it determines the request type in testing the 'request
                 bits' of the shared page k.  It finds out that it is a
                 request for transmitting a message.
              *  it takes the message text from the output buffer of the
                 shared page k, formats it into a complete message and
                 transmits to the Handler in a very similar way as above
                 (See Open a primary link).
              *  it goes to sleep.

      [1]  Remark:  In a first phase the user will directly write the
                    network functions in his program.  Later on
                    subroutines will be put at user's disposal.  These
                    subroutines will be very close to those described in
                    2.4.













Deloche                                                        [Page 22]

RFC 11          Host - Host Software Procedures in GORDO     August 1969


APPENDIX A

   Flowcharts

                       [see PDF file for flowcharts]

       [ This RFC was put into machine readable form for entry ]
          [ into the online RFC archives by Bob German 8/99 ]











































Deloche                                                        [Page 23]