rfc2676.txt

著名的RFC文档,其中有一些文档是已经翻译成中文的的.

        -------------------------------------------------
        0               8,191                   1
        1               65,528                  8
        2               524,224                 64
        3               4,193,792               512
        4               33,550,336              4,096
        5               268,402,688             32,768
        6               2,147,221,504           262,144
        7               17,177,772,032          2,097,152

          Ranges of Exponent Values for 13 bits,
               base 8 Encoding, in Bytes/s

   The bandwidth encoding rule may be summarized as: "represent
   available bandwidth in 16 bit field as a 3 bit exponent (with assumed
   base of 8) followed by a 13 bit mantissa as shown below and advertise
   2's complement of the above representation."

        0       8       16
        |       |       |
        -----------------
       |EXP| MANT        |
        -----------------

   Thus, the above encoding advertises a numeric value that is

      2^16 -1 -(exponential encoding of the available bandwidth):

   This has the property of advertising a higher numeric value for lower
   available bandwidth, a notion that is consistent with that of cost.

   Although it may seem slightly pedantic to insist on the property that
   less bandwidth is expressed higher values, it has, besides
   consistency, a robustness aspect in it.  A router with a poor OSPF
   implementation could misuse or misunderstand bandwidth metric as
   normal administrative cost provided to it and compute spanning trees
   with a "normal" Dijkstra.  The effect of a heavily congested link
   advertising numerically very low cost could be disastrous in such a
   scenario.  It would raise the link's attractiveness for future
   traffic instead of lowering it.  Evidence that such considerations
   are not speculative, but similar scenarios have been encountered, can
   be found in [Tan89].







Apostolopoulos, et al.        Experimental                     [Page 20]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   Concluding with an example, assume a link with bandwidth of 8 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 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).  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., %(001) 1 0111
   1111 1111% which corresponds to a decimal value of (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 available
   bandwidth on the link.  The encoding of this available 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 representation of %(101)
   1 1001 0000 0000% or decimal value of 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.

   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
   attractive the link becomes.  Furthermore, the targeted property of
   better granularity for links with less bandwidth available is also
   achieved.  It should, however, be pointed out that the numbers given
   in the above examples match exactly the resolution of the proposed
   encoding, which is of course not always the case in practice.  This
   leaves open the question of how to encode available bandwidth values
   when they do not exactly match the encoding.  The standard practice
   is to round it to the closest number.  Because we are ultimately
   interested in the cost value for which it may be better to be
   pessimistic than optimistic, we choose to round costs up and,
   therefore, bandwidth down.

3.2.2. Encoding Delay

   Delay is encoded in microseconds using the same exponential method 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
   (2^13-1) *4^7 i.e., approx. 134 seconds.

3.3. Packet Formats

   Given the extended TOS notation to account for QoS metrics, no
   changes in packet formats are necessary except for the
   (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
   metrics distributed or consider those as `unknown' TOS.






Apostolopoulos, et al.        Experimental                     [Page 21]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   To support QoS, there are additions to two Link State Advertisements,
   the Router Links Advertisement and the Summary Links Advertisement.
   As stated above, a router identifies itself as supporting QoS by
   setting the Q-bit in the options field of the Link State Header.
   When a router that supports QoS receives either the Router Links or
   Summary Links Advertisement, it should parse the QoS metrics encoded
   in the received Advertisement.

3.4. Calculating the Inter-area Routes

   This document proposes a very limited use of OSPF areas, that is, it
   is assumed that summary links advertisements exist for all networks
   in the area.  This document does not discuss the problem of providing
   support for area address ranges and QoS metric aggregation.  This is
   left for further studies.

3.5. Open Issues

   Support for AS External Links, Virtual Links, and incremental updates
   for summary link advertisements are not addressed in this document
   and are left for further study.  For Virtual Links that do exist, it
   is assumed for path selection that these links are non-QoS capable
   even if the router advertises QoS capability.  Also, as stated
   earlier, this document does not address the issue of non-QoS routers
   within a QoS domain.

4. A Reference Implementation based on GateD

   In this section we report on the experience gained from implementing
   the pre-computation based approach of Section 2.3.1 in the GateD
   [Con] environment.  First, we briefly introduce the GateD
   environment, and then present some details on how the QoS extensions
   were implemented in this environment.  Finally, we discuss issues
   that arose during the implementation effort and present some
   measurement based results on the overhead that the QoS extensions
   impose on a QoS capable router and a network of QoS routers.  For
   further details on the implementation study, the reader is referred
   to [AGK99].  Additional performance evaluation based on simulations
   can be found in [AGKT98].

4.1. The Gate Daemon (GateD) Program

   GateD [Con] is a popular, public domain (9) program that provides a
   platform for implementing routing protocols on hosts running the Unix
   operating system.  The distribution of the GateD software also
   includes implementations of many popular routing protocols, including
   the OSPF protocol.  The GateD environment offers a variety of
   services useful for implementing a routing protocol.  These services



Apostolopoulos, et al.        Experimental                     [Page 22]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   include a) support for creation and management of timers, b) memory
   management, c) a simple scheduling mechanism, d) interfaces for
   manipulating the host's routing table and accessing the network, and
   e) route management (e.g., route prioritization and route exchange
   between protocols).

   All GateD processing is done within a single Unix process, and
   routing protocols are implemented as one or several tasks.  A GateD
   task is a collection of code associated with a Unix socket.  The
   socket is used for the input and output requirements of the task.
   The main loop of GateD contains, among other operations, a select()
   call over all task sockets to determine if any read/write or error
   conditions occurred in any of them.  GateD implements the OSPF link
   state database using a radix tree for fast access to individual link
   state records.  In addition, link state records for neighboring
   network elements (such as adjacent routers) are linked together at
   the database level with pointers.  GateD maintains a single routing
   table that contains routes discovered by all the active routing
   protocols.  Multiple routes to the same destination are prioritized
   according to a set of rules and administrative preferences and only a
   single route is active per destination.  These routes are
   periodically downloaded in the host's kernel forwarding table.

4.2. Implementing the QoS Extensions of OSPF

4.2.1. Design Objectives and Scope

   One of our major design objectives was to gain substantial experience
   with a functionally complete QoS routing implementation while
   containing the overall implementation complexity.  Thus, our
   architecture was modular and aimed at reusing the existing OSPF code
   with only minimal changes.  QoS extensions were localized to specific
   modules and their interaction with existing OSPF code was kept to a
   minimum.  Besides reducing the development and testing effort, this
   approach also facilitated experimentation with different alternatives
   for implementing the QoS specific features such as triggering
   policies for link state updates and QoS route table computation.
   Several of the design choices were also influenced by our assumptions
   regarding the core functionalities that an early prototype
   implementation of QoS routing must demonstrate.  Some of the
   important assumptions/requirements are:

   -  Support for only hop-by-hop routing.  This affected the path
      structure in the QoS routing table as it only needs to store next
      hop information.  As mentioned earlier, the structure can be
      easily extended to allow construction of explicit routes.





Apostolopoulos, et al.        Experimental                     [Page 23]

RFC 2676       QoS Routing Mechanisms and OSPF Extensions    August 1999


   -  Support for path pre-computation.  This required the creation of a
      separate QoS routing table and its associated path structure, and
      was motivated by the need to minimize processing overhead.

   -  Full integration of the QoS extensions into the GateD framework,
      including configuration support, error logging, etc.  This was
      required to ensure a fully functional implementation that could be
      used by others.

   -  Ability to allow experimentation with different approaches, e.g.,
      use of different update and pre-computation triggering policies
      with support for selection and parameterization of these policies
      from the GateD configuration file.

   -  Decoupling from local traffic and resource management components,
      i.e., packet classifiers and schedulers and local call admission.
      This is supported by providing an API between QoS routing and the
      local traffic management module, which hides all internal details
      or mechanisms.  Future implementations will be able to specify
      their own mechanisms for this module.

   -  Interface to RSVP. The implementation assumes that RSVP [RZB+97]
      is the mechanism used to request routes with specific QoS
      requirements.  Such requests are communicated through an interface
      based on [GKR97], and used the RSVP code developed at ISI, version
      4.2a2 [RZB+97].

   In addition, our implementation also relies on several of the
   simplifying assumptions made earlier in this document, namely:

   -  The scope of QoS route computation is currently limited to a
      single area.

   -  All routers within the area are assumed to run a QoS enabled
      version of OSPF, i.e., inter-operability with non-QoS aware
      versions of the OSPF protocol is not considered.

   -  All interfaces on a router are assumed to be QoS capable.

4.2.2. Architecture

   The above design decisions and assumptions resulted in the
   architecture shown in Figure 2.  It consists of three major
   components:  the signaling component (RSVP in our case); the QoS
   routing component; and the traffic manager.  In the rest of this
   section we concentrate on the structu