rfc1322.txt
来自「中、英文RFC文档大全打包下载完全版 .」· 文本 代码 · 共 1,376 行 · 第 1/5 页
TXT
1,376 行
where a BR receives from each of its neighbors a vector that contains distances to a set of destinations.]. The path, expressed in terms of the domains (or confederations) traversed so far, is carried in a special path attribute which records the sequence of routing domains through which the reachability information has passed. Suppression of routing loops is implemented via this special path attribute, in contrast to LS and distance vector which use a globally-defined monotonically-increasing metric for route selection [Shin87]. Because PV does not require all routing domains to have homogeneousEstrin, Rekhter & Hotz [Page 15] RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 criteria (policies) for route selection, route selection policies used by one routing domain are not necessarily known to other routing domains. To maintain the maximum degree of autonomy and independence between routing domains, each domain which participates in PV may have its own view of what constitutes an optimal route. This view is based solely on local route selection policies and the information carried in the path attributes of a route. PV standardizes only the results of the route selection procedure, while allowing the selection policies that affect the route selection to be non-standard [Footnote: This succinct observation is attributed to Ross Callon (Digital Equipment Corporation).].3.3 Complexity Given the above description of PV algorithms, we can compare them to LS algorithms in terms of the three complexity parameters defined earlier.3.3.1 Storage Overhead Without any aggregation of routing information, and ignoring storage overhead associated with transit constraints, it is possible to show that under some rather general assumptions the average case RIB storage overhead of the PV scheme for a single TOS ranges between O(N) and O(Nlog(N)), where N is the total number of routing domains ([Rekhter91]). The LS RIB, with no aggregation of routing information, no transit constraints, a single homogeneous route selection policy across all the domains, and a single TOS, requires a complete domain-level topology map whose size is O(N). Supporting heterogeneous route selection and transit policies with hop-by-hop forwarding and LS requires each domain to know all other domains route selection and transit policies. This may significantly increase the amount of routing information that must be stored by each domain. If the number of policies advertised grows with the number of domains, then the storage could become unsupportable. In contrast, support for heterogeneous route selection policies has no effect on the storage complexity of the PV scheme (aside from simply storing the local policy information). The presence of transit constraints in PV results in a restricted distribution of routing information, thus further reducing storage overhead. In contrast, with LS no such reduction is possible since each domain must know every other domain's transit policies. Finally, some of the transit constraints (e.g., path sensitive constraints) can be expressed in a more concise form in PV (see aggregation discussion below). The ability to further restrict storage overhead is facilitated by the PV routing algorithm, where route computation precedes routingEstrin, Rekhter & Hotz [Page 16] RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 information dissemination, and only routing information associated with the routes selected by a domain is distributed to adjacent domains. In contrast, route selection with LS is decoupled from the distribution of routing information, and has no effect on such distribution. While theoretically routing information aggregation can be used to reduce storage complexity in both LS and PV, only aggregation of topological information would yield the same gain for both. Aggregating transit constraints with LS may result in either reduced connectivity or less information reduction, as compared with PV. Aggregating heterogeneous route selection policies in LS is highly problematic, at best. In PV, route selection policies are not distributed, thus making aggregation of route selection policies a non-issue [Footnote: Although a domain's selection policies are not explicitly distributed, they have an impact on the routes available to other domains. A route that may be preferred by a particular domain, and not prohibited by transit restrictions, may still be unavailable due to the selection policies of some intermediate domain. The ability to compute and install alternative routes that may be lost using hop-by-hop routing (either LS of PV) is the critical functionality provided by SDR.]. Support for multiple TOSs has the same impact on storage overhead for both LS and for PV. Potentially the LS FIB may be smaller if routes are computed at each node on demand. However, the gain of such a scheme depends heavily on the traffic patterns, memory size, and caching strategy. If there is not a high degree of locality, severely degraded performance can result due to excessive overall computation time and excessive computation delay when forwarding packets to a new destination. If demand driven route computation is not used for LS, then the size of the FIB would be the same for both LS and PV.Estrin, Rekhter & Hotz [Page 17] RFC 1322 A Unified Approach to Inter-Domain Routing May 19923.3.2 Route Computation Complexity Even if all domains employ exactly the same route selection policy, computational complexity of PV is smaller than that of LS. The PV computation consists of evaluating a newly arrived route and comparing it with the existing one [Footnote: Some additional checks are required when an update is received to insure that a routing loop has not been created.]. Whereas, conventional LS computation requires execution of an SPF algorithm such as Dijkstra's. With PV, topology changes only result in the recomputation of routes affected by these changes, which is more efficient than complete recomputation. However, because of the inclusion of full path information with each distance vector, the effect of a topology change may propagate farther than in traditional distance vector algorithms. On the other hand, the number of affected domains will still be smaller with PV than with conventional LS hop-by-hop routing. With PV, only those domains whose routes are affected by the changes have to recompute, while with conventional LS hop-by-hop routing all domains must recompute. While it is also possible to employ partial recomputation with LS (i.e., when topology changes, only the affected routes are recomputed), "studies suggest that with a very small number of link changes (perhaps 2) the expected computational complexity of the incremental update exceeds the complete recalculation" ([ANSI87-150R]). However these checks are much simpler than executing a full SPF algorithm. Support for heterogeneous route selection policies has serious implications for the computational complexity. The major problem with supporting heterogeneous route selection policies with LS is the computational complexity of the route selection itself. Specifically, we are not aware of any algorithm with less than exponential time complexity that would be capable of computing routes to all destinations, with LS hop-by-hop routing and heterogeneous route selection policies. In contrast, PV allows each domain to make its route selection autonomously, based only on local policies. Therefore support for dissimilar route selection policies has no negative implications for the complexity of route computation in PV. Similarly, providing support for path-sensitive transit policies in LS implies exponential computation, while in PV such support has no impact on the complexity of route computation. In summary, because NR will rely primarily on precomputation of routes, aggregation is essential to the long-term scalability of the architecture. To the extent aggregation is facilitated with PV, so is reduced computational complexity. While similar arguments may be made for LS, the aggregation capabilities that can be achieved with LS are more problematic because of LS' reliance on consistentEstrin, Rekhter & Hotz [Page 18] RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 topology maps at each node. It is also not clear what additional computational complexity will be associated with aggregation of transit constraints and heterogeneous route selection policies in LS.3.3.3 Bandwidth Overhead PV routing updates include fully-expanded information. A complete route for each supported TOS is advertised. In LS, TOS only contributes a factor increase per link advertised, which is much less than the number of complete routes. Although TOSs may be encoded more efficiently with LS than with PV, link state information is flooded to all domains, while with PV, routing updates are distributed only to the domains that actually use them. Therefore, it is difficult to make a general statement about which scheme imposes more bandwidth overhead, all other factors being equal. Moreover, this is perhaps really not an important difference, since we are more concerned with the number of messages than with the number of bits (because of compression and greater link bandwidth, as well as the increased physical stability of links).3.4 Aggregation Forming confederations of domains, for the purpose of consistent, hop-by-hop, LS route computation, requires that domains within a confederation have consistent policies. In addition, LS confederation requires that any lower level entity be a member of only one higher level entity. In general, no intra-confederation information can be made visible outside of a confederation, or else routing loops may occur as a result of using an inconsistent map of the network at different domains. Therefore, the use of confederations with hop-by-hop LS is limited because each domain (or confederation) can only be a part of one higher level confederation and only export policies consistent with that confederation (see examples in Section 2.2). These restrictions are likely to impact the scaling capabilities of the architecture quite severely. In comparison, PV can accommodate different confederation definitions because looping is avoided by the use of full path information. Consistent network maps are not needed at each route server, since route computation precedes routing information dissemination. Consequently, PV confederations can be nested, disjoint, or overlapping. A domain (or confederation) can export different policies or TOS as part of different confederations, thus providing the extreme flexibility that is crucial for the overall scaling and extensibility of the architecture. In summary, aggregation is essential to achieve acceptable complexityEstrin, Rekhter & Hotz [Page 19] RFC 1322 A Unified Approach to Inter-Domain Routing May 1992 bounds, and flexibility is essential to achieve acceptable aggregation across the global, decentralized internet. PV's strongest advantage stems from its flexibility.3.5 Policy The need to allow expression of transit policy constraints on any route (i.e., NR routes as well as SDR routes), by itself, can be supported by either LS or PV. However, the associated complexities of supporting transit policy constraints are noticeably higher for LS than for PV. This is due to the need to flood all transit policies with LS, where with PV transit policies are controlled via restricted distribution of routing information. The latter always imposes less overhead than flooding. While all of the transit constraints that can be supported with LS can be supported with PV, the reverse is not true. In other words, there are certain transit constraints (e.g., path-sensitive transit constraints) that are easily supported with PV, and are prohibitively expensive (in terms of complexity) to support in LS. For example, it is not clear how NR with LS could support something like ECMA-style policies that are based on hierarchical relations between domains, while support for such policies is straightforward with PV. As indicated above, support for heterogeneous route selection policies, in view of its computational and storage complexity, is impractical with LS hop-by-hop routing. In contrast, PV can accommodate heterogeneous route selection with little additional overhead.3.6 Information Hiding PV has a clear advantage with respect to selective information hiding. LS with hop-by-hop routing hinges on the ability of all⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?