Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!mailrus!cornell!mak
From: mak@hymir.cs.cornell.edu (Mesaac Makpangou)
Newsgroups: comp.protocols.tcp-ip
Subject: Re: Building a reliable datagram protocol on top of UDP
Message-ID: <35461@cornell.UUCP>
Date: 22 Dec 89 19:21:11 GMT
References: <1486@wacsvax.OZ>
Sender: nobody@cornell.UUCP
Reply-To: mak@cs.cornell.edu (Mesaac Makpangou)
Organization: Cornell Univ. CS Dept, Ithaca NY
Lines: 118

In article <1486@wacsvax.OZ> jamesp@wacsvax.uwa.oz.OZ (James Pinakis) writes:

> I'm trying to write a protocol which delivers variable size packets
> reliably (i.e. in sequence, no dups, no dropped packets) using the
> Internet UDP.  I opted to use UDP since I wanted a single (server)
> process to be able to accept messages from any number of sites (clients),
> rather than (using the tcp-ip client/server model) a process having
> to accept a connection, then fork a process to talk on that connection.
> I would also prefer to only have one socket to listen on, rather than
> a pile of file descriptors to select on (since the number of clients
> is potentially large).

I implemented almost such a transport protocol at INRIA (France) for 
the SOS communication service. (SOS is an object-oriented distributed 
operating system developped at INRIA by the SOR group.)

To summarize, the SOS communication service is made of four layers:
	1) The network interface layer.
	2) The transport layer.
	3) The protocol objects layer.
	4) The application interface layer.
In the transport layer, I  implementrd
a reliable unicast and multicast datagram transport protocol.
The difference with what you want, is that this protocol doesn't enforce
the delivery in sequence of messages exchanged between protocol objects.
There are a lot of reasons of doing so. The main one is that,
not all application protocols (here encapsulated by what we call 
protocol objects) need this functionnality. So we made the
choice to provide such functionality at a higher level 
(i.e at the protocol object layer).

The protocol objects which want to enforce the sequencing
implement it by queueing messages arriving in an incorrect
order, and just waiting the arrival of the appropriate message.

> I'm currently implementing a sliding window protocol (Tanenbaum's
> protocol 6, actually) but this is getting nastily complicated.

To do this, I used some kind of sliding window too. The main point is
that I have a very large window. I managed to accept messages even
if they were not in sequence, but I ensure that every message
is delivered to its destinator(s) (i.e reliable datagram).

> It amounts to having to maintain a set of protocol state information
> for every client which establishes a "connection" to the server.
> This implies a reasonably large setting up operation every time
> a new client wants to start talking with the server.

In my implementation, I have also a set of protocol state.
I think however that its size is reasonable.
For my implementation, I assumed that the set of potential
clients and servers was known (this was realistic since this
was the set of sites runing our system).

> Basically, I'm wondering if anyone has experience/source code which
> they would like to share with me. 

I have the code, and an article and my Ph.D dissertation describing
this stuff. I will also continue to work on its improvement
sometimes by end february 1990. So I will be glad to share
my experience and my source with you.

> How efficient is this protocol likely to be? 

As far as the efficiency is concerned, the measures I did
year ago, tended to show that my protocol outperforms
tcp for messages of size range from 1024 bytes to 1500 bytes.
Below 1024 bytes, the tcp was better than my protocol.
The best explanation I have is that, UDP sends one
packet for every user message. I did not look closely to the
tcp code, but I suspect that small user messages could be sent
in a single inter-sites message.
For messages bigger than 1500 bytes, I did no measures
since my implementation assumes a maximum size of 1500
for all transport packet (the fragmentation is
implemented by the protocol object level).

> Would I be better off sticking with tcp-ip and
> accepting a limit to the number of client processes?

At the end of my implementation, I asked myself if
it was really necessary to do this, instead of using
tcp. I provide some answers in my thesis.
To summarize, I think that it is suitable for an
operating system to allow each application (or more precisely each
application protocol) to pay only for what it really needs.
I'm convince that enforcing the sequence (more generally the
delivery order: causal ordering, atomic ordering, fifo ordering, etc.),
and enforcing the fragmentation/reassemblage for examples, are not needed
by all application protocols. These functionalities should be 
better implemented by appropriate protocol objects.

So, in my case, I still believe it was necessary.
In your case however, it seems to me that your choice should be guided
by the importance of the limitation of the number of client processes
in your system.

References:
-----------

1) Protocoles de communication et Programmation par Objets: l'exemple de SOS.
	(Ph.D Thesis, Universite' Paris 6, France. February 1989.
	 Available as Rapport de Recherche INRIA.)

	This dissertation discusses extensively the structure and the
	implementation of the SOS communication service.
	Chapter 4 describes the implemtation of our reliable datagram protocol.
	Chapter 8 discusses the performance figure of this protocol and
	compares it with tcp and udp.

2) The SOS Object-Oriented Communication Service 
	(In procedings of ICCC89 Tel Aviv (Israel), October-November 89.)

I will be happy to send you a copy of both.
Also, the code is in C++, and I will check how we
can share this code once I go back at INRIA sometimes in February.

Mesaac