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


                              Connectivity
                 <draft-ietf-ippm-connectivity-01.txt>


1. Status of this Memo

   This document is an Internet  Draft.   Internet  Drafts  are  working
   documents  of  the Internet Engineering Task Force (IETF), its areas,
   and its working groups.  Note that other groups may  also  distribute
   working documents as Internet 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-ippm-
   framework-01.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 1997


 +    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
      metrics are defined for connectivity over an interval of time.
 +    Using  these  metrics,  an  analytic  metric,  called  Type-P1-P2-
      Interval-Temporal-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-Temporal-Connectivity    in   a   variety   of
      settings.
   Careful definition of  Type-P1-P2-Interval-Temporal-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 1997


3.5. Discussion:

   This  metric  is  probably  not  directly  useful,  because   it   is
   instantaneous    and    unidirectional.    For   most   applications,
   bidirectional connectivity 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  transient  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
   difficult  to  measure  in the absence of connectivity in the reverse
   direction.  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 1997


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
   connected  if  at time T address A1 has instantaneous connectivity to
   address  A2,  and  at  time  T+dT  address   A2   has   instantaneous
   connectivity  to  A1,  where  T+dT  is  when  the packet sent from A1
   arrives at A2.  This  definition  is  more  useful  for  measurement,
   because  the  measurement  can  use a reply from A2 to A1 in order to
   assess full connectivity.  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  discussion  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
   interval.}








Mahdavi and Paxson                                              [Page 4]


ID                            Connectivity                 November 1997


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
   interval.}


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
   interval   and   address   A2   has   Type-P-Interval-Unidirectional-
   Connectivity to address A1 during the interval.










Mahdavi and Paxson                                              [Page 5]


ID                            Connectivity                 November 1997


6.5. Discussion:

   This  metric  is  not  quite  what's  needed  for  defining  "useful"
   connectivity - that requires the notion that a packet sent from A1 to
   A2 can elicit a response from A2  that  will  reach  A1.   With  this
   definition,  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 Temporal Connectivity


7.1. Metric Name:

   Type-P1-P2-Interval-Temporal-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
   interval.}


7.3. Metric Units:

   Boolean.


7.4. Definition:

   Address  Src   has   *Type-P1-P2-Interval-Temporal-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 Type-P1 packet sent by Src at time  T1
      to arrive at Dst.







Mahdavi and Paxson                                              [Page 6]


ID                            Connectivity                 November 1997


 +    dT2 is the time taken for a Type-P2 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
   different types of packets for forward and  reverse  traffic,  it  is
   possible  (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-Temporal-Connectivity.   It  is a class rather than a single
   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].
 +    N, the number  of  packets  to  send  as  probes  for  determining
      connectivity.
 +    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].








Mahdavi and Paxson                                              [Page 7]


ID                            Connectivity                 November 1997


 +    At each sending time, transmit from A1  a  well-formed  packet  of
      type P1 to A2.
 +    Inspect  incoming  network  traffic  to  A1  to  determine  if   a
      successful  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
   temporal  connectivity  at  every  instant in time between [T, T+dT].
   The value of N  trades  off  measurement  precision  against  network
   measurement 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.  Network traffic incoming to
   A1 is interpreted as follows:
 +    A SYN-ack packet from A2 to A1  with  the  proper  acknowledgement
      fields and ports indicates temporal connectivity.  The measurement
      terminates immediately with a  value  of  "true".   {Comment:  the
      connection  now  established  between A1 and A2 should be properly
      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  indicates
      temporal  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   temporal
      connectivity  between the addresses (and again a *lack* of service
      connectivity    for    TCP-port-N1-port-N2).     {Comment:     TCP
      implementations   generally   do  not  need  to  send  ICMP  port-
      unreachable messages because a  separate  mechanism  is  available
      (sending a RST).  However, RFC 1122 states that a TCP receiving an
      ICMP port-unreachable MUST treat it the  same  as  the  equivalent
      transport-level mechanism (for TCP, a RST).}








Mahdavi and Paxson                                              [Page 8]


ID                            Connectivity                 November 1997


 +    An  ICMP  host-unreachable  or  network-unreachable  to  A1   (not
      necessarily from A2) with an enclosed IP header matching that sent
      from A1 to A2 *suggests* a lack of temporal connectivity.   If  by
      time  T+dT no evidence of temporal 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.}


8. Security Considerations

   This memo raises no security issues.


9. References

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

   R. Braden, "Requirements for Internet hosts - communication  layers",
   RFC 1122, October 1989.

   V. Paxson, G. Almes, J. Mahdavi, and M.  Mathis,  Paxson,  "Framework
   for   IP   Performance  Metrics",  Internet  Draft  <draft-ietf-ippm-
   framework-01.txt>, November 1996.

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




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]