diff options
Diffstat (limited to 'doc/rfc/rfc1433.txt')
| -rw-r--r-- | doc/rfc/rfc1433.txt | 1011 |
1 files changed, 1011 insertions, 0 deletions
diff --git a/doc/rfc/rfc1433.txt b/doc/rfc/rfc1433.txt new file mode 100644 index 0000000..9f3aacb --- /dev/null +++ b/doc/rfc/rfc1433.txt @@ -0,0 +1,1011 @@ + + + + + + +Network Working Group J. Garrett +Request for Comments: 1433 AT&T Bell Laboratories + J. Hagan + University of Pennsylvania + J. Wong + AT&T Bell Laboratories + March 1993 + + + Directed ARP + +Status of this Memo + + This memo defines an Experimental Protocol for the Internet + community. Discussion and suggestions for improvement are requested. + Please refer to the current edition of the "IAB Official Protocol + Standards" for the standardization state and status of this protocol. + Distribution of this memo is unlimited. + +Abstract + + A router with an interface to two IP networks via the same link level + interface could observe that the two IP networks share the same link + level network, and could advertise that information to hosts (via + ICMP Redirects) and routers (via dynamic routing protocols). + However, a host or router on only one of the IP networks could not + use that information to communicate directly with hosts and routers + on the other IP network unless it could resolve IP addresses on the + "foreign" IP network to their corresponding link level addresses. + Directed ARP is a dynamic address resolution procedure that enables + hosts and routers to resolve advertised potential next-hop IP + addresses on foreign IP networks to their associated link level + addresses. + +Acknowledgments + + The authors are indebted to Joel Halpern of Network Systems + Corporation and David O'Leary who provided valuable comments and + insight to the authors, as well as ongoing moral support as the + presentation of this material evolved through many drafts. Members + of the IPLPDN working group also provided valuable comments during + presentations and through the IPLPDN mailing list. Chuck Hedrick of + Rutgers University, Paul Tsuchiya of Bell Communications Research, + and Doris Tillman of AT&T Bell Laboratories provided early insight as + well as comments on early drafts. + + + + + + +Garrett, Hagan & Wong [Page 1] + +RFC 1433 Directed ARP March 1993 + + +1. Terminology + + A "link level network" is the upper layer of what is sometimes + referred to (e.g., OSI parlance) as the "subnetwork", i.e., the + layers below IP. The term "link level" is used to avoid potential + confusion with the term "IP sub-network", and to identify addresses + (i.e., "link level address") associated with the network used to + transport IP datagrams. + + From the perspective of a host or router, an IP network is "foreign" + if the host or router does not have an address on the IP network. + +2. Introduction + + Multiple IP networks may be administered on the same link level + network (e.g., on a large public data network). A router with a + single interface on two IP networks could use existing routing update + procedures to advertise that the two IP networks shared the same link + level network. Cost/performance benefits could be achieved if hosts + and routers that were not on the same IP network could use that + advertised information, and exchange packets directly, rather than + through the dual addressed router. But a host or router can not send + packets directly to an IP address without first resolving the IP + address to its link level address. + + IP address resolution procedures are established independently for + each IP network. For example, on an SMDS network [1], address + resolution may be achieved using the Address Resolution Protocol + (ARP) [2], with a separate SMDS ARP Request Address (e.g., an SMDS + Multicast Group Address) associated with each IP network. A host or + router that was not configured with the appropriate ARP Request + Address would have no way to learn the ARP Request Address associated + with an IP network, and would not send an ARP Request to the + appropriate ARP Request Address. On an Ethernet network a host or + router might guess that an IP address could be resolved by sending an + ARP Request to the broadcast address. But if the IP network used a + different address resolution procedure (e.g., administered address + resolution tables), the ARP Request might go unanswered. + + Directed ARP is a procedure that enables a router advertising that an + IP address is on a shared link level network to also aid in resolving + the IP address to its associated link level address. By removing + address resolution constraints, Directed ARP enables dynamic routing + protocols such as BGP [3] and OSPF [4] to advertise and use routing + information that leads to next-hop addresses on "foreign" IP + networks. In addition, Directed ARP enables routers to advertise + (via ICMP Redirects) next-hop addresses that are "foreign" to hosts, + since the hosts can use Directed ARP to resolve the "foreign" next- + + + +Garrett, Hagan & Wong [Page 2] + +RFC 1433 Directed ARP March 1993 + + + hop addresses. + +3. Directed ARP + + Directed ARP uses the normal ARP packet format, and is consistent + with ARP procedures, as defined in [1] and [2], and with routers and + hosts that implement those procedures. + +3.1 ARP Helper Address + + Hosts and routers maintain routing information, logically organized + as a routing table. Each routing table entry associates one or more + destination IP addresses with a next-hop IP address and a physical + interface used to forward a packet to the next-hop IP address. If + the destination IP address is local (i.e., can be reached without the + aid of a router), the next-hop IP address is NULL (or a logical + equivalent, such as the IP address of the associated physical + interface). Otherwise, the next-hop IP address is the address of a + next-hop router. + + A host or router that implements Directed ARP procedures associates + an ARP Helper Address with each routing table entry. If the host or + router has been configured to resolve the next-hop IP address to its + associated link level address (or to resolve the destination IP + address, if the next-hop IP address is NULL), the associated ARP + Helper Address is NULL. Otherwise, the ARP Helper Address is the IP + address of the router that provided the routing information + indicating that the next-hop address was on the same link level + network as the associated physical interface. Section 4 provides + detailed examples of the determination of ARP Helper Addresses by + dynamic routing procedures. + +3.2 Address Resolution Procedures + + To forward an IP packet, a host or router searches its routing table + for an entry that is the best match based on the destination IP + address and perhaps other factors (e.g., Type of Service). The + selected routing table entry includes the IP address of a next-hop + router (which may be NULL), the physical interface through which the + IP packet should be forwarded, an ARP Helper Address (which may be + NULL), and other information. The routing function passes the next- + hop IP address, the physical interface, and the ARP Helper Address to + the address resolution function. The address resolution function + must then resolve the next-hop IP address (or destination IP address + if the next-hop IP address is NULL) to its associated link level + address. The IP packet, the link level address to which the packet + should be forwarded, and the interface through which the packet + should be forwarded are then passed to the link level driver + + + +Garrett, Hagan & Wong [Page 3] + +RFC 1433 Directed ARP March 1993 + + + associated with the physical interface. The link level driver + encapsulates the IP packet in one or more link level frames (i.e., + may do fragmentation) addressed to the associated link level address, + and forwards the frame(s) through the appropriate physical interface. + The details of the functions performed are described via C pseudo- + code below. + + The procedures are organized as two functions, Route() and Resolve(), + corresponding to routing and address resolution. In addition, the + following low level functions are also used: + + Get_Route(IP_Add,Other) returns a pointer to the routing table + entry with the destination field that best matches IP_Add. If no + matching entry is found, NULL is returned. Other information such + as Type of Service may be considered in selecting the best route. + + Forward(Packet,Link_Level_Add,Phys_Int) fragments Packet (if + needed), and encapsulates Packet in one or more Link Level Frames + addressed to Link_Level_Add, and forwards the frame(s) through + interface, Phys_Int. + + Look_Up_Add_Res_Table(IP_Add,Phys_Int) returns a pointer to the + link level address associated with IP_Add in the address + resolution table associated with interface, Phys_Int. If IP_Add + is not found in the address resolution table, NULL is returned. + + Local_Add_Res(IP_Add,Phys_Int) returns a pointer to the Link Level + address associated with IP_Add, using address resolution + procedures associated with address, IP_Add, and interface, + Phys_Int. If address resolution is unsuccessful, NULL is + returned. Note that different address resolution procedures may + be used for different IP networks. + + Receive_ARP_Response(IP_Add,Phys_Int) returns a pointer to an ARP + Response received through interface, Phys_Int, that resolves + IP_Add. If no ARP response is received, NULL is returned. + + Dest_IP_Add(IP_Packet) returns the IP destination address from + IP_Packet. + + Next_Hop(Entry) returns the IP address in the next-hop field of + (routing table) Entry. + + Interface(Entry) returns the physical interface field of (routing + table) Entry. + + ARP_Helper_Add(Entry) returns the IP address in the ARP Helper + Address field of (routing table) Entry. + + + +Garrett, Hagan & Wong [Page 4] + +RFC 1433 Directed ARP March 1993 + + + ARP_Request(IP_Add) returns an ARP Request packet with IP_Add as + the Target IP address. + + Source_Link_Level(ARP_Response) returns the link level address of + the sender of ARP_Response. + + + + + ROUTE(IP_Packet) + { + Entry = Get_Route(Dest_IP_Add(IP_Packet),Other(IP_Packet)); + If (Entry == NULL) /* No matching entry in routing table */ + Return; /* Discard IP_Packet */ + else + { /* Resolve next-hop IP address to link level address */ + If (Next_Hop(Entry) != NULL) /* Route packet via next-hop router */ + Next_IP = Next_Hop(Entry); + else /* Destination is local */ + Next_IP = Dest_IP_Add(IP_Packet); + L_L_Add = Resolve(Next_IP,Interface(Entry),ARP_Helper_Add(Entry)); + If (L_L_Add != NULL) + Forward(IP_Packet,L_L_Add,Interface(Entry)); + else /* Couldn't resolve next-hop IP address */ + Return; /* Discard IP_Packet */ + Return; + } + } + + Figure 1: C Pseudo-Code for the Routing function. + + + + + + + + + + + + + + + + + + + + + +Garrett, Hagan & Wong [Page 5] + +RFC 1433 Directed ARP March 1993 + + + Resolve(IP_Add,Interface,ARP_Help_Add) + { + If ((L_L_Add = Look_Up_Add_Res_Table(IP_Add,Interface)) != NULL) + { /* Found it in Address Resolution Table */ + Return L_L_Add; + } + else + { + If (ARP_Help_Add == NULL) + { /* Do local Address Resolution Procedure */ + Return Local_Add_Res(IP_Add,Interface); + } + else /* ARP_Help_Add != NULL */ + { + L_L_ARP_Help_Add = Look_Up_Add_Res_Table(ARP_Help_Add,Interface); + If (L_L_ARP_Help_Add == NULL) + /* Not in Address Resolution Table */ + L_L_ARP_Help_Add = Local_Add_Res(ARP_Help_Add,Interface); + If (L_L_ARP_Help_Add == NULL) /* Can't Resolve ARP Helper Add */ + Return NULL; /* Address Resolution Failed */ + else + { /* ARP for IP_Add */ + Forward(ARP_Request(IP_Add),L_L_ARP_Help_Add,Interface); + ARP_Resp = Receive_ARP_Response(IP_Add,Interface); + If (ARP_Resp == NULL) /* No ARP Response (after persistence) */ + Return NULL; /* Address Resolution Failed */ + else + Return Source_Link_Level(ARP_Resp); + } + } + } + } + } + + Figure 2: C Pseudo-Code for Address Resolution function. + + + +3.3 Forwarding ARP Requests + + A host that implements Directed ARP procedures uses normal procedures + to process received ARP Requests. That is, if the Target IP address + is the host's address, the host uses normal procedures to respond to + the ARP Request. If the Target IP address is not the host's address, + the host silently discards the ARP Request. + + If the Target IP address of an ARP Request received by a router is + the router's address, the router uses normal procedures to respond to + + + +Garrett, Hagan & Wong [Page 6] + +RFC 1433 Directed ARP March 1993 + + + the ARP Request. But if the Target IP address is not the router's + address, the router may forward the ARP Request back through the same + interface it was received from, addressed to a Link Level Address + that corresponds to an ARP Helper Address in the router's routing + table. The procedures used to process an ARP Request are described + via C pseudo-code below. The function Receive() describes procedures + followed by hosts and routers, and the function Direct() describes + additional procedures followed by routers. In addition, the + following low level functions are also used: + + Is_Local_IP_Add(IP_Add,Phys_Int) returns TRUE if Phys_Int has been + assigned IP address, IP_Add. Otherwise, returns FALSE. + + Do_ARP_Processing(ARP_Request,Interface) processes ARP_Request + using ARP procedures described in [2]. + + I_Am_Router returns TRUE if device is a router and False if device + is a host. + + Target_IP(ARP_Request) returns the Target IP address from + ARP_Request. + + Filter(ARP_Request,Phys_Int) returns TRUE if ARP_Request passes + filtering constraints, and FALSE if filtering constraints are not + passed. See section 3.4. + + Forward(Packet,Link_Level_Add,Phys_Int) fragments Packet (if + needed), and encapsulates Packet in one or more Link Level Frames + addressed to Link_Level_Add, and forwards the frame(s) through + interface, Phys_Int. + + Look_Up_Next_Hop_Route_Table(IP_Add) returns a pointer to the + routing table entry with the next-hop field that matches IP_Add. + If no matching entry is found, NULL is returned. + + Look_Up_Dest_Route_Table(IP_Add) returns a pointer to the routing + table entry with the destination field that best matches IP_Add. + If no matching entry is found, NULL is returned. + + Link_Level_ARP_Req_Add(IP_Add,Phys_Int) returns the link level + address to which an ARP Request to resolve IP_Add should be + forwarded. If ARP is not used to perform local address resolution + of IP_Add, NULL is returned. + + Local_Add_Res(IP_Add,Phys_Int) returns a pointer to the Link Level + address associated with IP_Add, using address resolution + procedures associated with address, IP_Add, and interface, + Phys_Int. If address resolution is unsuccessful, NULL is + + + +Garrett, Hagan & Wong [Page 7] + +RFC 1433 Directed ARP March 1993 + + + returned. Note that different address resolution procedures may + be used for different IP networks. + + Next_Hop(Entry) returns the IP address in the next-hop field of + (routing table) Entry. + + Interface(Entry) returns the physical interface field of (routing + table) Entry. + + ARP_Helper_Add(Entry) returns the IP address in the ARP Helper + Address field of (routing table) Entry. + + Source_Link_Level(ARP_Request) returns the link level address of + the sender of ARP_Request. + + + + + + Receive(ARP_Request,Interface) + { + If (Is_Local_IP_Add(Target_IP(ARP_Request),Interface)) + Do_ARP_Processing(ARP_Request,Interface); + else /* Not my IP Address */ + If (I_Am_Router) /* Hosts don't Direct ARP Requests */ + If (Filter(ARP_Request,Interface)) /* Passes Filter Test */ + /* See Section 3.4 */ + Direct(ARP_Request,Interface); /* Directed ARP Procedures */ + Return; + } + + Figure 3: C Pseudo-Code for Receiving ARP Requests. + + + + + + + + + + + + + + + + + + + +Garrett, Hagan & Wong [Page 8] + +RFC 1433 Directed ARP March 1993 + + + Direct(ARP_Request,Phys_Int) + { + Entry = Look_Up_Next_Hop_Route_Table(Target_IP(ARP_Request)); + If (Entry == NULL) /* Target_IP Address is not a next-hop */ + { /* in Routing Table */ + Entry = Look_Up_Dest_Route_Table(Target_IP(ARP_Request)); + If (Entry == NULL) /* Not a destination either */ + Return; /* Discard ARP Request */ + else + If (Next_Hop(Entry) != NULL) /* Not a next-hop and Not local */ + Return; /* Discard ARP Request */ + } + If (Interface(Entry) != Phys_Int) + /* Must be same physical interface */ + Return; /* Discard ARP Request */ + If (ARP_Helper_Add(Entry) != NULL) + { + L_L_ARP_Helper_Add = Resolve(ARP_Helper_Add(Entry),Phys_Int,NULL); + If (L_L_ARP_Helper_Add != NULL) + Forward(ARP_Request,L_L_ARP_Helper_Add,Phys_Int); + /* Forward ARP_Request to ARP Helper Address */ + Return; + } + else /* Do local address resolution. */ + { + L_L_ARP_Req_Add = + Link_Level_ARP_Req_Add(Target_IP(ARP_Request),Phys_Int); + If (L_L_ARP_Req_Add != NULL) + { /* Local address resolution procedure is ARP. */ + /* Forward ARP_Request. */ + Forward(ARP_Request,L_L_ARP_Req_Add,Phys_Int); + Return; + } + else + { /* Local address resolution procedure is not ARP. */ + /* Do "published ARP" on behalf of Target IP Address */ + Target_Link_Level = + Local_Add_Res(Target_IP(ARP_Request),Phys_Int); + If (Target_Link_Level != NULL) /* Resolved Address */ + { + Forward(ARP_Response,Source_Link_Level(ARP_Request),Phys_Int); + } + Return; + } + } + } + + Figure 4: C Pseudo_Code for Directing ARP Requests. + + + +Garrett, Hagan & Wong [Page 9] + +RFC 1433 Directed ARP March 1993 + + +3.4 Filtering Procedures + + A router performing Directed ARP procedures must filter the + propagation of ARP Request packets to constrain the scope of + potential "ARP floods" caused by misbehaving routers or hosts, and to + terminate potential ARP loops that may occur during periods of + routing protocol instability or as a result of inappropriate manual + configurations. Specific procedures to filter the propagation of ARP + Request packets are beyond the scope of this document. The following + procedures are suggested as potential implementations that should be + sufficient. Other procedures may be better suited to a particular + implementation. + + To control the propagation of an "ARP flood", a router performing + Directed ARP procedures could limit the number of identical ARP + Requests (i.e., same Source IP address and same Target IP address) + that it would forward per small time interval (e.g., no more than one + ARP Request per second). This is consistent with the procedure + suggested in [5] to prevent ARP flooding. + + Forwarding of ARP Request packets introduces the possibility of ARP + loops. The procedures used to control the scope of potential ARP + floods may terminate some ARP loops, but additional procedures are + needed if the time required to traverse a loop is longer than the + timer used to control ARP floods. A router could refuse to forward + more than N identical ARP Requests per T minutes, where N and T are + administered numbers. If T and N are chosen so that T/N minutes is + greater than the maximum time required to traverse a loop, such a + filter would terminate the loop. In some cases a host may send more + than one ARP Request with the same Source IP address,Target IP + address pair (i.e., N should be greater than 1). For example, the + first ARP Request might be lost. However, once an ARP Response is + received, a host would normally save the associated information, and + therefore would not generate an identical ARP Request for a period of + time on the order of minutes. Therefore, T may be large enough to + ensure that T/N is much larger than the time to traverse any loop. + + In some implementations the link level destination address of a frame + used to transport an ARP Request to a router may be available to the + router's Directed ARP filtering process. An important class of + simple ARP loops will be prevented from starting if a router never + forwards an ARP Request to the same link level address to which the + received ARP Request was addressed. Of course, other procedures such + as the one described in the paragraph above will stop all loops, and + are needed, even if filters are implemented that prevent some loops + from starting. + + + + + +Garrett, Hagan & Wong [Page 10] + +RFC 1433 Directed ARP March 1993 + + + Host requirements [5] specify that "the packet receive interface + between the IP layer and the link layer MUST include a flag to + indicate whether the incoming packet was addressed to a link-level + broadcast address." An important class of simple ARP floods can be + eliminated if routers never forward ARP Requests that were addressed + to a link-level broadcast address. + +4. Use of Directed ARP by Routing + + The exchange and use of routing information is constrained by + available address resolution procedures. A host or router can not + use a next-hop IP address learned via dynamic routing procedures if + it is unable to resolve the next-hop IP address to the associated + link level address. Without compatible dynamic address resolution + procedures, a router may not advertise a next-hop address that is not + on the same IP network as the host or router receiving the + advertisement. Directed ARP is a procedure that enables a router + that advertises routing information to make the routing information + useful by also providing assistance in resolving the associated + next-hop IP addresses. + + The following subsections describe the use of Directed ARP to expand + the scope of ICMP Redirects [6], distance-vector routing protocols + (e.g., BGP [3]), and link-state routing protocols (e.g., OSPF [4]). + +4.1 ICMP Redirect + + If a router forwards a packet to a next-hop address that is on the + same link level network as the host that originated the packet, the + router may send an ICMP Redirect to the host. But a host can not use + a next-hop address advertised via an ICMP Redirect unless the host + has a procedure to resolve the advertised next-hop address to its + associated link level address. Directed ARP is a procedure that a + host could use to resolve an advertised next-hop address, even if the + host does not have an address on the same IP network as the + advertised next-hop address. + + A host that implements Directed ARP procedures includes an ARP Helper + Address with each routing table entry. The ARP Helper Address + associated with an entry learned via an ICMP Redirect is NULL if the + associated next-hop address matches a routing table entry with a NULL + next-hop and a NULL ARP Helper Address (i.e., the host already knows + how to resolve the next-hop address). Otherwise, the ARP Helper + Address is the IP address of the router that sent the ICMP Redirect. + Note that the router that sent the ICMP Redirect is the current + next-hop to the advertised destination [5]. Therefore, the host + should have an entry in its address resolution table for the new ARP + Helper Address. If the host is unable to resolve the next-hop IP + + + +Garrett, Hagan & Wong [Page 11] + +RFC 1433 Directed ARP March 1993 + + + address advertised in the ICMP Redirect (e.g., because the associated + ARP Helper Address is on a foreign IP network; i.e., was learned via + an old ICMP Redirect, and the address resolution table entry for that + ARP Helper Address timed out), the host must flush the associated + routing table entry. Directed ARP procedures do not recursively use + Directed ARP to resolve an ARP Helper Address. + + A router that performs Directed ARP procedures might advertise a + foreign next-hop to a host that does not perform Directed ARP. + Following existing procedures, the host would silently discard the + ICMP Redirect. A router that does not implement Directed ARP should + not advertise a next-hop on a foreign IP network, as specified by + existing procedures. If it did, and the ICMP Redirect was received + by a host that implemented Directed ARP procedures, the host would + send an ARP Request for the foreign IP address to the advertising + router, which would silently discard the ARP Request. When address + resolution fails, the host should flush the associated entry from its + routing table. + + For various reasons a host may ignore an ICMP Redirect and may + continue to forward packets to the same router that sent the ICMP + Redirect. For example, a host that does not implement Directed ARP + procedures would silently discard an ICMP Redirect advertising a + next-hop address on a foreign IP network. Routers should implement + constraints to control the number of ICMP Redirects sent to hosts. + For example, a router might limit the number of repeated ICMP + Redirects sent to a host to no more than N ICMP Redirects per T + minutes, where N and T are administered values. + +4.2 Distance Vector Routing Protocol + + A distance-vector routing protocol provides procedures for a router + to advertise a destination address (e.g., an IP network), an + associated next-hop address, and other information (e.g., associated + metric). But a router can not use an advertised route unless the + router has a procedure to resolve the advertised next-hop address to + its associated link level address. Directed ARP is a procedure that + a router could use to resolve an advertised next-hop address, even if + the router does not have an address on the same IP network as the + advertised next-hop address. + + The following procedures assume a router only accepts routing updates + if it knows the IP address of the sender of the update, can resolve + the IP address of the sender to its associated link level address, + and has an interface on the same link level network as the sender. + + A router that implements Directed ARP procedures includes an ARP + Helper Address with each routing table entry. The ARP Helper Address + + + +Garrett, Hagan & Wong [Page 12] + +RFC 1433 Directed ARP March 1993 + + + associated with an entry learned via a routing protocol update is + NULL if the associated next-hop address matches a routing table entry + with a NULL next-hop and NULL ARP Helper Address (i.e., the router + already knows how to resolve the next-hop address). Otherwise, the + ARP Helper Address is the IP address of the router that sent the + routing update. + + Some distance-vector routing protocols (e.g., BGP [3]) provide syntax + that would permit a router to advertise an address on a foreign IP + network as a next-hop. If a router that implements Directed ARP + procedures advertises a foreign next-hop IP address to a second + router that does not implement Directed ARP procedures, the second + router can not use the advertised foreign next-hop. Depending on the + details of the routing protocol implementation, it might be + appropriate for the first router to also advertise a next-hop that is + not on a foreign IP network (e.g., itself), perhaps at a higher cost. + Or, if the routing relationship is an administered connection (e.g., + BGP relationships are administered TCP/IP connections), the + administrative procedure could determine whether foreign next-hop IP + addresses should be advertised. + + A distance-vector routing protocol could advertise that a destination + is directly reachable by specifying that the router receiving the + advertisement is, itself, the next-hop to the destination. In + addition, the advertised metric for the route might be zero. If the + router did not already have a routing table entry that specified the + advertised destination was local (i.e., NULL next-hop address), the + router could add the new route with NULL next-hop, and the IP address + of the router that sent the update as ARP Helper Address. + +4.3 Link State Routing Protocol + + A link-state routing protocol provides procedures for routers to + identify links to other entities (e.g., other routers and networks), + determine the state or cost of those links, reliably distribute + link-state information to other routers in the routing domain, and + calculate routes based on link-state information received from other + routers. A router with an interface to two (or more) IP networks via + the same link level interface is connected to those IP networks via a + single link, as described above. If a router could advertise that it + used the same link to connect to two (or more) IP networks, and would + perform Directed ARP procedures, routers on either of the IP networks + could forward packets directly to hosts and routers on both IP + networks, using Directed ARP procedures to resolve addresses on the + foreign IP network. With Directed ARP, the cost of the direct path + to the foreign IP network would be less than the cost of the path + through the router with addresses on both IP networks. + + + + +Garrett, Hagan & Wong [Page 13] + +RFC 1433 Directed ARP March 1993 + + + To benefit from Directed ARP procedures, the link-state routing + protocol must include procedures for a router to advertise + connectivity to multiple IP networks via the same link, and the + routing table calculation process must include procedures to + calculate ARP Helper Addresses and procedures to accurately calculate + the reduced cost of the path to a foreign IP network reached directly + via Directed ARP procedures. + + The Shortest Path First algorithm for calculating least cost routes + is based on work by Dijkstra [7], and was first used in a routing + protocol by the ARPANET, as described by McQuillan [8]. A router + constructs its routing table by building a shortest path tree, with + itself as root. The process is iterative, starting with no entries + on the shortest path tree, and the router, itself, as the only entry + in a list of candidate vertices. The router then loops on the + following two steps. + + 1. Remove the entry from the candidate list that is closest to + root, and add it to the shortest path tree. + + 2. Examine the link state advertisement from the entry added to + the shortest path tree in step 1. For each neighbor (i.e., + router or IP network to which a link connects) + + - If the neighbor is already on the shortest path tree, do + nothing. + + - If the neighbor is on the candidate list, recalculate the + distance from root to the neighbor. Also recalculate the + next-hop(s) to the neighbor. + + - If the neighbor is not on the candidate list, calculate + the distance from root to the neighbor and the next-hop(s) + from root to the neighbor, and add the neighbor to the + candidate list. + +The process terminates when there are no entries on the candidate list. + +To take advantage of Directed ARP procedures, the link-state protocol +must provide procedures to advertise that a router accesses two or more +IP networks via the same link. In addition, the Shortest Path First +calculation is modified to calculate ARP Helper Addresses and recognize +path cost reductions achieved via Directed ARP. + + 1. If a neighbor under consideration is an IP network, and its + parent (i.e., the entry added to the shortest path tree in step + 1, above) has advertised that the neighbor is reached via the + same link as a network that is already on the shortest path + + + +Garrett, Hagan & Wong [Page 14] + +RFC 1433 Directed ARP March 1993 + + + tree, the distance from root and next-hop(s) from root to the + neighbor are the same as the distance and next-hop(s) + associated with the network already on the shortest path tree. + If the ARP Helper Address associated with the network that is + already on the shortest path tree is not NULL, the neighbor + also inherits the ARP Helper Address from the network that is + already on the shortest path tree. + + 2. If the calculated next-hop to the neighbor is not NULL, the + neighbor inherits the ARP Helper Address from its parent. + Otherwise, except as described in item 1, the ARP Helper + Address is the IP address of the next-hop to the neighbor's + parent. Note that the next-hop to root is NULL. + + For each router or IP network on the shortest path tree, the Shortest + Path First algorithm described above must calculate one or more + next-hops that can be used to access the router or IP network. A + router that advertises a link to an IP network must include an IP + address that can be used by other routers on the IP network when + using the router as a next-hop. A router might advertise that it was + connected to two IP networks via the same link by advertising the + same next-hop IP address for access from both IP networks. To + accommodate the address resolution constraints of routers on both IP + networks the router might advertise two IP addresses (one from each + IP network) as next-hop IP addresses for access from both IP + networks. + +5. Robustness + + Hosts and routers can use Directed ARP to resolve third-party next- + hop addresses; i.e., next-hop addresses learned from a routing + protocol peer or current next-hop router. Undetected failure of a + third party next-hop can result in a routing "black hole". To avoid + "black holes", host requirements [5] specify that a host "...MUST be + able to detect the failure of a 'next-hop' gateway that is listed in + its route cache and to choose an alternate gateway." A host may + receive feedback from protocol layers above IP (e.g., TCP) that + indicates the status of a next-hop router, and may use other + procedures (e.g., ICMP echo) to test the status of a next-hop router. + But the complexity of routing is borne by routers, whose routing + information must be consistent with the information known to their + peers. Routing protocols such as BGP [3], OSPF [4], and others, + require that routers must stand behind routing information that they + advertise. Routers tag routing information with the IP address of + the router that advertised the information. If the information + becomes invalid, the router that advertised the information must + advertise that the old information is no longer valid. If a source + of routing information becomes unavailable, all information received + + + +Garrett, Hagan & Wong [Page 15] + +RFC 1433 Directed ARP March 1993 + + + from that source must be marked as no longer valid. The complexity + of dynamic routing protocols stems from procedures to ensure routers + either receive routing updates sent by a peer, or are able to + determine that they did not receive the updates (e.g., because + connectivity to the peer is no longer available). + + Third-party next-hops can also result in "black holes" if the + underlying link layer network connectivity is not transitive. For + example, SMDS filters [9] could be administered to permit + communication between the SMDS addresses of router R1 and router R2, + and between the SMDS addresses of router R2 and router R3, and to + block communication between the SMDS addresses of router R1 and + router R3. Router R2 could advertise router R3 as a next-hop to + router R1, but SMDS filters would prevent direct communication + between router R1 and router R3. Non-symmetric filters might permit + router R3 to send packets to router R1, but block packets sent by + router R1 addressed to router R3. + + A host or router could verify link level connectivity with a next-hop + router by sending an ICMP echo to the link level address of the + next-hop router. (Note that the ICMP echo is sent directly to the + link level address of the next-hop router, and is not routed to the + IP address of the next-hop router. If the ICMP echo is routed, it + may follow a path that does not verify link level connectivity.) This + test could be performed before adding the associated routing table + entry, or before the first use of the routing table entry. Detection + of subsequent changes in link level connectivity is a dynamic routing + protocol issue and is beyond the scope of this memo. + +References + + [1] Piscitello, D., and J. Lawrence, "The Transmission of IP + Datagrams over the SMDS Service", RFC 1209, Bell Communications + Research, March 1991. + + [2] Plummer, D., "An Ethernet Address Resolution Protocol - or - + Converting Network Protocol Addresses to 48.bit Ethernet Address + for Transmission on Ethernet Hardware", RFC 826, Symbolics, Inc., + November 1982. + + [3] Lougheed, K. and Y. Rekhter, "A Border Gateway Protocol 3 (BGP- + 3)", RFC 1267, cisco Systems and IBM T. J. Watson Research + Center, October 1991. + + [4] Moy, J., "OSPF Version 2", RFC 1247, Proteon, Inc., July 1991. + + [5] Braden, R., editor, "Requirements for Internet Hosts -- + Communication Layers", STD 3, RFC 1122, USC/Information Sciences + + + +Garrett, Hagan & Wong [Page 16] + +RFC 1433 Directed ARP March 1993 + + + Institute, October 1989. + + [6] Postel, J., "Internet Control Message Protocol - DARPA Internet + Program Protocol Specification", STD 5, RFC 792, USC/Information + Sciences Institute, September 1981. + + [7] Dijkstra, E. W., "A Note on Two Problems in Connection with + Graphs", Numerische Mathematik, Vol. 1, pp. 269-271, 1959. + + [8] McQuillan, J. M., I. Richer, and E. C. Rosen, "The New Routing + Algorithm for the ARPANET", IEEE Transactions on Communications, + Vol. COM-28, May 1980. + + [9] "Generic System Requirements In Support of Switched Multi- + megabit Data Service", Technical Reference TR-TSV-000772, Bell + Communications Research Technical Reference, Issue 1, May 1991. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Garrett, Hagan & Wong [Page 17] + +RFC 1433 Directed ARP March 1993 + + +Security Considerations + + Security issues are not discussed in this memo. + +Authors' Addresses + + John Garrett + AT&T Bell Laboratories + 184 Liberty Corner Road + Warren, N.J. 07060-0906 + + Phone: (908) 580-4719 + EMail: jwg@garage.att.com + + + John Dotts Hagan + University of Pennsylvania + Suite 221A + 3401 Walnut Street + Philadelphia, PA 19104-6228 + + Phone: (215) 898-9192 + EMail: Hagan@UPENN.EDU + + + Jeffrey A. Wong + AT&T Bell Laboratories + 184 Liberty Corner Road + Warren, N.J. 07060-0906 + + Phone: (908) 580-5361 + EMail: jwong@garage.att.com + + + + + + + + + + + + + + + + + + + +Garrett, Hagan & Wong [Page 18] +
\ No newline at end of file |