Internet DRAFT - draft-giacalone-scored-fair-metric-routing
draft-giacalone-scored-fair-metric-routing
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]
