As per Relevance of the word transport, we have this rfc below:
Network Working Group T.
Request for Comments: 1693 P.
Category: Experimental P.
University of
November 1994
An Extension to TCP : Partial Order
Status of This
This memo defines an Experimental Protocol for the
community. This memo does not specify an Internet standard of
kind. Discussion and suggestions for improvement are requested
Distribution of this memo is
IESG Note
Note that the work contained in this memo does not describe
Internet standard. The Transport AD and Transport Directorate do
recommend the implementation of the TCP modifications described
However, outside the context of TCP, we find that the memo offers
useful analysis of how misordered and incomplete data may be handled
See, for example, the discussion of Application Layer Framing by D
Clark and D. Tennenhouse in, "Architectural Considerations for a
Generation of Protocols", SIGCOM 90 Proceedings, ACM, September 1990.
This RFC introduces a new transport mechanism for TCP based
partial ordering. The aim is to present the concepts of
ordering and promote discussions on its usefulness in
communications. Distribution of this memo is unlimited
A service which allows partial order delivery and partial
is one which requires some, but not all objects to be received in
order transmitted while also allowing objects to be
unreliably (i.e., some may be lost).
The realization of such a service requires, (1) communication and/
negotiation of what constitutes a valid ordering and/or loss-level
and (2) an algorithm which enables the receiver to ascertain
deliverability of objects as they arrive. These issues are
here - both conceptually and formally - summarizing the results
research and initial implementation efforts
Connolly, Amer & Conrad [Page 1]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
The authors envision the use of a partial order service within
connection-oriented, transport protocol such as TCP providing
further level of granularity to the transport user in terms of
type and quality of offered service. This RFC focuses
on extending TCP to provide partial order connections
The idea of a partial order service is not limited to TCP. It may
considered a useful option for any transport protocol and
encourage researchers and practitioners to investigate further
most effective uses for partial ordering whether in a next-
TCP, or another general purpose protocol such as XTP, or
within a "special purpose" protocol tailored to a
application and network profile
Finally, while the crux of this RFC relates to and introduces a
way of considering object ordering, a number of other
transport mechanisms are also seen in a new light - among these
reliability, window management and data acknowledgments
Keywords: partial order, quality of service, reliability, multimedia
client/server database, Windows, transport
Table of
1. Introduction and motivation .................................. 3
2. Partial Order Delivery ....................................... 4
2.1 Example 1: Remote Database .................................. 4
2.2 Example 2: Multimedia ....................................... 8
2.3 Example 3: Windows Screen Refresh ........................... 9
2.4 Potential Savings ........................................... 10
3. Reliability vs. Order ........................................ 12
3.1 Reliability Classes ......................................... 13
4. Partial Order Connection ..................................... 15
4.1 Connection Establishment .................................... 16
4.2 Data Transmission ........................................... 19
4.2.1 Sender .................................................... 22
4.2.2 Receiver .................................................. 25
5. Quantifying and Comparing Partial Order Services ............. 30
6. Future Direction ............................................. 31
7. Summary ...................................................... 32
8. References ................................................... 34
Security Considerations ......................................... 35
Authors' Addresses .............................................. 36
Connolly, Amer & Conrad [Page 2]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
1. Introduction and
Current applications that need to communicate objects (i.e., octets
packets, frames, protocol data units) usually choose between a
ordered service such as that currently provided by TCP and one
does not guarantee any ordering such as that provided by UDP.
similar "all-or-nothing" choice is made for object reliability -
reliable connections which guarantee all objects will be
verses unreliable data transport which makes no guarantee. What
more appropriate for some applications is a partial order and/
partial reliability service where a subset of objects
communicated must arrive in the order transmitted, yet some
may arrive in a different order, and some (well specified subset)
the objects may not arrive at all
One motivating application for a partial order service is
emerging area of multimedia communications. Multimedia traffic
often characterized either by periodic, synchronized parallel
of information (e.g., combined audio-video), or by structured
streams (e.g., displays of multiple overlapping and
windows). These applications have a high degree of tolerance
less-than-fully-ordered data transport as well as data loss.
they are ideal candidates for using a partial order,
reliability service. In general, any application which
parallel and/or independent data structures may potentially be
to profit from a partial order service
A second application that could benefit from a partial order
involves remote or distributed databases. Imagine the case where
database user transmitting queries to a remote server expects
(or records) to be returned in some order, although not
total order. For example a user writing an SQL data query
specify this with the "order by" clause. There exist today a
number of commercial implementations of distributed databases
utilize - and thus are penalized by - an ordered delivery service
Currently these applications must use and pay for a
ordered/fully reliable service even though they do not need it.
introduction of partial services allows applications to lower
demanded quality of service (QOS) of the communication assuming
such a service is more efficient and less costly. In effect,
partial order extends the service level from two extremes -
and unordered - to a range of discreet values encompassing both
the extremes and all possible partial orderings in between.
similar phenomenon is demonstrated in the area of reliability
Connolly, Amer & Conrad [Page 3]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
It is worth mentioning that a TCP implementation providing a
order service, as described here, would be able to communicate with
non-partial order implementation simply by recognizing this fact
connection establishment - hence this extension is
compatible with earlier versions of TCP. Furthermore, it
conceivable for a host to support the sending-half (or receiving
half) of a partial order connection alone to reduce the size of
TCP as well as the effort involved in the implementation.
"levels of conformance" have been proposed in other
extensions such as [Dee89] involving IP multicasting
This RFC proceeds as follows. The principles of partial
delivery, published in [ACCD93a], are presented in Section 2.
notion of partial reliability, published in [ACCD93b], is
in Section 3 followed by an explanation of "reliability classes".
Then, the practical issues involved with setting up and maintaining
Partial Order Connection (POC) within a TCP framework are
in Section 4 looking first at connection establishment, and
discussing the sender's role and the receiver's role. Section 5
provides insights into the expected performance improvements of
partial order service over an ordered service and Section 6
some future directions. Concluding remarks are given in Section 7.
2. Partial Order
Partial order services are needed and can be employed as soon as
complete ordering is not mandatory. When two objects can
delivered in either order, there is no need to use an ordered
that must delay delivery of the second one transmitted until
first arrives as the following examples demonstrate
2.1 Example 1: Remote
Simpson's Sporting Goods (SSG) has recently installed a state-of
the-art enterprise-wide network. Their first "network application
is a client/server SQL database with the following four records
numbered {1 2 3 4} for convenience
SALESPERSON LOCATION CHARGES
------------- ----------------- --------- -----------------
1 Anderson Atlanta, GA $4,200 Camping
2 Baker Boston, MA $849 Camping
3 Crowell Boston, MA $9,500
4 Dykstra Wash., DC $1,000
SSG employees running the client-side of the application can
the database server from any location in the enterprise net
standard SQL commands and the results will be displayed on
Connolly, Amer & Conrad [Page 4]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
screen. From the employee's perspective, the network is
reliable and delivers data (records) in an order that conforms
their SQL request. In reality though, it is the transport
protocol which provides the reliability and order on top of
unreliable network layer - one which introduces loss, duplication
and disorder
Consider the four cases in Figure 1 - in the first query (1.a),
ordered by SALESPERSON, the records have only one acceptable order
the destination, 1,2,3,4. This is evident due to the fact that
are four distinct salespersons. If record 2 is received
record 1 due to a network loss during transmission, the
service can not deliver it and must therefore buffer it until
1 arrives. An ordered service, also referred to as a virtual
or FIFO channel, provides the desired level of service in this case
At the other extreme, an unordered service is motivated in Figure 1.
where the employee has implicitly specified that any ordering
valid simply by omitting the "order by" clause. Here any of 4! = 24
delivery orderings would satisfy the application, or from
transport layer's point of view, all records are
deliverable as soon as they arrive from the network. No record
to buffered should it arrive out of sequential order. As notation, 4
ordered objects are written 1;2;3;4 and 4 unordered objects
written using a parallel operator: 1||2||3||4.
Figures 1.b and 1.c demonstrate two possible partial orders
permit 2 and 4 orderings respectively at the destination. Using
notation just described, the valid orderings for the query in 1.b
specified as 1;(2||3);4, which is to say that record 1 must
delivered first followed by record 2 and 3 in either order
by record 4. Likewise, the ordering for 1.c is (1||2);(3||4).
these two cases, an ordered service is too strict and an
service is not strict enough
Connolly, Amer & Conrad [Page 5]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
+-----------------------------------------------------------------+
| SELECT SALESPERSON, LOCATION, CHARGES, DESCRIPTION |
| FROM BILLING_TABLE |
| |
| SALESPERSON LOCATION CHARGES DESCRIPTION |
| ------------- ----------------- --------- --------------- |
| 1 Anderson Atlanta, GA $4,200 Camping Gear |
| 2 Baker Boston, MA $849 Camping Gear |
| 3 Crowell Boston, MA $9,500 Sportswear |
| 4 Dykstra Wash., DC $1,000 Sportswear |
+=================================================================+
|a - ORDER BY SALESPERSON |
| |
| 1,2,3,4 1,2,3,4 |
| |
| Sender -----------> NETWORK --------------> Receiver |
| (1 valid ordering) |
+-----------------------------------------------------------------+
|b - ORDER BY LOCATION |
| 1,2,3,4 |
| 1,2,3,4 1,3,2,4 |
| |
| Sender -----------> NETWORK --------------> Receiver |
| (2 valid orderings) |
+-----------------------------------------------------------------+
|c - ORDER BY DESCRIPTION |
| 1,2,3,4 |
| 2,1,3,4 |
| 1,2,3,4 1,2,4,3 |
| 2,1,4,3 |
| |
| Sender -----------> NETWORK --------------> Receiver |
| (4 valid orderings) |
+-----------------------------------------------------------------+
|d - (no order by clause) |
| 1,2,3,4 |
| 1,2,4,3 |
| 1,2,3,4 ... |
| 4,3,2,1 |
| |
| Sender -----------> NETWORK --------------> Receiver |
| (4!=24 valid orderings) |
+-----------------------------------------------------------------+
Figure 1: Ordered vs. Partial Ordered vs. Unordered
It is vital for the transport layer to recognize the
requirements of the application and to ensure that these are met
However, there is no inherent need to exceed these requirements;
Connolly, Amer & Conrad [Page 6]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
the contrary, by exceeding these requirements unecessary
are consumed. This example application requires a
connection - all records must eventually be delivered - but has
flexibility when it comes to record ordering
In this example, each query has a different partial order. In total
there exist 16 different partial orders for the desired 4 records
For an arbitrary number of objects N, there exist many
partial orders each of which accepts some number of valid
between 1 and N! (which correspond to the ordered and
cases respectively). For some classes of partial orders, the
of valid orderings can be calculated easily, for others
calculation is intractable. An in-depth discussion on
and comparing the number of orderings for a given partial order
be found in [ACCD93a].
Connolly, Amer & Conrad [Page 7]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
2.2 Example 2:
A second example application that motivates a partial order
is a multimedia broadcast involving video, audio and text components
Consider an extended presentation of the evening news - extended
include two distinct audio channels, a text subtitle and a closed
captioned sign language video for the hearing impaired, in
to the normal video signal, as modeled by the following diagram
(left audio) (right audio
+------+ +------+
| ++++ | | ++++ |
| ++++ | | ++++ |
+------+ +------+
===================================================
I +---------------+
I | |
I | (hand signs) |
I | |
I +---------------+
I
I
I (Main Video)
I
I
I
I
I +------------------------------------------+
I | (text subtitle) |
I +------------------------------------------+
I
===================================================
Figure 2: Multimedia broadcast
The multimedia signals have differing characteristics. The main
signal may consist of full image graphics at a rate of 30 images/
while the video of hand signs requires a lower quality, say 10
images/sec. Assume the audio signals are each divided into 60
fragments/sec and the text object each second consists of either (1)
new text, (2) a command to keep the previous second of text, or (3)
command for no subtitle
During a one-second interval of the broadcast, a sender transmits 30
full-motion video images, 10 closed-captioned hand sign images, 60
packets of a digitized audio signal for each of the audio streams
a single text packet. The following diagram then might represent
characteristics of the multimedia presentation in terms of the
types, the number of each, and their ordering. Objects connected by
Connolly, Amer & Conrad [Page 8]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
horizontal line must be received in order, while those in
have no inherent ordering requirement
+----------------------------------------------------------------------+
| |
| |-o-|-o-|-o-|-o-|-o-|-o-|-o-|-o-|-o-...-o-|-o-|-o-| right audio |
| | | | | | | | | | | | | (60/sec) |
| | | | | | | | | | | | | |
| |-o-|-o-|-o-|-o-|-o-|-o-|-o-|-o-|-o-...-o-|-o-|-o-| left audio |
| | | | | | | | (60/sec) |
| | | | | | | | |
| |---o---|---o---|---o---|---o---|---...---|---o---| normal video |
| | | | (30/sec) |
| | | | |
| |-----------o-----------|--------o--...--------o--| hand signs |
| | | (10/sec) |
| | | |
| |-----------------------------o-----...-----------| text |
| | | (1/sec) |
| |
+----------------------------------------------------------------------+
Figure 3: Object ordering in multimedia
Of particular interest to our discussion of partial ordering is
fact that, while objects of a given media type generally must
received in order, there exists flexibility between the
"streams" of multimedia data (where a "stream" represents
sequence of objects for a specific media type). Another
characteristic of this example is the repeating nature of the
orderings. Figure 3 represents a single, one-second, partial
snapshot in a stream of possibly thousands of repeating
periods of communication
It is assumed that further synchronization concerns in presenting
objects are addressed by a service provided on top of the
partial order service. Temporal ordering for synchronized
is considered, for example, in [AH91, HKN91].
2.3 Example 3: Windows Screen
A third example to motivate a partial order service
refreshing a workstation screen/display containing multiple
from a remote source. In this case, objects (icons, still or
images) that do not overlap have a "parallel" relationship (i.e.,
their order of refreshing is independent) while overlapping
objects have a "sequential" relationship and should be delivered
order. Therefore, the way in which the windows overlap induces
partial order
Connolly, Amer & Conrad [Page 9]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
Consider the two cases in Figure 4. A sender wishes to refresh
remote display that contains four active windows (objects) named {1 2
3 4}. Assume the windows are transmitted in numerical order and
receiving application refreshes windows as soon as the
service delivers them. If the windows are configured as in
4a, then there exist two different orderings for redisplay,
1,2,3,4 or 1,3,2,4. If window 2 is received before window 1,
transport service cannot deliver it or an incorrect image will
displayed. In Figure 4b, the structure of the windows results in
possible orderings - 1,2,3,4 or 1,3,2,4 or 1,3,4,2 or 3,4,1,2
3,1,4,2 or 3,1,2,4.
+================================+============================+
|a +-----------+ |b +----------+ |
| | 1 | | | 1 | |
| | | | | +----------+ |
| +---------+ +----------+ | +-----| 2 | |
| | 2 |----| 3 | | | | |
| | +-----------+ | | +----------+ |
| | | 4 | | | +----------+ |
| +-----| |-------+ | | 3 | |
| | | | | +----------+ |
| +-----------+ | +------| 4 | |
| | | | |
| | +----------+ |
| | |
| 1;(2||3);4 | (1;2)||(3;4) |
+================================+============================+
Figure 4: Window screen
2.4 Potential
In each of these examples, the valid orderings are strictly
upon, and must be specified by the application. Intuitively, as
number of acceptable orderings increases, the amount of
utilized by a partial order transport service, in terms of
and retransmissions, should decrease as compared to a fully
transport service thus also decreasing the overall cost of
connection. Just how much lower will depend largely upon
flexibility of the application and the quality of the
network
As an indication of the potential for improved service, let
briefly look at the case where a database has the following 14
records
Connolly, Amer & Conrad [Page 10]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
SALESPERSON LOCATION CHARGES
------------- ----------------- --------- ---------------
1 Anderson Washington $4,200 Camping
2 Anderson Philadelphia $2,000 Golf
3 Anderson Boston $450 Bowling
4 Baker Boston $849
5 Baker Washington $3,100
6 Baker Washington $2000 Camping
7 Baker Atlanta $290 Baseball
8 Baker Boston $1,500
9 Crowell Boston $9,500 Camping
10 Crowell Philadelphia $6,000 Exercise
11 Crowell New York $1,500
12 Dykstra Atlanta $1,000
13 Dykstra Dallas $15,000 Rodeo
14 Dykstra Miami $3,200 Golf
Using formulas derived in [ACCD93a] one may calculate the
number of valid orderings for any partial order that can
represented in the notation mentioned previously. For the case
a user specifies "ORDER BY SALESPERSON", the partial order above
be expressed as
(1||2||3);(4||5||6||7||8);(9||10||11);(12||13||14)
Of the 14!=87,178,291,200 total possible combinations, there
25,920 valid orderings at the destination. A service that
deliver the records in any of these 25,920 orderings has a great
more flexibility than in the ordered case where there is only 1
order for 14 objects. It is interesting to consider the
possibility of hundreds or even thousands of objects and
potential savings in communication costs
In all cases, the underlying network is assumed to be unreliable
may thus introduce loss, duplication, and disorder. It makes
sense to put a partial order service on top of a reliable network
While the exact amount of unreliability in a network may vary and
not always well understood, initial experimental research
that real world networks, for example the service provided by
Internet's IP level, "yield high losses, duplicates and
of packets" [AS93,BCP93]. The authors plan to conduct
experimentation into measuring Internet network unreliability.
information would say a great deal about the practical merit of
partial order service
Connolly, Amer & Conrad [Page 11]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
3. Reliability vs.
While TCP avoids the loss of even a single object, in fact for
applications, there exists a genuine ability to tolerate loss
Losing one frame per second in a 30 frame per second video or
a segment of its accompanying audio channel is usually not a problem
Bearing this in mind, it is of value to consider a quality of
that combines a partial order with a level of tolerated loss (
reliability). Traditionally there exist 4 services: reliable
ordered, reliable-unordered, unreliable-ordered, and unreliable
unordered. See Figure 5. Reliable-ordered service (denoted by
single point) represents the case where all objects are delivered
the order transmitted. File transfer is an example
requiring such a service
reliable-ordered reliable-
| |
| |
v
zero loss-->*---------------------------------*
min loss-->|<-- |<--
. | |
. |<-- |<--
| |
|<-- unreliable- |<-- unreliable
RELIABILITY | ordered |
|<-- |<--
| |
|<-- |<--
max loss-->| |
+-+--+--+--+--+--+--+--+--+--+--+-+
ordered partial ordered
Figure 5: Quality Of Service: Reliability vs. Order -
Traditional Service
In a reliable-unordered service (also a single point), all
must be delivered, but not necessarily according to the
transmitted; in fact, any order will suffice. Some
processing applications such as credit card verification require
a service
Unreliable-ordered service allows some objects to be lost.
that are delivered, however, must arrive in relative order (
"unreliable" service does not necessarily lose objects; rather,
may do so without failing to provide its advertised quality
Connolly, Amer & Conrad [Page 12]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
service; e.g., the postal system provides an unreliable service).
Since there are varying degrees of unreliability, this service
represented by a set of points in Figure 5. An unreliable-
service is applicable to packet-voice or
applications
Finally unreliable-unordered service allows objects to be lost
delivered in any order. This is the kind of service used for
e-mail (without acknowledgment receipts) and electronic
or junk e-mail
As mentioned previously, the concept of a partial order expands
order dimension from the two extremes of ordered and unordered to
range of discrete possibilities as depicted in Figure 6.
Additionally, as will be discussed presently, the notion
reliability is extended to allow for varying degrees of
on a per-object basis providing even greater flexibility and
resource utilization
reliable-
| | | | | | | | | | | |
| | | | | | | | | | | |
v v v v v v v v v v v
zero loss-->*---------------------------------*
min loss-->| . . . . . . . . . . . |
. | . . . . . . . . . . . |
. | . . . . . . . . . . . |
| . . . . . . |
RELIABILITY | . . . unreliable-PO . . . |
| . . . . . . . . . . . |
| . . . . . . . . . . . |
| . . . . . . . . . . . |
| . . . . . . . . . . . |
max loss-->| . . . . . . . . . . . |
+-+--+--+--+--+--+--+--+--+--+--+-+
ordered partial ordered
Figure 6: Quality Of Service: Reliability vs. Order -
Order
3.1 Reliability
When considering unreliable service, one cannot assume that
objects are equal with regards to their reliability.
classification is reasonable if all objects are identical (e.g.,
Connolly, Amer & Conrad [Page 13]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
video frames in a 30 frame/second film). Many applications, such
multimedia systems, however, often contain a variety of object types
Thus three object reliability classes are proposed: BART-NL, BART-L
and NBART-L. Objects are assigned to one of these classes
on their temporal value as will be show presently
BART-NL objects must be delivered to the destination. These
have temporal value that lasts for an entire established
and require reliable delivery (NL = No Loss allowed). An example
BART-NL objects would be the database records in Example 2.1 or
windows in the screen refresh in Example 2.3. If all objects are
type BART-NL, the service is reliable. One possible way to
eventual delivery of a BART-NL object in a protocol is for the
to buffer it, start a timeout timer, and retransmit it if no
arrives before the timeout. The receiver in turn returns an ACK
the object has safely arrived and been delivered (BART = Buffers
ACKs, Retransmissions, Timers).
BART-L objects are those that have temporal value over
intermediate amount of time - enough to permit timeout
retransmission, but not everlasting. Once the temporal value
these objects has expired, it is better to presume them lost than
delay further the delivery pipeline of information. One
for deciding when an object's usefulness has expired is to
each object to contain information defining its precise
value [DS93]. An example of a BART-L object would be a
subtitle, sent in parallel with associated film images, which
valuable any time during a twenty second film sequence. If
delivered sometime during the first ten seconds, the subtitle
its value and can be presumed lost. These objects are buffered
ACKed-retransmitted up to a certain point in time and then
lost
NBART-L objects are those with temporal values too short to
timing out and retransmitting. An example of a NBART-L object
be a single packet of speech in a packetized phone conversation
one image in a 30 image/sec film. A sender transmits these
once and the service makes a best effort to deliver them. If the
attempt is unsuccessful, no further attempts are made
An obvious question comes to mind - what about NBART-NL objects?
such objects exist? The authors have considered the notion
communicating an object without the use of BART and still being
to provide a service without loss. Perhaps with the use of
error correction this may become a viable alternative and
certainly be included in the protocol. However, for our purposes
this document, only the first three classifications will
considered
Connolly, Amer & Conrad [Page 14]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
While classic transport protocols generally treat all
equally, the sending and receiving functions of a protocol
partial order/partial reliability service will behave differently
each class of object. For example, a sender buffers and,
necessary, retransmits any BART-NL or BART-L objects that are
acknowledged within a predefined timeout period. On the contrary
NBART-L objects are forgotten as soon as they are transmitted
4. Partial Order
The implementation of a protocol that provides partial order
requires, at a minimum, (1) communication of the partial
between the two endpoints, and (2) dynamic evaluation of
deliverability of objects as they arrive at the receiver.
addition, this RFC describes the mechanisms needed to (3) initiate
connection, (4) provide varying degrees of reliability for
objects being transmitted, and (5) improve buffer utilization at
sender based on object reliability
Throughout the discussion of these issues, the authors use
generic notion of "objects" in describing the service details. Thus
one of the underlying requirements of a partial order service is
ability to handle such an abstraction (e.g., recognize
boundaries). The details of object management are
dependent and thus are not specified in this RFC. However, as
represents a potential fundamental change to the TCP protocol,
discussion is in order
At one extreme, it is possible to consider octets as objects
require that the application specify the partial order
(octet by octet). This likely would entail an inordinate amount
overhead, processing each octet on an individual basis (
breaking up contiguous segments to determine which, if any,
are deliverable and which are not). At the other extreme,
transport protocol could maintain object atomicity regardless of
- passing arbitrarily large data structures to IP for transmission
At the sending side of the connection this would actually work
IP is prepared to perform source fragmentation, however, there is
guarantee that the receiving IP will be able to reassemble
fragments! IP relies on the TCP max segment size to prevent
situation from occurring[LMKQ89].
A more realistic approach given the existing IP constraints might
to maintain the current notion of a TCP max segment size for
lower-layer interface with IP while allowing a much larger
size at the upper-layer interface. Of course this presents
additional complexities. First of all, the transport layer will
have to be concerned with fragmentation/reassembly of objects
Connolly, Amer & Conrad [Page 15]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
than the max segment size and secondly, the increased object
will require significantly more buffer space at the receiver if
want to buffer the object until it arrives in entirety
Alternatively, one may consider delivering "fragments" of an
as they arrive as long as the ordering of the fragments is
and the application is able to process the fragments (this notion
fragmented delivery is discussed further in Section 6).
4.1 Connection
By extending the transport paradigm to allow partial ordering
reliability classes, a user application may be able to take
of a more efficient data transport facility by negotiating
optimal service level which is required - no more, no less. This
accomplished by specifying these variables as QOS parameters or,
TCP terminology, as options to be included in the TCP header [Pos81].
A TCP implementation that provides a partial order service
the use of two new TCP options. The first is an enabling
"POC-permitted" (Partial Order Connection Permitted) that may be
in a SYN segment to request a partial order service. The other
the "POC-service-profile" option which is used periodically
communicate the service characteristics. This second option may
sent only after successful transmission and acknowledgment of
POC-permitted option
A user process issuing either an active or passive OPEN may choose
include the POC-permitted option if the application can benefit
the use of a partial order service and in fact, in cases where
viability of such service is unknown, it is suggested that the
be used and that the decision be left to the user's peer
For example, a multimedia server might issue a passive with
POC-permitted option in preparation for the connection by a
user
Upon reception of a segment with the POC-permitted option,
receiving user has the option to respond with a similar POC-
indication or may reject a partial order connection if
application does not warrant the service or the receiving user
simply unable to provide such a service (e.g., does not recognize
POC-permitted option).
In the event that simultaneous initial segments are exchanged
the TCP will initiate a partial order connection only if both
include the POC-permitted option
Connolly, Amer & Conrad [Page 16]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
A brief example should help to demonstrate this procedure.
following notation (a slight simplification on that employed in
793) will be used. Each line is numbered for reference purposes
TCP-A (on the left) will play the role of the receiver and TCP-B
be the sender. Right arrows (-->) indicate departure of a
segment from TCP-A to TCP-B, or arrival of a segment at B from A
Left arrows indicate the reverse. TCP states represent the
AFTER the departure or arrival of the segment (whose contents
shown in the center of the line). Liberties are taken with
contents of the segments where only the fields of interest are shown
TCP-A TCP-
1. CLOSED
2. SYN-SENT --> --> SYN-
3. ESTABLISHED <-- <-- SYN-
4. ESTABLISHED --> -->
Figure 7. Basic 3-Way handshake for a partial order
In line 1 of Figure 7, the sending user has already issued a
OPEN with the POC-permitted option and is waiting for a connection
In line 2, the receiving user issues an active OPEN with the
option which in turn prompts TCP-A to send a SYN segment with
POC-permitted option and enter the SYN-SENT state. TCP-B is able
confirm the use of a PO connection and does so in line 3, after
TCP-A enters the established state and completes the connection
an ACK segment in line 4.
In the event that either side is unable to provide partial
service, the POC-permitted option will be omitted and normal
processing will ensue
For completeness, the authors include the following specification
both the POC-permitted option and the POC-service-profile option in
format consistent with the TCP specification document [Pos81].
TCP POC-permitted Option
Kind: 9 Length: - 2
+-----------+-------------+
| Kind=9 | Length=2 |
+-----------+-------------+
Connolly, Amer & Conrad [Page 17]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
TCP POC-service-profile Option
Kind: 10 Length: 3
1 bit 1 bit 6
+----------+----------+------------+----------+--------+
| Kind=10 | Length=3 | Start_flag | End_flag | Filler |
+----------+----------+------------+----------+--------+
The first option represents a simple indicator communicated
the two peer transport entities and needs no further explanation
The second option serves to communicate the information necessary
carry out the job of the protocol - the type of information which
typically found in the header of a TCP segment - and raises
interesting questions
Standard TCP maintains a 60-byte maximum header size on all segments
The obvious intuition behind this rule is that one would like
minimize the amount of overhead information present in each
while simultaneously increasing the payload, or data, section.
this is acceptable for most TCP connections today, a partial-
service would necessarily require that significantly more
information be passed between transport entities at certain
during a connection. Maintaining the strict interpretation of
rule would prove to be inefficient. If, for example, the
profile occupied a total of 400 bytes (a modest amount as will
confirmed in the next section), then one would have to fragment
information across at least 10 segments, allocating 20 bytes
segment for the normal TCP header
Instead, the authors propose that the service profile be carried
the data section of the segment and that the 3-byte POC-service
profile option described above be placed in the header to
the presence of this information. Upon reception of such a segment
the TCP extracts the service profile and uses it appropriately
will be discussed in the following sections
The option itself, as shown here, contains two 1-bit flags
to handle the case where the service profile does not fit in a
TCP segment. The "Start_flag" indicates that the information in
data section represents the beginning of the service profile and
"End_flag" represents the converse. For service profiles which
completely in a single segment, both flags will be set to 1.
Otherwise, the Start_flag is set in the initial segment and
End_flag in the final segment allowing the peer entity to
the entire service profile (using the normal sequence numbers in
segment header). The "Filler" field serves merely to complete
third byte of the option
Connolly, Amer & Conrad [Page 18]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
Note that the length of the service profile may vary during
connection as the order or reliability requirements of the
change but this length must not exceed the buffering ability of
peer TCP entity since the entire profile must be stored. The
makeup of this data structure is presented in Section 4.2.
4.2 Data
Examining the characteristics of a partial order TCP in
fashion, one would start off with the establishment of a
as described in Section 4.1. After which, although both ends
acknowledged the acceptability of partial order transport,
has actually begun a partial order transmission - in other words
both the sending-side and the receiving-side are operating in
normal, ordered-reliable mode. For the subsequent discussion,
important distinction is made in the terms sending-side
receiving-side which refer to the data flow from the sender and
from the receiver, respectively
For the partial ordering to commence, the TCP must be made aware
the acceptable object orderings and reliability for both the send
side and receive-side of the connection for a given set of
(hereafter referred to as a "period"). This information is
in the service profile and it is the responsibility of the
application to define this profile. Unlike standard TCP
applications implicitly define a reliable, ordered profile;
partial order TCP, the application must explicity define a profile
The representation of the service profile is one of the concerns
the transport protocol. It would be useful if the TCP could encode
partial ordering in as few bits as possible since these bits will
transmitted to the destination each time the partial order changes
A matrix representation appears to be well-suited to encoding
partial order and a vector has been proposed to communicate
manage the reliability aspects of the service. Temporal values
be included within the objects themselves or may be defined as
function of the state of the connection [DS93]. Using these
structures, the complete service profile would include (1) a
order matrix, (2) a reliability vector and (3) an object_sizes
which represents the size of the objects in octets (
[ACCD93a,CAC93] for a discussion on alternative structures for
variables).
Throughout this section, we use the following service profile as
running example. Shown here is a partial order matrix and
representation for a simple partial order with 6 objects -
((1;2)||(3;4)||5);6. In the graphical diagram, arrows (-->)
sequential order and objects in parallel can be delivered in
Connolly, Amer & Conrad [Page 19]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
order. So in this example, object 2 must be delivered after
1, object 4 must be delivered after object 3, and object 6 must
delivered after objects 1 through 5 have all been delivered.
the 6 objects, there are 30 valid orderings for this partial
(each valid ordering is known as a linear extension of the
order).
1 2 3 4 5 6
+-------------+
1 | - 1 0 0 0 1 | | | |
2 | - - 0 0 0 1 | |-->1-->|-->2-->| |
3 | - - - 1 0 1 | | | |
4 | - - - - 0 1 | |-->3-->|-->4-->|-->6-->|
5 | - - - - - 1 | | | |
6 | - - - - - - | |------>5------>| |
+-------------+ | | |
PO Matrix PO
In the matrix, a 1 in row i of column j denotes that object i must
delivered before object j. Note that if objects are numbered in
way such that 1,2,3,...,N is a valid ordering, only the upper
triangle of the transitively closed matrix is needed [ACCD93a].
Thus, for N objects, the partial order can be encoded in (N*(N-1)/2)
bits
The reliability vector for the case where reliability classes
enumerated types such as {BART-NL=1, BART-L=2, NBART-L = 3} and
objects are BART-NL would simply be, <1, 1, 1, 1, 1, 1>.
with the object_sizes vector, the complete service profile
described
This information must be packaged and communicated to the sending
before the first object is transmitted using a TCP service
or comparable means depending upon the User/TCP interface. Once
service profile has been specified to the TCP, it remains in
until the connection is closed or the sending user specifies a
service profile. In the event that the largest object size can
be processed by the receiving TCP, the user application is
that the connection cannot be maintained and the normal
close procedure is followed
Typically, as has been described here, the service profile
and specification is handled at the sending end of the connection
but there could be applications (such as the screen refresh)
the receiving user has this knowledge. Under these circumstances
receiving user is obliged to transmit the object ordering on
Connolly, Amer & Conrad [Page 20]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
return side of the connection (e.g., when making the request for
screen refresh) and have the sender interpret this data to be used
the send side of the connection
Requiring that the sending application specify the service profile
not an arbitrary choice. To ensure proper object identification,
receiving application must transmit the new object numbering to
sending application (not the sending transport layer). Since
sending application must receive this information in any case,
simplifies matters greatly to require that the sending application
the only side that may specify the service profile to the
layer
Consider now the layered architecture diagram in Figure 8 and
that a connection already is established. Let us now say that
specifies the service profile for the sending-side of the
via its interface with TCP-A. TCP-A places the profile in the
of one or more data packets (depending upon the size of the
profile, the profile may require several packets), sets the POC
service-profile option and passes it to IP for transmission over
network. This packet must be transmitted reliably, therefore TCP-
buffers it and starts a normal retransmit timer. Subsequently,
service profile arrives at the destination node and is handed
TCP-B (as indicated by the arrows in Figure 8). TCP-B returns
acknowledgment and immediately adopts the service profile for
direction of data flow over the connection. When the
arrives back at TCP-A, the cycle is complete and both sides are
able to use the partial order service
+--------+ +----------+
Service | UserA | | UserB |
Profile +--------+ +----------+
| | |
| | |
v | |
| +---------+ +-----------+
| | TCP-A | | TCP-B |
| +---------+ +-----------+ ^
| | | |
| | | |
| | | |
| +---------------------------------------+ |
v | | |
------>| ---- Service Profile -------------> |----->
+---------------------------------------+
Figure 8. Layered Communication
Connolly, Amer & Conrad [Page 21]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
Note that one of the TCP entities learns of the profile via its
interface, while the other TCP entity is informed via its
interface
For the remaining discussions, we will assume that a partial
profile has been successfully negotiated for a single direction
the connection (as depicted in Figure 8) and that we may now speak
a "sending TCP" (TCP-A) and a "receiving TCP" (TCP-B). As such
TCP-A refers to the partial order data stream as the "send-side"
the connection, while TCP-B refers to the same data stream as
"receive-side".
Having established a partial order connection, the communicating
each have their respective jobs to perform to ensure proper
delivery. The sending TCP ascertains the object ordering
reliability from the service profile and uses this information in
buffering/retransmission policy. The receiver modifications are
significant, particularly the issues of object deliverability
reliability. And both sides will need to redefine the notion
window management. Let us look specifically at how each side of
TCP connection is managed under this new paradigm
4.2.1
The sender's concerns are still essentially four-fold -
data, managing buffer space, processing acknowledgments
retransmitting after a time-out - however, each takes on a
meaning in a partial order service. Additionally, the management
the service profile represents a fifth duty not previously needed
Taking a rather simplistic view, normal TCP output
involves (1) setting up the header, (2) copying user data into
outgoing segment, (3) sending the segment, (4) making a copy in
send buffer for retransmission and (5) starting a
timer. The only difference with a partial order service is that
reliability vector must be examined to determine whether or not
buffer the object and start a timer - if the object is classified
NBART-L, then steps 4 and 5 are omitted
Buffer management at the sending end of a partial order connection
dependent upon the object reliability class and the object size
When transmitting NBART-L objects the sender need not store the
for later possible retransmission since NBART-L objects are
retransmitted. The details of buffer management - such as whether
allocate fixed-size pools of memory, or perhaps utilize a
heap allocation strategy - are left to the particular
implementer
Connolly, Amer & Conrad [Page 22]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
Acknowledgment processing remains essentially intact -
acknowledgments are cumulative and specify the peer TCP's
advertisement. However, determination of this advertisement is
longer a trivial process dependent only upon the available
space (this is discussed further in Section 4.2.2). Moreover,
should be noted that the introduction of partial ordering and
reliability presents several new and interesting alternatives for
acknowledgment policy. The authors are investigating several
these strategies through a simulation model and have included a
discussion of these issues in Section 6.
The retransmit function of the TCP is entirely unchanged and
therefore not discussed further
For some applications, it may be possible to maintain the
partial order for multiple periods (e.g., the application repeats
same partial order). In the general case, however, the protocol
be able to change the service profile during an existing connection
When a change in the service profile is requested, the sending TCP
obliged to complete the processing of the current partial
before commencing with a new one. This ensures consistency
the user applications in the event of a connection failure
simplifies the protocol (future study is planned to investigate
performance improvement gained by allowing concurrent
partial orders). The current partial order is complete when
sending buffers are free. Then negotiation of the new
profile is performed in the same manner as with the initial profile
Combining these issues, we propose the following simplified
machine for the protocol (connection establishment and tear
remains the same and is not show here).
(1)Send Request (5)Ack
+------+ +-----------+
| | | |
| V | |
+----------+ (4) New PO Profile +----------+ |
+---->| |----------------------->| PO |<-----+
| | ESTAB | | |
(2) | | | | SETUP |
Ack +-----| |<-----------------------| |<-----+
Arrival +----------+ (7)PO Setup Complete +----------+ |
^ | | |
| | | |
+------+ +---------+
(3)Timeout (6)
Connolly, Amer & Conrad [Page 23]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
Event (1) - User Makes a Data Send
=========
If Piggyback Timer is set
cancel piggyback
Package and send the object (with ACK for receive-side
If object type = (BART-L,BART-NL)
Store the object and start a retransmit
If sending window is full
Block Event (1) - allow no further send requests from
Event (2) - ACK
=========
If ACKed object(s) is buffered
Release the buffer(s) and stop the retransmit timer(s
Extract the peer TCP's window
If remote TCP's window advertisement > sending window
Enable Event (1)
If remote TCP's window advertisement <= sending window
Block Event (1) - allow no further send requests from
Adjust sending window based on received window
Event (3) - Retransmit Timer
=========
If Piggyback Timer is set
cancel piggyback
Re-transmit the segment (with ACK for receive-side
Restart the
Event (4) - PO Service Profile Arrives at the User
=========
Transition to the PO SETUP
Store the Send-side PO service
Package the profile into 1 or more segments, setting
POC-Service-Profile option on
If Piggyback Timer is set
cancel piggyback
Send the segment(s) (with ACK for receive-side
Store the segment(s) and start a retransmit
Event (5) - ACK
=========
If ACKed object(s) is buffered
Release the buffer(s) and stop the retransmit timer(s
Extract the peer TCP's window
If all objects from previous service profile have been ACKed
the new service profile has been ACKed then enable Event (7)
Connolly, Amer & Conrad [Page 24]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
Event (6) - Retransmit Timer
=========
If Piggyback Timer is set
cancel piggyback
Re-transmit the segment (with ACK for receive-side
Restart the
Event (7) - PO Setup
=========
Transition to the ESTAB state and begin processing new
4.2.2
The receiving TCP has additional decisions to make involving
deliverability, reliability and window management. Additionally,
service profile must be established (and re-established)
and some special processing must be performed at the end of
period
When an object arrives, the question is no longer, "is this the
deliverable object?", but rather, "is this ONE OF the
deliverable objects?" Hence, it is convenient to think of
"Deliverable Set" of objects with a partial order protocol.
determine the elements of this set and answer the question
deliverability, the receiver relies upon the partial order
but, unlike the sender, the receiver dynamically updates the
as objects are processed thus making other objects (possibly
buffered objects) deliverable as well. A check of the object
also must be performed since BART-NL and BART-L objects require
ACK to be returned to the sender but NBART-L do not. Consider
example from the previous section
1 2 3 4 5 6
+-------------+
1 | - 1 0 0 0 1 | | | |
2 | - - 0 0 0 1 | |-->1-->|-->2-->| |
3 | - - - 1 0 1 | | | |
4 | - - - - 0 1 | |-->3-->|-->4-->|-->6-->|
5 | - - - - - 1 | | | |
6 | - - - - - - | |------>5------>| |
+-------------+ | | |
PO Matrix PO
When object 5 arrives, the receiver scans column 5, finds that
object is deliverable (since there are no 1's in the column)
immediately delivers the object to the user application. Then,
Connolly, Amer & Conrad [Page 25]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
matrix is updated to remove the constraint of any object
delivery depends on object 5 by clearing all entries of row 5.
may enable other objects to be delivered (for example, if object 2
buffered then the delivery of object 1 will make object 2
deliverable). This leads us to the next issue - delivery of
objects
In general, whenever an object is delivered, the buffers must
examined to see if any other stored object(s) becomes deliverable
CAC93 describes an efficient algorithm to implement this
based on traversing the precedence graph
Consideration of object reliability is interesting. The authors
taken a polling approach wherein a procedure is
periodically, say once every 100 milliseconds, to evaluate
temporal value of outstanding objects on which the destination
waiting. Those whose temporal value has expired (i.e. which are
longer useful as defined by the application) are "declared lost"
treated in much the same manner as delivered objects - the matrix
updated, and if the object type is BART-L, an ACK is sent.
objects from the current period which have not yet been delivered
declared lost are candidates for the "Terminator" as the procedure
called. The Terminator's criterion is not specifically addressed
this RFC, but one example might be for the receiving user
periodically pass a list of no-longer-useful objects to TCP-B
Another question which arises is, "How does one calculate the
and receive windows?" With a partial order service, these
are no longer contiguous intervals of objects but rather sets
objects. In fact, there are three sets which are of interest to
receiving TCP one of which has already been mentioned -
Deliverable Set. Additionally, we can think of the Bufferable
and the Receivable Set. Some definitions are in order
Deliverable Set: objects which can be immediately passed up
the user
Buffered Set: objects stored in a buffer awaiting delivery
Bufferable Set: objects which can be stored but not
delivered (due to some ordering constraint).
Receivable Set: union of the Deliverable Set and the
Set (which are disjoint) - intuitively, all objects
are "receivable" must be either "deliverable"
"bufferable".
Connolly, Amer & Conrad [Page 26]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
The following example will help to illustrate these sets.
our simple service profile from earlier for the case where the
of each object is 1 MByte and the receiver has only 2 MBytes
buffer space (enough for 2 objects). Define a boolean vector
length N (N = number of objects in a period) called the
Vector which is used to indicate which objects from the
period have been delivered or declared lost. Initially, all
are empty and the PO Matrix and Processed Vector are as shown here
1 2 3 4 5 6
+-------------+
1 | - 1 0 0 0 1 |
2 | - - 0 0 0 1 |
3 | - - - 1 0 1 |
4 | - - - - 0 1 |
5 | - - - - - 1 | [ F F F F F F ]
6 | - - - - - - | 1 2 3 4 5 6
+-------------+
PO Matrix Processed
From the PO Matrix, it is clear that the Deliverable Set =
{(1,1),(1,3),(1,5)}, where (1,1) refers to object #1 from period #1,
asssuming that the current period is period #1.
The Bufferable Set, however, depends upon how one defines
objects. Several approaches are possible. The authors'
approach to determining the Bufferable Set can best be explained
terms of the following rules
Rule 1: Remaining space must be allocated for all objects
period i before any object from period i+1 is
Rule 2: In the event that there exists enough space to
some but not all objects from a given period, space
be reserved for the first objects (i.e. 1,2,3,...,k
With these rules, the Bufferable Set = {(1,2),(1,4)}, the
Set is trivially equal to the empty set, { }, and the Receivable
= {(1,1),(1,2),(1,3),(1,4),(1,5)}.
Note that the current acknowledgment scheme uses the min and
values in the Receivable Set for its window advertisement which
transmitted in all ACK segments sent along the receive-side of
connection (from receiver to sender). Moreover,
"piggyback_delay" timer is still used to couple ACKs with return
(as utilized in standard TCP).
Connolly, Amer & Conrad [Page 27]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
Returning to our example, let us now assume that object 1 and then 3
arrive at the receiver and object 2 is lost. After processing
objects, the PO Matrix and Processed Vector will have the
updated structure
1 2 3 4 5 6
+-------------+
1 | - 0 0 0 0 0 |
2 | - - 0 0 0 1 |
3 | - - - 0 0 0 |
4 | - - - - 0 1 |
5 | - - - - - 1 | [ T F T F F F ]
6 | - - - - - - | 1 2 3 4 5 6
+-------------+
PO Matrix Processed
We can see that the Deliverable Set = {(1,2),(1,4),(1,5)}, but
should the Bufferable Set consist of? Since only one buffer
required for the current period's objects, we have 1 Mbyte
additional space available for "future" objects and therefore
the first object from period #2 in both the Bufferable and
Receivable Set
Deliverable Set = {(1,2),(1,4),(1,5)}
Bufferable Set = {(1,6),(2,1)}
Buffered Set = { }
Receivable Set = {(1,2),(1,4),(1,5),(1,6),(2,1)}
In general, the notion of window management takes on new meaning
a partial order service. One may re-examine the classic
relations with a partial order service in mind and devise new,
restrictive relations which may shed further light on the
of such a service
Two final details: (1) as with the sender, the receiver
periodically establish or modify the PO service profile and (2)
processing the last object in a period, the receiver must re-set
PO matrix and Processed vector to their initial states
Connolly, Amer & Conrad [Page 28]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
Let us look at the state machine and pseudo-code for the receiver
(2)Data Segment Arrival (5)PO Profile fragment
+------+ +-------+
| | | |
| V (1)First PO Profile |
+---------+ fragment arrives +---------+(6) Data
+---->| |----------------------->| |<-----+
| | ESTAB | | PO |------+
| | | | |
| | | | SETUP |<-----+
(3) +-----| |<-----------------------| |------+
Terminator+---------+ (9)PO Setup complete +---------+(7)
^ | | ^
| | | |
+------+ +------+
(4)Piggyback Timeout (8)Piggyback
Event 1 - First PO Service Profile fragment arrives at
=======
Transition to the PO SETUP
Store the PO service profile (fragment
Send an Acknowledgement of the PO service profile (fragment
Event 2 - Data Segment
=======
If object is in Deliverable Set
Deliver the
Update PO Matrix and Processed
Check buffers for newly deliverable
If all objects from current period have been processed
Start the next period (re-initialize data structures
Start piggyback_delay timer to send an
Else if object is in Bufferable Set
Store the
Discard
Start piggyback_delay timer to send an
Event 3 - Periodic call of the
=======
For all unprocessed objects in the current period
If object is "no longer useful"
Update PO Matrix and Processed
If object is in a buffer
Release the
Check buffers for newly deliverable
Connolly, Amer & Conrad [Page 29]
RFC 1693 An Extension to TCP: Partial Order Service November 1994
If all objects from current period have been
then Start the next period (re-initialize
structures
Event 4 - Piggyback_delay Timer
=======
Send an
Disable piggyback_delay
Event 5 - PO Service Profile fragment arrives at network
=======
Store the PO service profile (fragment
Send an Acknowledgement of the PO service profile (fragment
If entire PO Service profile has been received then enable
(9)
Event 6 - Data Segment
=======
(See event 2)
Event 7 - Periodic call of the
=======
(See Event 3)
Event 8 - Piggyback_delay Timer
=======
(See Event 4)
Event 9 - PO S