No title

From 489c54be1766844a2b4521bccdab99f85de0debe Mon Sep 17 00:00:00 2001 From: Alex AUVOLAT Date: Thu, 30 Oct 2014 15:38:13 +0100 Subject: This is VERSION 1. --- doc/spec-1.html | 1718 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1718 insertions(+) create mode 100644 doc/spec-1.html (limited to 'doc/spec-1.html') diff --git a/doc/spec-1.html b/doc/spec-1.html new file mode 100644 index 0000000..c9ee0df --- /dev/null +++ b/doc/spec-1.html @@ -0,0 +1,1718 @@ + + + + + No title + + + + + + + + +

+ + + +

The NARP protocol specification +

+ + + +

A Generic Recursive Communication Protocol for + Networked Applications

+ In this document we explain the purpose and provide a draft + specification for the NARP protocol, a general-purpose networking + protocol destined to be used in many layers of a new operating system + and networking system. +

1Introduction

+ We begin by remarking that a basic operation in all computer operation + processes consists in naming objects and providing acces to these named + objects. Here are a few examples of naming in real use cases: +

+
+ Naming of files on a local or distant file system +
+
+
+ Naming of devices in the /dev virtual filesystem on + Unix machines +
+
+
+ Naming of networked machines (with IP adresses and DNS records) +
+
+
+ Naming of internet ressources over protocols such as HTTP, IMAP, + IRC, specfic web services, … +
+

+ We propose here a novel architecture with the purpose of unifying all + the naming happening at all levels of the system, with two base concepts + : objects and service. +

+
+ objects are ressources that may implement different + semantics : bidirectionnal communication (such as sockets) ; + unidirectionnal communication (FIFO-like) ; file semantics ; etc. +
+
+
+ services are a way of naming objects, querying the + interfaces they implement, and multiplexing communications with them +
+

+ We suggest that a NARP service may be provided on any bidirectionnal + channel of communication supporting the (reliable) sending and recieving + of messages. In addition, NARP objects may implement such a send/recieve + interface ; therefore a NARP service can be channeled into an object. + Such a construction of using a NARP object to access a NARP service is a + fundamental operation that we call recursive multiplexing, or + just multiplexing. +

+ The NARP protocol is a client/server protocol meant to include a variety + of different operations that may or may not be implemented by a specific + NARP server. +

2High-level overview

2.1The basic operations on services and + objects

+ A NARP service is basically any object that implements the following + operations: +

+
+ query : get information on a ressource identified by name +
+
+
+ list : know the names of ressources presented by the + service (possibly in a specific sub-path) +
+
+
+ attach : get an object interface for accessing a ressource, + identified by name +
+

+ A NARP object is basically any object that implements the following + operations : +

+
+ send : send a message (an arbitrary byte string) to the + object +
+
+
+ recieve : recieve a message from the object (this may be + done asynchronously with handler functions) +
+
+
+ detach : delete object connection +
+

2.2The basics of the NARP protocol

+ Given any interface with send/recieve capabilities considered as an + assymetric (client/server) configuration, the following client messages + consitute the basics of the NARP protocol for providing a NARP service + on the interface: +

+
+ hello : initialize a connection, check version + information, … +
+
+
+ authenticate and appropriate response messages : use + credentials (user/password or access token) to gain acces to some + ressources provided by the server (the protocol is thus statefull) +
+
+
+ walk, list and appropriate response + messages : get information about the available ressources +
+
+
+ attach and appropriate response messages : give an + identifier (a descriptor) to a ressource in order to communicate + with it +
+
+
+ send and appropriate response messages : send a + message to an attached ressource, identified by its descriptor +
+
+
+ detach : close a descriptor and detach from a + ressource +
+
+
+ create, delete, rename, + link : requests the creation or modification of a + ressource in the namespace +
+

+ The server may also at any moment send a message, including: +

+
+ a response to a query +
+
+
+ recieve : a notification of a message sent from the + object to the client +
+
+
+ detached : the connection to the object has been + terminated by the object server +
+

2.3Recursion

+ If an object is a NARP server, the messages sent to it and recieved from + it are messages of the NARP protocol. Otherwise, they are arbitrary. +

2.4Reverse object

+ Some NARP servers may support reverse object serving: the client creates + an object on the server and handles all the requests arriving to this + object (therefore the initial NARP server only serves as a relay between + the new server and its clients +

+ 1. Research is to be done on shortcutting mechanisms in + specific situations where too many levels of recursion cause a + performance issue. +

+ + + ¹ + ). A client wishing to act as a reverse object server may use the + following commands: +

+
+ serve : listen for attach requests on a servable + (empty) object created in the server namespace (if authorized) +
+
+
+ accept and reject : accept (or + reject) an attach request to the object +
+
+
+ detach : close connection between object and client + (this is the same detach message as in standard communications) +
+
+
+ unserve : stop serving for the object. Attached + clients continue to be attached. +
+

+ The server may in turn send the following messages concerning the server + object: +

+
+ attach_request : a client is willing to attach to + the object. A descriptor is already associated to the connection to + be established, but the server may reject it. +
+

+ Once a client is attached to the object, a classical send/recieved + interface is provided. +

+ Typically, the protocol exchanged over the object is NARP protocol, + therefore enabling the reverse server to provide its own namespace and + other functionnality. +

2.5Specific object types and associated + messages

2.5.1Objects are sockets

+ Sockets are the basis of the NARP protocol : attaching to an objects + opens a socket connection to the process serving the object, and when + the connection is accepted, basic send/recieve functionnality is + provided. See also the reverse object protocol described in section 2.4. +

2.5.2File objects

+ Small files may implement the following interface: +

+
+ put : erase the whole file and put the transmitted + content +
+
+
+ get : retrieve the whole file content +
+

+ Big files may implement the following interface: +

+
+ write : write a portion of the file at a given + offset +
+
+
+ read : read a portion of the file at a given offset +
+

2.5.3User IO (terminals…)

+ Virtual terminals can be seen as objects implementing a simple + send/recieve semantic, where the data transmitted is unstructured (or + structured given a specific terminal data structure). More specific + interfaces can be defined for advanced terminals and GUIs. +

2.5.4Specific applications

+ Specific applications may define custom messages. Examples include: +

+
+ e-mail +
+
+
+ instant messaging +
+
+
+ collaborative editing of text-based documents +
+

+ and many other applications yet to be invented. +

2.6Big messages

+ The message size in the NARP protocol is limited to 64kb, and + recommended not to exceed 4kb+header (4kb is the size of a memory page + on many machines). Therefore a possibility would be for the NARP + protocol to include a way to transmit big messages by fragmenting them + into small messages. Optionnal error correction may be included. This + can be useful for example when using put or get + on large files, or reads and writes of + big file portions. The recieving of a large fragmented message may have + a specific implementation allowing the reciever to work with the partial + data as soon as it starts arriving and not having to wait for the whole + message to be transmitted and buffered. Research is yet to be done on + this specific subject. +

2.7Permissions

+ For each attached client the server may keep track of associated + permissions, and accept or reject requests according to those + permissions. The client may use an authentication command to gain + supplementary privileges on the server's ressources. The client may + request a token to delegate it's privileges on a given object to another + client. Advanced right management functionnalities are to be discussed. +

2.8Reliability concerns

+ The NARP protocol relies on the fact that when transmitting a message, + the other end will recieve it. It is nevertheless recommended that NARP + implementations support the repeating of messages if an expected + acknowlegment has not arrived after a given delay. +

2.9Example NARP servers

2.9.1Virtual NARP server (i.e. NARP + router)

+ This server implements a namespace where any client may create an empty + object and serve connections to it. Additionnaly, the server may + implement the possibility to create virtual files, virtual directories, + FIFO queues, etc. +

+ This server may be connected to other virtual NARP servers in order to + provide a global namespace accessible to all. Each virtual NARP server + acts as an endpoint into the network and may have functionnality for + routing the communications to objects to the clients that serve them. +

2.9.2NARP file server

+ This server simply implements access to a filesystem : listed ressources + are the same as the files present in a served directory, each of these + implements the filing protocol (served directly by the file server), and + the creation of files/directories may also be implemented. +

2.9.3NARP terminal/GUI server

+ Clients may create objects on the server ; each of these objects + correspond to a GUI window. Two interfaces may be implemented : text IO + (terminal) and graphical interaction. Advanced terminal interaction + features may be implemented at the protocol level, such as + auto-completion of commands or of text being edited… +

+ Suggestion for a third kind of window : the data sent by the client + corresponds to a description of the scene in a given markup language and + the server does the rendering. The client can also subscribed to events + such as clicking on an item or entering text. This possibility is to be + explored. +

2.9.4NARP e-mail and newsgroup server

+ Several features to be implemented: +

+
+ user login and private user mailboxes +
+
+
+ bridge to standard SMTP/POP3/IMAP services +
+
+
+ private threads of conversation with access rights (the users don't + each have a copy of the thread) +
+
+
+ synchronization between many servers +
+
+
+ public discussion forums +
+

2.9.5NARP chat server

+
+ user login and status notification +
+
+
+ online and offline private messaging +
+
+
+ public chat rooms, chat room logging independently of user being + online or offline +
+
+
+ bridging and synchronization between many servers +
+

2.9.6NARP applicative server

+ TODO… +

3Specifics of the NARP protocol

3.1Protocol description format

+ A protocol message is given in the following form: +

+ + + + + + + + + + + + +

element type	element type	…	element type
element description	element description	…	element description

+ The following element types apply: +

+
+ int16, int32, int64 : 16-bit, 32-bit or 64-bit little-endian + integers +
+
+
+ str : a string, prefixed by a 16-bit length header +
+
+
+ arr(T) : an array of T's (where T + is another element type), prefixed by a 16-bit length header +
+
+
+ * (for the last element) : consider all the rest of the message as a + byte string +
+

3.2Basic message format

+ The basic format of a message is : +

+ + + + + + + + + + +

int16	int16	*
message size	message type	payload

+ We will abbreviate by “header” the first 32 bits (4 bytes) + of the message. The list of message types is given in section 3.10.1. +

+ Messages for communication with an attached ressource will have the + following format : +

+ + + + + + + + + + + + +

int16	int16	int32	*
message size	message type	ressource descriptor (handle)	payload

+ Many client messages awating a response will have a message ID included + ; this message ID is an arbitrary number generated by the client and + used by the server when giving its response. The header then looks like + this: +

+ + + + + + + + + + + + +

int16	int16	int32	*
message size	message type	message ID	payload

3.3Message list for core NARP protocol

+ Client messages have an up arrow (↑) next to their name, + while server messages have a down arrow (↓). +

+ The core NARP protocol is meant for small size and rapidity (so that + many layers can be encapsulated with minimal overhead), therefore no + acknowlegment is to be sent for recursive send/recieve messages. Other + messages usually imply some kind of action or getting of information, + therefore an acknowlegment or an error is usually sent as a response. +

Hello`↑↓`

+ + + + + + + + + + +
int32 arr(int32)
header version list of needed/provided interfaces
+ +

+ When a NARP connection is established, the client is always the + first to send a Hello message. The object may then + respond either with a Hello message indicating that + the requested interfaces can be provided, or with an + Error message. The two common error causes are + interface not implemented and incompatible + versions. +

+ For interface numbers : see table in section 3.10.3. +

Error`↓`

+ Generic error response message for any operation. +

+ + + + + + + + + + + + +

	int32	int32	str
header	request ID	error ID	error string

+ Common error IDs are specified in section 3.10.2. +

Ack`↓`

+ + + + + + + + +

	int32
header	request ID

+ +

+ Generic acknowlegment message for commands that require it. An + acknowlege implies the command has been sucessfully executed + (otherwise an error message is sent). +

Stat`↑`

+ + + + + + + + + + +

	int32	str
header	request ID	filename

+ +

+ The request ID is an ID decided by the client so that it can + identify the answer. +

StatR`↓`

Response to the + Stat message. +

+ + + + + + + + + + +

	int32	arr(int32)
header	request ID	implemented interface

+ Common interface numbers are to be found in section 3.10.3. +

+ If a Stat query on an object gives a certain list + of interfaces, then when connecting to the object at least all these + interfaces must be included in the server's Hello + message as supported interfaces. +

+ Note that some interface numbers correspond to actions that can be + done on the object from the connection where the object exists (e.g. + : symbolic link, directory), and others correspond to actions that + can be performed after attaching to the object (e.g. file, terminal, + …) +

List`↑`

+ + + + + + + + + + + + + + +

	int32	int32	int32	str
header	request ID	first entry number	number of entries requested	base path string

ListR`↓`

Response to the + List message. +

+ One message is passed for each entry in the requested range: +

+ + + + + + + + + + + + +

	int32	int32	str
header	request ID	entry number	entry name

+ After the directory has finished being enumerated, a supplementary + entry is given with entry number the last valid entry number plus + one and an empty entry name. This supplementary entry is only given + if its (ficious) entry number is included in the range requested by + the client. +

+ Possible extension : combine List and Stat so that when the answer to + List is given, information is also given on the object's implemented + interfaces. +

Attach`↑`

+ + + + + + + + + + +

	int32	str
header	request ID	filename

Attached`↓`

Response to the + Attach command. +

+ + + + + + + + + + +

	int32	int32
header	request ID	handle

+ +

+ (the handle, ie the ressource descriptor, is attributed by the + server) +

Send`↑`

+ + + + + + + + + + +

	int32	*
header	handle	payload

+ +

+ This message does not expect a response. +

Recieve`↓`

+ Spontaneous server message indicating some data is sent by an + attached ressource. This message does not expect a response. +

+ +

+ + + + + + + + + + +

	int32	*
header	handle	payload

Detach`↑`

+ + + + + + + + +

	int32
header	handle

+ +

+ This message does not expect a response. +

Detached`↓`

+ Spontaneous server message indicating the object has been detached. +

+ +

+ + + + + + + + +

	int32
header	handle

Create`↑`

+ + + + + + + + + + + + +

	int32	arr(int32)	str
header	request ID	needed interfaces	path

+ +

+ A create request is accompanied with a list of needed interfaces + that direct the server into creating the corresponding type of + object (e.g. an empty object to be served, a directory, a file, + …) +

Created`↓`

Response to the + Create command. +

+ + + + + + + + + + +

	int32	arr(int32)
header	request ID	implemented interfaces

+ +

+ Signals that the object has been created, and has corresponding + interfaces associated to it. +

Delete`↑`

+ + + + + + + + + + +

	int32	str
header	request ID	path

+ +

+ This message expects a standard Ack response + message. +

Link`↑`

+ + + + + + + + + + + + +

	int32	str	str
header	request ID	destination path	link path

+ This message expects a standard Ack response + message. +

+ Semantics of the link object: +

+
+ attaching or serving on this objects corresponds to resolving + the linked path and attaching/serving on the linked object +
+
+
+ stating the link will stat the linked object and add as an + implemented interface the “this is a symlink” + information +
+
+
+ directory listings follow links +
+
+
+ deleting the link will not delete the original file but only the + link +
+

ReadLink`↑`

+ + + + + + + + + + +

	int32	str
header	request ID	path

ReadLinkR`↓`

Response to the + ReadLink message. +

+ + + + + + + + + + +

	int32	str
header	request ID	link description

+ +

+ This will only return the first level of linking, ie the link data + directly associated to the link object. +

Rename`↑`

+ + + + + + + + + + + + +

	int32	str	str
header	request ID	original path	new path

+ +

+ This message expects a standard Ack response + message. +

Serve`↑`

+ + + + + + + + + + + + +

	int32	str	array(int32)
header	request ID	path	announced interfaces

+ This message is a request for the client to be a reverse server to + an object. The response message to this message is an + Attached message. The handle attributed to the + served object is known as the server handle and is used in + the Incoming and Detach messages. +

+ To stop serving an object, the client simply sends a + Detach command on the server handle. The semantics + is that all connections that have been openned through the + reverse-served object are preserved when the object stops being + served, and an individual Detach message must be + sent to all of them if we want to close them. +

+ The announced interfaces serves to answer + Stat messages on the object while we are serving + it. +

Incoming`↓`

+ + + + + + + + + + +

	int32	int32
header	server handle	client hande

+ +

+ This message is sent by the server when another client wishes to + attach to an object reverse-served by this client. The server handle + is the one given as a response to the Serve + message. The client handle is a handle associated to the connection. + The reverse server may reject the connection by issuing a + Detach command on the client handle, or may accept + it using the Accept message given below. +

Accept`↑`

+ + + + + + + + +

	int32
header	client handle

+ +

+ Once a connection has been accepted, the reverse server may at any + moment close it by sending a Detach command on the + corresponding client handle. +

3.4Big message protocol

+ To be defined. Is it really usefull? What role exactly does it have? Can + it implement repetition in the case where the message hasn't been + acknowledge? … +

+ Reserved message IDs : [20,30) and [10020,10030). +

3.5Authentification and rights managment + commands

Authenticate`↑`

+ + + + + + + + + + + + +

	int32	int32	*
header	message ID	authentification method	authentification data

+ Used to gain access using credentials (user/password, token, + …). Response messages are standard Ack on + success or Error on failure. Autentification + methods include : +

+
+ 1 : user + password +
+
+
+ 2 : token +
+

NewToken`↑`

+ + + + + + + + + + +

	int32	str
header	message ID	path

+ +

+ Requests the server to create an authentication token for accessing + a given object with the privileges of the connected client. Once the + token has been returned, it may be transmitted to another client so + that that client will use it to gain same access to the object. +

NewTokenR`↓`

Response to the + NewToken message. +

+ + + + + + + + + + +

	int32	str
header	message ID	token

+ TODO : request account creation, manage user groups and ACLs, … +

3.6File protocol

+ Client messages [50,100) ; server messages [10050,10100). TODO +

3.7UI protocols

+ Client messages [100,200) and server messages [10100,10200). +

3.7.1Terminal protocol

+ TODO +

3.7.2Graphical user interface protocol

+ TODO +

3.8Communication protocols

+ Client messages [200,300) and server messages [10200,10300). +

3.8.1Email and newsgroups protocol

+ Client messages [200,220), server messages + [10200⁣,10220). +

3.8.2Instant messaging protocol

+ Client messages [220,250), server messages + [10220⁣,10250). +

3.9Other protocols

+ Protocols not discussed in this specification may use client messages + with type IDs [1000,10000) and server messages [11000,20000). Overlaps + between several protocols are allowed : the information about + implemented interfaces for an object is meant to disambiguate such + situations. +

3.10Table of IDs

+ The tables presented in this section give the number associated to the + message types. These tables are the reference on the subject ; any + information found somewhere else is wrong if it is not the same as found + here. This is for protocol version 1. +

3.10.1Message types

Base protocol

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

message	`↑` id	`↓` id	message	`↑` id	`↓` id
Hello	0	10000	Stat / StatR	10	10010
Error		10001	List / ListR	11	10011
Ack		10002	Create / Created	12	10012
			Delete	13
Attach / Attached	5	10005	Rename	14
Send / Recieve	6	10006	Link	15
Detach / Detached	7	10007	ReadLink / + ReadLinkR	16	10016
Serve	8
Incoming		10008
Accept	9

Authentication & privileges

+ + + + + + + + + + + + + + +

message	`↑` id	`↓` id
Authenticate	30
NewToken / + NewTokenR	31	10031

3.10.2Error messages

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

id	cause
1	Incompatible versions
2	Command/interface not implemented
3	Invalid request (e.g. : out of bounds)
4	Invalid handle
5	Attach request rejected
6	Action impossible because object is in use (cannot + delete, …)
7	No such object (invalid path)
8	Could not resolve link
9	Incorrect credentials
10	Unauthorized

3.10.3Object interfaces

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

id	name	must implement messages
0	servable	Serve, Accept, + Incoming
1	non-NARP inside	once attached, inside data is arbitrary
2	NARP service	once attached, inside data is a NARP service (ie has + objects, …)
3	enumerable	List, ListR
4	is symlink	ReadLink, + ReadLinkR
10	file	once attached, file semantics
11	terminal	once attached, terminal semantics
12	graphics window	once attached, GUI semantics

Servable

This interface specifies that the object is + currently an empty object waiting for someone to issue a + Serve command on it, providing it with an + implementation of some interfaces. +

non-NARP inside

This interfaces indicates that once + attached to the object, the messages sent/recieved to it are not + supposed to be NARP format but any arbitrary format. If this interface + is not specified, then it is expected that the messages transmitted will + follow the general NARP protocol (message format, standard + hello/ack/error messages). +

NARP service

This interface indicates that once + attached to the object, one can have access to a new NARP namespace + where at least the following operations are supported : + Stat, Attach, Send, + Recieve, Detach. Additionnal messages + may or may not be supported. +

4Architecture of a NARP implementation in + OCaml or Haskell

+ An asynchronous implementation can be easily programmed in functionnal + languages such as OCaml or Haskell, using closures as continuations for + what to do when a (response) message arrives. +

+ TODO +

5Using NARP to design an Operating System

+ When designing the NARP protocol, we had in mind that it would be + possible to use it in a new operating system design at many levels : + access to devices, process management, memory management, filesystems, + IPC, GUI, … +

+ Kernel helpers could be developped so that a part of the NARP + multiplexing and demultiplexing takes place in kernel land, before + messages are passed to userspace. This would allow the simplification of + useless mux-demux chains taking place on the same machine. Another + possible helper would be to map a virtual memory region to a NARP + ressource implementing a standard filing protocol, much as memory mapped + files in standard OSes (only this would work with arbitrary ressources). +

+ TODO +

+ + \ No newline at end of file -- cgit v1.2.3

1Introduction

2High-level overview

2.1The basic operations on services and + objects

2.2The basics of the NARP protocol

2.3Recursion

2.4Reverse object

2.5Specific object types and associated + messages

2.5.1Objects are sockets

2.5.2File objects

2.5.3User IO (terminals…)

2.5.4Specific applications

2.6Big messages

2.7Permissions

2.8Reliability concerns

2.9Example NARP servers

2.9.1Virtual NARP server (i.e. NARP + router)

2.9.2NARP file server

2.9.3NARP terminal/GUI server

2.9.4NARP e-mail and newsgroup server

2.9.5NARP chat server

2.9.6NARP applicative server

3Specifics of the NARP protocol

3.1Protocol description format

3.2Basic message format

3.3Message list for core NARP protocol

Hello↑↓

Error↓

Ack↓

Stat↑

StatR↓

List↑

ListR↓

Attach↑

Attached↓

Send↑

Recieve↓

Detach↑

Detached↓

Create↑

Created↓

Delete↑

Link↑

ReadLink↑

ReadLinkR↓

Rename↑

Serve↑

Incoming↓

Accept↑

3.4Big message protocol

3.5Authentification and rights managment + commands

Authenticate↑

NewToken↑

NewTokenR↓

3.6File protocol

3.7UI protocols

3.7.1Terminal protocol

3.7.2Graphical user interface protocol

3.8Communication protocols

3.8.1Email and newsgroups protocol

3.8.2Instant messaging protocol

3.9Other protocols

3.10Table of IDs

3.10.1Message types

Base protocol

Authentication & privileges

3.10.2Error messages

3.10.3Object interfaces

Servable

non-NARP inside

NARP service

4Architecture of a NARP implementation in + OCaml or Haskell

5Using NARP to design an Operating System

Hello`↑↓`

Error`↓`

Ack`↓`

Stat`↑`

StatR`↓`

List`↑`

ListR`↓`

Attach`↑`

Attached`↓`

Send`↑`

Recieve`↓`

Detach`↑`

Detached`↓`

Create`↑`

Created`↓`

Delete`↑`

Link`↑`

ReadLink`↑`

ReadLinkR`↓`

Rename`↑`

Serve`↑`

Incoming`↓`

Accept`↑`

Authenticate`↑`

NewToken`↑`

NewTokenR`↓`