Network Working Group F. Tommasi Internet Draft S. Molendini Document: draft-tommasi-rsvp-list-compr-00.txt University of Lecce Expiration date: September 2000 March 2000 Compression of RSVP protocol's MESSAGE_ID_LIST objects Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. 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-D rafts. 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 to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract This document describes a simple method for compressing lists of Message_Identifiers contained in MESSAGE_ID_LIST objects of the RSVP protocol, as defined in [RSVP2205] and [Berger2000]. This method helps to alleviate the scaling problem of the RSVP protocol. Conventions used in this document 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 RFC2119. F.Tommasi / S.Molendini Expires September 2000 [Page 1] draft-tommasi-rsvp-list-compr-00.txt March 2000 Contents 1. INTRODUCTION..................................................2 2. COMPRESSION METHOD OVERVIEW...................................3 3. WHEN A NODE CAN USE COMPRESSION...............................4 4. FORMAT OF THE MESSAGE_ID OBJECT...............................4 5. FORMAT OF MESSAGE_ID_LIST OBJECTS.............................5 6. DESCRIPTORS...................................................6 7. THREE EXAMPLES................................................8 8. CONSIDERATIONS ABOUT IMPLEMENTATION...........................9 9. PERFORMANCES MEASURED WITH A TEST PROGRAM.....................9 10. SECURITY CONSIDERATIONS......................................10 11. ACKNOWLEDGEMENT..............................................10 12. REFERENCES...................................................10 13. AUTHORS' ADDRESSES...........................................11 1. Introduction Functional specifications of RSVP are defined in [RFC2205]. In the RSVP protocol, a node sends a Path or Resv message to create or change an RSVP session. This message is called trigger message because it advertises a state change. F.Tommasi / S.Molendini Expires September 2000 [Page 2] draft-tommasi-rsvp-list-compr-00.txt March 2000 Because of the soft state nature of the RSVP protocol, the same message is periodically sent over the network with the rate Refresh_Time, typically set at the value of 30 seconds. Thus, the node receiving this refresh message keeps the state alive, and failure to receive refresh messages for a certain number of refresh periods, causes state deletion. Recently a certain amount of work has been devoted to reduce the excessive load the protocol introduces in terms of messages exchange and their processing, especially in routers that handle a large number of sessions. In [Berger2000] a solution is proposed to reduce the refresh traffic, based on the use of message identifiers in trigger messages. In this document an enhancement to this proposal, based on a simple and robust compression technique, is introduced that substantially reduces the RSVP traffic. 2. Compression method overview The solution in [Berger2000] can be divided in two steps: 1. A new MESSAGE_ID object is inserted in trigger messages. This object contains a 32-bits Message_Identifier that is unique on a per sender/hop-by-hop basis. It is used to simplify acknowledgement and refresh. 2. A new MESSAGE_ID_LIST object is defined to transport large lists of Message_Identifiers. Such objects are carried by new Srefresh messages that replace refresh messages. When a node receives an ID in a MESSAGE_ID_LIST object, it refreshes the related state. In this document an enhancement to this proposal is introduced: lists of Message_Identifiers in the MESSAGE_ID_LIST objects are compressed with a simple algorithm. In order to manage these extensions, the 32-bits Message_Identifier is reduced to 31-bits. Compression of MESSAGE_ID_LIST objects sent by a node can be performed only if the destination node has set to 1 the Compression_Desired flag in the last MESSAGE_ID object sent to the same node. As usual, a node transmits the 31-bits Message_Identifier into MESSAGE_ID objects in trigger messages. Also state-refresh is performed as in [Berger2000] by sending MESSAGE_ID_LIST objects with the list of IDs that identify the state to refresh. F.Tommasi / S.Molendini Expires September 2000 [Page 3] draft-tommasi-rsvp-list-compr-00.txt March 2000 The proposed change is in the way the list of IDs is represented. In [Berger2000] each ID is 1-word long; i.e. a list of 100 IDs is 400 bytes long. The simple compression described in this document, reduces the lists' length. Let us suppose for example to have to transmit the following list of IDs: 2,3,6,7,9. Instead of transmitting the 5 words with the numbers 2,3,6,7, and 9 (1-word each), the following is sent: 1) 1 word with the first ID in the list (2). 2) 1 word containing a bitmap: 1001101000000... The bitmap is interpreted as follows: starting from the last defined ID (2), the bitmap associates a '1' to the message_ids that are to be transmitted (3,6,7,9) and a '0'to those that are not to be transmitted (4,5,8,10, ...). In order to distinguish between ID-words and bitmap-words, all the ID-words have the first bit set to 0, and all the bitmap-words have the first bit set to 1. That is, each ID and each bitmap are 31-bits long. 3. When a node can use compression A node is allowed to send MESSAGE_ID_LIST object of the compressed type, only if its neighbour agrees to use them. That is, only if: 1. It is sure that the neighbour is configured to receive them. 2. The last MESSAGE_ID object it has received from the neighbour has the Compression_Desired flag set to 1. The compression mechanism can be asymmetric. That is, a node can transmit to a neighbour compressed lists of IDs, but can receive uncompressed ones from it. For such a reason, if a node receives from a neighbor compressed MESSAGE_ID_LIST objects, it is not allowed to send compressed MESSAGE_ID_LIST objects, until one of the previously listed conditions is true. 4. Format of the MESSAGE_ID object MESSAGE_ID Class = Value to be assigned by IANA of form 10bbbbbb MESSAGE_ID object Class = MESSAGE_ID Class, C-Type = 1 F.Tommasi / S.Molendini Expires September 2000 [Page 4] draft-tommasi-rsvp-list-compr-00.txt March 2000 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Flags | Epoch | +-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0| Message_Identifier | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of this object is identical to the format of the MESSAGE_ID object in [Berger2000], with the following exceptions: Flags: 8 bits. The following new flag is defined: 0x02 = Compression_Desired flag Indicates that the sender is able to perform compression, and that the sender will use it. Message_Identifier: 31 bits In order to manage compression, this field is reduced from 32 bits to 31 bits. The 1-bit field at the left of this field, MUST be 0. See [Berger2000] about usage rules of MESSAGE_ID objects, and about a full explanation of fields' meaning. 5. Format of MESSAGE_ID_LIST objects MESSAGE_ID_LIST Class = Value to be assigned by IANA of form 0bbbbbbb MESSAGE_ID_LIST object Class = MESSAGE_ID_LIST Class, C-Type = 1 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Flags | Epoch | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | First Descriptor | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ............ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Last Descriptor | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of this object is identical to the format of the MESSAGE_ID object in [Berger2000], with the following exceptions: Flags: 8 bits. The following new flag is defined: F.Tommasi / S.Molendini Expires September 2000 [Page 5] draft-tommasi-rsvp-list-compr-00.txt March 2000 0x01 = Compression flag This flag is used to advertise the receiver that in this object compression is used. Descriptor(s): They describe the compressed list of Message_Identifiers, as explained in the paragraph 6. See [Berger2000] about usage rules of MESSAGE_ID_LIST objects, and about a full explanation of fields' meaning. 6. Descriptors The number N of descriptors is variable, and can be derived from the object's header. Each descriptor can be: 1) ID descriptor: a Message_Identifier. 2) Bitmap descriptor: a Bitmap of IDs. Format of ID descriptor: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0| Message_Identifier | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Message_Identifier is a 31-bits field. The Message_Identifier field is equal to a Message_Identifier value in the corresponding MESSAGE_ID object. Format of Bitmap descriptor: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1| Bitmap | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Bitmap is a 31-bits field. Processing of descriptors: Bitmap words are sequentially processed. The Bitmap field's bits are processed from left to right F.Tommasi / S.Molendini Expires September 2000 [Page 6] draft-tommasi-rsvp-list-compr-00.txt March 2000 In order to decompress the bitmap, a local Current_Message_ID variable can be maintained. As descriptors are sequentially encountered, they are processed according to the rules given below: ID descriptor: the Message_Identifier belongs to the list and the Current_Message_ID is equal to the represented Message_Identifier. Bitmap descriptor: The list of Message_IDs is represented through a string of bits. The Bitmap field's bits are processed from left to right. If a bit is equal to 1, the Message_ID equal to Current_Message_ID + 1 belongs to the list. Current_Message_ID + 1 becomes the new Current_Message_ID. Because this compression is a differential one, the first descriptor in a MESSAGE_ID_LIST object MUST be an ID descriptor. F.Tommasi / S.Molendini Expires September 2000 [Page 7] draft-tommasi-rsvp-list-compr-00.txt March 2000 7. Three Examples Example N.1: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Flags | Epoch | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0| 50 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0| 977 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0| 2080 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ This object describes the Message_Identifiers' list: 50, 977, 2080 Example N.2: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Flags | Epoch | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0| 49 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|0 1 1 0 0 0 0 1 1 1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 1 1 1 1 1| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|1 1 1 1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 0 1 0 1| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ This object describes the Message_Identifiers' list: 49, 51, 52, 57, 58, 59, 62, 64, 66, 68, 70, 71, 76, 77, 78, 79, 80, 81, 82, 83, 84, 87, 89, 91, 93, 95, 96, 101, 102, 103, 104, 107, 109, 111. Example N.3: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Flags | Epoch | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0| 23 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|0 1 1 0 0 0 0 1 1 1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 1 1 1 1 1| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0| 100 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|1 1 1 1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 0 1 0 1| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ This object describes the Message_Identifiers' list: 23, 25, 26, 31, 32, 33, 36, 38, 40, 42, 44, 45, 50, 51, 52, 53, 54, 100, 101, 102, 103, 104, 107, 109, 111, 113, 115, 116, 121, 122, 123, 124, 127, 129, 131. F.Tommasi / S.Molendini Expires September 2000 [Page 8] draft-tommasi-rsvp-list-compr-00.txt March 2000 8. Considerations about implementation Compression is simple to implement. Only a Current_Message_ID variable (CUR_MSG_ID from now on), and a 32-word-length ID buffer are needed. The following steps are performed until the node's IDs list is empty. We suppose that this list is ordered by increasing IDs. CUR_MSG_ID is just a pointer to an ID 1) Get an ID from the node's IDs list and set CUR_MSG_ID to this ID. 2) Write CUR_MSG_ID to the forming MESSAGE_ID_LIST object 3) Get the IDs between CUR_MSG_ID +1 and CUR_MSG_ID +31 from the node's IDs list 4) If no ID is get, go to 1 5) If at least one ID is get, then 5.1) set the proper '1' in the Bitmap Word 5.2) write this word to the MESSAGE_ID_LIST object 5.3) set CUR_MSG_ID = CUR_MSG_ID +31 5.4) go to 3 Using this algorithm: o) Compression is simple because it is locally performed, by compressing local sequences of IDs without looking at the whole list. o) Compression gives good results if IDs are assigned with a sequential logic. That is, Message_Identifiers are numerically close to each other. o) In the worst case, the length of the compressed object is the same of the uncompressed object (i.e. there is no 'negative' compression). All the descriptors are 'pure IDs' ones (see example 1). o) This compression scheme does not suffer from the ID's wrap-around problem. Values are compressed till the wrap-around value; then, a new ID descriptor is assigned to the new low value, from which new bitmaps start. 9. Performances measured with a test program A simple program was run: it generates a given number of RSVP independent and identically distributed unicast sessions. The mean life of each session is exponentially distributed, with a given statistical mean. When a session ends, a new one is started. The program gives sequential IDs to sessions. F.Tommasi / S.Molendini Expires September 2000 [Page 9] draft-tommasi-rsvp-list-compr-00.txt March 2000 We then calculate the length of messages used for refresh purposes, using the compression described in this document. The Compression parameter is the ratio between the length of the non compressed list (i. e. NumberOfSessions*4 bytes), and the compressed one. In the following table, the Compression values are reported. Along then row, the mean life of sessions is reported. Along then columns, the number of sessions is reported. Table of Compression values Number of sessions Sessions' | 100 1000 10000 Mean Life |------------------------------ 10 | 6.67 6.89 7.15 | 100 | 7.12 7.25 7.44 | 1000 | 7.44 7.59 7.65 The Compression values are near to the value 7 (with the exponential distribution of sessions' life model). That is, with 10000 sessions, instead of 4*10000 = 40Kb per 30 seconds the node transmits only 40/7 ~ 5.7 Kb per 30 seconds. 10. Security Considerations No new security issues are raised in this document. 11. Acknowledgement This work benefit from the discussions held within the RSVP WG during the 46th IETF meeting in Washington. Thanks to Lou Berger and Bob Braden for specific feedback on the document. 12. References [Berger2000] Berger, L., Gan, D., Swallow, G., Pan, P.,_RSVP Refresh Reduction Extensions_, Internet Draft, draft-ietf-rsvp-refresh-reduct-01.txt, October 1999 [RFC2205] Braden, R. Ed. et al, "Resource ReserVation Protocol -- Version 1 Functional Specification", RFC 2205, September 1997. F.Tommasi / S.Molendini Expires September 2000 [Page 10] draft-tommasi-rsvp-list-compr-00.txt March 2000 13. Authors' Addresses Franco Tommasi University of Lecce, Fac. Ingegneria Via Monteroni 73100 Lecce, ITALY tommasi@ilenic.unile.it Simone Molendini University of Lecce, Fac. Ingegneria Via Monteroni 73100 Lecce, ITALY molendini@ultra5.unile.it F.Tommasi / S.Molendini Expires September 2000 [Page 11]