should be noted that the introduction of partial ordering and partial
reliability presents several new and interesting alternatives for the
acknowledgment policy. The authors are investigating several of
these strategies through a simulation model and have included a brief
discussion of these issues in Section 6.
The retransmit function of the TCP is entirely unchanged and is
therefore not discussed further.
For some applications, it may be possible to maintain the same
partial order for multiple periods (e.g., the application repeats the
same partial order). In the general case, however, the protocol must
be able to change the service profile during an existing connection.
When a change in the service profile is requested, the sending TCP is
obliged to complete the processing of the current partial order
before commencing with a new one. This ensures consistency between
the user applications in the event of a connection failure and
simplifies the protocol (future study is planned to investigate the
performance improvement gained by allowing concurrent different
partial orders). The current partial order is complete when all
sending buffers are free. Then negotiation of the new service
profile is performed in the same manner as with the initial profile.
Combining these issues, we propose the following simplified state
machine for the protocol (connection establishment and tear down
remains the same and is not show here).
(1)Send Request (5)Ack Arrival
+------+ +-----------+
| | | |
| V | |
+----------+ (4) New PO Profile +----------+ |
+---->| |----------------------->| PO |<-----+
| | ESTAB | | |
(2) | | | | SETUP |
Ack +-----| |<-----------------------| |<-----+
Arrival +----------+ (7)PO Setup Complete +----------+ |
^ | | |
| | | |
+------+ +---------+
(3)Timeout (6)Timeout
Event (1) - User Makes a Data Send Request
=========
If Piggyback Timer is set then
cancel piggyback timer
Package and send the object (with ACK for receive-side)
If object type = (BART-L,BART-NL) then
Store the object and start a retransmit timer
If sending window is full then
Block Event (1) - allow no further send requests from user
Event (2) - ACK Arrives
=========
If ACKed object(s) is buffered then
Release the buffer(s) and stop the retransmit timer(s)
Extract the peer TCP's window advertisement
If remote TCP's window advertisement > sending window then
Enable Event (1)
If remote TCP's window advertisement <= sending window then
Block Event (1) - allow no further send requests from user
Adjust sending window based on received window advertisement
Event (3) - Retransmit Timer Expires
=========
If Piggyback Timer is set then
cancel piggyback timer
Re-transmit the segment (with ACK for receive-side)
Restart the timer
Event (4) - PO Service Profile Arrives at the User Interface
=========
Transition to the PO SETUP state
Store the Send-side PO service profile
Package the profile into 1 or more segments, setting the
POC-Service-Profile option on each
If Piggyback Timer is set then
cancel piggyback timer
Send the segment(s) (with ACK for receive-side)
Store the segment(s) and start a retransmit timer
Event (5) - ACK Arrival
=========
If ACKed object(s) is buffered then
Release the buffer(s) and stop the retransmit timer(s)
Extract the peer TCP's window advertisement
If all objects from previous service profile have been ACKed and
the new service profile has been ACKed then enable Event (7)
Event (6) - Retransmit Timer Expires
=========
If Piggyback Timer is set then
cancel piggyback timer
Re-transmit the segment (with ACK for receive-side)
Restart the timer
Event (7) - PO Setup Completed
=========
Transition to the ESTAB state and begin processing new service
profile
4.2.2 Receiver
The receiving TCP has additional decisions to make involving object
deliverability, reliability and window management. Additionally, the
service profile must be established (and re-established) periodically
and some special processing must be performed at the end of each
period.
When an object arrives, the question is no longer, "is this the next
deliverable object?", but rather, "is this ONE OF the next
deliverable objects?" Hence, it is convenient to think of a
"Deliverable Set" of objects with a partial order protocol. To
determine the elements of this set and answer the question of
deliverability, the receiver relies upon the partial order matrix
but, unlike the sender, the receiver dynamically updates the matrix
as objects are processed thus making other objects (possibly already
buffered objects) deliverable as well. A check of the object type
also must be performed since BART-NL and BART-L objects require an
ACK to be returned to the sender but NBART-L do not. Consider our
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 Graph
When object 5 arrives, the receiver scans column 5, finds that the
object is deliverable (since there are no 1's in the column) and
immediately delivers the object to the user application. Then, the
matrix is updated to remove the constraint of any object whose
delivery depends on object 5 by clearing all entries of row 5. This
may enable other objects to be delivered (for example, if object 2 is
buffered then the delivery of object 1 will make object 2
deliverable). This leads us to the next issue - delivery of stored
objects.
In general, whenever an object is delivered, the buffers must be
examined to see if any other stored object(s) becomes deliverable.
CAC93 describes an efficient algorithm to implement this processing
based on traversing the precedence graph.
Consideration of object reliability is interesting. The authors have
taken a polling approach wherein a procedure is executed
periodically, say once every 100 milliseconds, to evaluate the
temporal value of outstanding objects on which the destination is
waiting. Those whose temporal value has expired (i.e. which are no
longer useful as defined by the application) are "declared lost" and
treated in much the same manner as delivered objects - the matrix is
updated, and if the object type is BART-L, an ACK is sent. Any
objects from the current period which have not yet been delivered or
declared lost are candidates for the "Terminator" as the procedure is
called. The Terminator's criterion is not specifically addressed in
this RFC, but one example might be for the receiving user to
periodically pass a list of no-longer-useful objects to TCP-B.
Another question which arises is, "How does one calculate the send
and receive windows?" With a partial order service, these windows
are no longer contiguous intervals of objects but rather sets of
objects. In fact, there are three sets which are of interest to the
receiving TCP one of which has already been mentioned - the
Deliverable Set. Additionally, we can think of the Bufferable Set
and the Receivable Set. Some definitions are in order:
Deliverable Set: objects which can be immediately passed up to
the user.
Buffered Set: objects stored in a buffer awaiting delivery.
Bufferable Set: objects which can be stored but not immediately
delivered (due to some ordering constraint).
Receivable Set: union of the Deliverable Set and the Bufferable
Set (which are disjoint) - intuitively, all objects which
are "receivable" must be either "deliverable" or
"bufferable".
The following example will help to illustrate these sets. Consider
our simple service profile from earlier for the case where the size
of each object is 1 MByte and the receiver has only 2 MBytes of
buffer space (enough for 2 objects). Define a boolean vector of
length N (N = number of objects in a period) called the Processed
Vector which is used to indicate which objects from the current
period have been delivered or declared lost. Initially, all buffers
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 Vector
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 bufferable
objects. Several approaches are possible. The authors' initial
approach to determining the Bufferable Set can best be explained in
terms of the following rules,
Rule 1: Remaining space must be allocated for all objects from
period i before any object from period i+1 is buffered
Rule 2: In the event that there exists enough space to buffer
some but not all objects from a given period, space will
be reserved for the first objects (i.e. 1,2,3,...,k)
With these rules, the Bufferable Set = {(1,2),(1,4)}, the Buffered
Set is trivially equal to the empty set, { }, and the Receivable Set
= {(1,1),(1,2),(1,3),(1,4),(1,5)}.
Note that the current acknowledgment scheme uses the min and max
values in the Receivable Set for its window advertisement which is
transmitted in all ACK segments sent along the receive-side of the
connection (from receiver to sender). Moreover, the
"piggyback_delay" timer is still used to couple ACKs with return data
(as utilized in standard TCP).
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 both
objects, the PO Matrix and Processed Vector will have the following
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 Vector
We can see that the Deliverable Set = {(1,2),(1,4),(1,5)}, but what
should the Bufferable Set consist of? Since only one buffer is
required for the current period's objects, we have 1 Mbyte of
additional space available for "future" objects and therefore include
the first object from period #2 in both the Bufferable and the
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 with
a partial order service. One may re-examine the classic window
relations with a partial order service in mind and devise new, less
restrictive relations which may shed further light on the operation
of such a service.
Two final details: (1) as with the sender, the receiver must
periodically establish or modify the PO service profile and (2) upon
processing the last object in a period, the receiver must re-set the
PO matrix and Processed vector to their initial states.
Let us look at the state machine and pseudo-code for the receiver.
(2)Data Segment Arrival (5)PO Profile fragment Arrival
+------+ +-------+
| | | |
| V (1)First PO Profile | V
+---------+ fragment arrives +---------+(6) Data Segment
+---->| |----------------------->| |<-----+ Arrival
| | ESTAB | | PO |------+
| | | | |
| | | | SETUP |<-----+
(3) +-----| |<-----------------------| |------+
Terminator+---------+ (9)PO Setup complete +---------+(7) Terminator
^ | | ^
| | | |
+------+ +------+
(4)Piggyback Timeout (8)Piggyback Timeout
Event 1 - First PO Service Profile fragment arrives at network
======= interface
Transition to the PO SETUP state
Store the PO service profile (fragment)
Send an Acknowledgement of the PO service profile (fragment)
Event 2 - Data Segment Arrival
=======
If object is in Deliverable Set then
Deliver the object
Update PO Matrix and Processed Vector
Check buffers for newly deliverable objects
If all objects from current period have been processed then
Start the next period (re-initialize data structures)
Start piggyback_delay timer to send an ACK
Else if object is in Bufferable Set then
Store the object
Else
Discard object
Start piggyback_delay timer to send an ACK
Event 3 - Periodic call of the Terminator
=======
For all unprocessed objects in the current period do
If object is "no longer useful" then
Update PO Matrix and Processed Vector
If object is in a buffer then
Release the buffer
Check buffers for newly deliverable objects
If all objects from current period have been processed
then Start the next period (re-initialize data
structures)
Event 4 - Piggyback_delay Timer Expires
=======
Send an ACK
Disable piggyback_delay timer
Event 5 - PO Service Profile fragment arrives at network interface
=======
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 Event
(9)
Event 6 - Data Segment arrival
=======
(See event 2)
Event 7 - Periodic call of the terminator
=======
(See Event 3)
Event 8 - Piggyback_delay Timer Expires
=======
(See Event 4)
Event 9 - PO Setup Complete
=======
Transition to the ESTAB state
Note that, for reasons of clarity, we have used a transitively closed
matrix representation of the partial order. A more efficient
implementation based on an adjacency list representation of a
transitively reduced precedence graph results in a more efficient
running time [CAC93].
5. Quantifying and Comparing Partial Order Services
While ordered, reliable delivery is ideal, the existence of less-
than-ideal underlying networks can cause delays for applications that
need only partial order or partial reliability. By introducing a
partial order service, one may in effect relax the requirements on
order and reliability and presumably expect some savings in terms of
buffer utilization and bandwidth (due to fewer retransmissions) and
shorter overall delays. A practical question to be addressed is,
"what are the expected savings likely to be?"
As mentioned in Section 2, the extent of such savings will depend
largely on the quality of the underlying network - bandwidth, delay,
amount and distribution of loss/duplication/disorder - as well as the
flexibility of the partial order itself - specified by the PO matrix
and reliability vector. If the underlying network has no loss, a
partial order service essentially becomes an ordered service.
Collecting experimental data to ascertain realistic network
conditions is a straightforward task and will help to quantify in
general the value of a partial order service [Bol93]. But how can
one quantify and compare the cost of providing specific levels of
service?
Preliminary research indicates that the number of linear extensions
(orderings) of a partial order in the presence of loss effectively
measures the complexity of that order. The authors have derived
formulae for calculating the number of extensions when a partial
order is series-parallel and have proposed a metric for comparing
partial orders based on this number [ACCD93b]. This metric could be
used as a means for charging for the service, for example. What also
may be interesting is a specific head-to-head comparison between
different partial orders with varying degrees of flexibility. Work
is currently underway on a simulation model aimed at providing this
information. And finally, work is underway on an implementation of
TCP which includes partial order service.
6. Future Direction
In addition to the simulation and implementation work the authors are
pursuing several problems related to partial ordering which will be
mentioned briefly.
An interesting question arises when discussing the acknowledgment
strategy for a partial order service. For classic protocols, a
cumulative ACK of object i confirms all objects "up to and including"
i. But the meaning of "up to and including" with a partial order
service has different implications than with an ordered service.
Consider our example partial order, ((1;2)||(3;4)||5);6). What
should a cumulative ACK of object 4 confirm? The most logical
definition would say it confirms receipt of object 4 and all objects
that precede 4 in the partial order, in this case, object 3. Nothing
is said about the arrival of objects 1 or 2. With this alternative
interpretation where cumulative ACKs depend on the partial order, the
sender must examine the partial order matrix to determine which
buffers can be released. In this example, scanning column 4 of the
matrix reveals that object 3 must come before object 4 and therefore
both object buffers (and any buffers from a previous period) can be
released.
Other partial order acknowledgment policies are possible for a
protocol providing a partial order service including the use of
selective ACKs (which has been proposed in [JB88] and implemented in
the Cray TCP [Chang93]) as well as the current TCP strategy where an
ACK of i also ACKs everything <= i (in a cyclical sequence number
space). The authors are investigating an ACK policy which utilizes a
combination of selective and "partial-order-cumulative"
acknowledgments. This is accomplished by replacing the current TCP
cumulative ACK with one which has the partial order meaning as
described above and augmenting this with intermittent selective ACKs
when needed.
In another area, the notion of fragmented delivery, mentioned in the
beginning of Section 4, looks like a promising technique for certain
classes of applications which may offer a substantial improvement in
memory utilization. Briefly, the term fragmented delivery refers to
the ability to transfer less-than-complete objects between the
transport layer and the user application (or session layer as the
case may be). For example, a 1Mbyte object could potentially be
delivered in multiple "chunks" as segments arrive thus freeing up
valuable memory and reducing the delay on those pieces of data. The
scenario becomes somewhat more complex when multiple "parallel
streams" are considered where the application could now receive
pieces of multiple objects associated with different streams.
Additional work in the area of implementing a working partial order
protocol is being performed both at the University of Delaware and at
the LAAS du CNRS laboratory in Toulouse, France - particularly in
support of distributed, high-speed, multimedia communication. It will
be interesting to examine the processing requirements for an
implementation of a partial order protocol at key events (such as
object arrival) compared with a non-partial order implementation.
Finally, the authors are interested in the realization of a network
application utilizing a partial order service. The aim of such work
is threefold: (1) provide further insight into the expected
performance gains, (2) identify new issues unique to partial order
transport and, (3) build a road-map for application designers
interested in using a partial order service.
7. Summary
This RFCintroduces the concepts of a partial order service and
discusses the practical issues involved with including partial
ordering in a transport protocol. The need for such a service is
motivated by several applications including the vast fields of
distributed databases, and multimedia. The service has been
presented as a backward-compatible extension to TCP to adapt to
applications with different needs specified in terms of QOS
parameters.
The notion of a partial ordering extends QOS flexibility to include
object delivery, reliability, and temporal value thus allowing the
transport layer to effectively handle a wider range of applications
(i.e., any which might benefit from such mechanisms). The service
profile described in Section 4 accurately characterizes the QOS for a
partial order service (which encompasses the two extremes of total
ordered and unordered transport as well).
Several significant modifications have been proposed and are
summarized here:
(1) Replacing the requirement for ordered delivery with one for
application-dependent partial ordering
(2) Allowing unreliable and partially reliable data transport
(3) Conducting a non-symmetrical connection (not entirely foreign
to TCP, the use of different MSS values for the two sides
of a connection is an example)
(4) Management of "objects" rather than octets
(5) Modified acknowledgment strategy
(6) New definition for the send and receive "windows"
(7) Extension of the User/TCP interface to include certain
QOS parameters
(8) Use of new TCP options
As evidenced by this list, a partial order and partial reliability
service proposes to re-examine several fundamental transport
mechanisms and, in so doing, offers the opportunity for substantial
improvement in the support of existing and new application areas.
8. References
[ACCD93a] Amer, P., Chassot, C., Connolly, T., and M. Diaz,
"Partial Order Transport Service for Multimedia
Applications: Reliable Service", Second International
Symposium on High Performance Distributed Computing
(HPDC-2), Spokane, Washington, July 1993.
[ACCD93b] Amer, P., Chassot, C., Connolly, T., and M. Diaz,
"Partial Order Transport Service for Multimedia
Applications: Unreliable Service", Proc. INET '93, San
Francisco, August 1993.
[AH91] Anderson, D., and G. Homsy, "A Continuous Media I/O
Server and its Synchronization Mechanism", IEEE
Computer, 24(10), 51-57, October 1991.
[AS93] Agrawala, A., and D. Sanghi, "Experimental Assessment
of End-to-End Behavior on Internet," Proc. IEEE INFOCOM
'93, San Francisco, CA, March 1993.
[BCP93] Claffy, K., Polyzos, G., and H.-W. Braun, "Traffic
Characteristics of the T1 NSFNET", Proc. IEEE INFOCOM
'93, San Francisco, CA, March 1993.
[Bol93] Bolot, J., "End-to-End Packet Delay and Loss Behavior
in the Internet", SIGCOMM '93, Ithaca, NY, September
1993.
[CAC93] Conrad, P., Amer, P., and T. Connolly, "Improving
Performance in Transport-Layer Communications Protocols
by using Partial Orders and Partial Reliability",
Work in Progress, December 1993.
[Chang93] Chang, Y., "High-Speed Transport Protocol Evaluation --
the Final Report", MCNC Center for Communications
Technical Document, February 1993.
[Dee89] Deering, S., "Host Extensions for IP Multicasting," STD
5, RFC1112 Stanford University, August 1989.
[DS93] Diaz, M., and P. Senac, "Time Stream Petri Nets: A
Model for Multimedia Synchronization", Proceedings of
Multimedia Modeling '93, Singapore, 1993.
[HKN91] Hardt-Kornacki, S., and L. Ness, "Optimization Model
for the Delivery of Interactive Multimedia Documents",
In Proc. Globecom '91, 669-673, Phoenix, Arizona,
December 1991.
[JB88] Jacobson, V., and R. Braden, "TCP Extensions for
Long-Delay Paths", RFC1072, LBL, USC/Information
Sciences Institute, October 1988.
[JBB92] Jacobson, V., Braden, R., and D. Borman, "TCP
Extensions for High Performance", RFC1323, LBL, Cray
Research, USC/Information Sciences Institute, May 1992.
[LMKQ89] Leffler, S., McKusick, M., Karels, M., and J.
Quarterman, "4.3 BSD UNIX Operating System",
Addison-Wesley Publishing Company, Reading, MA, 1989.
[OP91] O'Malley, S., and L. Peterson, "TCP Extensions
Considered Harmful", RFC1263, University of Arizona,
October 1991.
[Pos81] Postel, J., "Transmission Control Protocol - DARPA
Internet Program Protocol Specification," STD 7,
RFC793, DARPA, September 1981.
Security Considerations
Security issues are not discussed in this memo.
Authors' Addresses
Tom Connolly
101C Smith Hall
Department of Computer & Information Sciences
University of Delaware
Newark, DE 19716 - 2586
EMail: connolly@udel.edu
Paul D. Amer
101C Smith Hall
Department of Computer & Information Sciences
University of Delaware
Newark, DE 19716 - 2586
EMail: amer@udel.edu
Phill Conrad
101C Smith Hall
Department of Computer & Information Sciences
University of Delaware
Newark, DE 19716 - 2586