RFCs in HTML Format


RFC 1478

Network Working Group                                     M. Steenstrup
Request for Comments: 1478                 BBN Systems and Technologies
                                                              June 1993


            An Architecture for Inter-Domain Policy Routing













Steenstrup                                                      [Page 1]

RFC 1478 IDPR Architecture June 1993 Table of Contents 1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. The Internet Environment. . . . . . . . . . . . . . . . . . . 4 2. Approaches to Policy Routing. . . . . . . . . . . . . . . . . . 5 2.1. Policy Route Generation . . . . . . . . . . . . . . . . . . . 5 2.1.1. Distance Vector Approach. . . . . . . . . . . . . . . . . . 5 2.1.2. Link State Approach . . . . . . . . . . . . . . . . . . . . 7 2.2. Routing Information Distribution. . . . . . . . . . . . . . . 8 2.2.1. Distance Vector Approach. . . . . . . . . . . . . . . . . . 8 2.2.2. Link State Approach . . . . . . . . . . . . . . . . . . . .10 2.3. Message Forwarding along Policy Routes. . . . . . . . . . . .10 2.3.1. Hop-by-Hop Approach . . . . . . . . . . . . . . . . . . . .11 2.3.1.1. A Clarification . . . . . . . . . . . . . . . . . . . . .11 2.3.2. Source Specified Approach . . . . . . . . . . . . . . . . .12 3. The IDPR Architecture . . . . . . . . . . . . . . . . . . . . .13 3.1. IDPR Functions. . . . . . . . . . . . . . . . . . . . . . . .13 3.2. IDPR Entities . . . . . . . . . . . . . . . . . . . . . . . .13 3.2.1. Path Agents . . . . . . . . . . . . . . . . . . . . . . . .16 3.2.2. IDPR Servers. . . . . . . . . . . . . . . . . . . . . . . .17 3.2.3. Entity Identifiers. . . . . . . . . . . . . . . . . . . . .19 3.3. Security and Reliability. . . . . . . . . . . . . . . . . . .20 3.3.1. Retransmissions and Acknowledgements. . . . . . . . . . . .20 3.3.2. Integrity Checks. . . . . . . . . . . . . . . . . . . . . .21 3.3.3. Source Authentication . . . . . . . . . . . . . . . . . . .21 3.3.4. Timestamps. . . . . . . . . . . . . . . . . . . . . . . . .21 3.4. An Example of IDPR Operation. . . . . . . . . . . . . . . . .22 4. Accommodating a Large, Heterogeneous Internet . . . . . . . . .25 4.1. Domain Level Routing. . . . . . . . . . . . . . . . . . . . .25 4.2. Route Generation. . . . . . . . . . . . . . . . . . . . . . .27 4.3. Super Domains . . . . . . . . . . . . . . . . . . . . . . . .29 4.4. Domain Communities. . . . . . . . . . . . . . . . . . . . . .30 4.5. Robustness in the Presence of Failures. . . . . . . . . . . .31 4.5.1. Path Repair . . . . . . . . . . . . . . . . . . . . . . . .31 4.5.2. Partitions. . . . . . . . . . . . . . . . . . . . . . . . .33 5. References. . . . . . . . . . . . . . . . . . . . . . . . . . .XX 5. Security Considerations . . . . . . . . . . . . . . . . . . . .34 6. Author's Address . . . . . . . . . . . . . . . . . . . . . . .34 Steenstrup [Page 2]
RFC 1478 IDPR Architecture June 1993 1. Introduction As data communications technologies evolve and user populations grow, the demand for internetworking increases. Internetworks usually proliferate through interconnection of autonomous, heterogeneous networks administered by separate authorities. We use the term "administrative domain" (AD) to refer to any collection of contiguous networks, gateways, links, and hosts governed by a single administrative authority who selects the intra-domain routing procedures and addressing schemes, specifies service restrictions for transit traffic, and defines service requirements for locally- generated traffic. Interconnection of administrative domains can broaden the range of services available in an internetwork. Hence, traffic with special service requirements is more likely to receive the service requested. However, administrators of domains offering special transit services are more likely to establish stringent access restrictions, in order to maintain control over the use of their domains' resources. An internetwork composed of many domains with diverse service requirements and restrictions requires "policy routing" to transport traffic between source and destination. Policy routing constitutes route generation and message forwarding procedures for producing and using routes that simultaneously satisfy user service requirements and respect transit domain service restrictions. With policy routing, each domain administrator sets "transit policies" that dictate how and by whom the resources within its domain should be used. Transit policies are usually public, and they specify offered services comprising: - Access restrictions: e.g., applied to traffic to or from certain domains or classes of users. - Quality: e.g., delay, throughput, or error characteristics. - Monetary cost: e.g., charge per byte, message, or unit time. Each domain administrator also sets "source policies" for traffic originating within its domain. Source policies are usually private, and they specify requested services comprising: - Access restrictions: e.g., domains to favor or avoid in routes. - Quality: e.g., acceptable delay, throughput, or reliability. - Monetary cost: e.g., acceptable session cost. Steenstrup [Page 3]
RFC 1478 IDPR Architecture June 1993 In this document, we describe an architecture for inter-domain policy routing (IDPR), and we provide a set of functions which can form the basis for a suite of IDPR protocols and procedures. 1.1. The Internet Environment The Internet currently comprises over 7000 operational networks and over 10,000 registered networks. In fact, for the last several years, the number of constituent networks has approximately doubled annually. Although we do not expect the Internet to sustain this growth rate, we must provide an architecture for IDPR that can accommodate the Internet five to ten years in the future. According to the functional requirements for inter-autonomous system (i.e., inter-domain) routing set forth in [6], the IDPR architecture and protocols must be able to handle O(100,000) networks distributed over O(10,000) domains. Internet connectivity has increased along with the number of component networks. In the early 1980s, the Internet was purely hierarchical, with the ARPANET as the single backbone. The current Internet possesses a semblance of a hierarchy in the collection of backbone, regional, metropolitan, and campus domains that compose it. However, technological, economical, and political incentives have prompted the introduction of inter-domain links outside of those in the strict hierarchy. Hence, the Internet has the properties of both hierarchical and mesh connectivity. We expect that the Internet will evolve in the following way. Over the next five years, the Internet will grow to contain O(10) backbone domains, most providing connectivity between many source and destination domains and offering a wide range of qualities of service, for a fee. Most domains will connect directly or indirectly to at least one Internet backbone domain, in order to communicate with other domains. In addition, some domains may install direct links to their most favored destinations. Domains at the lower levels of the hierarchy will provide some transit service, limited to traffic between selected sources and destinations. However, the majority of Internet domains will be "stubs", that is, domains that do not provide any transit service for other domains. The bulk of Internet traffic will be generated by hosts in these stub domains, and thus, the applications running in these hosts will determine the traffic service requirements. We expect application diversity encompassing electronic mail, desktop videoconferencing, scientific visualization, and distributed simulation, to list a few. Many of these applications have strict requirements on loss, delay, and throughput. Steenstrup [Page 4]
RFC 1478 IDPR Architecture June 1993 Ensuring that Internet traffic traverses routes that provide the required services without violating domain usage restrictions will be the task of policy routing in the Internet in the next several years. Refer to [1]-[10] for more information on the role of policy routing in the Internet. 2. Approaches to Policy Routing In this section, we provide an assessment of candidate approaches to policy routing, concentrating on the "distance vector" and "link state" alternatives for routing information distribution and route generation and on the "hop-by-hop" and "source specified" alternatives for data message forwarding. The IDPR architecture supports link state routing information distribution and route generation in conjunction with source specified message forwarding. We justify these choices for IDPR below. 2.1. Policy Route Generation We present policy route generation from the distance vector perspective and from the link state perspective. 2.1.1. Distance Vector Approach Distance vector route generation distributes the computation of a single route among multiple routing entities along the route. Hence, distance vector route generation is potentially susceptible to the problems of routing loop formation and slow adaptation to changes in an internetwork. However, there exist several techniques that can be applied during distance vector route generation to reduce the severity of, or even eliminate, these problems. For information on a loop-free, quickly adapting distance vector routing procedure, consult [13] and [14]. During policy route generation, each recipient of a distance vector message assesses the acceptability of the associated route and determines the set of neighboring domains to which the message should be propagated. In the context of policy routing, both of the following conditions are necessary for route acceptability: - The route is consistent with at least one transit policy for each domain, not including the current routing entity's domain, contained in the route. To enable each recipient of a distance vector message to verify consistency of the associated route with the transit policies of all constituent domains, each routing entity should include its domain's identity and transit policies in each acceptable distance vector message it propagates. Steenstrup [Page 5]
RFC 1478 IDPR Architecture June 1993 - The route is consistent with at least one source policy for at least one domain in the Internet. To enable each recipient of a distance vector message to verify consistency of the associated route with the source policies of particular domains, each domain must provide other domains with access to its source policies. In addition, at least one of the following conditions is necessary for route acceptability: - The route is consistent with at least one of the transit policies for the current routing entity's domain. In this case, the routing entity accepts the distance vector message and then proceeds to compare the associated route with its other routes to the destinations listed in the message. If the routing entity decides that the new route is preferable, it updates the distance vector message with its domain's identity and transit policies and then propagates the message to the appropriate neighboring domains. We discuss distance vector message distribution in more detail in section 2.2.1. The route is consistent with at least one of the source policies for the current routing entity's domain. In this case, the routing entity need not propagate the distance vector message but does retain the associated route for use by traffic from local hosts, bound for the destinations listed in the message. The routing entity discards any distance vector message that does not meet these necessary conditions. With distance vector policy route generation, a routing entity may select and store multiple routes of different characteristics, such as qualities of service, to a single destination. A routing entity uses the quality of service information, provided in the transit policies contained in accepted distance vector messages, to discriminate between routes based on quality of service. Moreover, a routing entity may select routes that are specific to certain source domains, provided that the routing entity has access to the source policies of those domains. In the distance vector context, the flexibility of policy route generation afforded by accounting for other domains' transit and source policies in route selection has the following disadvantages: - Each recipient of a distance vector message must bear the cost of verifying the consistency of the associated route with the constituent domains' transit policies. Steenstrup [Page 6]
RFC 1478 IDPR Architecture June 1993 - Source policies must be made public. Thus, a domain must divulge potentially private information. - Each recipient of a distance vector message must bear the potentially high costs of selecting routes for arbitrary source domains. In particular, a routing entity must store the source policies of other domains, account for these source policies during route selection, and maintain source-specific forwarding information. Moreover, there must be a mechanism for distributing source policy information among domains. Depending on the mechanism selected, distribution of source policies may add to the costs paid by each routing entity in supporting source-specific routing. We note, however, that failure to distribute source policies to all domains may have unfortunate consequences. In the worst case, a domain may not learn of any acceptable routes to a given destination, even though acceptable routes do exist. For example, suppose that AD V is connected to AD W and that AD W can reach AD Z through either AD X or AD Y. Suppose also that AD~W, as a recipient of distance vector messages originating in AD Z, prefers the route through AD Y to the route through AD X. Furthermore, suppose that AD W has no knowledge of AD V's source policy precluding traffic from traversing AD Y. Hence, AD W distributes to AD V the distance vector message containing the route WYZ but not the distance vector message containing the route WXZ. AD V is thus left with no known route to AD Z, although a viable route traversing AD W and AD X does exist. 2.1.2. Link State Approach Link state route generation permits concentration of the computation of a single route within a single routing entity at the source of the route. In the policy routing context, entities within a domain generate link state messages containing information about the originating domain, including the set of transit policies that apply and the connectivity to adjacent domains, and they distribute these messages to neighboring domains. Each recipient of a link state message stores the routing information for anticipated policy route generation and also distributes it to neighboring domains. Based on the set of link state messages collected from other domains and on its domain's source and transit policies, a routing entity constructs and selects policy routes from its domain to other domains in the Internet. We have selected link state policy route generation for IDPR for the following reasons: - Each domain has complete control over policy route generation from the perspective of itself as source. Steenstrup [Page 7]
RFC 1478 IDPR Architecture June 1993 - The cost of computing a route is completely contained within the source domain. Hence, routing entities in other domains need not bear the cost of generating policy routes that their domains' local hosts may never use. - Source policies may be kept private and hence need not be distributed. Thus, there are no memory, processing, or transmission bandwidth costs incurred for distributing and storing source policies. 2.2. Routing Information Distribution A domain's routing information and the set of domains to which that routing information is distributed each influence the set of generable policy routes that include the given domain. In particular, a domain administrator may promote the generation of routes that obey its domain's transit policies by ensuring that its domain's routing information: - Includes resource access restrictions. - Is distributed only to those domains that are permitted to use these resources. Both of these mechanisms, distributing restrictions with and restricting distribution of a domain's routing information, can be applied in both the distance vector and link state contexts. 2.2.1. Distance Vector Approach A routing entity may distribute its domain's resource access restrictions by including the appropriate transit policy information in each distance vector it accepts and propagates. Also, the routing entity may restrict distribution of an accepted distance vector message by limiting the set of neighboring domains to which it propagates the message. In fact, restricting distribution of routing information is inherent in the distance vector approach, as a routing entity propagates only the preferred routes among all the distance vector messages that it accepts. Although restricting distribution of distance vector messages is easy, coordinating restricted distribution among domains requires each domain to know other domains' distribution restrictions. Each domain may have a set of distribution restrictions that apply to all distance vector messages generated by that domain as well as sets of distribution restrictions that apply to distance vector messages generated by other domains. Steenstrup [Page 8]
RFC 1478 IDPR Architecture June 1993 As a distance vector message propagates among domains, each routing entity should exercise the distribution restrictions associated with each domain constituting the route thus far constructed. In particular, a routing entity should send an accepted distance vector message to a given neighbor, only if distribution of that message to that neighbor is not precluded by any domain contained in the route. To enable a routing entity to exercise these distribution restrictions, each domain must permit other domains access to its routing information distribution restrictions. However, we expect that domains may prefer to keep distribution restrictions, like source policies, private. There are at least two ways to make a domain's routing information distribution restrictions generally available to other domains: - Prior to propagation of an accepted distance vector message, a routing entity includes in the message its domain's distribution restrictions (all or only those to that apply to the given message). This method requires no additional protocol for disseminating the distribution restrictions, but it may significantly increase the size of each distance vector message. - Each domain independently disseminates its distribution restrictions to all other domains, so that each domain will be able to exercise all other domains' distribution restrictions. This method requires an additional protocol for disseminating the distribution restrictions, and it may require a significant amount of memory at each routing entity for storing all domains' distribution restrictions. We note that a domain administrator may describe the optimal distribution pattern of distance vector messages originating in its domain, as a directed graph rooted at its domain. Furthermore, if all domains in the directed graph honor the directionality and if the graph is also acyclic, no routing loops may form, because no two domains are able to exchange distance vector messages pertaining to the same destination. However, an acyclic graph also means that some domains may be unable to discover alternate paths when connectivity between adjacent domains fails, as we show below. We reconsider the example from section 2.1.1. Suppose that the distance vector distribution graph for AD Z is such that all distance vectors originating in AD Z flow toward AD V. In particular, distance vectors from AD Z enter AD W from AD X and AD Y and leave AD W for AD V. Now, suppose that the link between the AD Z and AD X breaks. AD X no longer has knowledge of any viable route to AD Z, although such a route exists through AD W. To ensure discovery of alternate routes to AD Z during connectivity failures, the distance Steenstrup [Page 9]
RFC 1478 IDPR Architecture June 1993 vector distribution graph for AD Z must contain bidirectional links between AD W and AD X and between AD W and AD Y. 2.2.2. Link State Approach With link state routing information distribution, all recipients of a domain's link state message gain knowledge of that domain's transit policies and hence service restrictions. For reasons of efficiency or privacy, a domain may also restrict the set of domains to which its link state messages should be distributed. Thus, a domain has complete control over distributing restrictions with and restricting distribution of its routing information. A domain's link state messages automatically travel to all other domains if no distribution restrictions are imposed. Moreover, to ensure that distribution restrictions, when imposed, are applied, the domain may use source specified forwarding of its link state messages, such that the messages are distributed and interpreted only by the destination domains for which they were intended. Thus, only those domains receive the given domain's link state messages and hence gain knowledge of that domain's service offerings. We have selected link state routing information distribution for IDPR for the following reasons: - A domain has complete control over the distribution of its own routing information. - Routing information distribution restrictions may be kept private and hence need not be distributed. Thus, there are no memory, processing, or transmission bandwidth costs incurred for distributing and storing distribution restrictions. 2.3. Message Forwarding along Policy Routes To transport data messages along a selected policy route, a routing entity may use either hop-by-hop or source specified message forwarding. 2.3.1. Hop-by-Hop Approach With hop-by-hop message forwarding, each routing entity makes an independent forwarding decision based on a message's source, destination, and requested services and on information contained in the entity's forwarding information database. Hop-by-hop message forwarding follows a source-selected policy route only if all routing entities along the route have consistent routing information and make consistent use of this information when generating and selecting Steenstrup [Page 10]
RFC 1478 IDPR Architecture June 1993 policy routes and when establishing forwarding information. In particular, all domains along the route must have consistent information about the source domain's source policies and consistent, but not necessarily complete, information about transit policies and domain adjacencies within the Internet. In general, this implies that each domain should have knowledge of all other domains' source policies, transit policies, and domain adjacencies. When hop-by-hop message forwarding is applied in the presence of inconsistent routing information, the actual route traversed by data messages not only may differ from the route selected by the source but also may contain loops. In the policy routing context, private source policies and restricted distribution of routing information are two potential causes of routing information inconsistencies among domains. Moreover, we expect routing information inconsistencies among domains in a large Internet, independent of whether the Internet supports policy routing, as some domains may not want or may not be able to store routing information from the entire Internet. 2.3.1.1. A Clarification In a previous draft, we presented the following example which results in persistent routing loops, when hop-by-hop message forwarding is used in conjunction with distance vector routing information distribution and route selection. Consider the sequence of events: - AD X receives a distance vector message containing a route to AD Z, which does not include AD Y. AD X selects and distributes this route as its primary route to AD Z. - AD Y receives a distance vector message containing a route to AD Z, which does not include AD X. AD Y selects and distributes this route as its primary route to AD Z. - AD X eventually receives the distance vector message containing the route to AD Z, which includes AD Y but not AD X. AD X prefers this route over its previous route to AD Z and selects this new route as its primary route to AD Z. - AD Y eventually receives the distance vector message containing the route to AD Z, which includes AD X but not AD Y. AD Y prefers this route over its previous route to AD Z and selects this new route as its primary route to AD Z. Thus, AD X selects a route to AD Z that includes AD Y, and AD Y selects a route to AD Z that includes AD X. Steenstrup [Page 11]
RFC 1478 IDPR Architecture June 1993 Suppose that all domains along the route selected by AD X, except for AD Y, make forwarding decisions consistent with AD X's route, and that all domains along the route selected by AD Y, except for AD X, make forwarding decisions consistent with AD Y's route. Neither AD X's selected route nor AD Y's selected route contains a loop. Nevertheless, data messages destined for AD Z and forwarded to either AD X or AD Y will continue to circulate between AD X and AD Y, until there is a route change. The reason is that AD X and AD Y have conflicting notions of the route to AD Z, with each domain existing as a hop on the other's route. We note that while BGP-3 [8] is susceptible to such routing loops, BGP-4 [9] is not. We thank Tony Li and Yakov Rekhter for their help in clarifying this difference between BGP-3 and BGP-4. 2.3.2. Source Specified Approach With source specified message forwarding, the source domain dictates the data message forwarding decisions to the routing entities in each intermediate domain, which then forward data messages according to the source specification. Thus, the source domain ensures that any data message originating within it follows its selected routes. For source specified message forwarding, each data message must carry either an entire source specified route or a path identifier. Including the complete route in each data message incurs a per message transmission and processing cost for transporting and interpreting the source route. Using path identifiers does not incur these costs. However, to use path identifiers, the source domain must initiate, prior to data message forwarding, a path setup procedure that forms an association between the path identifier and the next hop in the routing entities in each domain along the path. Thus, path setup may impose an initial delay before data message forwarding can begin. We have selected source specified message forwarding for IDPR data messages for the following reasons: - Source specified message forwarding respects the source policies of the source domain, regardless of whether intermediate domains along the route have knowledge of these source policies. - Source specified message forwarding is loop-free, regardless of whether the all domains along the route maintain consistent routing information. Also, we have chosen path identifiers over complete routes, to affect source specified message forwarding, because of the reduced Steenstrup [Page 12]
RFC 1478 IDPR Architecture June 1993 transmission and processing cost per data message. 3. The IDPR Architecture We now present the architecture for IDPR, including a description of the IDPR functions, the entities that perform these functions, and the features of IDPR that aid in accommodating Internet growth. 3.1. IDPR Functions Inter-domain policy routing comprises the following functions: - Collecting and distributing routing information including domain transit policies and inter-domain connectivity. - Generating and selecting policy routes based on the routing information distributed and on the source policies configured or requested. - Setting up paths across the Internet using the policy routes generated. - Forwarding messages across and between domains along the established paths. - Maintaining databases of routing information, inter-domain policy routes, forwarding information, and configuration information. 3.2. IDPR Entities From the perspective of IDPR, the Internet comprises administrative domains connected by "virtual gateways" (see below), which are in turn connected by intra-domain routes supporting the transit policies configured by the domain administrators. Each domain administrator defines the set of transit policies that apply across its domain and the virtual gateways between which each transit policy applies. Several different transit policies may be configured for the intra- domain routes connecting a pair of virtual gateways. Moreover, a transit policy between two virtual gateways may be directional. That is, the transit policy may apply to traffic flowing in one direction, between the virtual gateways, but not in the other direction. Virtual gateways (VGs) are the only connecting points recognized by IDPR between adjacent administrative domains. Each virtual gateway is actually a collection of directly-connected "policy gateways" (see below) in two adjacent domains, whose existence has been sanctioned by the administrators of both domains. Domain administrators may agree to establish more than one virtual gateway between their Steenstrup [Page 13]
RFC 1478 IDPR Architecture June 1993 domains. For example, if two domains are to be connected at two geographically distant locations, the domain administrators may wish to preserve these connecting points as distinct at the inter-domain level, by establishing two distinct virtual gateways. Policy gateways (PGs) are the physical gateways within a virtual gateway. Each policy gateway forwards transit traffic according to the service restrictions stipulated by its domain's transit policies applicable to its virtual gateway. A single policy gateway may belong to multiple virtual gateways. Within a domain, two policy gateways are "neighbors" if they are in different virtual gateways. Within a virtual gateway, two policy gateways are "peers" if they are in the same domain and are "adjacent" if they are in different domains. Peer policy gateways must be able to communicate over intra-domain routes that support the transit policies that apply to their virtual gateways. Adjacent policy gateways are "directly connected" if they are the only Internet addressable entities attached to the connecting medium. Note that this definition implies that not only point-to-point links but also multiaccess networks may serve as direct connections between adjacent policy gateways. Combining multiple policy gateways into a single virtual gateway affords three advantages: - A reduction in the amount of IDPR routing information that must be distributed and maintained throughout the Internet. - An increase in the reliability of IDPR routes through redundancy of physical connections between domains. - An opportunity for load sharing of IDPR traffic among policy gateways. Several different entities are responsible for performing the IDPR functions: - Policy gateways collect and distribute routing information, participate in path setup, forward data messages along established paths, and maintain forwarding information databases. - "Path agents" act on behalf of hosts to select policy routes, to set up and manage paths, and to maintain forwarding information databases. - Special-purpose servers maintain all other IDPR databases as follows: Steenstrup [Page 14]
RFC 1478 IDPR Architecture June 1993 o Each "route server" is responsible for both its database of routing information, including domain connectivity and transit policy information, and its database of policy routes. Also, each route server generates policy routes on behalf of its domain, using entries from its routing information database and source policy information supplied through configuration or obtained directly from the path agents. o Each "mapping server" is responsible for its database of mappings that resolve Internet names and addresses to administrative domains. o Each "configuration server" is responsible for its database of configured information that applies to policy gateways, path agents, and route servers in the given administrative domain. The configuration information for a given domain includes source and transit policies and mappings between local IDPR entities and their Internet addresses. To maximize IDPR's manageability, one should embed all of IDPR's required functionality within the IDPR protocols and procedures. However, to minimize duplication of implementation effort, one should take advantage of required functionality already provided by mechanisms external to IDPR. Two such cases are the mapping server functionality and the configuration server functionality. The functions of the mapping server can be integrated into an existing name service such as the DNS, and the functions of the configuration server can be integrated into the domain's existing network management system. Within the Internet, only policy gateways, path agents, and route servers must be able to generate, recognize, and process IDPR messages. The existence of IDPR is invisible to all other gateways and hosts. Mapping servers and configuration servers perform necessary but ancillary functions for IDPR, and they are not required to execute the IDPR protocols. 3.2.1. Path Agents Any Internet host can reap the benefits of IDPR, as long as there exists a path agent configured to act on its behalf and a means by which the host's messages can reach that path agent. Path agents select and set up policy routes for hosts, accounting for service requirements. To obtain a host's service requirements, a path agent may either consult its configured IDPR source policy information or extract service requirements directly from the host's data messages, provided such information is available in these data messages. Steenstrup [Page 15]
RFC 1478 IDPR Architecture June 1993
RFC 1478 IDPR Architecture June 1993 domain community. By default, this community encompasses all Internet domains. However, the domain administrator may restrict community membership by describing the community as a neighborhood (defined, for example, in terms of domain hops) or as a list of member domains. A group of domain administrators may mutually agree on distribution of their domains' routing information among their domains and hence multilaterally define a domain community. By default, this community encompasses all Internet domains. However, the domain administrators may restrict community membership by describing the community as a list of member domains. In fact, this domain community may serve as a multicast group for routing information distribution. 4.5. Robustness in the Presence of Failures The IDPR architecture possesses the following features that make it resistent to failures in the Internet: - Multiple connections between adjacent policy gateways in a virtual gateway and between peer and neighbor policy gateways across an administrative domain minimize the number of single component failures that are visible at the inter-domain level. - Policy gateways distribute IDPR routing information immediately after detecting a connectivity failure at the inter-domain level, and route servers immediately incorporate this information into their routing information databases. This ensures that new policy routes will not include those domains involved in the connectivity failure. - The routing information database query/response mechanism ensures rapid updating of the routing information database for a previously failed route server following the route server's reconnection to the Internet. - To minimize user service disruption following a failure in the primary path, policy gateways attempt local path repair immediately after detecting a connectivity failure. Moreover, path agents may maintain standby alternate paths that can become the primary path if necessary. - Policy gateways within a domain continuously monitor domain connectivity and hence can detect and identify domain partitions. Moreover, IDPR can continue to operate properly in the presence of partitioned domains. Steenstrup [Page 30]
RFC 1478 IDPR Architecture June 1993 4.5.1. Path Repair Failure of one or more entities on a given policy route may render the route unusable. If the failure is within a domain, IDPR relies on the intra-domain routing procedure to find an alternate route across the domain, which leaves the path unaffected. If the failure is in a virtual gateway, policy gateways must bear the responsibility of repairing the path. Policy gateways nearest to the failure are the first to recognize its existence and hence can react most quickly to repair the path. Relinquishing control over path repair to policy gateways in other domains may be unacceptable to some domain administrators. The reason is that these policy gateways cannot guarantee construction of a path that satisfies the source policies of the source domain, as they have no knowledge of other domains' source policies. Nevertheless, limited local path repair is feasible, without distributing either source policy information throughout the Internet or detailed path information among policy gateways in a domain or in a virtual gateway. We say that a path is "locally repairable" if there exists an alternate route between two policy gateways, separated by at most one policy gateway, on the path. This definition covers path repair in the presence of failed routes between consecutive policy gateways as well as failed policy gateways themselves. A policy gateway attempts local path repair, proceeding in the forward direction of the path, upon detecting that the next policy gateway on a path is no longer reachable. The policy gateway must retain enough of the original path setup information to repair the path locally. Using the path setup information, the policy gateway attempts to locate a route around the unreachable policy gateway. Specifically, the policy gateway attempts to establish contact with either: - A peer of the unreachable policy gateway. In this case, the contacted policy gateway attempts to locate the next policy gateway following the unreachable policy gateway, on the original path. - A peer of itself, if the unreachable policy gateway is an adjacent policy gateway and if the given policy gateway no longer has direct connections to any adjacent policy gateways. In this case, the contacted policy gateway attempts to locate a peer of the unreachable policy gateway, which in turn attempts to locate the next policy gateway following the unreachable policy gateway, on the original path. Steenstrup [Page 31]
RFC 1478 IDPR Architecture June 1993 If it successfully reaches the next policy gateway, the contacted policy gateway informs the requesting policy gateway. In this case, the requesting, contacted, and next policy gateways update their forwarding information databases to conform to the new part of the path. If it does not successfully reach the next policy gateway, the contacted policy gateway initiates teardown of the original path; in this case, the source path agent is responsible for finding a new route to the destination. 4.5.2. Partitions A "domain partition" exists whenever there are at least two entities within the domain that can no longer communicate over any intra- domain route. Domain partitions not only disrupt intra-domain communication but also may interfere with inter-domain communication, particularly when the partitioned domain is a transit domain. Therefore, we have designed the IDPR architecture to permit effective use of partitioned domains and hence maximize Internet connectivity in the presence of domain partitions. When a domain is partitioned, it becomes a set of multiple distinct "components". A domain component is a subset of the domain's entities such that all entities within the subset are mutually reachable via intra-domain routes, but no entities in the complement of the subset are reachable via intra-domain routes from entities within the subset. Each domain component has a unique identifier, namely the identifier of the domain together with the ordinal number of the lowest-numbered operational policy gateway within the domain component. No negotiation among policy gateways is necessary to determine the domain component's lowest-numbered operational policy gateway. Instead, within each domain component, all policy gateway members discover mutual reachability through intra-domain reachability information. Therefore, all members have a consistent view of which is the lowest-numbered operational policy gateway in the component. IDPR entities can detect and compensate for all domain partitions that isolate at least two groups of policy gateways from each other. They cannot, however, detect any domain partition that isolates groups of hosts only. Note that a domain partition may segregate portions of a virtual gateway, such that peer policy gateways lie in separate domain components. Although itself partitioned, the virtual gateway does not assume any additional identities. However, from the perspective of the adjacent domain, the virtual gateway now connects to two separate domain components. Policy gateways use partition information to select routes across virtual gateways to the correct domain components. They also Steenstrup [Page 32]
RFC 1478 IDPR Architecture June 1993 distribute partition information to route servers as part of the IDPR routing information. Thus, route servers know which domains are partitioned. However, route servers do not know which hosts reside in which components of a partitioned domain; tracking this information would require extensive computation and communication. Instead, when a route server discovers that the destination of a requested route is a partitioned domain, it attempts to generate a suitable policy route to each component of the destination domain. Generation of multiple routes, on detection of a partitioned destination domain, maximizes the chances of obtaining at least one policy route that can be used for communication between the source and destination hosts. Steenstrup [Page 33]
RFC 1478 IDPR Architecture June 1993 5. References [1] Rekhter, Y., "EGP and Policy Based Routing in the New NSFNET Backbone", RFC 1092, February 1989. [2] Clark, D., "Policy Routing in Internet Protocols", RFC 1102, May 1989 [3] Braun, H-W., "Models of Policy Based Routing", RFC 1104, June 1989 [4] Leiner, B., "Policy Issues in Interconnecting Networks", RFC 1124, September 1989. [5] Estrin, D., "Requirements for Policy Based Routing in the Research Internet", RFC 1125, November 1989. [6] Little, M., "Goals and Functional Requirements for Inter- Autonomous System Routing", RFC 1126, July 1989. [7] Honig, J., Katz, D., Mathis, M., Rekhter, Y., and Yu, J., "Application of the Border Gateway Protocol in the Internet", RFC 1164, June 1990. [8] Lougheed, K. and Rekhter, Y., "A Border Gateway Protocol 3 (BGP-3)", RFC 1267, October 1991. [9] Rekhter, Y. and Li, T. Editors, "A Border Gateway Protocol 4 (BGP-4)", Work in Progress, September 1992. [10] ISO, "Information Processing Systems - Telecommunications and Information Exchange between Systems - Protocol for Exchange of Inter-domain Routeing Information among Intermediate Systems to Support Forwarding of ISO 8473 PDUs", ISO/IEC DIS 10747, August 1992 [11] Perlman, R., "Network Layer Protocols with Byzantine Robust- ness", Ph.D. Thesis, Department of Electrical Engineering and Computer Science, MIT, August 1988. [12] Estrin, D. and Tsudik, G., "Secure Control of Transit Internet- work Traffic", TR-89-15, Computer Science Department, University of Southern California. [13] Garcia-Luna-Aceves, J.J., "A Unified Approach for Loop-Free Routing using Link States or Distance Vectors", ACM Computer Communication Review, Vol. 19, No. 4, SIGCOMM 1989, pp. 212-223. Steenstrup [Page 34]
RFC 1478 IDPR Architecture June 1993 [14] Zaumen, W.T. and Garcia-Luna-Aceves, J.J., "Dynamics of Distri- buted Shortest-Path Routing Algorithms", ACM Computer Communica- tion Review, Vol. 21, No. 4, SIGCOMM 1991, pp. 31-42.



Back to RFC index

 

 



Sponsered-Sites:

Register domain name and transfer | Cheap webhosting service | Domain name registration

 

 

""