\section{Routing of Requests}
\label{sec:rr}

\begin{changebar}
Record routing is the process whereby a proxy server can request to
receive all messages between two UAs for a particular call leg.  The
proxy accomplishes this by inserting a header, called
\header{Record-Route} into the initial request that begins the
call leg. The user agents use these headers to construct a set of
\header{Route} headers, that gets inserted into subsequent requests in
the call leg.  The \header{Route} headers contain a set of elements
that the request must visit.  Proxies use these to forward the
requests, much like strict IP source routing.
\end{changebar}

The process of record-routing works for any SIP request that initiates
some kind of session. For this specification, that includes only
{\INVITE}. Extensions {\MAY} identify new requests as ones which
initiate sessions, in which case the procedures defined here apply to
processing of those requests.

All user agents {\MUST} support the processing rules below which apply to
them.  As such, they {\MUST} be able to parse and process both
\header{Record-Route} and \header{Route} headers.  Proxies {\MAY}  support
the record routing procedures of Section \ref{sec:rr:proxy}, but they
\MUST support the route header procedures of Section{sec:rr:proxy2}. 

\motivation{This is a change from RFC2543, where all record-route and
route processing was optional for user agents.}

The syntax for the \header{Route} header is described in Section
\ref{sec:Route}. The syntax for the \header{Record-Route} header is
described in Section \ref{sec:Record-Route}.

\subsection{UAC Processing for initial transaction}
\label{sec:rr:uac}

The UAC formulates its {\em initial} request for the session
as defined in section \ref{sec:ua-invitation}.  If the final
response is a 200 class response, it may contain \header{Record-Route}
headers, and may contain a \header{Contact} header.
\motivation{Contact was not mandatory in RFC2543.  Thus, if the UAC is
talking to an older UAS, the UAS might not insert the \header{Contact}
header.  Thus, this text says that the
\header{Contact} ``may'' be present in the response.  Note also that this
may is lower case; it is NOT saying that a UAS compliant to this
specification can optionally insert the
\header{Contact} header into the 200-class response.} The UAC {\MUST}
construct a {\em route set}, defined as a list of URIs, in the following
manner:

\begin{enumerate}

\item The list of URIs present in the \header{Record-Route} headers in
the 200 class response are taken, if present, including all URI
parameters, and their order is reversed.

\item The URI in the \header{Contact} header from the 200 class
response, if present, is taken, including all URI parameters, and
appended to the end of the list from the previous step.

\item The list of URIs resulting from the above two operations is
referred to as the {\em route set}.

\end{enumerate}

The UAC {\MUST} store the route set for the duration of the call leg. 
NOTE that it is possible for the route set to be empty.  This will occur
if neither \header{Record-Route} headers nor a \header{Contact} header
were present in the 200 class response.  Since there may be multiple 200
OK responses to an {\INVITE} request, each response constitutes a
separate call leg, and thus has a separate route set.  The UAC {\MUST}
also remember whether the bottom-most entry in the route set was
constructed from a \header{Contact} header or not.  This is 
a boolean value, which we refer to as CONTACT\_SET.

An {\ACK} request for the 200 class response to an initial {\INVITE}
transaction {\MUST} be formulated according to the rules of Section
\ref{sec:ua-ack}, as if it were a subsequent request within the call
leg. That is, the {\ACK} for a 200 class response contains
\header{Route} headers.

\header{Record-Route} headers {\MAY} be present in a provisional
response to {\INVITE}. In this case, the UAC can construct a route set for the
call-leg associated with that provisional response, in the same way it
would construct a route set for a 200 class response. This route set
will only be needed if the UAC sends a request to the far end of the
call leg before the initial {\INVITE} transaction completes.

\subsection{UAS Processing of initial transaction}
\label{sec:rr:uas}

When a UAS receives a request for a new call session, and it
responds with a 200 class response, it {\MUST} copy the contents of the
\header{Record-Route} headers from the request to the response.  This
includes the URIs, URI parameters, and any \header{Record-Route} header
parameters, whether they are known or unknown to the UAS. 
\motivation{Record-Route parameters are very useful for proxies.  They
allow the proxy to match the record-route entry in the response with the
one in the request.} The order of the \header{Record-Route} headers
{\MUST} be preserved in the response.

The UAS {\MUST} construct a {\em route set} in the following manner:

\begin{enumerate}
\item The list of URIs in the \header{Record-Route} headers in the
initial request, if present, are taken, including any URI parameters.

\item The URI in the \header{Contact} header from the request, if
present, is taken, including any URI parameters.  The URI is appended to
the bottom of the list of URIs from the previous step. 

\item The resulting list of URIs is called the {\em route set}. 

\end{enumerate}

The UAS {\MUST} store the route set for the duration of the call leg. 
It is possible for the route set to be empty.  This will occur if
neither \header{Record-Route} headers nor a \header{Contact} header were
present in the initial request.  The UAS {\MUST} also remember whether
the bottom-most entry in the route set was constructed from a
\header{Contact} header or not.  This is effectively a boolean value,
which we refer to as CONTACT\_SET. 

If the UAS sends provisional responses before the session is accepted, it
{\SHOULD} copy the \header{Record-Route} headers from the request into
the provisional responses in the same manner described above for the
200 class response. 

\subsection{Proxy procedures for record routing a transaction}
\label{sec:rr:proxy}

Each proxy {\MAY} independently decide to record-route a transaction
that initiates a session. Amongst the methods defined in this
specification, that includes only the {\INVITE} transaction. However,
extensions {\MAY} designate new methods as ones that initiate a
session of some sort. In that case, the procedures described here
apply to those requests. Both the initial request that initiates the
session, and any refreshes (such as a re-{\INVITE}) {\MUST} be
record-routed if the the initial request was record routed. This means
a proxy will often need to record-route requests that contain
\header{Route} headers. \annotation{The purpose of record-routing
mid-call requests, like a re-{\INVITE}, 
is twofold.  First, it allows for proper record-routing in the case of
pre-loaded Route headers (see Section \ref{sec:rr:preloaded}).
Secondly, it allows for optional recovery from a UA crash and restart,
in which case the UA loses call state, and as a result, its route set
as well.  
} Generally, the choice about whether to
record-route or not is a tradeoff of features vs.  performance.
Faster request processing and higher scalability is achieved when
proxies do not record route.  However, provision of certain services
may require a proxy to observe all messages for a call leg.  It is
{\RECOMMENDED} that proxies do not automatically record route.  They
should do so only if specifically required.

To record-route, the proxy inserts a \header{Record-Route} header into
the request before proxying it onwards.  A forking proxy {\MAY} insert a
different \header{Record-Route} header into each forked request.  The
\header{Record-Route} header that it inserts {\MUST} be inserted as the
first \header{Record-Route} header, appearing before any existing ones
in the request.  The URL in the header {\MUST} be a SIP URL. 
\annotation{This is because the URLs in the Record-Route headers are used
for forwarding requests by other proxies.  Since no other URL but a SIP
URL is mandatory, a proxy could not be sure that any other URL is
interpretable by other proxies.  Thus, SIP URLs are mandatory}.
\begin{changebar}The URL 
\SHOULDNOT contain the transport parameter, but can in private
networks where it is known the next downstream proxy to record-route
supports the specific transport. \end{changebar} \annotation{Thats
because only UDP is mandatory.  If a proxy inserts a transport
parameter in the URL with TCP or TLS as the transport, the proxy that
ends up using that URL to forward the request might not support that
transport.  The result, according to the ``Locating a SIP Server''
procedure, would be for the proxy to give up.} The URL {\MUST} have
the property that when the processing described in
\cite{draft-ietf-sip-srv} is followed for that URL, the result of the
lookup is an address/port of the proxy server inserting the
\header{Record-Route}.  The URL and the proxy configuration {\SHOULD}
be such that if a request is received with this URL in the
\header{Request-URI}, the proxy's normal request processing will cause
it to be forwarded to one of the previous-hop servers that the request
traversed, including the UAS.
\motivation{These two properties are important.  The first one guarantees
that subsequent requests from the called party are routed back to this
actually proxy.  The second property is there for robustness.  It
guarantees that the request URI always contain meaningful information,
even if there are no \header{Route} headers that tell the proxy where to
forward the request to next.} The URL placed into the
\header{Record-Route} header {\MUST} be unique for each unique
\header{Request-URI} in the request, but must not equal the
\header{Request-URI} of the request (they will not be equal
if the proxy adds an maddr parameter). \annotation{Why is this the
case? The reason has to do with record-routing through spirals. When a
proxy record-routes through a spiral, the URI in the RR needs to be
different each time through the spiral. If it weren't, when the called
party send a re-{INVITE}, two of the \header{Route} headers will be identical,
resulting in a loop.} The proxy {\MAY} insert
\header{Record-Route} header parameters into the request.  These will be
returned to the proxy in any 200 class response to the \INVITE, and are
useful for pushing state into the message.

If a 200 class response arrives for the proxied request, the response will
contain the entire list of \header{Record-Route} headers inserted by
proxies along the request path.  The proxy {\MAY} modify the
\header{Record-Route} value matching the one it inserted into the
request.  \begin{changebar} Like the URL in the request, it {\MUST} be
a SIP URL and \SHOULDNOT contain a transport parameter.  However, it
{\MAY} contain a transport parameter if the proxy knows that the next
record-routing proxy upstream supports the specific
transport. \end{changebar} The URL in this
\header{Record-Route} header {\MUST} have the property that when the
processing described in \cite{draft-ietf-sip-srv} is followed for that
URL, the result of the lookup is an address/port of the proxy server
that inserted the \header{Record-Route}.  The URL in this header, and
the proxy configuration {\SHOULD} be such that if a request is
received with this URL in the \header{Request-URI}, the proxy's normal
request processing will cause it to be forwarded to the same next hop
server that the original request was forwarded to. The URL
placed into the \header{Record-Route} header {\MUST} be unique for each unique
\header{Request-URI} in the request, but must not equal the
\header{Request-URI} of the request (they will not be equal
if the proxy adds an maddr parameter).

The four properties (two for the request, two for the response), can be
satisfied in a number of ways.  One way is that the URL inserted into
the \header{Record-Route} in the request is nearly the same as the
\header{Contact} header in the initial request (if present, else the
\header{From} field), but with the maddr and port set to resolve to the
proxy, and with a transaction identifier added to the user part of the
request-URI (in order to meet the requirement that the URI in the
\header{Record-Route} be different for each distinct
\header{Request-URI}). Then, the proxy modifies the URL in the
\header{Record-Route} 
header in the response, setting it to be the URL from the
\header{Request-URI} of the initial request, but with the maddr and port
set to resolve to the proxy. 

As an example, consider a proxy at 10.0.1.1 listening on port 5061 which
receives the following request (many headers are omitted for brevity):

\begin{verbatim}
INVITE sip:user@example.com SIP/2.0
Via:  SIP/2.0/UDP callerspc.univ.edu
Contact:  sip:caller@callerspc.univ.edu
\end{verbatim}

The proxy forwards this request to
\texttt{sip:j\_user@div11.example.com}, and record-routes:

\begin{verbatim}
INVITE sip:j_user@div11.example.com SIP/2.0
Via: SIP/2.0/UDP 10.0.1.1:5061
Via: SIP/2.0/UDP callerspc.univ.edu
Record-Route: <sip:caller.8jjs0@callerspc.univ.edu:5061;maddr=10.0.1.1>
Contact:  sip:caller@callerspc.univ.edu
\end{verbatim}

The 200 response received by the proxy will look like, in part:

\begin{verbatim}
SIP/2.0 200 OK
Via: SIP/2.0/UDP 10.0.1.1:5061
Via: SIP/2.0/UDP callerspc.univ.edu
Record-Route: <sip:caller.8jjs@callerspc.univ.edu:5061;maddr=10.0.1.1>
Contact: sip:j_user@host32.div11.example.com
\end{verbatim}

The proxy modifies its \header{Record-Route} header in the response,
resulting in the new response forwarded upstream:

\begin{verbatim}
SIP/2.0 200 OK
Via:  SIP/2.0/UDP callerspc.univ.edu
Record-Route:  <sip:user@example.com:5061;maddr=10.0.1.1>
Contact:  sip:j_user@host32.div11.example.com
\end{verbatim}

The route set computed by the UAS is:

\begin{verbatim}
sip:caller.8jjs@callerspc.univ.edu:5061;maddr=10.0.1.1
sip:caller@callerspc.univ.edu
\end{verbatim}

and the route set computed by the UAC is:

\begin{verbatim}
sip:j_user@example.com:5061;maddr=10.0.1.1
sip:j_user@host32.div11.example.com
\end{verbatim}

There are other ways to meet these requirements.  The proxy could
construct a URL for the request which encodes all of the needed
information, by placing it in the user portion, for example.  A call
stateful proxy could insert a URL into the request with the form
sip:proxy.example.com, and not modify it in the response.  This URL
clearly satisfies the first required property (of getting routed back to
the proxy that inserted it).  The second property can be maintained by
being call stateful, and extracting the needed parameters from local
storage.

When a proxy does decide to modify the \header{Record-Route} header in
the response, one of the operations it must perform is to locate the
\header{Record-Route} that it had inserted.  If the request spiraled,
and the proxy inserted a \header{Record-Route} in each iteration of the
spiral, locating the correct header in the response (which must be the
proper iteration in the reverse direction) is tricky. Note that the
rules above dictate that a proxy insert a different URI into the
\header{Record-Route} for each distinct \header{Request-URI}
received. The two issues can be solved jointly. A {\RECOMMENDED}
mechanism is for the proxy to append a piece of data to the user
portion of the URL. This piece of data is a hash of the transaction
key for the incoming request, concatenated with a unique identifier
for the proxy instance. Since the transaction key includes the
\header{Request-URI}, this key will be unique for each distinct
\header{Request-URI}. When the response arrives, the proxy modifies
the first \header{Record-Route} whose identifier matches the proxy
instance. The modification results in a URI without this piece of data
appended to the user portion of the URI. Upon the next iteration, the
same algorithm (find the topmost \header{Record-Route} header with the
parameter) will correctly extract the next
\header{Record-Route} header inserted by that proxy.

\subsection{UA Processing of Subsequent Requests in a Call Leg}
\label{sec:rr:uasubsequent}

When a UA wishes to send another request for the call-leg (such as a
\header{BYE} or \header{INVITE}), it follows the procedures defined in
this subsection.  The procedures here {\MUST} also be followed for an
\ACK request for a 200 response to the initial {\INVITE} for a call
leg.  The procedures here \MUSTNOT be followed for a \CANCEL request or
an \ACK request for a non-200 class response.  This implies that
\CANCEL for an initial {\INVITE} never contains a \header{Route}
header, nor does an \ACK for a non-200 response.

The request is constructed as specified in Section \ref{sec:ua-sub}.
The UA then takes the list of URI in the route set.  The top URI is
inserted into the request URI of the request, including all
parameters.  Any URI parameters not allowed in the request URI {\MUST}
then be stripped.  Each of the remaining URIs (if any) from the route
set, including all URI parameters, are placed into a \header{Route}
header into the request, in order.  The procedures of
\cite{draft-ietf-sip-srv} are then applied to the URI in the request
URI, the the request is forwarded to the resulting server.

If a UAS has a route set for a call leg, and receives a refresh for
that call leg containing \header{Record-Route} headers (the only
refresh defined in this specification is a re-{\INVITE}), it {\MUST} copy
those headers into any 200 class response to that request.  If the
boolean variable CONTACT\_SET is true, the \header{Contact} header in
the request (if present) replaces the last entry in the route set.  If
the boolean variable CONTACT\_SET is false, the UAS {\MUST} add the URL
in the \header{Contact} header in the re-{\INVITE} to the bottom of the
route set, and then set CONTACT\_SET to true.  If the request did
not contain a \header{Contact} header, the route-set at the UAS remains
unchanged.

Similarly, if a UAC has a route set for a call leg, and receives a 200
class response to a refresh it sent, the \header{Contact} header is
examined.  If not present, the route set remains unchanged.  If the
response had a \header{Contact} header, and the boolean
variable CONTACT\_SET is false, the URL in the \header{Contact} header
in the response is added to the bottom of the route set, and CONTACT\_SET
is set to true.  If the re-{\INVITE} response had a \header{Contact}
header, and CONTACT\_SET is true, the URL in the \header{Contact} header
of the re-{\INVITE} response replaces the bottom value in the route set.

The above two paragraphs allow a UA to update its \header{Contact}
address mid-call, but proxies cannot update their route address.  Once
on the route, a proxy remains on the route for the duration of the
call leg.  \motivation{Why the different treatment for Contact and
Record-Route in a re-{\INVITE}?  It has to do with backwards
compatibility.  RFC2543 did not mandate that a proxy needs to refresh
its record-route headers.  As a result, the lack of a record-route in
a re-{\INVITE} cannot be interpreted to mean that the proxy does not want
to be included on the route any longer.  Updating of the
\header{Contact} header mid-call is useful for mobility applications,
and is also useful for forms of third party call control}.

\subsubsection{Local outbound proxies}

Special considerations exist for local outbound proxies.

A UA which uses a local outbound proxy will send all requests without
\header{Route} headers to that proxy. Typically, this includes initial
{\INVITE} requests for a call. 

If a local outbound proxy wishes to remain on the SIP messaging path
for a call leg, it {\MUST} record-route using the procedures
above. \annotation{You might think that this isn't needed. After all,
if the UA sent the first request to its local outbound proxy, why
can't it send all requests for the call leg there? In that case, it
wouldn't need to insert record-route into the response. However, a
proxy has no reliable way to know whether it received a request
because the previous hop is configured to use it as a local outbound
proxy. So, to be sure it stays on the path, it needs to
record-route}.

A UA which uses a local outbound proxy, and attempts to send a
subequent request in a call leg with a route set, {\SHOULD} use the
procedures in Section
\ref{sec:rr:uasubsequent}. \begin{changebar} However, in some
instances, a UA may not be 
willing or capable of sending the request to the top element in the
route set. One example is a UA that is not
capable of DNS, and therefore may not be able to follow those
procedures. In these cases, the UA {\MAY} send the request to a local
outbound proxy. In this case, it {\MUSTNOT} remove the top
\header{Route} header. If the UA is the caller, it sets the
\header{Request-URI} to the same value it used for the initial
request, and sends it to its local outbound proxy. 
\end{changebar}

\subsection{Proxy routing procedures}
\label{sec:rr:proxy2}

The rules in this section {\MUST} be followed by all proxies to
determine the appropriate routing procedures to apply to a
request. Proxies {\MAY} respond to requests with \header{Route}
headers for any reason (in order to perform proxy authorization, for
example).  But, if the request is to be proxied, the procedures here
{\MUST} be used to determine where the request is proxied to.  The
procedures in this section apply indepedent of the request method.
They {\MUST} be followed even if the request method is unknown to the
proxy.
\annotation{This last sentence is really, really important.  It allows for
other methods, defined in the future, to have record-routing applied
to them.  As an example, an instant messaging session run over SIP
might begin with a {\MESSAGE} request.  That extension can allow for
these sessions to be record-routed by proxies that know of this
extension.  However, the record-routing will only work if proxies that
don't know about the extension follow the Route headers properly.  As
such, supporting \header{Route} headers for all methods, known or
unknown, is very important for a robust and future proof proxy
implementation.} Since {\CANCEL} can never contain \header{Route},
these procedures never apply to {\CANCEL}.  However, they do apply to
{\ACK} requests for a ``200 OK'' response, which do contain
\header{Route} headers.

When a proxy receives a request, it {\MUST} check for the existence of a
\header{Route} header. If one exists, it {\MUST} pop that
\header{Route} header, and place it (including all URI parameters)
into the \header{Request-URI}. Any URL parameters present in the top
\header{Route} header which are 
not allowed in the request URI {\MUST} be removed from the
\header{Request-URI} by the proxy.It
{\SHOULD} be sent using the procedures of
\cite{draft-ietf-sip-srv}. If no \header{Route} header is present, the
proxy examines the \header{Request-URI}. If it contains an maddr
parameter, and the address in maddr is not an
interface that the proxy is listening on, the proxy {\SHOULD} forward the
request using the procedures of \cite{draft-ietf-sip-srv} on the
\header{Request-URI}. This will cause it to be forwarded to the
address in the maddr. If the maddr is present, but is an interface the
proxy is listening on, the proxy {\MUST} strip the maddr, and then
continue processing as if it were never there. If there was no maddr
(or if it was stripped in the previous step), and the domain of the
\header{Request-URI} is not a domain the proxy is managing, the
procedures of \cite{draft-ietf-sip-srv} {\SHOULD} be used to forward the
request to that URI. If the domain is one the proxy is managing, the
request is processed by whatever policies are desired by the
administrator. 

Stateless proxies are limited in the policies they may apply for
routing. Specifically, stateless proxies {\MUST} have routing policies
that can be expressed as a combinatoric function of the fields of the
incoming request and static configuration parameters. This explicitly
excludes probabilistic routing, time-of-day routing, or other dynamic
mechanisms. As a result of this restriction, a proxy that supports
run-time configuration changes will need to process transactions
statefully for some time if the configuration change affects routing.
\annotation{This restricton exists to make sure that request
retransmissions, {\CANCEL}s and {\ACK}s for a transaction are always
routed to the same place.}

\subsection{Pre-Loaded Route Headers}
\label{sec:rr:preloaded}

Normally, a UA constructs the Route headers in a request from the route
set learned through \header{Record-Route} headers.  However, in some
circumstances, it is useful for a UA to insert \header{Route} headers
into an initial request.  These headers may have been learnt by the UA
through some out of bands means.  When an initial request (initial as
far as the UAC and UAS are concerned) contains \header{Route} headers,
this is referred to as a ``pre-loaded Route''.  It is equivalent to
strict source routing in IP.  Proxies will often not be able to
distinguish this case from the case described in Section
\ref{sec:rr:proxy}, and will therefore properly use these route headers
to forward the request.  If the proxies are interested in receiving
subsequent messages for the call leg, their insertion of
\header{Record-Route} as mandated by Section \ref{sec:rr:proxy} will
establish a correct route set at both UAC and UAS.  This route set may
end up being different from the pre-loaded Route used by the UAC.  As
such, a UAC that inserts a pre-loaded route set {\MUST} follow the
procedures of Section \ref{sec:rr:uac} in processing the response to
this initial \INVITE.
