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 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459
|
Network Working Group Bob Bressler
Request for Comments: 333 MIT/Dynamic Modeling
NIC # 9926 Dan Murphy
Category: C9 (experimentation) BBN/TENEX
Obsoletes: 62 Dave Walden
Updates: none BBN/IMP
15 May 1972
A PROPOSED EXPERIMENT WITH A MESSAGE SWITCHING PROTOCOL
CONTENTS
Introduction .................................................. 1
Some Background ............................................... 2
References .................................................... 3
MSP Specification ............................................. 4
Issue ......................................................... 8
Message Header ................................................ 10
Examples ...................................................... 15
TELNET ........................................................ 16
The Information Operator ...................................... 16
Unique Port Numbers ........................................... 20
Flow Chart .................................................... 23
MSP Variations ................................................ 25
Appendix ...................................................... 26
INTRODUCTION
A message switching protocol (MSP) is a system whose function is to
switch messages among its ports.
For example, there is an implementation of an MSP in each Interface
Message Processor. We believe that the effective utilization of
communications networks by computer operating systems will require a
better understanding of MSPs. In particular, we feel that Network
Control Programs (NCPs), as they have been implemented on the ARPA
Computer Network (ARPANET), do not adequately emphasize the
communications aspects of networking -- i.e., they reflect a certain
reluctance on the part of systems people to move away from what we
term "the stream orientation". We propose, as an aside the network
development using the current NCPs, to rethink the design of NCP-
level software beginning with a consideration of MSPs.
The thrust of this note is to sketch how one would organize the
lowest level host-host protocol in the ARPANET around MSPs and how
this organization would affect the implementation of host software.
Bressler, et al. Experimentation [Page 1]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
SOME BACKGROUND
Over the past several weeks there has been considerable informal
discussion about the possibility of implementing, on an experimental
basis, in several of the ARPA Network Host Computers, NCPs which
follow a protocol based on the concept of message switching rather
than the concept of line switching (see the parenthetical sentence in
the first paragraph of page 6 of NIC document 8246, Host/Host
Protocol for the ARPA Network). Party to this discussion have been
Bob Bressler (MIT/Dynamic Modeling) Steve Crocker (ARPA), Will
Crowther (BBN/IMP), Tom Knight (MIT/AI), Alex McKenzie (BBN/IMP), Bob
Metcalfe (MIT/Dynamic Modeling), Dan Murphy (BBN/TENEX), Jon Postel
(UCLA/NMC), and Dave Walden (BBN/IMP).
Several interesting points and conclusions have been made during this
discussion:
1. Bressler has implemented a message switched interprocess
communication system for the Dynamic Modeling PDP-10 and has
extended it so it could be used for interprocess communication
between processes in the Dynamic Modeling PDP-10 and the AI
PDP-10. He reports that it is something like an order of
magnitude smaller than his NCP.
2. Murphy has noted that a Host/Host protocol based on message
switching could be implemented experimentally and run in
parallel with the real Host/Host protocol using some of the
links set aside for experimentation. Further, Murphy has noted
that if this experimental message switching protocol were
implemented in TENEX, a number of (TENEX) sites could easily
participate in the experiment.
3. It is the consensus of the discussants that Bressler should
take a crack at specifying a message switching protocol* and
that if this specification looked relatively easy to implement,
a serious attempt should be made by Murphy and Bressler to find
the resources to implement the experimental protocol on the two
BBN TENEX and the MIT Dynamic Modeling and AI machines.
4. MSP was chosen as the acronym for Message Switching Protocol,
and links 192-195 were reserved for use in an MSP experiment.
-------------
*This note fulfills any obligation Bressler may have incurred to
produce an MSP specification.
Bressler, et al. Experimentation [Page 2]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
We solicit comments and suggestions from the Network Working Group
with regard to this experiment. However, although we will very much
appreciate comments and suggestions, because this is a limited
experiment and not an attempt to specify a protocol to supersede the
present Host/Host protocol for the ARPA Network, we may arbitrarily
reject suggestions.
REFERENCES
Familiarly with the following references will be helpful to the
reading of the rest of this note.
1) NIC document 8246, HOST/HOST PROTOCOL FOR THE ARPA NETWORK
2) NIC document 9348 on the Telnet Protocol
3) NIC document 7101, OFFICIAL INITIAL CONNECTION PROTOCOL,
DOCUMENT # 2
4) a system of interprocess communication in a resource sharing
computer network, CACM, April, 1972.
Reference 4 is a revision of RFC 62. We strongly suggest the reader
be familiar with reference 4 before he attempts to read the present
RFC; a reprint of reference 4 is attached as an appendix.
Bressler, et al. Experimentation [Page 3]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
MSP SPECIFICATION
Our MSP is essentially a generalization of the interprocess
communication system outlined in Section 3 of the fourth reference.
(Henceforth, if we are required to mention the interprocess
communication system presented in Section 3 of reference 4, we shall
call it "the IPC".) For two processes to communicate using the MSP,
the process desiring to send must in some sense execute a SEND and
the process desiring to receive must in some sense execute a RECEIVE.
The SEND and RECEIVE, in effect, rendezvous somewhere and
transmission is allowed to take place. With the RECEIVE are
specified (among other things) a FROM-TO-PORT-ID, a TO-PORT-ID, and a
RENDEZVOUS HOST. With SEND are specified a from-port-id, a to-port-
id, a rendezvous Host, and (possibly) some data to be transmitted.
Using SEND and RECEIVE, sending a message from a SENDER PROCESS to a
RECEIVER PROCESS takes place as follows. The sender process executes
a SEND which causes an OUT-MESSAGE plus the specified data to be
transmitted to the Host specified as the rendezvous Host in the SEND.
Concurrently (although not necessarily simultaneously)the receiver
process executes a RECEIVE which causes an IN-MESSAGE to be sent to
the Host specified as the rendezvous Host in the RECEIVE. At the
rendezvous Host, OUT-messages and IN-messages are entered in a table
called the RENDEZVOUS TABLE. When an OUT-message and an IN-message
are detected with matching to-port-id, from-port-id, and rendezvous
Host, three things are done: 1) the OUT-message plus the data is
forwarded to the Host which was the source of the IN-message, 2) the
IN-message is forwarded to the Host which was the source of the OUT-
message, and 3) the IN-message and OUT-message plus the data are
deleted from the rendezvous table in the rendezvous Host.
The process is greatly simplified if the rendezvous Host is also
either the send Host or receive Host. Specific algorithms
enumerating these sequences appear later in this note.
To clarify the basic concepts, let us look at a case involving three
Hosts, to which we shall give the names SND, RCV, and RNDZ. At Host
SND, process S is doing a send, and at Host RCV, process R is doing a
receive. Both specify rendezvous at Host RNDZ.
Bressler, et al. Experimentation [Page 4]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
+--------------------+ +----------+ +--------------------+
|HOST SND | | | |HOST RCV |
| | | | | |
| | | | | |
| (PROCESS) | +----------+ | |
| ( S ) | HOST | |
| \ | RNDZ | (PROCESS) |
| [DATA]| | ( R ) |
+--------------------+ +--------------------+
Process S now executes a SEND with
from-port-id = S, to-port-id = R, and rendezvous-Host = RNDZ.
Host SND then creates a table entry in its rendezvous table.
+-----------------------------------+
|HOST SND MSP _ _ _ |
| ------------->|_ _ _| |
| / ^ |_ _ _| <-|-------RENDEZVOUS
| / | |_ _ _| | TABLE
|(PROCESS) | |
|( S ) +-- SEND (from=S to=R; rend=RNDZ)
| \ |
| [DATA] |
+-----------------------------------+
Host SND now sends an "OUT" message with S's data to Host RNDZ.
HOST SND HOST RNDZ
+------------+ +---------------------------+
| MSP| "OUT" + DATA |MSP _____ RENDEZVOUS |
| |--------------------|--> |_ _ _| TABLE |
| | from=S; to=R | \ |_ _ _| |
| | | \ |_ _ _| |
+------------+ | \ __ |
| \---------->| | DATA |
| |__|BUFFER |
| |
+---------------------------+
Concurrently process R at Host RCV executes a RECEIVE with from-
port-id = S, to-port-id = R, and rendezvous-Host = RNDZ. As above,
Host RCV creates a table entry in its rendezvous table and sends an
"IN" message to Host RNDZ (see following figure).
Bressler, et al. Experimentation [Page 5]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
(Don't panic now about buffering in an intermediate Host. The time
to panic is afer you've read and understood the rest of our
arguments.)
HOST RNDZ HOST RCV
+------------------------+ +-----------------------+
| MSP | | MSP |
| TABLE _____ | | _____ TABLE |
| +-|_ _ _| | "IN" | |_ _ _| |
| | |_ _ _|<-|----------|_ _ _|<-\ |RECEIVE
| | |_ _ _| | | |_ _ _| \ <--|(from=S
| | | | \ | to=R
| _V_ | | \ | rend=RNDZ)
| BUFFER | | | | (PROCESS) |
| |___| | | ( R ) |
+------------------------+ +-----------------------+
Host RNDZ now notices that the "OUT" from Host SND and the "IN" from
R at RCV match one another and thus Host RNDZ takes three actions:
1. Sends an "IN to Host SND (from-port-id = S, to-port-id = R,
rendezvous-Host = RNDZ).
2. Sends an "OUT" and the buffered data to Host RCV (from-port-id
= S, to-port-id = R, rendezvous-Host =RNDZ)
3. Clears the entry from its table.
HOST SND HOST RCV
+------------------+ +------------+ +-------------+
| | | TABLE | | |
| TABLE ___ | "IN" | ___ | "OUT" | ___ TABLE|
| |___| | | |___| | + DATA | |_ _| |
| |___|<---|--------|---|___|----|---------|->|_ _| |
| |___| | | |___| | | |_ _| |
| ( S ) | +------------+ | ( R )|
| | HOST RNDZ | |
+------------------+ +-------------+
Host RCV gets the "OUT" and DATA and finds the matching entry in its
table. It gives the DATA to process R and clears the entry from its
table.
Host SND gets an "IN" which matches an entry in his table and clears
that entry. This message serves as a combined acknowledgement and go
ahead which can be passed along to process S.
The transmission is now complete.
Bressler, et al. Experimentation [Page 6]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
By both, one, or neither of the sender and receiver processes
specifying a remote rendezvous Host, four important different kinds
of transmissions can be made to take place. These are illustrated in
the following four figures. In the figures crossed or parallel
dotted lines are used to indicate rendezvous. The site of the
"crossed rendezvous" is the important difference between types of
transmission illustrated in figures. Circles indicate processes.
Rectangles are rendezvous tables.
The figures also show "(IN)" and "(OUT)" messages being passed into
the processes. The parentheses are used to indicate that the "IN"
and "OUT" are only CONCEPTUALLY passed into the processes. What
actually happens is implementation dependent. The process might be
awakened and be given no further information if it blocked when
issuing the SEND or RECEIVE. The process might be interrupted and
passed some information such as the to-port-id from the IN or the
from-port-id of the OUT. The process might actually be passed the
complete IN or OUT message.
------ _________ ------
( ) | | ( )
( ) SEND | | RECEIVE ( )
( )------>|--+ +---|<--------( )
( ) | \/ | ( )
( ) (IN) | /\ | (OUT) ( )
( )<------|--+ +--|-------->( )
(______) |_________| +DATA (______)
|<------------- Host K ------------------>|
A Rendezvous at the Sender's Host
---- _______ ______ ----
( ) | | | | ( )
( ) SEND | | IN | | RECEIVE( )
( )------>|-+ +--|<------------|------|<-------( )
( ) | \/ | | | ( )
( ) (IN) | /\ | OUT+DATA | | (OUT) ( )
( )<------|-+ +--|------------>|------|------->( )
(____) |_______| |______| +DATA (____)
|<---- Host K ------>|<-- Network-->|<----- Host L ----->|
A Rendezvous at the Sender's Host
Bressler, et al. Experimentation [Page 7]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
---- ______ _______ ----
( ) | | | | ( )
( ) SEND | | OUT+DATA | | RECEIVE( )
( )------>|------|------------->|-+ +--|<-------( )
( ) | | | \/ | ( )
( ) (IN) | | IN | /\ | (OUT) ( )
( )<------|------|<-------------|-+ +--|------->( )
( ) | | | | +DATA ( )
(____) |______| |______ | (____)
|<---- Host K ----->|<-- Network-->|<----- Host L ----->|
A Rendezvous at the Receiver's Host
---- ______ _______ ______ ----
( ) | | | | | | ( )
( ) SEND | | OUT+DATA | | IN | |RECEIVE( )
( )------>|------|--------->|-+ +--|<---------|------|<------( )
( ) | | | \/ | | | ( )
( ) (IN) | | IN | /\ |OUT+DATA | | (OUT) ( )
( )<------|------|<---------|-+ +--|--------->|------|------>( )
( ) | | | | | | +DATA ( )
(____) |______| |______ | |______| (____)
|<---- Host K ----->|<--Net-->|<-Host->|<--Net-->|<----- Host L ----->|
M
A Rendezvous at an Intermediate Host
ISSUES
Timeouts.
The issue of timeouts is a very sticky one. A coherent system of
timeouts simplifies everything and does away with races. However,
many Hosts are unwilling or unable to use timeouts, especially
timeouts whose duration is specified.
Without these timeouts there is probably a need for a negative
acknowledgment which goes back to the source of an IN or OUT when one
is timed out. However, this now leads to races.
A negative acknowledgment (which we will refer to as a FLUSH message)
could be employed by a Host to mean:
Bressler, et al. Experimentation [Page 8]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
1. I have no room in my table
2. I have no more available buffer space or
3. I no longer wish to retain the table entry/buffer.
In general, we believe that a Host should be allowed to throw away
an IN or OUT+data whenever it is no longer convenient for the Host
to hold the messages. This can be immediately on the arrival of a
message; for instance, if the Host does not want to buffer traffic
for which it does not have a user buffer. In lieu of timeouts,
any time a process issues a SEND or RECEIVE, it can take it back
by issuing the matching RECEIVE or SEND.
Blocking the Process After a Send or Receive.
This is a question which is left implementation dependent. In
general, we do not think it is a good idea to block the process
after a SEND since it may want to do another to another port or
even do a RECEIVE. In fact, we see nothing inherently wrong with
a process doing two or more SENDs to the same port as long as the
communicating processes know what they are doing. Of course, some
communicating processes will prohibit several simultaneous
messages being in transit between the same ports, for instance the
TELNETs may well prohibit this. However, for reasons of
increasing bandwidth, etc., two processes may well want several
simultaneous messages. In this case we think it is up to the
processes to worry about the sequencing of messages; however, we
refer users desiring their processes to take a care of message
sequencing to the method used in the IMP/Very Distant Host
interface which is documented in Appendix F of BBN Report 1822.
Message Buffering
A few points are worth mentioning with regard to message
buffering. First, most OUTs will probably be accompanied by data.
Therefore, in general, since the receiver process may be swapped
out, the receiver Host monitor must be prepared to buffer some
data somewhere. To minimize the amount of buffering needed, the
monitor could refuse further traffic from the IMP until the
earlier traffic from the IMP has been written on a disk or drum.
Or the monitor could have a small number of buffers in the monitor
area of memory which it fills as traffic comes from the IMP, and
which are swapped with buffers claimed earlier by the receiver
processes as the receiver processes are swapped in. Note that the
buffers may be less than the maximum subnet message size in length
if the RECEIVEs never specify a longer message length -- of
course, this can be enforced. Finally note that the message size,
Bressler, et al. Experimentation [Page 9]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
receive-port-id, etc. are available in the first 144 bits which
come in from the IMP. It might be useful to read this before
deciding into which buffer to read the rest of the message.
Positive Acknowledgments
Built into the system is a certain form of acknowledgment. The
information is always available as to when the receiving process
has done a RECEIVE. The sending Host is assured of receiving an
"IN" when the receive call is issued.
Further forms of acknowledgment and validation can be implemented
at the first user level, and advanced protocols will probably
develop a library of such routines.
MESSAGE HEADER
The following section deals with the specific format of Host to
Host messages and algorithms describing the proper response to a
given message.
Each message begins with a 144 bit header containing the following
fields:
1. HOST-TO-IMP leader (32 bits) as specified in BBN Reports 1822
2. to port ID (i.e., the id of the port receiving the message) (24
bits)
3. MSG TYPE (8 bits) IN, OUT, FLUSH, etc.
4. from port ID (i.e., id or the port sending the message) (24
bits)
5. initiating Host's table position (8 bits) see below.
6. HOST "sourcing" this message (8 bits) see below.
7. RENDEZVOUS HOST (8 bits)
8. bit count of data (16 bits)
The header format has been arranged so that no data item will cross a
word boundary on machines with 16, 32, and 36-bit words, except where
the size of the item is greater than the word size. The actual
arrangement of bytes within words is shown in the following figures
for these three word sizes. For the benefit of 36-bit Hosts, bytes 4
and 13 (numbering from 0) are unused. The 2 and 3-byte items do not
Bressler, et al. Experimentation [Page 10]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
cross word boundaries except for the port ID's on the 16 bit
machines. This attention to packing and unpacking ease was given
both for general convenience, and in particular because Hosts may
wish to examine the header at interrupt level to determine where the
rest of the message should go.
+-------------+-------------+
0 | HOST/IMP | DESTINATION |
| FLAGS | |
+-------------+-------------+
1 | LINK | /////////// |
| | /////////// |
+-------------+-------------+
2 | /////////// | |
| /////////// | |
+-------------+ |
3 | TO PORT ID |
| |
+-------------+-------------+
4 | MESSAGE | |
| TYPE | |
+-------------+ |
5 | FROM PORT ID |
| |
+-------------+-------------+
6 | TABLE | /////////// |
| POSITION | /////////// |
+-------------+-------------+
7 | SOURCE | RENDEZVOUS |
| HOST | HOST |
+-------------+-------------+
8 | BIT COUNT |
| |
+-------------+-------------+
| |
9 | DATA |
// //
| |
+-------------+-------------+
16-bit Host Format
+-------------+
| | ////////// = unused
| | //////////
+-------------+
8 bits
Bressler, et al. Experimentation [Page 11]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
0 8 16 24 32 36
+-------------+-------------+-------------+-------------+------+
0 | HOST/IMP | FOREIGN | LINK | ////////////////// |
| FLAGS | HOST | | ////////////////// |
+------+------+-------------+-------------+-------+-----+------+
1 | //// | TO PORT ID | MESSAGE |
| //// | | TYPE |
+------+------+-------------+-------------+-------------+------+
2 | FROM PORT ID | TABLE | //// |
| | POSITION | //// |
+------+-------------+-------------+------+-------------+------+
3 | //// | SOURCE | RENDEZVOUS | BIT COUNT |
| //// | HOST | HOST | |
+------+-------------+-------------+---------------------------+
| |
4 | |
// DATA //
| |
| |
+-------------+-------------+-------------+-------------+------+
36-bit Host Format
+-------------+-------------+-------------+-------------+
0 | HOST/IMP | FOREIGN | LINK | /////////// |
| FLAGS | HOST | | /////////// |
+-------------+-------------+-------------+-------------+
1 | /////////// | TO PORT ID |
| | |
+-------------+-------------+-------------+-------------+
2 | MESSAGE | FROM PORT ID |
| TYPE | |
+-------------+-------------+-------------+-------------+
3 | TABLE | /////////// | SOURCE | RENDEZVOUS |
| POSITION | /////////// | HOST | HOST |
+-------------+-------------+-------------+-------------+
| BIT COUNT | |
| | |
+-------------+-------------+ |
| |
// DATA //
| |
+-------------+-------------+-------------+-------------+
32-bit Host Format
Bressler, et al. Experimentation [Page 12]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
The fields within the Host/IMP leader are already familiar to NCP
programmers however, two points about these fields are worth
mentioning. First, the destination field originally contains the
number of the rendezvous Host. After rendezvous at a intermediate
site, the destination field contains the source of the message
rendezvous with. Second, the link field for the MSP experiment can
only contain link number 192-195. We have not taken the time to
figure out a sensible allocation of these four links among all the
messages which might be sent using the MSP. One alternative is to
cycle over the links to increase the bandwidth of the "pipe" between
any two Hosts. For the time being, until further consideration is
given to this issue, we suggest each Host at a site using one
(unique) link for all its communication.
The message types we have to represent in the message type field are
few now: we suggest message type 2 for SEND or OUT messages and
message 3 for RECEIVE or IN messages. Message type 4 is the FLUSH
message, if FLUSH is used.
The rendezvous Host field needs no comment. Except that the field is
unnecessary after the rendezvous has taken place and could then be
used for something else.
The bit count is a count of data bits in an OUT message or the size
of the input buffer (not including the header) in an IN message.
Thus the sender process can tell from the IN message bit count when
it receives the IN message how much of the data in the OUT message
was accepted by the receiver process and can use this knowledge to
retransmit the remainder of the message if so desired. After the
rendezvous, we recommend that all of the data in the message be sent
on the source of the IN message even if the OUT bit count was greater
than the IN bit count. Thus, at the receiver Host the monitor has
the option (if it wants to take it) of discarding the message for
being too long, sending the number of bits the receiver process has
done an IN for into the receiver process and discarding the rest, or
queuing the rest of the bits and somehow notify the receiver process
that there are more bits which the receiver process can ask for.
The to- and from-port-id fields are 24-bit numbers. This size was
chosen to help the TIPs. The first eight bits of a port Id should be
the number of the Host at which this port id was created. Note well,
that this is not necessarily the Host at which the port is being
used. This is necessary since rendezvous take place at intermediate
sites and because ports may move from site to site. We suggest that
all port ids with the first eight bits all zero be reserved for
network-wide use. In particular, a port id with all 24 bits zero
will be used to mean "ANY". This gives us the options of:
Bressler, et al. Experimentation [Page 13]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
RECEIVE from ANY to SPECIFIC
RECEIVE from SPECIFIC to SPECIFIC
SEND from SPECIFIC to ANY
and SEND from SPECIFIC to SPECIFIC
Examples of the use of these options will be given below.
The other options (RECEIVE to ANY) and (SEND from ANY) we feel are
kind of useless but would not prohibit them. We believe that in the
absence of explicit specification of rendezvous Host, the use of an
ANY port id in the user's system call should affect the default
rendezvous site as follows:
RECEIVE from ANY--rendezvous in receiver
RECEIVE from SPECIFIC--rendezvous in sender
SEND to ANY--rendezvous in sender
SEND to SPECIFIC--rendezvous in sender
The less significant 16 bits of the id can be used however a Host
wants to. For instance, eight bits might be used as a process id and
eight bits might be used as a channel specification within the
specified process. We suggest that each Host reserve the port ids
with the middle eight bits all zero for special uses as well known
ports.
The table position field is included to help prevent costly table
searches at interrupt level. Hosts sending INs and OUTs, put in the
table position field the rendezvous table position of the SEND or
RECEIVE associated with the IN or OUT. At an intermediate Host
rendezvous, the table position fields in the matching IN and OUT are
swapped so that when the messages arrive at the opposite end, the
matching SEND and RECEIVE can be found quickly. The MSP must do the
swap at the rendezvous, but of course the MSPs need not fill in the
table position field when first transmitting an IN or OUT in which
case the information arriving in an IN or OUT will be meaningless.
The general algorithm, then, is to check the table position as
specified in this field and if that fails, search the whole table.
The source field is filled in INs and OUTs by the MSP which
originally sends these messages. At the rendezvous the source of
each message is preserved in the message being forwarded to the final
Host. When an IN or OUT arrives at a process, the process can use
Bressler, et al. Experimentation [Page 14]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
the source information to update its understanding of the rendezvous
Host (e.g., when the destination Host and rendezvous Host are
different).
EXAMPLES
The typical example.
We envision communication normally taking place using specifications
to and from ports and rendezvous at the sender. For instance, the
TIP would probably send to other Hosts using this method and would
certainly receive from other Host until the TIP asks for it. In this
"normal" method a monitor could even look at the bit count in the
arriving IN-message, use that as an allocation and then simulate an
OUT-message of the exact correct length.
The logging example
Consider an example of SEND to SPECIFIC and RECEIVE from ANY with the
rendezvous at the receiver. This method might be used by some
logging receiver process with a well-known to-port. For instance, a
measurements program to which statistics are sent from many processes
throughout the net.
The program library example
Suppose within a given time-sharing system there is a particular
library routine which is available for use by any process in the
network. The library process has a RECEIVE from ANY always pending
at a well-known port. Eventually, some process sends a message to
the library process' well-known-port. This message includes the data
to be processed, a port to use for sending the answer, and the money.
The library process takes some of the money and sends it to the
well-known port of the accounting process which itself has a RECEIVE
from ANY pending. The library process then processes the data and
sends the answer back to the process which requested the service
using a SEND to SPECIFIC message which rendezvous at the destination
where there is already a RECEIVE from SPECIFIC pending. Of course,
in this message besides the answer, any change the requesting process
has coming is returned.
A comment
As can be seen from our examples, we think rendezvousing at an
intermediate Host will seldom be done as the chief benefit of this
comes when it is desirable to move a port (see reference 4 for a
discussion of this). We would like to see all Hosts provide some
Bressler, et al. Experimentation [Page 15]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
(meager) amount of buffering for this purpose but would not require
it. It shouldn't be too painful to provide a little of this kind of
buffering-especially since a Host can throw away any message it can't
handle.
(THIS PAGE WILL BE REPLACED WITH A BETTER DESCRIPTION OF TELNET UNDER
MSP IN A FEW DAYS--DCW)
TELNET
Let us postulate a pair of Telnet programs that maintain two
bidirectional communication paths, one for data and one for control.
Let us also assume, for convenience that the port IDs are as follows:
If the WRITE-CONTROL-ID is N, then --
READ-CONTROL-ID=N+1,
WRITE-DATA=N+2,
READ-DATA=N+3.
The initial state is the server Telnet sitting with a READ-FROM-ANY
pending.
The user Telnet now issues a SEND-TO-SPECIFIC with the data field
containing the PORT-ID of the SERVER's WRITE-CONTROL-ID. This message
is sent from the user-Telnet's WRITE-CONTROL-ID.
Thus all port IDs are specified by the user Telnet, so, if desired,
he need only remember one number and derive the rest. Uniqueness is
preserved since the port IDs supplied by the user Telnet contain his
Host ID and other information making the ID unique to him.
Now that these communication paths are established, the two processes
can exchange data and control information according to established
Telnet protocols.
THE INFORMATION OPERATOR
The Message Switching Protocol itself impose no fixed requirements on
the use of the port ID's, and the problem of process identification
is somewhat separated from the means used to effect communication.
It is, however, very much a part of the overall issue of interprocess
communication, and so we here specify a facility for handling process
identification, the information operator.
Bressler, et al. Experimentation [Page 16]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
One goal in a process identification scheme is to provide a means by
which processes can select their own identifiers which can be
guaranteed unique and can contain information meaningful to the user.
Problems of efficiency prevent making the port ID's themselves large
enough to accomplish this aim. Efficiency questions aside, it would
appear to be ideal to allow processes to use character strings of
arbitrary length to identify themselves. Uniqueness can then be
easily ensured if, for example, users follow the convention of
including their names in the process identification string. Further,
the remainder of the name can be chosen to have some meaning related
to its use with obvious advantages and convenience for users.
One solution is to establish a convention whereby the symbolic
identifiers are used only during some initial phase of communication
and not in every message. That is, processes identify each other
initially using symbolic identifiers, but exchange local port
identifiers at the same time which are used for all ensuing messages.
The means of providing this facility is to establish a process at
each of a number of Hosts (e.g., all server Hosts) called the
"information operator". The function of this process is to associate
symbolic identification strings and port ID's. A process can
identify itself and/or a foreign process to the information operator,
and may request the port ID of the foreign process. The symbolic
identification strings are chosen by the processes and are long
enough to contain meaningful information, e.g., LOGGER, MURPHY-
TESTPROG.
Communication with the information operator, whether by local or
remote processes, is via the regular MSP functions. The information
operator will always have a RECEIVE ANY outstanding on a well-known
port. This could in general be the only well-known port in
existence. A message received on this port contains the following
parameters:
1. String identifying the foreign process with which communication
is desired.
2. String identifying the calling process.
3. Calling process' port number.
4. A delay specification.
Bressler, et al. Experimentation [Page 17]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
The format of these parameters is shown in Fig. 4. In some cases,
one or more of the arguments would be null. Following receipt of a
message, the information operator will, in some cases, do a SEND
SPECIFIC to the calling process' port number providing the desired
information or notice of failure.
The following two cases would appear to cover all functions of the
information operator. They correspond to the SEND/RECEIVE SPECIFIC
ANY cases of the MSP.
1. Two processes each knowing the specific identify of the other wish
to communicate. Each does a SEND SPECIFIC to the information
operator, giving parameters 1-2, the default delay spec in this
case being WAIT. When the information operator receives the
second of these and notes that a match exists, it sends to each
process the port ID of the other process and deletes both strings
and both port ID's from its tables. The two processes, which have
each done a RECEIVE SPECIFIC in anticipation of the foreign port
number, can then communicate using just the port numbers and basic
MSP functions.
2. A process is set up to provide some sort of general service or
information, and its name and protocol advertised. This process
intends to maintain an outstanding SEND or RECEIVE ANY for the
first (and perhaps only) message transaction, e.g., the library
process discussed earlier. Most such processes would be receivers
initially, but there might be a few cases where a SEND could be
left outstanding, and a forcing process could come along and pick
up the information. In either case, the service process will do
SEND SPECIFIC to the information operator giving the local
symbolic ID and local port ID. The foreign symbolic ID would be
null, and the default delay spec is NO-WAIT. That is,
INFO ( -, local ID, local port)
The information operator will enter this information in its tables
but return nothing to the caller. The caller would proceed to do
its SEND/RECEIVE ANY to wait for business. When another process
wishes to use the advertised service, it asks the logger for the
port ID of the service process, i.e.,
INFO (service ID, -, local port)
The local symbolic ID need not be specified, and the default delay
spec is NO-WAIT. The information operator would SEND the port ID
of the service process to the local port of the caller, and retain
the table entry for future callers. Only the service process
Bressler, et al. Experimentation [Page 18]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
could request the entry be deleted. If the service ID was unknown
to the information operator at the time of this call, it would
immediately return a failure indication, i.e., zero.
Communicating processes would normally use the information operator
local to one or the other, and like the rendezvous Host in the MSP,
this would be agreed upon in advance. Service processes would
normally use the information operator at their local site, and
correspondingly, user processes would call the information operator
at the site where the service process was expected to be available.
There is no restriction on using an information operator at some
other site of course, and some small and/or lazy servers could use a
different Host for their service process ID's. It presents no
problem for two or more information operators to have entries for the
same service process, and in fact, this may be very desirable for
special types of service processes which exist only one place on the
net and may move around from time to time.
Processes would specify their own local port numbers, and each system
would have to provide some way to help user processes do this. In
TENEX for example, one would probably use the job number concatenated
with another number assigned within the job. The information
operator cannot supply port numbers because it will be running on a
different Host than one or both of the communicants and cannot know
what is a unique number for that Host. In some cases, processes
would ask the "unique number process" (described below) for their
local port ID, and would make it known via the information operator.
In actual practice, a few exceptions would be made to the rule that
the only "well-known" port in the world is the information operator.
Such exceptions would be processes common to many Hosts, e.g.,
LOGGER, or those in particularly frequent use. In such cases the
unique port numbers would be assigned by administrative fiat and
recorded and published to all users.
The symbolic identification strings are specified to be from 1 to 39
(an arbitrary maximum) ASCII characters terminated by a null (byte of
all zeroes). The characters will be 7-bit ASCII in 8-bit bytes with
the high order bit set to zero. A null string (first byte is null)
is used where no argument is required.
Bressler, et al. Experimentation [Page 19]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
Format of Information Operator Messages
To Information Operator: A stream of 8-bit bytes.
+------+--//---+------+------+--//---+------+------+-------+-------+
|char 0| 1// n | null |char 0| 1// n | null | port | number| delay |
| | // | | | // | | | |spec |
+------+--//---+------+------+--//---+------+------+-------+-------+
\ /\ /\ /\ /
\_________________/ \___________________/ \___________/ \____/
PARAMETER 1 PARAMETER 2 PARAMETER 3 PARAMETER
4
Parameters given:
1. String identifying the foreign process with which communication
is desired. (1 to 39 characters, or null)
2. String identifying the calling process. (1 to 39 characters, or
null)
3. Calling process' port number.
4. Delay specification:
0=default
1=wait for match
2=don't wait for match
From Information Operator: 3 8-bit bytes.
+--------|-------|-------+
| byte 0 | 1 | 2 |
+--------|-------|-------+
Port number (24 bits) of requested foreign port if successful, 0 if
unsuccessful.
UNIQUE PORT NUMBERS
The existence of unique port numbers is essential to the operation of
the MSP. For instance, when two communicating processes specify
message rendezvous at an intermediate site, the processes must be
able to specify to- and from-ports which are not being used by other
processes which have specified message rendezvous at the same site or
else messages may be delivered to incorrect destinations. We have
alluded to a method of providing unique port numbers earlier in this
note. This method is to partition the 24-bit port number space into
disjointed segments and give one segment to each Host in the network
Bressler, et al. Experimentation [Page 20]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
to distribute when it is called upon to "create" a unique port id.
Thus each 24-bit Host number will consist of two major parts. The
first 8 bits will be the number of the Host "creating" the port id
and the next 16 bits can be used in any manner the creating Host
desires. This gives each Host 2^16 port numbers to distribute, and
each Host will have the burden of distributing its segment of the
port number space in a unique manner. We recommend the convention
that the port numbers with the middle 8 bits equal to zero be
reserved for well-known ports in the creating Host's system. We
already recommend in an earlier section that port numbers with the
first 8 bits equal to zero be reserved for network-wide use and in
particular the port number with all 24 bits equal to zero be used to
mean ANY.
Since each Host only has 2-16- port numbers to distribute, in general
port numbers will not be able to be held and used by processes for
long periods of time (e.g., weeks and months). More typically, Hosts
will probably implicitly "take back' all port numbers the Host has
distributed each time the Host's system goes down and will
redistribute the port numbers as required when the system comes back
up. In other words, port numbers will not in general remain unique
over the going down of the creating Hosts. Of course, a given Host
may see to give the same port numbers to a number of standard
processes (such as the FORTRAN compiler) each time it comes up port
numbers registered with an information operator will frequently
remain constant over system ups and downs.
In spite of the fact that each Host will probably not in general be
able to distribute port numbers to arbitrary user processes which ca
be guaranteed to remain unique over a long period of time, there will
still be demand for provision of long-term unique port numbers. To
some, the procedure of going through the information operator smacks
much too much of making a connection. These people will insist that
for a variety of reasons their processes be allowed to communicate
via ports whose identifiers remain constant for long periods of time.
Therefore, it would be nice if at one or two places in the network, a
long-term unique number service was provided. We'll call a process
providing this service the Unique Number Process. The Unique Number
Process would have assigned to it one segment of the unique port
number space-all those port numbers, for instance, with the first 8-
bits equal to 377-8. This process would have a SEND-to-ANY pending
from a well-known port with local rendezvous specified. When any
process wanted a unique number which it could depend on not to be
used for all time or until the number is given back, it would send a
RECEIVE-from-SPECIFIC specifying the well-known port of the Unique
Number Process and rendezvous at the Unique Number Process' Host.
The Unique Number Process' pending SEND-to-ANY would contain a unique
number. Also, the Unique Number Process would have a RECEIVE-from-
Bressler, et al. Experimentation [Page 21]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
ANY always pending at another well-known port with local rendezvous
specified. At this port the Unique Number Process would receive
unique numbers which processes are giving back. The Unique Number
Process would maintain a bit table 2-16- bits long indicating the
state of each of its unique numbers (free or in use) in some long-
term storage medium such as in the file system. The Unique Number
Process might also maintain some information about each process to
which it gives a unique number so that when the supply of unique
number gets depleted, processes can be asked to return them.
It has already been mentioned that some of the process ID's
registered along with their symbolic names at the information
operator might be long-term unique numbers gotten from the Unique
Number Process. It should also be mentioned that there would seem to
be no reason, other than scarcity of storage space, that in addition
to the port number through which primary access is gained to a
process and which was called the process ID in the previous section,
arbitrary port numbers along with their symbolic identified could not
be registered with an information operator. For instance, rather
than registering the name BBN-FORTRAN and a single port number, one
could perhaps register the port numbers whose symbolic identifiers
were BBN-FORTRAN-CONTROL-TELETYPE, BBN-FORTRAN-INPUT-FILE, BBN-
FORTRAN-LISTING-FILE, and BBN-FORTRAN-BINARY-OUTPUT-FILE. This is
perhaps at odds with standard practice within operating systems, but
is consistent with the philosophy of reference 4 that communication
is done with ports and not processes.
Let us now address an issue which has been ignored up to now and
which was only alluded to in reference 4, the issue of port
protection. We have not given this matter a great deal of thought;
however, one mechanism for port protection seems quite
straightforward. The heart of this mechanism is a process at each
Host which we shall call (alliteratively) the Port Protection Process
(PPP). The PPP maintains a list of all processes which exist at the
Host and for each process the numbers of all ports which the process
has "legally" obtained. Every time a process does a SEND or RECEIVE,
the monitor checks with the PPP to see if the process has specified
port numbers it has the right to use; i.e., those legally obtained.
The PPP has some RECEIVEs always pending at well-known ports. When
one process wants to pass a port to some other process, the first
process sends a message to the PPP specifying the number of the port
to be sent, the Host number at which the second process resides, a
port at which the second process is expecting to receive the port,
etc. The PPP looks up in its tables whether the first process has
the port it wants to send. If it does, it sends a message to the PPP
at the destination site. The message contains the number of the port
to be transferred and the RECEIVE port for the destination process.
The destination PPP checks in its table whether the process has the
Bressler, et al. Experimentation [Page 22]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
RECEIVE port, and if so, passes the new port to the process and
updates its tables to indicate the process now possesses the new
port. The messages to a PPP will optionally be able to specify that
a copy of a port be sent, a port be deleted, etc. The PPPs would
probably have some built-in legal ports for each process,
particularly the port's processes used to communicate with the PPP.
The exact specification requires development but that should not be
hard (see (3),(6), and (7) in reference 4). The main difficulty we
see is efficient checking of the PPP's tables by the monitor for
every RECEIVE or SEND without entirely supplanting the monitor's
current protection system.
FLOW CHART
The following section describes a flow chart for most of the MSP. A
distinction is made between calls made by local processes called SEND
and RECEIVE, and messages coming in over the NET called IN and OUT.
An additional distinction is made between calls (or messages) with a
local rendezvous and those with a foreign rendezvous Host.
Since the code is quite similar, the distinction need not be made,
but will be included for the sake of clarity.
It is assumed that the MSP has table provisions for the following
items:
source of message
rendezvous Host
FROM-PORT-ID
TO-PORT-ID
table position
type of message
data size and location
data about the user process
User does a SEND or RECEIVE
A. Rendezvous is at a foreign host
1. Store the appropriate table data
2. Send a message to the rendezvous host
a. SEND: OUT + DATA
b. RECEIVE: IN
B. Rendezvous is local - look for entry in table
Bressler, et al. Experimentation [Page 23]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
1. Entry NOT found: create entry with appropriate data
2. A matching entry exists in table:
a. RECEIVE: give user the data
b. Send a message to the other host (as specified by the source
field of the original msg)
1)SEND: OUT+DATA
2)RECEIVE: IN
c. Alert user to the fact that transaction is complete
d. Clear table entry
An IN is received over the NET-search table for matching entry.
A. No matching entry create an entry with appropriate data.
B. A match exists
1. Entry was cause by a local SEND
a. Send "OUT _ DATA" to source of IN
b. Inform user of transaction
c. Clear table entry
2. Entry was caused by an OUT received over net-acting as third
host.
a. Send IN to site that created table entry
b. Send OUT + DATA (previously buffered) to site sending the IN
c. Clear table entry
An OUT + DATA is received over the NET -search table for matching
entry
A. No match is found
1. buffer data
2. create appropriate table information
Bressler, et al. Experimentation [Page 24]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
B. A match is found
1. Table entry was caused by locally executed RECEIVE
a. give data to the user and alert him to its existence.
b. send a matching "IN" to the source of the "OUT"
c. remove entry from table
2. Table entry was caused by the receipt of an "IN" over the NET,
thus we are acting as a third party host
a. send the "OUT + DATA" to the host stored in the table
b. send an "IN" to the host from which the "OUT" had just
arrived.
MSP VARIATIONS
It may of interest to the reader to know of some of the other MSPs we
have considered while arriving at the present one.
The simplest we considered is an MSP based on all rendezvous being
done at the destination Host. The sender process sends an OUT-
message plus the data to the destination Host. The receiver process
does an IN which stays at the receivers Host. The OUT and RECEIVE
rendezvous and the data is passed to the receiver process. The
transmission is now complete, except in some variations of this MSP
an acknowledgement is sent to the sender process. This MSP has
couple of disadvantages: In the simplest formulation, the RECEIVE had
to be waiting when the OUT+data arrived, otherwise the out data were
thrown away. This puts too tight a constraint on the timing of the
SEND and RECEIVE, especially since the sender and receiver processes
can be a continent apart. However, if the IN is allowed to arrive
first and must be held until matched by a RECEIVE, the monitor must
buffer an indeterminate amount of data in all cases including the
normal one. Further, basing everything on rendezvous at the
destination makes the process of moving a port difficult.
The next simplest MSP we considered was the IPC of reference 4. This
works just the opposite of the above described MSP in that it is
based on almost all rendezvous being done at the source Host with two
special messages to handle the relatively uncommon cases when a
rendezvous must be done at the destination or an intermediate Host.
This system, its advantages, and disadvantages is discussed at very
great length in the reference.
Bressler, et al. Experimentation [Page 25]
RFC 333 MESSAGE SWITCHING PROTOCOL EXPERIMENT May 1972
A third variation on the MSP, suggested by Crowther, is the same as
the present MSP in that the OUT and IN rendezvous at a process
specified rendezvous Host and the OUT is sent to the source of the IN
and the IN to the source of the OUT, but the data is not sent along
with the OUT. Instead, when the OUT finally reaches the source of
the IN, another message is sent from the receiver Host to the source
Host requesting the data to be sent. The data finally is transmitted
to the destination in response to this data request message. Our
main objection to this system is its lack of symmetry, but we do
recognize that it does not require any Host to buffer data for which
a process has not set up an input buffer and perhaps for that reason
it is a better system than the MSP we are presenting.
In the last MSP variation we considered, the difference between SEND
or RECEIVE and OUT or IN was discarded. In this case only one
message is used which we will call TRANSFER. When a process executes
a TRANSFER it can specify an input buffer, an output buffer, both, or
neither. Two processes wishing to communicate both execute TRANSFERs
specifying the same to and from port ids and the same rendezvous
Host. The TRANSFERs result in TRANSFER-messages plus data in the
case that an output buffer was specified which rendezvous at the
rendezvous Host. When the rendezvous occurs, the TRANSFER-messages
plus their data cross and each is sent to the source of the other.
The system allows processes not to know whether they must do a SEND,
or RECEIVE and is (perhaps) a nice generalization of the MSP
presented in this note. For instance, two processes can exchange
data using this system, or two processes can kind of interrupt each
other by sending dataless TRANSFERs. This variation of the MSP is a
development of a suggestion of Steve Crocker. Its disadvantages are:
(1) unintentional matches are more likely to occur, (2) rendezvous
selection site is more complex, and (3) it's hard to think about.
APPENDIX
A system for Interprocess Communication in a Resource Sharing
Computer Network. Communications of the ACM, April, 1972.
Permission to reprint this paper was granted by permission of the
Association for Computing Machinery. [Omitted in republished version
of RFC 333.]
N.B. The ideas of section 4 of the following paper are in no way
critical to the ideas developed in section 3--DCW.
[ This RFC was put into machine readable form for entry ]
[ into the online RFC archives by Via Genie 3/00 ]
Bressler, et al. Experimentation [Page 26]
|