Network Working Group                                         F.J. Baker
Internet-Draft                                             Cisco Systems
Intended status: Standards Track                       February 17, 2013
Expires: August 21, 2013


                          Extensible OSPF LSAs
                  draft-baker-ipv6-ospf-extensible-00

Abstract

   This note describes the changes necessary for OSPFv3 to route
   extensible classes of traffic.  This implies not routing "to a
   destination", but "traffic matching a classification tuple" which
   includes a destination but may also include other attributes such as
   the source address, DSCP, or Flow Label.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   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."

   This Internet-Draft will expire on August 21, 2013.

Copyright Notice

   Copyright (c) 2013 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.



Baker                   Expires August 21, 2013                 [Page 1]


Internet-Draft                                             February 2013


Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
     1.1.  Requirements Language . . . . . . . . . . . . . . . . . .   3
   2.  Theory of Routing . . . . . . . . . . . . . . . . . . . . . .   3
     2.1.  Dealing with ambiguity  . . . . . . . . . . . . . . . . .   3
   3.  Extensions necessary for OSPFv3 . . . . . . . . . . . . . . .   4
     3.1.  OSPF optional data extensions . . . . . . . . . . . . . .   4
       3.1.1.  IPv6 Destination Prefix TLV . . . . . . . . . . . . .   4
       3.1.2.  IPv6 Forwarding Address TLV . . . . . . . . . . . . .   5
       3.1.3.  Referenced Advertising Router TLV . . . . . . . . . .   5
       3.1.4.  Metric TLV  . . . . . . . . . . . . . . . . . . . . .   6
       3.1.5.  External Route Tag TLV  . . . . . . . . . . . . . . .   6
       3.1.6.  Referenced Link State ID TLV  . . . . . . . . . . . .   7
     3.2.  OSPF extensible LSAs  . . . . . . . . . . . . . . . . . .   7
       3.2.1.  Extensible-Inter-area-prefix-LSA  . . . . . . . . . .   8
       3.2.2.  Extensible-AS-external-LSA  . . . . . . . . . . . . .   9
       3.2.3.  Extensible-Intra-Area-Prefix-LSA  . . . . . . . . . .   9
   4.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  10
   5.  Security Considerations . . . . . . . . . . . . . . . . . . .  10
   6.  Privacy Considerations  . . . . . . . . . . . . . . . . . . .  11
   7.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .  11
   8.  Change Log  . . . . . . . . . . . . . . . . . . . . . . . . .  11
   9.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  11
     9.1.  Normative References  . . . . . . . . . . . . . . . . . .  11
     9.2.  Informative References  . . . . . . . . . . . . . . . . .  11
   Appendix A.  FIB Design . . . . . . . . . . . . . . . . . . . . .  11
     A.1.  Linux Source-Address Forwarding . . . . . . . . . . . . .  12
       A.1.1.  One FIB per source prefix . . . . . . . . . . . . . .  12
       A.1.2.  One FIB per source prefix plus a general FIB  . . . .  13
     A.2.  PATRICIA  . . . . . . . . . . . . . . . . . . . . . . . .  13
       A.2.1.  Virtual Bit String  . . . . . . . . . . . . . . . . .  13
       A.2.2.  Tree Construction . . . . . . . . . . . . . . . . . .  14
       A.2.3.  Tree Lookup . . . . . . . . . . . . . . . . . . . . .  15
   Author's Address  . . . . . . . . . . . . . . . . . . . . . . . .  15


1.  Introduction

   In related documents, the author proposes extensions to OSPF and IS-
   IS for the routing of IPv6 traffic using more than the destination
   address as the definition of a class of traffic to be routed.  These
   include the possibility of source/destination routing, and especially
   egress routing, routing based on the destination plus the DSCP value
   such as is discussed in [RFC4915], and routing using the destination
   plus the IPv6 Flow Label for a form of Role Based Access Control - if
   the sender doesn't know the flow label value that the receiver is
   using, which it would learn from the network administrator through



Baker                   Expires August 21, 2013                 [Page 2]


Internet-Draft                                             February 2013


   configuration, DHCP, or some other means, it in effect has no route
   to the destination.

   These capabilities, in OSPFv3, are have as a premise an extensible
   LSA; an LSA that contains the necessary elements of any LSA as
   discussed in section 4.4.1 of [RFC5340], a destination address, and a
   set of options.  This document describes extensible inter-area-
   prefix-LSAs, intra-area-prefix-LSAs, and AS-external-LSAs.
   Additional options are defined in other documents.

   Existing OSPF LSAs that specify only a destination prefix may be
   understood as identifying a destination prefix and "any" other
   option, whether it be source address, flow label, or something else.
   This is also a useful class of traffic to compactly represent, so
   existing LSA types are not deprecated, merely added to.

1.1.  Requirements Language

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].

2.  Theory of Routing

   Both IS-IS and OSPF perform their calculations by building a routes
   from the router performing the calculation to each router, and then
   use those routes to get to destinations that those routes advertise
   connectivity to.  Following the SPF algorithm, calculation starts by
   selecting a starting point (typically the router doing the
   calculation), and successively adding {link, router) pairs until one
   has calculated a route to every router in the network.  As each
   router is added, including the original router, destinations that it
   is directly connected to are turned into routes in the route table:
   "to get to 2001:db8::/32, route traffic to {interface, list of next
   hop routers}".  For immediate neighbors to the originating router, of
   course, there is no next hop router; traffic is handled locally.

2.1.  Dealing with ambiguity

   In any routing protocol, there is the possibility of ambiguity.  An
   area border router might, for example, summarize the routes to other
   areas into a small set of relatively short prefixes, which have more
   specific routes within the area.  Traditionally, we have dealt with
   that using a "longest match first" rule.  If the same datagram
   matches more than one destination prefix advertised within the area,
   we follow the route to the longest matching prefix.





Baker                   Expires August 21, 2013                 [Page 3]


Internet-Draft                                             February 2013


   When routing a class of traffic, we follow an analogous "most
   specific match" rule; we follow the route for the most specific
   matching tuple.  In cases of simple overlap, such as routing to
   2001:db8::/32 or 2001:db8:1::/48, that is exactly analogous; we
   choose one of the two routes.

   It is possible, however, to construct an ambiguous case in which
   neither class subsumes the other.  For example, presume that

   o  A is a prefix,

   o  B is a more-specific prefix within A,

   o  C is a different prefix, and

   o  D is a more-specific prefix of C.

   The two classes {A, D, *, *} and {B, C, *, *} are ambiguous: a
   datagram within {B, D, *, *} matches both classes, and it is not
   clear in the data plane what decision to make.  Solving this requires
   the addition of a third route in the FIB corresponding to the class
   {B, D, *, *}, which is more-specific than either of the first two,
   and can be given routing guidance based on metrics or other policy in
   the usual way.

3.  Extensions necessary for OSPFv3

   Changing OSPF to provide for this type of change requires cloning
   many of the existing LSAs: the inter-area-prefix-LSAs, the AS-
   external-LSAs, and the intra-area-prefix LSA.  This can be done
   specifically with the information we have thought about, or designed
   for extensibility.  We choose extensibility.

3.1.  OSPF optional data extensions

   This section defines a number of optional type-length-value (TLV)
   information elements that may be included in an extensible LSA.  In
   an extensible LSA, elements not included are not considered in
   classification and as a result are in effect wild-carded.

3.1.1.  IPv6 Destination Prefix TLV

   The IPv6 Destination Prefix TLV MAY be used with the IPv6 Source
   Prefix TLV, but MUST NOT be used with the IPv4 Source Prefix TLV or
   the IPv4 Destination Prefix TLV.

   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1



Baker                   Expires August 21, 2013                 [Page 4]


Internet-Draft                                             February 2013


   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |      Type     |    Length     |Prefix Length  |    Prefix
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                          Destination Prefix TLV

   Destination Prefix Type:  assigned by IANA

   TLV Length:  Length of the TLV in octets

   Prefix Length:  Length of the prefix in bits, in the range 0..128

   Prefix:  (Destination prefix length +7)/8 octets of prefix

3.1.2.  IPv6 Forwarding Address TLV

   The IPv6 Forwarding Address TLV is only used in the Extensible-AS-
   external-LSA, and is optional.

   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |      Type     |    Length     |  128 bit IPv6 Address
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                        IPv6 Forwarding Address TLV

   Flow Label Type:  assigned by IANA

   TLV Length:  Length of the TLV in octets

   IPv6 Address:  A fully qualified IPv6 address (128 bits).  If
      included, data traffic for the advertised destination will be
      forwarded to this address.  It MUST NOT be set to the IPv6
      Unspecified Address (0:0:0:0:0:0:0:0) or an IPv6 Link-Local
      Address (Prefix FE80/10).  While OSPFv3 routes are normally
      installed with link-local addresses, an OSPFv3 implementation
      advertising a forwarding address MUST advertise a global IPv6
      address.  This global IPv6 address may be the next-hop gateway for
      an external prefix or may be obtained through some other method
      (e.g., configuration).

3.1.3.  Referenced Advertising Router TLV

   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |      Type     |    Length     |  Referenced Advertising Router



Baker                   Expires August 21, 2013                 [Page 5]


Internet-Draft                                             February 2013


   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                     Referenced Advertising Router TLV

   Flow Label Type:  assigned by IANA

   TLV Length:  Length of the TLV in octets

   Referenced Link State ID:  With the Referenced Link State ID TLV
      (Referenced LS Type and Referenced Link State ID), Identifies the
      router-LSA or network-LSA with which the IPv6 traffic classes
      should be associated.  If Referenced LS Type is 0x2001, the
      prefixes are associated with a router-LSA, Referenced Link State
      ID should be 0, and Referenced Advertising Router should be the
      originating router's Router ID.  If Referenced LS Type is 0x2002,
      the prefixes are associated with a network-LSA, Referenced Link
      State ID should be the Interface ID of the link's Designated
      Router, and Referenced Advertising Router should be the Designated
      Router's Router ID.

3.1.4.  Metric TLV

   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |      Type     |    Length     |  Metric                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | PrefixOptions | Information elements for the traffic class
   +-+-+-+-+-+-+-+-+

                                Metric TLV

   Flow Label Type:  assigned by IANA

   TLV Length:  Length of the TLV in octets

   Metric:  The cost of this traffic class.  Expressed in the same units
      as the interface costs in router-LSAs.

   Information Elements  This information element will be followed by
      zero or more information elements that describe the traffic class.
      the traffic class will have been fully described when parsing
      reaches the end of the LSA or finds a new Metric TLV.

3.1.5.  External Route Tag TLV




Baker                   Expires August 21, 2013                 [Page 6]


Internet-Draft                                             February 2013


   The External Route Tag TLV is only used in the Extensible-AS-
   external-LSA, and is optional.

   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |      Type     |    Length     |    External Route Tag
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                          External Route Tag TLV

   Flow Label Type:  assigned by IANA

   TLV Length:  Length of the TLV in octets

   Route Tag:  A 32-bit field that MAY be used to communicate additional
      information between AS boundary routers.

3.1.6.  Referenced Link State ID TLV

   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |      Type     |    Length     |  Referenced LS Type           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                 Referenced Link State ID                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                       Referenced Link State ID TLV

   Flow Label Type:  assigned by IANA

   TLV Length:  Length of the TLV in octets

   Referenced LS Type:  The LSType of the associate LSA.

   Referenced Link State ID:  If included, additional information
      concerning the advertised external route can be found in the LSA
      having LS type equal to "Referenced LS Type", Link State ID equal
      to "Referenced Link State ID", and Advertising Router the same as
      that specified in the Extensible-AS-external-LSA's link-state
      header.  This additional information is not used by the OSPF
      protocol itself.  It may be used to communicate information
      between AS boundary routers.  The precise nature of such
      information is outside the scope of this specification.

3.2.  OSPF extensible LSAs




Baker                   Expires August 21, 2013                 [Page 7]


Internet-Draft                                             February 2013


   This section defines the extensible Extensible-Inter-Area-Prefix-LSA,
   Extensible-AS-external-LSA, and Extensible-Intra-Area-Prefix LSA.

3.2.1.  Extensible-Inter-area-prefix-LSA

   Extensible-Inter-area-prefix-LSAs have LS type equal to [IANA?].
   These LSAs are equivalent to OSPFv2's type 3 summary-LSAs (see
   Section 12.4.3 of [RFC2328]).  Originated by area border routers,
   they describe IPv4 or IPv6 traffic classes that belong to other
   areas, and are encoded using the TLVs defined in Section 3.1.  A
   separate inter-area-prefix-LSA is originated for each such traffic
   class.  For details concerning the construction of inter-area-
   prefix-LSAs, see [RFC5340] Section 4.4.3.4.

   For stub areas, inter-area-prefix-LSAs can also be used to describe a
   (per-area) default route.  Default summary routes are used in stub
   areas instead of flooding a complete set of external routes.  When
   describing a default summary route, the Extensible-inter-area-prefix-
   LSA omits the Destination Prefix information element, which has the
   same effect as matching 0.0.0.0/0 or ::/0.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |           LS Age              |0|0|1|       LS-Type           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Link State ID                           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Advertising Router                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    LS Sequence Number                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |        LS Checksum            |            Length             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |      0        |                  Metric                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Zero or more Information Element TLVs
   +

                Figure 1: Extensible-Inter-area-prefix-LSA

   LS-Type:  To be assigned by IANA

   Metric:  The cost of this route.  Expressed in the same units as the
      interface costs in router-LSAs.  When the Extensible-inter-area-
      prefix-LSA is describing a route to a range of addresses (see
      [RFC5340] Appendix C.2), the cost is set to the maximum cost to
      any reachable component of the address range.



Baker                   Expires August 21, 2013                 [Page 8]


Internet-Draft                                             February 2013


3.2.2.  Extensible-AS-external-LSA

   This is an AS-external-LSAs, but may include other information
   elements.  Unlike the AS-external-LSAs, however, the presence of
   optional information is determined by the presence of the information
   elements, not by flags.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |           LS Age              |0|1|0|         Type            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Link State ID                           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Advertising Router                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    LS Sequence Number                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |        LS Checksum            |            Length             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |      0  |E|0 0|                  Metric                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  One or more Information Element TLVs
   +

                   Figure 2: Extensible-AS-external-LSA

   E: The type of external metric.  If bit E is set, the metric
      specified is a Type 2 external metric.  This means the metric is
      considered larger than any intra-AS path.  If bit E is zero, the
      specified metric is a Type 1 external metric.  This means that it
      is expressed in the same units as other LSAs (i.e., the same units
      as the interface costs in router-LSAs).

   :  The cost of this route.  Interpretation depends on the external
      type indication (bit E above).

3.2.3.  Extensible-Intra-Area-Prefix-LSA

   This LSA MUST include a Referenced Link State ID TLV and a Referenced
   Advertising Router TLV immediately following the number of traffic
   classes.  It MUST also include the indicated number of Metric TLVs,
   each of which is followed by the information elements that define
   that class of traffic, which will usually include a Destination
   Prefix TLV and may include a source prefix TLV, Flow Label TLV, or
   DSCP TLV.





Baker                   Expires August 21, 2013                 [Page 9]


Internet-Draft                                             February 2013


   Extensible-Intra-area-prefix-LSAs have LS types assigned by IANA.  A
   router uses Extensible-intra-area-prefix-LSAs to advertise one or
   more traffic classes that are associated with a local router address,
   an attached stub network segment, or an attached transit network
   segment.  In IPv4, the first two were accomplished via the router's
   router-LSA and the last via a network-LSA.  In OSPF for IPv6, all
   addressing information that was advertised in router-LSAs and
   network-LSAs has been removed and is now advertised in intra-area-
   prefix-LSAs.  For details concerning the construction of intra-area-
   prefix-LSA, see [RFC5340] Section 4.4.3.9.

   A router can originate multiple extensible-intra-area-prefix-LSAs for
   each router or transit network.  Each such LSA is distinguished by
   its unique Link State ID.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |           LS Age              |0|0|1|            9            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Link State ID                           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Advertising Router                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    LS Sequence Number                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |        LS Checksum            |             Length            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         # Traffic Classes     | Information Elements
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                Figure 3: Extensible-Intra-Area-Prefix-LSA

   # Traffic Classes:  The number of traffic classes that will be
      specified.  Each traffic class has, first, a metric TLV, and then
      one or more other TLVs, normally including a Destination Prefix
      TLV.

4.  IANA Considerations

   This section will request LSID values for the LSAs defined, plus
   define a registry for optional fields.  This is deferred to the -01
   version of the draft.

5.  Security Considerations

   To be considered.




Baker                   Expires August 21, 2013                [Page 10]


Internet-Draft                                             February 2013


6.  Privacy Considerations

   To be considered.

7.  Acknowledgements

8.  Change Log

   Initial Version:  February 2013

9.  References

9.1.  Normative References

   [ISO.10589.1992]
              International Organization for Standardization,
              "Intermediate system to intermediate system intra-domain-
              routing routine information exchange protocol for use in
              conjunction with the protocol for providing the
              connectionless-mode Network Service (ISO 8473)", ISO
              Standard 10589, 1992.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC2328]  Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.

   [RFC5340]  Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF
              for IPv6", RFC 5340, July 2008.

9.2.  Informative References

   [PATRICIA]
              Morrison, D.R., "Practical Algorithm to Retrieve
              Information Coded in Alphanumeric", Journal of the ACM
              15(4) pp514-534, October 1968.

   [RFC4915]  Psenak, P., Mirtorabi, S., Roy, A., Nguyen, L., and P.
              Pillay-Esnault, "Multi-Topology (MT) Routing in OSPF", RFC
              4915, June 2007.

Appendix A.  FIB Design









Baker                   Expires August 21, 2013                [Page 11]


Internet-Draft                                             February 2013


   While the design of the Forwarding Information Base is not a matter
   for standardization, as it only has to work correctly, not
   interoperate with something else, the design of a FIB for this type
   of lookup may differ from approaches used in destination routing.  We
   describe one possible approach that is known to work, from the
   perspective of a proof of concept.

A.1.  Linux Source-Address Forwarding

   The University of Waikato has added to the Linux Advanced Routing &
   Traffic Control facility the ability to maintain multiple FIBS, one
   for each of a set of prefixes.  Implementing source/destination
   routing using this mechanism is not difficult.

   The router must know what source prefixes might be used in its
   domain.  This may be by configuration or, at least in concept,
   learned from the routing protocols themselves.  In whichever way that
   is done, one can imagine two fundamental FIB structures to serve N
   source prefixes; N FIBs, one per prefix, or N+1 FIBs, one per prefix
   plus one for destinations for which the source prefix is unspecified.

A.1.1.  One FIB per source prefix

   In an implementation with one FIB per source prefix, the routing
   algorithm has two possibilities.

   o  If it calculates a route to a prefix (such as a default route)
      associated with a given source prefix, it stores the route in the
      FIB for the relevant source prefix.

   o  If it calculates a route for which the source prefix is
      unspecified, it stores that route in all N FIBs.

   When forwarding a datagram, the IP forwarder looks at the source
   address of the datagram to determine which FIB it should use.  If it
   is from an address for which there is no FIB, the forwarder discards
   the datagram as containing a forged source address.  If it is from an
   address within one of the relevant prefixes, it looks up the
   destination in the indicated FIB and forwards it in the usual way.

   The argument for this approach is simplicity: there is one place to
   look in making a forwarding decision for any given datagram.  The
   argument against it is memory space; it is likely that the FIBs will
   be similar, but every destination route not associated with a source
   prefix is duplicated in each FIB.  In addition, since it
   automatically removes traffic whose source address is not among the
   configured list, it limits the possibility of user software using
   improper addresses.



Baker                   Expires August 21, 2013                [Page 12]


Internet-Draft                                             February 2013


A.1.2.  One FIB per source prefix plus a general FIB

   In an implementation with N+1 FIBs, the algorithm is slightly more
   complex.

   o  If it calculates a route to a prefix (such as a default route)
      associated with a given source prefix, it stores the route in the
      FIB for the relevant source prefix.

   o  If it calculates a route for which the source prefix is
      unspecified, it stores that route in the FIB that is not
      associated with a source prefix.

   When forwarding a datagram, the IP forwarder looks at the source
   address of the datagram to determine which FIB it should use.  If it
   is from one of the configured prefixes, it looks the destination up
   in the indicated FIB.  In any event it also looks the destination up
   in the "unspecified source address" FIB.  If the destination is found
   in only one of the two, the indicated route is followed.  If the
   destination is found in both, the more specific route is followed.

   The argument for this approach is memory space; if a large percentage
   of routes are only in the general FIB, such as when egress routing is
   used for the default route and all other routes are internal, the
   other FIBs are likely to be very small - perhaps only a single
   default route.  The argument against this approach is complexity:
   most lookups if not all will be done in a prefix-specific FIB and in
   the general FIB.

A.2.  PATRICIA

   One approach is a [PATRICIA] Tree.  This is a relative of a Trie, but
   unlike a Trie, need not use every bit in classification, and does not
   need the bits used to be contiguous.  It depends on treating the bit
   string as a set of slices of some size, potentially of different
   sizes.  Slice width is an implementation detail; since the algorithm
   is most easily described using a slice of a single bit, that will be
   presumed in this description.

A.2.1.  Virtual Bit String

   It is quite possible to view the fields in a datagram header
   incorporated into the classification tuple as a virtual bit string
   such as is shown in Figure 4.  This bit string has various regions
   within it.  Some vary and are therefore useful in a radix tree
   lookup.  Some may be essentially constant - all global IPv6 addresses
   at this writing are within 2000::/3, for example, so while it must be
   tested to assure a match, incorporating it into the radix tree may



Baker                   Expires August 21, 2013                [Page 13]


Internet-Draft                                             February 2013


   not be very helpful in classification.  Others are ignored; if the
   destination is a remote /64, we really don't care what the EID is.
   In addition, due to variation in prefix length and other details, the
   widths of those fields vary among themselves.  The algorithm the FIB
   implements, therefore, must efficiently deal with the fact of a
   discontiguous lookup key.

   +---------------------+----------------------+-----+-----------+
   |Destination Prefix   |Source Prefix         |DSCP | Flow Label|
   +------+------+-------+------+-------+-------+-----+-----------+
    Common|Varying|Ignored|Common|Varying|Ignored|Varying or ignored

        Figure 4: Treating a traffic class as a virtual bit string

A.2.2.  Tree Construction

   The tree is constructed by recursive slice-wise decomposition.  At
   each stage, the input is a set of classes to be classified.  At each
   stage, the result is the addition of a lookup node in the tree that
   identifies the location of its slice in the virtual bit string (which
   might be a bit number), the width of the slice to be inspected, and
   an enumerated set of results.  Each result is a similar set of
   classes, and is analyzed in a similar manner.

   The analysis is performed by enumerating which bits that have not
   already been considered are best suited to classification.  For a
   slice of N bits, one wants to select a slide that most evenly divides
   the set of classes into 2^N subsets.  If one or more bits in the
   slice is ignored in some of the classes, those classes must be
   included in every subset, as the actual classification of them will
   depend on other bits.

   Input:{2001:db8::/32, ::/0, *, *}
         {2001:db8:1::/48, ::/0, AF41, *}
         {2001:db8:1::/48, ::/0, AF42, *}
         {2001:db8:1::/48, ::/0, AF43, *}
   Common parts: Destination prefix 2001:dba, source prefix, and label
   Varying parts: DSCP and the third set of sixteen bits in the
                  destination prefix
   One possible decomposition:
   (1) slice = DSCP
       enumerated cases:
   (a) { {2001:db8::/32, ::/0, *, *}, {2001:db8:1::/48, ::/0, AF41, *} }
   (b) { {2001:db8::/32, ::/0, *, *}, {2001:db8:1::/48, ::/0, AF42, *} }
   (c) { {2001:db8::/32, ::/0, *, *}, {2001:db8:1::/48, ::/0, AF43, *} }
   (2) slice = third sixteen bit field in destination
       This divides each enumerated case into those containing 0001 and
       "everything else", which would imply 2001:db8::/32



Baker                   Expires August 21, 2013                [Page 14]


Internet-Draft                                             February 2013


                              (1) DSCP
                    --------------------------
                   (1a)       (1b)         (1c)
                  /    \     /    \       /    \
                /32   /48  /32   /48    /32   /48

                      Figure 5: Example PATRICIA Tree

A.2.3.  Tree Lookup

   To look something up in a PATRICIA Tree, one starts at the root of
   the tree and performs the indicated comparisons recursively walking
   down the tree until one reaches a terminal node.  When the enumerated
   subset is empty or contains only a single class, classification
   stops.  Either classification has failed (there was no matching
   class, or one has presumably found the indicated class.  At that
   point, every bit in the virtual bit string must be compared to the
   classifier; classification is accepted on a perfect match.

   In the example in Figure 5, if a packet {2001:db8:1:2:3:4:5:6,
   2001:db8:2:3:4:5:6:7, AF41, 0} arrives, we start at the root.  Since
   it is an AF41 packet, we deduce that case (1a) applies, and since the
   destination has 0001 in the third sixteen bit field of the
   destination address, we are comparing to {2001:db8:1::/48, ::/0,
   AF41, *}. Since the destination address is within 2001:db8:1::/48,
   classification as that succeeds.

Author's Address

   Fred Baker
   Cisco Systems
   Santa Barbara, California  93117
   USA

   Email: fred@cisco.com















Baker                   Expires August 21, 2013                [Page 15]