Internet Draft




Internet Draft                                        Yakov Rekhter
Expiration date:January 1998                          cisco Systems
                                                        Bruce Davie
                                                      cisco Systems
                                                          Dave Katz
                                              Juniper Networks Inc.
                                                         Eric Rosen
                                                      cisco Systems
                                                     George Swallow
                                                      cisco Systems
                                                     Dino Farinacci
                                                      cisco Systems
                                                          July 1997


                 Tag Switching Architecture - Overview

                  draft-rekhter-tagswitch-arch-01.txt


1. Status of this Memo

   This document is an Internet Draft. 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 may be updated, replaced, or obsoleted by
   other documents at any time. It is not appropriate to use Internet
   Drafts as reference material or to cite them other than as a "working
   draft" or "work in progress."

   Please check the 1id-abstracts.txt listing contained in the
   internet-drafts Shadow Directories on nic.ddn.mil, nnsc.nsf.net,
   nic.nordu.net, ftp.nisc.sri.com, or munnari.oz.au to learn the
   current status of any Internet Draft.














                                                                [Page 1]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


2. Abstract

   This document provides an overview of tag switching. Tag switching is
   a way to combine the label-swapping forwarding paradigm with network
   layer routing. This has several advantages. Tags can have a wide
   spectrum of forwarding granularities, so at one end of the spectrum a
   tag could be associated with a group of destinations, while at the
   other a tag could be associated with a single application flow. At
   the same time forwarding based on tag switching, due to its
   simplicity, is well suited to high performance forwarding. These
   factors facilitate the development of a routing system which is both
   functionally rich and scalable. Finally, tag switching simplifies
   integration of routers and ATM switches by employing common
   addressing, routing, and management procedures.



3. Introduction

   Continuous growth of the Internet demands higher bandwidth within the
   Internet Service Providers (ISPs). However, growth of the Internet is
   not the only driving factor for higher bandwidth - demand for higher
   bandwidth also comes from emerging multimedia applications. Demand
   for higher bandwidth, in turn, requires higher forwarding performance
   for both multicast and unicast traffic.

   The growth of the Internet also demands improved scaling properties
   of the Internet routing system. The ability to contain the volume of
   routing information maintained by individual routers and the ability
   to build a hierarchy of routing knowledge are essential to support a
   high quality, scalable routing system.

   While the destination-based forwarding paradigm is adequate in many
   situations, we already see examples where it is no longer adequate.
   The ability to overcome the rigidity of destination-based forwarding
   and to have more flexible control over how traffic is routed is
   likely to become more and more important.

   We see the need to improve forwarding performance while at the same
   time adding routing functionality to support multicast, allowing more
   flexible control over how traffic is routed, and providing the
   ability to build a hierarchy of routing knowledge. Moreover, it
   becomes more and more crucial to have a routing system that can
   support graceful evolution to accommodate new and emerging
   requirements.

   Tag switching is a technology that provides an efficient solution to
   these challenges. Tag switching blends the flexibility and rich



                                                                [Page 2]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


   functionality provided by Network Layer routing with the simplicity
   provided by the label swapping forwarding paradigm. The simplicity of
   the tag switching forwarding paradigm (label swapping) enables
   improved forwarding performance, while maintaining competitive
   price/performance. By associating a wide range of forwarding
   granularities with a tag, the same forwarding paradigm can be used to
   support a wide variety of routing functions, such as destination-
   based routing, multicast, hierarchy of routing knowledge, and
   flexible routing control. Finally, a combination of simple
   forwarding, a wide range of forwarding granularities, and the ability
   to evolve routing functionality while preserving the same forwarding
   paradigm enables a routing system that can gracefully evolve to
   accommodate new and emerging requirements.



4. Tag Switching components

   Tag switching consists of two components: forwarding and control. The
   forwarding component uses the tag information (tags) carried by
   packets and the tag forwarding information maintained by a tag switch
   to perform packet forwarding. The control component is responsible
   for maintaining correct tag forwarding information among a group of
   inter- connected tag switches.

   Segregating control and forwarding into separate components promotes
   modularity, which in turn enables to build a system that can
   gracefully evolve to accommodate new and emerging requirements.


5. Forwarding component

   The fundamental forwarding paradigm employed by tag switching is
   based on the notion of label swapping. When a packet with a tag is
   received by a tag switch, the switch uses the tag as an index in its
   Tag Information Base (TIB). Each entry in the TIB consists of an
   incoming tag, and one or more sub-entries of the form . If the switch
   finds an entry with the incoming tag equal to the tag carried in the
   packet, then for each  in the entry the switch replaces the tag in
   the packet with the outgoing tag, replaces the link level information
   (e.g MAC address) in the packet with the outgoing link level
   information, and forwards the packet over the outgoing interface.

   From the above description of the forwarding component we can make
   several observations. First, the forwarding decision is based on the
   exact match algorithm using a fixed length, fairly short tag as an



                                                                [Page 3]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


   index. This enables a simplified forwarding procedure, relative to
   longest match forwarding traditionally used at the network layer.
   This in turn enables higher forwarding performance (higher packets
   per second). The forwarding procedure is simple enough to allow a
   straightforward hardware implementation.

   A second observation is that the forwarding decision is independent
   of the tag's forwarding granularity. For example, the same forwarding
   algorithm applies to both unicast and multicast - a unicast entry
   would just have a single (outgoing tag, outgoing interface, outgoing
   link level information) sub-entry, while a multicast entry may have
   one or more (outgoing tag, outgoing interface, outgoing link level
   information) sub-entries. (For multi-access links, the outgoing link
   level information in this case would include a multicast MAC
   address.) This illustrates how with tag switching the same forwarding
   paradigm can be used to support different routing functions (e.g.,
   unicast, multicast, etc...)

   The simple forwarding procedure is thus essentially decoupled from
   the control component of tag switching. New routing (control)
   functions can readily be deployed without disturbing the forwarding
   paradigm. This means that it is not necessary to re-optimize
   forwarding performance (by modifying either hardware or software) as
   new routing functionality is added.

   In the tag switching architecture, various implementation options are
   acceptable. For example, support for network layer forwarding by a
   tag switch (i.e., forwarding based on the network layer header as
   opposed to a tag) is optional. Moreover, use of network layer
   forwarding may be constrained to handling network layer control
   traffic only. (Note, however, that a tag switch must be able to
   source and sink network layer packets, e.g. to participate in network
   layer routing protocols)

   For the purpose of handling network layer hop count (time-to-live)
   the architecture allows two alternatives: network layer hops may
   correspond directly to hops formed by tag switches, or one network
   layer hop may correspond to several tag switched hops.

   When a switch receives a packet with a tag, and the TIB maintained by
   the switch has no entry with the incoming tag equal to the tag
   carried by the packet, or the entry exists, the outgoing tag entry is
   entry, and the entry does not indicate local delivery to the switch,
   the switch may either (a) discard the packet, or (b) strip the tag
   information, and submit the packet for network layer processing.
   Support for the latter is optional (as support for network layer
   forwarding is optional). Note that it may not always be possible to
   successfully forward a packet after stripping a tag even if a tag



                                                                [Page 4]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


   switch supports network layer forwarding.

   The architecture allows a tag switch to maintain either a single TIB
   per tag switch, or a TIB per interface. Moreover, a tag switch could
   mix both of these options - some tags could be maintained in a single
   TIB, while other tags could be maintained in a TIB associated with
   individual interfaces.


5.1. Tag encapsulation

   Tag switching clearly requires a tag to be carried in each packet.
   The tag information can be carried in a variety of ways:


      - as a small "shim" tag header inserted between the layer 2 and
      the Network Layer headers;

      - as part of the layer 2 header, if the layer 2 header provides
      adequate semantics (e.g., Frame Relay, or ATM);

      - as part of the Network Layer header (e.g., using the Flow Label
      field in IPv6 with appropriately modified semantics).


   It is therefore possible to implement tag switching over virtually
   any media type including point-to-point links, multi-access links,
   and ATM. At the same time the forwarding component allows specific
   optimizations for particular media (e.g., ATM).

   Observe also that the tag forwarding component is Network Layer
   independent. Use of control component(s) specific to a particular
   Network Layer protocol enables the use of tag switching with
   different Network Layer protocols.


6. Control component

   Essential to tag switching is the notion of binding between a tag and
   Network Layer routing (routes). The control component is responsible
   for creating tag bindings, and then distributing the tag binding
   information among tag switches. Creating a tag binding involves
   allocating a tag, and then binding a tag to a route. The distribution
   of tag binding information among tag switches could be accomplished
   via several options:

      - piggybacking on existing routing protocols




                                                                [Page 5]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


      - using a separate Tag Distribution Protocol (TDP)

   While the architecture supports distribution of tag binding
   information that is independent of the underlying routing protocols,
   the architecture acknowledges that considerable optimizations can be
   achieved in some cases by small enhancements of existing protocols to
   enable piggybacking tag binding information on these protocols.

   One important characteristic of the tag switching architecture is
   that creation of tag bindings is driven primarily by control traffic
   rather than by data traffic. Control traffic driven creation of tag
   bindings has several advantages, as compared to data traffic driven
   creation of tag bindings. For one thing, it minimizes the amount of
   additional control traffic needed to distribute tag binding
   information, as tag binding information is distributed only in
   response to control traffic, independent of data traffic. It also
   makes the overall scheme independent of and insensitive to the data
   traffic profile/pattern. Control traffic driven creation of tag
   binding improves forwarding performance, as tags are precomputed
   (prebound) before data traffic arrives, rather than being created as
   data traffic arrives. It also simplifies the overall system behavior,
   as the control plane is controlled solely by control traffic, rather
   than by a mix of control and data traffic.

   Another important characteristic of the tag switching architecture is
   that distribution and maintenance of tag binding information is
   consistent with distribution and maintenance of the associated
   routing information. For example, distribution of tag binding
   information for tags associated with unicast routing is based on the
   technique of incremental updates with explicit acknowledgment. This
   is very similar to the way unicast routing information gets
   distributed by such protocols as OSPF and BGP. In contrast,
   distribution of tag binding information for tags associated with
   multicast routing is based on period updates/ refreshes, without any
   explicit acknowledgments. This is consistent with the way multicast
   routing information is distributed by such protocols as PIM.

   To provide good scaling characteristics, while also accommodating
   diverse routing functionality, tag switching supports a wide range of
   forwarding granularities. At one extreme a tag could be associated
   (bound) to a group of routes (more specifically to the Network Layer
   Reachability Information of the routes in the group). At the other
   extreme a tag could be bound to an individual application flow (e.g.,
   an RSVP flow). A tag could also be bound to a multicast tree. In
   addition, a tag may be bound to a path that has been selected for a
   certain set of packets based on some policy (e.g. an explicit route).

   The control component is organized as a collection of modules, each



                                                                [Page 6]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


   designed to support a particular routing function. To support new
   routing functions, new modules can be added. The architecture does
   not mandate a prescribed set of modules that have to be supported by
   every tag switch.

   The following describes some of the modules.


6.1. Destination-based routing

   In this section we describe how tag switching can support
   destination-based routing. Recall that with destination-based routing
   a router makes a forwarding decision based on the destination address
   carried in a packet and the information stored in the Forwarding
   Information Base (FIB) maintained by the router. A router constructs
   its FIB by using the information it receives from routing protocols
   (e.g., OSPF, BGP).

   To support destination-based routing with tag switching, a tag
   switch, just like a router, participates in routing protocols (e.g.,
   OSPF, BGP), and constructs its FIB using the information it receives
   from these protocols.

   There are three permitted methods for tag allocation and Tag
   Information Base (TIB) management: (a) downstream tag allocation, (b)
   downstream tag allocation on demand, and (c) upstream tag allocation.
   In all cases, a switch allocates tags and binds them to address
   prefixes in its FIB. In downstream allocation, the tag that is
   carried in a packet is generated and bound to a prefix by the switch
   at the downstream end of the link (with respect to the direction of
   data flow). On demand allocation means that tags will only be
   allocated and distributed by the downstream switch when it is
   requested to do so by the upstream switch. Method (b) is most useful
   in ATM networks (see Section 8). In upstream allocation, tags are
   allocated and bound at the upstream end of the link. Note that in
   downstream allocation, a switch is responsible for creating tag
   bindings that apply to incoming data packets, and receives tag
   bindings for outgoing packets from its neighbors. In upstream
   allocation, a switch is responsible for creating tag bindings for
   outgoing tags, i.e. tags that are applied to data packets leaving the
   switch, and receives bindings for incoming tags from its neighbors.

   The downstream tag allocation scheme operates as follows: for each
   route in its FIB the switch allocates a tag, creates an entry in its
   Tag Information Base (TIB) with the incoming tag set to the allocated
   tag, and then advertises the binding between the (incoming) tag and
   the route to other adjacent tag switches. The advertisement could be
   accomplished by either piggybacking the binding on top of the



                                                                [Page 7]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


   existing routing protocols, or by using a separate Tag Distribution
   Protocol (TDP). When a tag switch receives tag binding information
   for a route, and that information was originated by the next hop for
   that route, the switch places the tag (carried as part of the binding
   information) into the outgoing tag of the TIB entry associated with
   the route. This creates the binding between the outgoing tag and the
   route.

   With the downstream on demand tag allocation scheme, operation is as
   follows. For each route in its FIB, the switch identifies the next
   hop for that route. It then issues a request (via TDP) to the next
   hop for a tag binding for that route. When the next hop receives the
   request, it allocates a tag, creates an entry in its TIB with the
   incoming tag set to the allocated tag, and then returns the binding
   between the (incoming) tag and the route to the switch that sent the
   original request. When the switch receives the binding information,
   the switch creates an entry in its TIB, and sets the outgoing tag in
   the entry to the value received from the next hop. Handling of data
   packets is as for downstream allocation. The main application for
   this mode of operation is with ATM switches, as described in Section
   8.

   The upstream tag allocation scheme is used as follows. If a tag
   switch has one or more point-to-point interfaces, then for each route
   in its FIB whose next hop is reachable via one of these interfaces,
   the switch allocates a tag, creates an entry in its TIB with the
   outgoing tag set to the allocated tag, and then advertises to the
   next hop (via TDP) the binding between the (outgoing) tag and the
   route. When a tag switch that is the next hop receives the tag
   binding information, the switch places the tag (carried as part of
   the binding information) into the incoming tag of the TIB entry
   associated with the route.

   Note that, while we have described upstream allocation for the sake
   of completeness, we have found the two downstream allocation methods
   adequate for all practical purposes so far.

   Independent of which tag allocation method is used, once a TIB entry
   is populated with both incoming and outgoing tags, the tag switch can
   forward packets for routes bound to the tags by using the tag
   switching forwarding algorithm (as described in Section 5).

   When a tag switch creates a binding between an outgoing tag and a
   route, the switch, in addition to populating its TIB, also updates
   its FIB with the binding information. This enables the switch to add
   tags to previously untagged packets.

   So far we have described how a tag could be bound to a single route,



                                                                [Page 8]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


   creating a one-to-one mapping between routes and tags. However, under
   certain conditions it is possible to bind a tag not just to a single
   route, but to a group of routes, creating a many-to-one mapping
   between routes and tags. Consider a tag switch that is connected to a
   router.  It is quite possible that the switch uses the router as the
   next hop not just for one route, but for a group of routes. Under
   these conditions the switch does not have to allocate distinct tags
   to each of these routes - one tag would suffice. The distribution of
   tag binding information is unaffected by whether there is a one-to-
   one or one-to-many mapping between tags and routes. Now consider a
   tag switch that receives from one of its neighbors (tag switching
   peers) tag binding information for a set of routes, such that the set
   is bound to a single tag. If the switch decides to use some or all of
   the routes in the set, then for these routes the switch does not need
   to allocate individual tags - one tag would suffice. Such an approach
   may be valuable when tags are a precious resource. Note that the
   ability to support many-to-one mapping makes no assumptions about the
   routing protocols being used.

   When a tag switch adds a tag to a previously untagged packet the tag
   could be either associated with the route to the destination address
   carried in the packet, or with the route to some other tag switch
   along the path to the destination (in some cases the address of that
   other tag switch could be gleaned from network layer routing
   protocols). The latter option provides yet another way of mapping
   multiple routes into a single tag. However, this option is either
   dependent on particular routing protocols, or would require a
   separate mechanism for discovering tag switches along a path.

   To understand the scaling properties of tag switching in conjunction
   with destination-based routing, observe that the total number of tags
   that a tag switch has to maintain can not be greater than the number
   of routes in the switch's FIB. Moreover, as we have just seen, the
   number of tags can be much less than the number of routes. Thus, much
   less state is required than would be the case if tags were allocated
   to individual flows.

   In general, a tag switch will try to populate its TIB with incoming
   and outgoing tags for all routes to which it has reachability, so
   that all packets can be forwarded by simple label swapping. Tag
   allocation is thus driven by topology (routing), not data traffic -
   it is the existence of a FIB entry that causes tag allocations, not
   the arrival of data packets.

   Use of tags associated with routes, rather than flows, also means
   that there is no need to perform flow classification procedures for
   all the flows to determine whether to assign a tag to a flow. That,
   in turn, simplifies the overall scheme, and makes it more robust and



                                                                [Page 9]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


   stable in the presence of changing traffic patterns.

   Note that when tag switching is used to support destination-based
   routing, tag switching does not completely eliminate the need to
   perform normal Network Layer forwarding at some network elements.
   First of all, to add a tag to a previously untagged packet requires
   normal Network Layer forwarding. This function could be performed by
   the first hop router, or by the first router on the path that is able
   to participate in tag switching. In addition, whenever a tag switch
   aggregates a set of routes (e.g., by using the technique of
   hierarchical routing), into a single route, and the routes do not
   share a common next hop, the switch needs to perform Network Layer
   forwarding for packets carrying the tag associated with the
   aggregated route. However, one could observe that the number of
   places where routes get aggregated is smaller than the total number
   of places where forwarding decisions have to be made. Moreover, quite
   often aggregation is applied to only a subset of the routes
   maintained by a tag switch. As a result, on average a packet can be
   forwarded most of the time using the tag switching algorithm. Note
   that many tag switches may not need to perform any network layer
   forwarding.


6.2. Hierarchy of routing knowledge

   The IP routing architecture models a network as a collection of
   routing domains. Within a domain, routing is provided via interior
   routing (e.g., OSPF), while routing across domains is provided via
   exterior routing (e.g., BGP). However, all routers within domains
   that carry transit traffic (e.g., domains formed by Internet Service
   Providers) have to maintain information provided by not just interior
   routing, but exterior routing as well, even if only some of these
   routers participate in exterior routing. That creates certain
   problems. First of all, the amount of this information is not
   insignificant. Thus it places additional demand on the resources
   required by the routers.  Moreover, increase in the volume of routing
   information quite often increases routing convergence time. This, in
   turn, degrades the overall performance of the system.

   Tag switching allows complete decoupling of interior and exterior
   routing. With tag switching only tag switches at the border of a
   domain would be required to maintain routing information provided by
   exterior routing - all other switches within the domain would just
   maintain routing information provided by the domains interior routing
   (which is usually significantly smaller than the exterior routing
   information), with no "leaking" of exterior routing information into
   interior routing. This, in turn, reduces the routing load on non-
   border switches, and shortens routing convergence time.



                                                               [Page 10]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


   To support this functionality, tag switching allows a packet to carry
   not one but a set of tags, organized as a stack. A tag switch could
   either swap the tag at the top of the stack, or pop the stack, or
   swap the tag and push one or more tags into the stack.

   Consider a tag switch that is at the border of a routing domain. This
   switch maintains both exterior and interior routes. The interior
   routes provide routing information and tags to all the other tag
   switches within the domain. For each exterior route that the switch
   receives from some other border tag switch that is in the same domain
   as the local switch, the switch maintains not just a tag associated
   with the route, but also a tag associated with the route to that
   other border tag switch. Moreover, for inter-domain routing protocols
   that are capable of passing the "third-party" next hop information
   the switch would maintain a tag associated with the route to the next
   hop, rather than with the route to the border tag switch from whom
   the local switch received the exterior route.

   When a packet is forwarded between two (border) tag switches in
   different domains, the tag stack in the packet contains just one tag
   (associated with an exterior route). However, when a packet is
   forwarded within a domain, the tag stack in the packet contains not
   one, but two tags (the second tag is pushed by the domain's ingress
   border tag switch). The tag at the top of the stack provides packet
   forwarding to an appropriate egress border tag switch (or the
   "third-party" next hop), while the next tag in the stack provides
   correct packet forwarding at the egress switch (or at the "third-
   party" next hop). The stack is popped by either the egress switch (or
   the "third-party" next hop) or by the penultimate (with respect to
   the egress switch/"third-party" next hop) switch.

   One could observe that when tag switching is confined to a single
   routing domain, the above still could be used to decouple interior
   from exterior routing, similar to what was described above. However,
   in this case a border tag switch wouldn't maintain tags associated
   with each exterior route, and forwarding between domains would be
   performed at the network layer.

   The control component used in this scenario is fairly similar to the
   one used with destination-based routing. In fact, the only essential
   difference is that in this scenario the tag binding information is
   distributed both among physically adjacent tag switches, and among
   border tag switches within a single domain. One could also observe
   that the latter (distribution among border switches) could be
   trivially accommodated by very minor extensions to BGP.

   The notion of supporting hierarchy of routing knowledge with tag
   switching is not limited to the case of exterior/interior routing,



                                                               [Page 11]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


   but could be applicable to other cases where the hierarchy of routing
   knowledge is possible. Moreover, while the above describes only a
   two-level hierarchy of routing knowledge, the tag switching
   architecture does not impose limits on the depth of the hierarchy.

   In the presence of hierarchy of routing knowledge a tag switched path
   at the level N in the hierarchy has to have its endpoints at tag
   switches that are at border between the level N and (N-1) in the
   hierarchy (level 0 in the hierarchy corresponds to an untagged path).


6.3. Multicast

   Essential to multicast routing is the notion of spanning trees.
   Multicast routing procedures (e.g., PIM) are responsible for
   constructing such trees (with receivers as leafs), while multicast
   forwarding is responsible for forwarding multicast packets along such
   trees. Thus, to support a multicast forwarding function with tag
   switching we need to be able to associate a tag with a multicast
   tree.  The following describes the procedures for allocation and
   distribution of tags for multicast.

   When tag switching is used for multicast, it is important that tag
   switching be able to utilize multicast capabilities provided by the
   Data Link layer (e.g., multicast capabilities provided by Ethernet).
   To be able to do this, an (upstream) tag switch connected to a given
   Data Link subnetwork should use the same tag when forwarding a
   multicast packet to all of the (downstream) switches on that
   subnetwork. This way the packet will be multicasted at the Data Link
   layer over the subnetwork. To support this, all tag switches that are
   part of a given multicast tree and are on a common subnetwork must
   agree on a common tag that would be used for forwarding multicast
   packets along the tree over the subnetwork. Moreover, since multicast
   forwarding is based on Reverse Path Forwarding (RPF), it is crucial
   that, when a tag switch receives a multicast packet, a tag carried in
   a packet must enable the switch to identify both (a) a particular
   multicast group, as well as (b) the previous hop (upstream) tag
   switch that sent the packet.

   To support the requirements outlined in the previous paragraph, the
   tag switching architecture assumes that (a) multicast tags are
   associated with interfaces on a tag switch (rather than with a tag
   switch as a whole), (b) the tag space that a tag switch could use for
   allocating tags for multicast is partitioned into non-overlapping
   regions among all the tag switches connected to a common Data Link
   subnetwork, and (c) there are procedures by which tag switches that
   belong to a common multicast tree and are on a common Data Link
   subnetwork agree on the tag switch that is responsible for allocating



                                                               [Page 12]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


   a tag for the tree.

   One possible way of partitioning tag space into non-overlapping
   regions among tag switches connected to a common subnetwork is for
   each tag switch to claim a region of the space and announce this
   region to its neighbors. Conflicts are resolved based on the IP
   address of the contending switches (the higher address wins, the
   lower retries). Once the tag space is partitioned among tag switches,
   the switches may create bindings between tags and multicast trees
   (routes).

   At least in principle there are two possible ways to create bindings
   between tags and multicast trees (routes). With the first alternative
   for a set of tag switches that share a common Data Link subnetwork,
   the tag switch that is upstream with respect to a particular
   multicast tree allocates a tag (out of its own region that does not
   overlap with the regions of other switches on the subnetwork), binds
   the tag to a multicast route, and then advertises the binding to all
   the (downstream) switches on the subnetwork. With the second
   alternative, one of the tag switches that is downstream with respect
   to a particular multicast tree allocates a tag (out of its own region
   that does not overlap with the regions of other switches on the
   subnetwork), binds the tag to a multicast route, and then advertises
   the binding to all the switches (both downstream and upstream) on the
   subnetwork. Usually the first tag switch to join the group is the one
   that performs the allocation.

   Each of the above alternatives has its own trade-offs. The first
   alternative is fairly simple - one upstream router does the tag
   binding and multicasts the binding downstream. However, the first
   alternative may create uneven distribution of allocated tags, as some
   tag switches on a common subnetwork may have more upstream multicast
   sources than the others. Also, changes in topology could result in
   upstream neighbor changes, which in turn would require tag re-
   binding. Finally, one could observe that distributing tag binding
   from upstream towards downstream is inconsistent with the direction
   of multicast routing information distribution (from downstream
   towards upstream).

   The second alternative, even if more complex that the first one, has
   its own advantages. For one thing, it makes distribution of multicast
   tag binding consistent with the distribution of unicast tag binding.
   It also makes distribution of multicast tag binding consistent with
   the distribution of multicast routing information. This, in turn,
   allows the piggybacking of tag binding information on existing
   multicast routing protocols (PIM). This alternative also avoids the
   need for tag re-binding when there are changes in upstream neighbor.
   Finally it is more likely to provide more even distribution of



                                                               [Page 13]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


   allocated tags, as compared to the first alternative. Note that this
   approach does require a mechanism to choose the tag allocator from
   among the downstream tag switches on the subnetwork.


6.4. Quality of service

   Two mechanisms are needed for providing a range of qualities of
   service to packets passing through a router or a tag switch. First,
   we need to classify packets into different classes. Second, we need
   to ensure that the handling of packets is such that the appropriate
   QOS characteristics (bandwidth, loss, etc.) are provided to each
   class.

   Tag switching provides an easy way to mark packets as belonging to a
   particular class after they have been classified the first time.
   Initial classification could be done using configuration information
   (e.g., all traffic from a certain interface) or using information
   carried in the network layer or higher layer headers (e.g., all
   packets between a certain pair of hosts). A tag corresponding to the
   resultant class would then be applied to the packet. Tagged packets
   can then be efficiently handled by the tag switching routers in their
   path without needing to be reclassified. The actual scheduling and
   queueing of packets is largely orthogonal - the key point here is
   that tag switching enables simple logic to be used to find the state
   that identifies how the packet should be scheduled.

   Tag switching can, for example, be used to support a small number of
   classes of service in a service provider network (e.g. premium and
   standard). On frame-based media, the class can be encoded by a field
   in the tag header. On ATM tag switches, additional tags can be
   allocated to differentiate the different classes. For example, rather
   than having one tag for each destination prefix in the FIB, an ATM
   tag switch could have two tags per prefix, one to be used by premium
   traffic and one by standard. Thus a tag binding in this case is a
   triple consisting of . Such a tag would be
   used both to make a forwarding decision and to make a scheduling
   decision, e.g., by selecting the appropriate queue in a weighted fair
   queueing (WFQ) scheduler.

   To provide a finer granularity of QOS, tag switching can be used with
   RSVP. We propose a simple extension to RSVP in which a tag object is
   defined. Such an object can be carried in an RSVP reservation message
   and thus associated with a session. Each tag capable router assigns a
   tag to the session and passes it upstream with the reservation
   message. Thus the association of tags with RSVP sessions works very
   much like the binding of tags to routes with downstream allocation.
   Note, however, that binding is accomplished using RSVP rather than



                                                               [Page 14]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


   TDP. (It would be possible to use TDP, but it is simpler to extend
   RSVP to carry tags and this ensures that tags and reservation
   information are communicated in a similar manner.)

   When data packets are transmitted, the first router in the path that
   is tag-capable applies the tag that it received from its downstream
   neighbor. This tag can be used at the next hop to find the
   corresponding reservation state, to forward and schedule the packet
   appropriately, and to find the suitable outgoing tag value provided
   by the next hop.  Note that tag imposition could also be performed at
   the sending host.


6.5. Flexible routing (explicit routes)

   One of the fundamental properties of destination-based routing is
   that the only information from a packet that is used to forward the
   packet is the destination address. While this property enables highly
   scalable routing, it also limits the ability to influence the actual
   paths taken by packets. This, in turn, limits the ability to evenly
   distribute traffic among multiple links, taking the load off highly
   utilized links, and shifting it towards less utilized links. For
   Internet Service Providers (ISPs) who support different classes of
   service, destination-based routing also limits their ability to
   segregate different classes with respect to the links used by these
   classes. Some of the ISPs today use Frame Relay or ATM to overcome
   the limitations imposed by destination-based routing. Tag switching,
   because of the flexible granularity of tags, is able to overcome
   these limitations without using either Frame Relay or ATM.

   Another application where destination-based routing is no longer
   adequate is routing with resource reservations (QOS routing).
   Increasing the number of ways by which a particular reservation could
   traverse a network may improve the success of the reservation.
   Increasing the number of ways, in turn, requires the ability to
   explore paths that are not constrained to the ones constructed solely
   based on destination.

   To provide forwarding along paths that are different from the paths
   determined by destination-based routing, the control component of tag
   switching allows installation of tag bindings in tag switches that do
   not correspond to the destination-based routing paths.

   One possible alternative for supporting explicit routes is to allow
   TDP to carry information about an explicit route, where such a route
   could be expressed as a sequence of tag switches. Another alternative
   is to use tag-capable RSVP (see Section 6.4) as a mechanism to
   distribute tag bindings, and to augment RSVP with the ability to



                                                               [Page 15]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


   steer the PATH message along a particular (explicit) route. Finally,
   it is also possible in principle to use some form of source route
   (e.g., SDRP, GRE) to steer RSVP PATH messages carrying tag bindings
   along a particular path. Note, however, that this would require a
   change to the way in which RSVP handles PATH messages, as it would be
   necessary to store the source route as part of the PATH state.


7. Tag Forwarding Granularities and Forwarding Equivalence Classes

   A conventional router has some sort of structure or set of structures
   which may be called a "forwarding table", which has a finite number
   of entries. Whenever a packet is received, the router applies a
   classification algorithm which maps the packet to one of the
   forwarding table entries. This entry specifies how to forward the
   packet.

   We can think of this classification algorithm as a means of
   partitioning the universe of possible packets into a finite set of
   "Forwarding Equivalence Classes" (FECs).

   Each router along a path must have some way of determining the next
   hop for that FEC. For a given FEC, the corresponding entry in the
   forwarding table may be created dynamically, by operation of the
   routing protocols (unicast or multicast), or it might be created by
   configuration, or it might be created by some combination of
   configuration and protocol.

   In tag switching, if a pair of tag switches are adjacent along a tag
   switched path, they must agree on an assignment of tags to FECs. Once
   this agreement is made, all tag switches on the tag switched path
   other than the first are spared the work of actually executing the
   classification algorithm. In fact, subsequent tag switches need not
   even have the code which would be necessary to do this.

   There are a large number of different ways in which one may choose to
   partition a set of packets into FECs. Some examples:

      1. Consider two packets to be in the same FEC if there is a single
      address prefix in the routing table which is the longest match for
      the destination address of each packet;

      2. Consider two packets to be in the same FEC if these packets
      have to traverse through a common router/tag switch;

      3. Consider two packets to be in the same FEC if they have the
      same source address and the same destination address;




                                                               [Page 16]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


      4. Consider two packets to be in the same FEC if they have the
      same source address, the same destination address, the same
      transport protocol, the same source port, and the same destination
      port.

      5. Consider two packets to be in the same FEC if they are alike in
      some arbitrary manner determined by policy. Note that the
      assignment of a packet to a FEC by policy need not be done solely
      by examining the network layer header. One might want, for
      example, all packets arriving over a certain interface to be
      classified into a single FEC, so that those packets all get
      tunnelled through the network to a particular exit point.


   Other examples can easily be thought of.

   In case 1, the FEC can be identified by an address prefix (as
   described in Section 6.1). In case 2, the FEC can be identified by
   the address of a tag switch (as described in Section 6.1). Both 1 and
   2 are useful for binding tags to unicast routes - tags are bound to
   FECs, and an address prefix, or an address identifies a particular
   FEC. Case 3 is useful for binding tags to multicast trees that are
   constructed by protocols such as PIM (as described in Section 6.3).
   Case 4 is useful for binding tags to individual flows, using, say,
   RSVP (as described in Section 6.4). Case 5 is useful as a way of
   connecting two pieces of a private network across a public backbone
   (without even assuming that the private network is an IP network) (as
   described in Section 6.5).

   Any number of different kinds of FEC can co-exist in a single tag
   switch, as long as the result is to partition the universe of packets
   seen by that tag switch. Likewise, the procedures which different tag
   switches use to classify (hitherto untagged) packets into FECs need
   not be identical.

   Networks could be organized around a hierarchy of FECs. For example,
   (non-adjacent) tag switches TSa and TSb may classify packets into
   some set of FECs FEC1,...,FECn.  However from the point of view of
   the intermediate tag switches between TSa and TSb, all of these FECs
   may be treated indistinguishably. That is, as far as the intermediate
   tag switches are concerned, the union of the FEC1,...,FECn is a
   single FEC.  Each intermediate tag switch may then prefer to use a
   single tag for this union (rather than maintaining individual tags
   for each member of this union). Tag switching accommodates this by
   providing a hierarchy of tags, organized in a stack.

   Much of the power of tag switching arises from the facts that:




                                                               [Page 17]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


      - there are so many different ways to partition the packets into
      FECs,

      - different tag switches can partition the hitherto untagged
      packets in different ways,

      - the route to be used for a particular FEC can be chosen in
      different ways,

      - a hierarchy of tags, organized as a stack, can be used to
      represent the network's hierarchy of FECs.

   Note that tag switching does not specify, as an element of any
   particular protocol, a general notion of "FEC identifier". Even if it
   were possible to have such a thing, there is no need for it, since
   there is no "one size fits all" setup protocol which works for any
   arbitrary combination of packet classifier and routing protocol.
   That's why tag distribution is sometimes done with TDP, sometimes
   with BGP, sometimes with PIM, sometimes with RSVP.


8. Tag switching with ATM

   Since the tag switching forwarding paradigm is based on label
   swapping, and since ATM forwarding is also based on label swapping,
   tag switching technology can readily be applied to ATM switches by
   implementing the control component of tag switching.

   The tag information needed for tag switching can be carried in the
   VCI field. If two levels of tagging are needed, then the VPI field
   could be used as well, although the size of the VPI field limits the
   size of networks in which this would be practical. However, for most
   applications of one level of tagging the VCI field is adequate.

   To obtain the necessary control information, the switch should be
   able to support the tag switching control component. Moreover, if the
   switch has to perform routing information aggregation, then to
   support destination-based unicast routing the switch should be able
   to perform Network Layer forwarding for some fraction of the traffic
   as well.

   Supporting the destination-based routing function with tag switching
   on an ATM switch may require the switch to maintain not one, but
   several tags associated with a route (or a group of routes with the
   same next hop). This is necessary to avoid the interleaving of
   packets which arrive from different upstream tag switches, but are
   sent concurrently to the same next hop.




                                                               [Page 18]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


   If an ATM switch has built-in mechanism(s) to suppress cell
   interleave, then the switch could implement the destination-based
   routing function precisely the way it was described in Section 6.1.
   This would eliminate the need to maintain several tags per route.
   Note, however, that suppressing cell interleave is not part of the
   ATM User Plane, as defined by the ATM Forum.

   Yet another alternative that eliminates the need to maintain several
   tags per route is to carry the tag information in the VPI field, and
   use the VCI field for identifying cells that were sent by different
   tag switches. Note, however, that the scalability of this alternative
   is constrained by the size of the VPI space (4096 tags total).
   Moreover, this alternative assumes that for a set of ATM tag switches
   that form a contiguous segment of a network topology there exists a
   mechanism to assign to each ATM tag switch around the edge of the
   segment a set of unique VCIs that would be used by this switch alone.

   The downstream tag allocation on demand scheme is likely to be a
   preferred scheme for the tag allocation and TIB maintenance
   procedures with ATM switches, as this scheme allows efficient use of
   entries in the cross-connect tables maintained by ATM switches.

   Implementing tag switching on an ATM switch simplifies integration of
   ATM switches and routers. From a routing peering point of view an ATM
   switch capable of tag switching would appear as a router to an
   adjacent router; this reduces the number of routing peers a router
   would have to maintain (relative to the common arrangement where a
   large number of routers are fully meshed over an ATM cloud). Tag
   switching enables better routing, as it exposes the underlying
   physical topology to the Network Layer routing. Finally tag switching
   simplifies overall operations by employing common addressing,
   routing, and management procedures among both routers and ATM
   switches. That could provide a viable, more scalable alternative to
   the overlay model. Because creation of tag binding is driven by
   control traffic, rather than data traffic, application of this
   approach to ATM switches does not produce high call setup rates, nor
   does it depend on the longevity of flows.

   Implementing tag switching on an ATM switch does not preclude the
   ability to support a traditional ATM control plane (e.g., PNNI) on
   the same switch. The two components, tag switching and the ATM
   control plane, would operate in a Ships In the Night mode (with
   VPI/VCI space and other resources partitioned so that the components
   do not interact).







                                                               [Page 19]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


9. Tag switching migration strategies

   Since tag switching is performed between a pair of adjacent tag
   switches, and since the tag binding information can be distributed on
   a pairwise basis, tag switching could be introduced in a fairly
   simple, incremental fashion. For example, once a pair of adjacent
   routers are converted into tag switches, each of the switches would
   tag packets destined to the other, thus enabling the other switch to
   use tag switching. Since tag switches use the same routing protocols
   as routers, the introduction of tag switches has no impact on
   routers. In fact, a tag switch connected to a router acts just as a
   router from the router's perspective.

   As more and more routers are upgraded to enable tag switching, the
   scope of functionality provided by tag switching widens. For example,
   once all the routers within a domain are upgraded to support tag
   switching, in becomes possible to start using the hierarchy of
   routing knowledge function.


10. Summary

   In this paper we described the tag switching technology. Tag
   switching is not constrained to a particular Network Layer protocol -
   it is a multiprotocol solution. The forwarding component of tag
   switching is simple enough to facilitate high performance forwarding,
   and may be implemented on high performance forwarding hardware such
   as ATM switches. The control component is flexible enough to support
   a wide variety of routing functions, such as destination-based
   routing, multicast routing, hierarchy of routing knowledge, and
   explicitly defined routes. By allowing a wide range of forwarding
   granularities that could be associated with a tag, we provide both
   scalable and functionally rich routing. A combination of a wide range
   of forwarding granularities and the ability to evolve the control
   component fairly independently from the forwarding component results
   in a solution that enables graceful introduction of new routing
   functionality to meet the demands of a rapidly evolving computer
   networking environment.













                                                               [Page 20]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


11. Security Considerations

   Security considerations are not addressed in this document.


12. Intellectual Property Considerations

   Cisco Systems may seek patent or other intellectual property
   protection for some or all of the technologies disclosed in this
   document. If any standards arising from this document are or become
   protected by one or more patents assigned to Cisco Systems, Cisco
   intends to disclose those patents and license them under openly
   specified and non-discriminatory terms, for no fee.


13. Acknowledgments

   Significant contributions to this work have been made by Anthony
   Alles, Fred Baker, Paul Doolan, Guy Fedorkow, Jeremy Lawrence, Arthur
   Lin, Morgan Littlewood, Keith McCloghrie, and Dan Tappan.


14. References


15. Authors' Addresses


      Yakov Rekhter
      Cisco Systems, Inc.
      170 Tasman Drive
      San Jose, CA, 95134
      E-mail: yakov@cisco.com

      Bruce Davie
      Cisco Systems, Inc.
      250 Apollo Drive
      Chelmsford, MA, 01824
      E-mail: bsd@cisco.com

      Dave Katz
      Juniper Networks
      3260 Jay Street
      Santa Clara, CA 95051
      E-mail: dkatz@jnx.com


      Eric Rosen



                                                               [Page 21]





Internet Draft    draft-rekhter-tagswitch-arch-01.txt          July 1997


      Cisco Systems, Inc.
      250 Apollo Drive
      Chelmsford, MA, 01824
      E-mail: erosen@cisco.com

      George Swallow
      Cisco Systems, Inc.
      250 Apollo Drive
      Chelmsford, MA, 01824
      E-mail: swallow@cisco.com

      Dino Farinacci
      Cisco Systems, Inc.
      170 West Tasman Drive
      San Jose, CA 95134
      E-mail: dino@cisco.com



































                                                               [Page 22]