High Availability within a Forwarding and Control Element Separation (ForCES) Network Element
RFC 7121
Document | Type |
RFC
- Proposed Standard
(February 2014)
Errata
Updated by RFC 7391
Updates RFC 5810
|
|
---|---|---|---|
Authors | Kentaro Ogawa , Weiming Wang , Evangelos Haleplidis , Jamal Hadi Salim | ||
Last updated | 2019-03-30 | ||
RFC stream | Internet Engineering Task Force (IETF) | ||
Formats | |||
Additional resources | Mailing list discussion | ||
IESG | Responsible AD | Adrian Farrel | |
Send notices to | (None) |
RFC 7121
Network Working Group D. Korn Request for Comments: 3284 AT&T Labs Category: Standards Track J. MacDonald UC Berkeley J. Mogul Hewlett-Packard Company K. Vo AT&T Labs June 2002 The VCDIFF Generic Differencing and Compression Data Format Status of this Memo This document specifies an Internet standards track protocol for the Internet community, and requests discussion and suggestions for improvements. Please refer to the current edition of the "Internet Official Protocol Standards" (STD 1) for the standardization state and status of this protocol. Distribution of this memo is unlimited. Copyright Notice Copyright (C) The Internet Society (2002). All Rights Reserved. Abstract This memo describes VCDIFF, a general, efficient and portable data format suitable for encoding compressed and/or differencing data so that they can be easily transported among computers. Korn, et. al. Standards Track [Page 1] RFC 3284 VCDIFF June 2002 Table of Contents 1. Executive Summary ........................................... 2 2. Conventions ................................................. 4 3. Delta Instructions .......................................... 5 4. Delta File Organization ..................................... 6 5. Delta Instruction Encoding .................................. 12 6. Decoding a Target Window .................................... 20 7. Application-Defined Code Tables ............................. 21 8. Performance ................................................. 22 9. Further Issues .............................................. 24 10. Summary ..................................................... 25 11. Acknowledgements ............................................ 25 12. Security Considerations ..................................... 25 13. Source Code Availability .................................... 25 14. Intellectual Property Rights ................................ 26 15. IANA Considerations ......................................... 26 16. References .................................................. 26 17. Authors' Addresses .......................................... 28 18. Full Copyright Statement .................................... 29 1. Executive Summary Compression and differencing techniques can greatly improve storage and transmission of files and file versions. Since files are often transported across machines with distinct architectures and performance characteristics, such data should be encoded in a form that is portable and can be decoded with little or no knowledge of the encoders. This document describes Vcdiff, a compact portable encoding format designed for these purposes. Data differencing is the process of computing a compact and invertible encoding of a "target file" given a "source file". Data compression is similar, but without the use of source data. The UNIX utilities diff, compress, and gzip are well-known examples of data differencing and compression tools. For data differencing, the computed encoding is called a "delta file", and for data compression, it is called a "compressed file". Delta and compressed files are good for storage and transmission as they are often smaller than the originals. Data differencing and data compression are traditionally treated as distinct types of data processing. However, as shown in the Vdelta technique by Korn and Vo [1], compression can be thought of as a special case of differencing in which the source data is empty. The basic idea is to unify the string parsing scheme used in the Lempel- Ziv'77 (LZ'77) style compressors [2] and the block-move technique of Tichy [3]. Loosely speaking, this works as follows: Korn, et. al. Standards Track [Page 2] RFC 3284 VCDIFF June 2002 a. Concatenate source and target data. b. Parse the data from left to right as in LZ'77 but make sure that a parsed segment starts the target data. c. Start to output when reaching target data. Parsing is based on string matching algorithms, such as suffix trees [4] or hashing with different time and space performance characteristics. Vdelta uses a fast string matching algorithm that requires less memory than other techniques [5,6]. However, even with this algorithm, the memory requirement can still be prohibitive for large files. A common way to deal with memory limitation is to partition an input file into chunks called "windows" and process them separately. Here, except for unpublished work by Vo, little has been done on designing effective windowing schemes. Current techniques, including Vdelta, simply use source and target windows with corresponding addresses across source and target files. String matching and windowing algorithms have great influence on the compression rate of delta and compressed files. However, it is desirable to have a portable encoding format that is independent of such algorithms. This enables the construction of client-server applications in which a server may serve clients with unknown computing characteristics. Unfortunately, all current differencing and compressing tools, including Vdelta, fall short in this respect. Their storage formats are closely intertwined with the implemented string matching and/or windowing algorithms. The encoding format Vcdiff proposed here addresses the above issues. Vcdiff achieves the characteristics below: Output compactness: The basic encoding format compactly represents compressed or delta files. Applications can further extend the basic encoding format with "secondary encodersRFC 7121 ForCES Intra-NE High Availability February 2014 configuration plane (FEM). In the pre-association phase, the first CE (lowest table index) in the AllCEs table MUST be the first CE with which the FE will attempt to connect and associate. If the FE fails to connect and associate with the first listed CE, it will attempt to connect to the second CE and so forth, and it cycles back to the beginning of the list until there is a successful association. The FE MUST associate with at least one CE. Upon a successful association, a component of the FEPO LFB, specifically the CEID component, identifies the current associated master CE. While it would be much simpler to have the FE not respond to any messages from a CE other than the master, in practice it has been found to be useful to respond to queries and heartbeats from backup CEs. For this reason, we allow backup CEs to issue queries to the FE. Configuration messages (SET/DEL) from backup CEs MUST be dropped by the FE and logged as received errors. Asynchronous events that the master CE has subscribed to, as well as heartbeats, are sent to all associated CEs. Packet redirects continue to be sent only to the master CE. The Heartbeat Interval, the CE Heartbeat (CEHB) policy, and the FE Heartbeat (FEHB) policy are global for all CEs (and changed only by the master CE). Figure 4 illustrates the state machine that facilitates connection recovery with HA enabled. Ogawa, et al. Standards Track [Page 14] RFC 7121 ForCES Intra-NE High Availability February 2014 FE tries to associate +-->-----+ | | (CE changes master || | | CE issues Teardown || +---+--------v----+ Lost association) && | Pre-association | CE failover policy = 0 | (Association | +------------>-->-->| in +<----+ | | progress) | | | | | | | +--------+--------+ | | CE Association | | CEFTI | Response V | timer | +------------------+ | expires | |FE issues CEPrimaryDown ^ | |FE issues PrimaryCEChanged ^ | V | +-+-----------+ +------+-----+ | | (CE changes master || | Not | | | CE issues Teardown || | Associated | | | Lost association) && | +->----------+ | Associated | CE failover policy = 1 |(May | find first | | | | Continue | associated v | |-------->------->------>| Forwarding)| CE or retry| | | Start CEFTI timer | | associating| | | | |-<----------+ | | | | +----+--------+ +-------+----+ | | ^ Found | associated CE | or newly | associated CE | V | (Cancel CEFTI timer) | +_________________________________________+ FE issues CEPrimaryDown event FE issues PrimaryCEChanged event Figure 4: FE State Machine Considering HA Once the FE has associated with a master CE, it moves to the post- association phase (associated state). It is assumed that the master CE will communicate with other CEs within the NE for the purpose of synchronization via the CE-CE interface. The CE-CE interface is out of scope for this document. An election result amongst CEs may result in the desire to change the mastership to a different associated CE; at which point, the current assumed master CE will instruct the FE to use a different master CE. Ogawa, et al. Standards Track [Page 15] RFC 7121 ForCES Intra-NE High Availability February 2014 FE CE#1 CE#2 ... CE#N | | | | | Association Establishment | | | | Capabilities Exchange | | | 1 |<------------------------->| | | | | | | | State Update | | | 2 |<------------------------->| | | | | | | | Association Establishment | | | Capabilities Exchange | | 3I|<-------------------------------------->| | ... ... ... ... |Association Establishment, Capabilities Exchange | 3N|<----------------------------------------------->| | | | | 4 |<------------------------->| | | . . . . 4x|<------------------------->| | | | FAILURE | | | | | | | Event Report (LastCEID changed) | | 5 |--------------------------------------->|------->| | Event Report (CE#2 is new master) | | 6 |--------------------------------------->|------->| | | | 7 |<-------------------------------------->| | . . . . 7x|<-------------------------------------->| | . . . . Figure 5: CE Failover for Hot Standby While in the post-association phase, if the CE failover policy is set to 1 and the HAMode is set to 2 (hot standby), then the FE, after successfully associating with the master CE, MUST attempt to connect and associate with all the CEs of which it is aware. Figure 5, steps #1 and #2 illustrates the FE associating with CE#1 as the master, and then proceeding to steps #3I to #3N, it shows the association with backup CEs CE#2 to CE#N. If the FE fails to connect or associate with some CEs, the FE MAY flag them as unreachable to avoid continuous attempts to connect. The FE MAY try to re-associate with unreachable CEs when possible. When the master CE, for any reason, is considered to be down, then the FE MUST try to find the first associated CE from the list of all CEs in a round-robin fashion. Ogawa, et al. Standards Track [Page 16] RFC 7121 ForCES Intra-NE High Availability February 2014 If the FE is unable to find an associated FE in its list of CEs, then it MUST attempt to connect and associate with the first from the list of all CEs and continue in a round-robin fashion until it connects and associates with a CE or the CEFTI timer expires. Once the FE selects an associated CE to use as the new master, the FE issues a PrimaryCEDown Event Notification to all associated CEs to notify them that the last primary CE went down (and what its identity was); a second event, PrimaryCEChanged, identifying the new master CE is sent as well to identify which CE the reporting FE considers to be the new master. In most HA architectures, there exists the possibility of split brain. However, in our setup, since the FE will never accept any configuration messages from any other than the master CE, we consider the FE to be fenced against data corruption from the other CEs that consider themselves as the master. The split-brain issue becomes mostly a CE-CE communication problem, which is considered to be out of scope. By virtue of having multiple CE connections, the FE switchover to a new master CE will be relatively much faster. The overall effect is improving the NE recovery time in case of communication failure or faults of the master CE. This satisfies the requirement we set to fulfill. 4. IANA Considerations Following the policies outlined in "Guidelines for Writing an IANA Considerations Section in RFCs" [RFC5226], the "Logical Functional Block (LFB) Class Names and Class Identifiers" namespace has been updated. A new column, LFB version, has been added to the table after the LFB Class Name. The table now reads as follows: +----------------+------------+-----------+-------------+-----------+ | LFB Class | LFB Class | LFB | Description | Reference | | Identifier | Name | Version | | | +----------------+------------+-----------+-------------+-----------+ Logical Functional Block (LFB) Class Names and Class Identifiers The rules defined in [RFC5812] apply, with the addition that entries must provide the LFB version as a string. Ogawa, et al. Standards Track [Page 17] RFC 7121 ForCES Intra-NE High Availability February 2014 Upon publication of this document, all current entries are assigned a value of 1.0. New versions of already defined LFBs MUST NOT remove the previous version entries. It would make sense to have LFB versions appear in sequence in the registry. The table SHOULD be sorted, and the sorting should be done by Class ID first and then by version. This document introduces the FE Protocol Object version 1.1 as follows: +------------+----------+---------+---------------------+-----------+ | LFB Class | LFB | LFB | Description | Reference | | Identifier | Class | Version | | | | | Name | | | | +------------+----------+---------+---------------------+-----------+ | 2 | FE | 1.1 | Defines parameters | [RFC7121] | | | Protocol | | for the ForCES | | | | Object | | protocol operation | | +------------+----------+---------+---------------------+-----------+ Logical Functional Block (LFB) Class Names and Class Identifiers 5. Security Considerations Security considerations, as defined in Section 9 of [RFC5810], apply to securing each CE-FE communication. Multiple CEs associated with the same FE still require the same procedure to be followed on a per- association basis. It should be noted that since the FE is initiating the association with a CE, a CE cannot initiate association with the FE and such messages will be dropped. Thus, the FE is secured from rogue CEs that are attempting to associate with it. CE implementers should have in mind that once associated, the FE cannot distinguish whether the CE has been compromised or has been malfunctioning while not losing connectivity. Securing the CE is out of scope of this document. While the CE-CE plane is outside the current scope of ForCES, we recognize that it may be subjected to attacks that may affect the CE- FE communication. Ogawa, et al. Standards Track [Page 18] RFC 7121 ForCES Intra-NE High Availability February 2014 The following considerations should be made: 1. Secure communication channels should be used between CEs for coordination and keeping of state to at least avoid connection of malicious CEs. 2. The master CE should take into account DoS and Distributed Denial-of-Service (DDoS) attacks from malicious or malfunctioning CEs. 3. CEs should take into account the split-brain issue. There are currently two fail-safes in the FE: Firstly, the FE has the CEID component that denotes which CE is the master. Secondly, the FE does not allow BackupCEs to configure the FE. However, backup CEs that consider that the master CE has dropped should, as masters themselves, first do a sanity check and query the FE CEID component. 6. References 6.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 5226, May 2008. [RFC5810] Doria, A., Hadi Salim, J., Haas, R., Khosravi, H., Wang, W., Dong, L., Gopal, R., and J. Halpern, "Forwarding and Control Element Separation (ForCES) Protocol Specification", RFC 5810, March 2010. [RFC5812] Halpern, J. and J. Hadi Salim, "Forwarding and Control Element Separation (ForCES) Forwarding Element Model", RFC 5812, March 2010. 6.2. Informative References [Err3487] RFC Errata, Errata ID 3487, RFC 5812, <http://www.rfc-editor.org>. [RFC3654] Khosravi, H. and T. Anderson, "Requirements for Separation of IP Control and Forwarding", RFC 3654, November 2003. Ogawa, et al. Standards Track [Page 19] RFC 7121 ForCES Intra-NE High Availability February 2014 [RFC3746] Yang, L., Dantu, R., Anderson, T., and R. Gopal, "Forwarding and Control Element Separation (ForCES) Framework", RFC 3746, April 2004. Ogawa, et al. Standards Track [Page 20] RFC 7121 ForCES Intra-NE High Availability February 2014 Appendix A. New FEPO Version The xml has been validated against the schema defined in [RFC5812]. <LFBLibrary xmlns="urn:ietf:params:xml:ns:forces:lfbmodel:1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:noNamespaceSchemaLocation="lfb-schema.xsd" provides="FEPO"> <!-- XXX --> <dataTypeDefs> <dataTypeDef> <name>CEHBPolicyValues</name> <synopsis> The possible values of the CE Heartbeat policy </synopsis> <atomic> <baseType>uchar</baseType> <specialValues> <specialValue value="0"> <name>CEHBPolicy0</name> <synopsis> The CE will send heartbeats to the FE every CEHDI timeout if no other messages have been sent since. </synopsis> </specialValue> <specialValue value="1"> <name>CEHBPolicy1</name> <synopsis> The CE will not send heartbeats to the FE </synopsis> </specialValue> </specialValues> </atomic> </dataTypeDef> <dataTypeDef> <name>FEHBPolicyValues</name> <synopsis> The possible values of the FE Heartbeat policy </synopsis> <atomic> <baseType>uchar</baseType> <specialValues> <specialValue value="0"> <name>FEHBPolicy0</name> <synopsis> The FE will not generate any heartbeats to the CE </synopsis> </specialValue> Ogawa, et al. Standards Track [Page 21] RFC 7121 ForCES Intra-NE High Availability February 2014 <specialValue value="1"> <name>FEHBPolicy1</name> <synopsis> The FE generates heartbeats to the CE every FEHI if no other messages have been sent to the CE. </synopsis> </specialValue> </specialValues> </atomic> </dataTypeDef> <dataTypeDef> <name>FERestartPolicyValues</name> <synopsis> The possible values of the FE restart policy </synopsis> <atomic> <baseType>uchar</baseType> <specialValues> <specialValue value="0"> <name>FERestartPolicy0</name> <synopsis> The FE restarts its state from scratch </synopsis> </specialValue> </specialValues> </atomic> </dataTypeDef> <dataTypeDef> <name>HAModeValues</name> <synopsis> The possible values of HA modes </synopsis> <atomic> <baseType>uchar</baseType> <specialValues> <specialValue value="0"> <name>NoHA</name> <synopsis> The FE is not running in HA mode </synopsis> </specialValue> <specialValue value="1"> <name>ColdStandby</name> <synopsis> The FE is running in HA mode cold standby </synopsis> </specialValue> <specialValue value="2"> Ogawa, et al. Standards Track [Page 22] RFC 7121 ForCES Intra-NE High Availability February 2014 <name>HotStandby</name> <synopsis> The FE is running in HA mode hot standby </synopsis> </specialValue> </specialValues> </atomic> </dataTypeDef> <dataTypeDef> <name>CEFailoverPolicyValues</name> <synopsis> The possible values of the CE failover policy </synopsis> <atomic> <baseType>uchar</baseType> <specialValues> <specialValue value="0"> <name>CEFailoverPolicy0</name> <synopsis> The FE should stop functioning immediately and transition to the FE OperDisable state </synopsis> </specialValue> <specialValue value="1"> <name>CEFailoverPolicy1</name> <synopsis> The FE should continue forwarding even without an associated CE for CEFTI. The FE goes to FE OperDisable when the CEFTI expires and there is no association. Requires graceful restart support. </synopsis> </specialValue> </specialValues> </atomic> </dataTypeDef> <dataTypeDef> <name>FEHACapab</name> <synopsis> The supported HA features </synopsis> <atomic> <baseType>uchar</baseType> <specialValues> <specialValue value="0"> <name>GracefullRestart</name> <synopsis> The FE supports graceful restart </synopsis> Ogawa, et al. Standards Track [Page 23] RFC 7121 ForCES Intra-NE High Availability February 2014 </specialValue> <specialValue value="1"> <name>HA</name> <synopsis> The FE supports HA </synopsis> </specialValue> </specialValues> </atomic> </dataTypeDef> <dataTypeDef> <name>CEStatusType</name> <synopsis>Status values. Status for each CE</synopsis> <atomic> <baseType>uchar</baseType> <specialValues> <specialValue value="0"> <name>Disconnected</name> <synopsis>No connection attempt with the CE yet </synopsis> </specialValue> <specialValue value="1"> <name>Connected</name> <synopsis>The FE connection with the CE at the TML has been completed </synopsis> </specialValue> <specialValue value="2"> <name>Associated</name> <synopsis>The FE has associated with the CE </synopsis> </specialValue> <specialValue value="3"> <name>IsMaster</name> <synopsis>The CE is the master (and associated) </synopsis> </specialValue> <specialValue value="4"> <name>LostConnection</name> <synopsis>The FE was associated with the CE but lost the connection </synopsis> </specialValue> <specialValue value="5"> <name>Unreachable</name> <synopsis>The CE is deemed as unreachable by the FE </synopsis> </specialValue> Ogawa, et al. Standards Track [Page 24] RFC 7121 ForCES Intra-NE High Availability February 2014 </specialValues> </atomic> </dataTypeDef> <dataTypeDef> <name>StatisticsType</name> <synopsis>Statistics Definition</synopsis> <struct> <component componentID="1"> <name>RecvPackets</name> <synopsis>Packets received</synopsis> <typeRef>uint64</typeRef> </component> <component componentID="2"> <name>RecvErrPackets</name> <synopsis>Packets received from the CE with errors </synopsis> <typeRef>uint64</typeRef> </component> <component componentID="3"> <name>RecvBytes</name> <synopsis>Bytes received from the CE</synopsis> <typeRef>uint64</typeRef> </component> <component componentID="4"> <name>RecvErrBytes</name> <synopsis>Bytes received from the CE in Error</synopsis> <typeRef>uint64</typeRef> </component> <component componentID="5"> <name>TxmitPackets</name> <synopsis>Packets transmitted to the CE</synopsis> <typeRef>uint64</typeRef> </component> <component componentID="6"> <name>TxmitErrPackets</name> <synopsis> Packets transmitted to the CE that incurred errors </synopsis> <typeRef>uint64</typeRef> </component> <component componentID="7"> <name>TxmitBytes</name> <synopsis>Bytes transmitted to the CE</synopsis> <typeRef>uint64</typeRef> </component> &" to achieve more compression. Data portability: The basic encoding format is free from machine byte order and word size issues. This allows data to be encoded on one machine and decoded on a different machine with different architecture. Algorithm genericity: The decoding algorithm is independent from string matching and windowing algorithms. This allows competition among implementations of the encoder while keeping the same decoder. Korn, et. al. Standards Track [Page 3] RFC 3284 VCDIFF June 2002 Decoding efficiency: Except for secondary encoder issues, the decoding algorithm runs in time proportionate to the size of the target file and uses space proportionate to the maximal window size. Vcdiff differs from more conventional compressors in that it uses only byte-aligned data, thus avoiding bit-level operations, which improves decoding speed at the slight cost of compression efficiency. The combined differencing and compression method is called "delta compression" [14]. As this way of data processing treats compression as a special case of differencing, we shall use the term "delta file" to indicate the compressed output for both cases. 2. Conventions The basic data unit is a byte. For portability, Vcdiff shall limit a byte to its lower eight bits even on machines with larger bytes. The bits in a byte are ordered from right to left so that the least significant bit (LSB) has value 1, and the most significant bit (MSB), has value 128. For purposes of exposition in this document, we adopt the convention that the LSB is numbered 0, and the MSB is numbered 7. Bit numbers never appear in the encoded format itself. Vcdiff encodes unsigned integer values using a portable, variable- sized format (originally introduced in the Sfio library [7]). This encoding treats an integer as a number in base 128. Then, each digit in this representation is encoded in the lower seven bits of a byte. Except for the least significant byte, other bytes have their most significant bit turned on to indicate that there are still more digits in the encoding. The two key properties of this integer encoding that are beneficial to a data compression format are: a. The encoding is portable among systems using 8-bit bytes, and b. Small values are encoded compactly. For example, consider the value 123456789, which can be represented with four 7-bit digits whose values are 58, 111, 26, 21 in order from most to least significant. Below is the 8-bit byte encoding of these digits. Note that the MSBs of 58, 111 and 26 are on. +-------------------------------------------+ | 10111010 | 11101111 | 10011010 | 00010101 | +-------------------------------------------+ MSB+58 MSB+111 MSB+26 0+21 Korn, et. al. Standards Track [Page 4] RFC 3284 VCDIFF June 2002 Henceforth, the terms "byte" and "integer" will refer to a byte and an unsigned integer as described. Algorithms in the C language are occasionally exhibited to clarify the descriptions. Such C code is meant for clarification only, and is not part of the actual specification of the Vcdiff format. The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14, RFC 2119 [12]. 3. Delta Instructions A large target file is partitioned into non-overlapping sections called "target windows". These target windows are processed separately and sequentially based on their order in the target file. A target window T, of length t, may be compared against some source data segment S, of length s. By construction, this source data segment S comes either from the source file, if one is used, or from a part of the target file earlier than T. In this way, during decoding, S is completely known when T is being decoded. The choices of T, t, S and s are made by some window selection algorithm, which can greatly affect the size of the encoding. However, as seen later, these choices are encoded so that no knowledge of the window selection algorithm is needed during decoding. Assume that S[j] represents the jth byte in S, and T[k] represents the kth byte in T. Then, for the delta instructions, we treat the data windows S and T as substrings of a superstring U, formed by concatenating them like this: S[0]S[1]...S[s-1]T[0]T[1]...T[t-1] The "address" of a byte in S or T is referred to by its location in U. For example, the address of T[k] is s+k. The instructions to encode and direct the reconstruction of a target window are called delta instructions. There are three types: ADD: This instruction has two arguments, a size x and a sequence of x bytes to be copied. COPY: This instruction has two arguments, a size x and an address p in the string U. The arguments specify the substring of U that must be copied. We shall assert that such a substring must be entirely contained in either S or T. Korn, et. al. Standards Track [Page 5] RFC 3284 VCDIFF June 2002 RUN: This instruction has two arguments, a size x and a byte b, that will be repeated x times. Below are example source and target windows and the delta instructions that encode the target window in terms of the source window. a b c d e f g h i j k l m n o p a b c d w x y z e f g h e f g h e f g h e f g h z z z z COPY 4, 0 ADD 4, w x y z COPY 4, 4 COPY 12, 24 RUN 4, z Thus, the first letter 'a' in the target window is at location 16 in the superstring. Note that the fourth instruction, "COPY 12, 24", copies data from T itself since address 24 is position 8 in T. This instruction also shows that it is fine to overlap the data to be copied with the data being copied from, as long as the latter starts earlier. This enables efficient encoding of periodic sequences, i.e., sequences with regularly repeated subsequences. The RUN instruction is a compact way to encode a sequence repeating the same byte even though such a sequence can be thought of as a periodic sequence with period 1. To reconstruct the target window, one simply processes one delta instruction at a time and copies the data, either from the source window or the target window being reconstructed, based on the type of the instruction and the associated address, if any. 4. Delta File Organization A Vcdiff delta file starts with a Header section followed by a sequence of Window sections. The Header section includes magic bytes to identify the file type, and information concerning data processing beyond the basic encoding format. The Window sections encode the target windows. Below is the overall organization of a delta file. The indented items refine the ones immediately above them. An item in square brackets may or may not be present in the file depending on the information encoded in the Indicator byte above it. Korn, et. al. Standards Track [Page 6] RFC 3284 VCDIFF June 2002 Header Header1 - byte Header2 - byte Header3 - byte Header4 - byte Hdr_Indicator - byte [Secondary compressor ID] - byte [Length of code table data] - integer [Code table data] Size of near cache - byte Size of same cache - byte Compressed code table data Window1 Win_Indicator - byte [Source segment size] - integer [Source segment position] - integer The delta encoding of the target window Length of the delta encoding - integer The delta encoding Size of the target window - integer Delta_Indicator - byte Length of data for ADDs and RUNs - integer Length of instructions and sizes - integer Length of addresses for COPYs - integer Data section for ADDs and RUNs - array of bytes Instructions and sizes section - array of bytes Addresses section for COPYs - array of bytes Window2 ... 4.1 The Header Section Each delta file starts with a header section organized as below. Note the convention that square-brackets enclose optional items. Header1 - byte = 0xD6 Header2 - byte = 0xC3 Header3 - byte = 0xC4 Header4 - byte Hdr_Indicator - byte [Secondary compressor ID] - byte [Length of code table data] - integer [Code table data] Korn, et. al. Standards Track [Page 7] RFC 3284 VCDIFF June 2002 The first three Header bytes are the ASCII characters 'V', 'C' and 'D' with their most significant bits turned on (in hexadecimal, the values are 0xD6, 0xC3, and 0xC4). The fourth Header byte is currently set to zero. In the future, it might be used to indicate the version of Vcdiff. The Hdr_Indicator byte shows if there is any initialization data required to aid in the reconstruction of data in the Window sections. This byte MAY have non-zero values for either, both, or neither of the two bits VCD_DECOMPRESS and VCD_CODETABLE below: 7 6 5 4 3 2 1 0 +-+-+-+-+-+-+-+-+ | | | | | | | | | +-+-+-+-+-+-+-+-+ ^ ^ | | | +-- VCD_DECOMPRESS +---- VCD_CODETABLE If bit 0 (VCD_DECOMPRESS) is non-zero, this indicates that a secondary compressor may have been used to further compress certain parts of the delta encoding data as described in Sections 4.3 and 6. In that case, the ID of the secondary compressor is given next. If this bit is zero, the compressor ID byte is not included. If bit 1 (VCD_CODETABLE) is non-zero, this indicates that an application-defined code table is to be used for decoding the delta instructions. This table itself is compressed. The length of the data comprising this compressed code table and the data follow next. Section 7 discusses application-defined code tables. If this bit is zero, the code table data length and the code table data are not included. If both bits are set, then the compressor ID byte is included before the code table data length and the code table data. 4.2 The Format of a Window Section Each Window section is organized as follows: Win_Indicator - byte [Source segment length] - integer [Source segment position] - integer The delta encoding of the target window Korn, et. al. Standards Track [Page 8] RFC 3284 VCDIFF June 2002 Below are the details of the various items: Win_Indicator: This byte is a set of bits, as shown: 7 6 5 4 3 2 1 0 +-+-+-+-+-+-+-+-+ | | | | | | | | | +-+-+-+-+-+-+-+-+ ^ ^ | | | +-- VCD_SOURCE +---- VCD_TARGET If bit 0 (VCD_SOURCE) is non-zero, this indicates that a segment of data from the "source" file was used as the corresponding source window of data to encode the target window. The decoder will use this same source data segment to decode the target window. If bit 1 (VCD_TARGET) is non-zero, this indicates that a segment of data from the "target" file was used as the corresponding source window of data to encode the target window. As above, this same source data segment is used to decode the target window. The Win_Indicator byte MUST NOT have more than one of the bits set (non-zero). It MAY have none of these bits set. If one of these bits is set, the byte is followed by two integers to indicate respectively, the length and position of the source data segment in the relevant file. If the indicator byte is zero, the target window was compressed by itself without comparing against another data segment, and these two integers are not included. The delta encoding of the target window: This contains the delta encoding of the target window, either in terms of the source data segment (i.e., VCD_SOURCE or VCD_TARGET was set) or by itself if no source window is specified. This data format is discussed next. lt;component componentID="8"> <name>TxmitErrBytes</name> Ogawa, et al. Standards Track [Page 25] RFC 7121 ForCES Intra-NE High Availability February 2014 <synopsis> Bytes transmitted to the CE that incurred errors </synopsis> <typeRef>uint64</typeRef> </component> </struct> </dataTypeDef> <dataTypeDef> <name>AllCEType</name> <synopsis>Table type for the AllCE component</synopsis> <struct> <component componentID="1"> <name>CEID</name> <synopsis>ID of the CE</synopsis> <typeRef>uint32</typeRef> </component> <component componentID="2"> <name>Statistics</name> <synopsis>Statistics per the CE</synopsis> <typeRef>StatisticsType</typeRef> </component> <component componentID="3"> <name>CEStatus</name> <synopsis>Status of the CE</synopsis> <typeRef>CEStatusType</typeRef> </component> </struct> </dataTypeDef> </dataTypeDefs> <LFBClassDefs> <LFBClassDef LFBClassID="2"> <name>FEPO</name> <synopsis> The FE Protocol Object, with new CEHA </synopsis> <version>1.1</version> <components> <component componentID="1" access="read-only"> <name>CurrentRunningVersion</name> <synopsis>Currently running the ForCES version</synopsis> <typeRef>uchar</typeRef> </component> <component componentID="2" access="read-only"> <name>FEID</name> <synopsis>Unicast FEID</synopsis> <typeRef>uint32</typeRef> </component> Ogawa, et al. Standards Track [Page 26] RFC 7121 ForCES Intra-NE High Availability February 2014 <component componentID="3" access="read-write"> <name>MulticastFEIDs</name> <synopsis> The table of all multicast IDs </synopsis> <array type="variable-size"> <typeRef>uint32</typeRef> </array> </component> <component componentID="4" access="read-write"> <name>CEHBPolicy</name> <synopsis> The CE Heartbeat policy </synopsis> <typeRef>CEHBPolicyValues</typeRef> &Korn, et. al. Standards Track [Page 9] RFC 3284 VCDIFF June 2002 4.3 The Delta Encoding of a Target Window The delta encoding of a target window is organized as follows: Length of the delta encoding - integer The delta encoding Length of the target window - integer Delta_Indicator - byte Length of data for ADDs and RUNs - integer Length of instructions section - integer Length of addresses for COPYs - integer Data section for ADDs and RUNs - array of bytes Instructions and sizes section - array of bytes Addresses section for COPYs - array of bytes Length of the delta encoding: This integer gives the total number of remaining bytes that comprise the data of the delta encoding for this target window. The delta encoding: This contains the data representing the delta encoding which is described next. Length of the target window: This integer indicates the actual size of the target window after decompression. A decoder can use this value to allocate memory to store the uncompressed data. Delta_Indicator: This byte is a set of bits, as shown: 7 6 5 4 3 2 1 0 +-+-+-+-+-+-+-+-+ | | | | | | | | | +-+-+-+-+-+-+-+-+ ^ ^ ^ | | | | | +-- VCD_DATACOMP | +---- VCD_INSTCOMP +------ VCD_ADDRCOMP VCD_DATACOMP: bit value 1. VCD_INSTCOMP: bit value 2. VCD_ADDRCOMP: bit value 4. Korn, et. al. Standards Track [Page 10] RFC 3284 VCDIFF June 2002 As discussed, the delta encoding consists of COPY, ADD and RUN instructions. The ADD and RUN instructions have accompanying unmatched data (that is, data that does not specifically match any data in the source window or in some earlier part of the target window) and the COPY instructions have addresses of where the matches occur. OPTIONALLY, these types of data MAY be further compressed using a secondary compressor. Thus, Vcdiff separates the encoding of the delta instructions into three parts: a. The unmatched data in the ADD and RUN instructions, b. The delta instructions and accompanying sizes, and c. The addresses of the COPY instructions. If the bit VCD_DECOMPRESS (Section 4.1) was on, each of these sections may have been compressed using the specified secondary compressor. The bit positions 0 (VCD_DATACOMP), 1 (VCD_INSTCOMP), and 2 (VCD_ADDRCOMP) respectively indicate, if non-zero, that the corresponding parts are compressed. Then, these parts MUST be decompressed before decoding the delta instructions. Length of data for ADDs and RUNs: This is the length (in bytes) of the section of data storing the unmatched data accompanying the ADD and RUN instructions. Length of instructions section: This is the length (in bytes) of the delta instructions and accompanying sizes. Length of addresses for COPYs: This is the length (in bytes) of the section storing the addresses of the COPY instructions. Data section for ADDs and RUNs: This sequence of bytes encodes the unmatched data for the ADD and RUN instructions. Instructions and sizes section: This sequence of bytes encodes the instructions and their sizes. Addresses section for COPYs: This sequence of bytes encodes the addresses of the COPY instructions. Korn, et. al. Standards Track [Page 11] RFC 3284 VCDIFF June 2002 5. Delta Instruction Encoding The delta instructions described in Section 3 represent the results of string matching. For many data differencing applications in which the changes between source and target data are small, any straightforward representation of these instructions would be adequate. However, for applications including differencing of binary files or data compression, it is important to encode these instructions well to achieve good compression rates. The keys to this achievement is to efficiently encode the addresses of COPY instructions and the sizes of all delta instructions. 5.1 Address Encoding Modes of COPY Instructions Addresses of COPY instructions are locations of matches and often occur close by or even exactly equal to one another. This is because data in local regions are often replicated with minor changes. In turn, this means that coding a newly matched address against some recently matched addresses can be beneficial. To take advantage of this phenomenon and encode addresses of COPY instructions more efficiently, the Vcdiff data format supports the use of two different types of address caches. Both the encoder and decoder maintain these caches, so that decoder's caches remain synchronized with the encoder's caches. a. A "near" cache is an array with "s_near" slots, each containing an address used for encoding addresses nearby to previously encoded addresses (in the positive direction only). The near cache also maintains a "next_slot" index to the near cache. New entries to the near cache are always inserted in the next_slot index, which maintains a circular buffer of the s_near most recent addresses. b. A "same" cache is an array with "s_same", with a multiple of 256 slots, each containing an address. The same cache maintains a hash table of recent addresses used for repeated encoding of the exact same address. By default, the parameters s_near and s_same are respectively set to 4 and 3. An encoder MAY modify these values, but then it MUST encode the new values in the encoding itself, as discussed in Section 7, so that the decoder can properly set up its own caches. At the start of processing a target window, an implementation (encoder or decoder) initializes all of the slots in both caches to zero. The next_slot pointer of the near cache is set to point to slot zero. Korn, et. al. Standards Track [Page 12] RFC 3284 VCDIFF June 2002 Each time a COPY instruction is processed by the encoder or decoder, the implementation's caches are updated as follows, where "addr" is the address in the COPY instruction. a. The slot in the near cache referenced by the next_slot index is set to addr. The next_slot index is then incremented modulo s_near. b. The slot in the same cache whose index is addr%(s_same*256) is set to addr. [We use the C notations of % for modulo and * for multiplication.] 5.2 Example code for maintaining caches To make clear the above description, below are examples of cache data structures and algorithms to initialize and update them: typedef struct _cache_s { int* near; /* array of size s_near */ int s_near; int next_slot; /* the circular index for near */ int* same; /* array of size s_same*256 */ int s_same; } Cache_t; cache_init(Cache_t* ka) { int i; ka->next_slot = 0; for(i = 0; i < ka->s_near; ++i) ka->near[i] = 0; for(i = 0; i < ka->s_same*256; ++i) ka->same[i] = 0; } cache_update(Cache_t* ka, int addr) { if(ka->s_near > 0) { ka->near[ka->next_slot] = addr; ka->next_slot = (ka->next_slot + 1) % ka->s_near; } if(ka->s_same > 0) ka->same[addr % (ka->s_same*256)] = addr; } Korn, et. al. Standards Track [Page 13] RFC 3284 VCDIFF June 2002 5.3 Encoding of COPY instruction addresses The address of a COPY instruction is encoded using different modes, depending on the type of cached address used, if any. Let "addr" be the address of a COPY instruction to be decoded and "here" be the current location in the target data (i.e., the start of the data about to be encoded or decoded). Let near[j] be the jth element in the near cache, and same[k] be the kth element in the same cache. Below are the possible address modes: VCD_SELF: This mode has value 0. The address was encoded by itself as an integer. VCD_HERE: This mode has value 1. The address was encoded as the integer value "here - addr". Near modes: The "near modes" are in the range [2,s_near+1]. Let m be the mode of the address encoding. The address was encoded as the integer value "addr - near[m-2]". Same modes: The "same modes" are in the range [s_near+2,s_near+s_same+1]. Let m be the mode of the encoding. The address was encoded as a single byte b such that "addr == same[(m - (s_near+2))*256 + b]". 5.4 Example code for encoding and decoding of COPY instruction addresses We show example algorithms below to demonstrate the use of address modes more clearly. The encoder has the freedom to choose address modes, the sample addr_encode() algorithm merely shows one way of picking the address mode. The decoding algorithm addr_decode() will uniquely decode addresses, regardless of the encoder</component> <component componentID="5" access="read-write"> <name>CEHDI</name> <synopsis> The CE Heartbeat Dead Interval in milliseconds </synopsis> <typeRef>uint32</typeRef> </component> <component componentID="6" access="read-write"> <name>FEHBPolicy</name> <synopsis> The FE Heartbeat policy </synopsis> <typeRef>FEHBPolicyValues</typeRef> </component> <component componentID="7" access="read-write"> <name>FEHI</name> <synopsis> The FE Heartbeat Interval in milliseconds </synopsis> <typeRef>uint32</typeRef> </component> <component componentID="8" access="read-write"> <name>CEID</name> <synopsis> The primary CE this FE is associated with </synopsis> <typeRef>uint32</typeRef> </component> <component componentID="9" access="read-write"> <name>BackupCEs</name> Ogawa, et al. Standards Track [Page 27] RFC 7121 ForCES Intra-NE High Availability February 2014 <synopsis> The table of all backup CEs other than the primary </synopsis> <array type="variable-size"> <typeRef>uint32</typeRef> </array> </component> <component componentID="10" access="read-write"> <name>CEFailoverPolicy</name> <synopsis> The CE failover policy </synopsis> <typeRef>CEFailoverPolicyValues</typeRef> </component> <component componentID="11" access="read-write"> <name>CEFTI</name> <synopsis> The CE Failover Timeout Interval in milliseconds </synopsis> <typeRef>uint32</typeRef> </component> <component componentID="12" access="read-write"> <name>FERestartPolicy</name> <synopsis> The FE restart policy </synopsis> <typeRef>FERestartPolicyValues</typeRef> </component> <component componentID="13" access="read-write"> <name>LastCEID</name> <synopsis> The primary CE this FE was last associated with </synopsis> <typeRef>uint32</typeRef> </component> <component componentID="14" access="read-write"> <name>HAMode</name> <synopsis> The HA mode used </synopsis> <typeRef>HAModeValues</typeRef> </component> <component componentID="15" access="read-only"> <name>AllCEs</name> <synopsis>The table of all CEs</synopsis> <array type="variable-size's algorithm choice. Note that the address caches are updated immediately after an address is encoded or decoded. In this way, the decoder is always synchronized with the encoder. Korn, et. al. Standards Track [Page 14] RFC 3284 VCDIFF June 2002 int addr_encode(Cache_t* ka, int addr, int here, int* mode) { int i, d, bestd, bestm; /* Attempt to find the address mode that yields the * smallest integer value for "d", the encoded address * value, thereby minimizing the encoded size of the * address. */ bestd = addr; bestm = VCD_SELF; /* VCD_SELF == 0 */ if((d = here-addr) < bestd) { bestd = d; bestm = VCD_HERE; } /* VCD_HERE == 1 */ for(i = 0; i < ka->s_near; ++i) if((d = addr - ka->near[i]) >= 0 && d < bestd) { bestd = d; bestm = i+2; } if(ka->s_same > 0 && ka->same[d = addr%(ka->s_same*256)] == addr) { bestd = d%256; bestm = ka->s_near + 2 + d/256; } cache_update(ka,addr); *mode = bestm; /* this returns the address encoding mode */ return bestd; /* this returns the encoded address */ } Note that the addr_encode() algorithm chooses the best address mode using a local optimization, but that may not lead to the best encoding efficiency because different modes lead to different instruction encodings, as described below. The functions addrint() and addrbyte() used in addr_decode(), obtain from the "Addresses section for COPYs" (Section 4.3), an integer or a byte, respectively. These utilities will not be described here. We simply recall that an integer is represented as a compact variable- sized string of bytes, as described in Section 2 (i.e., base 128). Korn, et. al. Standards Track [Page 15] RFC 3284 VCDIFF June 2002 int addr_decode(Cache_t* ka, int here, int mode) { int addr, m; if(mode == VCD_SELF) addr = addrint(); else if(mode == VCD_HERE) addr = here - addrint(); else if((m = mode - 2) >= 0 && m < ka->s_near) /* near cache */ addr = ka->near[m] + addrint(); else /* same cache */ { m = mode - (2 + ka->s_near); addr = ka->same[m*256 + addrbyte()]; } cache_update(ka, addr); return addr; } 5.4 Instruction Codes Matches are often short in lengths and separated by small amounts of unmatched data. That is, the lengths of COPY and ADD instructions are often small. This is particularly true of binary data such as executable files or structured data, such as HTML or XML. In such cases, compression can be improved by combining the encoding of the sizes and the instruction types, as well as combining the encoding of adjacent delta instructions with sufficiently small data sizes. Effective choices of when to perform such combinations depend on many factors including the data being processed and the string matching algorithm in use. For example, if many COPY instructions have the same data sizes, it may be worthwhile to encode these instructions more compactly than others. The Vcdiff data format is designed so that a decoder does not need to be aware of the choices made in encoding algorithms. This is achieved with the notion of an "instruction code table", containing 256 entries. Each entry defines, either a single delta instruction or a pair of instructions that have been combined. Note that the code table itself only exists in main memory, not in the delta file (unless using an application-defined code table, described in Section 7). The encoded data simply includes the index of each instruction and, since there are only 256 indices, each index can be represented as a single byte. Korn, et. al. Standards Track [Page 16] RFC 3284 VCDIFF June 2002 Each instruction code entry contains six fields, each of which is a single byte with an unsigned value: +-----------------------------------------------+ | inst1 | size1 | mode1 | inst2 | size2 | mode2 | +-----------------------------------------------+ Each triple (inst,size,mode) defines a delta instruction. The meanings of these fields are as follows: inst: An "inst" field can have one of the four values: NOOP (0), ADD (1), RUN (2) or COPY (3) to indicate the instruction types. NOOP means that no instruction is specified. In this case, both the corresponding size and mode fields will be zero. size: A "size" field is zero or positive. A value zero means that the size associated with the instruction is encoded separately as an integer in the "Instructions and sizes section" (Section 6). A positive value for "size" defines the actual data size. Note that since the size is restricted to a byte, the maximum value for any instruction with size implicitly defined in the code table is 255. mode: A "mode" field is significant only when the associated delta instruction is a COPY. It defines the mode used to encode the associated addresses. For other instructions, this is always zero. 5.6 The Code Table Following the discussions on address modes and instruction code tables, we define a "Code Table" to have the data below: s_near: the size of the near cache, s_same: the size of the same cache, i_code: the 256-entry instruction code table. Vcdiff itself defines a "default code table" in which s_near is 4 and s_same is 3. Thus, there are 9 address modes for a COPY instruction. The first two are VCD_SELF (0) and VCD_HERE (1). Modes 2, 3, 4 and 5 are for addresses coded against the near cache. And modes 6, 7 and 8, are for addresses coded against the same cache. Korn, et. al. Standards Track [Page 17] RFC 3284 VCDIFF June 2002 TYPE SIZE MODE TYPE SIZE MODE INDEX --------------------------------------------------------------- 1. RUN 0 0 NOOP 0 0 0 2. ADD 0, [1,17] 0 NOOP 0 0 [1,18] 3. COPY 0, [4,18] 0 NOOP 0 0 [19,34] 4. COPY 0, [4,18] 1 NOOP 0 0 [35,50] 5. COPY 0, [4,18] 2 NOOP 0 0 [51,66] 6. COPY 0, [4,18] 3 NOOP 0 0 [67,82] 7. COPY 0, [4,18] 4 NOOP 0 0 [83,98] 8. COPY 0, [4,18] 5 NOOP 0 0 [99,114] 9. COPY 0, [4,18] 6 NOOP 0 0 [115,130] 10. COPY 0, [4,18] 7 NOOP 0 0 [131,146] 11. COPY 0, [4,18] 8 NOOP 0 0 [147,162] 12. ADD [1,4] 0 COPY [4,6] 0 [163,174] 13. ADD [1,4] 0 COPY [4,6] 1 [175,186] 14. ADD [1,4] 0 COPY [4,6] 2 [187,198] 15. ADD [1,4] 0 COPY [4,6] 3 [199,210] 16. ADD [1,4] 0 COPY [4,6] 4 [211,222] 17. ADD [1,4] 0 COPY [4,6] 5 [223,234] 18. ADD [1,4] 0 COPY 4 6 [235,238] 19. ADD [1,4] 0 COPY 4 7 [239,242] 20. ADD [1,4] 0 COPY 4 8 [243,246] 21. COPY 4 [0,8] ADD 1 0 [247,255] --------------------------------------------------------------- The default instruction code table is depicted above, in a compact representation that we use only for descriptive purposes. See section 7 for the specification of how an instruction code table is represented in the Vcdiff encoding format. In the depiction, a zero value for size indicates that the size is separately coded. The mode of non-COPY instructions is represented as 0, even though they are not used. In the depiction, each numbered line represents one or more entries in the actual instruction code table (recall that an entry in the instruction code table may represent up to two combined delta instructions.) The last column ("INDEX") shows which index value, or range of index values, of the entries are covered by that line. (The notation [i,j] means values from i through j, inclusively.) The first 6 columns of a line in the depiction, describe the pairs of instructions used for the corresponding index value(s). If a line in the depiction includes a column entry using the [i,j] notation, this means that the line is instantiated for each value in the range from i to j, inclusively. The notation "0, [i,j]" means that the line is instantiated for the value 0 and for each value in the range from i to j, inclusively. Korn, et. al. Standards Track [Page 18] RFC 3284 VCDIFF June 2002 If a line in the depiction includes more than one entry using the [i,j] notation, implying a "nested loop" to convert the line to a range of table entries, the first such [i,j] range specifies the outer loop, and the second specifies the inner loop. The below examples should make clear the above description: Line 1 shows the single RUN instruction with index 0. As the size field is 0, this RUN instruction always has its actual size encoded separately. Line 2 shows the 18 single ADD instructions. The ADD instruction with size field 0 (i.e., the actual size is coded separately) has index 1. ADD instructions with sizes from 1 to 17 use code indices 2 to 18 and their sizes are as given (so they will not be separately encoded.) Following the single ADD instructions are the single COPY instructions ordered by their address encoding modes. For example, line 11 shows the COPY instructions with mode 8, i.e., the last of the same cache. In this case, the COPY instruction with size field 0 has index 147. Again, the actual size of this instruction will be coded separately. Lines 12 to 21 show the pairs of instructions that are combined together. For example, line 12 depicts the 12 entries in which an ADD instruction is combined with an immediately following COPY instruction. The entries with indices 163, 164, 165 represent the pairs in which the ADD instructions all have size 1, while the COPY instructions have mode 0 (VCD_SELF) and sizes 4, 5 and 6 respectively. The last line, line 21, shows the eight instruction pairs, where the first instruction is a COPY and the second is an ADD. In this case, all COPY instructions have size 4 with mode ranging from 0 to 8 and all the ADD instructions have size 1. Thus, the entry with the largest index 255 combines a COPY instruction of size 4 and mode 8 with an ADD instruction of size 1. The choice of the minimum size 4 for COPY instructions in the default code table was made from experiments that showed that excluding small matches (less then 4 bytes long) improved the compression rates. Korn, et. al. Standards Track [Page 19] RFC 3284 VCDIFF June 2002 6. Decoding a Target Window Section 4.3 discusses that the delta instructions and associated data are encoded in three arrays of bytes: Data section for ADDs and RUNs, Instructions and sizes section, and Addresses section for COPYs. Further, these data sections may have been further compressed by some secondary compressor. Assuming that any such compressed data has been decompressed so that we now have three arrays: inst: bytes coding the instructions and sizes. data: unmatched data associated with ADDs and RUNs. addr: bytes coding the addresses of COPYs. These arrays are organized as follows: inst: a sequence of (index, [size1], [size2]) tuples, where "index" is an index into the instruction code table, and size1 and size2 are integers that MAY or MAY NOT be included in the tuple as follows. The entry with the given "index" in the instruction code table potentially defines two delta instructions. If the first delta instruction is not a VCD_NOOP and its size is zero, then size1 MUST be present. Otherwise, size1 MUST be omitted and the size of the instruction (if it is not VCD_NOOP) is as defined in the table. The presence or absence of size2 is defined similarly with respect to the second delta instruction. data: a sequence of data values, encoded as bytes. addr: a sequence of address values. Addresses are normally encoded as integers as described in Section 2 (i.e., base 128). However, since the same cache emits addresses in the range [0,255], same cache addresses are always encoded as a single byte. To summarize, each tuple in the "> Ogawa, et al. Standards Track [Page 28] RFC 7121 ForCES Intra-NE High Availability February 2014 <typeRef>AllCEType</typeRef> </array> </component> </components> <capabilities> <capability componentID="30"> <name>SupportableVersions</name> <synopsis> The table of ForCES versions that FE supports </synopsis> <array type="variable-size"> <typeRef>uchar</typeRef> </array> </capability> <capability componentID="31"> <name>HACapabilities</name> <synopsis> The table of HA capabilities the FE supports </synopsis> <array type="variable-size"> <typeRef>FEHACapab</typeRef> </array> </capability> </capabilities> <events baseID="61"> <event eventID="1"> <name>PrimaryCEDown</name> <synopsis> The primary CE has changed </synopsis> <eventTarget> <eventField>LastCEID</eventField> </eventTarget> <eventChanged/> <eventReports> <eventReport> <eventField>LastCEID</eventField> </eventReport> </eventReports> </event> <event eventID="2"> <name>PrimaryCEChanged</name> <synopsis>A new primary CE has been selected </synopsis> <eventTarget> <eventField>CEID</eventField> </eventTarget> <eventChanged/> Ogawa, et al. Standards Track [Page 29] RFC 7121 ForCES Intra-NE High Availability February 2014 <eventReports> <eventReport> <eventField>CEID</eventField> </eventReport> </eventReports> </event> </events> </LFBClassDef> </LFBClassDefs> </LFBLibrary> Ogawa, et al. Standards Track [Page 30] RFC 7121 ForCES Intra-NE High Availability February 2014 Authors' Addresses Kentaro Ogawa NTT Corporation 3-9-11 Midori-cho Musashino-shi, Tokyo 180-8585 Japan EMail: k.ogawa@ntt.com Weiming Wang Zhejiang Gongshang University 18 Xuezheng Str., Xiasha University Town Hangzhou 310018 P.R. China Phone: +86 571 28877751 EMail: wmwang@zjsu.edu.cn Evangelos Haleplidis University of Patras Department of Electrical and Computer Engineering Patras 26500 Greece EMail: ehalep@ece.upatras.gr Jamal Hadi Salim Mojatatu Networks Suite 400, 303 Moodie Dr. Ottawa, Ontario K2H 9R4 Canada EMail: hadi@mojatatu.com Ogawa, et al. Standards Track [Page 31]