Fast Path Characterization Protocol (FPCP)
Version of Tuesday, September 19, 2000 22:49 -0700

Todo

This section is here to record things that need to be addressed.  It is not really part of this document.

• partial trace
• forced next hop to deal with path fork problem -- This is a MAJOR problem - See "Force Next Hop" objects.
• In IPv6 is there enough specificity in having one IP address to identify an interface, or the converse, might there be confusion by having possibly multiple different addresses refer to the same interface?
• What about NATs?  Should we break the trace at a NAT and have the querying application deal with it?  (NATs may also break the reply-to-udp address.)
• Might we want a "suppress" data mechanism to hid hops that are fast/low latency/small-congestion?
• Might we want multiple objects, similar to the WRED object, to represent various queuing disciplines and drop disciplines?

Abstract

FPCP (Fast Path Characterization Protocol) is a fast and inexpensive way to obtain information about a path through the Internet.  FPCP is intended to be used by content management systems in order to evaluate content placement options.  FPCP also serves as an alternative to troubleshooting tools such as "traceroute".

FPCP operates by sending a probe packet along the path to be evaluated.  The FPCP probe contains a description of a hypothetical flow.  The routers along the path examine the hypothetical flow and append appropriate router and link information to the probe packet before forwarding that packet to the next hop router.  When the probe has reached the end of the path, the accumulated information is sent back to the querying application for analysis.

FPCP may be used in both IPv4 and IPv6 networks.

FPCP contains mechanisms to handle various conditions such as forwarding loops, forwarding paths that fork, non-FPCP aware routers, excessive growth of probe packets, etc.

The FPCP packet structure is based on type-length-value structures.  This will ease the burden of extending the capabilities of FPCP in the future.

FPCP does not require real-time processing within the high-speed forwarding paths of routers.  Rather FPCP is designed to be handled at low priority.

Table of Contents

• Overview

• Packages and Objects

  • Objects

    • Object Header

  • Packages

    • Package Header

• Packet Format

• Packages

  • Query Package

  • Initial Hop Data Package

  • Next Hop Data Package

  • Path Fork Data Package

• Objects

  • Reporting IP Address IPv4
  • Reporting IP Address IPv6
  • Reply-To IPv4 UDP address
  • Reply-To IPv6 UDP address
  • Start-IP address IPv4
  • Start-IP address IPv6
  • Force Next Hop IPv4
  • Force Next Hop IPv6
  • Hypothetical IPv4 header
  • Hypothetical IPv6 header
  • Hypothetical sender TSPEC
  • Link Type
  • Link Speed
  • Link HighSpeed
  • Link Transit Time Estimate
  • Link Loss Estimate
  • Router Latency Estimate
  • Router Drop Probability Estimate
  • WRED Estimate
  • Next Hop IPv4
  • Next Hop IPv6
  • Possible Path IPv4
  • Possible Path IPv6

• IPv4 and IPv6

• Numeric Precision

• When the Probe Packet Grows Too Large

• Obtaining Information About the Initial link

• Dealing With Forking Paths

• Loop Suppression

• Measuring A Partial Path

• What Happens When An FPCP Packet Is Lost

• How A Router Processes A Received FPCP Packet ("Elements of Procedure")

• The Querying Application

• Number Assignments

• Security

• Acknowledgements

• References

• Authors

Overview

FPCP is the Fast Path Characterization Protocol.

There is a need on the Internet for people and applications to ascertain whether the network path between a pair of potential communications partners will be adequate.  There is a similar need to evaluate the relative merits of different network paths when selecting among multiple potential communications peers.

In many instances people or applications make rough guesses based on inadequate and possibly misleading data.  Among the most frequently used data are the ICMP Echo (Ping) or DNS query round trip time and the number of hops on what may or may not be the one-way path from one point on the net to another.

TCP's flows, particularly when they are carrying more than a few segment size's worth of of data, are often more sensitive to path bandwidth and packet loss than they are to hop counts and round trip times.  Consequently, when evaluating a path for a data flow of more than trivial size that will be carried using TCP, one is probably more interested in bandwidth and loss than hop count and round trip time.  (Note: For small size transfers, ones in which the transfer time will be dominated by TCP connection and tear-down handshakes rather than by the data transfer itself, round trip time is probably more relevant than bandwidth.  Similarly, transfers that involve a lot of end-to-end interactions tend to be more affected by round-trip-time than by bandwidth.)

The increasing presence of mechanisms such as policy routing, flow-based traffic pacing and traffic shaping, QoS, fair queuing, and asymmetrical routes further tends to diminish the value of simple ping-based or DNS based round trip time estimates - it is unlikely that the ping or DNS query will be given the same QoS or routing treatment as the proposed flow.

Tools such as Pathchar, pchar, and clink can provide better data on which to evaluate a network path.  But those tools are packet intensive and require a long period of time to accumulate the data.  And they are blind to any QoS, policy, or priority handling that may be accorded to certain data streams.

FPCP is designed to fill this information gap.  FPCP is designed to quickly measure the actual path that the user's data will follow.  (Each direction is evaluated using a distinct FPCP operation.)

In the best case, FPCP can obtain information on a path in slightly more than one round trip time.

Router processing of FPCP packets is intended to be lightweight and may occur at relatively low processing priorities.  (In other words FPCP could be handled by low priority software in the routers.)  Most of the burden of FPCP falls on the device that is making the query, and even then the burden is fairly small - probably about the same as would fall on an multicast traceroute (MTRACE) client.

The FPCP probe packet is unicast from each hop to next with the destination address being changed at each step to be the next hop router; the Router Alert IP option is neither necessary for- nor used by- FPCP.

Each FPCP probe packet contains an embedded IP header the describes the hypothetical flow that is being evaluated.  Each router uses that hypothetical header to examine how it would handle an IP packet with that header and appends an FPCP information package to the probe packet.

An optional hypothetical TSPEC [RFC2215] may be sent along with the hypothetical IP header in order to describe the dynamics of the hypothetical traffic flow.

An FPCP query begins when a querying application sends a probe packet to the first router in a path.  That router uses the hypothetical IP header (and optional TSPEC) in the probe packet to examine the routers forwarding tables.  The router determines the next router to which the hypothetical IP packet would be sent and appends an information package to the probe packet.  The revised probe packet is then addressed to, and sent directly to, that next router.

This bucket-brigade procedure continues until the probe packet either reaches the last hop router, the path forks (perhaps due to load balancing), or the probe packet has accumulated so many packages that it has grown too large.  When any of these events occurs, the accumulated probe packet is sent back to the querying application and the FPCP processing by the routers ceases.  If the full path was not evaluated, it is up to the querying application to pick up where the query left off.  For example, if the probe packet became too large and was returned to the querying application, it would be up to the application to start a new FPCP with a new, empty probe starting at the router where the oversize condition occurred.

There are special-case mechanisms to deal with the initial link from a host to its first hop router and when the probe packet vanishes into a router that does not support FPCP.  (These are described later.)

FPCP processing contains tests to detect queries that loop due to single or multiple hop forwarding loops.

For convenience in implementation (and to obtain the protection of a checksum) all FPCP packets are encapsulated in UDP.

The current design of FPCP has the probe packet being forwarded explicitly from each router to the next.  This makes FPCP sensitive to non-participating routers - such routers require an FPCP client to engage in a rather slower "traceroute" technique to walk pas the non-participating router(s).  Consequently, it is possible that a variation of FPCP will be defined in which the probe packet is addressed to the ultimate destination IP address and has the Router Alert Option.

FPCP is not expected to be a burden on routers.  The software processing load to handle an FPCP packet is anticipated to be reasonably low if the software has a reasonably efficient means to inquire how a hypothetical IP packet would be routed were it to arrive on a particular interface.  (In addition, if the hypothetical packet could be forwarded down multiple paths, FPCP needs to be able to ascertain that fact and to enumerate the set of possible immediate next hops.)

For each hop along the path FPCP may obtain several kinds of information.  

• Some information about the outgoing interface outgoing link:
  • Link Type (Same enumerated values as in ifType in RFC2233)
  • Link Speed (As defined by ifSpeed and ifHighSpeed in RFC2233)

  • Link MTU  (As defined by ifMTU in RFC2233)

• Estimates for the time that would be required for the hypothetical packet to move through the router and over the outgoing link to the next hop or the final destination.  Each of these estimates is accompanied by an a statistical measure of its accuracy.  It is intended that the sum of all the time estimates for all hops will approximate the actual end-to-end delay.  The actual time to process and forward an FPCP query has no relationship to these estimates for the hypothetical packet.  This removes any requirement for real-time processing of FPCP itself.

  • Time estimate for the hypothetical packet to move from ingress interface to our outgoing interface.  (I.e. internal delay.)

  • Time estimate for the hypothetical packet to transit the link between the outgoing interface and the next hop interface.  (I.e. external delay.)

• Estimates of the chances that the hypothetical packet would be dropped (intentionally or otherwise) within the router or lost (perhaps due to noise or other causes) on the link to the next router.  As with the time estimates, each of these estimates is accompanied by a statistical measure of its accuracy.  It is intended that the sum of all the loss estimates for all hops will approximate the actual end-to-end loss probability.

  • Chance that the hypothetical packet will be dropped somewhere in this router/switch.  (I.e. internal loss rate.)
  • Description of packet drop disciplines that would be applied to the hypothetical flow such as WRED.

  • Chance that the hypothetical packet will be lost somewhere on the link between the outgoing interface and the next hop interface.  (I.e. external loss rate.)

When in a network in which FPCP is active on all routers, FPCP serves as an alternative to Path MTU Discovery and traceroute.

When used as a means of comparing the paths between a network client and a set of potential servers, FPCP becomes a useful means for content management systems to ascertain which server have the best effective communications with the client.

Packages and Objects

FPCP two kinds of composite structures - objects and packages.

Of the two, objects are the more basic structure.

Objects are built from basic data elements, usually numbers.

Packages contain zero or more objects.  Packages may contain only certain kinds of objects, however, an implementation that encounters an object that it does not comprehend MUST skip over and ignore that object for purposes of its own processing.  An implementation MUST forward all packages and objects along the FPCP query path even if the implementation does not understand those packages and objects.

Packages do not contain other packages.

Objects may never be used alone - they are always wrapped within a package.

The order of packages within a packet may be significant; implementations MUST preserve package order.

Packages and objects are all composed of an integral number of bytes.   Packages and objects are packed; no padding bytes are used between packages and objects.  Hence some packages and objects may not fall on the "natural" memory boundaries of any particular machine.  Programmers should take care that their software allows for generalized byte alignment of packages, objects, and object contents.

The specific kinds of packages and objects will be described in detail later in this document.

Objects

An object is essentially a named datum.  Depending on the object that datum is a single fundamental type or it may be a composite structure of other basic types.

Objects are identified by a type code.  Object type codes are unique across all types of packages.

An implementation that encounters an object that it does not comprehend MUST skip over and ignore that object for purposes of its own processing.  Objects that are not understood MUST be forwarded, unchanged, as the FPCP packet is processed.

Objects are found only wrapped within a package.

The order of objects within a package may be significant; implementations MUST preserve object order.

Although order of objects must be preserved when packages are are relayed, unless an order is mandated by the specification, an implementation is free to generate the objects in a package in any order.  Note: since it would not be surprising to see FPCP object parsers with order sensitivity, it is suggested that to avoid inducing failures in those admittedly out-of-specification conservative implementations a gracious FPCP implementation may wish to take some care to generate objects in the sequence in which they appear in the object definitions.

All objects begin with a standard header.

Object Header

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  | Object contents...            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Packages

Packages are much like what are called "objects" in RSVP [RFC2205] and COPS [RFC2748] - they are distinct chunks of information that are appended to the FPCP probe packet as it moves through a sequence of routers.  The order of packages is important and routers MUST append any packages after other packages, if any, in the packet.  A router MUST NOT disturb the order or content of any other packages in the packet.

Each package is self-describing - every package contains a tag that identifies the package type (and hence the format of its contents) as well as a length indicator.

An implementation that encounters a package that it does not comprehend MUST skip over and ignore that package, including all the objects that that package might contain.   Packages that are not understood MUST be forwarded, unchanged, as the FPCP packet is processed.

All packages begin with a standard header.

The information in a package may have a limited lifetime.  The package header contains a time-to-live value that establishes the period that the information may be considered valid.

Package Header

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Pkg Type   |    Pkg TTL    |            Pkg Length         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                      Package Contents ...                   ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Packet Format

There is really only one kind of FPCP packet.

The FPCP packet begins with a FPCP header, described below, that is followed by zero or more packages.  All of this is carried within the data portion of a UDP packet.

All FPCP packets take the following form.  Note that every packet contains a Query package.

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  VER  | Status|     Flags     | Hops Left     | Reserved (MBZ)|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|       Query Identifier        |      Maximum packet size      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Query Package...                                            ...
...                                                           ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Zero or more result packages...                             ...
...                                                           ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The fields of the header have the following meanings:

Packages

The following subsections define the various kinds of packages and the objects that they may contain.

Most FPCP packages come in two forms - an IPv4 flavor and an IPv6 flavor.  Each flavor is treated as a distinct kind of package.  See the section on IPv4 

Query Package

A Query package contains information about a hypothetical flow about which the routers are to formulate FPCP results.

A thing to note about the Query Package is that the Reply-To objects may be either IPv4 or IPv6 - this permits the reply to be wrapped in whatever version of IP the querying application would like.

Query IPv4 Package bill-of-materials

Query IPv6 Package bill-of-materials

Initial Hop Data Package:

The Initial Hop Data package contains information about the hop from the source of the hypothetical IP packet to a first hop router.  In other words this is a link coming into the router that is generating the package.

Initial Hop IPv4 Package bill-of-materials

Initial Hop IPv6 Package bill-of-materials

Next Hop Data Package:

The Next Hop Data package contains information about the hop from one router to the next.  A Next Hop Data package contains information about a link that is outgoing from the router that is creating the package.

Next Hop IPv4 Package bill-of-materials

Next Hop IPv6 Package bill-of-materials

Path Fork Data Package:

The Path Fork Data package enumerates the possible forwarding paths that exist when there is more than a single forwarding path.

Path Fork IPv4 Package bill-of-materials

Path Fork IPv6 Package bill-of-materials

Objects

Reporting IP Address IPv4

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |   Reporting IPv4 Address ...  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|... Reporting IPv4 Address     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Reporting IP Address IPv6

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |   Reporting IPv6 Address ...  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|  ... Reporting IPv6 Address                                   |
|                                                               |
|                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Reply-To IPv4 UDP Address Object

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |         UDP Port number       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    Reply-To IPv4 Address                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Reply-To IPv6 UDP Address Object

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |         UDP Port number       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|                    Reply-To IPv6 Address                      |
|                                                               |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Start-IP address IPv4 Object

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |      Start IPv4 Address ...   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... Start IPv4 Address        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Start-IP address IPv6 Object

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |      Start IPv6 Address ...   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|  ... Start IPv6 Address                                       |
|                                                               |
|                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Force Next Hop IPv4 Object

The IP address of the egress interface that is to be used.  This IP address must identify an interface that is operationally and administratively active, however it need not be an interface that would be normally be indicated by routing mechanisms as in interface to be used to forward the hypothetical packet.

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |  Force Next IPv6 Address ...  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  ...Force Next IPv4 Address   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Force Next Hop IPv6 Object

The IP address of the egress interface that is to be used.  This IP address must identify an interface that is operationally and administratively active, however it need not be an interface that would be normally be indicated by routing mechanisms as in interface to be used to forward the hypothetical packet.

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |  Force Next IPv6 Address ...  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|  ...Force Next IPv6 Address                                   |
|                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Hypothetical IPv4 Header Object

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |          IPv4 Header ...      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|  ... IPv4 Header ...                                          |
...                                                           ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Hypothetical IPv6 Header Object

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |          IPv6 Header ...      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|  ... IPv6 Header ...                                          |
...                                                           ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Hypothetical Sender TSPEC Object

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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |   Token Bucket Rate ...       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     ...Token Bucket Rate      |   Token Bucket Size ...       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     ...Token Bucket Size      |   Peak Data Rate ...          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     ... Peak Data Rate        |   Minimum Policed Unit ...    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     ... Minimum Policed Unit  |   Maximum Packet Size ...     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     ... Maximum Packet Size   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Link Type Object

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |            Link MTU           |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                           Link Type                           |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Link Speed Object

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |            Link Speed...        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  ... Link Speed               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Link HighSpeed Object

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |            Link High Speed... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  ... Link High Speed          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Link Transit Time Estimate Object

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  | Link Transit Time Estimate... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|... Link Transit Time Estimate |Link Transit Time Est StdDev...|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|...Link Transit Time Est StdDev|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Link Loss Estimate  Object

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  | Link Loss Est |Loss Est StdDev|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Router Latency Estimate Object

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |          Delay Estimate...    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  ... Delay Estimate           |       Delay Estimate StdDev...|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  ... Delay Estimate StdDev    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Router Drop Probability Estimate Object

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |  Drop Probability Estimate... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... Drop Probability Estimate | Drop Probability Est StdDev...|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|...Drop Probability Est StdDev |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

WRED Estimate Object

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |         Est. TTL              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                  StdDev                       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Next Hop IPv4 Object

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |    Hop Chance   |Outgoing IPv4|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  ... Outgoing IPv4 Interface Address            |Next Hop IPv4|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  ... Next Hop IPv4 Address                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Next Hop IPv6 Object

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |    Hop Chance   |Outgoing IPv6|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|                                                               |
|  ... Outgoing IPv6 Interface Address                          |
|                                                 +-+-+-+-+-+-+-+
|                                                 |Next Hop IPv6|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|                                                               |
|  ... Next Hop IPv6 Address                                    |
|                                                 +-+-+-+-+-+-+-+
|                                                 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Possible Path IPv4 Object

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |    Hop Chance   |Next Hop IPv4|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  ... Next Hop IPv4 Address                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Possible Path IPv6 Object

 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 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Object Type  |   Obj Length  |    Hop Chance   |Next Hop IPv6|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|                                                               |
|  ... Next Hop IPv6 Address                                    |
|                                                 +-+-+-+-+-+-+-+
|                                                 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

IPv4 and IPv6

The choice of IPv4 or IPv6 encapsulation is completely independent of whether FPCP is being used to evaluate an IPv4 or IPv6 path.  An IPv6 FPCP probe may be carried in an IPv4 frame and vice versa.

Indeed, the IP version used for the wrapper may change at each hop at the discretion of the device that is sending the FPCP packet..  The only place that the IP version is nailed down is for the encapsulation used to send the result back to the querying application.

As an overall rule, FPCP packets that contain an IPv4 Query package MUST contain only the IPv4 versions of those packages that have IP version variants.  Similarly those FPCP packets that contain an IPv6 Query package MUST contain only the IPv6 versions of those packages that have IP version variants.

Because the any version of IP may be used to carry an FPCP packet that itself queries any version of IP, it is necessary that the FPCP portion of the packet not depend on information obtained from the enclosing IP and UDP headers.  In particular, the destination IP address from the IP/UDP header is insufficient to indicate to a router that is receiving an FPCP query directly from a querying application (as opposed to receiving it from another router that is bucket-brigading the probe packet) which interface to use to begin the FPCP sequence.  For this reason, the Query Package contains a Start IP address object to indicate the router ingress address at which the probe is to begin.

Numeric Precision

FPCP is not intended to obtain highly precise numbers - one should assume that the results contain relatively few significant digits.

The intent is, rather, to obtain something that is a fair, but not perfect, set of numbers that can be used for comparative purposes with FPCP values obtained between other source/destination pairs.

It is expected that when one wants more precise values that one will resort to SNMP and MIBs. 

When the Probe Packet Grows Too Large

A probe packet gets larger and larger as it moves through a sequence of routers along a path.

At some point the addition of a new package of information to the probe would make the resulting packet exceed a size limit set in the probe packet or some local implementation limitation.

In that case, rather than adding an information package, the router that detects this condition sets the WouldExceedSizeLimit flag in the probe packet and then sends the probe packet back to an address indicated in the probe.  (That address is presumably that of the application that is performing the FPCP query.)  Once the probe is sent back to the querying application the router performs no further processing of the probe.

When the router is generating multiple packages, this size test is performed for each package rather than for all the packages together.  Thus it is possible that the first package(s) generated may fit while the subsequent package(s) may not.  The error packat that is returned to the querying application will thus contain all the packages that could fit.

Upon receipt of the returned probe packet that application has the option of stopping or of starting a new FPCP query starting at the router that returned the probe with the WouldExceedSizeLimit indication.  The querying application is responsible for logically splicing the information obtained from the initial FPCP with that obtained from successor FPCP sessions.  Note: because the probe that triggered the oversize situation contains all the packages that could fit, the querying application should be prepared for the successor FPCP session to generate some packages that duplicate those generated by the last hop of the query that triggered the oversize situation.

Obtaining Information About the Initial link

The Next Hop and Path Fork packages are forward looking - they contain information about how the hypothetical packet will be moved forward towards the destination from the current router.

The Initial Hop package is retrospective - it contains data about how the source host indicated by the hypothetical packet will move the hypothetical packet to the router that has been asked to generate the Initial Hop package.

There is a flag in the Flag field of the FPCP header - Request Initial HopData.

If set, this flag indicates that if if the following conditions are met, the router should attempt to generate an Initial Hop Data package (of the correct IP version) before attempting to generate any other package:

• No packages except the a Query package are in the probe packet.

• The interface indicated by the Start-IP address object in the Query package is both operationally and administratively operational.

• The source IP address of the hypothetical IP header in the Query package is on the directly attached subnet on the interface indicated by the Start-IP address object in the Query package.

Upon successfully generating and appending the Initial Hop Data package, the router SHALL reset the Request Initial HopData flag so that the subsequent routers do not attempt to generate an Initial Hop Data package.

Dealing With Forking Paths

An FPCP probe stops when it hits a router where the path to the destination splits so that there is more than one possible next hop.  However, before stopping, a Path Fork package is generated and added to the probe, which is then sent back to the querying application.

This Path Fork package contains a list of the possible next hops, along with an assessment as to the probability that the hypothetical packet would be sent to each of those potential next hops.  It is up to the querying application to use this information to start a new FPCP query starting with each of those potential next hops (or at least those that have a non-trivial chance of being used) and splicing the results together with the already-accumulated FPCP information to build an overall assessment of the forked path.  How that splicing is done is a matter for the application and is not defined by this specification.

<<**TODO**>> Say how one uses Force Next Hop object to resume the trace at the router where the fork occurred.

Dealing With Non-FPCP Routers.

FPCP is loosely modeled on the multicast traceroute (draft-ietf-idmr-traceroute-ipm-06.txt).  In particular FPCP makes use of a probe packet that is sent from an FPCP application to the first router in a path.  From then on the probe packet is forwarded hop by hop to each successive router.  Each router appends an information segment about itself and, optionally, about the incoming and outgoing interfaces and links used by the probe.  If an error is encountered or if the path forks or the probe grows too large, the FPCP is terminated and a response sent back to FPCP application.  When the probe grew too large, the FPCP application may simply start a continuing FPCP with a fresh (and hence still-small) probe at the point of the problem.  When the path splits, the FPCP application may initiate a new FPCP for each of the forks.

Detecting and Suppressing Probe Packet Loops

When processing a probe packet, a router must scan the list of items in the packet placed there by previous routers.  If one is encountered that has an address of one of the router's interfaces, then there is a routing loop.  The probe packet MUST be marked with the routing-loop detected error code and sent to the querying application's address in the probe packet.  Further processing of the FPCP probe packet by the router then ceases.

However, checking for probe packet loops by the routers is not sufficient.  It is possible for a routing situation to be made invisible because of an intervening break in the FPCP procedure due to a probe packet becoming too large or a route forking.  Thus the querying application MUST take steps to detect loops.

In particular, the querying application MUST NOT send a probe packet to any router that has already been examined by any of the FPCP pieces that are being spliced together.  As a practical matter this means that whenever a querying application is engaged in the task of piecing together multiple FPCP results that it must scan all the results that it has already accumulated to see whether the router to which it is intending on sending the probe packet is to be found in any of the accumulated data.  If so, the querying application MUST declare a routing loop and MUST abort the FPCP procedure.

Measuring A Partial Path

<<**TODO**>>

What Happens When An FPCP Packet Is Lost.

FPCP packets are carried in UDP.  And UDP makes no guarantees of delivery.

If one desires a guaranteed FPCP service, the querying application must maintain lists of unanswered queries and associated timers.  The querying application must decide for itself when a query has gone awry and must start a new query.

The querying application MUST not re-use a query identifier unless the querying application is certain that old probe packets with the query id have gone to the great network bit bucket in the sky.  As a practical matter this means not re-using a query id for at least 256 seconds.

How A Router Processes A Received FPCP Packet ("Elements of Procedure")

<<**TODO**>>

The Querying Application

<<**TODO**>>

Issues

**TODO** Measuring delays in routers, especially in output queues - how is it done?

**TODO** How does router determine queue delay and link delay (and queue loss probability) for IP headers with unusual QoS or options?

Number Assignments

Status Values in FPCP Packet Header

Flag Values in FPCP Packet Header

Package Types

Object Types

Security

Design Documents

Draft document  <<<***Out of Date***>>>

Acknowledgements

This work was originally conceived while reading a paper by Allen Downey.

Substantial and invaluable comments were received from Bruce Mah.

References

Authors

• Karl Auerbach
  karl@cisco.com
  Cisco Systems, Inc.
  San Jose, California   USA