idnits 2.17.1 draft-ietf-avt-reedsolomon-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 176: '...f the media stream it protects. It MAY...' RFC 2119 keyword, line 192: '... naling protocol MUST establish a symb...' RFC 2119 keyword, line 222: '...he specification MUST set this bit to ...' RFC 2119 keyword, line 448: '...ilizing encryption SHOULD encrypt both...' RFC 2119 keyword, line 464: '... MUST NOT substantially increase the...' Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (November 3, 1998) is 9305 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? '1' on line 513 looks like a reference -- Missing reference section? '2' on line 516 looks like a reference -- Missing reference section? '3' on line 520 looks like a reference -- Missing reference section? '4' on line 524 looks like a reference -- Missing reference section? '5' on line 527 looks like a reference Summary: 8 errors (**), 0 flaws (~~), 2 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Engineering Task Force Audio Video Transport WG 2 Internet Draft J.Rosenberg,H.Schulzrinne 3 draft-ietf-avt-reedsolomon-00.txt Bell Laboratories,Columbia U. 4 November 3, 1998 5 Expires: May 2, 1999 7 An RTP Payload Format for Reed Solomon Codes 9 STATUS OF THIS MEMO 11 This document is an Internet-Draft. Internet-Drafts are working docu- 12 ments of the Internet Engineering Task Force (IETF), its areas, and 13 its working groups. Note that other groups may also distribute work- 14 ing documents as Internet-Drafts. 16 Internet-Drafts are draft documents valid for a maximum of six months 17 and may be updated, replaced, or obsoleted by other documents at any 18 time. It is inappropriate to use Internet-Drafts as reference 19 material or to cite them other than as ``work in progress''. 21 To learn the current status of any Internet-Draft, please check the 22 ``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow 23 Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), 24 munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or 25 ftp.isi.edu (US West Coast). 27 Distribution of this document is unlimited. 29 ABSTRACT 31 This document specifies a payload format for forward 32 error correction of media encapsulated in RTP using Reed 33 Solomon codes. The payload format allows end systems to 34 transmit using arbitrary block lengths and codes. It also 35 allows for the recovery of both the payload and critical 36 RTP header fields. Since FEC is sent as a separate 37 stream, it is backwards compatible with non-FEC capable 38 hosts, so that receivers which do not wish to implement 39 FEC can just ignore the extensions. 41 1 Introduction 42 The quality of packet voice on the Internet has been mediocre due, in 43 part, to high packet loss rates. This is especially true on wide-area 44 connections. Unfortunately, the strict delay requirements of real- 45 time multimedia usually eliminate the possibility of retransmissions. 46 It is for this reason that forward error correction (FEC) has been 47 proposed to compensate for packet loss in the Internet [1] [2]. In 48 particular, the use of traditional error correcting codes, such as 49 parity, Reed-Solomon, and Hamming codes, has attracted attention. To 50 support these mechanisms, protocol support is required. 52 This document defines a payload format for RTP which allows for for- 53 ward error correction of media based on Reed Solomon (RS) codes. It 54 is similar in design to [3], which specifies forward error correction 55 using exclusive or based parity codes. As with that format, the Reed 56 Solomon format described here is generic. This means that the proto- 57 col is (1) independent of the nature of the media being protected, be 58 it audio, video, or otherwise, (2) flexible enough to support a wide 59 variety of RS codes, (3) designed for adaptivity so that the FEC 60 technique can be modified easily without out of band signaling, and 61 (4) supportive of a number of different mechanisms for transporting 62 the FEC packets. 64 2 Terminology 66 The following terms are used throughout this document: 68 1. Media Payload: is a piece of raw, un-protected user data 69 which is to be transmitted from the sender. The media pay- 70 load would is placed inside of an RTP packet. 72 2. Media Header: is the RTP header for the packet containing 73 the media payload. 75 3. Media Packet: The combination of a media payload and media 76 header is called a media packet. 78 4. FEC Packet: The forward error correction algorithms at the 79 transmitter take the media packets as an input. They output 80 both the media packets that they are passed, and new pack- 81 ets called FEC packets. The FEC packets are formatted 82 according to the rules specified in this document. 84 5. FEC Header: The FEC header is the header information con- 85 tained in an FEC packet. 87 6. FEC Payload: The FEC payload is the payload in an FEC 88 packet. 90 7. Media Block: The media block is a set of K consecutive 91 media packets which are used to generate the FEC packets. 93 8. Coding Block: The coding block is a set of N packets, con- 94 sisting of the K packets from a single media block, plus 95 N-K additional FEC packets generated from the media block. 97 9. K: K is a variable which represents the number of media 98 packets in a media block. 100 10. N: N is a variable which represents the total number of 101 packets in a coding block. 103 11. Reed Solomon Code: A Reed Solomon code is uniquely deter- 104 mined by the values of N and K, as defined above, and the 105 symbol length. 107 3 Basic Operation 109 The media packets are broken into blocks of K. K can vary from block 110 to block. The Reed Solomon coding is used to obtain N-K FEC packets 111 which protect the K media packets. 113 The FEC packets are sent as a separate stream from the media packets. 114 This implies that the FEC packets have their own sequence number 115 space. Although the timestamps for the FEC packets are derived from 116 the media packets, they increment monotonically. Combined together, 117 FEC packet streams work well with RTP header compression. The media 118 packet stream is unaffected by the use of FEC. This allows the two to 119 be sent on a separate multicast group, so that non-FEC receivers can 120 ignore the FEC and just receive the original media. The separation 121 also allows for coherent values for the sequence numbers and times- 122 tamps. 124 This document does not prescibe the definition of "separate streams", 125 but leaves this to applications and higher level protocols to define. 126 For multicast, the separate stream may be implemented by separate 127 multicast groups, different ports in the same group, or by a dif- 128 ferent SSRC within the same group/port. For unicast, different ports 129 or different SSRC may be used. Each of these approaches has drawbacks 130 and benefits which depend on the application. 132 At the receiver, arriving FEC and media packets are used to generate 133 a stream of media packets for direct use by the application. This 134 results in a clean separation of error protection from the applica- 135 tion. 137 FEC packets encoded according to this document are indicated through 138 the payload type in the packet header. These payload types are sig- 139 naled dynamically. 141 4 Reed Solomon Codes 143 The detailed operation and theory behind Reed Solomon codes is not 144 important here. A Reed Solomon code takes a group of K data blocks 145 and generates N - K FEC blocks. A receiver needs to receive any K of 146 the N data or FEC blocks in order to recover the K data blocks. 147 Besides K and N, the only parameters of the algorithm are the symbol 148 length, which is the number of bits per symbol used in the algorithm. 149 If the symbol length is l, the size of the data block must be a mul- 150 tiple of l. For more information of Reed Solomon codes, the reader is 151 referred to [4]. 153 Reed Solomon codes are systematic. This means that the K data blocks 154 are not modified as a result of the FEC operation. 156 5 RTP Media Packet Structure 158 The media packets and FEC packets are sent as separate streams. The 159 media packets are unaffected by FEC, and are sent in the same fashion 160 they would be sent if there were no FEC. 162 This lends to a very efficient encoding. When little (or no) FEC is 163 used, there are mostly media packets being sent. This means that the 164 overhead (present in FEC packets only) tracks the amount of FEC in 165 use. 167 6 FEC Packet Structure 169 When a packet is to be transmitted which contains FEC data, the RTP 170 header is followed by an FEC header. We first discuss the semantics 171 of the RTP header fields. 173 The version field is set to 2. The padding bit is computed via the 174 protection operation, defined below. The extension bit is also com- 175 puted via the protection operation. The SSRC value should generally 176 be the same as the SSRC value of the media stream it protects. It MAY 177 be different if the FEC stream is being demultiplexed via the SSRC 178 value. The CC value is computed via the protection operation. The 179 CSRC list is never present, independent of the value of the CC field. 180 The extension is never present, independent of the value of the X 181 bit. The marker bit is computed via the protection operation. 183 The sequence number has the standard definition: it is one higher 184 than the sequence number in the previously transmitted FEC packet. 185 The timestamp is set in the following fashion. When the FEC packet is 186 sent, the value of the media RTP timestamp is examined. This value is 187 used as the timestamp of the FEC packet. This results in the TS value 188 in FEC packets to be monotonically increasing, independent of the FEC 189 scheme. 191 The payload type is obtained through out of band signaling. The sig- 192 naling protocol MUST establish a symbol length to be associated with 193 the payload type value. End systems which cannot recognize a payload 194 type must discard it. This provides backwards compatibility. The FEC 195 mechanisms can then be used in a multicast group with mixed FEC- 196 capable and FEC-uncapable receivers. 198 Following the RTP header is the Reed Solomon header. 200 6.1 Reed Solomon Header 202 The format of the Reed-Solomon FEC header is shown below. 204 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 205 | SN Base | length recovery | 206 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 207 |E| PT Recovery | N | K | i | 208 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 209 | TS Recovery | 210 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 212 The length recovery field is used to determine the length of any 213 recovered packets. It is computed via the protection operation 214 applied to the 16 bit natural binary representation of the lengths 215 (in bytes) of the media payload, CSRC list, extension and padding of 216 media packets in the media block (in other words, the CSRC list, 217 extension, and padding, if present, are "counted" as part of the pay- 218 load). This allows for the FEC procedure to be applied even when the 219 lengths of the media packets are not identical. 221 The E bit indicates a header extension. Implementations conforming to 222 this version of the specification MUST set this bit to zero. 224 The PT recovery field is obtained via the protection operation 225 applied to the payload type values of the media packets in the media 226 block. 228 The TS recovery field is computed via the protection operation 229 applied to the timestamps of the media packets in the media block. 230 This allows the timestamp to be completely recovered. 232 The SN base is the sequence number of the first media packet in the 233 media block protected by FEC. The K field is the number of media 234 packets in the media block, minus 1. The N field is the total number 235 of FEC plus data packets in the coding block, minus 1. The i field 236 indicates that this packet is the i+1th FEC packet of the N-K FEC 237 packets in the code. The symbol length of the code is indicated by 238 means of the payload type field in the RTP header. 240 The payload of the FEC packet is the protection operation applied to 241 the CSRC List plus payloads plus extension plus padding of the media 242 packets in the media block. 244 7 Protection Operation 246 The protection operation involves taking a variety of fields from the 247 various headers, adding the payloads, appending the whole thing 248 together, padding zeroes, and then computing the FEC across the 249 resulting binary block. The result is then placed into the FEC 250 packet. 252 For each media block consisting of K media packets, K binary arrays 253 are generated (one for each packet) by appending the following fields 254 from the header and payload together: 256 o Padding Bit (1 bit) 258 o Extension Bit (1 bit) 260 o CC bits (3 bits) 262 o Marker bit (1 bit) 264 o Payload Type (7 bits) 266 o Timestamp (32 bits) 268 o Natural binary representation of the length of the CSRC List 269 plus padding plus payload plus extension of the media packet 270 (16 bits) 272 o CSRC List (if CC is 1), else null (variable) 274 o Header Extension (if X is 1), else null (variable) 276 o the payload (variable) 277 o Padding, if present (variable) 279 If the lengths of the binary arrays are not equal, they are padded 280 with zeroes to be the length of the longest binary array. If the 281 resulting binary arrays have a length which is not a multiple of the 282 symbol length, they are all padded further until they are a multiple 283 of the symbol length. 285 The Reed Solomon encoding operation is then applied to the K binary 286 arrays, generating N-K FEC arrays. Each FEC array is used to generate 287 a single FEC packet. 289 The first bit in the FEC packet binary array is written into the Pad- 290 ding Bit of the FEC packet. The second bit in the FEC packet binary 291 array is written into the Extension bit of the FEC packet. The next 292 three bits of the FEC packet binary array are written into the CC 293 field of the FEC packet. The next bit of the FEC packet binary array 294 is written into the marker bit of the FEC packet. The next 7 bits of 295 the FEC packet binary array are written into the PT recovery field in 296 the FEC packet header. The next 32 bits of the FEC packet binary 297 array are written into the TS recovery field in the packet header. 298 The next 16 bits are written into the Length Recovery field in the 299 FEC packet header. The remaining bits are set to be the payload of 300 the FEC packet. 302 8 Recovery Procedures 304 The FEC packets allow end systems to recover from the loss of media 305 packets. All of the header fields of the missing packets, including 306 CSRC lists, extensions, padding bits, marker and payload type, are 307 recoverable. This section describes the procedure for performing 308 this recovery. 310 Recovery requires two distinct operations. The first determines when 311 recovery should be attempted, based on the packets which have 312 arrived. The second is to actually perform the reconstruction. 314 The determination of when to recover is straightforward. For each 315 coding block, once K of the N packets in the block have arrived, 316 recovery can be attempted. Each FEC packet contains an FEC base, and 317 the value of K an N. Using these, it is easy to determine when K of N 318 packets have been received. 320 One approach for an implementation of this logic is to use linked 321 lists of packets. Each list is associated with two numbers: an SN 322 base and a value of K. When an FEC packet arrives, if there is no 323 list associated with its SN base field, a new list is created. Other- 324 wise, the FEC packet is placed in the list associated with that SN 325 base field. When a media packet arrives, its sequence number is 326 checked against each list. If its SN is between the SN base and SN 327 base plus K, the media packet is also placed in the list. Once a list 328 has K packets in it, recovery can be peformed. 330 8.1 Reconstruction 332 Reconstruction is possible when any K of the packets (media or FEC) 333 from the coding block have arrived. Let T be the list of packets (FEC 334 and media) which can be combined to recover some media packet xi. The 335 procedure is as follows: 337 1. For each of the media packets in T, compute the binary 338 array as described in the previous section. 340 2. For the FEC packets in T, compute the binary array in the 341 same fashion, except always set the CSRC list, extension, 342 and padding to null. 344 3. If the resulting K binary arrays are not of equal length, 345 pad them with zeroes to be the length of the longest binary 346 array. 348 4. If the lengths are not a multiple of the symbol length, pad 349 them until they are a multiple. 351 5. Apply the Reed Solomon operation to the K binary arrays. 352 This will result in N binary arrays, one of which is the 353 recovery array corresponding to the packet to be recovered. 355 6. Create a new packet with the standard 12 byte header and no 356 payload. 358 7. Set the version of the new packet to 2. 360 8. Set the Padding bit in the new packet to the first bit in 361 the recovery array. 363 9. Set the Extension bit in the new packet to the second bit 364 in the recovery array. 366 10. Set the CC field to the next three bits in the recovery 367 array. 369 11. Set the marker bit in the new packet to the next bit in the 370 recovery array. 372 12. Set the payload type in the new packet to the next 7 bits 373 in the recovery array. 375 13. Set the SN field in the new packet to xi. 377 14. Set the TS field in the new packet to the next 32 bits in 378 the recovery array. 380 15. Take the next 16 bits of the recovery array. Whatever the 381 natural binary number this corresponds to, take that many 382 bytes from the recovery array and append them to the new 383 packet. This represents the CSRC list, extension, payload, 384 and padding. 386 16. Set the SSRC of the new packet to the SSRC of the media 387 stream its protecting 389 This procedure will completely recover both the header and payload of 390 an RTP packet. 392 9 Use with Redundant Encodings 394 One can consider an FEC packet as a "redundant coding" of the media. 395 Because of this, the payload format for encoding of redundant audio 396 data [5] can be used to carry the FEC data along with the media. The 397 procedure for this is simple. In some media packet, the payload type 398 is set to the value for redundant encodings. The secondary coder is 399 then set to be the FEC data. This means that the PTI of the secondary 400 coder is set to the PTI value which indicates FEC. The block length 401 of the secondary coder is set to the length of the FEC header and 402 payload. The timestamp offset is set to the difference between the 403 media timestamp and the timestamp from the FEC packet. The secondary 404 coder payload includes the FEC header and FEC payload. 406 This procedure only works if an FEC packet is sent after the last of 407 the media packets in the media block has been sent. Otherwise, the 408 timestamp offset would be negative, which is not allowed. 410 Using the redundant encodings payload format also implies that the 411 marker bit cannot be recovered. 413 An advantage of this approach is a reduction in the overhead for 414 sending FEC packets. 416 10 Conclusion 418 This document has presented a new RTP payload format which allows for 419 Reed Solomon based forward error correction of audio visual media. It 420 is flexible, allowing nearly any Reed Solomon Code to be used. It is 421 also backwards compatible with existing RTP implementations. 422 Receivers which cannot understand FEC can discard the FEC packets, 423 and still receive the media packets. 425 11 Security Considerations 427 The use of FEC has implications on the usage and changing of keys for 428 encryption. As the FEC packets do consist of a separate stream, there 429 are a number of permutations on the usage of encryption. In particu- 430 lar: 432 o The FEC stream may be encrypted, while the media stream is 433 not. 435 o The media stream may be encrypted, while the FEC stream is 436 not. 438 o The media stream and FEC stream are both encrypted, but using 439 different keys. 441 o The media stream and FEC stream are both encrypted, but using 442 the same key. 444 The first three of these would require any application level signal- 445 ing protocols to be aware of the usage of FEC, and to thus exchange 446 keys for it and negotiate its usage on the media and FEC streams 447 separately. In the final case, no such additional mechanisms are 448 needed. Applications utilizing encryption SHOULD encrypt both 449 streams, however. Encrypting just one may make certain known- 450 plaintext attacks possible. 452 However, the changing of keys becomes problematic. For example, if 453 two packets a and b are sent, and FEC packet f(a,b) is sent, and the 454 keys used for a and b are different, which key should be used to 455 decode f(a,b)? In general, old keys will likely need to be cached, so 456 that when the keys change for the media stream, the old key is kept, 457 and used, until it is determined that the key has changed on the FEC 458 packets as well. 460 Another issue with the use of FEC is its impact on network conges- 461 tion. Adding FEC in the face of increasing network losses is a bad 462 idea, as it can lead to increased congestion and eventual congestion 463 collapse if done on a widespread basis. As a result, implementors 464 MUST NOT substantially increase the amount of FEC in use as network 465 losses increase. 467 12 Full Copyright Statement 468 Copyright (C) The Internet Society (1998). All Rights Reserved. 470 This document and translations of it may be copied and furnished to 471 others, and derivative works that comment on or otherwise explain it 472 or assist in its implmentation may be prepared, copied, published and 473 distributed, in whole or in part, without restriction of any kind, 474 provided that the above copyright notice and this paragraph are 475 included on all such copies and derivative works. 477 However, this document itself may not be modified in any way, such as 478 by removing the copyright notice or references to the Internet Soci- 479 ety or other Internet organizations, except as needed for the purpose 480 of developing Internet standards in which case the procedures for 481 copyrights defined in the Internet Standards process must be fol- 482 lowed, or as required to translate it into languages other than 483 English. 485 The limited permissions granted above are perpetual and will not be 486 revoked by the Internet Society or its successors or assigns. 488 This document and the information contained herein is provided on an 489 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 490 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 491 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 492 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MER- 493 CHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE." 495 13 Author's Addresses 497 Jonathan Rosenberg 498 Lucent Technologies, Bell Laboratories 499 101 Crawfords Corner Rd. 500 Holmdel, NJ 07733 501 Rm. 4C-526 502 email: jdrosen@bell-labs.com 504 Henning Schulzrinne 505 Columbia University 506 M/S 0401 507 1214 Amsterdam Ave. 508 New York, NY 10027-7003 509 email: schulzrinne@cs.columbia.edu 511 14 Bibliography 513 [1] J.-C. Bolot and A. Garcia, "The case for fec-based error control 514 for packet audio in the internet," Multimedia Systems , 1997. 516 [2] C. Perkins and C. Perkins, "Options for repair of streaming 517 media," Request for Comments (Informational) 2354, Internet Engineer- 518 ing Task Force, June 1998. 520 [3] J. Rosenberg and H. Schulzrinne, "An RTP payload format for gen- 521 eric forward error correction," Internet Draft, Internet Engineering 522 Task Force, Aug. 1998. Work in progress. 524 [4] L. Rizzo, "Erasure codes for computer communication protocols," 525 technical report, Universita di Pisa, Pisa, Italy, Jan. 1997. 527 [5] C. Perkins, I. Kouvelas, V. Hardman, M. Handley, and J. Bolot, 528 "RTP payload for redundant audio data," Request for Comments (Pro- 529 posed Standard) 2198, Internet Engineering Task Force, Sept. 1997.