rfc1693.txt

来自「RFC 的详细文档！」· 文本 代码 · 共 1,331 行 · 第 1/5 页

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.