(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2004/0174884 A1
`Wright
`(43) Pub. Date:
`Sep. 9, 2004
`
`US 2004O174884A1
`
`(54) METHOD FOR TRAFFICENGINEERING OF
`CONNECTIONLESS VIRTUAL PRIVATE
`NETWORK SERVICES
`(76) Inventor: Steven Allan Wright, Roswell, GA
`(US)
`Correspondence Address:
`CANTOR COLBURN, LLP
`55 GRIFFINROAD SouTH
`BLOOMFIELD CT 06002
`9
`10/382,258
`
`(21) Appl. No.:
`
`(22) Filed:
`
`Mar. 5, 2003
`
`Publication Classification
`
`(51) Int. Cl. .................................................. H04L 12/28
`(52) U.S. Cl. ........................................................ 370/395.41
`
`(57)
`
`ABSTRACT
`
`A method for traffic engineering of connectionless virtual
`private network (VPN) services. The method comprises
`receiving physical connectivity data for a connectionless
`VPN including service nodes and links between the service
`nodes. One or more of the Service nodes are also edge nodes.
`Logical connectivity data for the edge nodes is received. A
`restricted topology is created in response to the physical
`connectivity data and to the logical connectivity data. The
`restricted topology includes a Single path between each pair
`of the edge nodes and each path includes a plurality of the
`Service nodes and one or more of the links. A bandwidth
`requirement for each link in the restricted topology is
`calculated. The bandwidth requirement is reserved on each
`link in the restricted topology. The method further comprises
`directing routing Software to force a packet received from an
`edge node through one of the paths in the restricted topol
`Ogy.
`
`
`
`Ex.1006
`CISCO SYSTEMS, INC. / Page 1 of 11
`
`

`

`Patent Application Publication Sep. 9, 2004 Sheet 1 of 5
`
`US 2004/0174884 A1
`
`
`
`Ys
`
`Ex.1006
`CISCO SYSTEMS, INC. / Page 2 of 11
`
`

`

`Patent Application Publication Sep. 9, 2004 Sheet 2 of 5
`
`US 2004/0174884 A1
`
`
`
`s
`
`S
`
`s
`
`Q
`
`S
`
`Ex.1006
`CISCO SYSTEMS, INC. / Page 3 of 11
`
`

`

`Patent Application Publication Sep. 9, 2004 Sheet 3 of 5
`
`US 2004/0174884 A1
`
`
`
`s
`
`S
`
`CY
`
`s
`
`Ex.1006
`CISCO SYSTEMS, INC. / Page 4 of 11
`
`

`

`Patent Application Publication Sep. 9, 2004 Sheet 4 of 5
`
`US 2004/0174884 A1
`
`
`
`da?nog euOO_-80°
`
`Ex.1006
`CISCO SYSTEMS, INC. / Page 5 of 11
`
`

`

`Patent Application Publication Sep. 9, 2004 Sheet 5 of 5
`
`US 2004/0174884 A1
`
`RECEIVE PHYSICAL
`NETWORK CONNECTIONS
`
`5O2
`
`RECEIVE LOGICAL
`CONNECTIVITY REQUIREMENTS
`
`504
`
`CREATE A RESTRICTED
`TOPOLOGY TO PROVIDE
`LOGICAL CONNECTIONS
`
`5O6
`
`CALCULATE BANDWIDTH
`REQUIREMENTS
`
`508
`
`RESERVE BANDWIDTH
`
`510
`
`
`
`SET UP ROUTING TO
`FORCE PACKET THROUGH
`THE RESTRICTED TOPOLOGY
`
`512
`
`FIG. 6
`
`Ex.1006
`CISCO SYSTEMS, INC. / Page 6 of 11
`
`

`

`US 2004/0174884 A1
`
`Sep. 9, 2004
`
`METHOD FOR TRAFFIC ENGINEERING OF
`CONNECTIONLESS VIRTUAL PRIVATE
`NETWORK SERVICES
`
`BACKGROUND OF THE INVENTION
`0001. The present disclosure relates generally to traffic
`engineering of connectionless virtual private network (VPN)
`Services and in particular, to a method of traffic engineering
`that can be utilized to provide a quality of Service guarantee
`on a connectionless VPN service.
`0002 Many corporations utilize connectionless VPNs to
`provide communication between offices and plants that are
`located in different geographic locations. A VPN may be
`implemented in a variety of manners, including building a
`VPN on top of an existing asynchronous transfer mode
`(ATM) network and building a VPN directly over the
`Internet. Typically, each geographic location within a VPN
`includes a firewall and a network means to access the other
`geographic locations covered by the VPN (e.g., a tunnel
`between each geographic location within the VPN). A VPN
`may provide a connectionless or connection-oriented Ser
`Vice. A connectionless Service is often compared to a postal
`System and refers to a network Service where each packet
`carries a full destination address and each packet is routed
`through the network independently of other packets within
`the network. This is contrasted with a connection-oriented
`Service, where a requesting node establishes a connection
`with a receiving node, Sends data via the connection and
`then discontinues the connection. Both types of network
`Services, connectionless and connection-oriented, may be
`characterized by a quality of Service (QoS) metric, or
`guarantee.
`0003. The basic technique for providing QoS guarantees
`is the allocation of network resources along the path of the
`Service instance. Typically, the network resource allocation
`is Summarized as the bandwidth allocation for that Service
`on a link, or path. Bandwidth allocation is a fundamental
`requirement for a variety of QoS guarantees. For example,
`guarantees on bandwidth, latency, loSS and jitter all require,
`at a minimum, that bandwidth can be guaranteed. This works
`for connection-oriented Services, but has problems for con
`nectionless Services where the path must be defined on a
`packet-by-packet basis. There is no formally Standardized
`Solution that provides a mechanism to dimension the con
`nectionless network. Generally, the connectionless network
`is considered as a "cloud” network and link bandwidths are
`upgraded individually as the traffic load reaches critical
`thresholds. QoS approaches (e.g., Differentiated Services)
`require dimensioning for bandwidth across the whole net
`work as they decouple from the routing. In layer 3 VPNs
`(e.g., RFC 2547 style VPNs) the traffic between the end
`points of the VPN is restricted to a logical mesh between
`those endpoints. A similar approach may be utilized for layer
`2 VPNs in the context of virtual private LAN service
`(VPLS). One approach to a QoS extension is to reserve
`bandwidth along each of those logical paths in the logical
`mesh of endpoint connections. The mesh of connections
`could be implemented by a variety of tunneling mechanisms
`such as multi protocol label switching (MPLS), generic
`routing encapsulation (GRE) and internet protocol Security
`protocol (IPsec).
`0004. A drawback to reserving bandwidth along each of
`the logical paths in the logical mesh is that the bandwidth
`
`reservation requirements Scale with the number of end
`points. In order to guarantee bandwidth for a connectionless
`Service, it must be possible to guarantee bandwidth between
`each of the endpoints, or edge nodes within the network. For
`example, a first edge node may have a maximum bandwidth
`to the network of one-hundred megabits per second (Mb/s)
`and it may be necessary to dimension the network Such that
`those one-hundred Mb/s can be delivered to any other edge
`node in the connectionless network. One way to do this is to
`reserve bandwidth for each direct path between the first edge
`node and each other edge node. For example, if three other
`edge nodes exist in the network, this would require three
`hundred Mb/s to be reserved through the network even
`though the first edge node can only Send a maximum of
`one-hundred Mb/s. As the number of edge nodes becomes
`large, the amount of bandwidth required to be reserved
`based on each of the logical paths in the logical mesh may
`not be physically available on the links within the connec
`tionless VPN.
`
`BRIEF DESCRIPTION OF THE INVENTION
`0005 The above discussed and other drawbacks and
`deficiencies of the prior art are overcome or alleviated by a
`method for traffic engineering of connectionless virtual
`private network (VPN) services. In an exemplary embodi
`ment, the method comprises receiving physical connectivity
`data for a connectionless VPN including service nodes and
`links between the service nodes. One or more of the service
`nodes are also edge nodes. Logical connectivity data for the
`edge nodes is received. A restricted topology is created in
`response to the physical connectivity data and to the logical
`connectivity data. The restricted topology includes a Single
`path between each pair of the edge nodes and each path
`includes a plurality of the Service nodes and one or more of
`the links. A bandwidth requirement for each link in the
`restricted topology is calculated. The bandwidth require
`ment is reserved on each link in the restricted topology. The
`method further comprises directing routing Software to force
`a packet received from an edge node through one of the
`paths in the restricted topology.
`0006. In another aspect, a computer program product for
`traffic engineering of connectionless VPN Services com
`prises a storage medium readable by a processing circuit and
`Storing instructions for execution by the processing circuit
`for performing a method. The method comprises receiving
`physical connectivity data for a connectionless VPN includ
`ing Service nodes and links between the Service nodes. One
`or more of the Service nodes are also edge nodes. Logical
`connectivity data for the edge nodes is received. A restricted
`topology is created in response to the physical connectivity
`data and to the logical connectivity data. The restricted
`topology includes a Single path between each pair of the
`edge nodes and each path includes a plurality of the Service
`nodes and one or more of the linkS. A bandwidth require
`ment for each link in the restricted topology is calculated.
`The bandwidth requirement is reserved on each link in the
`restricted topology. The method further comprises directing
`routing Software to force a packet received from an edge
`node through one of the paths in the restricted topology.
`0007. In a further aspect, a computer usable medium
`Storing a computer program for directing network hardware
`to perform a method comprising receiving physical connec
`tivity data for a connectionless VPN including service nodes
`
`Ex.1006
`CISCO SYSTEMS, INC. / Page 7 of 11
`
`

`

`US 2004/0174884 A1
`
`Sep. 9, 2004
`
`and links between the service nodes. One or more of the
`Service nodes are also edge nodes. Logical connectivity data
`for the edge nodes is received. A restricted topology is
`created in response to the physical connectivity data and to
`the logical connectivity data. The restricted topology
`includes a Single path between each pair of the edge nodes
`and each path includes a plurality of the Service nodes and
`one or more of the links. A bandwidth requirement for each
`link in the restricted topology is calculated. The bandwidth
`requirement is reserved on each link in the restricted topol
`ogy. The method further comprises directing routing Soft
`ware to force a packet received from an edge node through
`one of the paths in the restricted topology.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`0008 Referring to the exemplary drawings wherein like
`elements are numbered alike in the several FIGURES:
`0009 FIG. 1 is a block diagram of the physical connec
`tivity included in an exemplary connectionless VPN,
`0.010
`FIG. 2 is a block diagram of an exemplary logical
`connectivity mesh associated with the connectionless VPN
`depicted in FIG. 1;
`0.011
`FIG. 3 is a block diagram of an exemplary logical
`connectivity mesh constrained to a Specific topology asso
`ciated with the connectionless VPN depicted in FIG. 1;
`0012 FIG. 4 is a block diagram of an exemplary tree
`Structure that may be utilized as a logical connectivity mesh
`constrained to a specific topology; and
`0013 FIG. 5 is a flow diagram of an exemplary process
`for performing traffic engineering of a connectionless VPN
`Service.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`0.014) An embodiment of the present invention is directed
`to the dimensioning and Service functionality requirements
`to implement connectionless VPN services with bandwidth
`QoS guarantees. Briefly, an embodiment of the present
`invention provides enhanced bandwidth Scaling properties
`by forcing the logical paths to follow a restricted topology,
`where a single path exists between each pair of edge nodes
`within the VPN. This is contrasted to a full mesh approach
`where multiple paths may exist between each pair of edge
`nodes. The restricted topology for the VPN may be imple
`mented with a variety of mechanisms or technologies as
`long as it meets two objectives: first, that the logical mesh
`of connections is forced to run through the restricted topol
`ogy; and Second, that the restricted topology provides band
`width guarantees. The bandwidth guarantees of the
`restricted topology may be designed to ensure adequate
`bandwidth for the Service. The dimensioning approach can
`scale with the number of nodes in the VPN. Using an
`embodiment of the present invention to dimension the
`network, the bandwidth guarantees may be engineered to
`Support an arbitrary degree of over-Subscription of network
`resources, and therefore, effectively Scaling at a rate leSS
`than the number of nodes.
`0.015 The basic physical components utilized to provide
`the connectionless Service in an exemplary embodiment of
`the present invention are depicted in FIG. 1. FIG. 1 includes
`
`several edge nodes 102, service nodes 104, a VPN 106 and
`internal transport links 108. The edge nodes 102 are a special
`class of service nodes 104 that interface directly to the
`customer. The edge nodes 102 include all the properties
`discussed with respect to service nodes 104 because they are
`a Subset of Service nodes 104. The links 108 are considered
`to be transport links that provide a fixed bandwidth transport
`service between the service nodes 104 (including the edge
`nodes 102). Shown in FIG. 1, are all the physical links 108
`in the VPN 106 and therefore all the possible physical routes
`for sending packets through the VPN 106. In an exemplary
`embodiment, the links 108 are provided by a gigabit Eth
`ernet. Alternate embodiments include any link technology
`known in the art including using a Synchronized optical
`network (SONET) to provide the links 108 and virtual
`circuits with bandwidth guarantees through an ATM network
`to provide the links 108. The service nodes 104, including
`the edge nodes 102, provide the connectionless Service. In
`an exemplary embodiment, the connectionless VPN service
`includes packet-by-packet routing for a layer 3 Service, or
`alternatively, an emulated VPLS for a layer 2 service. The
`service nodes 104, including the edge nodes 102, make
`routing and forwarding decisions for the packetized data
`traffic. The service nodes 104 are the points in the VPN 106
`where queuing of packets may occur, as packets arriving at
`a service node 104 from several ingress links 108 contend
`for service on a single egress link 108. Service nodes 104
`may be implemented utilizing any hardware known in the art
`to provide service node 104 functions such as such as
`Ethernet Switches and IP routers.
`0016 FIG. 2 is a block diagram of an exemplary logical
`connectivity mesh associated with the connectionless VPN
`network depicted in FIG.1. As depicted in FIG. 2, all three
`edge nodes 102, labeled “A”, “B” and “C” communicate
`with each other through the VPN 106. FIG. 2 illustrates the
`logical connectivity without regard to the physical imple
`mentation. If a full logical mesh approach was implemented,
`then the logical connectivity would mirror the physical
`connectivity depicted in FIG. 1. Using a full logical mesh
`approach may result in a requirement to reserve more
`bandwidth than is required and is available. For example, if
`each link had a bandwidth requirement of “x and a band
`width QoS was to be provided, then each link 108 would be
`required to reserve a bandwidth of “X” for exclusive use by
`the VPN. FIG. 3 is a block diagram of an alternate exem
`plary logical connectivity mesh that is constrained to a
`Specific restricted topology (e.g., a virtual topology) through
`the physical VPN 106 depicted in FIG. 1. The restricted
`topology depicted in FIG. 3 is implemented utilizing the
`underlying Service nodes 104, including the edge nodes 102,
`and links 108 depicted in FIG. 1. All packets within the
`VPN 106 from edge nodes 102*A”, “B” and “C” travel
`along a subset of the links 302,304 and 306. Bandwidth is
`reserved along this Subset of links to Support a bandwidth
`QoS. As depicted in FIG. 3, a single path is created between
`each pair of edge nodes 102.
`0017. The exemplary virtual topology, or restricted topol
`ogy, depicted in FIG. 3 is selected to minimize the amount
`of bandwidth reserved on the links 108 to provide a band
`width QoS. For example, the logical connectivity from edge
`node 102'A' to edge node 102'B' and from edge node
`102"A" to edge node 102"C" share the same link 304 from
`edge node 102"A" to service node 104"D". Consider that the
`bandwidth requirement from edge node 102"A" to edge
`
`Ex.1006
`CISCO SYSTEMS, INC. / Page 8 of 11
`
`

`

`US 2004/0174884 A1
`
`Sep. 9, 2004
`
`node 102"B" is “X” Mb/s and from edge node 102"A" to
`edge node 102"C" is “y” Mb/s. One way to calculate the
`required reserved bandwidth from the edge node 102'A' to
`service node 104"D' is to reserve “x+y' Mb/s. In contrast,
`an exemplary embodiment of the present invention calcu
`lates the required reserved bandwidth as the maximum of
`“X” and “y” because it recognizes that there is maximum
`bandwidth that can be generated from edge node 102"A"
`traversing the link 304 to service node 104“D’. Similarly,
`the logical connectivity from edge node 102'B' to edge
`node 102'A' and from edge node 102'B' to edge node
`102"C" share the same link 306 from edge node 102"B" to
`Service node 104"D'. Therefore, the reserved bandwidth is
`calculated to be the maximum of the required bandwidths
`from edge node 102"B" to edge nodes 102"A" and “C”. In
`this manner, only the bandwidth actually required is
`reserved on the links 108.
`0.018. In general, the restricted topology may be chosen
`to identify the required bandwidth and to provide guarantees
`for that bandwidth in the service architecture. The mecha
`nism for providing bandwidth guarantees on the links 108
`between the service nodes 104 (including the edge nodes
`102) is implementation specific. In an exemplary embodi
`ment of the present invention, ATM virtual circuits are
`dimensioned to the required bandwidth. In another exem
`plary embodiment of the present invention, traffic engi
`neered tunnels are provisioned via MPLS. A key require
`ment for providing bandwidth guarantees is that that the
`Service nodes 104, including the edge nodes 102, provide the
`necessary queuing and link Scheduling mechanisms to pro
`vide the bandwidth guarantees for each link. In addition, the
`service nodes 104 should have the ability to route the VPN
`traffic, and only the VPN traffic, over that allocated band
`width. The bandwidth allocation at each link could specify
`a minimum bandwidth, or a maximum bandwidth, with
`different results for the aggregate, or end-to-end, Service.
`0019. A variety of mechanisms may be utilized in an
`exemplary embodiment of the present invention to achieve
`route restriction. For example, the if the logical mesh is
`implemented as MPLS label switched paths (LSPs), the
`logical topology may be implemented as MPLS traffic
`engineered tunnels. The routing restrictions may be imple
`mented in MPLS by “coloring” the traffic-engineered tun
`nels and restricting access to those colored routes to the VPN
`members. This is essentially a constrained routing problem
`for the mesh of LSPs, where they are constrained to only use
`the appropriately colored routes. Link coloring and con
`strained routing are well known capabilities of MPLS net
`works. For example, resource reservation protocol (RSVP)
`and constraint-based label distribution protocol (CRLDP)
`may be utilized to provide route restrictions in MPLS
`networks, and Ethernet protocols known in the art may be
`utilized to create a restricted topology (e.g., a tree Structure)
`and perform routing.
`0020 FIG. 4 is a block diagram of an exemplary tree
`Structure that may be utilized as a logical connectivity mesh
`constrained to a Specific topology in an exemplary embodi
`ment of the present invention. The tree Structure depicted in
`FIG. 4 includes leaves that are the Subscribers to a VPN,
`where the nodes of the tree are Service nodes and the
`branches are transport links. In FIG. 4, the leaves, or edge
`nodes, are implemented utilizing tandem Switches 402, and
`the Service nodes are implemented using tandem gateways
`
`404, edge routers 406 and core routers 408. As depicted in
`FIG. 4, the VPN participants are the tandem Switches 402
`that may be interconnected by a packet Switched connec
`tionless VPN with QoS guarantees on the minimum band
`width. Each tandem Switch 402 has a symmetric connection
`to the edge routers 406 (e.g., a L3 VPN a 1a RFC 2547)
`where the ingreSS bandwidth required to the packet network
`is equal to the egreSS bandwidth required from the packet
`network. In this example, the bandwidth requirement would
`correspond to the number of active calls that the tandem
`Switch 402 could support over this interface. The tandem
`Switches 402 may in general be able to support different
`numbers of calls, that is have different, but still symmetric
`access bandwidth into the connectionless VPN with QoS.
`For Simplicity in this example, it is assumed that they are all
`the same size and require a symmetric bandwidth of “a bits
`per Second. If the bandwidth is asymmetric, more specifics
`would be required about the bandwidth in the ingress
`direction (edge to core) versus the bandwidth in the egress
`direction (core to edge). Because the bandwidth is symmet
`ric at all edges in the exemplary embodiment depicted in
`FIG. 4, the bandwidth will be symmetric at all links though
`the tree and referring to the link bandwidth is specific
`enough.
`0021. In a simple tree structure the bandwidth of all the
`linkS is identical. In the exemplary embodiment depicted in
`FIG. 4, a "fat’ tree structure is utilized. In a fat tree structure,
`the bandwidths on the links increase closer to the core
`routers 408. AS depicted in FIG. 4, Stringent QoS guarantees
`on bandwidth are supported because the link bandwidth
`between the edge routers 406 and the next level in the tree
`is the sum of the bandwidths from the VPN participants
`attached to that edge node. This is depicted in FIG. 4, where
`the link bandwidth between the tandem gateways 404 and
`the edge routers 406 is “a” and the link bandwidth between
`the edge router 406 and the core routers 408 is “a+a', or “b.
`Similarly, the link bandwidth between the core routers is “c”.
`In an alternate embodiment, a leSS Stringent QoS guarantee
`may be required (e.g., a Statistical guarantee) and lesser
`bandwidth towards the core may be utilized. In this case,
`there is a reliance upon the user traffic Statistics that may
`Suggest that Simultaneous peak usage by all edge nodes is
`unlikely. This provides a mechanism for engineering the
`degree of over-Subscription of core network bandwidth.
`0022. The tree structure is not required to be regular in
`the Sense that all nodes have the same degree or all leaves
`are the same depth from the core. The tree Structure is loop
`free which may avoid a number of potential routing prob
`lems. The tree Structure also matches the topology of real
`acceSS networks and Simplifies the bandwidth requirement
`calculations. The construction of the tree Structured virtual
`topology may initially be manually configured on the
`Switches and routers involved. Alternatively, the virtual
`topology creation may be automated. A variety of algorithms
`exist to generate Such tree Structures. For example, the tree
`could be constructed as a core based tree or a Steiner tree.
`Several protocols have been developed for generating Such
`tree structures (e.g., spanning tree algorithm of Ethernet and
`various protocols for multicast trees).
`0023. In an alternate embodiment of the present inven
`tion, additional redundancy and/or resiliency is provided.
`The basic tree structure depicted in FIG. 4 does not take into
`account the various types of failures to which networks are
`
`Ex.1006
`CISCO SYSTEMS, INC. / Page 9 of 11
`
`

`

`US 2004/0174884 A1
`
`Sep. 9, 2004
`
`Subject. A variety of redundancy techniques may be used to
`enhance the virtual topology. To protect against link failures,
`each link could be made redundant by using a link-by-link
`protection Scheme (e.g., SONET rings, Ethernet load shared
`multi-link groups like IEEE802.1ad). To protect against
`node failures, additional links and nodes may be deployed,
`along with the mechanisms and criteria for recognizing link
`and node failures and recovering from them. One approach
`is to utilize a completely node and link disjoint Virtual
`topology. The two disjoint tree Structures could be run in a
`load Sharing mode or in an active Standby mode. The nodes
`at which the two disjoint tree Structures meet have to
`implement the load Sharing or active/standby Switching
`function. These nodes could be the Service edge nodes of the
`carrier network, or the Subscriber nodes. In addition, addi
`tional nodes may be added to the tree Structure based on
`capacity requirements. For example, a tandem Switch 402
`may be bigger than the tandem gateway 404 that it is linked
`to and therefore, a Second tandem gateway 404 linked to the
`tandem Switch 402 may provide enhanced throughput.
`0024 FIG. 5 is a flow diagram of an exemplary process
`for performing traffic engineering of connectionless VPN
`Service. At Step 502, the physical network connections, Such
`as those depicted in FIG. 1, are received. The physical
`network connections may include data Such as nodes and
`links included in the VPN. At step 504, the logical connec
`tivity requirements are received. AS discussed previously in
`reference to FIG. 2, the logical connectivity requirements
`are in terms of edge nodes and communication requirements
`between edge nodes. Step 506 includes creating a restricted
`topology to provide logical connections. AS discussed pre
`viously with respect to FIGS. 3 and 4, this topology may be
`based on a tree Structure and includes a Single path between
`each pair of endpoints. Once the restricted topology is
`created in step 506, step 508 is performed to calculate
`bandwidth requirements on links within the restricted topol
`ogy. At step 510, the required bandwidth is reserved and at
`Step 512 routing Software in directed to force packets within
`the VPN to be sent through the nodes in the restricted
`topology.
`0.025
`In addition, an embodiment of the present inven
`tion allows a bandwidth QoS to be supported in a connec
`tionless VPN. An embodiment of the present invention may
`result in reducing the core bandwidth requirements when
`compared to a meshed approach. For a VPN of N nodes,
`each of bandwidth x, the mesh approach requires N(N-1)/2
`paths of bandwidth (i.e., the bandwidth requirement Scales
`with the square of the number of VPN participants). In
`contrast, the maximum bandwidth between each level in the
`tree structure is N leaves of bandwidth x (i.e., the bandwidth
`scales linearly with the number of VPN participant for the
`tree topology case). The ability to provide a QoS guarantee
`with less reserved bandwidth may allow for more QoS
`bandwidth guarantees to be available due to the decreased
`cost in bandwidth. An embodiment of the present invention
`may be applied to the dimensioning of packet bandwidth to
`Support the interconnection of packet tandem Switches. The
`dimensioning approach of the present invention may also be
`applied to connectionless Services in an acceSS network,
`such as voice over IP (VoIP). A further embodiment of the
`present invention may be applicable for dynamic Session
`based services where admission to these services with QoS
`guarantees is controlled on a Session by Session basis (e.g.,
`Video-on-demand, Video conferencing).
`
`0026. As described above, the embodiments of the inven
`tion may be embodied in the form of computer-implemented
`processes and apparatuses for practicing those processes.
`Embodiments of the invention may also be embodied in the
`form of computer program code containing instructions
`embodied in tangible media, Such as floppy diskettes, CD
`ROMs, hard drives, or any other computer-readable Storage
`medium, wherein, when the computer program code is
`loaded into and executed by a computer, the computer
`becomes an apparatus for practicing the invention. An
`embodiment of the present invention can also be embodied
`in the form of computer program code, for example, whether
`Stored in a Storage medium, loaded into and/or executed by
`a computer, or transmitted over Some transmission medium,
`Such as over electrical wiring or cabling, through fiber
`optics, or via electromagnetic radiation, wherein, when the
`computer program code is loaded into and executed by a
`computer, the computer becomes an apparatus for practicing
`the invention. When implemented on a general-purpose
`microprocessor, the computer program code Segments con
`figure the microprocessor to create Specific logic circuits.
`0027. While the invention has been described with ref
`erence to exemplary embodiments, it will be understood by
`those skilled in the art that various changes may be made and
`equivalents may be substituted for elements thereof without
`departing from the Scope of the invention. In addition, many
`modifications may be made to adapt a particular situation or
`material to the teachings of the invention without departing
`from the essential Scope thereof. Therefore, it is intended
`that the invention not be limited to the particular embodi
`ment disclosed as the best mode contemplated for carrying
`out this invention, but that the invention will include all
`embodiments falling within the Scope of the appended
`claims. Moreover, the use of the terms first, Second, etc. do
`not denote any order or importance, but rather the terms first,
`Second, etc. are used to distinguish one element from
`another.
`
`What is claimed is:
`1. A method for traffic engineering of a connectionless
`Virtual private network Service, Said method comprising:
`receiving physical connectivity data for a connectionless
`Virtual private network including Service nodes and
`links between said Service nodes, wherein one or more
`of Said Service nodes are also edge nodes,
`receiving logical connectivity data for Said edge nodes,
`creating a restricted topology in response to Said physical
`connectivity data and to Said logical connectivity data,
`wherein Said restricted topology includes a Single path
`between each pair of Said edge nodes and wherein each
`Said path includes a plurality of Said Service nodes and
`one or more Said links;
`calculating a bandwidth requirement for each said link in
`Said restricted topology;
`reserving Said bandwidth requirement on each Said link in
`Said virtual private network; and
`directing routing Software to force a packet received from
`a said edge node through a said path in Said restricted
`topology.
`2. The method of claim 1 wherein Said restricted topology
`is a tree Structure.
`
`Ex.1006
`CISCO SYSTEMS, INC. / Page 10 of 11
`
`

`

`US 2004/0174884 A1
`
`Sep. 9, 2004
`
`3. The method of claim 2 wherein said tree structure is a
`fat tree Structure.
`4. The method of claim 1 further comprising providing a
`quality of Service guarantee in response to Said reserving
`Said bandwidth requirement.
`5. The method of claim 4 wherein said quality of service
`guarantee is a bandwidth guarantee.
`6. The method of claim 4 wherein said quality of service
`guarantee is a latency guarantee.
`7. The method of claim 4 wherein said quality of service
`guarantee is a loSS guarantee.
`8. The method of claim 4 wherein said quality of service
`guarantee is a jitter guarantee.
`9. The method of claim 1 wherein said packet is in multi
`protocol label Switching format.
`10. The method of claim 1 wherein said virtual private
`network is a level two network.
`11. The method of claim 1 wherein said virtual private
`network is a level three network.
`12. The method of claim 1 wherein Said calculating a
`bandwidth requirement results in an over Subscription of
`Said bandwidth requirement.
`13. The method of claim 1 wherein said calculating a
`bandwidth requirement results in an under Subscription of
`Said bandwidth requirement.
`14. The method of claim 1 further comprising adding a
`redundant Said link and Said Service node to a said path in
`Said restricted topology.
`15. The method of claim 1 wherein said routing software
`is based on constraint based label distribution protocol.
`16. The method of claim 1 wherein said routing software
`is based on resource reservation protocol.
`17. The method of claim 1 wherein said service nodes
`provide the necessary queuing and link Scheduling mecha
`nisms to provi