Internet Draft Network Working Group S. Giacalone INTERNET-DRAFT Predictive Systems Expiration Date: January 2001 Filename: draft-giacalone-scored-fair-metric-routing-00.txt August 2000 Scored Fair Metric Calculation This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract This memo defines a modular metric calculation system termed Scored Fair Metric Calculation (SFMC). SFMC can be integrated with Link State and Distance Vector routing protocols and their extensions [1,4,5,6,7], enabling them to find network paths that support the highest possible number of best metrics across a network. SFMC makes it possible to support and mix large sets of heterogeneous network features and capabilities. SFMC solves many of the issues inherent in routing protocols that attempt to use complex sets of metrics by decoupling raw metric data from the input side of routing protocols. Unlike the past, SFMC regards all metrics all the time, while treating all metrics equally (by default). Additionally, the SFMC architecture provides a simple and flexible interface for extensive manipulation of path selection. Please send comments to ospf@discuss.microsoft.com. Copyright Notice Expires February 2001 [Page 1] Internet Draft Scored Fair Metric Calculation August, 2000 Copyright (C) The Internet Society (2000). All Rights Reserved. Table of Contents TBD Overview While attempts have been made to build routing protocols which are able to compare metrics based on complex sets of network state data such as bandwidth, delay, and reliability there are still significant challenges in constructing protocols that: -Are simple -Treat metrics fairly by regarding all metrics all the time while not permitting some metrics to over-shadow others (metric starvation) -Permit differing (heterogeneous) metric types to be used for simplicity and extensibility In spite of the difficulties related to complex metric comparison in routing protocols, there has been renewed interest in adding the capability to discern more network state and capability data [1,4,5,6,7], than ever before. The goal of SFMC is to allow advanced and complex topological decisions to be made by routing protocols. SFMC is designed to be added to existing and developmental routing protocols (and their extensions) enabling them to use complex heterogeneous metric data simply and fairly. SFMC can be viewed by other protocols as a module. SFMC provides many benefits while removing issues related to previous complex metric usage in routing protocols. SFMC introduces a metric calculation system which takes in heterogeneous state and capability (including metric)data from routing protocols, extensions or elsewhere, pre-compares the data and then outputs (calculates) homogeneous metrics called "SFMC-scores" to path selection (possibly routing) protocols. Protocols must determine the potential set of physical best-Path interfaces (which might be next-hops) before sending data to SFMC for processing. Although SFMC compares metric data, it is more accurately termed a metric calculation system, as opposed to the metric comparison sub- systems found in current routing protocols. SFMC does not alter metric data, it interprets to produce (construct) abstracted metrics for use by routing protocols. When using SFMC, final metric comparison and next hop selection remain a function of the routing protocol. Expires January 2001 [Page 2] Internet Draft Scored Fair Metric Calculation August, 2000 While SFMC can be viewed by other protocols as a module, it is itself based on a modular internal architecture. SFMC scores are derived by comparing sets of metrics of each enabled type from each potential next-hop interface/s in isolated SFMC "rounds". In each SFMC round, the potential interface/s with the best metric/s is/are awarded SFMC point/s. SFMC points can then be tallied, and presented to other protocols as the metrics for use in best-path selection. SFMC is fair to all metrics sent to it, by considering all metrics in all instances, while preventing metric starvation (when very good metrics obscure more balanced paths). SFMC allows differing metric types to be used and metric data types can be advertised in their native format. Note that SFMC does not intend to change the way the routing protocols work; SFMC does not select best paths, it interprets metrics. Diagram of SFMC's relationship to an example protocol: +-+-+-+-+-+-+-+-+-+-+ | routing | | protocol | | | + +-+-+-+-+-+-+-+-+ | | protocol | | | extension |<-- heterogeneous metrics and capabilities-- | | reception |-- >heterogeneous metrics and capabilities-+ | | subsystem | | | +-+-+-+-+-+-+-+-+ | | | SFMC |-- < --------------------------------------+ | | subsystem |-- >homogeneous SFMC scores----------------+ | +-+-+-+-+-+-+-+-+ | | | | | topology | | | selection |-- < --------------------------------------+ | subsystem | +-+-+-+-+-+-+-+-+-+-+ The specific goals of SFMC are to: -Allow new advanced routing protocols to be developed. -Allow routing protocol extensions [1] to find shortest paths through a network based on sets of very granular network engineering information, instead of just cataloging it in a database. -Solve the problems found in the singular metric comparison schemes of current routing protocols Expires January 2001 [Page 3] Internet Draft Scored Fair Metric Calculation August, 2000 Since SFMC is a module in relation to other protocols, it provides an straightforward interface for manipulating metrics (SFMC scores), and therefor path selection. This document also outlines a number of methods for manipulating SFMC scores. Terminology -Good: When used to modify the word metric, good can mean higher or lower value, which ever is more preferable to the routing protocol. -Fair/Fairness: All will be considered, and one device's overwhelmingly "good" value won't win over many moderately "good" values, unless specifically configured to do so. -Next-hop: Can mean either the interface of the first hop towards the destination or intermediate interfaces, depending on how the routing protocol selects topology. For example Distance Vector protocols only understand destination-first (next) hop tupples. However, using Link State protocols, it may be possible to determine the best path interface from a set of intermediate next-hops. Issues with existing complex metric mechanisms There are numerous issues related to the use of current routing protocol metric comparison systems. This section outlines those issues, so that the benefits of Scored Fair Metric Calculation can be clearly defined in the subsequent section/s. Preference based mechanisms In routing protocols that use preference based metric mechanisms, some metrics are considered before others in predefined order. Only when metrics result in a tie are other "lower-level" metrics considered. This predefined ordering leads to some metrics not being considered at all. For (simple) example assume that we desire to find the best (lowest) delay and (highest) bandwidth path to a particular destination. Further assume that delay has consideration priority over bandwidth in our hypothetical metric mechanism. In this example, we would determine our path solely on delay (unless there was a tie) while ignoring bandwidth, which is "unfair" and undesirable. Example of device using a Preference based routing protocol (all metrics are arbitrary): Device A interface metrics Delay = 9 Banwidth = 150 \/ +-+-+-+-+-+-+ | Expires January 2001 [Page 4] Internet Draft Scored Fair Metric Calculation August, 2000 ----| Device A |---| | +-+-+-+-+-+-+ | +-+-+-+-+-+-+ | | |Calculating|---Network/s |Destination | Device | | | +-+-+-+-+-+-+ | +-+-+-+-+-+-+ | ----| Device B |---| +-+-+-+-+-+-+ | /\ Device B interface metrics Delay = 10 Banwidth = 200 In this diagram, Device A would be chosen to complete the shortest path, with no regard to either device's Bandwidth. Composite based mechanisms In routing protocols that use preference based metric mechanisms metrics data is mathematically combined into a single numerical value before consideration. The use of mathematical composite (combined) metrics presents issues which make it undesirable: -Firstly, in composite based mechanisms all metrics must be comprised of a mathematical compatible data type. For example, to determine topology based on both delay and bandwidth, a similar integer must be used for both metrics, as it is not possible to directly sum 1540Mbps and 10ms. A logical solution for making differing metrics mathematically compatible, is to convert them to an integer. For example, 1 to 255 with 255 as the best metric. After metrics are conversed to common integers, they can be added to form a composite of the individual metrics. The requirement for metrics to use mathematically compatible values presents a number of sub- issues: -Since metrics are combined into compatible metric numbers, the definition of "best" must be the same for all metrics. For example, the LOWER delay metrics (which are better)and HIGHER bandwidth metrics (which are better) might both be represented as 255 (the higher and better number. In this scenario, it's at the least confusing to represent lower delay values with a higher metric. Conversely, the lowest delay and highest bandwidth might both be represented as 1. In this scenario, it's confusing to represent higher bandwidth values with a lower metric. -The need to convert state values into generic numbers obscures the true state of the network, as native states are not easily accessible. Expires January 2001 [Page 5] Internet Draft Scored Fair Metric Calculation August, 2000 -Secondly, when mathematically compatible metrics are combined into composites, metric "starvation" becomes possible. Consider a scenario where device A has a single overwhelmingly "good" metric (Bandwidth) let say 255, but device B has two moderately "good" metrics (delay and jitter) lets say 90 and 90. In this scenario, device A is chosen as the shortest path, even though device B has better over-all state. This example represents the starvation of device B's metrics (where 255 is best): Device A interface metrics: Delay = 10/255 Jitter = 10/255 Bandwidth = 255/255 Total = 275 \/ +-+-+-+-+-+-+ | ----| Device A |---| | +-+-+-+-+-+-+ | +-+-+-+-+-+-+ | | |Calculating|---Network/s |Destination | Device | | | +-+-+-+-+-+-+ | +-+-+-+-+-+-+ | ----| Device B |---| +-+-+-+-+-+-+ | /\ Device B interface metrics: Delay = 90 Jitter = 90 Bandwidth = 90 Total = 270 Diagram representing "metric starvation", in which device A's bandwidth metric unfairly obscures device B's better over all metric suite. While metric starvation may be more critical in link-state protocols, it is also apparent in distance vector protocols. SFMC Benefits SFMC has numerous benefits, including: -It is simple -Providing a modular system for calculating (not only comparing) metrics (SFMC scores) based on very complex sets of advanced state data. SFMC an intermediary between raw metrics and protocols. -It can be used with many existing and developmental protocols, Expires January 2001 [Page 6] Internet Draft Scored Fair Metric Calculation August, 2000 with minimal modification to those protocols -Decoupling metric semantics from the metric (SFMC score) presented to protocols. -Metrics are not converted into mathematically compatible integers, as they do not need to be combined into composite metrics. -Allowing routing protocols, and even their metric enhancements, to continue to be used. This includes features such as variance [7], equal-cost-multi-path (ECMP), and any other routing protocol feature that does not effect the construction metric data. -Comparing all desired metrics, even when ties are present. SFMC is much more fair than preference based metric calculation mechanisms). -Allowing heterogeneous metrics data types and semantics. SFMC can compare heterogeneous metrics and interpret them to provide a single homogeneous metric (SFMC score) to protocols for topological selection. -It eliminates metric starvation. SFMC is designed to provide a better score to a potential next-hop which has the best metric suite, instead of one which has a small number of extremely good metrics. Since SFMC prefers next-hops with the best mix of desired metrics, it is much more fair than composite based schemes. -SFMC provides a logical step for the inclusion of metric and score tuning features. Even though SFMC prefers next-hops with the best mix of desired metrics, it includes features to influence scoring, and therefor routing. -Since SFMC does not attempt to make metric data compatible, native network state data is easily accessed from multiple points in the network. -It eliminates confusion resulting from metric conversion when metrics with lower is better metric semantics are converted into mathematically compatible integers with higher is better semantics. -It reduces resource consumption SFMC Basic Functionality Expires January 2001 [Page 7] Internet Draft Scored Fair Metric Calculation August, 2000 SFMC is a modular system for calculating advanced metrics. It is a module to other protocols, and is within itself, modular. SFMC useae may be added as a configurable option. The possible use/assignment of protocol "options bits" is TBD. Heterogeneous metric data is handed to SFMC which then makes relativistic interoperations of the data between interfaces to produce homogeneous scores, with which protocols (can) use to make topological selections. When data is sent to SFMC, SFMC must prune any interface that does not support desired capabilities. Note that this means that SFMC must not consider any metric for interfaces which do not support desired features. However, SFMC MUST consider all available metrics from interfaces that do not support some number of desired metrics. For example, if a best path based on support for RED capability, lowest delay and highest bandwidth is desired, SFMC must prune any interface not supporting RED. However, if an interface does not support the lowest delay metric, SFMC must still consider it (as long as is supports RED). Thereafter, SFMC begins a multi-stage (modular) relativistic process of comparing metrics and building score(s). The metric comparison process is supported by the construction of an SFMC table, which may include metric (and perhaps COS and Color), device ID, Interface ID, and SMFC points. The SFMC table relates metrics of the same type across a common set of interfaces, allowing relative comparison between those metrics. SFMC can then award points to the interface/s with the best metric/s for each related set. After SFMC compares a metric type-set, it moves on to the next set of metrics. When no more metric-type-sets exist, SFMC tabulates points to build SFMC scores. Obviously, SFMC must then send scores to the routing protocol for consideration in building topology. SFMC should work as efficiently and effectively as existing metric comparison systems in simple scenarios, but as complexity builds the benefits of SFMC become greater. Note that SMFC relies on actual metric data within the delay pair, and not a generic representation (i.e. composite metric). SFMC SCORES MAY BE USED BY THE ROUTING PROTOCOL TO MAKE TOPOLIGAL DECISIONS. There are no constraints in ordering the sets of specific metric types in the SFMC table. When metrics result in a tie, tied scores are sent to the protocol using SFMC. That protocol will determine how to the handle equal cost metrics (the scores). Note that even when metrics tie, subsequent metrics ARE considered by SFMC. Expires January 2001 [Page 8] Internet Draft Scored Fair Metric Calculation August, 2000 SFMC examples Metric values in all examples are arbitrary. In these examples, assume an arbitrary routing protocol. Note the use of native metric data types. Simple Example of SFMC To demonstrate a simple scenario using SFMC, assume that we want to calculate the best delay path between the calculating router and the destination network. Device A interface metrics: Delay = 10ms \/ +-+-+-+-+-+-+ | ----| Device A |---| | +-+-+-+-+-+-+ | +-+-+-+-+-+-+ | | |Calculating|---Network/s |Destination | Device | | | +-+-+-+-+-+-+ | +-+-+-+-+-+-+ | | ----| Device B |---| | +-+-+-+-+-+-+ | | /\ | Device B interface metrics: | Delay = 15ms | | \/ Calculating Device's Corresponding SFMC Table: Device A Device B Point|Metric|Metric | Point|Metric|Metric | |Type | | |Type | | - - | - - | - - | - - | - - | - - | 1 |Delay |10ms | 0 |Delay |15ms | - - | - - | - - | - - | - - | - - | Score 1 | | | 0 | | | In this simple example, SFMC prunes interfaces which don't support desired capabilities. However, in this example there are no desired capabilities, so each interface will considered. Next, in SFMC round 1, SFMC compares each delay metric, and awards an SFMC point to the interface with the best metric/s (Device A in this case, as the delay is lower). Since there was only one metric sent to SFMC, there is only a single SFMC round. Expires January 2001 [Page 9] Internet Draft Scored Fair Metric Calculation August, 2000 Finally, SFMC sums the points awarded during the metric comparison rounds (there was only one round in this case), a sends that data to the routing protocol. In this example device A has a better SFMC score, and most likely it would be chosen as the best path by the routing protocol. More Complex Example of SFMC To demonstrate a more complex scenario of SFMC operation, assume that we want to calculate the best delay, jitter, bandwidth and Current Average Queue depth path between the calculating router and the destination network. Further assume each device has two input interfaces with differing states: Device A interface metrics: Interface 1 Interface 2 Delay = 8ms Delay = 10ms Jitter = 20ms Jitter = 19ms Bandwidth = 100Mbps Bandwidth = 100Mbps Queue Depth = 10KB Queue Depth = 10KB Interface 1 \/ ---- +-+-+-+-+-+-+ | | | Device A |---| | --- +-+-+-+-+-+-+ | || /\ | || Interface 2 | || | +-+-+-+-+-+-+ || | |Calculating|---Network/s |Destination | Device | || | +-+-+-+-+-+-+ || | || Interface 1 | || \/ | | --- +-+-+-+-+-+-+ | | | Device B |---| ---- +-+-+-+-+-+-+ | /\ Interface 2 Device B interface metrics: Interface 1 Interface 2 Delay = 3ms Delay = 2ms Jitter = 10ms Jitter = 11ms Bandwidth = 1000Mbps Bandwidth = 1000Mbps Queue Depth = 1KB Queue Depth = NA Expires January 2001 [Page 10] Internet Draft Scored Fair Metric Calculation August, 2000 Calculating Device's Corresponding SFMC Table (table split into sections for pagination only): Device A Interface 1 Interface 2 Point|Metric |Metric |Point|Metric |Metric | |Type | | |Type | | - - | - - - - | - - - | - - | - - - - | - - - | 0 |Delay |8ms | 0 |Delay |10ms | - - | - - - - | - - - | - - | - - - - | - - - | 0 |Jitter |20ms | 0 |Jitter |19ms | - - | - - - - | - - - | - - | - - - - | - - - | 0 |Bandwidth |100mbps | 0 |Bandwidth |100Mbps | - - | - - - - | - - - | - - | - - - - | - - - | 0 |Queue De. |10KB | 0 |Queue De. |10KB | - - | - - - - | - - - | - - | - - - - | - - - | Score 0 | | | 0 | | | Device B Interface 1 Interface 2 Point|Metric |Metric |Point|Metric |Metric | |Type | | |Type | | - - | - - - - | - - - | - - | - - - - | - - - | 0 |Delay |3ms | 1 |Delay |2ms | - - | - - - - | - - - | - - | - - - - | - - - | 1 |Jitter |10ms | 0 |Jitter |11ms | - - | - - - - | - - - | - - | - - - - | - - - | 1 |Bandwidth |1000mbps| 1 |Bandwidth |1000Mbps| - - | - - - - | - - - | - - | - - - - | - - - | 1 |Queue De. |1 KB | 0 |Queue De. |NA | - - | - - - - | - - - | - - | - - - - | - - - | Score 3 | | | 2 | | | In this example the SFMC process is more complex than the previous example and therefor longer: As always, SFMC prunes interfaces which don't support desired capabilities. However, in this example there are no desired capabilities, so each interface will considered. In the first metric comparison, called round 1, SFMC compares delay metrics (and only delay metrics) across the (4) interfaces residing on each potential next hop node, of which there are two. In this comparison, interface 2 of device B is awarded a point, as it has the lowest delay. After delay metric comparison, next moves on to round 2 (there are no comparison ordering constraints). In round 2, jitter metrics (only) are compared across the (4) interfaces residing on each potential Expires January 2001 [Page 11] Internet Draft Scored Fair Metric Calculation August, 2000 next hop node. In this comparison, interface 1 of device B is awarded a point, as it has the most tightly constrained Jitter metric. In SFMC round 3, only bandwidth metrics are compared across the (4) interfaces residing on each potential next hop node. In this round, , interface 1 AND 2 of device B are awarded a point, as they tie for the highest bandwidth. As queue depth metrics are next in the table, SFMC compares them across the (4) interfaces residing on each potential next hop node. In this comparison, interface 1 of device B is awarded a point, as it has the smallest current average depth. Note in this round that SFMC treats interfaces that do not support specific metric types as having an arbitrarily "poor" metric. The final step in this example is for SFMC to sum each interface's SFMC points into a decoupled (metric-independent) SFMC score. This score is then presented to other protocols (routing protocols and extensions) as metric data. From the SFMC scores, which are now used as metrics, topology decisions can be made based on best metric/s. Example of Metric Fairness (Combating Metric-Starvation) This example demonstrates SFMC's default behavior when presented with metrics from an interface (or device) that would be cause metric starvation in other metric schemes. In this example, network administrators desire the best path between the calculating device and the destination network based on delay, bandwidth, jitter and queue depth. However, its clear the device A has overwhelmingly "good" bandwidth; which in other protocols would force device A to become the next hop in the path. SFMC allows all metrics (delay, bandwidth, jitter and queue depth) to be considered equally and fairly (by default). Device A interface metrics: Delay = 10ms Jitter = 10ms Bandwidth = 1000Mbps Queue Depth = 1KB \/ +-+-+-+-+-+-+ | ----| Device A |---| | +-+-+-+-+-+-+ | +-+-+-+-+-+-+ | | |Calculating|---Network/s |Destination | Device | | | +-+-+-+-+-+-+ | +-+-+-+-+-+-+ | | ----| Device B |---| | +-+-+-+-+-+-+ | | /\ Expires January 2001 [Page 12] Internet Draft Scored Fair Metric Calculation August, 2000 | Device B interface metrics: | Delay = 9ms | Jitter = 9ms | Bandwidth = 100Mbps | Queue Depth = .5KB | | \/ Calculating Device's Corresponding SFMC Table: Device A Device B Interface 1 Interface 1 Point|Metric |Metric |Point|Metric |Metric | |Type | | |Type | | - - | - - - - | - - - | - - | - - - - | - - - | 0 |Delay |10ms | 1 |Delay |5ms | - - | - - - - | - - - | - - | - - - - | - - - | 0 |Jitter |10ms | 1 |Jitter |5ms | - - | - - - - | - - - | - - | - - - - | - - - | 1 |Bandwidth |1000mbps| 0 |Bandwidth |155Mbps | - - | - - - - | - - - | - - | - - - - | - - - | 0 |Queue De. |1 KB | 1 |Queue De. |.5KB | - - | - - - - | - - - | - - | - - - - | - - - | Score 1 | | | 3 | | | During the SFMC process for this example, Device A is awarded a point for it's highest bandwidth. Device B is awarded points for lower delay, jitter, and queue depth. Note that even though device A's bandwidth ratio is much higher than any metric ratio in which device B wins, device B ) has a better SFMC score as it supports "more" best metrics and should therefor be selected by the routing protocol as the best path. SFMC Tuning Features Since SFMC allows metric calculation and path selection to be decoupled, all metrics are treated extremely fairly and default SFMC operation may not be optimal. A major benefit of SFMC's architecture is the simple and flexible interface it provides for extensive manipulation of path selection. This section outlines a number of methods which permit the granular control of SFMC operation. SFMC tuning features allow: -Weight to be placed on metric type- Which metric is most important? -Static constraint weighting- What ranges of metric values are most important? -Average constraint weighting- What relative ranges of metric values Expires January 2001 [Page 13] Internet Draft Scored Fair Metric Calculation August, 2000 are most important? -Variance- How much "worse" than the "best" metric is acceptable? -Constraint- What basic ranges of values are acceptable? It might be desirable to artificially manipulate the default score assigned to the interface/s with the best metric/s in a set. Changing the awarded SFMC points for a metric points would change that metric's influence in SFMC scoring. There are several methods through which varying SFMC scoring effects can be achieved. Note that all of these scoring enhancements operate at and manipulate SFMC scoring rounds. Static Metric Type Weighting Using Static Metric Type Weighting, the score of interface/s within a metric certain type is increased based on the type of metric. This is a simple method for assigning relative value for inter-metric comparison. Note that this is an enhancement of the scoring round at the metric level. For example: -Determine the best interface for a certain metric type. However, instead of assigning one SFMC point to that interface assign X number of points. Put differently -When comparing the delay metric between a set of routers, it might be beneficial to award the router with the lower delay two SFMC points (instead of one). Static Constraint Score Weighting Using Static Score Weighting, the score of interface/s within a certain metric type is increased based on a static range table of constraints. This is a simple method for assigning relative value for intra-metric comparison. Note that this is an enhancement of the scoring round at the metric level. For example: -If delay is between 0 and 10ms then award 2 SFMC points -If delay is between 10 and 20ms then award 1 SFMC points -Else award no points Averaged Delta Constraint Score Weighting Expires January 2001 [Page 14] Internet Draft Scored Fair Metric Calculation August, 2000 Using Averaged Delta Constraint Score Weighting, the score of the interface/s with the best metric/s of a certain type is/are automatically increased based on their relationship to other interfaces. This method averages each interface's metric with the others in a set, awarding numbers of points based on percentage. Note that Averaged Delta Score Weighting is an enhancement of the scoring round for a metric type. For example, if four interfaces have delay metrics of: -50ms (Interface 1) -50ms (Interface 2) -25ms (Interface 3) -10ms (Interface 4) Then calculate total delay (which is 135ms). Then average the interface delays: -Interface 1 = 37% = 0 POINTS -Interface 2 = 37%= 0 POINTS -Interface 3 = 18.5%= 1 POINT -Interface 4 = 7% = 2 POINTS Then compare to percentages to scoring table: -If between 0% and 10% then award 2 SFMC points -If between 10% and 20% then award 1 SFMC points -Else award no points Therefor in this example: -Interface 1 would be scored 0 POINTS -Interface 2 would be scored 0 POINTS -Interface 3 would be scored 1 POINT -Interface 4 would be scored 2 POINTS Note that the calculations in this example could be reversed for metrics in which higher values are "better". Variance Constraint Score Weighting In Variance Constraint Score Weighting, the score of the interface/s with the best metric/s of a certain type is/are automatically increased based on their relationship to interfaces with the best metric. This method determines the interface with the best metric in a set, and then awards SFMC points to it and all other interfaces within a configurable range. Using the delay example again, if four interfaces have delay metrics of: Expires January 2001 [Page 15] Internet Draft Scored Fair Metric Calculation August, 2000 -50ms (Interface 1) -50ms (Interface 2) -25ms (Interface 3) -10ms (Interface 4) -Then determine the interface with the best delay (which is interface 4). Award points to that interface and any interface within a configurable range (which might be +20ms or 14.8%) -Interface 1 = 0 POINTS -Interface 2 = 0 POINTS -Interface 3 = 1 POINT (as it is less the best metric plus 20ms) -Interface 4 = 1 POINT (as it is best) Note that the calculations in this example could be reversed for metrics in which higher values are "better". Constraint Based Scoring In Constraint Based SFMC Scoring only metrics within certain bounds are awarded points. Using the delay example again, if four interfaces have delay metrics of: -50ms (Interface 1) -50ms (Interface 2) -25ms (Interface 3) -10ms (Interface 4) -Then award points to only interfaces with delay lower than 30ms. -Interface 1 = 0 POINTS -Interface 2 = 0 POINTS -Interface 3 = 1 POINT (less than 30ms) -Interface 4 = 1 POINT (less than 30ms) 6 Acknowledgements 7 References [1] Giacalone, S., "Network Engineering Extensions to OSPFv3" work in progress (independent Internet Draft). [2] Moy, J., "OSPF Version 2", RFC 2328, April 1998 [3] Coltun, R., Moy, J., "OSPF for IPv6" RFC 2740, December 1999 Expires January 2001 [Page 16] Internet Draft Scored Fair Metric Calculation August, 2000 [4] Katz, D., Yeung, D, "Traffic Engineering Extensions to OSPF", internet Draft, April 2000 [5] Awduche, D., et al, "Requirements for Traffic Engineering Over MPLS, work in progress. [6] Luciani, J., Rajagopalan, B., Awduche, D., Cain, B., Jamoussi, B., " IP over Optical Networks - A Framework", work in progress. [7] Kompella, K., Rekhter, Y., Awduche, D., Hannan, A., Hjalmtysson, G., Lawrence, J., Okamoto, S., Basak, D., Bernstein, G., Drake, J., Margalit, N., Stern, E., "Extensions to IS-IS/OSPF and RSVP in support of MPL(ambda)S", work in progress. [8] Cisco Systems, "Internetwork Design Guide", February 1996 [9] Cisco Systems, "MPLS Traffic engineering", online, http://www.cisco.com/univercd/cc/td/doc/product/software /ios120/120newft/120limit/120s/120s8/te_1208s.htm#xtocid2395327 A Compatibility SFMC is a modular system that can be integrated with developmental and existing routing protocols and extensions. SFMC can inter-operate with both Link-State and Distance Vector protocols. Devices using a topology selection protocol which in turn relies on SFMC will, in all likelihood, view the network differently than devices which use topology selection protocol with more simple metric calculation mechanisms. Therefor, it may be necessary that all devices in a network either use, or don't use, an SFMC based topology selection protocol at a given time. A.1 Usage in direct metric relationship (lower metric-better) protocols This memo assumes that routing protocols consider higher metrics as "better" metrics. In the event that a routing protocol considers a lower metric as "better" there are two alternatives. Firstly, the routing protocol can be modified to work with the specification in this draft. Secondly, SFMC can be modified to award points to interfaces that do NOT posses the "best" metric in a set. In this alternative, SFMC would send lower scores for interfaces with better over all metrics. Note that this alternative might require some default point allocation, and modification of SFMC tuning features. A.2 SFMC in Distance Vector Protocols Expires January 2001 [Page 17] Internet Draft Scored Fair Metric Calculation August, 2000 This memo assumes SFMC use with Link-State protocols. However, there does not appear to be any issue with using SFMC with Distance Vector protocols. The most prevalent change when using SFMC with Distance Vector protocols would be that the metrics handed to SFMC would be metrics for an entire path, not hop by hop metrics. Basic SFMC operation will be unchanged. A.3 Usage with Resource Class/Color It is assumed that metric data will be sent into SFMC on a per interface and PER RESOURCE CLASS/COLOR basis. In this case SFMC would operate normally, but now for each resource class/color (separately). A.4 Usage with SRLG Shared Risk Link Groups may be handled in a number of ways: Firstly if a static SRLG is configured, then that SRLG is treated as a capability in SFMC. For example, if SRLG 1 is configured, SFMC can either include or exclude the device/interface. Secondly, SFMC may (only) compare device/interfaces with the same SRLG attribute, sending SFMC scores to the routing protocol for those device/interfaces. Other device/interfaces may be compared separately. Note that this might require extending SFMC. Thirdly, the routing protocol can handle SRLG, by determining what device/interface data to send to SFMC. A.5 Usage with existing routing protocol enhancements SFMC should not effect the basic operation (the premise) of path selection enhancements in existing routing protocols. This is because SFMC calculates metrics (scores) after interpreting raw metrics. The routing protocol continues to make final next hop/best path selection. There are also enhancements to allow Link-State protocols to operate over MPLS [9]. SFMC does not appear to over lap with these extensions, and may enhance them. A.6 Interoperation with OSPF A requirement of SFMC is that the routing protocol provide raw metric data pertaining to sets of potential best path interfaces at either the first or every hop towards the destination. Whether potential Expires January 2001 [Page 18] Internet Draft Scored Fair Metric Calculation August, 2000 best path interfaces can be discerned at only the first hop or each hop towards a destination depends on the routing protocol. A potential point at which SFMC and OSPF can interact is defined in [2], section 16.1.2 (d). But because of the semantics of OSPF's operation in this section, it may be necessary, to: -Have OSPF add (sum)the metrics for each metric type across each candidate path. In this scenario, SFMC would run once (one round for each metric type) as it does for Distance Vector protocols. -Provide all metrics for each hop for each candidate path. In this case SFMC would run as specified in this document, but the method for correlating hop by hop metrics to each other is TBD. It may also be possible to use SFMC in other ways with OSPF. This area should be further investigated. The most optimal method for interworking SFMC with OSPF would be if it was possible to compare potential best-path-interfaces at each hop across the network (towards the destination). For example, SFMC should operate optimally when metric sets are compared at the first hop set of interfaces, the second set, and so on. However, this method of SFMC interoperation may require changes to OSPF itself. B Security Considerations SFMC does not appear to provide risk in addition to that already present in routing protocols to which it may be applied. C Authors' Addresses Spencer Giacalone Predictive Systems, Inc. 25a Vreeland Road Florham Park, NJ 07932 Phone: +1 (973) 301-5695 EMail: spencer.giacalone@predictive.com D Full Copyright Statement Copyright (C) The Internet Society (2000). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this Expires January 2001 [Page 19] Internet Draft Scored Fair Metric Calculation August, 2000 document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Expires January 2001 [Page 20]