Abstract:
A technique for physically implementing a network of nodes in a virtual private network. To physically set-up all required connections in the network, a heuristic link selection algorithm is devised to systematically and efficiently determine interconnection links that realize the virtual private network subject to service level agreement requirements.

Description:
BACKGROUND OF THE DISCLOSURE  
         [0001]    1. Field of the Invention  
           [0002]    This invention relates generally to the configuration of a complex nodal-type network and, more particularly, to a methodology for heuristically selecting, subject to given constraints, links interconnecting network nodes to thereby configure the network.  
           [0003]    2. Description of the Background Art  
           [0004]    Conceptually, a Virtual Private Network (VPN) is characterized by a set of connections among N nodes. The connections may assume any topology such as full-mesh, partial-mesh, or stars. The connections may be uni-directional, bi-directional, point-to-point or point-to-multipoint, symmetric or asymmetric. VPN connections are usually associated with a set of performance requirements typically summarized in a service level agreement (SLA). Given a VPN request by a customer, specified by a SLA, the VPN service-planning task involves finding network resource necessary to fulfill the VPN-SLA requirement. In this context, network resource is defined to be a set of links chosen for the realization of the requested VPN connections.  
           [0005]    In a practical network, such as an ATM network or an IP MPLS network, multiple links normally exist between two nodes of such networks. Algorithms exist for finding the most efficient links satisfying a set of SLA requirements. An example of such an algorithm can be found in an article entitled “Finding the K Shortest Loopless Paths in a Network”, by J. Y. Yen, Management Science, 11 (1971), pages712-716.  
           [0006]    However, the problem for planning VPN is more involved due to the simultaneous requirement of a set of connections among N points. Suppose a VPN has connections 1,2, . . . C. Suppose the VPN planner (which can be a software) attempts to find the optimum path, that is, a set of links (dependent on certain global criteria to be discussed later) connecting a given one of the N points with another one of the N points sequentially for connections 1,2,3 . . . . It is assumed that the first connection path is found by using the method described in the reference cited above. Next, the planner proceeds to find an optimum path for connection 2. By selecting a path to realize connection 2, the planner inevitably changes the available network resource and therefore the network state. This change upsets the optimum conditions for the previously selected path 1 and renders such selection non-optimum. This simple illustration of the so-called “sequential approach” suggests that a global optimal solution cannot be obtained by a straightforward sequential application of the same algorithm that produces an optimal solution for a single connection. Of course, an exhaustive search of every possible combination of all the k paths for all the C connections will theoretically yield the optimum solution. Such approach, however, would be prohibitively time-consuming and computationally-consuming (non-polynomial time).  
           [0007]    Thus, a need exists in the art for a systematic procedure to configure a complete VPN given a specified SLA. As part of this procedure, it is necessary to obtain a tractable, effective solution that gives “close-to-optimum” results with negligible computational effort. “Close-to-optimum” means that the search result determines a feasible global minimum.  
         SUMMARY OF THE INVENTION  
         [0008]    These shortcomings and other limitations and deficiencies are obviated in accordance with the present invention by a method, and concomitant circuitry, to systematically and efficiently determine interconnection links so as to configure a general network composed of switching nodes into a VPN network subject to the service level agreement requirements.  
           [0009]    In accordance with the broad aspect of the present invention, a method is set forth for physically implementing a network of nodes interconnected by links subject to known constraints. The method includes the steps of (1) systematically selecting, based upon a prescribed mathematical algorithm, links interconnecting node pairs, the algorithm being determined to satisfy the requirements of a given service level agreement; and (2) interconnecting each node pair with the corresponding selected links.  
           [0010]    In accordance with the system aspect of the present invention, a network manager, coupled to each of the nodes via a local controller associated with each of the nodes, computes the prescribed mathematical algorithm to obtain configuration information, and then transmits the configuration information to the nodes via the controllers, whereupon each node is arranged in correspondence to the configuration information. Traffic is routed to end-point nodes via the configured network.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0011]    The teachings of the present invention can be readily understood by considering the following detailed description in conjunction with the accompanying drawings, in which:  
         [0012]    [0012]FIG. 1 illustrates an illustrative network to be configured as a VPN subject to a service level agreement;  
         [0013]    [0013]FIG. 2 illustrates the steps of the algorithm to determine the interconnection links of FIG. 1 that configure the network as a VPN subject to the service level agreement;  
         [0014]    [0014]FIG. 3 illustrates the arrangement, including a network manager and local controllers associated with each of the switching nodes of FIG. 1, for conveying VPN configuration information to the switching nodes to configure the VPN; and  
         [0015]    [0015]FIG. 4 is a high-level flow diagram of the method carried out by the network manager, in conjunction with each local controller and switching node, to configure the network of FIG. 1 as the VPN subject to the service level agreement.  
         [0016]    To facilitate understanding, identical reference numerals have been used, where possible, to designate identical elements that are common to the figures. 
     
    
     DETAILED DESCRIPTION  
       [0017]    After considering the following description, those skilled in the art will clearly realize that the teachings of this invention can be readily utilized in providing a VPN subject to a SLA.  
       Overview of VPN Planning Algorithm  
       [0018]    For illustrative purposes, we first consider a VPN with capacity as the only requirement comprising the SLA. Later, we will extend the method to cover other common SLA metrics (delay, loss, jitter).  
         [0019]    The following terminology is used in the sequel:  
         [0020]    (a) VPN has N end points. Each pair of end-points may constitute a connection. Therefore, a fully meshed VPN has a total of C=N(N−1) connections.  
         [0021]    (b) For each connection, there may exist k or less shortest paths with the largest number of links (or, synonymously, hops) equals L, wherein (i) a path is a set of links connecting two end-points, and (ii) a link is a physical or logical connection between two nodes. Also, in the sequel, k paths implies k or less paths with no other paths that have less hops than L.  
         [0022]    (c) A mini-max path is one of the k paths whose maximum capacity link is the minimum among the maximum-capacity links of the k paths.  
         [0023]    (d) A global criterion (metric) is a property of the entire network. Examples are mini-max link capacity, or total minimum number of traversed links. Local criterion, on the other hand refers to a property of a particular path of a connection.  
         [0024]    (e) A capacity matrix H(node,node,connection,k-path), corresponding to a hypothetical network, is a 4-dimentional matrix which represents the capacity assignment of the network. A capacity matrix can have capacity assignment from 1 or more connections. An H matrix is said to be SLA-enabled if all the SLA requirements are met.  
         [0025]    The goal of optimization of resources is to be able to fit as many VPNs into a network of finite capacity. However, since VPN requirements may come in various forms, there is no easy way to define what is an optimal allocation. Examples of criteria include minimum hops (or shortest path), or minimum delay. Taking into account SLA metrics including packet loss and delay, one common criterion is load balancing. With respect to load balancing, one strives to allocate network resources in such a way that the maximum load on any link is minimized. There are different measures (metrics) for achieving load balancing. Examples are mini-max, mini-xth percentile, which means that the largest x-th percentile of the allocated capacity is to be minimized, mini-mean, or mini-standard deviation. In the following, the method is based upon the mini-max criterion. However, the heuristic algorithm which is now described is applicable to all the other global criteria or combination of these criteria.  
         [0026]    The starting point is the assumption that k shortest paths for each connection can be obtained. The devised technique is illustrated with reference to VPN network  100  in FIG. 1, with summary information set forth in Table 1. Network  100  is composed of six VPN end-points H 1 , H 2 , . . . , H 6 , labeled  101 - 106 , respectively, and ten switching nodes S 1 , S 2 , . . . , S 10 , labeled  121 - 130 , respectively. The total number of VPN connections is 30 (i.e., C=N(N−1)=6(6−1)=30). Also shown in FIG. 1 is a representative set of links  141 ,  142 , and  143 ; one exemplary path from H 1  to H 2  is composed of these three links, which are shown explicitly in Table 1—other links composing paths are obtained straightforwardly.  
                               TABLE 1                       Connection   Connection 1   Connection 2       Connection C       Path   (H1-H2)   (H1-H3)   . . .   (H5-H6)                   k = 1   S1-S2   S1-S3-S5       S7-S8-S6           (links 141-142-143)       k = 2   S1-S3-S2   S1-S2-S6-S5   . . .   S7-S4-S6       k = 3   S1-S3-S4-S6-S2   . . .       . . .       . . .   . . .                  
 
         [0027]    The problem is to find a path (out of the k paths) that satisfies certain global criteria. An exhaustive search of the entire K-C space would require checking for K C  possibilities, which is NP (non-polynomial time).  
         [0028]    A straightforward approach, as alluded to above, is via a sequential assignment, which simply finds a best path for each of the connections sequentially (for connections 1 to C, in no particular order). However, the sequential approach does not take into account of available information regarding the resource requirement of all the C connections (which is a known quantity), and thus can generate unbalanced loading of the network.  
         [0029]    The devised heuristic algorithm, on the other hand, strives to use all the available information to arrive at a feasible global optimum. This is achieved with the use of three important notions in the method steps, namely: (i) a hypothetical network; (ii) an iterative procedure; and (iii) randomization of starting points.  
       Heuristic VPN Configuration Algorithm  
       [0030]    The steps for the heuristic VPN configuration algorithm are shown in FIG. 2. The algorithm commences with finding a set of k-shortest paths for each of the C connections. The search for this set of k-shortest paths needs to be done only once since shortest paths are a function of the topology of the network and not a function of the state (capacity) of the network.  
         [0031]    From this initial set of k-paths, the paths that violate SLAs (such as end-to-end physical delay) are first eliminated. Then, a random set of paths from the remaining k paths is chosen and assigned into a hypothetical network H. At this time, H may not be SLA-enabled.  
         [0032]    Next, an iteration process is initiated to re-assign each of the paths of the connections. Every time a new path is reassigned, it is chosen with respect to two criteria:  
         [0033]    (a) The path satisfies the SLA requirement or, if none of the k paths satisfy the SLA requirement, the least violator is chosen.  
         [0034]    (b) The path that minimizes a given metric, such as, for example, {a*max+b*mean}, where “max” is the hop in H that has the maximum capacity, and “mean” is the mean of the k-path.  
         [0035]    If there are conflicts between criteria 1 and 2, criterion 1 should have priority.  
         [0036]    The first iteration starts from connection 1 to connection C, and if a local minimum (defined as no change in all the connections) is not attained, the algorithm continues the second iteration and reassigns all the connections again. This is done until a local minimum is found.  
         [0037]    A local minimum is generally not a globally optimum solution, unless the search space is a convex. Since there is no reason to assume that the space is convex, multiple searching is performed with different initial set of k-paths. The search may be terminated if either certain pre-defined improvement has been achieved, or if the number of trials has attained a pre-defined limit. In this way, a solution that is produced is much better than a local minimum.  
         [0038]    The steps of FIG. 2 are as follows:  
         [0039]    Step 205—determining k shortest paths for all the C connections of the VPN  
         [0040]    Step 210—commence with random k-paths for all the C connections  
         [0041]    Step 215—eliminate those k-paths that do not satisfy SLA requirements  
         [0042]    Step 220—place the k-paths into a hypothetical network H  
         [0043]    Step 225—start the iteration loop  
         [0044]    Step 230—start the connection loop (c)  
         [0045]    Step 235—subtract k-path of the connection c from H to obtain H temp    
         [0046]    Step 240—eliminate those k-paths of connection c that do not satisfy the SLA requirements  
         [0047]    Step 245—choose a k-path for connection c based on a*max+b*mean  
         [0048]    Step 250—update H=H temp +K  
         [0049]    Step 255—continue connection loop  
         [0050]    Step 260—after connection loop complete, determine if there is a local minimum  
         [0051]    Step 265—if not a local minimum, then continue to next iteration  
         [0052]    Step 270—if a local minimum, determine if this is a global minimum; if not a global minimum, then go to step 210  
         [0053]    Step 275—if a global minimum, there is sufficient information to configure the network  
       EXAMPLE  
       [0054]    The devised algorithm is exemplified with reference to network  100  of FIG. 1. For SLA, the notion of equivalent bandwidth is applied, which maps packet loss ratio into a bandwidth requirement. In the devised technique, it is assumed that if any one of the links of a path exceeds certain pre-defined number, that particular path will not be used for the current selection. The heuristic algorithm is applied to this reference network for 100 times, each with a different set of VPN demand that ranges from 0.2 to 20 capacity units. K=4 is selected, along with a=9.5 and b=0.5. Table 2 shows the result of running the heuristic VPN planning algorithm for 100 times compared to other known approaches. For each run, the heuristic algorithm is compared with the sequential approach. It is seen that the heuristic approach outperforms the sequential approach almost all the time. For the experiments that the heuristic algorithm does not yield better results, it converges to the same result as the sequential approach.  
                                                 TABLE 2                                   Compare to   Compare to           minimum hops   sequential algorithm                                    K = 4;                       # of trials = 100       # of times heuristic algorithm   96       35       performs better       Heuristic algorithm better by an   9.9   units   3.8   units       average of       K = 3;       # of trials = 100       # of times heuristic algorithm   95       43       performs better       Heuristic algorithm better by an   10.8   units   3.6   units       average of                  
 
       Implementation of the VPN Network  
       [0055]    With reference to FIG. 3, there is shown a high-level block diagram of an augmented portion of FIG. 1 that is considered illustrative of the technique for configuring overall network  100  based upon the heuristic algorithm described above. In FIG. 3, network manger  301  is shown as interacting with local controllers  311  and  312  associated with switching nodes  111  and  112 , respectively. Although the local controllers are shown as being appliqués to nodes  111  and  112  for expository purposes, in practice controllers  311  and  312  are typically integral to nodes  111  and  112 . Moreover, network manager  301 , although shown as a stand-alone component, may also be co-located with or be any integral part of any one of the nodes. Network manager  301 , at a minimum, stores the VPN network set-up/configuration information obtained by the heuristic algorithm in an off-line implementation, or may preferably dynamically compute the network configuration information on a real-time basis—execution of the algorithm typically requires only tens of seconds. All switching nodes of network  100  register with manager  301  via the corresponding ones of the local controllers (e.g., controller  311  of node  111 ) over conventional low-speed signaling links exemplified by link  321  coupling local controller  311  and link  322  coupling controller  312  with network manager  301 . Manager  301  then notifies each of the switching nodes with local configuration information for the links emanating from each switching node that is sufficient to configure each switching node to effect the VPN network. This link configuration information is used to arrange conventional a look-up table in each switching node (e.g., in ATM, the VCI table) to configure the VPN network. As VPN network traffic is routed from one switching node to another, this traffic is forwarded over the corresponding links assigned to carry the traffic for the VPN network.  
         [0056]    The process to configure a VPN network for a given customer is commenced by a service order generated from a customer order request, as depicted by service order block  302  in FIG. 3; the service order includes SLA requirements that are passed to network manager  301 . In addition, once the VPN network is configured upon execution of the heuristic algorithm and downloading link information to the switching nodes, it possible to dynamically re-configure the VPN network when necessary, which may due to, for example, link outages.  
         [0057]    Conventionally, traffic state change data is collected for the network of FIG. 1, of which the VPN network is a subset—the activity of collecting traffic state change data is represented by traffic processing block  303 . Data is collected by traffic processing block  303  over conventional low speed links  333  and  334  connecting traffic processing block  303  with local controllers  311  and  312 , respectively.  
         [0058]    The flow diagram of FIG. 4 depicts the inventive methodology carried out by the structure of FIG. 3, as alluded to in the foregoing description of FIG. 3. Thus, in one illustrative embodiment, network manager  301  has stored, upon its initialization or by downloading, the prescribed heuristic algorithm (summarized by FIG. 2), as depicted by processing block  410 . The algorithm is used to compute, as per processing block  420 , the network paths to effect the VPN subject to the SLA constraints. As depicted by processing block  430 , once the path set-up is computed, each switching node  111 ,  112 , . . . , via communication between network manager  301  and each associated local controller  311 ,  312 , . . . , is informed of information to thereby configure network  100  as the desired VPN. Upon configuration, as evoked by processing block  440 , traffic is routed among VPN end-points  101 , . . . ,  106  in correspondence to the VPN configuration.  
         [0059]    Although the present invention have been shown and described in detail herein, those skilled in the art can readily devise many other varied embodiments that still incorporate these teachings.