home *** CD-ROM | disk | FTP | other *** search
/ Unix System Administration Handbook 1997 October / usah_oct97.iso / rfc / 1400s / rfc1433.txt < prev    next >
Text File  |  1993-03-03  |  41KB  |  1,011 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                        J. Garrett
  8. Request for Comments: 1433                       AT&T Bell Laboratories
  9.                                                                J. Hagan
  10.                                              University of Pennsylvania
  11.                                                                 J. Wong
  12.                                                  AT&T Bell Laboratories
  13.                                                              March 1993
  14.  
  15.  
  16.                               Directed ARP
  17.  
  18. Status of this Memo
  19.  
  20.    This memo defines an Experimental Protocol for the Internet
  21.    community.  Discussion and suggestions for improvement are requested.
  22.    Please refer to the current edition of the "IAB Official Protocol
  23.    Standards" for the standardization state and status of this protocol.
  24.    Distribution of this memo is unlimited.
  25.  
  26. Abstract
  27.  
  28.    A router with an interface to two IP networks via the same link level
  29.    interface could observe that the two IP networks share the same link
  30.    level network, and could advertise that information to hosts (via
  31.    ICMP Redirects) and routers (via dynamic routing protocols).
  32.    However, a host or router on only one of the IP networks could not
  33.    use that information to communicate directly with hosts and routers
  34.    on the other IP network unless it could resolve IP addresses on the
  35.    "foreign" IP network to their corresponding link level addresses.
  36.    Directed ARP is a dynamic address resolution procedure that enables
  37.    hosts and routers to resolve advertised potential next-hop IP
  38.    addresses on foreign IP networks to their associated link level
  39.    addresses.
  40.  
  41. Acknowledgments
  42.  
  43.    The authors are indebted to Joel Halpern of Network Systems
  44.    Corporation and David O'Leary who provided valuable comments and
  45.    insight to the authors, as well as ongoing moral support as the
  46.    presentation of this material evolved through many drafts.  Members
  47.    of the IPLPDN working group also provided valuable comments during
  48.    presentations and through the IPLPDN mailing list.  Chuck Hedrick of
  49.    Rutgers University, Paul Tsuchiya of Bell Communications Research,
  50.    and Doris Tillman of AT&T Bell Laboratories provided early insight as
  51.    well as comments on early drafts.
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58. Garrett, Hagan & Wong                                           [Page 1]
  59.  
  60. RFC 1433                      Directed ARP                    March 1993
  61.  
  62.  
  63. 1.  Terminology
  64.  
  65.    A "link level network" is the upper layer of what is sometimes
  66.    referred to (e.g., OSI parlance) as the "subnetwork", i.e., the
  67.    layers below IP.  The term "link level" is used to avoid potential
  68.    confusion with the term "IP sub-network", and to identify addresses
  69.    (i.e., "link level address") associated with the network used to
  70.    transport IP datagrams.
  71.  
  72.    From the perspective of a host or router, an IP network is "foreign"
  73.    if the host or router does not have an address on the IP network.
  74.  
  75. 2.  Introduction
  76.  
  77.    Multiple IP networks may be administered on the same link level
  78.    network (e.g., on a large public data network).  A router with a
  79.    single interface on two IP networks could use existing routing update
  80.    procedures to advertise that the two IP networks shared the same link
  81.    level network.  Cost/performance benefits could be achieved if hosts
  82.    and routers that were not on the same IP network could use that
  83.    advertised information, and exchange packets directly, rather than
  84.    through the dual addressed router.  But a host or router can not send
  85.    packets directly to an IP address without first resolving the IP
  86.    address to its link level address.
  87.  
  88.    IP address resolution procedures are established independently for
  89.    each IP network.  For example, on an SMDS network [1], address
  90.    resolution may be achieved using the Address Resolution Protocol
  91.    (ARP) [2], with a separate SMDS ARP Request Address (e.g., an SMDS
  92.    Multicast Group Address) associated with each IP network.  A host or
  93.    router that was not configured with the appropriate ARP Request
  94.    Address would have no way to learn the ARP Request Address associated
  95.    with an IP network, and would not send an ARP Request to the
  96.    appropriate ARP Request Address.  On an Ethernet network a host or
  97.    router might guess that an IP address could be resolved by sending an
  98.    ARP Request to the broadcast address.  But if the IP network used a
  99.    different address resolution procedure (e.g., administered address
  100.    resolution tables), the ARP Request might go unanswered.
  101.  
  102.    Directed ARP is a procedure that enables a router advertising that an
  103.    IP address is on a shared link level network to also aid in resolving
  104.    the IP address to its associated link level address.  By removing
  105.    address resolution constraints, Directed ARP enables dynamic routing
  106.    protocols such as BGP [3] and OSPF [4] to advertise and use routing
  107.    information that leads to next-hop addresses on "foreign" IP
  108.    networks.  In addition, Directed ARP enables routers to advertise
  109.    (via ICMP Redirects) next-hop addresses that are "foreign" to hosts,
  110.    since the hosts can use Directed ARP to resolve the "foreign" next-
  111.  
  112.  
  113.  
  114. Garrett, Hagan & Wong                                           [Page 2]
  115.  
  116. RFC 1433                      Directed ARP                    March 1993
  117.  
  118.  
  119.    hop addresses.
  120.  
  121. 3.  Directed ARP
  122.  
  123.    Directed ARP uses the normal ARP packet format, and is consistent
  124.    with ARP procedures, as defined in [1] and [2], and with routers and
  125.    hosts that implement those procedures.
  126.  
  127. 3.1  ARP Helper Address
  128.  
  129.    Hosts and routers maintain routing information, logically organized
  130.    as a routing table.  Each routing table entry associates one or more
  131.    destination IP addresses with a next-hop IP address and a physical
  132.    interface used to forward a packet to the next-hop IP address.  If
  133.    the destination IP address is local (i.e., can be reached without the
  134.    aid of a router), the next-hop IP address is NULL (or a logical
  135.    equivalent, such as the IP address of the associated physical
  136.    interface).  Otherwise, the next-hop IP address is the address of a
  137.    next-hop router.
  138.  
  139.    A host or router that implements Directed ARP procedures associates
  140.    an ARP Helper Address with each routing table entry.  If the host or
  141.    router has been configured to resolve the next-hop IP address to its
  142.    associated link level address (or to resolve the destination IP
  143.    address, if the next-hop IP address is NULL), the associated ARP
  144.    Helper Address is NULL.  Otherwise, the ARP Helper Address is the IP
  145.    address of the router that provided the routing information
  146.    indicating that the next-hop address was on the same link level
  147.    network as the associated physical interface.  Section 4 provides
  148.    detailed examples of the determination of ARP Helper Addresses by
  149.    dynamic routing procedures.
  150.  
  151. 3.2  Address Resolution Procedures
  152.  
  153.    To forward an IP packet, a host or router searches its routing table
  154.    for an entry that is the best match based on the destination IP
  155.    address and perhaps other factors (e.g., Type of Service).  The
  156.    selected routing table entry includes the IP address of a next-hop
  157.    router (which may be NULL), the physical interface through which the
  158.    IP packet should be forwarded, an ARP Helper Address (which may be
  159.    NULL), and other information.  The routing function passes the next-
  160.    hop IP address, the physical interface, and the ARP Helper Address to
  161.    the address resolution function.  The address resolution function
  162.    must then resolve the next-hop IP address (or destination IP address
  163.    if the next-hop IP address is NULL) to its associated link level
  164.    address.  The IP packet, the link level address to which the packet
  165.    should be forwarded, and the interface through which the packet
  166.    should be forwarded are then passed to the link level driver
  167.  
  168.  
  169.  
  170. Garrett, Hagan & Wong                                           [Page 3]
  171.  
  172. RFC 1433                      Directed ARP                    March 1993
  173.  
  174.  
  175.    associated with the physical interface.  The link level driver
  176.    encapsulates the IP packet in one or more link level frames (i.e.,
  177.    may do fragmentation) addressed to the associated link level address,
  178.    and forwards the frame(s) through the appropriate physical interface.
  179.    The details of the functions performed are described via C pseudo-
  180.    code below.
  181.  
  182.    The procedures are organized as two functions, Route() and Resolve(),
  183.    corresponding to routing and address resolution.  In addition, the
  184.    following low level functions are also used:
  185.  
  186.      Get_Route(IP_Add,Other) returns a pointer to the routing table
  187.       entry with the destination field that best matches IP_Add.  If no
  188.       matching entry is found, NULL is returned.  Other information such
  189.       as Type of Service may be considered in selecting the best route.
  190.  
  191.      Forward(Packet,Link_Level_Add,Phys_Int) fragments Packet (if
  192.       needed), and encapsulates Packet in one or more Link Level Frames
  193.       addressed to Link_Level_Add, and forwards the frame(s) through
  194.       interface, Phys_Int.
  195.  
  196.      Look_Up_Add_Res_Table(IP_Add,Phys_Int) returns a pointer to the
  197.       link level address associated with IP_Add in the address
  198.       resolution table associated with interface, Phys_Int.  If IP_Add
  199.       is not found in the address resolution table, NULL is returned.
  200.  
  201.      Local_Add_Res(IP_Add,Phys_Int) returns a pointer to the Link Level
  202.       address associated with IP_Add, using address resolution
  203.       procedures associated with address, IP_Add, and interface,
  204.       Phys_Int.  If address resolution is unsuccessful, NULL is
  205.       returned.  Note that different address resolution procedures may
  206.       be used for different IP networks.
  207.  
  208.      Receive_ARP_Response(IP_Add,Phys_Int) returns a pointer to an ARP
  209.       Response received through interface, Phys_Int, that resolves
  210.       IP_Add.  If no ARP response is received, NULL is returned.
  211.  
  212.      Dest_IP_Add(IP_Packet) returns the IP destination address from
  213.       IP_Packet.
  214.  
  215.      Next_Hop(Entry) returns the IP address in the next-hop field of
  216.       (routing table) Entry.
  217.  
  218.      Interface(Entry) returns the physical interface field of (routing
  219.       table) Entry.
  220.  
  221.      ARP_Helper_Add(Entry) returns the IP address in the ARP Helper
  222.       Address field of (routing table) Entry.
  223.  
  224.  
  225.  
  226. Garrett, Hagan & Wong                                           [Page 4]
  227.  
  228. RFC 1433                      Directed ARP                    March 1993
  229.  
  230.  
  231.      ARP_Request(IP_Add) returns an ARP Request packet with IP_Add as
  232.       the Target IP address.
  233.  
  234.      Source_Link_Level(ARP_Response) returns the link level address of
  235.       the sender of ARP_Response.
  236.  
  237.  
  238.  
  239.  
  240.    ROUTE(IP_Packet)
  241.    {
  242.    Entry = Get_Route(Dest_IP_Add(IP_Packet),Other(IP_Packet));
  243.    If (Entry == NULL)  /* No matching entry in routing table */
  244.      Return;  /*  Discard IP_Packet */
  245.    else
  246.      {  /* Resolve next-hop IP address to link level address */
  247.      If (Next_Hop(Entry) != NULL) /* Route packet via next-hop router */
  248.        Next_IP = Next_Hop(Entry);
  249.      else  /* Destination is local */
  250.        Next_IP = Dest_IP_Add(IP_Packet);
  251.      L_L_Add = Resolve(Next_IP,Interface(Entry),ARP_Helper_Add(Entry));
  252.      If (L_L_Add != NULL)
  253.        Forward(IP_Packet,L_L_Add,Interface(Entry));
  254.      else  /* Couldn't resolve next-hop IP address */
  255.        Return;  /* Discard IP_Packet */
  256.      Return;
  257.      }
  258.    }
  259.  
  260.    Figure 1:  C Pseudo-Code for the Routing function.
  261.  
  262.  
  263.  
  264.  
  265.  
  266.  
  267.  
  268.  
  269.  
  270.  
  271.  
  272.  
  273.  
  274.  
  275.  
  276.  
  277.  
  278.  
  279.  
  280.  
  281.  
  282. Garrett, Hagan & Wong                                           [Page 5]
  283.  
  284. RFC 1433                      Directed ARP                    March 1993
  285.  
  286.  
  287.    Resolve(IP_Add,Interface,ARP_Help_Add)
  288.    {
  289.    If ((L_L_Add = Look_Up_Add_Res_Table(IP_Add,Interface)) != NULL)
  290.      {   /* Found it in Address Resolution Table */
  291.      Return L_L_Add;
  292.      }
  293.    else
  294.      {
  295.      If (ARP_Help_Add == NULL)
  296.        {  /* Do local Address Resolution Procedure */
  297.        Return Local_Add_Res(IP_Add,Interface);
  298.        }
  299.      else  /* ARP_Help_Add != NULL */
  300.        {
  301.        L_L_ARP_Help_Add = Look_Up_Add_Res_Table(ARP_Help_Add,Interface);
  302.        If (L_L_ARP_Help_Add == NULL)
  303.                               /* Not in Address Resolution Table */
  304.          L_L_ARP_Help_Add = Local_Add_Res(ARP_Help_Add,Interface);
  305.        If (L_L_ARP_Help_Add == NULL)  /* Can't Resolve ARP Helper Add */
  306.          Return NULL;  /*  Address Resolution Failed */
  307.        else
  308.          {  /* ARP for IP_Add */
  309.          Forward(ARP_Request(IP_Add),L_L_ARP_Help_Add,Interface);
  310.          ARP_Resp = Receive_ARP_Response(IP_Add,Interface);
  311.          If (ARP_Resp == NULL) /* No ARP Response (after persistence) */
  312.            Return NULL;  /* Address Resolution Failed */
  313.          else
  314.            Return Source_Link_Level(ARP_Resp);
  315.            }
  316.          }
  317.        }
  318.      }
  319.    }
  320.  
  321.    Figure 2:  C Pseudo-Code for Address Resolution function.
  322.  
  323.  
  324.  
  325. 3.3  Forwarding ARP Requests
  326.  
  327.    A host that implements Directed ARP procedures uses normal procedures
  328.    to process received ARP Requests.  That is, if the Target IP address
  329.    is the host's address, the host uses normal procedures to respond to
  330.    the ARP Request.  If the Target IP address is not the host's address,
  331.    the host silently discards the ARP Request.
  332.  
  333.    If the Target IP address of an ARP Request received by a router is
  334.    the router's address, the router uses normal procedures to respond to
  335.  
  336.  
  337.  
  338. Garrett, Hagan & Wong                                           [Page 6]
  339.  
  340. RFC 1433                      Directed ARP                    March 1993
  341.  
  342.  
  343.    the ARP Request.  But if the Target IP address is not the router's
  344.    address, the router may forward the ARP Request back through the same
  345.    interface it was received from, addressed to a Link Level Address
  346.    that corresponds to an ARP Helper Address in the router's routing
  347.    table.  The procedures used to process an ARP Request are described
  348.    via C pseudo-code below.  The function Receive() describes procedures
  349.    followed by hosts and routers, and the function Direct() describes
  350.    additional procedures followed by routers.  In addition, the
  351.    following low level functions are also used:
  352.  
  353.      Is_Local_IP_Add(IP_Add,Phys_Int) returns TRUE if Phys_Int has been
  354.       assigned IP address, IP_Add.  Otherwise, returns FALSE.
  355.  
  356.      Do_ARP_Processing(ARP_Request,Interface) processes ARP_Request
  357.       using ARP procedures described in [2].
  358.  
  359.      I_Am_Router returns TRUE if device is a router and False if device
  360.       is a host.
  361.  
  362.      Target_IP(ARP_Request) returns the Target IP address from
  363.       ARP_Request.
  364.  
  365.      Filter(ARP_Request,Phys_Int) returns TRUE if ARP_Request passes
  366.       filtering constraints, and FALSE if filtering constraints are not
  367.       passed.  See section 3.4.
  368.  
  369.      Forward(Packet,Link_Level_Add,Phys_Int) fragments Packet (if
  370.       needed), and encapsulates Packet in one or more Link Level Frames
  371.       addressed to Link_Level_Add, and forwards the frame(s) through
  372.       interface, Phys_Int.
  373.  
  374.      Look_Up_Next_Hop_Route_Table(IP_Add) returns a pointer to the
  375.       routing table entry with the next-hop field that matches IP_Add.
  376.       If no matching entry is found, NULL is returned.
  377.  
  378.      Look_Up_Dest_Route_Table(IP_Add) returns a pointer to the routing
  379.       table entry with the destination field that best matches IP_Add.
  380.       If no matching entry is found, NULL is returned.
  381.  
  382.      Link_Level_ARP_Req_Add(IP_Add,Phys_Int) returns the link level
  383.       address to which an ARP Request to resolve IP_Add should be
  384.       forwarded.  If ARP is not used to perform local address resolution
  385.       of IP_Add, NULL is returned.
  386.  
  387.      Local_Add_Res(IP_Add,Phys_Int) returns a pointer to the Link Level
  388.       address associated with IP_Add, using address resolution
  389.       procedures associated with address, IP_Add, and interface,
  390.       Phys_Int.  If address resolution is unsuccessful, NULL is
  391.  
  392.  
  393.  
  394. Garrett, Hagan & Wong                                           [Page 7]
  395.  
  396. RFC 1433                      Directed ARP                    March 1993
  397.  
  398.  
  399.       returned.  Note that different address resolution procedures may
  400.       be used for different IP networks.
  401.  
  402.      Next_Hop(Entry) returns the IP address in the next-hop field of
  403.       (routing table) Entry.
  404.  
  405.      Interface(Entry) returns the physical interface field of (routing
  406.       table) Entry.
  407.  
  408.      ARP_Helper_Add(Entry) returns the IP address in the ARP Helper
  409.       Address field of (routing table) Entry.
  410.  
  411.      Source_Link_Level(ARP_Request) returns the link level address of
  412.       the sender of ARP_Request.
  413.  
  414.  
  415.  
  416.  
  417.  
  418.    Receive(ARP_Request,Interface)
  419.    {
  420.    If (Is_Local_IP_Add(Target_IP(ARP_Request),Interface))
  421.      Do_ARP_Processing(ARP_Request,Interface);
  422.    else  /*  Not my IP Address  */
  423.      If (I_Am_Router)  /*  Hosts don't Direct ARP Requests  */
  424.        If (Filter(ARP_Request,Interface))  /*  Passes Filter Test  */
  425.                                            /*  See Section 3.4  */
  426.          Direct(ARP_Request,Interface);  /*  Directed ARP Procedures  */
  427.    Return;
  428.    }
  429.  
  430.    Figure 3:  C Pseudo-Code for Receiving ARP Requests.
  431.  
  432.  
  433.  
  434.  
  435.  
  436.  
  437.  
  438.  
  439.  
  440.  
  441.  
  442.  
  443.  
  444.  
  445.  
  446.  
  447.  
  448.  
  449.  
  450. Garrett, Hagan & Wong                                           [Page 8]
  451.  
  452. RFC 1433                      Directed ARP                    March 1993
  453.  
  454.  
  455.    Direct(ARP_Request,Phys_Int)
  456.    {
  457.    Entry = Look_Up_Next_Hop_Route_Table(Target_IP(ARP_Request));
  458.    If (Entry == NULL)  /* Target_IP Address is not a next-hop */
  459.      {                 /*  in Routing Table */
  460.      Entry = Look_Up_Dest_Route_Table(Target_IP(ARP_Request));
  461.        If (Entry == NULL)  /* Not a destination either */
  462.          Return;  /* Discard ARP Request */
  463.        else
  464.          If (Next_Hop(Entry) != NULL) /* Not a next-hop and Not local */
  465.            Return;  /* Discard ARP Request */
  466.      }
  467.    If (Interface(Entry) != Phys_Int)
  468.                             /* Must be same physical interface */
  469.      Return;  /* Discard ARP Request */
  470.    If (ARP_Helper_Add(Entry) != NULL)
  471.      {
  472.      L_L_ARP_Helper_Add = Resolve(ARP_Helper_Add(Entry),Phys_Int,NULL);
  473.      If (L_L_ARP_Helper_Add != NULL)
  474.        Forward(ARP_Request,L_L_ARP_Helper_Add,Phys_Int);
  475.          /*  Forward ARP_Request to ARP Helper Address  */
  476.      Return;
  477.      }
  478.    else  /*  Do local address resolution.  */
  479.      {
  480.      L_L_ARP_Req_Add =
  481.                 Link_Level_ARP_Req_Add(Target_IP(ARP_Request),Phys_Int);
  482.      If (L_L_ARP_Req_Add != NULL)
  483.        {  /*  Local address resolution procedure is ARP. */
  484.           /*  Forward ARP_Request. */
  485.        Forward(ARP_Request,L_L_ARP_Req_Add,Phys_Int);
  486.        Return;
  487.        }
  488.      else
  489.        {  /*  Local address resolution procedure is not ARP.  */
  490.           /*  Do "published ARP" on behalf of Target IP Address  */
  491.        Target_Link_Level =
  492.                       Local_Add_Res(Target_IP(ARP_Request),Phys_Int);
  493.        If (Target_Link_Level != NULL)  /*  Resolved Address  */
  494.          {
  495.          Forward(ARP_Response,Source_Link_Level(ARP_Request),Phys_Int);
  496.          }
  497.        Return;
  498.        }
  499.      }
  500.    }
  501.  
  502.    Figure 4:  C Pseudo_Code for Directing ARP Requests.
  503.  
  504.  
  505.  
  506. Garrett, Hagan & Wong                                           [Page 9]
  507.  
  508. RFC 1433                      Directed ARP                    March 1993
  509.  
  510.  
  511. 3.4  Filtering Procedures
  512.  
  513.    A router performing Directed ARP procedures must filter the
  514.    propagation of ARP Request packets to constrain the scope of
  515.    potential "ARP floods" caused by misbehaving routers or hosts, and to
  516.    terminate potential ARP loops that may occur during periods of
  517.    routing protocol instability or as a result of inappropriate manual
  518.    configurations.  Specific procedures to filter the propagation of ARP
  519.    Request packets are beyond the scope of this document.  The following
  520.    procedures are suggested as potential implementations that should be
  521.    sufficient.  Other procedures may be better suited to a particular
  522.    implementation.
  523.  
  524.    To control the propagation of an "ARP flood", a router performing
  525.    Directed ARP procedures could limit the number of identical ARP
  526.    Requests (i.e., same Source IP address and same Target IP address)
  527.    that it would forward per small time interval (e.g., no more than one
  528.    ARP Request per second).  This is consistent with the procedure
  529.    suggested in [5] to prevent ARP flooding.
  530.  
  531.    Forwarding of ARP Request packets introduces the possibility of ARP
  532.    loops.  The procedures used to control the scope of potential ARP
  533.    floods may terminate some ARP loops, but additional procedures are
  534.    needed if the time required to traverse a loop is longer than the
  535.    timer used to control ARP floods.  A router could refuse to forward
  536.    more than N identical ARP Requests per T minutes, where N and T are
  537.    administered numbers.  If T and N are chosen so that T/N minutes is
  538.    greater than the maximum time required to traverse a loop, such a
  539.    filter would terminate the loop.  In some cases a host may send more
  540.    than one ARP Request with the same Source IP address,Target IP
  541.    address pair (i.e., N should be greater than 1).  For example, the
  542.    first ARP Request might be lost.  However, once an ARP Response is
  543.    received, a host would normally save the associated information, and
  544.    therefore would not generate an identical ARP Request for a period of
  545.    time on the order of minutes.  Therefore, T may be large enough to
  546.    ensure that T/N is much larger than the time to traverse any loop.
  547.  
  548.    In some implementations the link level destination address of a frame
  549.    used to transport an ARP Request to a router may be available to the
  550.    router's Directed ARP filtering process.  An important class of
  551.    simple ARP loops will be prevented from starting if a router never
  552.    forwards an ARP Request to the same link level address to which the
  553.    received ARP Request was addressed.  Of course, other procedures such
  554.    as the one described in the paragraph above will stop all loops, and
  555.    are needed, even if filters are implemented that prevent some loops
  556.    from starting.
  557.  
  558.  
  559.  
  560.  
  561.  
  562. Garrett, Hagan & Wong                                          [Page 10]
  563.  
  564. RFC 1433                      Directed ARP                    March 1993
  565.  
  566.  
  567.    Host requirements [5] specify that "the packet receive interface
  568.    between the IP layer and the link layer MUST include a flag to
  569.    indicate whether the incoming packet was addressed to a link-level
  570.    broadcast address."  An important class of simple ARP floods can be
  571.    eliminated if routers never forward ARP Requests that were addressed
  572.    to a link-level broadcast address.
  573.  
  574. 4.  Use of Directed ARP by Routing
  575.  
  576.    The exchange and use of routing information is constrained by
  577.    available address resolution procedures.  A host or router can not
  578.    use a next-hop IP address learned via dynamic routing procedures if
  579.    it is unable to resolve the next-hop IP address to the associated
  580.    link level address.  Without compatible dynamic address resolution
  581.    procedures, a router may not advertise a next-hop address that is not
  582.    on the same IP network as the host or router receiving the
  583.    advertisement.  Directed ARP is a procedure that enables a router
  584.    that advertises routing information to make the routing information
  585.    useful by also providing assistance in resolving the associated
  586.    next-hop IP addresses.
  587.  
  588.    The following subsections describe the use of Directed ARP to expand
  589.    the scope of ICMP Redirects [6], distance-vector routing protocols
  590.    (e.g., BGP [3]), and link-state routing protocols (e.g., OSPF [4]).
  591.  
  592. 4.1  ICMP Redirect
  593.  
  594.    If a router forwards a packet to a next-hop address that is on the
  595.    same link level network as the host that originated the packet, the
  596.    router may send an ICMP Redirect to the host.  But a host can not use
  597.    a next-hop address advertised via an ICMP Redirect unless the host
  598.    has a procedure to resolve the advertised next-hop address to its
  599.    associated link level address.  Directed ARP is a procedure that a
  600.    host could use to resolve an advertised next-hop address, even if the
  601.    host does not have an address on the same IP network as the
  602.    advertised next-hop address.
  603.  
  604.    A host that implements Directed ARP procedures includes an ARP Helper
  605.    Address with each routing table entry.  The ARP Helper Address
  606.    associated with an entry learned via an ICMP Redirect is NULL if the
  607.    associated next-hop address matches a routing table entry with a NULL
  608.    next-hop and a NULL ARP Helper Address (i.e., the host already knows
  609.    how to resolve the next-hop address).  Otherwise, the ARP Helper
  610.    Address is the IP address of the router that sent the ICMP Redirect.
  611.    Note that the router that sent the ICMP Redirect is the current
  612.    next-hop to the advertised destination [5].  Therefore, the host
  613.    should have an entry in its address resolution table for the new ARP
  614.    Helper Address.  If the host is unable to resolve the next-hop IP
  615.  
  616.  
  617.  
  618. Garrett, Hagan & Wong                                          [Page 11]
  619.  
  620. RFC 1433                      Directed ARP                    March 1993
  621.  
  622.  
  623.    address advertised in the ICMP Redirect (e.g., because the associated
  624.    ARP Helper Address is on a foreign IP network; i.e., was learned via
  625.    an old ICMP Redirect, and the address resolution table entry for that
  626.    ARP Helper Address timed out), the host must flush the associated
  627.    routing table entry.  Directed ARP procedures do not recursively use
  628.    Directed ARP to resolve an ARP Helper Address.
  629.  
  630.    A router that performs Directed ARP procedures might advertise a
  631.    foreign next-hop to a host that does not perform Directed ARP.
  632.    Following existing procedures, the host would silently discard the
  633.    ICMP Redirect.  A router that does not implement Directed ARP should
  634.    not advertise a next-hop on a foreign IP network, as specified by
  635.    existing procedures.  If it did, and the ICMP Redirect was received
  636.    by a host that implemented Directed ARP procedures, the host would
  637.    send an ARP Request for the foreign IP address to the advertising
  638.    router, which would silently discard the ARP Request.  When address
  639.    resolution fails, the host should flush the associated entry from its
  640.    routing table.
  641.  
  642.    For various reasons a host may ignore an ICMP Redirect and may
  643.    continue to forward packets to the same router that sent the ICMP
  644.    Redirect.  For example, a host that does not implement Directed ARP
  645.    procedures would silently discard an ICMP Redirect advertising a
  646.    next-hop address on a foreign IP network.  Routers should implement
  647.    constraints to control the number of ICMP Redirects sent to hosts.
  648.    For example, a router might limit the number of repeated ICMP
  649.    Redirects sent to a host to no more than N ICMP Redirects per T
  650.    minutes, where N and T are administered values.
  651.  
  652. 4.2  Distance Vector Routing Protocol
  653.  
  654.    A distance-vector routing protocol provides procedures for a router
  655.    to advertise a destination address (e.g., an IP network), an
  656.    associated next-hop address, and other information (e.g., associated
  657.    metric).  But a router can not use an advertised route unless the
  658.    router has a procedure to resolve the advertised next-hop address to
  659.    its associated link level address.  Directed ARP is a procedure that
  660.    a router could use to resolve an advertised next-hop address, even if
  661.    the router does not have an address on the same IP network as the
  662.    advertised next-hop address.
  663.  
  664.    The following procedures assume a router only accepts routing updates
  665.    if it knows the IP address of the sender of the update, can resolve
  666.    the IP address of the sender to its associated link level address,
  667.    and has an interface on the same link level network as the sender.
  668.  
  669.    A router that implements Directed ARP procedures includes an ARP
  670.    Helper Address with each routing table entry.  The ARP Helper Address
  671.  
  672.  
  673.  
  674. Garrett, Hagan & Wong                                          [Page 12]
  675.  
  676. RFC 1433                      Directed ARP                    March 1993
  677.  
  678.  
  679.    associated with an entry learned via a routing protocol update is
  680.    NULL if the associated next-hop address matches a routing table entry
  681.    with a NULL next-hop and NULL ARP Helper Address (i.e., the router
  682.    already knows how to resolve the next-hop address).  Otherwise, the
  683.    ARP Helper Address is the IP address of the router that sent the
  684.    routing update.
  685.  
  686.    Some distance-vector routing protocols (e.g., BGP [3]) provide syntax
  687.    that would permit a router to advertise an address on a foreign IP
  688.    network as a next-hop.  If a router that implements Directed ARP
  689.    procedures advertises a foreign next-hop IP address to a second
  690.    router that does not implement Directed ARP procedures, the second
  691.    router can not use the advertised foreign next-hop.  Depending on the
  692.    details of the routing protocol implementation, it might be
  693.    appropriate for the first router to also advertise a next-hop that is
  694.    not on a foreign IP network (e.g., itself), perhaps at a higher cost.
  695.    Or, if the routing relationship is an administered connection (e.g.,
  696.    BGP relationships are administered TCP/IP connections), the
  697.    administrative procedure could determine whether foreign next-hop IP
  698.    addresses should be advertised.
  699.  
  700.    A distance-vector routing protocol could advertise that a destination
  701.    is directly reachable by specifying that the router receiving the
  702.    advertisement is, itself, the next-hop to the destination.  In
  703.    addition, the advertised metric for the route might be zero.  If the
  704.    router did not already have a routing table entry that specified the
  705.    advertised destination was local (i.e., NULL next-hop address), the
  706.    router could add the new route with NULL next-hop, and the IP address
  707.    of the router that sent the update as ARP Helper Address.
  708.  
  709. 4.3  Link State Routing Protocol
  710.  
  711.    A link-state routing protocol provides procedures for routers to
  712.    identify links to other entities (e.g., other routers and networks),
  713.    determine the state or cost of those links, reliably distribute
  714.    link-state information to other routers in the routing domain, and
  715.    calculate routes based on link-state information received from other
  716.    routers.  A router with an interface to two (or more) IP networks via
  717.    the same link level interface is connected to those IP networks via a
  718.    single link, as described above.  If a router could advertise that it
  719.    used the same link to connect to two (or more) IP networks, and would
  720.    perform Directed ARP procedures, routers on either of the IP networks
  721.    could forward packets directly to hosts and routers on both IP
  722.    networks, using Directed ARP procedures to resolve addresses on the
  723.    foreign IP network.  With Directed ARP, the cost of the direct path
  724.    to the foreign IP network would be less than the cost of the path
  725.    through the router with addresses on both IP networks.
  726.  
  727.  
  728.  
  729.  
  730. Garrett, Hagan & Wong                                          [Page 13]
  731.  
  732. RFC 1433                      Directed ARP                    March 1993
  733.  
  734.  
  735.    To benefit from Directed ARP procedures, the link-state routing
  736.    protocol must include procedures for a router to advertise
  737.    connectivity to multiple IP networks via the same link, and the
  738.    routing table calculation process must include procedures to
  739.    calculate ARP Helper Addresses and procedures to accurately calculate
  740.    the reduced cost of the path to a foreign IP network reached directly
  741.    via Directed ARP procedures.
  742.  
  743.    The Shortest Path First algorithm for calculating least cost routes
  744.    is based on work by Dijkstra [7], and was first used in a routing
  745.    protocol by the ARPANET, as described by McQuillan [8].  A router
  746.    constructs its routing table by building a shortest path tree, with
  747.    itself as root.  The process is iterative, starting with no entries
  748.    on the shortest path tree, and the router, itself, as the only entry
  749.    in a list of candidate vertices.  The router then loops on the
  750.    following two steps.
  751.  
  752.      1.  Remove the entry from the candidate list that is closest to
  753.          root, and add it to the shortest path tree.
  754.  
  755.      2.  Examine the link state advertisement from the entry added to
  756.          the shortest path tree in step 1.  For each neighbor (i.e.,
  757.          router or IP network to which a link connects)
  758.  
  759.             - If the neighbor is already on the shortest path tree, do
  760.               nothing.
  761.  
  762.             - If the neighbor is on the candidate list, recalculate the
  763.               distance from root to the neighbor.  Also recalculate the
  764.               next-hop(s) to the neighbor.
  765.  
  766.             - If the neighbor is not on the candidate list, calculate
  767.               the distance from root to the neighbor and the next-hop(s)
  768.               from root to the neighbor, and add the neighbor to the
  769.               candidate list.
  770.  
  771. The process terminates when there are no entries on the candidate list.
  772.  
  773. To take advantage of Directed ARP procedures, the link-state protocol
  774. must provide procedures to advertise that a router accesses two or more
  775. IP networks via the same link.  In addition, the Shortest Path First
  776. calculation is modified to calculate ARP Helper Addresses and recognize
  777. path cost reductions achieved via Directed ARP.
  778.  
  779.      1.  If a neighbor under consideration is an IP network, and its
  780.          parent (i.e., the entry added to the shortest path tree in step
  781.          1, above) has advertised that the neighbor is reached via the
  782.          same link as a network that is already on the shortest path
  783.  
  784.  
  785.  
  786. Garrett, Hagan & Wong                                          [Page 14]
  787.  
  788. RFC 1433                      Directed ARP                    March 1993
  789.  
  790.  
  791.          tree, the distance from root and next-hop(s) from root to the
  792.          neighbor are the same as the distance and next-hop(s)
  793.          associated with the network already on the shortest path tree.
  794.          If the ARP Helper Address associated with the network that is
  795.          already on the shortest path tree is not NULL, the neighbor
  796.          also inherits the ARP Helper Address from the network that is
  797.          already on the shortest path tree.
  798.  
  799.      2.  If the calculated next-hop to the neighbor is not NULL, the
  800.          neighbor inherits the ARP Helper Address from its parent.
  801.          Otherwise, except as described in item 1, the ARP Helper
  802.          Address is the IP address of the next-hop to the neighbor's
  803.          parent.  Note that the next-hop to root is NULL.
  804.  
  805.    For each router or IP network on the shortest path tree, the Shortest
  806.    Path First algorithm described above must calculate one or more
  807.    next-hops that can be used to access the router or IP network.  A
  808.    router that advertises a link to an IP network must include an IP
  809.    address that can be used by other routers on the IP network when
  810.    using the router as a next-hop.  A router might advertise that it was
  811.    connected to two IP networks via the same link by advertising the
  812.    same next-hop IP address for access from both IP networks.  To
  813.    accommodate the address resolution constraints of routers on both IP
  814.    networks the router might advertise two IP addresses (one from each
  815.    IP network) as next-hop IP addresses for access from both IP
  816.    networks.
  817.  
  818. 5.  Robustness
  819.  
  820.    Hosts and routers can use Directed ARP to resolve third-party next-
  821.    hop addresses; i.e., next-hop addresses learned from a routing
  822.    protocol peer or current next-hop router.  Undetected failure of a
  823.    third party next-hop can result in a routing "black hole".  To avoid
  824.    "black holes", host requirements [5] specify that a host "...MUST be
  825.    able to detect the failure of a 'next-hop' gateway that is listed in
  826.    its route cache and to choose an alternate gateway."  A host may
  827.    receive feedback from protocol layers above IP (e.g., TCP) that
  828.    indicates the status of a next-hop router, and may use other
  829.    procedures (e.g., ICMP echo) to test the status of a next-hop router.
  830.    But the complexity of routing is borne by routers, whose routing
  831.    information must be consistent with the information known to their
  832.    peers.  Routing protocols such as BGP [3], OSPF [4], and others,
  833.    require that routers must stand behind routing information that they
  834.    advertise.  Routers tag routing information with the IP address of
  835.    the router that advertised the information.  If the information
  836.    becomes invalid, the router that advertised the information must
  837.    advertise that the old information is no longer valid.  If a source
  838.    of routing information becomes unavailable, all information received
  839.  
  840.  
  841.  
  842. Garrett, Hagan & Wong                                          [Page 15]
  843.  
  844. RFC 1433                      Directed ARP                    March 1993
  845.  
  846.  
  847.    from that source must be marked as no longer valid.  The complexity
  848.    of dynamic routing protocols stems from procedures to ensure routers
  849.    either receive routing updates sent by a peer, or are able to
  850.    determine that they did not receive the updates (e.g., because
  851.    connectivity to the peer is no longer available).
  852.  
  853.    Third-party next-hops can also result in "black holes" if the
  854.    underlying link layer network connectivity is not transitive.  For
  855.    example, SMDS filters [9] could be administered to permit
  856.    communication between the SMDS addresses of router R1 and router R2,
  857.    and between the SMDS addresses of router R2 and router R3, and to
  858.    block communication between the SMDS addresses of router R1 and
  859.    router R3.  Router R2 could advertise router R3 as a next-hop to
  860.    router R1, but SMDS filters would prevent direct communication
  861.    between router R1 and router R3.  Non-symmetric filters might permit
  862.    router R3 to send packets to router R1, but block packets sent by
  863.    router R1 addressed to router R3.
  864.  
  865.    A host or router could verify link level connectivity with a next-hop
  866.    router by sending an ICMP echo to the link level address of the
  867.    next-hop router.  (Note that the ICMP echo is sent directly to the
  868.    link level address of the next-hop router, and is not routed to the
  869.    IP address of the next-hop router.  If the ICMP echo is routed, it
  870.    may follow a path that does not verify link level connectivity.) This
  871.    test could be performed before adding the associated routing table
  872.    entry, or before the first use of the routing table entry.  Detection
  873.    of subsequent changes in link level connectivity is a dynamic routing
  874.    protocol issue and is beyond the scope of this memo.
  875.  
  876. References
  877.  
  878.    [1] Piscitello, D., and J. Lawrence, "The Transmission of IP
  879.        Datagrams over the SMDS Service", RFC 1209, Bell Communications
  880.        Research, March 1991.
  881.  
  882.    [2] Plummer, D., "An Ethernet Address Resolution Protocol - or -
  883.        Converting Network Protocol Addresses to 48.bit Ethernet Address
  884.        for Transmission on Ethernet Hardware", RFC 826, Symbolics, Inc.,
  885.        November 1982.
  886.  
  887.    [3] Lougheed, K. and Y. Rekhter, "A Border Gateway Protocol 3 (BGP-
  888.        3)", RFC 1267, cisco Systems and IBM T. J. Watson Research
  889.        Center, October 1991.
  890.  
  891.    [4] Moy, J., "OSPF Version 2", RFC 1247, Proteon, Inc., July 1991.
  892.  
  893.    [5] Braden, R., editor, "Requirements for Internet Hosts --
  894.        Communication Layers", STD 3, RFC 1122, USC/Information Sciences
  895.  
  896.  
  897.  
  898. Garrett, Hagan & Wong                                          [Page 16]
  899.  
  900. RFC 1433                      Directed ARP                    March 1993
  901.  
  902.  
  903.        Institute, October 1989.
  904.  
  905.    [6] Postel, J., "Internet Control Message Protocol - DARPA Internet
  906.        Program Protocol Specification", STD 5, RFC 792, USC/Information
  907.        Sciences Institute, September 1981.
  908.  
  909.    [7] Dijkstra, E. W., "A Note on Two Problems in Connection with
  910.        Graphs", Numerische Mathematik, Vol. 1, pp. 269-271, 1959.
  911.  
  912.    [8] McQuillan, J. M., I. Richer, and E. C. Rosen, "The New Routing
  913.        Algorithm for the ARPANET", IEEE Transactions on Communications,
  914.        Vol. COM-28, May 1980.
  915.  
  916.    [9] "Generic System Requirements In Support of Switched Multi-
  917.        megabit Data Service", Technical Reference TR-TSV-000772, Bell
  918.        Communications Research Technical Reference, Issue 1, May 1991.
  919.  
  920.  
  921.  
  922.  
  923.  
  924.  
  925.  
  926.  
  927.  
  928.  
  929.  
  930.  
  931.  
  932.  
  933.  
  934.  
  935.  
  936.  
  937.  
  938.  
  939.  
  940.  
  941.  
  942.  
  943.  
  944.  
  945.  
  946.  
  947.  
  948.  
  949.  
  950.  
  951.  
  952.  
  953.  
  954. Garrett, Hagan & Wong                                          [Page 17]
  955.  
  956. RFC 1433                      Directed ARP                    March 1993
  957.  
  958.  
  959. Security Considerations
  960.  
  961.    Security issues are not discussed in this memo.
  962.  
  963. Authors' Addresses
  964.  
  965.    John Garrett
  966.    AT&T Bell Laboratories
  967.    184 Liberty Corner Road
  968.    Warren, N.J. 07060-0906
  969.  
  970.    Phone: (908) 580-4719
  971.    EMail: jwg@garage.att.com
  972.  
  973.  
  974.    John Dotts Hagan
  975.    University of Pennsylvania
  976.    Suite 221A
  977.    3401 Walnut Street
  978.    Philadelphia, PA 19104-6228
  979.  
  980.    Phone: (215) 898-9192
  981.    EMail: Hagan@UPENN.EDU
  982.  
  983.  
  984.    Jeffrey A. Wong
  985.    AT&T Bell Laboratories
  986.    184 Liberty Corner Road
  987.    Warren, N.J. 07060-0906
  988.  
  989.    Phone: (908) 580-5361
  990.    EMail: jwong@garage.att.com
  991.  
  992.  
  993.  
  994.  
  995.  
  996.  
  997.  
  998.  
  999.  
  1000.  
  1001.  
  1002.  
  1003.  
  1004.  
  1005.  
  1006.  
  1007.  
  1008.  
  1009.  
  1010. Garrett, Hagan & Wong                                          [Page 18]
  1011.