rfc1693.txt

著名的RFC文档,其中有一些文档是已经翻译成中文的的.

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