Network Working Group R. Braden Request For Comments: 2209 ISI Category: Informational L. Zhang UCLA September 1997
This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited.
This memo contains an algorithmic description of the rules used by an RSVP implementation for processing messages. It is intended to clarify the version 1 RSVP protocol specification.
This memo provides a generic description of the rules for the operation of Version 1 of RSVP [RFC 2205]. It is intended to outline a set of algorithms that will accomplish the needed function, omitting many details.
This memo assumes the generic interface calls defined in [RFC 2005] and the following data structures. An actual implementation may use additional or different data structures and interfaces. The data structure fields that are shown are required unless they are explicitly labelled as optional.
Each PSB holds path state for a particular (session, sender) pair, defined by SESSION and SENDER_TEMPLATE objects, respectively, received in a PATH message.
PSB contents include the following values from a PATH message:
- Session - Sender_Template - Sender_Tspec - The previous hop IP address and the Logical Interface Handle (LIH) from a PHOP object - The remaining IP TTL - POLICY_DATA and/or ADSPEC objects (optional) - Non_RSVP flag - E_Police flag - Local_Only flag
In addition, the PSB contains the following information provided by routing: OutInterface_list, which is the list of outgoing interfaces for this (sender, destination), and IncInterface, which is the expected incoming interface. For a unicast destination, OutInterface_list contains one entry and IncInterface is undefined.
Note that there may be more than one PSB for the same (session,
sender) pair but different incoming interfaces. At most one of
these, which will have the Local_Only flag off, will be the PSB
used for forwarding PATH messages downstream; we will refer to
it as the "forwarding PSB" in the following. The other PSB's
will have the Local_Only flag on and an empty
OutInterface_list.h The Local_Only flag is needed to correctly
match PSB's against RSB's, by the rules of [RFC 2205].
Each RSB holds a reservation request that arrived in a particular RESV message, corresponding to the triple: (session, next hop, Filter_spec_list). Here "Filter_spec_list" may be a list of FILTER_SPECs (for SE style), a single FILTER_SPEC (FF style), or empty (WF style). We define the virtual object type "FILTER_SPEC*" for such a data structure.
RSB contents include:
- Session specification - Next hop IP address - Filter_spec_list - The outgoing (logical) interface OI on which the reservation is to be made or has been made. - Style - Flowspec - A SCOPE object (optional, depending upon style) - RESV_CONFIRM object that was received (optional)
Each TCSB holds the reservation specification that has been handed to traffic control for a specific outgoing interface. In general, TCSB information is derived from RSB's for the same outgoing interface. Each TCSB defines a single reservation for a particular triple: (session, OI, Filter_spec_list). TCSB contents include:
- Session - OI (Outgoing Interface) - Filter_spec_list - TC_Flowspec, the effective flowspec, i.e., the LUB over the corresponding FLOWSPEC values from matching RSB's. TC_Flowspec is passed to traffic control to make the actual reservation. - Fwd_Flowspec, the updated object to be forwarded after merging. - TC_Tspec, equal to Path_Te, the effective sender Tspec. - Police Flags
The flags are E_Police_Flag, M_Police_Flag, and B_Police_Flag.
- Rhandle, F_Handle_list
Handles returned by the traffic control interface, corresponding to a flowspec and perhaps a list of filter specs.
- A RESV_CONFIRM object to be forwarded.
Each BSB contains an element of blockade state. Depending upon the reservation style in use, the BSB's may be per (session, sender_template) pair or per (session, PHOP) pair. In practice, an implementation might embed a BSB within a PSB; however, for clarity we describe BSB's independently.
The contents of a BSB include:
- Session - Sender_Template (which is also a filter spec) - PHOP - FLOWSPEC Qb - Blockade timer Tb
The following Boolean Flag variables are used in this section: Path_Refresh_Needed, Resv_Refresh_Needed, Tear_Needed, Need_Scope, B_Merge, and NeworMod. Refresh_PHOP_list is a variable-length list of PHOPs to be refreshed.
MESSAGE ARRIVES
Verify version number and RSVP checksum, and discard message if any mismatch is found.
If the message type is not PATH or PTEAR or RACK and if the IP destination address does not match any of the addresses of the local interfaces, then forward the message to IP destination address and return.
Parse the sequence of objects in the message. If any required objects are missing or the length field of the common header does not match an object boundary, discard the message and return.
Verify the INTEGRITY object, if any. If the check fails, discard the message and return.
Verify the consistent use of port fields. If the DstPort in the SESSION object is zero but the SrcPort in a SENDER_TEMPLATE or FILTER_SPEC object is non-zero, then the message has a "conflicting source port" error; silently discard the message and return.
Processing of POLICY_DATA objects will be specified in the future.
Further processing depends upon message type.
PATH MESSAGE ARRIVES
Assume the PATH message arrives on interface InIf.
Process the sender descriptor object sequence in the message as follows. The Path_Refresh_Needed and Resv_Refresh_Needed flags are initially off.
During this search:
into the PSB.
- If the PHOP IP address, the LIH, or Sender_Tspec differs between the message and the PSB, copy the new value into the PSB and turn on the Path_Refresh_Needed flag. If the PHOP IP address or the LIH differ, also turn on the Resv_Refresh_Needed flag.
- Start or Restart the cleanup timer for the PSB. - If the message contains an ADSPEC object, copy it into the PSB. - Copy E_Police flag from SESSION object into PSB. - Store the received TTL into the PSB. If the received TTL differs from Send_TTL in the RSVP common header, set the Non_RSVP flag on in the PSB.
Call the results (Rt_OutL, Rt_InIf).
- Turn on the Local_Only flag and clear the OutInterface_list of the fPSB. Set the fPSB
pointer to NULL.
- Search for a PSB for the same (session, sender_template) pair whose IncInterface matches Rt_InIf. If one is found, set fPSB to point to it.
- Copy into the cPSB the OutInterface_list from the PSB, if any, pointed to by fPSB. Clear OutInterface_list and turn on the Local_Only flag in the PSB pointed to by fPSB, if any. - Turn off the Local_Only flag in the cPSB and set fPSB to point to cPSB.
- Update the OutInterface_list of the PSB from Rt_OutL, and then execute the PATH LOCAL REPAIR event sequence below.
Otherwise (the path state is new or modified), do refreshes, upcalls, and state updates as follows.
Call: <Upcall_Proc>( session-id, PATH_EVENT, flags, sender_tspec, sender_template [ , ADSPEC] [ , POLICY_DATA] )
If none is found, drop the PATH message and return.
PTEAR MESSAGE ARRIVES
- Delete from Filter_spec_list the FILTER_SPEC that matches the PSB. - if Filter_spec_list is now empty, delete the RSB.
- If this RSB matches no other PSB, then delete the RSB.
PERR MESSAGE ARRIVES
Call: <Upcall_Proc>( session-id, PATH_ERROR, Error_code, Error_value, Node_Addr, Sender_Template [ , Policy_Data] )
Any SENDER_TSPEC or ADSPEC object in the message is ignored.
Otherwise, send a copy of the PERR message to the PHOP IP address.
RESV MESSAGE ARRIVES
Initially, Refresh_PHOP_list is empty and the
Resv_Refresh_Needed and NeworMod flags are off. These variables
are used to control immediate reservation refreshes.
The logical outgoing interface OI is taken from the LIH in the NHOP object. (If the physical interface is not implied by the LIH, it can be learned from the interface matching the IP destination address).
If any existing RSB for the session has a style that is incompatible with the style of the message, build and send a RERR message specifying "Conflicting Style", drop the RESV message, and return.
Process the flow descriptor list to make reservations, as follows, depending upon the style. The following uses a filter spec list struct Filtss of type FILTER_SPEC* (defined earlier).
For FF style: execute the following steps independently for each flow descriptor in the message, i.e., for each (FLOWSPEC, Filtss) pair. Here the structure Filtss consists of the FILTER_SPEC from the flow descriptor.
For SE style, execute the following steps once for (FLOWSPEC, Filtss), with Filtss consisting of the list of FILTER_SPEC objects from the flow descriptor.
For WF style, execute the following steps once for (FLOWSPEC, Filtss), with Filtss an empty list.
If this set is empty, build and send an error message specifying "No sender information", and continue with the next flow descriptor in the RESV message.
If the UPDATE TRAFFIC CONTROL sequence fails with an error, then delete a new RSB but restore the original reservation in an old RSB.
If processing a RESV message finds an error, a RERR message is created containing flow descriptor and an ERRORS object. The Error Node field of the ERRORS object is set to the IP address of OI, and the message is sent unicast to NHOP.
RTEAR MESSAGE ARRIVES
Processing of a RTEAR message roughly parallels the processing of the corresponding RESV message
A RTEAR message arrives with an IP destination address matching outgoing interface OI. Flag Resv_Refresh_Needed is initially off and Refresh_PHOP_list is empty.
The logical outgoing interface OI is taken from the LIH in the NHOP object. (If the physical interface is not implied by the LIH, it can be learned from the interface matching the IP destination address).
For FF style: execute the following steps independently for each flow descriptor in the message, i.e., for each (FLOWSPEC, Filtss) pair. Here the structure Filtss consists of the FILTER_SPEC from the flow descriptor.
For SE style, execute the following steps once for (FLOWSPEC, Filtss), with Filtss consisting of the list of FILTER_SPEC objects from the flow descriptor.
For WF style, execute the following steps once for (FLOWSPEC, Filtss), with Filtss an empty list.
If the active RSB has a style that is incompatible with the style of the message, drop the RTEAR message and return.
Build and send any RTEAR messages to be forwarded, in the following manner.
- Search for an RSB (for any outgoing interface) to which the PSB routes and whose Filter_spec_list includes the SENDER_TEMPLATE from the PSB. - If an RSB is found, add the PHOP of the PSB to the Refresh_PHOP_list.
- Otherwise (no RSB is found), add the flow descriptor (Qj,Fj) to the new RTEAR message being built, in a manner appropriate to the style. - Continue with the next PSB.
RERR MESSAGE ARRIVES
A RERR message arrives through the (real) incoming interface In_If.
For WF (wildcard) style, there will be one BSB per (session, PHOP) pair.
For FF style, there will be one BSB per (session, filter_spec) pair. Note that an FF style RERR message carries only one flow descriptor.
For SE style, there will be one BSB per (session, filter_spec), for each filter_spec contained in the filter spec list of the flow descriptor.
- If the FLOWSPEC in the RERR message is strictly greater than the RSB Flowspec, then turn on the NotGuilty flag in the ERROR_SPEC. - Deliver an error upcall to application:
Call: <Upcall_Proc>( session-id, RESV_ERROR, Error_code, Error_value, Node_Addr, Error_flags, Flowspec, Filter_Spec_List [ , Policy_data] )
and continue with the next RSB.
RESV CONFIRM ARRIVES
Call: <Upcall_Proc>( session-id, RESV_CONFIRM, Error_code, Error_value, Node_Addr, LUB-Used, nlist, Flowspec, Filter_Spec_List, NULL, NULL )
Drop the RACK message and return.
UPDATE TRAFFIC CONTROL
The sequence is invoked by many of the message arrival sequences to set or adjust the local traffic control state in accordance with the current reservation and path state. An implicit parameter of this sequence is the `active' RSB.
If the result is to modify the traffic control state, this sequence notifies any matching local applications with a RESV_EVENT upcall. If the state change is such that it should trigger immediate RESV refresh messages, it also turns on the Resv_Refresh_Needed flag.
- Compute the effective kernel flowspec, TC_Flowspec, as the LUB of the FLOWSPEC values in these RSB's.
- Compute the effective traffic control filter spec (list) TC_Filter_Spec* as the union of the Filter_spec_lists from these RSB's. - If the active RSB has a FLOWSPEC larger than all the others, turn on the Is_Biggest flag.
If none is found, create a new TCSB.
TC_AddFlowspec( OI, TC_Flowspec,
Path_Te, police_flags)
-> Rhandle, Fwd_Flowspec
TC_AddFilter( OI, Rhandle, Session, F)
-> Fhandle
and record the returned Fhandle in the TCSB.
TC_DelFlowspec( OI, Rhandle )
TC_ModFlowspec( OI, Rhandle, TC_Flowspec,
Path_Te, police_flags )
-> Fwd_Flowspec
Call: <Upcall_Proc>( session-id, RESV_EVENT, style, Flowspec, Filter_spec_list [ , POLICY_DATA] )
where Flowspec and Filter_spec_list come from the TCSB and the style comes from the active RSB.
PATH REFRESH
This sequence sends a path refresh for a particular sender, i.e., a PSB. This sequence may be entered by either the expiration of a refresh timer or directly as the result of the Path_Refresh_Needed flag being turned on during the processing of a received PATH message.
RESV REFRESH
This sequence sends a reservation refresh towards a particular previous hop with IP address PH. This sequence may be entered by the expiration of a refresh timer, or invoked from the PATH MESSAGE ARRIVES, RESV MESSAGE ARRIVES, RTEAR MESSAGE ARRIVES, or RERR MESSAGE ARRIVES sequence.
In general, this sequence considers each of the PSB's with PHOP
address PH. For a given PSB, it scans the TCSBs for matching
reservations and merges the styles, FLOWSPECs and
Filter_spec_list's appropriately. It then builds a RESV message
and sends it to PH. The details depend upon the attributes of
the style(s) included in the reservations.
Initially the Need_Scope flag is off and the new_SCOPE object is empty.
- If TCSB contains a CONFIRM object, then create and send a RACK message containing the object and delete the CONFIRM object from the TCSB. - Continue with next PSB.
- Select BSB's that match this TCSB. If a selected BSB is expired, delete it. If any of the unexpired BSB's has a Qb that is not strictly larger than TC_Flowspec, then continue processing with the next TCSB.
However, if steps 1 and 2 result in finding that all TCSB's matching this PSB are blockaded, then:
- If this RESV REFRESH sequence was invoked from RESV ERROR RECEIVED, then return to the latter. - Otherwise, turn on the B_Merge flag and restart at step 1, immediately above.
- If B_Merge flag is off, compute the LUB over the flowspec objects. From each TCSB, use the Fwd_Flowspec object if present, else use the normal Flowspec object.
While computing the LUB, check for a RESV_CONFIRM object in each TCSB. If a RESV_CONFIRM object is found:
- If the flowspec (Fwd_Flowspec or Flowspec) in that TCSB is larger than all other (non- blockaded) flowspecs being compared, then save this RESV_CONFIRM object for forwarding and delete from the TCSB. - Otherwise (the corresponding flowspec is not the largest), create and send a RACK message to the address in the RESV_CONFIRM object. Include the RESV_CONFIRM object in the RACK message. The RACK message should also include an ERROR_SPEC object whose Error_Node parameter is IP address of OI from the TCSB and specifying "No Error". - Delete the RESV_CONFIRM object from the TCSB. - Otherwise (B_Merge flag is on), compute the GLB over the Flowspec objects of this set of TCSB's.
While computing the GLB, delete any RESV_CONFIRM object object in any of these TCSB's.
Distinct reservation (FF) style
Use the Sender_Template as the merged FILTER_SPEC. Pack the merged (FLOWSPEC, FILTER_SPEC, F_POLICY_DATA) triplet into the message as a flow descriptor.
Shared wildcard reservation (WF) style
There is no merged FILTER_SPEC. Merge (compute the LUB of) the merged FLOWSPECS from the TCSB's, across all PSB's for PH.
Shared distinct reservation (SE) style
Using the Sender_Template as the merged FILTER_SPEC, form the union of the FILTER_SPECS obtained from the TCSB's. Merge (compute the LUB of) the merged FLOWSPECS from the TCSB's, across all PSB's for PH.
- Find each RSB that matches this PSB, i.e., whose Filter_spec_list matches Sender_Template in the PSB and whose OI is included in OutInterface_list. - If the RSB either has no SCOPE list or its SCOPE list includes the sender IP address from the PSB, insert the sender IP address into new_SCOPE.
ROUTE CHANGE NOTIFICATION
This sequence is triggered when routing sends a route change notification to RSVP.
PATH LOCAL REPAIR
The sequence is entered to effect local repair after a route change for a given PSB.
[Baker96] Baker, F., "RSVP Cryptographic Authentication", Work in Progress.
[RFC 2205] Braden, R., Ed., Zhang, L., Berson, S., Herzog, S., and S. Jamin, "Resource ReSerVation Protocol (RSVP) -- Version 1 FunctionalSpecification", RFC 2205, September 1997.
[RFC 2207] Berger, L. and T. O'Malley, "RSVP Extensions for IPSEC IPv4 Data Flows", RFC 2207, September 1997.
[RSVP93] Zhang, L., Deering, S., Estrin, D., Shenker, S., and D. Zappala, "RSVP: A New Resource ReSerVation Protocol", IEEE Network, September 1993.
Processing the RSVP INTEGRITY object [Baker96] is only mentioned in this memo, because the processing rules are described here only in general terms. The RSVP support for IPSEC [RFC 2207] will imply modifications that have not yet been incorporated into these processing rules.
Bob Braden
USC Information Sciences Institute
4676 Admiralty Way
Marina del Rey, CA 90292
Phone: (310) 822-1511
EMail: Braden@ISI.EDU
Lixia Zhang
UCLA Computer Science Department
4531G Boelter Hall
Los Angeles, CA 90095-1596 USA
Phone: 310-825-2695
EMail: lixia@cs.ucla.edu