< draft-guerin-qos-routing-ospf-04.txt   draft-guerin-qos-routing-ospf-05.txt >
Internet Engineering Task Force G.Apostolopoulos/R. Guerin/S. Kamat Internet Engineering Task Force G.Apostolopoulos/R. Guerin/S. Kamat
INTERNET DRAFT IBM/UPenn/IBM INTERNET DRAFT IBM/UPenn/IBM
A. Orda/T. Przygienda/D. Williams A. Orda/T. Przygienda/D. Williams
Technion/Lucent/IBM Technion/Lucent/IBM
23 December 1998 14 April 1998
QoS Routing Mechanisms and OSPF Extensions QoS Routing Mechanisms and OSPF Extensions
draft-guerin-qos-routing-ospf-04.txt draft-guerin-qos-routing-ospf-05.txt
Status of This Memo Status of This Memo
This document is an Internet-Draft. Internet-Drafts are working This document is an Internet-Draft and is in full conformance with
documents of the Internet Engineering Task Force (IETF), its areas, all provisions of Section 10 of RFC2026.
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts. 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 Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at and may be updated, replaced, or obsoleted by other documents at
any time. It is inappropriate to use Internet- Drafts as reference any time. It is inappropriate to use Internet- Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
To view the entire list of current Internet-Drafts, please check The list of current Internet-Drafts can be accessed at
the "1id-abstracts.txt" listing contained in the Internet-Drafts
Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern http://www.ietf.org/ietf/1id-abstracts.txt
Europe), ftp.nic.it (Southern Europe), munnari.oz.au (Pacific Rim),
ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Abstract Abstract
This memo describes extensions to the OSPF [Moy98] protocol to This memo describes extensions to the OSPF [Moy98] protocol to
support QoS routes. The focus of this document is on the algorithms support QoS routes. The focus of this document is on the algorithms
used to compute QoS routes and on the necessary modifications to OSPF used to compute QoS routes and on the necessary modifications to OSPF
to support this function, e.g., the information needed, its format, to support this function, e.g., the information needed, its format,
how it is distributed, and how it is used by the QoS path selection how it is distributed, and how it is used by the QoS path selection
process. Aspects related to how QoS routes are established and process. Aspects related to how QoS routes are established and
managed are also briefly discussed. The goal of this document is managed are also briefly discussed. The goal of this document is
skipping to change at page 5, line 19 skipping to change at page 5, line 19
A last aspect of concern regarding the introduction of QoS routing, A last aspect of concern regarding the introduction of QoS routing,
is to control the overhead associated with the additional link is to control the overhead associated with the additional link
state updates caused by more frequent changes to link metrics. state updates caused by more frequent changes to link metrics.
The goal is to minimize the amount of additional update traffic The goal is to minimize the amount of additional update traffic
without adversely affecting the performance of path selection. In without adversely affecting the performance of path selection. In
Section 2.2, we present a brief discussion of various alternatives Section 2.2, we present a brief discussion of various alternatives
that trade accuracy of link state information for protocol overhead. that trade accuracy of link state information for protocol overhead.
Potential enhancements to the path selection algorithm, which seek Potential enhancements to the path selection algorithm, which seek
to (directly) account for the inaccuracies in link metrics, are to (directly) account for the inaccuracies in link metrics, are
described in [GOW97], while a comprehensive treatment of the subject described in [GOW97], while a comprehensive treatment of the subject
can be found in [GO97, LO]. In Section 4, we also describe the can be found in [GO97, LO98]. In Section 4, we also describe the
design choices made in a reference implementation, to allow future design choices made in a reference implementation, to allow future
extensions and experimentation with different link state update extensions and experimentation with different link state update
mechanisms. mechanisms.
The rest of this document is structured as follows. In Section 2, The rest of this document is structured as follows. In Section 2,
we describe the general design choices and mechanisms we rely we describe the general design choices and mechanisms we rely
on to support QoS request. This includes details on the path on to support QoS request. This includes details on the path
selection metrics, link state update extensions, and the path selection metrics, link state update extensions, and the path
selection algorithm itself. Section 3 focuses on the specific selection algorithm itself. Section 3 focuses on the specific
extensions that the OSPF protocol requires, while Section 4 describes extensions that the OSPF protocol requires, while Section 4 describes
skipping to change at page 11, line 25 skipping to change at page 11, line 25
vertex corresponding to the router where the algorithm is being run, vertex corresponding to the router where the algorithm is being run,
i.e., the computing router, is denoted as the ``source node'' for the i.e., the computing router, is denoted as the ``source node'' for the
purpose of path selection. The algorithm proceeds to pre-compute purpose of path selection. The algorithm proceeds to pre-compute
paths from this source node to all possible destination networks and paths from this source node to all possible destination networks and
for all possible bandwidth values. At each (hop count) iteration, for all possible bandwidth values. At each (hop count) iteration,
intermediate results are recorded in a QoS routing table, which has intermediate results are recorded in a QoS routing table, which has
the following structure: the following structure:
The QoS routing table: The QoS routing table:
- a Kx H matrix, where K is the number of destinations (vertices - a KxH matrix, where K is the number of destinations (vertices
in the graph) and H is the maximal allowed (or possible) number in the graph) and H is the maximal allowed (or possible) number
of hops for a path. of hops for a path.
- The (n;h) entry is built during the hth iteration (hop count - The (n;h) entry is built during the hth iteration (hop count
value) of the algorithm, and consists of two fields: value) of the algorithm, and consists of two fields:
* bw: the maximum available bandwidth, on a path of at most h * bw: the maximum available bandwidth, on a path of at most h
hops between the source node (router) and destination node hops between the source node (router) and destination node
n; n;
skipping to change at page 20, line 7 skipping to change at page 20, line 7
normal administrative cost provided to it and compute spanning trees normal administrative cost provided to it and compute spanning trees
with a ``normal'' Dijkstra. The effect of a heavily congested link with a ``normal'' Dijkstra. The effect of a heavily congested link
advertising numerically very low cost could be disastrous in such advertising numerically very low cost could be disastrous in such
a scenario. It would raise the link's attractiveness for future a scenario. It would raise the link's attractiveness for future
traffic instead of lowering it. Evidence that such considerations traffic instead of lowering it. Evidence that such considerations
are not speculative, but similar scenarios have been encountered, can are not speculative, but similar scenarios have been encountered, can
be found in [Tan89]. be found in [Tan89].
Concluding with an example, assume a link with bandwidth of 8 Concluding with an example, assume a link with bandwidth of 8
Gbits/s = 1024^3 Bytes/s, its encoding would consist of an exponent Gbits/s = 1024^3 Bytes/s, its encoding would consist of an exponent
value of 6 since 1024^3 = 4; 096 * 8^6, which would then have a value of 6 since 1024^3= 4,096*8^6, which would then have a
granularity of 8^6 or approx. 260 kBytes/s. The associated binary granularity of 8^6 or approx. 260 kBytes/s. The associated binary
representation would then be %(110) 0 1000 0000 0000% or 53,248 (8). representation would then be %(110) 0 1000 0000 0000% or 53,248 (8).
The bandwidth cost (advertised value) of this link when it is idle, The bandwidth cost (advertised value) of this link when it is idle,
is then the 2's complement of the above binary representation, i.e., is then the 2's complement of the above binary representation, i.e.,
%(001) 1 0111 1111 1111% which corresponds to a decimal value of %(001) 1 0111 1111 1111% which corresponds to a decimal value of
(2^16 - 1) - 53; 248 = 12;287. Assuming now a current reservation (2^16 - 1) - 53,248 = 12,287. Assuming now a current reservation
level of 6;400 Mbits/s = 200 * 1024^2, there remains 1;600 Mbits/s of level of 6;400 Mbits/s = 200 * 1024^2, there remains 1;600 Mbits/s of
available bandwidth on the link. The encoding of this available available bandwidth on the link. The encoding of this available
bandwidth of 1'600 Mbits/s is 6;400 * 8^5, which corresponds to bandwidth of 1'600 Mbits/s is 6,400 * 8^5, which corresponds to
a granularity of 8^5 or approx. 30 kBytes/s, and has a binary a granularity of 8^5 or approx. 30 kBytes/s, and has a binary
representation of %(101) 1 1001 0000 0000% or decimal value of representation of %(101) 1 1001 0000 0000% or decimal value of
47,360. The advertised cost of the link with this load level, is 47,360. The advertised cost of the link with this load level, is
then %(010) 0 0110 1111 1111%, or (2^16-1) -47;360 = 18;175. then %(010) 0 0110 1111 1111%, or (2^16-1) -47,360 = 18,175.
Note that the cost function behaves as it should, i.e., the less Note that the cost function behaves as it should, i.e., the less
bandwidth is available on a link, the higher the cost and the less bandwidth is available on a link, the higher the cost and the less
attractive the link becomes. Furthermore, the targeted property of attractive the link becomes. Furthermore, the targeted property of
better granularity for links with less bandwidth available is also better granularity for links with less bandwidth available is also
achieved. It should, however, be pointed out that the numbers given achieved. It should, however, be pointed out that the numbers given
in the above examples match exactly the resolution of the proposed in the above examples match exactly the resolution of the proposed
encoding, which is of course not always the case in practice. This encoding, which is of course not always the case in practice. This
leaves open the question of how to encode available bandwidth leaves open the question of how to encode available bandwidth
values when they do not exactly match the encoding. The standard values when they do not exactly match the encoding. The standard
practice is to round it to the closest number. Because we are practice is to round it to the closest number. Because we are
ultimately interested in the cost value for which it may be better ultimately interested in the cost value for which it may be better
to be pessimistic than optimistic, we choose to round costs up and, to be pessimistic than optimistic, we choose to round costs up and,
therefore, bandwidth down. therefore, bandwidth down.
3.2.2. Encoding Delay 3.2.2. Encoding Delay
Delay is encoded in microseconds using the same exponential method Delay is encoded in microseconds using the same exponential method
as described for bandwidth except that the base is defined to be 4 as described for bandwidth except that the base is defined to be 4
instead of 8. Therefore, the maximum delay that can be expressed is instead of 8. Therefore, the maximum delay that can be expressed is
(2^13-1) *4^7 i.e., approx.134 seconds. (2^13-1) *4^7 i.e., approx. 134 seconds.
3.3. Packet Formats 3.3. Packet Formats
Given the extended TOS notation to account for QoS metrics, Given the extended TOS notation to account for QoS metrics,
no changes in packet formats are necessary except for the no changes in packet formats are necessary except for the
---------------------------- ----------------------------
8. exponent in parenthesis 8. exponent in parenthesis
(re)introduction of T-bit as the Q-bit in the options field. Routers (re)introduction of T-bit as the Q-bit in the options field. Routers
not understanding the Q-bit should either not consider the QoS not understanding the Q-bit should either not consider the QoS
skipping to change at page 30, line 17 skipping to change at page 30, line 17
|Link_state_threshold_|___1_sec____|____5_sec____|____50_sec___| |Link_state_threshold_|___1_sec____|____5_sec____|____50_sec___|
|_________10%_________|.45%_(1.6%)_|__.29%_(2%)__|__.17%_(3%)__| |_________10%_________|.45%_(1.6%)_|__.29%_(2%)__|__.17%_(3%)__|
|_________80%_________|.16%_(2.4%)_|__.04%_(3%)__|_.02%_(3.8%)_| |_________80%_________|.16%_(2.4%)_|__.04%_(3%)__|_.02%_(3.8%)_|
isp isp
________________________________________________________________ ________________________________________________________________
|_________10%_________|3.37%_(2.1%)|_2.23%_(3.3%)|_1.78%_(7.7%)| |_________10%_________|3.37%_(2.1%)|_2.23%_(3.3%)|_1.78%_(7.7%)|
|_________80%_________|1.54%_(5.4%)|_.42%_(6.6%)_|_.14%_(10.4%)| |_________80%_________|1.54%_(5.4%)|_.42%_(6.6%)_|_.14%_(10.4%)|
8x 8 mesh 8x8 mesh
Table 2: Router processing load and (bandwidth blocking). Table 2: Router processing load and (bandwidth blocking).
In Table 2, processing load is expressed as the percentage of the In Table 2, processing load is expressed as the percentage of the
total CPU resources that are consumed by GateD processing. The total CPU resources that are consumed by GateD processing. The
same table also shows the routing performance that is achieved same table also shows the routing performance that is achieved
for each combination of QoS parameters, so that comparison of the for each combination of QoS parameters, so that comparison of the
different processing cost/routing performance trade-offs can be different processing cost/routing performance trade-offs can be
made. Routing performance is measured using the bandwidth blocking made. Routing performance is measured using the bandwidth blocking
ratio, defined as the sum of requested bandwidth of the requests ratio, defined as the sum of requested bandwidth of the requests
that were rejected over the total offered bandwidth. As can be that were rejected over the total offered bandwidth. As can be
skipping to change at page 31, line 15 skipping to change at page 31, line 15
_______________________________________ _______________________________________
|_Link_state_threshold_|_______________| |_Link_state_threshold_|_______________|
|_________10%__________|3112_bytes/sec_| |_________10%__________|3112_bytes/sec_|
|_________80%__________|177_bytes/sec__| |_________80%__________|177_bytes/sec__|
isp isp
________________________________________ ________________________________________
|_________10%__________|15438_bytes/sec_| |_________10%__________|15438_bytes/sec_|
|_________80%__________|1053_bytes/sec__| |_________80%__________|1053_bytes/sec__|
8x 8 mesh 8x8 mesh
Table 3: Link state update traffic Table 3: Link state update traffic
Summarizing, by carrying out the implementation of the proposed QoS Summarizing, by carrying out the implementation of the proposed QoS
routing extensions to OSPF we demonstrated that such extensions are routing extensions to OSPF we demonstrated that such extensions are
fairly straightforward to implement. Furthermore, by measuring fairly straightforward to implement. Furthermore, by measuring
the performance of the real system we were able to demonstrate the performance of the real system we were able to demonstrate
that the overheads associated with QoS routing are not excessive, that the overheads associated with QoS routing are not excessive,
and are definitely within the capabilities of modern processor and and are definitely within the capabilities of modern processor and
workstation technology. workstation technology.
skipping to change at page 39, line 10 skipping to change at page 39, line 10
with each edge in the graph is as before the bandwidth available on with each edge in the graph is as before the bandwidth available on
the corresponding interface, where b(n;m) is the available bandwidth the corresponding interface, where b(n;m) is the available bandwidth
on the edge between vertices n and m. The vertex corresponding to on the edge between vertices n and m. The vertex corresponding to
the router where the algorithm is being run is selected as the source the router where the algorithm is being run is selected as the source
node for the purpose of path selection, and the algorithm proceeds to node for the purpose of path selection, and the algorithm proceeds to
compute paths to all other nodes (destinations). compute paths to all other nodes (destinations).
Starting with the highest quantization index, Q, the algorithm Starting with the highest quantization index, Q, the algorithm
considers the indices consecutively, in decreasing order. For each considers the indices consecutively, in decreasing order. For each
index q, the algorithm deletes from the original network topology all index q, the algorithm deletes from the original network topology all
links (n;m) for which b(n;m) < bw[q], and then runs on the remaining links (n;m) for which b(n;m) < bw[q], and then runs on the remaining
topology a Dijkstra-based minimum hop count algorithm (10) between topology a Dijkstra-based minimum hop count algorithm (10) between
the source node and all other nodes (vertices) in the graph. Note the source node and all other nodes (vertices) in the graph. Note
that as with the Dijkstra used for on-demand path computation, the that as with the Dijkstra used for on-demand path computation, the
elimination of links such that b(n;m) < bw[q] could also be performed elimination of links such that b(n;m) < bw[q] could also be performed
while running the algorithm. while running the algorithm.
After the algorithm terminates, the q-th column in the routing table After the algorithm terminates, the q-th column in the routing table
is updated. This amounts to recording in the hops field the hop is updated. This amounts to recording in the hops field the hop
count value of the path that was generated by the algorithm, and by count value of the path that was generated by the algorithm, and by
updating the neighbor field. As before, the update of the neighbor updating the neighbor field. As before, the update of the neighbor
field depends on the scope of the path computation. In the case field depends on the scope of the path computation. In the case
of a hop-by-hop routing decision, the neighbor field is set to the of a hop-by-hop routing decision, the neighbor field is set to the
identity of the node adjacent to the source node (next hop) on the identity of the node adjacent to the source node (next hop) on the
path returned by the algorithm. However, note that in order to path returned by the algorithm. However, note that in order to
ensure that the path with the maximal available bandwidth is always ensure that the path with the maximal available bandwidth is always
chosen among all minimum hop paths that can accommodate a given chosen among all minimum hop paths that can accommodate a given
quantized bandwidth, a slightly different update mechanism of the quantized bandwidth, a slightly different update mechanism of the
neighbor field needs to be used in some instances. Specifically, neighbor field needs to be used in some instances. Specifically,
when for a given row, i.e., destination node n, the value of the when for a given row, i.e., destination node n, the value of the
hops field in column q is found equal to the value in column q + 1 hops field in column q is found equal to the value in column q+1
(here we assume q < Q), i.e., paths that can accommodate bw[q] and (here we assume q<Q), i.e., paths that can accommodate bw[q] and
bw[q+ 1] have the same hop count, then the algorithm copies the value bw[q+ 1] have the same hop count, then the algorithm copies the value
of the neighbor field from entry (n;q+1) into that of entry (n;q). of the neighbor field from entry (n;q+1) into that of entry (n;q).
Note: The pseudocode below assumes a hop-by-hop forwarding approach in Note: The pseudocode below assumes a hop-by-hop forwarding approach in
updating the neighbor field. The modifications needed to support updating the neighbor field. The modifications needed to support
explicit route construction are straightforward. The pseudocode explicit route construction are straightforward. The pseudocode
also does not handle equal cost multi-paths for simplicity, but the also does not handle equal cost multi-paths for simplicity, but the
modification needed to add this support have been described above. modification needed to add this support have been described above.
Details of the post-processing step of adding stub networks are Details of the post-processing step of adding stub networks are
omitted. omitted.
skipping to change at page 45, line 20 skipping to change at page 45, line 20
[GOW97] R. Guerin, A. Orda, and D. Williams. QoS Routing [GOW97] R. Guerin, A. Orda, and D. Williams. QoS Routing
Mechanisms and OSPF Extensions. In Proceedings of the 2nd Mechanisms and OSPF Extensions. In Proceedings of the 2nd
IEEE Global Internet Mini-Conference, Phoenix, AZ, November IEEE Global Internet Mini-Conference, Phoenix, AZ, November
1997. 1997.
[KNB98] F. Baker K. Nichols, S. Blake and D. Black. Definition of [KNB98] F. Baker K. Nichols, S. Blake and D. Black. Definition of
the differentiated services field (DS field) in the IPv4 the differentiated services field (DS field) in the IPv4
and IPv6 headers. INTERNET-DRAFT, October 1998. work in and IPv6 headers. INTERNET-DRAFT, October 1998. work in
progress. progress.
[LO] D. H. Lorenz and A. Orda. QoS Routing in Networks with [LO98] D. H. Lorenz and A. Orda. QoS Routing in Networks with
Uncertain Parameters. IEEE/ACM Transactions on Networking. Uncertain Parameters. IEEE/ACM Transactions on Networking,
To appear. 6(6):768--778, December 1998.
[Moy94] J. Moy. OSPF Version 2. INTERNET-RFC 1583, March 1994. [Moy94] J. Moy. OSPF Version 2. INTERNET-RFC 1583, March 1994.
[Moy98] J. Moy. OSPF Version 2. INTERNET-RFC 2328, April 1998. [Moy98] J. Moy. OSPF Version 2. INTERNET-RFC 2328, April 1998.
[Prz95] A. Przygienda. Link State Routing with QoS in ATM [Prz95] A. Przygienda. Link State Routing with QoS in ATM
LANs. Ph.D. Thesis Nr. 11051, Swiss Federal Institute of LANs. Ph.D. Thesis Nr. 11051, Swiss Federal Institute of
Technology, April 1995. Technology, April 1995.
[RMK+98] R. Rajan, J. C. Martin, S. Kamat, M. See, R. Chaudhury, [RMK+98] R. Rajan, J. C. Martin, S. Kamat, M. See, R. Chaudhury,
skipping to change at page 46, line 21 skipping to change at page 46, line 21
George Apostolopoulos George Apostolopoulos
IBM T.J. Watson Research Center IBM T.J. Watson Research Center
P.O. Box 704 P.O. Box 704
Yorktown Heights, NY 10598 Yorktown Heights, NY 10598
georgeap@watson.ibm.com georgeap@watson.ibm.com
VOICE +1 914 784-6204 VOICE +1 914 784-6204
FAX +1 914 784-6205 FAX +1 914 784-6205
Roch Guerin Roch Guerin
University Of Pennsylvania University Of Pennsylvania
Department of Electrical Engineering, Rm 376 GRW Department of Electrical Engineering, Rm 367 GRW
200 South 33rd Street 200 South 33rd Street
Philadelphia, PA 19104--6390 Philadelphia, PA 19104--6390
guerin@ee.upenn.edu guerin@ee.upenn.edu
VOICE +1 215-898-9351 VOICE +1 215-898-9351
Sanjay Kamat Sanjay Kamat
IBM T.J. Watson Research Center IBM T.J. Watson Research Center
P.O. Box 704 P.O. Box 704
Yorktown Heights, NY 10598 Yorktown Heights, NY 10598
sanjay@watson.ibm.com sanjay@watson.ibm.com
skipping to change at page 47, line 8 skipping to change at page 47, line 8
FAX +011 972-4-8323041 FAX +011 972-4-8323041
Tony Przygienda Tony Przygienda
Bell Labs, Lucent Technologies Bell Labs, Lucent Technologies
prz@dnrc.bell-labs.com prz@dnrc.bell-labs.com
VOICE +1 732 949-5936 VOICE +1 732 949-5936
Doug Williams Doug Williams
IBM T.J. Watson Research Center IBM T.J. Watson Research Center
P.O. Box 704 P.O. Box 704
Yorktown Heights, NY 10598 Yorktown Heights, NY 10598
dawillia@us.ibm.com dougw@watson.ibm.com
VOICE +1 919-543-8592 VOICE +1 914 784-5047
FAX +1 914 784-6318
 End of changes. 18 change blocks. 
30 lines changed or deleted 35 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/