Internet Engineering Task Force Tmima Koren Audio/Video Transport Working Group Patrick Ruddy INTERNET-DRAFT Andrew Johnson EXPIRES: February 2006 Cisco Systems July 2005 Packet reordering in Extended CRTP (ECRTP) draft-koren-avt-ecrtp-reorder-01.txt Status of this memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. This document is an Internet-Draft and is in full conformance with all provisions of Section 5 of RFC3667. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or cite them other than as "work in progress". The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/lid-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html Copyright Notice Copyright (C) The Internet Society (2005). All Rights Reserved. Abstract Extended RTP Header Compression (ECRTP) is tolerant to packet misordering. This document describes how ECRTP validates packets that arrive out of order. 1. Introduction A few Enhancements to CRTP (ECRTP) are defined in RFC3545. With these enhancements, CRTP performs well over links with packet loss, packet reordering and long delays. This document explains how to verify the decompression of out of order packets when using ECRTP. 1.1. Out of order packet validation Packets are not guaranteed to arrive at the destination in the same order they were sent. When using header compression, the decompressor might receive packets out of order. ECRTP uses the twice algorithm to reconstruct packets when there is packet loss or misordering, and verifies the validity of the reconstructed packet by calculating the UDP checksum or the header checksum of the packet and comparing to the checksum that was included in the compressed packet. The UDP checksum verifies all the fields in the packet except for the IP ID. Hence the validity of the IP ID in the reconstructed packet relies on the validity of the delta IP ID. If a packet arrives out of order by skipping a few packets, the validity of the IP ID is guaranteed up to N + 1 packets forward, where N is the link quality indicator used in ECRTP. When any delta field is changing, the change is repeated in N + 1 packets, so if the arriving packet is within N + 1 packets forward, either it includes a change in the IP ID, or the IP ID in the decompressor context is valid. If the packet includes a new delta IP ID, it also includes the IP ID. If the packet includes an update to the IP ID and the delta IP ID, twice may be applied even if the seq# skipped more than N + 1. If a packet arrives out of order backwards, the IP ID can be restored by remembering the last RTP sequence number where the delta IP ID has changed. Hence validation of out of order packets backwards depends on when the delta IP ID changed last. Note that in IPv6 there is no limit on the number of packets forward or backward that can be verified since there is no IP ID in the IPv6 IP header. 1.2 Extended context info - context history It is possible to add information to the context to increase the success rate of the twice algorithm backwards. In order to be able to twice m packets backwards, the context information of the last m seq# must be kept as follows: if the packet arrived and was accepted, then the context info is available. If a certain seq# did not arrive, then the context info for this seq# depends on the arrival of its neighboring packets. For example, if packet s arrived, then packet s + x arrives, then x - 1 seq# were skipped. Let's assume first that the arriving packet is within N + 1. If the arriving packet does not include any update, then the skipped packets also can't include updates, so their contexts are known. If the arriving packet does include updates, it can be decoded but it's not clear in which seq# the updates started, so the contexts of the skipped seq# are unknown, but when those seq# arrive with or without updates, their context info can be updated. Now let's assume that the skip is more than N + 1. In this case, if the arriving packet does not include the absolute IP ID, then the packet cannot be forwarded since the validity of the IP ID is not guaranteed. Optionally the packet could be stored for the case where the context becomes known at a later time. If the packet includes any other update, the update info can be kept in the seq# context. A CS should be sent to request context refresh. If the arriving packet does include the IP ID, then even though there is a skip larger than N + 1 twice can be applied, and if the checksum succeeds, the packet can be accepted and delivered, and the seq# context info for this seq# can be updated. But the contexts of the skipped seq# should remain indicating void info as a whole update sequence of the IP ID might have been lost there. Another optimization is to store the checksum in contexts that the checksum check failed. Usually it will be due to a loss of a whole update sequence. If the skipped packets arrive later with the update, twice can be reapplied and the checksum check for the failed context can be done again to check if it succeeds now. If there was also room to keep the payload, the packet can even be delivered to the IP layer. In summary, when a packet arrives skipping a few seq#, twice must be applied. The contexts below the arriving packet seq# are inspected, and the closest context below that has good info is selected for the twice. If there is enough info to twice and to validate the IP ID, the packet can be delivered. Otherwise a CS is sent and the packet is discarded or stored to be sent later if sufficient information becomes available. Note that in this method twice is always done forward. Also note that twice can always be applied in IPv6 (independent of N) since there is no IP ID in the IP header, and if the UDP checksum matches, the packet can be accepted. 1.3 Examples N=2 Within N + 1 Example 1: skip forward Order s update action S T dT I dI 1 1 101 2010 10 51 1 2 3 2 4 no twice 104 2040 10 54 1 Example 2: skip forward and backwards Order s update action S T dT I dI 1 1 101 2010 10 51 1 2 4 3 no twice 103 2030 10 53 1 2 4 I=66 twice 104 2040 10 66 1 5 6 3 7 no twice 107 2070 10 69 1 Note that for seq#7 twice is applied using the context at seq#4 where for seq#3 twice is applied using the context at seq#1 More than N + 1 Example 3: no update, send CS Order s update action S T dT I dI 1 1 101 2010 10 51 1 2 3 3 4 no twice 104 2040 10 54 1 2 5 no send CS(1), discard 4 6 no twice 106 2060 10 56 1 In this example seq#5 skipped more than N + 1 and does not include an update for I, so the packet can't be accepted and a CS(1) is sent notifying the compressor that the last good seq# that was received is seq#1. Before an update packet arrives, seq#3 arrives, and it is within N + 1 to context #1 so twice can be applied using context #1. Now seq#4 has a good context, so when seq#6 arrives twice can be applied again based on context #4 Example 4: Update I Order s update action S T dT I dI 1 1 101 2010 10 51 1 2 3 4 2 5 I=67 dI=2 twice: ok 105 2050 10 67 2 6 7 3 8 no twice 108 2080 10 73 2 In this example seq#5 skipped more than N + 1 but the packet includes updates to I and dI. Twice is applied using context #1 and succeeds. The packet is accepted since all the fields are verified by the checksum and the IP ID is valid. Packet #8 arrives and is twiced using context #5 Example 5: twice fails Order s update action S T dT I dI 1 1 101 2010 10 51 1 2 3 4 2 5 I=67 dI=2 twice: failed send CS(1), discard 3 6 I=69 dI=2 T=4000 twice 106 4000 10 69 2 7 8 4 9 no twice 109 4030 10 75 2 Even though there is an update to I in seq#5 twice based on seq#1 fails indicating that an update was lost during sequences 2-4. Then seq#6 arrives continuing the update of I and dI, and also updating T. We try again twice against seq#1 and succeed. Now seq#6 has a good context, so when seq#9 arrives it is twiced using seq#6. Eventually an update packet will arrive since a CS was sent at seq#5. Example 6: Update shows up late Order s update action S T dT I dI 1 1 101 2010 10 51 1 2 3 3 4 T=3000 twice 104 3000 10 54 1 2 5 I=67 dI=2 twice: failed send CS(1), discard 6 7 5 8 no twice 108 3040 10 73 2 4 9 I=75 dI=2 109 3050 10 75 2 Here again twice failed at seq#5 because the update of T that is included in the skipped seq#2-4 was lost. The checksum is kept in the context for later in case the skipped packets show up with the update. Then seq#4 arrives updating T. It is twiced using seq#1. The twice succeeds and the packet is accepted. At this point twice can be redone for seq#5. It succeeds, so now seq#5 has a good context. If the context of seq#5 also includes the payload, the packet of seq#5 can be delivered. Then seq#9 arrives with a large skip, but since it includes an update to I it is twiced using context #4 (or #5 if verified to be good) and accepted. Still it is not known if an update was lost during sequences 6-8. We'll find out when those packets show up. Then seq#8 arrives (without an update). Assuming that seq#5 was verified, twice can be applied for seq#8 using seq#5. 2. IANA Considerations This document does not require any assignments from IANA. 3. Security Considerations The security issues of this document are the same as [ECRTP]. 4. References Normative References [ECRTP] T. Koren, S. Casner, J. Geevarghese, B. Thompson, P. Ruddy, "Enhanced Compressed RTP (CRTP) for Links with High Delay, Packet Loss and Reordering", RFC3545, July 2003. [CRTP] S. Casner, V. Jacobson, "Compressing IP/UDP/RTP Headers for Low-Speed Serial Links", RFC 2508, February 1999. [TCRTP] B. Thompson, T. Koren, D. Wing, "Tunneling Multiplexed Compressed RTP ("TCRTP")", draft-ietf-avt-tcrtp-08.txt, September 2004. 5. Authors' Addresses Tmima Koren 170 West Tasman Drive San Jose, CA 95134-1706 United States of America Phone: +1 408 527 6169 Email: tmima@cisco.com Patrick Ruddy Cisco Systems, Inc. 3rd Floor 96 Commercial Street Leith, Edinburgh EH6 6LX Scotland EMail: pruddy@cisco.com Andrew Johnson Cisco Systems, Inc. 3rd Floor 96 Commercial Street Leith, Edinburgh EH6 6LX Scotland EMail: andrjohn@cisco.com 6. Copyright Notice Copyright (C) The Internet Society (2005). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. 7. Disclaimers This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf- ipr@ietf.org.