Network Working Group        J. Mahdavi, Pittsburgh Supercomputer Center
Internet Draft          V. Paxson, Lawrence Berkeley National Laboratory
Expiration Date: May 1997                                  November 1996


                              Connectivity
               <draft-ietf-bmwg-ippm-connect-00.txt>


1. Status of this Memo

   This document is an Internet Draft.  Internet Drafts are working doc-
   uments  of the Internet Engineering Task Force (IETF), its areas, and
   its working groups.  Note that other groups may also distribute work-
   ing documents as Internet Drafts.

   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''.

   To learn the current status of any Internet Draft, please  check  the
   ``1id-abstracts.txt'' listing contained in the Internet Drafts shadow
   directories  on  ftp.is.co.za   (Africa),   nic.nordu.net   (Europe),
   munnari.oz.au  (Pacific  Rim),  ds.internic.net  (US  East Coast), or
   ftp.isi.edu (US West Coast).

   This memo provides information for the Internet community.  This memo
   does  not  specify an Internet standard of any kind.  Distribution of
   this memo is unlimited.


2. Introduction

   Connectivity is the basic stuff from  which  the  Internet  is  made.
   Therefore,  metrics determining whether pairs of hosts (IP addresses)
   can reach each other must form the base of a measurement  suite.   We
   define  several  such metrics, some of which serve mainly as building
   blocks for the others.

   This memo defines a series of metrics for connectivity between a pair
   of  Internet hosts.  It builds on notions introduced and discussed in
   the revised IPPM Framework document (currently <draft-ietf-bmwg-ippm-
   framework-00.txt>);  the  reader  is assumed to be familiar with that
   document.

   The structure of the memo is as follows:




Mahdavi and Paxson                                              [Page 1]


ID                            Connectivity                 November 1996


 +    An analytic  metric,  called  Type-P-Instantaneous-Unidirectional-
      Connectivity, will be introduced to define one-way connectivity at
      one moment in time.
 +    Using  this  metric,  another  analytic  metric,  called   Type-P-
      Instantaneous-Bidirectional-Connectivity,  will  be  introduced to
      define two-way connectivity at one moment in time.
 +    Using these metrics, corresponding one- and two-way analytic  met-
      rics are defined for connectivity over an interval of time.
 +    Using   these   metrics,   an   analytic   metric,   called  Type-
      P1-P2-Interval-Causal-Connectivity, will be introduced to define a
      useful  notion  of  two-way connectivity between two hosts over an
      interval of time.
 +    Methodologies are then  presented  and  discussed  for  estimating
      Type-P1-P2-Interval-Causal-Connectivity  in a variety of settings.
   Careful definition of Type-P1-P2-Interval-Causal-Connectivity and the
   discussion  of the metric and the methodologies for estimating it are
   the two chief contributions of the memo.


3. Instantaneous One-way Connectivity


3.1. Metric Name:

   Type-P-Instantaneous-Unidirectional-Connectivity


3.2. Metric Parameters:
 +    Src, the IP address of a host
 +    Dst, the IP address of a host
 +    T, a time


3.3. Metric Units:

   Boolean.


3.4. Definition:

   Src has *Type-P-Instantaneous-Unidirectional-Connectivity* to Dst  at
   time  T if a type-P packet transmitted from Src to Dst at time T will
   arrive at Dst.








Mahdavi and Paxson                                              [Page 2]


ID                            Connectivity                 November 1996


3.5. Discussion:

   This metric is probably not directly useful, because it is  instanta-
   neous  and unidirectional.  For most applications, bidirectional con-
   nectivity is considerably more germane (e.g.,  any  TCP  connection).
   Most   applications  also  require  connectivity  over  an  interval.
   Finally, one might not have instantaneous connectivity due to a tran-
   sient  event  such  as  a  full  queue at a router, even if at nearby
   instants in time  one  does  have  connectivity.   These  points  are
   addressed below, with this metric serving as a building block.

   Note  also  that  we  have  not  explicitly defined *when* the packet
   arrives at Dst.  The TTL field in IP packets is  meant  to  limit  IP
   packet lifetimes to 255 seconds (RFC 791).  In practice the TTL field
   can be strictly a hop count (RFC 1812), with most Internet hops being
   much shorter than one second.  This means that most packets will have
   nowhere near the 255 second lifetime.  In principle, however,  it  is
   also  possible  that  packets  might survive longer than 255 seconds.
   Consideration of packet lifetimes  must  be  taken  into  account  in
   attempts to measure the value of this metric.

   Finally,  one might assume that unidirectional connectivity is diffi-
   cult to measure in the absence of connectivity in the reverse  direc-
   tion.   Consider,  however,  the  possibility that a process on Dst's
   host notes when it receives packets from Src and  reports  this  fact
   either using an external channel, or later in time when Dst does have
   connectivity to Src.  Such a methodology could reliably  measure  the
   unidirectional connectivity defined in this metric.


4. Instantaneous Two-way Connectivity


4.1. Metric Name:

   Type-P-Instantaneous-Bidirectional-Connectivity


4.2. Metric Parameters:
 +    A1, the IP address of a host
 +    A2, the IP address of a host
 +    T, a time









Mahdavi and Paxson                                              [Page 3]


ID                            Connectivity                 November 1996


4.3. Metric Units:

   Boolean.


4.4. Definition:

   Addresses   A1   and   A2  have  *Type-P-Instantaneous-Bidirectional-
   Connectivity* at time  T  if  address  A1  has  Type-P-Instantaneous-
   Unidirectional-Connectivity  to address A2 and address A2 has Type-P-
   Instantaneous-Unidirectional-Connectivity to address A1.


4.5. Discussion:

   An alternative definition would be that at A1 and A2 are  fully  con-
   nected  if  at  time  T  address A1 has instantaneous connectivity to
   address A2, and at time T+dT address A2 has instantaneous  connectiv-
   ity  to A1, where T+dT is when the packet sent from A1 arrives at A2.
   This definition is more useful for measurement, because the  measure-
   ment can use a reply from A2 to A1 in order to assess full connectiv-
   ity.  It is a more complex definition, however, because it breaks the
   symmetry  between A1 and A2, and requires a notion of quantifying how
   long a particular packet from A1 takes to reach A2.  We postpone dis-
   cussion  of  this  distinction  until  the  development  of interval-
   connectivity metrics below.


5. One-way Connectivity


5.1. Metric Name:

   Type-P-Interval-Unidirectional-Connectivity


5.2. Metric Parameters:
 +    Src, the IP address of a host
 +    Dst, the IP address of a host
 +    T, a time
 +    dT, a duration
   {Comment: Thus, the closed interval [T, T+dT] denotes a  time  inter-
   val.}








Mahdavi and Paxson                                              [Page 4]


ID                            Connectivity                 November 1996


5.3. Metric Units:

   Boolean.


5.4. Definition:

   Address   Src  has  *Type-P-Interval-Unidirectional-Connectivity*  to
   address Dst during the interval [T, T+dT] if for some T'  within  [T,
   T+dT] it has Type-P-instantaneous-connectivity to Dst.


6. Two-way Connectivity


6.1. Metric Name:

   Type-P-Interval-Bidirectional-Connectivity


6.2. Metric Parameters:
 +    A1, the IP address of a host
 +    A2, the IP address of a host
 +    T, a time
 +    dT, a duration
   {Comment:  Thus,  the closed interval [T, T+dT] denotes a time inter-
   val.}


6.3. Metric Units:

   Boolean.


6.4. Definition:

   Addresses A1 and A2 have *Type-P-Interval-Bidirectional-Connectivity*
   between  them during the interval [T, T+dT] if address A1 has Type-P-
   Interval-Unidirectional-Connectivity to address A2 during the  inter-
   val and address A2 has Type-P-Interval-Unidirectional-Connectivity to
   address A1 during the interval.










Mahdavi and Paxson                                              [Page 5]


ID                            Connectivity                 November 1996


6.5. Discussion:

   This metric is not quite what's needed for defining "useful"  connec-
   tivity  -  that  requires the notion that a packet sent from A1 to A2
   can elicit a response from A2 that will reach A1.  With this  defini-
   tion, it could be that A1 and A2 have full-connectivity but only, for
   example, at at time T1 early enough in the interval [T, T+dT] that A1
   and  A2  cannot  reply to packets sent by the other.  This deficiency
   motivates the next metric.


7. Two-way Causal Connectivity


7.1. Metric Name:

   Type-P1-P2-Interval-Causal-Connectivity


7.2. Metric Parameters:
 +    Src, the IP address of a host
 +    Dst, the IP address of a host
 +    T, a time
 +    dT, a duration
   {Comment: Thus, the closed interval [T, T+dT] denotes a  time  inter-
   val.}


7.3. Metric Units:

   Boolean.


7.4. Definition:

   Address  Src has *Type-P1-P2-Interval-Causal-Connectivity* to address
   Dst during the interval [T, T+dT] if there exist times T1 and T2, and
   time intervals dT1 and dT2, such that:
 +    T1, T1+dT1, T2, T2+dT2 are all in [T, T+dT].
 +    T1+dT1 <= T2.
 +    At time T1, Src has Type-P1 instantanous connectivity to Dst.
 +    At time T2, Dst has Type-P2 instantanous connectivity to Src.
 +    dT1  is  the  time  taken  for  a packet sent by Src at time T1 to
      arrive at Dst.







Mahdavi and Paxson                                              [Page 6]


ID                            Connectivity                 November 1996


 +    dT2 is the time taken for a packet sent  by  Dst  at  time  T2  to
      arrive at Src.


7.5. Discussion:

   This metric defines "useful" connectivity -- Src can send a packet to
   Dst that elicits a response.  Because many applications utilize  dif-
   ferent types of packets for forward and reverse traffic, it is possi-
   ble (and likely) that the desired responses to a Type-P1 packet  will
   be  of  a different type Type-P2.  Therefore, in this metric we allow
   for different types of packets in the forward and reverse directions.


7.6. Methodologies:

   Here  we  sketch  a  class  of  methodologies  for  estimating  Type-
   P1-P2-Interval-Causal-Connectivity.  It is a class rather than a sin-
   gle  methodology  because the particulars will depend on the types P1
   and P2.


7.6.1. Inputs:
 +    Types P1 and P2, addresses A1 and A2, interval [T, T+dT], and
 +    N, the number of packets to send as probes for determining connec-
      tivity.
 +    W,  the  "waiting time", which bounds for how long it is useful to
      wait for a reply to a packet.
   Required: W <= 255, dT > W.


7.6.2. Recommended values:

   dT = 60 seconds.
   W = 10 seconds.
   N = 20 packets.


7.6.3. Algorithm:

 +    Compute N *sending-times* that are randomly, uniformly distributed
      over [T, T+dT-W].
 +    At  each  sending  time,  transmit from A1 a well-formed packet of
      type P1 to A2.







Mahdavi and Paxson                                              [Page 7]


ID                            Connectivity                 November 1996


 +    Inspect incoming network traffic to A1 to determine if a  success-
      ful reply is received.   The particulars of doing so are dependent
      on types P1 & P2, discussed  below.   If  a  successful  reply  is
      received, the value of the measurement is "true".
 +    If  no  successful replies are received by time T+dT, the value of
      the measurement is "false".


7.6.4. Discussion:

   The algorithm is inexact because  it  does  not  (and  cannot)  probe
   causal  connectivity at every instant in time between [T, T+dT].  The
   value of N trades off measurement precision against network  measure-
   ment  load.   The  state-of-the-art in Internet research does not yet
   offer solid guidance for picking N.  The values given above are  just
   guidelines.


7.6.5. Specific methodology for TCP:

   A  TCP-port-N1-port-N2  methodology sends TCP SYN packets with source
   port N1 and dest port N2 at address A2.  Incoming network traffic  is
   interpreted as follows:
 +    A  SYN-ack  packet  from  A2 to A1 with the proper acknowledgement
      fields and ports on A1 indicates causal  connectivity.   The  mea-
      surement terminates immediately with a value of "true".  {Comment:
      the connection now established between A1 and A2 should  be  prop-
      erly  torn  down using the usual FIN handshake (not by using a RST
      packet, as these are not transmitted reliably).}
 +    A RST packet from A2 to A1 with the proper ports on  A1  indicates
      causal connectivity between the addresses (and a *lack* of service
      connectivity for TCP-port-N1-port-N2  -  something  that  probably
      should be addressed with another metric).
 +    An ICMP port-unreachable from A2 to A1 indicates causal connectiv-
      ity between the addresses (and again a *lack* of  service  connec-
      tivity  for  TCP-port-N1-port-N2).  {Comment: Are there TCP imple-
      mentations that generate ICMP's instead of RST's?   Do  the  RFC's
      allow  this?   Certainly  they  do  for  UDP,  so the notion makes
      sense.}
 +    An ICMP host-unreachable or network-unreachable to A1 (not  neces-
      sarily from A2) with an enclosed IP header matching that sent from
      A1 to A2 *suggests* a lack of causal  connectivity.   If  by  time
      T+dT  no  evidence  of causal connectivity has been gathered, then
      the receipt of the ICMP can be used as additional  information  to
      the measurement value of "false".

   {Comment: Similar methodologies are needed for ICMP Echo, UDP, etc.}




Mahdavi and Paxson                                              [Page 8]


ID                            Connectivity                 November 1996


8. Security Considerations

   This memo raises no security issues.


9. References

   G.  Almes, W. Cerveny, P. Krishnaswamy, J. Mahdavi, M. Mathis, and V.
   Paxson, "Framework for IP Provider Metrics", Internet  Draft  <draft-
   ietf-bmwg-ippm-framework-00.txt>, November 1996.

   J. Postel, "Internet Protocol", RFC 791, September 1981.

   F.  Baker,  "Requirements  for  IP Version 4 Routers", RFC 1812, June
   1995.




10. Authors' Addresses

   Jamshid Mahdavi <mahdavi@psc.edu>
   Pittsburgh Supercomputing Center
   4400 5th Avenue
   Pittsburgh, PA  15213
   USA

   Vern Paxson <vern@ee.lbl.gov>
   MS 50B/2239
   Lawrence Berkeley National Laboratory
   University of California
   Berkeley, CA  94720
   USA
   Phone: +1 510/486-7504

















Mahdavi and Paxson                                              [Page 9]