summaryrefslogtreecommitdiff
path: root/doc/rfc/rfc1693.txt
diff options
context:
space:
mode:
Diffstat (limited to 'doc/rfc/rfc1693.txt')
-rw-r--r--doc/rfc/rfc1693.txt2019
1 files changed, 2019 insertions, 0 deletions
diff --git a/doc/rfc/rfc1693.txt b/doc/rfc/rfc1693.txt
new file mode 100644
index 0000000..0ee3e3f
--- /dev/null
+++ b/doc/rfc/rfc1693.txt
@@ -0,0 +1,2019 @@
+
+
+
+
+
+
+Network Working Group T. Connolly
+Request for Comments: 1693 P. Amer
+Category: Experimental P. Conrad
+ University of Delaware
+ November 1994
+
+
+ An Extension to TCP : Partial Order Service
+
+Status of This Memo
+
+ This memo defines an Experimental Protocol for the Internet
+ community. This memo does not specify an Internet standard of any
+ kind. Discussion and suggestions for improvement are requested.
+ Distribution of this memo is unlimited
+
+IESG Note:
+
+ Note that the work contained in this memo does not describe an
+ Internet standard. The Transport AD and Transport Directorate do not
+ recommend the implementation of the TCP modifications described.
+ However, outside the context of TCP, we find that the memo offers a
+ 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 New
+ Generation of Protocols", SIGCOM 90 Proceedings, ACM, September 1990.
+
+Abstract
+
+ This RFC introduces a new transport mechanism for TCP based upon
+ partial ordering. The aim is to present the concepts of partial
+ ordering and promote discussions on its usefulness in network
+ communications. Distribution of this memo is unlimited.
+
+Introduction
+
+ A service which allows partial order delivery and partial reliability
+ is one which requires some, but not all objects to be received in the
+ order transmitted while also allowing objects to be transmitted
+ unreliably (i.e., some may be lost).
+
+ The realization of such a service requires, (1) communication and/or
+ negotiation of what constitutes a valid ordering and/or loss-level,
+ and (2) an algorithm which enables the receiver to ascertain the
+ deliverability of objects as they arrive. These issues are addressed
+ here - both conceptually and formally - summarizing the results of
+ 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 a
+ connection-oriented, transport protocol such as TCP providing a
+ further level of granularity to the transport user in terms of the
+ type and quality of offered service. This RFC focuses specifically
+ on extending TCP to provide partial order connections.
+
+ The idea of a partial order service is not limited to TCP. It may be
+ considered a useful option for any transport protocol and we
+ encourage researchers and practitioners to investigate further the
+ most effective uses for partial ordering whether in a next-generation
+ TCP, or another general purpose protocol such as XTP, or perhaps
+ within a "special purpose" protocol tailored to a specific
+ application and network profile.
+
+ Finally, while the crux of this RFC relates to and introduces a new
+ way of considering object ordering, a number of other classic
+ transport mechanisms are also seen in a new light - among these are
+ reliability, window management and data acknowledgments.
+
+ Keywords: partial order, quality of service, reliability, multimedia,
+ client/server database, Windows, transport protocol
+
+Table of Contents
+
+ 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 motivation
+
+ Current applications that need to communicate objects (i.e., octets,
+ packets, frames, protocol data units) usually choose between a fully
+ ordered service such as that currently provided by TCP and one that
+ does not guarantee any ordering such as that provided by UDP. A
+ similar "all-or-nothing" choice is made for object reliability -
+ reliable connections which guarantee all objects will be delivered
+ verses unreliable data transport which makes no guarantee. What is
+ more appropriate for some applications is a partial order and/or
+ partial reliability service where a subset of objects being
+ communicated must arrive in the order transmitted, yet some objects
+ may arrive in a different order, and some (well specified subset) of
+ the objects may not arrive at all.
+
+ One motivating application for a partial order service is the
+ emerging area of multimedia communications. Multimedia traffic is
+ often characterized either by periodic, synchronized parallel streams
+ of information (e.g., combined audio-video), or by structured image
+ streams (e.g., displays of multiple overlapping and nonoverlapping
+ windows). These applications have a high degree of tolerance for
+ less-than-fully-ordered data transport as well as data loss. Thus
+ they are ideal candidates for using a partial order, partial
+ reliability service. In general, any application which communicates
+ parallel and/or independent data structures may potentially be able
+ to profit from a partial order service.
+
+ A second application that could benefit from a partial order service
+ involves remote or distributed databases. Imagine the case where a
+ database user transmitting queries to a remote server expects objects
+ (or records) to be returned in some order, although not necessarily
+ total order. For example a user writing an SQL data query might
+ specify this with the "order by" clause. There exist today a great
+ number of commercial implementations of distributed databases which
+ utilize - and thus are penalized by - an ordered delivery service.
+
+ Currently these applications must use and pay for a fully
+ ordered/fully reliable service even though they do not need it. The
+ introduction of partial services allows applications to lower the
+ demanded quality of service (QOS) of the communication assuming that
+ such a service is more efficient and less costly. In effect, a
+ partial order extends the service level from two extremes - ordered
+ and unordered - to a range of discreet values encompassing both of
+ the extremes and all possible partial orderings in between. A
+ 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 partial
+ order service, as described here, would be able to communicate with a
+ non-partial order implementation simply by recognizing this fact at
+ connection establishment - hence this extension is backward
+ compatible with earlier versions of TCP. Furthermore, it is
+ conceivable for a host to support the sending-half (or receiving-
+ half) of a partial order connection alone to reduce the size of the
+ TCP as well as the effort involved in the implementation. Similar
+ "levels of conformance" have been proposed in other internet
+ extensions such as [Dee89] involving IP multicasting.
+
+ This RFC proceeds as follows. The principles of partial order
+ delivery, published in [ACCD93a], are presented in Section 2. The
+ notion of partial reliability, published in [ACCD93b], is introduced
+ in Section 3 followed by an explanation of "reliability classes".
+ Then, the practical issues involved with setting up and maintaining a
+ Partial Order Connection (POC) within a TCP framework are addressed
+ in Section 4 looking first at connection establishment, and then
+ discussing the sender's role and the receiver's role. Section 5
+ provides insights into the expected performance improvements of a
+ partial order service over an ordered service and Section 6 discusses
+ some future directions. Concluding remarks are given in Section 7.
+
+2. Partial Order Delivery
+
+ Partial order services are needed and can be employed as soon as a
+ complete ordering is not mandatory. When two objects can be
+ delivered in either order, there is no need to use an ordered service
+ that must delay delivery of the second one transmitted until the
+ first arrives as the following examples demonstrate.
+
+2.1 Example 1: Remote Database
+
+ 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 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
+
+ SSG employees running the client-side of the application can query
+ the database server from any location in the enterprise net using
+ standard SQL commands and the results will be displayed on their
+
+
+
+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 completely
+ reliable and delivers data (records) in an order that conforms to
+ their SQL request. In reality though, it is the transport layer
+ protocol which provides the reliability and order on top of an
+ 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 at
+ the destination, 1,2,3,4. This is evident due to the fact that there
+ are four distinct salespersons. If record 2 is received before
+ record 1 due to a network loss during transmission, the transport
+ service can not deliver it and must therefore buffer it until record
+ 1 arrives. An ordered service, also referred to as a virtual circuit
+ or FIFO channel, provides the desired level of service in this case.
+
+ At the other extreme, an unordered service is motivated in Figure 1.d
+ where the employee has implicitly specified that any ordering is
+ valid simply by omitting the "order by" clause. Here any of 4! = 24
+ delivery orderings would satisfy the application, or from the
+ transport layer's point of view, all records are immediately
+ deliverable as soon as they arrive from the network. No record needs
+ to buffered should it arrive out of sequential order. As notation, 4
+ ordered objects are written 1;2;3;4 and 4 unordered objects are
+ written using a parallel operator: 1||2||3||4.
+
+ Figures 1.b and 1.c demonstrate two possible partial orders that
+ permit 2 and 4 orderings respectively at the destination. Using the
+ notation just described, the valid orderings for the query in 1.b are
+ specified as 1;(2||3);4, which is to say that record 1 must be
+ delivered first followed by record 2 and 3 in either order followed
+ by record 4. Likewise, the ordering for 1.c is (1||2);(3||4). In
+ these two cases, an ordered service is too strict and an unordered
+ 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 Delivery
+
+ It is vital for the transport layer to recognize the exact
+ requirements of the application and to ensure that these are met.
+ However, there is no inherent need to exceed these requirements; on
+
+
+
+Connolly, Amer & Conrad [Page 6]
+
+RFC 1693 An Extension to TCP: Partial Order Service November 1994
+
+
+ the contrary, by exceeding these requirements unecessary resources
+ are consumed. This example application requires a reliable
+ connection - all records must eventually be delivered - but has some
+ 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 possible
+ partial orders each of which accepts some number of valid orderings
+ between 1 and N! (which correspond to the ordered and unordered
+ cases respectively). For some classes of partial orders, the number
+ of valid orderings can be calculated easily, for others this
+ calculation is intractable. An in-depth discussion on calculating
+ and comparing the number of orderings for a given partial order can
+ be found in [ACCD93a].
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Connolly, Amer & Conrad [Page 7]
+
+RFC 1693 An Extension to TCP: Partial Order Service November 1994
+
+
+2.2 Example 2: Multimedia
+
+ A second example application that motivates a partial order service
+ is a multimedia broadcast involving video, audio and text components.
+ Consider an extended presentation of the evening news - extended to
+ include two distinct audio channels, a text subtitle and a closed-
+ captioned sign language video for the hearing impaired, in addition
+ to the normal video signal, as modeled by the following diagram.
+
+ (left audio) (right audio)
+ +------+ +------+
+ | ++++ | | ++++ |
+ | ++++ | | ++++ |
+ +------+ +------+
+ ===================================================
+ I +---------------+I
+ I | |I
+ I | (hand signs) |I
+ I | |I
+ I +---------------+I
+ I I
+ I I
+ I (Main Video) I
+ I I
+ I I
+ I I
+ I I
+ I +------------------------------------------+ I
+ I | (text subtitle) | I
+ I +------------------------------------------+ I
+ I I
+ ===================================================
+ Figure 2: Multimedia broadcast example
+
+ The multimedia signals have differing characteristics. The main video
+ signal may consist of full image graphics at a rate of 30 images/sec
+ while the video of hand signs requires a lower quality, say 10
+ images/sec. Assume the audio signals are each divided into 60 sound
+ 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) a
+ 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 and
+ a single text packet. The following diagram then might represent the
+ characteristics of the multimedia presentation in terms of the media
+ types, the number of each, and their ordering. Objects connected by a
+
+
+
+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 parallel
+ 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 application
+
+ Of particular interest to our discussion of partial ordering is the
+ fact that, while objects of a given media type generally must be
+ received in order, there exists flexibility between the separate
+ "streams" of multimedia data (where a "stream" represents the
+ sequence of objects for a specific media type). Another significant
+ characteristic of this example is the repeating nature of the object
+ orderings. Figure 3 represents a single, one-second, partial order
+ snapshot in a stream of possibly thousands of repeating sequential
+ periods of communication.
+
+ It is assumed that further synchronization concerns in presenting the
+ objects are addressed by a service provided on top of the proposed
+ partial order service. Temporal ordering for synchronized playback
+ is considered, for example, in [AH91, HKN91].
+
+2.3 Example 3: Windows Screen Refresh
+
+ A third example to motivate a partial order service involves
+ refreshing a workstation screen/display containing multiple windows
+ from a remote source. In this case, objects (icons, still or video
+ images) that do not overlap have a "parallel" relationship (i.e.,
+ their order of refreshing is independent) while overlapping screen
+ objects have a "sequential" relationship and should be delivered in
+ order. Therefore, the way in which the windows overlap induces a
+ 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 a
+ remote display that contains four active windows (objects) named {1 2
+ 3 4}. Assume the windows are transmitted in numerical order and the
+ receiving application refreshes windows as soon as the transport
+ service delivers them. If the windows are configured as in Figure
+ 4a, then there exist two different orderings for redisplay, namely
+ 1,2,3,4 or 1,3,2,4. If window 2 is received before window 1, the
+ transport service cannot deliver it or an incorrect image will be
+ displayed. In Figure 4b, the structure of the windows results in six
+ possible orderings - 1,2,3,4 or 1,3,2,4 or 1,3,4,2 or 3,4,1,2 or
+ 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 refresh
+
+2.4 Potential Savings
+
+ In each of these examples, the valid orderings are strictly dependent
+ upon, and must be specified by the application. Intuitively, as the
+ number of acceptable orderings increases, the amount of resources
+ utilized by a partial order transport service, in terms of buffers
+ and retransmissions, should decrease as compared to a fully ordered
+ transport service thus also decreasing the overall cost of the
+ connection. Just how much lower will depend largely upon the
+ flexibility of the application and the quality of the underlying
+ network.
+
+ As an indication of the potential for improved service, let us
+ 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 DESCRIPTION
+ ------------- ----------------- --------- ---------------
+ 1 Anderson Washington $4,200 Camping Gear
+ 2 Anderson Philadelphia $2,000 Golf Equipment
+ 3 Anderson Boston $450 Bowling shoes
+ 4 Baker Boston $849 Sportswear
+ 5 Baker Washington $3,100 Weights
+ 6 Baker Washington $2000 Camping Gear
+ 7 Baker Atlanta $290 Baseball Gloves
+ 8 Baker Boston $1,500 Sportswear
+ 9 Crowell Boston $9,500 Camping Gear
+ 10 Crowell Philadelphia $6,000 Exercise Bikes
+ 11 Crowell New York $1,500 Sportswear
+ 12 Dykstra Atlanta $1,000 Sportswear
+ 13 Dykstra Dallas $15,000 Rodeo Gear
+ 14 Dykstra Miami $3,200 Golf Equipment
+
+ Using formulas derived in [ACCD93a] one may calculate the total
+ number of valid orderings for any partial order that can be
+ represented in the notation mentioned previously. For the case where
+ a user specifies "ORDER BY SALESPERSON", the partial order above can
+ 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 exist
+ 25,920 valid orderings at the destination. A service that may
+ deliver the records in any of these 25,920 orderings has a great deal
+ more flexibility than in the ordered case where there is only 1 valid
+ order for 14 objects. It is interesting to consider the real
+ possibility of hundreds or even thousands of objects and the
+ potential savings in communication costs.
+
+ In all cases, the underlying network is assumed to be unreliable and
+ may thus introduce loss, duplication, and disorder. It makes no
+ 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 is
+ not always well understood, initial experimental research indicates
+ that real world networks, for example the service provided by the
+ Internet's IP level, "yield high losses, duplicates and reorderings
+ of packets" [AS93,BCP93]. The authors plan to conduct further
+ experimentation into measuring Internet network unreliability. This
+ information would say a great deal about the practical merit of a
+ partial order service.
+
+
+
+
+
+
+
+Connolly, Amer & Conrad [Page 11]
+
+RFC 1693 An Extension to TCP: Partial Order Service November 1994
+
+
+3. Reliability vs. Order
+
+ While TCP avoids the loss of even a single object, in fact for many
+ applications, there exists a genuine ability to tolerate loss.
+ Losing one frame per second in a 30 frame per second video or losing
+ 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 service
+ that combines a partial order with a level of tolerated loss (partial
+ reliability). Traditionally there exist 4 services: reliable-
+ ordered, reliable-unordered, unreliable-ordered, and unreliable-
+ unordered. See Figure 5. Reliable-ordered service (denoted by a
+ single point) represents the case where all objects are delivered in
+ the order transmitted. File transfer is an example application
+ requiring such a service.
+
+ reliable-ordered reliable-unordered
+ | |
+ | |
+ v v
+ zero loss-->*---------------------------------*
+ min loss-->|<-- |<--
+ . | |
+ . |<-- |<--
+ | |
+ |<-- unreliable- |<-- unreliable-
+ RELIABILITY | ordered | unordered
+ |<-- |<--
+ | |
+ |<-- |<--
+ max loss-->| |
+ +-+--+--+--+--+--+--+--+--+--+--+-+
+ ordered partial ordered unordered
+
+ ORDER
+
+ Figure 5: Quality Of Service: Reliability vs. Order -
+ Traditional Service Types
+
+ In a reliable-unordered service (also a single point), all objects
+ must be delivered, but not necessarily according to the order
+ transmitted; in fact, any order will suffice. Some transaction
+ processing applications such as credit card verification require such
+ a service.
+
+ Unreliable-ordered service allows some objects to be lost. Those
+ that are delivered, however, must arrive in relative order (An
+ "unreliable" service does not necessarily lose objects; rather, it
+ may do so without failing to provide its advertised quality of
+
+
+
+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 is
+ represented by a set of points in Figure 5. An unreliable-ordered
+ service is applicable to packet-voice or teleconferencing
+ applications.
+
+ Finally unreliable-unordered service allows objects to be lost and
+ delivered in any order. This is the kind of service used for normal
+ e-mail (without acknowledgment receipts) and electronic announcements
+ or junk e-mail.
+
+ As mentioned previously, the concept of a partial order expands the
+ order dimension from the two extremes of ordered and unordered to a
+ range of discrete possibilities as depicted in Figure 6.
+ Additionally, as will be discussed presently, the notion of
+ reliability is extended to allow for varying degrees of reliability
+ on a per-object basis providing even greater flexibility and improved
+ resource utilization.
+
+ reliable-PO
+
+ | | | | | | | | | | | |
+ | | | | | | | | | | | |
+ v v v v v v v v v v v v
+ zero loss-->*---------------------------------*
+ min loss-->| . . . . . . . . . . . |
+ . | . . . . . . . . . . . |
+ . | . . . . . . . . . . . |
+ | . . . . . . |
+ RELIABILITY | . . . unreliable-PO . . . |
+ | . . . . . . . . . . . |
+ | . . . . . . . . . . . |
+ | . . . . . . . . . . . |
+ | . . . . . . . . . . . |
+ max loss-->| . . . . . . . . . . . |
+ +-+--+--+--+--+--+--+--+--+--+--+-+
+ ordered partial ordered unordered
+
+ ORDER
+
+ Figure 6: Quality Of Service: Reliability vs. Order - Partial
+ Order Service
+
+3.1 Reliability Classes
+
+ When considering unreliable service, one cannot assume that all
+ objects are equal with regards to their reliability. This
+ 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 as
+ 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 depending
+ on their temporal value as will be show presently.
+
+ BART-NL objects must be delivered to the destination. These objects
+ have temporal value that lasts for an entire established connection
+ and require reliable delivery (NL = No Loss allowed). An example of
+ BART-NL objects would be the database records in Example 2.1 or the
+ windows in the screen refresh in Example 2.3. If all objects are of
+ type BART-NL, the service is reliable. One possible way to assure
+ eventual delivery of a BART-NL object in a protocol is for the sender
+ to buffer it, start a timeout timer, and retransmit it if no ACK
+ arrives before the timeout. The receiver in turn returns an ACK when
+ the object has safely arrived and been delivered (BART = Buffers,
+ ACKs, Retransmissions, Timers).
+
+ BART-L objects are those that have temporal value over some
+ intermediate amount of time - enough to permit timeout and
+ retransmission, but not everlasting. Once the temporal value of
+ these objects has expired, it is better to presume them lost than to
+ delay further the delivery pipeline of information. One possibility
+ for deciding when an object's usefulness has expired is to require
+ each object to contain information defining its precise temporal
+ value [DS93]. An example of a BART-L object would be a movie
+ subtitle, sent in parallel with associated film images, which is
+ valuable any time during a twenty second film sequence. If not
+ delivered sometime during the first ten seconds, the subtitle loses
+ its value and can be presumed lost. These objects are buffered-
+ ACKed-retransmitted up to a certain point in time and then presumed
+ lost.
+
+ NBART-L objects are those with temporal values too short to bother
+ timing out and retransmitting. An example of a NBART-L object would
+ be a single packet of speech in a packetized phone conversation or
+ one image in a 30 image/sec film. A sender transmits these objects
+ once and the service makes a best effort to deliver them. If the one
+ attempt is unsuccessful, no further attempts are made.
+
+ An obvious question comes to mind - what about NBART-NL objects? Do
+ such objects exist? The authors have considered the notion of
+ communicating an object without the use of BART and still being able
+ to provide a service without loss. Perhaps with the use of forward
+ error correction this may become a viable alternative and could
+ certainly be included in the protocol. However, for our purposes in
+ this document, only the first three classifications will be
+ considered.
+
+
+
+Connolly, Amer & Conrad [Page 14]
+
+RFC 1693 An Extension to TCP: Partial Order Service November 1994
+
+
+ While classic transport protocols generally treat all objects
+ equally, the sending and receiving functions of a protocol providing
+ partial order/partial reliability service will behave differently for
+ each class of object. For example, a sender buffers and, if
+ necessary, retransmits any BART-NL or BART-L objects that are not
+ acknowledged within a predefined timeout period. On the contrary,
+ NBART-L objects are forgotten as soon as they are transmitted.
+
+4. Partial Order Connection
+
+ The implementation of a protocol that provides partial order service
+ requires, at a minimum, (1) communication of the partial ordering
+ between the two endpoints, and (2) dynamic evaluation of the
+ deliverability of objects as they arrive at the receiver. In
+ addition, this RFC describes the mechanisms needed to (3) initiate a
+ connection, (4) provide varying degrees of reliability for the
+ objects being transmitted, and (5) improve buffer utilization at the
+ sender based on object reliability.
+
+ Throughout the discussion of these issues, the authors use the
+ generic notion of "objects" in describing the service details. Thus,
+ one of the underlying requirements of a partial order service is the
+ ability to handle such an abstraction (e.g., recognize object
+ boundaries). The details of object management are implementation
+ dependent and thus are not specified in this RFC. However, as this
+ represents a potential fundamental change to the TCP protocol, some
+ discussion is in order.
+
+ At one extreme, it is possible to consider octets as objects and
+ require that the application specify the partial order accordingly
+ (octet by octet). This likely would entail an inordinate amount of
+ overhead, processing each octet on an individual basis (literally
+ breaking up contiguous segments to determine which, if any, octets
+ are deliverable and which are not). At the other extreme, the
+ transport protocol could maintain object atomicity regardless of size
+ - passing arbitrarily large data structures to IP for transmission.
+ At the sending side of the connection this would actually work since
+ IP is prepared to perform source fragmentation, however, there is no
+ guarantee that the receiving IP will be able to reassemble the
+ fragments! IP relies on the TCP max segment size to prevent this
+ situation from occurring[LMKQ89].
+
+ A more realistic approach given the existing IP constraints might be
+ to maintain the current notion of a TCP max segment size for the
+ lower-layer interface with IP while allowing a much larger object
+ size at the upper-layer interface. Of course this presents some
+ additional complexities. First of all, the transport layer will now
+ have to be concerned with fragmentation/reassembly of objects larger
+
+
+
+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 sizes
+ will require significantly more buffer space at the receiver if we
+ want to buffer the object until it arrives in entirety.
+ Alternatively, one may consider delivering "fragments" of an object
+ as they arrive as long as the ordering of the fragments is correct
+ and the application is able to process the fragments (this notion of
+ fragmented delivery is discussed further in Section 6).
+
+4.1 Connection Establishment
+
+ By extending the transport paradigm to allow partial ordering and
+ reliability classes, a user application may be able to take advantage
+ of a more efficient data transport facility by negotiating the
+ optimal service level which is required - no more, no less. This is
+ accomplished by specifying these variables as QOS parameters or, in
+ TCP terminology, as options to be included in the TCP header [Pos81].
+
+ A TCP implementation that provides a partial order service requires
+ the use of two new TCP options. The first is an enabling option
+ "POC-permitted" (Partial Order Connection Permitted) that may be used
+ in a SYN segment to request a partial order service. The other is
+ the "POC-service-profile" option which is used periodically to
+ communicate the service characteristics. This second option may be
+ sent only after successful transmission and acknowledgment of the
+ POC-permitted option.
+
+ A user process issuing either an active or passive OPEN may choose to
+ include the POC-permitted option if the application can benefit from
+ the use of a partial order service and in fact, in cases where the
+ viability of such service is unknown, it is suggested that the option
+ be used and that the decision be left to the user's peer.
+
+ For example, a multimedia server might issue a passive <SYN> with the
+ POC-permitted option in preparation for the connection by a remote
+ user.
+
+ Upon reception of a <SYN> segment with the POC-permitted option, the
+ receiving user has the option to respond with a similar POC-permitted
+ indication or may reject a partial order connection if the
+ application does not warrant the service or the receiving user is
+ simply unable to provide such a service (e.g., does not recognize the
+ POC-permitted option).
+
+ In the event that simultaneous initial <SYN> segments are exchanged,
+ the TCP will initiate a partial order connection only if both sides
+ 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. The
+ following notation (a slight simplification on that employed in RFC
+ 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 will
+ be the sender. Right arrows (-->) indicate departure of a TCP
+ 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 state
+ AFTER the departure or arrival of the segment (whose contents are
+ shown in the center of the line). Liberties are taken with the
+ contents of the segments where only the fields of interest are shown.
+
+ TCP-A TCP-B
+
+ 1. CLOSED LISTEN
+
+ 2. SYN-SENT --> <CTL=SYN><POC-perm> --> SYN-RECEIVED
+
+ 3. ESTABLISHED <-- <CTL=SYN,ACK><POC-perm> <-- SYN-RECEIVED
+
+ 4. ESTABLISHED --> <CTL=ACK> --> ESTABLISHED
+
+ Figure 7. Basic 3-Way handshake for a partial order connection
+
+ In line 1 of Figure 7, the sending user has already issued a passive
+ OPEN with the POC-permitted option and is waiting for a connection.
+ In line 2, the receiving user issues an active OPEN with the same
+ option which in turn prompts TCP-A to send a SYN segment with the
+ POC-permitted option and enter the SYN-SENT state. TCP-B is able to
+ confirm the use of a PO connection and does so in line 3, after which
+ TCP-A enters the established state and completes the connection with
+ an ACK segment in line 4.
+
+ In the event that either side is unable to provide partial order
+ service, the POC-permitted option will be omitted and normal TCP
+ processing will ensue.
+
+ For completeness, the authors include the following specification for
+ both the POC-permitted option and the POC-service-profile option in a
+ format consistent with the TCP specification document [Pos81].
+
+ TCP POC-permitted Option:
+
+ Kind: 9 Length: - 2 bytes
+
+ +-----------+-------------+
+ | 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 bytes
+
+ 1 bit 1 bit 6 bits
+ +----------+----------+------------+----------+--------+
+ | Kind=10 | Length=3 | Start_flag | End_flag | Filler |
+ +----------+----------+------------+----------+--------+
+
+ The first option represents a simple indicator communicated between
+ the two peer transport entities and needs no further explanation.
+ The second option serves to communicate the information necessary to
+ carry out the job of the protocol - the type of information which is
+ typically found in the header of a TCP segment - and raises some
+ 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 to
+ minimize the amount of overhead information present in each packet
+ while simultaneously increasing the payload, or data, section. While
+ this is acceptable for most TCP connections today, a partial-order
+ service would necessarily require that significantly more control
+ information be passed between transport entities at certain points
+ during a connection. Maintaining the strict interpretation of this
+ rule would prove to be inefficient. If, for example, the service
+ profile occupied a total of 400 bytes (a modest amount as will be
+ confirmed in the next section), then one would have to fragment this
+ information across at least 10 segments, allocating 20 bytes per
+ segment for the normal TCP header.
+
+ Instead, the authors propose that the service profile be carried in
+ the data section of the segment and that the 3-byte POC-service-
+ profile option described above be placed in the header to indicate
+ the presence of this information. Upon reception of such a segment,
+ the TCP extracts the service profile and uses it appropriately as
+ will be discussed in the following sections.
+
+ The option itself, as shown here, contains two 1-bit flags necessary
+ to handle the case where the service profile does not fit in a single
+ TCP segment. The "Start_flag" indicates that the information in the
+ data section represents the beginning of the service profile and the
+ "End_flag" represents the converse. For service profiles which fit
+ completely in a single segment, both flags will be set to 1.
+ Otherwise, the Start_flag is set in the initial segment and the
+ End_flag in the final segment allowing the peer entity to reconstrcut
+ the entire service profile (using the normal sequence numbers in the
+ segment header). The "Filler" field serves merely to complete the
+ 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 the
+ connection as the order or reliability requirements of the user
+ change but this length must not exceed the buffering ability of the
+ peer TCP entity since the entire profile must be stored. The exact
+ makeup of this data structure is presented in Section 4.2.
+
+4.2 Data Transmission
+
+ Examining the characteristics of a partial order TCP in chronological
+ fashion, one would start off with the establishment of a connection
+ as described in Section 4.1. After which, although both ends have
+ acknowledged the acceptability of partial order transport, neither
+ has actually begun a partial order transmission - in other words,
+ both the sending-side and the receiving-side are operating in a
+ normal, ordered-reliable mode. For the subsequent discussion, an
+ important distinction is made in the terms sending-side and
+ receiving-side which refer to the data flow from the sender and that
+ from the receiver, respectively.
+
+ For the partial ordering to commence, the TCP must be made aware of
+ the acceptable object orderings and reliability for both the send-
+ side and receive-side of the connection for a given set of objects
+ (hereafter referred to as a "period"). This information is contained
+ in the service profile and it is the responsibility of the user
+ application to define this profile. Unlike standard TCP where
+ applications implicitly define a reliable, ordered profile; with
+ partial order TCP, the application must explicity define a profile.
+
+ The representation of the service profile is one of the concerns for
+ the transport protocol. It would be useful if the TCP could encode a
+ partial ordering in as few bits as possible since these bits will be
+ transmitted to the destination each time the partial order changes.
+ A matrix representation appears to be well-suited to encoding the
+ partial order and a vector has been proposed to communicate and
+ manage the reliability aspects of the service. Temporal values may
+ be included within the objects themselves or may be defined as a
+ function of the state of the connection [DS93]. Using these data
+ structures, the complete service profile would include (1) a partial
+ order matrix, (2) a reliability vector and (3) an object_sizes vector
+ which represents the size of the objects in octets (see
+ [ACCD93a,CAC93] for a discussion on alternative structures for these
+ variables).
+
+ Throughout this section, we use the following service profile as a
+ running example. Shown here is a partial order matrix and graphical
+ representation for a simple partial order with 6 objects -
+ ((1;2)||(3;4)||5);6. In the graphical diagram, arrows (-->) denote
+ sequential order and objects in parallel can be delivered in either
+
+
+
+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 object
+ 1, object 4 must be delivered after object 3, and object 6 must be
+ delivered after objects 1 through 5 have all been delivered. Among
+ the 6 objects, there are 30 valid orderings for this partial order
+ (each valid ordering is known as a linear extension of the partial
+ 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 Graph
+
+
+ In the matrix, a 1 in row i of column j denotes that object i must be
+ delivered before object j. Note that if objects are numbered in any
+ way such that 1,2,3,...,N is a valid ordering, only the upper right
+ 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 are
+ enumerated types such as {BART-NL=1, BART-L=2, NBART-L = 3} and all
+ objects are BART-NL would simply be, <1, 1, 1, 1, 1, 1>. Together
+ with the object_sizes vector, the complete service profile is
+ described.
+
+ This information must be packaged and communicated to the sending TCP
+ before the first object is transmitted using a TCP service primitive
+ or comparable means depending upon the User/TCP interface. Once the
+ service profile has been specified to the TCP, it remains in effect
+ until the connection is closed or the sending user specifies a new
+ service profile. In the event that the largest object size can not
+ be processed by the receiving TCP, the user application is informed
+ that the connection cannot be maintained and the normal connection
+ close procedure is followed.
+
+ Typically, as has been described here, the service profile definition
+ and specification is handled at the sending end of the connection,
+ but there could be applications (such as the screen refresh) where
+ the receiving user has this knowledge. Under these circumstances the
+ receiving user is obliged to transmit the object ordering on the
+
+
+
+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 a
+ screen refresh) and have the sender interpret this data to be used on
+ the send side of the connection.
+
+ Requiring that the sending application specify the service profile is
+ not an arbitrary choice. To ensure proper object identification, the
+ receiving application must transmit the new object numbering to the
+ sending application (not the sending transport layer). Since the
+ sending application must receive this information in any case, it
+ simplifies matters greatly to require that the sending application be
+ the only side that may specify the service profile to the transport
+ layer.
+
+ Consider now the layered architecture diagram in Figure 8 and assume
+ that a connection already is established. Let us now say that UserA
+ specifies the service profile for the sending-side of the connection
+ via its interface with TCP-A. TCP-A places the profile in the header
+ of one or more data packets (depending upon the size of the service
+ profile, the profile may require several packets), sets the POC-
+ service-profile option and passes it to IP for transmission over the
+ network. This packet must be transmitted reliably, therefore TCP-A
+ buffers it and starts a normal retransmit timer. Subsequently, the
+ service profile arrives at the destination node and is handed to
+ TCP-B (as indicated by the arrows in Figure 8). TCP-B returns an
+ acknowledgment and immediately adopts the service profile for one
+ direction of data flow over the connection. When the acknowledgment
+ arrives back at TCP-A, the cycle is complete and both sides are now
+ able to use the partial order service.
+
+ +--------+ +----------+
+ Service | UserA | | UserB |
+ Profile +--------+ +----------+
+ | | |
+ | | |
+ v | |
+ | +---------+ +-----------+ Service
+ | | TCP-A | | TCP-B | Profile
+ | +---------+ +-----------+ ^
+ | | | |
+ | | | |
+ | | | |
+ | +---------------------------------------+ |
+ v | | |
+ ------>| ---- Service Profile -------------> |----->
+ +---------------------------------------+
+
+ Figure 8. Layered Communication Architecture
+
+
+
+
+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 user
+ interface, while the other TCP entity is informed via its network
+ interface.
+
+ For the remaining discussions, we will assume that a partial order
+ profile has been successfully negotiated for a single direction of
+ the connection (as depicted in Figure 8) and that we may now speak of
+ 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" of
+ the connection, while TCP-B refers to the same data stream as the
+ "receive-side".
+
+ Having established a partial order connection, the communicating TCPs
+ each have their respective jobs to perform to ensure proper data
+ delivery. The sending TCP ascertains the object ordering and
+ reliability from the service profile and uses this information in its
+ buffering/retransmission policy. The receiver modifications are more
+ significant, particularly the issues of object deliverability and
+ reliability. And both sides will need to redefine the notion of
+ window management. Let us look specifically at how each side of the
+ TCP connection is managed under this new paradigm.
+
+4.2.1 Sender
+
+ The sender's concerns are still essentially four-fold - transmitting
+ data, managing buffer space, processing acknowledgments and
+ retransmitting after a time-out - however, each takes on a new
+ meaning in a partial order service. Additionally, the management of
+ the service profile represents a fifth duty not previously needed.
+
+ Taking a rather simplistic view, normal TCP output processing
+ involves (1) setting up the header, (2) copying user data into the
+ outgoing segment, (3) sending the segment, (4) making a copy in a
+ send buffer for retransmission and (5) starting a retransmission
+ timer. The only difference with a partial order service is that the
+ reliability vector must be examined to determine whether or not to
+ buffer the object and start a timer - if the object is classified as
+ NBART-L, then steps 4 and 5 are omitted.
+
+ Buffer management at the sending end of a partial order connection is
+ dependent upon the object reliability class and the object size.
+ When transmitting NBART-L objects the sender need not store the data
+ for later possible retransmission since NBART-L objects are never
+ retransmitted. The details of buffer management - such as whether to
+ allocate fixed-size pools of memory, or perhaps utilize a dynamic
+ heap allocation strategy - are left to the particular system
+ 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 window
+ advertisement. However, determination of this advertisement is no
+ longer a trivial process dependent only upon the available buffer
+ space (this is discussed further in Section 4.2.2). Moreover, it
+ 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
+
+
+
+
+
+Connolly, Amer & Conrad [Page 23]
+
+RFC 1693 An Extension to TCP: Partial Order Service November 1994
+
+
+ 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)
+
+
+
+
+
+Connolly, Amer & Conrad [Page 24]
+
+RFC 1693 An Extension to TCP: Partial Order Service November 1994
+
+
+ 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
+
+
+
+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 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".
+
+
+
+
+
+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. 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).
+
+
+
+
+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 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.
+
+
+
+
+
+
+
+
+
+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 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
+
+
+
+Connolly, Amer & Conrad [Page 29]
+
+RFC 1693 An Extension to TCP: Partial Order Service November 1994
+
+
+ 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?"
+
+
+
+Connolly, Amer & Conrad [Page 30]
+
+RFC 1693 An Extension to TCP: Partial Order Service November 1994
+
+
+ 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.
+
+
+
+Connolly, Amer & Conrad [Page 31]
+
+RFC 1693 An Extension to TCP: Partial Order Service November 1994
+
+
+ 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 RFC introduces 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
+
+
+
+Connolly, Amer & Conrad [Page 32]
+
+RFC 1693 An Extension to TCP: Partial Order Service November 1994
+
+
+ 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.
+
+
+
+
+
+
+
+
+
+
+
+
+
+Connolly, Amer & Conrad [Page 33]
+
+RFC 1693 An Extension to TCP: Partial Order Service November 1994
+
+
+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, RFC 1112 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.
+
+
+
+
+
+
+
+Connolly, Amer & Conrad [Page 34]
+
+RFC 1693 An Extension to TCP: Partial Order Service November 1994
+
+
+ [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", RFC 1072, LBL, USC/Information
+ Sciences Institute, October 1988.
+
+ [JBB92] Jacobson, V., Braden, R., and D. Borman, "TCP
+ Extensions for High Performance", RFC 1323, 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", RFC 1263, University of Arizona,
+ October 1991.
+
+ [Pos81] Postel, J., "Transmission Control Protocol - DARPA
+ Internet Program Protocol Specification," STD 7,
+ RFC 793, DARPA, September 1981.
+
+Security Considerations
+
+ Security issues are not discussed in this memo.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Connolly, Amer & Conrad [Page 35]
+
+RFC 1693 An Extension to TCP: Partial Order Service November 1994
+
+
+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
+
+ EMail: pconrad@udel.edu
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Connolly, Amer & Conrad [Page 36]
+