RFC 1693
An Extension to TCP : Partial Order Service
RFC 1693: An Extension to TCP : Partial Order Service 💖
- Stream: Network Working Group 🌐
- RFC number: 1693 🎀
- Authors: T. Connolly, P. Amer, and P. Conrad, all from the University of Delaware 🦋
- Category: Experimental 🧪
- Date: November 1994 📅
- Obsoletes / Updates: the title block doesn't list either one, so this RFC isn't replacing or updating anything 🙅♀️
Status of This Memo 📣
Okay bestie, first the boring but important part! This memo defines an Experimental Protocol for the Internet community. It does not specify an Internet standard of any kind. The authors want discussion and suggestions for improvement 🫶 and distribution of this memo is unlimited ✨
IESG Note 🧐
Heads up, this work is not an Internet standard. The Transport AD and Transport Directorate do not recommend implementing the TCP modifications described here 😬 BUT (lowkey the best part) outside the context of TCP, the memo offers a useful analysis of how misordered and incomplete data may be handled 🔥
If you want the juicy background, check out 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 on partial ordering 🦋 The aim is to present the concepts of partial ordering and get people talking about how useful it is in network communications 💬 Distribution of this memo is unlimited.
Introduction 💅
Okay so the vibe here is: right now apps basically get two choices. Either they pick a fully ordered service (like TCP, where everything arrives in the order it was sent) or an unordered one that doesn't promise any ordering at all (like UDP) 😵💫
A partial order and partial reliability service is the in-between option, and it's giving main character energy ✨ It's a service where some, but not all, objects must arrive in the order they were transmitted, other objects can arrive out of order, and some (a well-specified subset) might never arrive at all 🧩
To make this work, you need two things 👑 First, the two ends have to communicate and/or negotiate what counts as a valid ordering and/or loss level. Second, the receiver needs an algorithm that lets it figure out whether each object can be delivered as it arrives 🔍 The authors dig into both of these, conceptually AND formally, and they summarize the results of their research and early implementation work 🧠
The authors picture a partial order service living inside a connection-oriented transport protocol like TCP 💖 It gives the transport user one more level of control over the type and quality of service they get. This RFC focuses specifically on extending TCP to support partial order connections 🎀
Partial ordering isn't only a TCP thing, though 🌈 The authors say it could be a useful option for any transport protocol, and they encourage researchers and practitioners to keep exploring the most effective uses for it. That could be in a next-generation TCP, in another general purpose protocol like XTP, or in a "special purpose" protocol built for one specific application and network profile 🧚
Last but not least, while the crux of this RFC is a new way of thinking about object ordering, it also gives a fresh look at some classic transport mechanisms 😭 Reliability, window management, and data acknowledgments all get seen in a new light ✨
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 .............................................. 361. Introduction and motivation 🦋
Alright, real talk: right now most apps are stuck with an all-or-nothing vibe. They usually pick between a fully ordered service, like the one TCP gives, and one that doesn't guarantee any ordering at all, like UDP. Objects here means octets, packets, frames, or protocol data units 📦 Reliability is also all-or-nothing: you get reliable connections that guarantee every object is delivered, or unreliable transport that makes no guarantee at all 😤
What a lot of apps actually want is a partial order and/or partial reliability service 💅 In that setup, a subset of the objects has to arrive in the order they were sent, some objects can arrive out of order, and some (a well-specified subset) might not arrive at all. It's giving flexibility, and it's so much more iykyk 🫶
One big motivating application is multimedia 🎬 Multimedia traffic often shows up as periodic, synchronized parallel streams (think combined audio-video), or as structured image streams (like displays with multiple overlapping and nonoverlapping windows) 🪟 These apps can handle less-than-fully-ordered data and even some data loss, which makes them perfect candidates for a partial order, partial reliability service 🌸 Honestly, any app that communicates parallel and/or independent data structures could potentially profit from this 🤑
Another app that could totally benefit is remote or distributed databases 🗄️ Picture a database user sending queries to a remote server who expects the records to come back in some order, though not necessarily a total order. For example, someone writing an SQL data query might say so with the "order by" clause 🧾 Right now there are tons of commercial distributed database implementations that use an ordered delivery service and get penalized for it 😩
Right now these apps have to use and pay for a fully ordered, fully reliable service even when they don't need one 💀 Partial services let apps lower the quality of service (QOS) they ask for, on the assumption that such a service is more efficient and less costly ✨ Basically, partial order stretches the service levels from two extremes, ordered and unordered, into a range of discrete values covering both extremes and all the possible partial orderings in between 🌈 The same thing happens with reliability too 💖
Here's something worth knowing 🎀 A TCP implementation providing a partial order service, as described here, could talk to a non-partial order implementation just by recognizing this at connection establishment. That makes this extension backward compatible with earlier versions of TCP 🫶 It's also conceivable for a host to support only the sending half (or the receiving half) of a partial order connection, which could reduce the size of TCP and the effort needed to implement it 🧩 Similar "levels of conformance" have been proposed in other internet extensions, like the IP multicasting work in [Dee89] 🦋
Here's the roadmap, bestie 🗺️ The principles of partial order delivery, published in [ACCD93a], are covered in Section 2. The notion of partial reliability, published in [ACCD93b], comes next in Section 3, followed by an explanation of "reliability classes". Then Section 4 gets into the practical side of setting up and maintaining a Partial Order Connection (POC) within a TCP framework: connection establishment first, then the sender's role and the receiver's role 🔧 Section 5 shares insights into the expected performance improvements of a partial order service over an ordered service, Section 6 talks about future directions, and Section 7 wraps everything up 🎉
2. Partial Order Delivery ✨
Okay so the key idea here is simple. Partial order services are needed and can be employed as soon as a complete ordering isn't mandatory 🙌 When two objects can be delivered in either order, there's zero reason to use an ordered service that makes the second one wait until the first one arrives. The examples below show exactly that 👀
2.1. Example 1: Remote Database 💅
Simpson's Sporting Goods (SSG) just got a state-of-the-art enterprise-wide network 🌐. Their first "network application" is a client/server SQL database with 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 SportswearSSG employees on the client side can query the database server from anywhere in the enterprise net using standard SQL commands, and the results pop up on their screen ✨. From the employee's POV, the network is totally reliable and hands records over in an order that matches their SQL request. Plot twist 🙈: the transport layer protocol is the one providing reliability and order on top of an unreliable network layer, one that can introduce loss, duplication, and disorder.
Check out the four cases in Figure 1. In query 1.a, ordered by SALESPERSON, there's only one acceptable order at the destination, 1,2,3,4, because there are four distinct salespersons. If record 2 shows up before record 1 because something got lost along the way, the transport service can't deliver it, so it has to buffer it until record 1 arrives. An ordered service, also called a virtual circuit or FIFO channel, is exactly what this case needs 💖.
Now the other extreme. In 1.d, the employee left out the "order by" clause, which means any ordering is valid 🦋. Here, 4! = 24 delivery orderings would satisfy the app. From the transport layer's point of view, every record is immediately deliverable as soon as it arrives from the network, so nothing has to be buffered when it shows up out of sequence. For notation, 4 ordered objects are written 1;2;3;4, and 4 unordered objects use a parallel operator: 1||2||3||4.
Figures 1.b and 1.c are two partial orders, permitting 2 and 4 orderings at the destination. The valid orderings for 1.b are 1;(2||3);4, which means record 1 is delivered first, then record 2 and 3 in either order, then record 4. The ordering for 1.c is (1||2);(3||4). In both cases, an ordered service is too strict and an unordered service isn't strict enough 🎀.
+-----------------------------------------------------------------+
| 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's vital for the transport layer to recognize the exact requirements of the application and make sure they're met. But there's no inherent need to go beyond them. Going above and beyond just burns unnecessary resources 😤. This example app needs a reliable connection (all records must eventually be delivered), but it has flexibility when it comes to record ordering.
Each query here has a different partial order. In total, there are 16 different partial orders for the 4 records 🧚. For an arbitrary number of objects N, there are many possible partial orders, and each one accepts some number of valid orderings between 1 and N!, which match the ordered and unordered cases respectively. For some classes of partial orders, the number of valid orderings is easy to calculate. For others, the calculation is intractable. The deep dive on calculating and comparing these counts is in [ACCD93a].
2.2. Example 2: Multimedia 🎬
A second example that motivates a partial order service is a multimedia broadcast with video, audio, and text components. Picture an extended presentation of the evening news, with two distinct audio channels, a text subtitle, and a closed-captioned sign language video for the hearing impaired, all on top of the normal video signal. Here's how it's modeled:
(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 very different vibes 💜. The main video is full image graphics at 30 images/sec, while the hand sign video needs a lower quality, say 10 images/sec. Each audio signal is divided into 60 sound fragments/sec. The text object, each second, is 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 slice of the broadcast, a sender transmits 30 full-motion video images, 10 closed-captioned hand sign images, 60 packets of digitized audio for each of the audio streams, and a single text packet 🌸. The diagram below shows the media types, how many of each there are, and how they're ordered. Objects connected by a horizontal line must be received in order, while objects 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 applicationokay so the partial ordering part is lowkey the most interesting bit here 🦋 objects of one media type generally must be received in order, but there's real flexibility between the separate "streams" of multimedia data (a "stream" is just the sequence of objects for one media type) 💅. also the orderings keep repeating!! Figure 3 is one single, one-second partial order snapshot out of a stream of possibly thousands of repeating sequential periods of communication ✨
further synchronization stuff for presenting the objects is handled by a service sitting on top of the proposed partial order service 🧚 (temporal ordering for synchronized playback gets covered in [AH91, HKN91] 🎀)
2.3 Example 3: Windows Screen Refresh
example 3 is giving multi-window energy 💻🌸 refreshing a workstation screen or display with multiple windows from a remote source. objects like icons or still and video images that do not overlap have a "parallel" relationship (their refresh order is independent, do whatever 💅), while overlapping screen objects have a "sequential" relationship and should be delivered in order. so the way the windows overlap basically induces a partial order. iykyk 👑
consider the two cases in Figure 4 ✨ a sender wants to refresh a remote display with four active windows (objects) named {1 2 3 4}. assume the windows get transmitted in numerical order, and the receiving app refreshes each window as soon as the transport service delivers it. if the windows are set up like Figure 4a, there are two different orderings for redisplay: 1,2,3,4 or 1,3,2,4. if window 2 shows up before window 1, the transport service cannot deliver it, or else an incorrect image will be displayed 💀 in Figure 4b the window structure gives 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 refresh2.4 Potential Savings
in every one of these examples, the valid orderings are strictly dependent on, and must be specified by, the application 📝 vibe check: as the number of acceptable orderings goes up, the resources a partial order transport service uses (buffers and retransmissions) should go down compared to a fully ordered transport service, and that also lowers the overall cost of the connection 💜. just how much lower depends a lot on how flexible the app is and how good the underlying network is ✨
as a little glow-up teaser 🌈 check out a database with these 14 records:
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 Equipmentusing formulas from [ACCD93a], you can calculate the total number of valid orderings for any partial order that can be represented in the notation we mentioned before 🧮 if 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 are 25,920 valid orderings at the destination 😳 a service that may deliver the records in any of these 25,920 orderings has way more flexibility than the ordered case, where there is only 1 valid order for 14 objects. imagine 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 💅 the exact amount of unreliability in a network may vary and is not always well understood, but early experimental research says real world networks (like the Internet's IP level) "yield high losses, duplicates and reorderings of packets" [AS93,BCP93] 😭 the authors plan to run more experiments measuring Internet network unreliability 🔬, and that info would say a great deal about the practical merit of a partial order service 🎀
3. Reliability vs. Order
okay real talk 🎀 TCP avoids the loss of even a single object, but for lots of apps there's a genuine ability to tolerate loss. losing one frame per second in a 30 frame per second video, or a segment of its accompanying audio channel, is usually not a problem 🎬 so it's valuable to look at a quality of service that combines a partial order with a level of tolerated loss (partial reliability) 💜 traditionally there are 4 services: reliable-ordered, reliable-unordered, unreliable-ordered, and unreliable-unordered. See Figure 5 🦋 reliable-ordered service (denoted by a single point) means all objects get delivered in the order they were transmitted. file transfer is a classic example that needs this 📁
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 Typesin 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 apps, like credit card verification, need this kind of service 💳
unreliable-ordered service allows some objects to be lost. the ones that do get delivered, though, must arrive in relative order (an "unreliable" service doesn't necessarily lose objects; it may do so without failing to provide its advertised quality of 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 ✨ unreliable-ordered is the right fit for packet-voice or teleconferencing apps 🎙️
finally, unreliable-unordered service allows objects to be lost and delivered in any order 🌀 this is the vibe 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 whole range of discrete possibilities, as shown in Figure 6 🌈 and as we'll get into in a sec, reliability is extended to allow varying degrees of reliability on a per-object basis, which gives 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 Service3.1 Reliability Classes 🎀
okay so bestie, when we're talking about unreliable service, you can't just assume every object is the same when it comes to reliability 👀 that's fine if everything is identical, like video frames in a 30 frame/second film. but multimedia stuff usually has a whole mix of object types 🌈 so we propose three reliability classes: BART-NL, BART-L, and NBART-L. objects get sorted into one of these based on their temporal value, which I'll show you in a sec ✨
BART-NL objects must be delivered to the destination 💌 their temporal value lasts for the entire established connection, and they need reliable delivery (NL = No Loss allowed). examples are the database records from Example 2.1 or the windows in the screen refresh from Example 2.3. if every object is BART-NL, the service is reliable 💖 one way to make sure a BART-NL object eventually arrives is for the sender to buffer it, start a timeout timer, and retransmit it if no ACK shows up before the timeout. the receiver sends back an ACK once the object has safely arrived and been delivered (BART = Buffers, ACKs, Retransmissions, Timers) 🫶
BART-L objects are the in-between ones 🦋 they have temporal value over some middle amount of time, long enough to allow a timeout and a retransmission, but not forever. once that value has expired, it's better to presume them lost than to hold up the delivery pipeline 🚫 one option for deciding when an object's usefulness is up is to make each object carry information that defines its exact temporal value [DS93]. a good example is a movie subtitle sent alongside the film images that's valuable any time during a twenty second film sequence. if it isn't delivered during the first ten seconds, the subtitle loses its value and can be presumed lost 😭 these objects get buffered, ACKed, and retransmitted up to a certain point in time, and then they're presumed lost.
NBART-L objects have temporal values that are too short to bother timing out and retransmitting 💀 an example is a single packet of speech in a packetized phone conversation, or one image in a 30 image/sec film. the sender transmits these objects once, and the service makes a best effort to deliver them. if that one attempt is unsuccessful, no further attempts are made 🫠
okay now the obvious question: what about NBART-NL objects? do those even exist? 🤔 the authors have thought about communicating an object without using BART and still providing a service without loss. maybe with forward error correction this could become a viable alternative, and it could certainly be included in the protocol 🔥 but for our purposes in this document, we're only considering the first three classifications 💅
classic transport protocols usually treat all objects equally, but 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 aren't acknowledged within a predefined timeout period. NBART-L objects, on the other hand, are forgotten the moment they're 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 ✨ on top of that, 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" when describing the service details. so one of the underlying requirements of a partial order service is the ability to handle that abstraction (e.g., recognize object boundaries) 🧚 the details of object management are implementation dependent and thus aren't specified in this RFC. still, since this represents a potential fundamental change to the TCP protocol, some discussion is in order 🎀
at one extreme, it's possible to consider octets as objects and require that the application specify the partial order accordingly (octet by octet). this would likely 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 aren't) 😵💫 at the other extreme, the transport protocol could maintain object atomicity regardless of size, passing arbitrarily large data structures to IP for transmission. on the sending side this would actually work since IP is prepared to perform source fragmentation 🙌 however, there's 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 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 its 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 ✨
okay bestie, so the whole point of extending the transport paradigm to allow partial ordering and reliability classes 💖 is that an app can shop for the exactly right service level. no more, no less 💅. you negotiate it by setting these variables as QOS parameters, or in TCP terms, as options in the TCP header [Pos81] 🎀
a TCP implementation that offers partial order service needs two new TCP options 🦋. the first is the enabling option POC-permitted (Partial Order Connection Permitted), which can show up in a SYN segment to ask for partial order service. the second is POC-service-profile, which gets sent periodically to communicate the service characteristics. this second one is only allowed to be sent after the POC-permitted option has been successfully transmitted and acknowledged 🫶
a user process doing either an active or passive OPEN can include POC-permitted if the app would benefit from a partial order service 🌸. and when it's unclear whether the service is viable? the suggestion is to just include the option and let the peer make the call 🤷
for example, a multimedia server might send a passive <SYN> with POC-permitted while it gets ready for a remote user to connect 🎬
when a <SYN> with POC-permitted shows up, the receiving user can answer with its own POC-permitted indication. or it can reject the partial order connection, if the app doesn't warrant it or the user just can't provide it (like if it doesn't recognize the option at all) 🙈
and if both initial SYN segments cross each other, TCP only starts a partial order connection if both sides included POC-permitted 👯
okay so now a quick example 🧁. we're using a notation that's a slight simplification of the one in RFC 793. every line is numbered so we can point at it. TCP-A (on the left) plays the receiver and TCP-B is the sender. right arrows (-->) mean a segment leaving A for B, or arriving at B from A. left arrows are the reverse. the TCP states shown are the state AFTER the segment departs or arrives (the segment's contents are in the middle of the line). we took some liberties with the contents, only showing the fields that matter 📝
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 connectionso in line 1 of Figure 7, the sending user has already done a passive OPEN with POC-permitted and is just waiting for a connection 👀. in line 2, the receiving user does an active OPEN with the same option, which makes TCP-A send a SYN with POC-permitted and jump into SYN-SENT 🚀. TCP-B confirms that a PO connection is happening in line 3, then TCP-A goes ESTABLISHED and wraps things up with an ACK in line 4 💜
if either side can't provide partial order service, POC-permitted gets left out and normal TCP processing just carries on as usual 💀
for completeness, the authors include the spec for both POC-permitted and POC-service-profile in a format that matches the TCP spec [Pos81] 📋
TCP POC-permitted Option:
Kind: 9 Length: - 2 bytes
+-----------+-------------+
| Kind=9 | Length=2 |
+-----------+-------------+
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 is a simple indicator between the two peer transport entities, so no further explanation needed ✨. the second one carries the info needed to run the protocol, the kind of stuff that normally lives in a TCP segment header, and ngl it raises some interesting questions 🤔
okay so standard TCP keeps a 60-byte maximum header size on all segments 📦. the vibe behind that rule is: keep the overhead per packet tiny and make room for the payload. that's totally fine for most TCP connections today 👍, BUT a partial-order service would need way more control information passed between transport entities at certain points in a connection 😬. sticking to the strict version of the rule would be super inefficient. like, if the service profile was 400 bytes (a modest amount, as we'll confirm in the next section 👀), you'd have to chop it across at least 10 segments, allocating 20 bytes per segment for the normal TCP header 🧩
so the authors propose that the service profile rides in the data section of the segment, and the 3-byte POC-service-profile option goes in the header to flag that this info is there ✨. when a receiver gets one of these segments, it pulls out the profile and uses it appropriately, as we'll get into in the following sections 💅
the option has two 1-bit flags for when the profile doesn't fit in a single segment 🧩:
Start_flagsays the data section represents the beginning of the service profile.End_flagis the converse, marking the end of it.
if the profile fits completely in one segment, both flags get set to 1 🙌. otherwise, Start_flag is set in the initial segment and End_flag in the final one, so the peer can reconstruct the entire profile using the normal sequence numbers in the segment header 🧠. and the Filler field? it just completes the third byte of the option 🫧
one last thing 🚨: the length of the service profile can change during the connection as the order or reliability requirements change, but it must not exceed the buffering ability of the peer TCP entity, since the entire profile has to be stored 😭
the exact makeup of this data structure is presented in Section 4.2 🎀
4.2 Data Transmission 💖
Okay so picture the timeline. We start with the connection setup from 4.1, and both ends have agreed that partial order is cool 🫶. But nobody has actually started a partial order transmission yet. Both the sending-side and the receiving-side are still chilling in normal ordered-reliable mode 🧚. Quick vocab check, because these two terms are going to be everywhere: sending-side is the data flow coming from the sender, and receiving-side is the data flow coming from the receiver 💅.
Before the partial ordering can start, TCP has to know which object orderings and reliability levels are allowed on both the send-side and the receive-side for a given set of objects. We call that set a "period" ✨. All of this info lives in the service profile, and it's the user application's job to define it. Standard TCP is kind of lazy about this, because applications implicitly get a reliable, ordered profile for free. With partial order TCP, the application has to explicitly define a profile 😤.
Now, how to represent that profile is one of the transport protocol's big concerns 🎀. Ideally, TCP would encode a partial ordering in as few bits as possible, since those bits get sent to the destination every time the partial order changes. A matrix looks like a great fit for the ordering, and a vector has been proposed for managing the reliability side of things 🦋. Temporal values can go inside the objects themselves, or they can be defined as a function of the connection's state [DS93]. So the complete service profile has three parts: (1) a partial order matrix, (2) a reliability vector, and (3) an object_sizes vector, which holds the size of each object in octets. (If you want the deeper dive on other structures for these variables, check [ACCD93a,CAC93] 🤓.)
For the rest of this section, we'll use one service profile as our running example 🍓. Here's a partial order matrix and graph for a simple partial order with 6 objects, written as ((1;2)||(3;4)||5);6. In the graph, arrows (-->) mean sequential order, and objects that sit in parallel can be delivered in either order. So in this example, object 2 has to come after object 1, object 4 has to come after object 3, and object 6 has to come after objects 1 through 5 have all been delivered 👑. Out of those 6 objects there are 30 valid orderings, and each one is called 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 GraphIn the matrix, a 1 in row i, column j means object i has to be delivered before object j 🌈. Here's the neat trick: if the objects are numbered so that 1,2,3,...,N is a valid ordering, you only need the upper right triangle of the transitively closed matrix [ACCD93a] 🫧. That means N objects can be encoded in N*(N-1)/2 bits. Super compact, iconic behaviour 💅.
Next up is the reliability vector. Say the reliability classes are enumerated types like {BART-NL=1, BART-L=2, NBART-L = 3}, and every object is BART-NL. Then the reliability vector is simply <1, 1, 1, 1, 1, 1> 🎀. Put that together with the object_sizes vector, and boom, the whole service profile is described ✨.
This info has to be packaged up and handed to the sending TCP before the first object gets transmitted 📦. How exactly that happens depends on the User/TCP interface, and it can be a TCP service primitive or some comparable means. Once the service profile is set, it stays in effect until the connection closes or the sending user specifies a new service profile 🔁.
Heads up, this one's serious: if the receiving TCP can't process the largest object size, the user application gets told that the connection can't be maintained, and the normal connection close procedure kicks in. No drama, just the rules 💀.
Usually, the sending end is the one that handles defining and specifying the service profile. But there are apps, like the screen refresh, where the receiving user is the one with that knowledge 👀. In that case, the receiving user has to send the object ordering back over the return side of the connection (for example, when it asks for a screen refresh), and then the sender interprets that data and uses it on the send side 🫶.
Why does the sending application have to be the one specifying the profile? It's not random, I promise 🙈. To make sure objects get identified properly, the receiving application has to send the new object numbering to the sending application, not the sending transport layer. And since the sending application needs that info anyway, it's way simpler to say the sending application is the only side allowed to specify the service profile to the transport layer 🧠.
Let's look at the layered architecture in Figure 8, and assume a connection is already up ⭐. Say UserA specifies the service profile for the sending-side of the connection through its interface with TCP-A. TCP-A puts the profile in the header of one or more data packets (it depends on the profile's size, since the profile might need several packets), sets the POC-service-profile option, and passes it to IP for transmission over the network 🚀. This packet has to be transmitted reliably, so TCP-A buffers it and starts a normal retransmit timer ⏱️. Eventually the service profile reaches the destination node and gets handed to TCP-B (the arrows in Figure 8 show the path). TCP-B sends back an acknowledgment and immediately adopts the service profile for one direction of data flow over the connection 🦋. When that acknowledgment gets back to TCP-A, the cycle is complete, and both sides can now use the partial order service 🎉.
+--------+ +----------+
Service | UserA | | UserB |
Profile +--------+ +----------+
| | |
| | |
v | |
| +---------+ +-----------+ Service
| | TCP-A | | TCP-B | Profile
| +---------+ +-----------+ ^
| | | |
| | | |
| | | |
| +---------------------------------------+ |
v | | |
------>| ---- Service Profile -------------> |----->
+---------------------------------------+Figure 8. Layered Communication Architecture
Notice that one TCP entity learns about the profile through its user interface, while the other TCP entity learns about it through its network interface 👀.
For the rest of the discussion, we'll assume a partial order profile has been successfully negotiated for one direction of the connection (the one shown in Figure 8) 💖. From here on, TCP-A is the "sending TCP" and TCP-B is the "receiving TCP" 🌸. TCP-A calls that partial order data stream the "send-side" of the connection, and TCP-B calls the same stream the "receive-side" 🫶.
Now that a partial order connection is established, both communicating TCPs have their own jobs to do so data still gets delivered properly 🔥. The sending TCP figures out the object ordering and reliability from the service profile and uses that in its buffering and retransmission policy 📚. The receiver changes are way bigger, especially when it comes to object deliverability and reliability 😭. And both sides have to redefine what window management means in this new paradigm 🪟. Let's dig into how each side of the TCP connection is managed under this new setup 👑✨.
4.2.1. Sender 💌
okay so the sender still has basically four jobs: sending data, managing buffer space, handling acks, and retransmitting after a timeout 🫶 but each one hits different in a partial order service, and there's a brand new fifth job on top: managing the service profile 💅 main character energy
taking a simple look, normal TCP output processing is: (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. ngl the only difference with partial order is that you have to check the reliability vector to decide whether to buffer the object and start a timer. if the object is NBART-L, then steps 4 and 5 get skipped 🙈
buffer management at the sending end depends on the object's reliability class and its size. when sending NBART-L objects, the sender doesn't have to store the data for a possible retransmission, because NBART-L objects are never retransmitted 🧚 stuff like whether to use fixed-size memory pools or a dynamic heap is left up to whoever implements it 🍓
ack processing is mostly the same. acks are cumulative and carry the peer TCP's window advertisement 🦋 BUT working out that advertisement is no longer just "whatever buffer space is free," so it's a bit more involved (more on that in Section 4.2.2). also, partial ordering and partial reliability open up some new and interesting ack policy options 👀 the authors are testing a few of these in a simulation, and they've got a short chat about them in Section 6.
the retransmit function of TCP is completely unchanged, so we're not going to dig into it 💤
for some apps, you might keep the same partial order for multiple periods (like when the app repeats the same partial order). in the general case though, the protocol has to be able to change the service profile in the middle of a connection. when that happens, the sending TCP has to finish processing the current partial order before starting a new one 🫶 this keeps both user apps consistent if the connection fails, and it keeps the protocol simpler (future study is planned to see whether it's worth allowing concurrent, different partial orders 👀). the current partial order is complete once all sending buffers are free. then the new service profile gets negotiated the same way the initial one did ✨
putting it all together, here's the simplified state machine for the protocol. connection establishment and teardown stay the same and aren't drawn out 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)Timeouthere's what each event does 👇
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 userEvent (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 advertisementEvent (3) - Retransmit Timer Expires
=========
If Piggyback Timer is set then
cancel piggyback timer
Re-transmit the segment (with ACK for receive-side)
Restart the timerEvent (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 timerEvent (5) - ACK Arrival
=========
If ACKed object(s) is buffered then
Release the buffer(s) and stop the retransmit timer(s)
Extract the peer TCP's window advertisement
If all objects from previous service profile have been ACKed and
the new service profile has been ACKed then enable Event (7)Event (6) - Retransmit Timer Expires
=========
If Piggyback Timer is set then
cancel piggyback timer
Re-transmit the segment (with ACK for receive-side)
Restart the timerEvent (7) - PO Setup Completed
=========
Transition to the ESTAB state and begin processing new service
profile4.2.2 Receiver 🎀
okay bestie, the receiving TCP has even MORE decisions to make 💅 like object deliverability, reliability, AND window management. on top of that, the service profile must be established (and re-established) periodically, and some special processing has to happen at the end of each period ✨
when an object shows up, the question isn't "is this the next deliverable object?" anymore 😭 it's "is this ONE OF the next deliverable objects?" so it's giving Deliverable Set energy 🦋 with a partial order protocol. to figure out what's in that set and answer deliverability, the receiver uses the PO matrix. BUT unlike the sender, the receiver updates the matrix on the fly as objects get processed, which means other objects (even ones already sitting in buffers!) can become deliverable too 🔥 also, the object type has to be checked, because BART-NL and BART-L objects need an ACK sent back to the sender, and NBART-L objects don't. let's look at our example from the last 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 Graphokay so when object 5 arrives, the receiver scans column 5, sees there are no 1's in it (so it's deliverable!!), and immediately hands it to the user application 🫶 then the matrix gets updated. every entry in row 5 gets cleared, which removes the constraint on any object whose delivery depended on object 5. that can unlock other objects too. like, if object 2 is buffered, delivering object 1 makes object 2 deliverable 💜 which brings us to the next issue: delivering stored objects 👀
whenever an object gets delivered, the buffers have to be checked to see if any other stored object(s) become deliverable. CAC93 describes an efficient algorithm for this that works by traversing the precedence graph ✨
reliability is lowkey so interesting 🌈 the authors took a polling approach. a procedure runs periodically, say once every 100 milliseconds, to check the temporal value of outstanding objects that the destination is waiting on 🧚 anything whose temporal value has expired (aka it's no longer useful as defined by the application) gets "declared lost" 💀 and is handled pretty much like a delivered object: the matrix gets updated, and if the object type is BART-L, an ACK is sent. any objects from the current period that haven't been delivered or declared lost yet are candidates for the "Terminator" each time the procedure runs. the RFC doesn't specifically address the Terminator's criterion, but one example could be the receiving user periodically passing a list of no-longer-useful objects to TCP-B 🎀
now the big question: how do you calculate the send and receive windows? 🤔 with a partial order service, these windows aren't contiguous intervals anymore. they're sets of objects 🌸 the receiving TCP cares about three sets: the Deliverable Set (we already met it), plus the Bufferable Set and the Receivable Set. here's the tea:
- 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".
let's run an example to make these sets click 💖 we'll use our simple service profile from earlier, where each object is 1 MByte and the receiver only has 2 MBytes of buffer space (enough for 2 objects). we define a boolean vector of length N (N = number of objects in a period) called the Processed Vector, which tracks which objects from the current period have been delivered or declared lost. at the start, all buffers are empty, and the PO Matrix and Processed Vector look like this:
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 Vectorfrom the PO Matrix, it's clear that Deliverable Set = {(1,1),(1,3),(1,5)}, where (1,1) means object #1 from period #1 (assuming the current period is period #1) 🌸
the Bufferable Set, though, depends on how you define "bufferable" objects, and several approaches are possible 🧠 the authors' initial approach can be explained with these 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 those rules, Bufferable Set = {(1,2),(1,4)}, the Buffered Set is trivially the empty set { }, and Receivable Set = {(1,1),(1,2),(1,3),(1,4),(1,5)} ✨
the current acknowledgment scheme uses the min and max values in the Receivable Set for its window advertisement 🦋 that advertisement goes out in all ACK segments sent along the receive side of the connection (from receiver to sender). and the piggyback_delay timer still couples ACKs with return data, just like standard TCP 💜
back to the example: object 1 arrives, then object 3 arrives, and object 2 is lost 😭 after processing both, the PO Matrix and Processed Vector look like this:
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 Vectornow the Deliverable Set is {(1,2),(1,4),(1,5)}. but what should the Bufferable Set be? since only one buffer is needed for the current period's objects, there's 1 Mbyte of extra space left for "future" objects 🧚 so the first object from period #2 gets included in both the Bufferable and Receivable Sets:
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, window management takes on a whole new meaning with a partial order service 💅 you can re-examine the classic window relations with PO service in mind and come up with new, less restrictive relations that might shed more light on how this service works ✨
two last things 🫶 (1) just like the sender, the receiver must periodically establish or modify the PO service profile, and (2) after processing the last object in a period, the receiver must re-set the PO matrix and Processed Vector to their initial states.
now let's look at the state machine and pseudo-code for the receiver 🧚
(2)Data Segment Arrival (5)PO Profile fragment Arrival
+------+ +-------+
| | | |
| V (1)First PO Profile | V
+---------+ fragment arrives +---------+(6) Data Segment
+---->| |----------------------->| |<-----+ Arrival
| | ESTAB | | PO |------+
| | | | |
| | | | SETUP |<-----+
(3) +-----| |<-----------------------| |------+
Terminator+---------+ (9)PO Setup complete +---------+(7) Terminator
^ | | ^
| | | |
+------+ +------+
(4)Piggyback Timeout (8)Piggyback Timeout Event 1 - First PO Service Profile fragment arrives at network
======= interface
Transition to the PO SETUP state
Store the PO service profile (fragment)
Send an Acknowledgement of the PO service profile (fragment)
Event 2 - Data Segment Arrival
=======
If object is in Deliverable Set then
Deliver the object
Update PO Matrix and Processed Vector
Check buffers for newly deliverable objects
If all objects from current period have been processed then
Start the next period (re-initialize data structures)
Start piggyback_delay timer to send an ACK
Else if object is in Bufferable Set then
Store the object
Else
Discard object
Start piggyback_delay timer to send an ACK
Event 3 - Periodic call of the Terminator
=======
For all unprocessed objects in the current period do
If object is "no longer useful" then
Update PO Matrix and Processed Vector
If object is in a buffer then
Release the buffer
Check buffers for newly deliverable objects
If all objects from current period have been processed
then Start the next period (re-initialize data
structures)
Event 4 - Piggyback_delay Timer Expires
=======
Send an ACK
Disable piggyback_delay timer
Event 5 - PO Service Profile fragment arrives at network interface
=======
Store the PO service profile (fragment)
Send an Acknowledgement of the PO service profile (fragment)
If entire PO Service profile has been received then enable Event
(9)
Event 6 - Data Segment arrival
=======
(See event 2)
Event 7 - Periodic call of the terminator
=======
(See Event 3)
Event 8 - Piggyback_delay Timer Expires
=======
(See Event 4)
Event 9 - PO Setup Complete
=======
Transition to the ESTAB stateone last note 💅 for clarity, we've 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, gives a more efficient running time [CAC93] 🚀
5. Quantifying and Comparing Partial Order Services ✨
okay so ordered, reliable delivery is the dream 🫶 but real underlying networks are kinda messy, and that can slow apps down when they really only need partial order or partial reliability 😭 by adding a partial order service, you basically relax the rules on order and reliability, and the vibe is that you should get some savings in buffer use and bandwidth (fewer retransmissions!) and shorter overall delays 🦋 so the big practical question is, "what are the expected savings likely to be?" 🤔
as we said in Section 2, how big the savings are depends a lot on how good the underlying network is (bandwidth, delay, how much loss/duplication/disorder there is) and also how flexible the partial order is, which is set by the PO matrix and the reliability vector 💅 if the underlying network has no loss at all, a partial order service just becomes an ordered service, no cap 💀 collecting experimental data to figure out realistic network conditions is pretty straightforward and will help show the value of a partial order service in general [Bol93] 📊 but how do you quantify and compare what it costs to provide specific levels of service? 👀
okay so preliminary research says the number of linear extensions (orderings) of a partial order, when there's loss, is basically a way to measure how complex that order is 🧠 the authors worked out formulas for counting the extensions when a partial order is series-parallel, and they proposed a metric for comparing partial orders based on that number [ACCD93b] ✨ this metric could even be used for charging for the service, for example 💰 another thing that'd be super interesting is a head-to-head comparison of different partial orders with different levels of flexibility 🔥 work on a simulation model to get that info is currently underway 🧚 and last but not least, work is underway on an implementation of TCP that includes a partial order service 🎀
6. Future Direction 🔮
so in addition to the simulation and implementation work, the authors are chasing a few more partial-ordering problems, which I'll just mention quickly 🌸
okay this one is lowkey a brain teaser 🧠 when you talk about the acknowledgment strategy for a partial order service, things get weird. for classic protocols, a cumulative ACK of object i confirms all objects "up to and including" i 💅 but "up to and including" means something different with a partial order service than it does with an ordered service 🙈
let's use our example partial order, ((1;2)||(3;4)||5);6) 🍓 what should a cumulative ACK of object 4 confirm? 🤔 the most logical answer is that it confirms receipt of object 4 and all the objects that come before 4 in the partial order, which here is object 3 💜 nothing is said about objects 1 or 2 arriving, so they don't get confirmed 😭 with this alternative take, where cumulative ACKs depend on the partial order, the sender has to look at the partial order matrix to figure out which buffers it can free up 🧹 in this example, scanning column 4 of the matrix shows that object 3 has to come before object 4, so both object buffers (and any buffers from a previous period) can be released ✨
there are other partial order acknowledgment policies too 🦋 for example, selective ACKs (which were proposed in [JB88] and implemented in the Cray TCP [Chang93]), plus the current TCP strategy where an ACK of i also ACKs everything <= i (in a cyclical sequence number space) 🌈 the authors are looking into an ACK policy that mixes selective and "partial-order-cumulative" acknowledgments 💖 the way they do it is by swapping the current TCP cumulative ACK for one with the partial order meaning described above, and then adding intermittent selective ACKs when they're needed 🎀
on another note, fragmented delivery (which we brought up at the start of Section 4) looks like a promising technique for certain kinds of applications, and it could be a big win for memory utilization 🔥 basically, fragmented delivery means you can move less-than-complete objects between the transport layer and the user application (or the session layer, depending on the case) 🧚 like, a 1Mbyte object could potentially be delivered in multiple "chunks" as segments arrive, which frees up valuable memory and cuts down the delay on those pieces of data 🫧 it gets a little more complex when you consider multiple "parallel streams," where the application could be receiving pieces of several objects from different streams at once 🌀
more work on actually implementing a working partial order protocol is happening both at the University of Delaware and at the LAAS du CNRS lab in Toulouse, France 🇫🇷 especially for distributed, high-speed, multimedia communication 🎥 it'll be super interesting to look at how much processing an implementation of a partial order protocol needs at key events (like object arrival) compared to a non-partial order implementation ⚡
finally, the authors want to build a network application that uses a partial order service 🚀 the goal is threefold: (1) get more insight into the expected performance gains, (2) identify new issues that are unique to partial order transport, and (3) build a road-map for application designers who want to use a partial order service 🗺️💖
7. Summary 🎀
okay recap time 💅 this RFC introduces the concepts of a partial order service and talks through the practical issues of including partial ordering in a transport protocol 🌸 the need for it is motivated by several applications, including the huge fields of distributed databases and multimedia 📀 the service is presented as a backward-compatible extension to TCP, so it can adapt to applications with different needs, which are described in terms of QOS parameters ✨
partial ordering extends QOS flexibility to cover object delivery, reliability, and temporal value 🫶 so the transport layer can handle a wider range of applications (basically, any app that could benefit from these mechanisms) 🌈 the service profile described in Section 4 characterizes the QOS for a partial order service really accurately, and it covers the two extremes of totally ordered and unordered transport too 🔥
a bunch of significant modifications have been proposed, and here they are 👑
(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 you can see from this list, a partial order and partial reliability service wants to re-examine several fundamental transport mechanisms 🤯 and by doing that, it offers a real chance for big improvements in supporting existing and new application areas 🦋💖
8. References 📚
[ACCD93a] Amer, P., Chassot, C., Connolly, T., and M. Diaz,
"Partial Order Transport Service for Multimedia
Applications: Reliable Service", Second International
Symposium on High Performance Distributed Computing
(HPDC-2), Spokane, Washington, July 1993.
[ACCD93b] Amer, P., Chassot, C., Connolly, T., and M. Diaz,
"Partial Order Transport Service for Multimedia
Applications: Unreliable Service", Proc. INET '93, San
Francisco, August 1993.
[AH91] Anderson, D., and G. Homsy, "A Continuous Media I/O
Server and its Synchronization Mechanism", IEEE
Computer, 24(10), 51-57, October 1991.
[AS93] Agrawala, A., and D. Sanghi, "Experimental Assessment
of End-to-End Behavior on Internet," Proc. IEEE INFOCOM
'93, San Francisco, CA, March 1993.
[BCP93] Claffy, K., Polyzos, G., and H.-W. Braun, "Traffic
Characteristics of the T1 NSFNET", Proc. IEEE INFOCOM
'93, San Francisco, CA, March 1993.
[Bol93] Bolot, J., "End-to-End Packet Delay and Loss Behavior
in the Internet", SIGCOMM '93, Ithaca, NY, September
1993.
[CAC93] Conrad, P., Amer, P., and T. Connolly, "Improving
Performance in Transport-Layer Communications Protocols
by using Partial Orders and Partial Reliability",
Work in Progress, December 1993.
[Chang93] Chang, Y., "High-Speed Transport Protocol Evaluation --
the Final Report", MCNC Center for Communications
Technical Document, February 1993.
[Dee89] Deering, S., "Host Extensions for IP Multicasting," STD
5, 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.
[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. 😱 (yes, it's really that: no security stuff in here, so read up elsewhere before you ship anything 💀)
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📦 where this page comes from
- ietf: rfc1693 1994-11
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms