table was built using the algorithm of Section 2.3.1 or Appendix C.
Specifically, in both cases, the neighbor field in each entry points
to the previous node on the path from the source node and with the
same bandwidth capabilities as those associated with the current
entry. The complete path is, therefore, reconstructed by following
the pointers provided by the neighbor field of successive entries.
In the case of the Bellman-Ford algorithm of Section 2.3.1, this
means moving backwards in the table from column to column, using at
each step the row index pointed to by the neighbor field of the entry
in the previous column. Each time, the corresponding vertex index
specified in the neighbor field is pre-pended to the list of vertices
constructed so far. Since we start at column h, the process ends
when the first column is reached, i.e., after h steps, at which point
the list of vertices making up the path has been reconstructed.
In the case of the Dijkstra algorithm of Appendix C, the backtracking
process is similar although slightly different because of the
different relation between paths and columns in the routing table,
i.e., a column now corresponds to a quantized bandwidth value instead
of a hop count. The backtracking now proceeds along the column
corresponding to the quantized bandwidth value needed to satisfy the
bandwidth requirements of the flow. At each step, the vertex index
specified in the neighbor field is pre-pended to the list of vertices
constructed so far, and is used to identify the next row index to
move to. The process ends when an entry is reached whose neighbor
field specifies the origin vertex of the flow. Note that since there
are as many rows in the table as there are vertices in the graph,
i.e., N, it could take up to N steps before the process terminates.
Note that the identification of the first entry in the routing table
is identical to what was described for the hop-by-hop routing case.
However, as described in this section, the update of the neighbor
fields while constructing the QoS routing tables, is being performed
differently in the explicit and hop-by-hop routing cases. Clearly,
two different neighbor fields can be kept in each entry and updates
to both could certainly be performed jointly, if support for both
xplicit routing and hop-by-hop routing is needed.
Endnotes
1. In this document we commit the abuse of notation of calling a
"network" the interconnection of routers and networks through
which we attempt to compute a QoS path.
2. This is true for uni-cast flows, but in the case of multi-cast
flows, hop-by-hop and an explicit routing clearly have different
implications.
3. Some hysteresis mechanism should be added to suppress updates when
the metric value oscillates around a class boundary.
4. In this document, we use the terms node and vertex
interchangeably.
5. Various hybrid methods can also be envisioned, e.g., periodic
computations except if more than a given number of updates are
received within a shorter interval, or periodic updates except if
the change in metrics corresponding to a given update exceeds a
certain threshold. Such variations are, however, not considered
in this document.
6. Modifications to support explicit routing are discussed in
Appendix D.
7. Note, that this does not say anything on whether to differentiate
between outgoing and incoming bandwidth on a shared media network.
As a matter of fact, a reasonable option is to set the incoming
bandwidth (from network to router) to infinity, and only use the
outgoing bandwidth value to characterize bandwidth availability on
the shared network.
8. exponent in parenthesis
9. Access to some of the more recent versions of the GateD software
is restricted to the GateD consortium members.
10. Note that a Breadth-First-Search (BFS) algorithm [CLR90] could
also be used. It has a lower complexity, but would not allow
reuse of existing code in an OSPF implementation.
References
[AGK99] G. Apostolopoulos, R. Guerin, and S. Kamat. Implementation
and performance meassurements of QoS routing extensions to
OSPF. In Proceedings of INFOCOM'99, pages 680--688, New
York, NY, March 1999.
[AGKT98] G. Apostolopoulos, R. Guerin, S. Kamat, and S. K. Tripathi.
QoS routing: A performance perspective. In Proceedings of
ACM SIGCOMM'98, pages 17--28, Vancouver, Canada, October
[Alm92] Almquist, P., "Type of Service in the Internet Protocol
Suite", RFC1349, July 1992.
[AT98] G. Apostolopoulos and S. K. Tripathi. On reducing the
processing cost of on-demand QoS path computation. In
Proceedings of ICNP'98, pages 80--89, Austin, TX, October
1998.
[BP95] J.-Y. Le Boudec and T. Przygienda. A Route Pre-Computation
Algorithm for Integrated Services Networks. Journal of
Network and Systems Management, 3(4), 1995.
[Car79] B. Carre. Graphs and Networks. Oxford University Press,
ISBN 0-19-859622-7, Oxford, UK, 1979.
[CLR90] T. H. Cormen, C. E. Leiserson, and R. L. Rivest.
Introduction to Algorithms. MIT Press, Cambridge, MA, 1990.
[Con] Merit GateD Consortium. The Gate Daemon (GateD) project.
[GJ79] M.R. Garey and D.S. Johnson. Computers and Intractability.
Freeman, San Francisco, 1979.
[GKH97] R. Guerin, S. Kamat, and S. Herzog. QoS Path Management
with RSVP. In Proceedings of the 2nd IEEE Global Internet
Mini-Conference, pages 1914-1918, Phoenix, AZ, November
[GKR97] Guerin, R., Kamat, S. and E. Rosen, "An Extended RSVP
Routing Interface, Work in Progress.
[GLG+97] Der-Hwa G., Li, T., Guerin, R., Rosen, E. and S. Kamat,
"Setting Up Reservations on Explicit Paths using RSVP", Work
in Progress.
[GO99] R. Guerin and A. Orda. QoS-Based Routing in Networks with
Inaccurate Information: Theory and Algorithms. IEEE/ACM
Transactions on Networking, 7(3):350--364, June 1999.
[GOW97] R. Guerin, A. Orda, and D. Williams. QoS Routing Mechanisms
and OSPF Extensions. In Proceedings of the 2nd IEEE Global
Internet Mini-Conference, pages 1903-1908, Phoenix, AZ,
November 1997.
[KNB98] Nichols, K., Blake, S., Baker F. and D. Black, "Definition
of the Differentiated Services Field (DS Field) in the IPv4
and IPv6 Headers", RFC2474, December 1998.
[LO98] D. H. Lorenz and A. Orda. QoS Routing in Networks with
Uncertain Parameters. IEEE/ACM Transactions on Networking,
6(6):768--778, December 1998.
[Moy94] Moy, J., "OSPF Version 2", RFC1583, March 1994.
[Moy98] Moy, J., "OSPF Version 2", STD 54, RFC2328, April 1998.
[Prz95] A. Przygienda. Link State Routing with QoS in ATM LANs.
Ph.D. Thesis Nr. 11051, Swiss Federal Institute of
Technology, April 1995.
[RMK+98] R. Rajan, J. C. Martin, S. Kamat, M. See, R. Chaudhury, D.
Verma, G. Powers, and R. Yavatkar. Schema for
differentiated services and integrated services in networks.
INTERNET-DRAFT, October 1998. work in progress.
[RZB+97] Braden, R., Editor, Zhang, L., Berson, S., Herzog, S. and S.
Jamin, "Resource reSerVation Protocol (RSVP) Version 1,
Functional Specification", RFC2205, September 1997.
[SPG97] Shenker, S., Partridge, C. and R. Guerin, "Specification of
Guaranteed Quality of Service", RFC2212, November 1997.
[ST83] D.D. Sleator and R.E. Tarjan. A Data Structure for Dynamic
Trees. Journal of Computer Systems, 26, 1983.
[Tan89] A. Tannenbaum. Computer Networks. Addisson Wesley, 1989.
[YPG97] Yavatkar, R., Pendarakis, D. and R. Guerin, "A Framework for
Policy-based Admission Control", INTERNET-DRAFT, April 1999.
Work in Progress.
Authors' Addresses
George Apostolopoulos
IBM T.J. Watson Research Center
P.O. Box 704
Yorktown Heights, NY 10598
Phone: +1 914 784-6204
Fax: +1 914 784-6205
EMail: georgeap@watson.ibm.com
Roch Guerin
University Of Pennsylvania
Department of Electrical Engineering, Rm 367 GRW
200 South 33rd Street
Philadelphia, PA 19104--6390
Phone: +1 215-898-9351
EMail: guerin@ee.upenn.edu
Sanjay Kamat
Bell Laboratories
Lucent Technologies
Room 4C-510
101 Crawfords Corner Road
Holmdel, NJ 07733
Phone: (732) 949-5936
email: sanjayk@dnrc.bell-labs.com
Ariel Orda
Dept. Electrical Engineering
Technion - I.I.T
Haifa, 32000 - ISRAEL
Phone: +011 972-4-8294646
Fax: +011 972-4-8323041
EMail: ariel@ee.technion.ac.il
Tony Przygienda
Siara Systems
300 Ferguson Drive
Moutain View
California 94043
Phone: +1 732 949-5936
Email: prz@siara.com
Doug Williams
IBM T.J. Watson Research Center
P.O. Box 704
Yorktown Heights, NY 10598
Phone: +1 914 784-5047
Fax: +1 914 784-6318
EMail: dougw@watson.ibm.com
Full Copyright Statement
Copyright (C) The Internet Society (1999). 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
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.
Acknowledgement
Funding for the RFCEditor function is currently provided by the
Internet Society.