System and method for generating route target attributes

A system for, and method of, generating a minimum quantity of route target attributes is described. According to a method embodiment, a minimal set of unique permutations of data flows between sites of one or more Virtual Private Network (VPNs) is computed by comparing permutations of data flows to and from each site of a customer (i.e., variations of connectivity between sites) and identifying which permutation of data flows are unique while ignoring any duplicate permutations of data flows. Unique route target attributes are then generated, each route target attribute corresponding to a particular one of the unique permutations of data flows. Typically, the quantity of unique route target numbers generated is equal to the minimum quantity of unique permutations of data flows.

TECHNICAL FIELD

This invention relates to virtual private networks (VPNs), and in particular, to generating route target (RT) attributes for use with VPNs.

BACKGROUND

A virtual private network (VPN) provides secure communication across one or more shared core networks also referred to as backbones. A VPN service is provided by a Service Provider to a Customer sometimes referred to as an Enterprise. Increasingly Customers are contracting with a Service Provider to manage connectivity between sites. That is, the Customer desires to outsource their inter-site routing to the Service Provider. The Customer sends the Service Provider its routing information, and then relies on the Service Provider to distribute routing information to and from the other sites via one or more VPNs associated with the customer. Accordingly, from the customer's perspective, they may only view their internal routers communicating with their Customer Edge (CE) routers from one site to another through one or more VPNs managed by the Service Provider.

The Service Provider may operate and maintain each customer's inter-site routing connectivity through specific types of VPNs known as Border Gateway Protocol/Multi-protocol Label Switching IP VPNs (BGP/MPLS IP VPNs). These VPNs use the “Border Gateway Protocol” to distribute the routes, and “Multiprotocol Label Switching” to indicate which routes particular packets need to follow. Additional information about BGP/MPLS IP VPNs is articulated in Internet protocol proposal Request for Comment 2547 (RFC 2547) entitled “BGP/MPLS VPN's,” by E. Rosen et al. (and subsequent industry drafts), which has gained acceptance in the industry.

When provisioning VPNs for a customer, the Service Provider configures what is known as its Provider Edge (PE) routers, which are routers that form part of the backbone of the Service Provider. Typically, PE routers connect with one or more CE routers at the customer's sites. A PE router is configured with a VRF table (Virtual Routing and Forwarding table), which is a table that stores routes available to particular sites connected to the PE router.

Route Target attributes are stored in VRF tables and allow a very fine degree of control over the distribution of routes among VRFs. This can be used to create extranets, or to enforce various customer policies. Particular Route Target attributes can be assigned to particular routes. Thus, Route Targets are the mechanisms that enable each PE router to only maintain routing information for the VPNs it is supporting. The use of Import Targets and Exports Targets also provides considerable flexibility in constructing a variety of VPN topologies. More information about Route Targets and encoding may be obtained as part of BGP Extended Communities attributes (see BGP Multi-Protocol Extensions specified in RFC 2848 from the Internet Engineering Task Force).

One area that has become problematic for Service Providers is the management of RT values. As the size and complexity of each customer's routes and polices increase, most Service Providers randomly generate RT values and assign them without further considerations. With larger customers, the quantity of RT values may become exceedingly large making assignment of RT values complicated and prone to errors. One of the challenges, from a Service Provider's perspective, is to effectively manage thousands of customers of varying sizes each potentially having multiple VPNs including a variety of VPN topologies such as bidirectional and/or unidirectional connections between sites. Reducing the amount of information associated with managing each customer's VPNs including RT attributes, can reduce the complexity and efficiency of managing hundreds of thousands of routes and many different customer policies and topologies.

SUMMARY

To address the above-discussed deficiencies associated with managing route target attributes today, this invention provides a system for, and method of, generating a minimum quantity of route target attributes. In one embodiment, a minimal set of unique permutations of data flows between customer sites of one or more Virtual Private Network (VPNs) is computed by comparing permutations of data flows to and from each site (i.e., variations of connectivity between sites) and identifying which permutation of data flows are unique. Unique route target attributes are then generated, each unique route target attribute corresponding to a particular one of the unique permutations of data flows. Whereas no new unique route target attributes are generated for duplicate permutations of data flows eliminating unnecessary redundancies. Typically, the quantity of unique route target numbers generated is equal to the minimum quantity of unique permutations of data flows.

As a result of the reduction of quantity of route target attributes, the complexity and amount of information associated with provisioning and managing BGP/MPLS VPNs per customer is substantially reduced. Accordingly, the present invention allows Service Providers to more efficiently and accurately manage BGP/MPLS VPNs for Customers. Further features and advantages of this invention may become apparent to those skilled in the art after reading the Detailed Description section in conjunction with the drawings.

DETAILED DESCRIPTION

Network Environment and Overview

A system for, and method of, generating a minimum quantity of Route Target (RT) attributes is described herein. This Detailed Description assumes the reader is familiar with basic Service Provider network architectures as well as the basics behind the Border Gateway Protocol Multi-protocol Label Switching BGP/MPLS VPNs, as described in Internet protocol proposal Request for Comment 2547 (RFC 2547) entitled “BGP/MPLS VPN's,” by E. Rosen et al., and subsequent industry drafts, which have gained acceptance in the industry. For instance, it is assumed that those skilled in the art understand the common ways in which a customer network is typically attached to a Service Provider network using one or more Customer Edge (CE) devices which attach to Provider Edge (PE) routers via some sort of attachment circuit. Further, it should be appreciated by those skilled in the art that Service Provider networks can be implemented in a variety of different configurations using various different types of routers, devices, and switches.

BGP/MPLS IP VPNs are ideally suited for use with customers that desire to outsource the inter-site routing (e.g., routing between sites) to the SP. Typically, the customer does not understand nor want to know the physical backbone structure of the SP network. That is, the customer wants the SP to make the backbone and its internal routing completely transparent to the customer's own routing policies. Accordingly, the customer is usually not aware of any part of the SP's network, other than potentially PE routers and the customer sites that may attach to the customer site.

When submitting information to the Service Provider to provision and manage inter-site connectivity, the customer may only desire to describe their network to the SP in terms of “connectivity” requirements between sites within the customer's network. The connectivity requirements may include customer policies such as bidirectional and unidirectional connectivity and routing topology particulars.

For example,FIG. 1shows site connectivity of a customer's network100. In particular, the customer desires that the SP provision four Virtual Private Networks (VPN1, VPN2, VPN3, and VPN4) to interconnect eight sites Head Quarters (HQ), data center, engineering, factory1, factory2, marketing, sales1, and sales2. As shown inFIG. 1, traffic flow (connectivity) between sites is bi-directional with the exception of VPN4in which connectivity between marketing and the data center is unidirectional, with marketing only being able send data to the data center.

In this embodiment, the SP desires to configure the VPNs and various permutations of traffic flow between sites using BGP/MPLS IP VPNs using a minimal number of Route Target (RT) attributes. The route target attributes may be generated by a route target tool122in accordance with the present invention. It is appreciated by those skilled in the art having the benefit of this disclosure, that route target tool122may be implemented as part of a larger provisioning tool, although the following discussion will focus primarily on the generation of route target attributes generated by route target tool122.

Reference herein to “one embodiment”, “an embodiment”, or similar formulations herein, means that a particular feature, structure, operation, or characteristic described in connection with the embodiment, is included in at least one embodiment of the present invention. Thus, the appearances of such phrases or formulations herein are not necessarily all referring to the same embodiment. Furthermore, various particular features, structures, operations, or characteristics may be combined in any suitable manner in one or more embodiments.

In one embodiment, route target tool122includes an analyzer124and a route target ID generator124. Route target tool122, as well as analyzer124and route target ID generator124are modules representing computer-executable instructions and/or logic that may be executed by any general purpose or special purpose computing device128. A sample of such a computer device is described below with reference toFIG. 5.

Briefly, analyzer124is configured to compute a minimal set of unique permutations of data flows between sites of one or more Virtual Private Network (VPNs). As used herein unique permutations of data flows means unique instances of a bidirectional or unidirectional connections between one or more sites of the customer. Analyzer124is configured to receive permutations of data flows between the sites; compare the permutations to each other; and identify which is unique while ignoring any duplicate permutations. A route target ID generator126, in conjunction with analyzer124, is configured to generate a minimum quantity of unique Route Target attributes, each corresponding to a particular one of the unique permutations of data flows.

Exemplary Methods of Operation

FIG. 2illustrates an exemplary method200for generating a minimal quantity of route target attributes. Method200includes blocks202,204and206(each of the blocks represents one or more operational acts). The order in which the method is described is not to be construed as a limitation, and any number of the described method blocks can be combined in any order to implement the method. Furthermore, the method can be implemented in any suitable hardware, software, firmware, or combination thereof.

In a block202, once desired connectivity as represented inFIG. 1is received from the customer, connectivity is listed to determine all connections (bidirectional as well as unidirectional) between sites of a customer's network. Typically, an analyzer124is configured to list all connections in a format, such as a table, for further processing and analysis.

For example, for purposes of understanding this discussion, a connectivity matrix300may be created by analyzer124as shown inFIG. 3. That is, connectivity matrix300lists all permutations of traffic flow between customer sites shown inFIG. 1in a two dimensional array. An “X” in the matrix indicates there is a bidirectional connection between two sites corresponding at a particular row and column. Whereas, a “Y” in the matrix indicates there is a unidirectional connection between two sites corresponding at a particular row and column. An empty block indicates there no data flow (i.e., no connection) between sites.

In a block204a minimal set of unique permutations of data flows between sites of one or more Virtual Private Network (VPNs) is computed. For example, analyzer124is configured to determine the minimal set of unique permutations of data flows between sites. Again, unique permutations of data flows generally mean unique instances of bidirectional or unidirectional connections between one or more sites of the customer. This is determined by comparing permutations (variations) of data flows to and from each site; and identifying each permutation of data flow which is unique while ignoring any duplicate permutations of data flows.

In block206, unique route target attributes each corresponding to a particular one of the unique permutations of data flows is generated. For example, route target ID generator126produces unique route target values each associated with a particular one of the unique permutations of data flows. These route target values (such as a number) may then be associated with sites of a customer site to facilitate bidirectional or unidirectional connectivity between the sites of a customer's network, such as shown inFIGS. 1 and 3. The route target attribute values may include an import route target attribute and/or an export route target attribute. The minimal quantity of route target attribute values may also be used when provisioning VPNs for the customer.

It will be appreciated by those skilled in this field and having the benefit of the present disclosure, that there are many ways to compute the minimal set of unique permutations of data flows between sites and assign route target attribute values. For example,FIG. 4illustrates one method400for computing the minimal set of unique permutations of data flows between sites and generating route target attribute values. These route target attribute values may then be assigned to VRF tables (not shown) of PE routers (not shown) of a Service Provider's backbone.

Method400includes blocks402,404,406,408,410,412,414, and416. Each of the blocks represents one or more operational acts. The order in which the method is described is not to be construed as a limitation, and any number of the described method blocks can be combined in any order to implement the method. Furthermore, the method can be implemented in any suitable hardware, software, firmware, or combination thereof.

In block402ofFIG. 4, a variable group (temporary group) called GX is created. Each group has an Import Route Target List and an Export Route Target list. For example, using the connectivity of a customer's network inFIGS. 1 and 3, it is possible to create a first variable group by examining connectivity to and from HQ. In this case,

In block404, a determination is made whether the temporary group (set of permutations of traffic flows) is unique. Since this is the first group and there are no other groups to compare it to, it is determined to be unique. Therefore, according to the YES branch of decisional block404, method400proceeds to block406. If the group was not unique, method400would have proceeded to block412, which shall be explained in more detail below.

In block406, since the group was determined to be unique, it is assigned a group number. For example, GX equals G0. The actual values used herein are for illustration purposes, and other suitable values or indicia could be generated if a group is determined to be unique.

In block408, a route target attribute value is also assigned. For example, a route target number2020is assigned to group G0. Different route target numbers could be assigned to the export and import route target list, but for simplicity herein, identical route target numbers are assigned to both lists if the Group is unique. It should again be appreciated that the actual value of the route target value used herein is for illustrative purposes, and it is expected that many other suitable values may be assigned to the group.

In block410, the route target attribute value is associated with the site which was just analyzed and determined unique. So according to this example,2020is the route target attribute value assigned to HQ. In one embodiment route target ID generator126(FIG. 1) produces unique route target values each associated with a particular one of the unique permutations of data flows.

In a block412, a next site is selected for connectivity analysis and method400repeats proceeding back to block400. For example, returning back to block402the next site selected is the data center. The variable group GX is created:

In block404a decision is made whether this group unique. Accordingly, temporary group GX is compared to G0. Since GX in this scenario is different from G0, then according to the YES branch of block404method400proceeds to block406.

Still referring to the example ofFIG. 1, in block406, G1is assigned to the group. Then, in block408a route target number of2030is assigned to group G1. In block410, the route target attribute value is associated with the site which was just analyzed which is DC.

In a block412, a next site is selected for connectivity analysis and method400repeats proceeding back to block402.

For example, returning back to block400the next site selected is Engineering (Eng) (FIG. 1). After performing, steps402,404,406408,410with reference to connectivity to and from Engineering it is determined that

Accordingly, GX when compared to G0and G1is unique and therefore a group G2is generated associated with set of data flows and a route target number2040is associated with the G2={ETL: HQ, Eng, F1, F2

In block412, a next site is selected for connectivity analysis and method400repeats proceeding back to block400. In this case, Factory1(F1) is selected.

In block402, the variable group GX is created for the next location F1

In block404a decision is made whether this group is unique. Since this temporary group is the same as G2, then according to the NO branch of block404method400proceeds to block414.

In block414, the set of permutations of data flows comprising GX is not unique and is therefore ignored as it matches G2and is redundant. That is, rather than assign a new Group and new route targets, the route target attribute associated with the matching group G2is also associated with the site F1. Thus, the identical number2040associated with Engineering (FIG. 1) is used as the route target attribute value assigned to F1. Method400proceeds to block410and in block412the process repeats returning back to block402.

For example, returning back to block400the next site selected is site F2. After performing, steps402,404,414,416with reference to F2it is determined that the temporary group for F2is identical to G2. Accordingly the route target number associated with G2, which is2040is assigned to F2as well.

After analyzing all the sites using method400it is determined that for the next location, Marketing, its group is unique. Thus,

G⁢⁢3={ETL⁢:⁢⁢HQ,D⁢⁢C,M,S⁢⁢1,S⁢⁢2ITL⁢:⁢⁢HQ,M,S⁢⁢1,S⁢⁢2}
And a route target number2050is assigned to Marketing.

For the next location Sales1(S1)

GX={ETL⁢:⁢⁢HQ,M,S⁢⁢1,S⁢⁢2ITL⁢:⁢⁢HQ,M,S⁢⁢1,S⁢⁢2}
Since this set is unique

G⁢⁢4={ETL⁢:⁢⁢HQ,M,S⁢⁢1,S⁢⁢2ITL⁢:⁢⁢HQ,M,S⁢⁢1,S⁢⁢2}
And, a route target number of2060is assigned to S1. For the next location Sales2, it is obvious from the matrix (FIG. 3) that the group for this location is the same as G4. Thus,2060is assigned to S2as well.

Now, in a block416route target attributes may be assigned to sites in as both part of Import Route Target Lists and Export Route Target Lists. These values can then be configured by the Service Provider into every PE router in which the customer's CE routers connect.

For example,

Eng={ERT⁢:⁢⁢2020,2040IRT⁢:⁢⁢2020,2040}F⁢⁢1={ERT⁢:⁢⁢2020,2040IRT⁢:⁢⁢2020,2040}F⁢⁢2={ERT⁢:⁢⁢2020,2040IRT⁢:⁢⁢2020,2040}M={ERT⁢:⁢⁢2020,2030,2050,2060IRT⁢:⁢⁢2020,2050,2060}S⁢⁢1={ERT⁢:⁢⁢2020,2050,2060IRT⁢:⁢⁢2020,2050,2060}
Exemplary System Platform For Generating Route Target Attributes

Any functionality provided by a route target generator tool122(FIG. 1) and the methods200(FIG. 2) and 400(FIG. 4) can be implemented in any general purpose or special purpose computing system. Examples of well known computing systems, environments, and/or configurations that may be suitable for use to generate route target attributes for a provisioning VPNs include, but are not limited to, personal computers, server computers, multiprocessor systems, microprocessor-based systems, network computers, routers, minicomputers, mainframe computers, distributed computing environments or devices that include any of the above systems or devices, and the like.

Additionally, any exemplary functionality provided by a route target generator system may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, logic, and other executable data that perform particular tasks or implement particular abstract data types. Program modules may be located in local, remote, and/or distributed computer storage media including memory storage devices.

FIG. 5illustrates an exemplary physical representation of a computer platform500used to implement functionality performed by route target generator tool122(FIG. 1). In particular, computer platform500represents any general purpose or special purpose computing system with modifications to hardware, firmware, and/or software. Computer platform500is only one example of computer platform and is not intended to suggest any limitation as to the scope of use or functionality of any system or method described herein. Neither should the computer platform500be interpreted as having any dependency or requirement relating to any one or combination of components described herein.

Computer platform500includes a control module504, which controls the operation of platform500. Control module504can be implemented in hardware, firmware, logic, software, or any combination of thereof. In the illustrative exemplary implementation control module504is implemented as a program module that may be described in the general context of computer-executable instructions, being executed by a computer, i.e., one or more processors in a processing unit522. Control module504resides in memory524.

Memory524typically includes a variety of computer readable media. Such media can be any available media that is accessible by computer platform500and includes both volatile and non-volatile media, removable and non-removable media. The computer-readable media provide non-volatile storage of computer readable instructions, data structures, program modules, and other data for computer platform500. Any number of program modules can be stored in the computer readable media of memory524, including one or more portions of control module504.

It is also noted that portions of control module504may be stored in a remote memory storage device remote from computer platform500. Additionally, even though control module504is illustrated herein as a discrete block, it is recognized that any of these components may reside at various times in different storage components of computer platform500and are executed by one or more processors of a computer, such as processing units522.

A route target attribute tool122is typically stored in control module504of the computer platform200. For example, in one implementation, route target attribute tool122represents computer-executable instructions executed by a processing unit522of a computer, but could also be implemented in hardware or any combination of hardware, firmware, logic, and software.

Although route target attribute tool122is shown as a single block, it is understood that when actually implemented in the form of computer-executable instructions, logic, firmware, and/or hardware, that the functionality described with reference to it may not exist as separate identifiable block. Additionally, route target attribute tool122may also be integrated with other components or as a module in a larger system, such as provisioning software and systems.

The embodiments described herein are to be considered in all respects only as exemplary and not restrictive. The scope of the invention is, therefore, indicated by the subjoined claims rather by the foregoing description. All changes which come within the meaning and range of equivalency of the claims are to be embraced within their scope.