Abstract:
A method for decomposing a service activation request (SAR) into sub-requests for specific network resources and classifying the SAR with an adaptive bucket value based on the dynamic performance characteristics of the corresponding network resources. Each SAR has a virtual bucket value whose size is determined by the bucket values of its constituent sub-requests. Over time, as multiple SARs are processed, the bucket values associated with each requested resource are adjusted to reflect system resource loading and availability. If the bucket value of a constituent sub-request is adaptively decreased down to a zero value, for instance due to an overflow condition or an excess of requests for that particular service, any new SAR requesting the same resource will be prevented from decomposition and processing. This will happen even if the sub-request is mature, i.e., due to be executed in the very near-term. This mechanism insures optimal utilization of network resources and provides an efficient, automated handling mechanism for processing complex service activation requests.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to network management systems and, in particular, to provisioning services across a network or a set of networks. 
     2. Description of the Related Art 
     Network operators and network customers request the activation of services by use of simple service orders known as service activation requests (SARs), often provided on paper hardcopy. SARs are processed based upon customer demand and their requested activation date. Customers may demand immediate activation or delayed activation in the short- or long-term, i.e., service requests may have various levels of time criticality. In most situations this is a highly manual and labor- and paper-intensive process. 
     To add a further dimension to the problem, SARs (including service changes) may also involve complex interactions between many disparate network management systems (NMSs) and Element Management Systems (EMSs) and the elements therein and thus may not be confined to a single network resource under local control. Such a SAR is referred to as a complex SAR, containing many service sub-requests. For instance, a customer may request end-to-end service between two distant cities. Provision of this service may require obtaining dedicated bandwidth on several network resources owned and/or controlled by different parties (NMSs, or EMSs), such as a metropolitan area network in the originating city, a long-haul transport network, and a metropolitan network in the destination city. 
     Each SAR has its own “due date,” i.e., the calendar date and time on which the customer expects the entire service to be provided. All sub-requests share the same SAR due date. 
     This complexity introduces a level of difficulty in processing SARs with all of the necessary detail to meet customer requirements. As can be seen above, a large-scale (complex) service activation request necessarily includes numerous activation sub-requests addressed to network elements potentially owned by several different parties. Processing such a request currently over-burdens network operators, the network management system or systems where present, and the element management systems. Virtually all of current SARs and their components are handled manually using numerous communication systems, including computer networks and software systems, facsimiles, and the mails. 
     Prior art systems have attempted to address these shortfalls by a technique known as bulk provisioning. This technique requests multiple services in one large SAR, but is still essentially paper-oriented. While a single SAR contains numerous sub-requests affecting multiple network elements, the decomposition of the SAR is still performed manually, on paper, by human network planners. Bulk provisioning is thus insufficiently fast to keep up with the expanding needs of the modem network. 
     Automated bulk provisioning (ABP) is also known in the art. Typically, an ABP service activation module (SAM) contains many SARs for the same end-to-end service. For example, an ABP SAM might request “one thousand 25 Mbps virtual private network (VPN) services from San Jose, California to Austin, Texas.” Such a SAM thus consists of one thousand VPN SARs; as noted above, each SAR may contain many sub-requests. Current ABP systems, however, often lack robustness and tolerance for resource contention. In the present example, if any one of the sub-requests in any of the 1000 end-to-end VPN SARs cannot be processed, the corresponding SAR will fail. Any sub-request connections already provisioned for the failed SAR must be “rolled back” or de-allocated. The entire ABP SAM may also fail, if the management system that created it so dictates. 
     ABP systems are also non-scaleable to situations where a large number of different end-to-end services are requested because they lack robust means for managing resource overflow and provisioning errors. 
     Computer-based provisioning systems, including multi-threaded polling systems, have attempted to address the speed and efficiency problems, but with little success. Multi-threaded polling, in particular, requires too much memory and suffers from performance degradation when faced with complex SARs affecting multiple network elements. Resource shortfalls and the consequent contention issues also cause dead locks in which no SAR or sub-request is able to obtain the contended resource. Prior art automated systems also require complex rollback mechanisms to undo partially-filled complex SARs when a resource contention or error occurs. 
     What is needed is a method of automatically processing and decomposing complex SARs into service sub-requests appropriate to the required multitude of network resources affected. Furthermore, such a method must be fast, robust, and highly efficient and operable in a wide range of networks of varying complexity. 
     SUMMARY 
     Presently disclosed is a method for decomposing a service activation request (SAR) into a series of sub-requests, one per each specific network resource requested, and classifying the SAR with an adaptive bucket value (i.e., classifying it according to a ranking index that can change according to circumstances) based on the dynamic performance characteristics of the corresponding network resources. Each SAR has a virtual bucket value (ranking index) whose size is determined by the bucket values of its constituent sub-requests. Over time, as multiple SARs are processed, the bucket values associated with each sub-request&#39;s requested resource are adjusted to reflect system resource loading and availability. If the bucket value of a constituent sub-request is adaptively decreased down to a zero value, for instance due to an overflow condition or an excess of requests for that particular service, any new SAR requesting the same resource will be prevented from decomposition and processing. This will happen even if the sub-request is mature, i.e., due to be executed in the very near-term. This mechanism insures optimal utilization of network resources and provides an efficient, automated handling mechanism for processing complex service activation requests. 
     The present method also eliminates idling of the service activation request processing system due to resource contention and eliminates the need for complex database locking and/or blocking mechanisms to prevent over-utilization of network resources. Furthermore, the system operates without requiring any polling or absolute measurement of network performance in terms of the network&#39;s ability to provision services. Rather, the systems utilizes only the network response time to a request for services to determine its ability to handle further requests. By using a closed loop adaptation system, the present method constantly adjusts its response to each new complex SAR based on the ability of the system to process past SARs. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The present disclosure may be better understood, and its numerous features and advantages made apparent to those skilled in the art by referencing the accompanying drawings. 
     FIG. 1 is a high-level flowchart of the process of one embodiment of the present invention. 
     FIG. 2 is a high-level flowchart of the window size adjustment process according to one embodiment of the present invention. 
    
    
     The use of the same reference symbols in different drawings indicates similar or identical items. 
     DETAILED DESCRIPTION 
     Service activation requests arrive at the service or business management system (as those terms are understood in the context of the well known telecommunications management network [TMN] model) and are processed and fulfilled (provisioned) by the lower levels of the TMN system. Network operators and administrators currently activate services on customer demand by communicating directly with the affected resource using the NMS and/or the low-level EMS (e.g., by using a graphical user interface or command line interface to configure a router). As currently known, this is a highly manual and paper-intensive process. 
     The TMN and network management systems in general are further described in H. Wang,  Telecommunications Network Management  McGraw-Hill (1999), incorporated herein by reference in its entirety. 
     Provisioning, whether through a high-level (multi-element) NMS or simply the access port for a single router or other element, is performed in a completely asynchronous fashion. Customers may request service at any time of any calendar day, and expect complete, end-to-end fulfillment by a customer-supplied due date. Furthermore, SARs may contain sub-requests for service affecting any number of network elements, sub-requests that, themselves, are to be filled asychronously with the end-to-end service of the SAR. In general, each sub-request must be filled before the end-to-end requests (represented by the complex SAR) is filled, but the individual ordering of sub-request fulfillment is not necessarily defined at the time the SAR is initiated. 
     Referring to FIG. 1, the process  100  of one embodiment the present invention performs maturity checking  110  on received SAR  105  to determine its overall (end-to-end) due date. This due date, a calendar date and time, is used to calculate a SAR time index, which can be any heuristic or fuzzy logic ranking of timeliness, such as an index from the set {now, soon, later, much later} or a numerical ranking. 
     Maturity checking  110  comprises both aggressive and passive checking. Aggressive checking means each SAR itself contains a wake-up alarm seed which will wake the SAR when it matures and thus inform the checker  110  that it is due to be processed. Passive checking means a scheduler (or polling) function is provided by checker  110  to manage and monitor the wake-up process. Embodiments of the present invention may contain either or both of these mechanisms. Both are well-known in the art. 
     If the SAR is found to be mature in test  120 , process  100  determines  130  the resources required by the constituent sub-requests of SAR  105 . “Mature” status (in test  120 ) is defined by the following equation. 
     
       
         Δ T   S   &lt;=T   P   
       
     
     where 
     
       
         Δ T   S   =T   DUE DATE   −T   NOW   
       
     
     and 
     
       
         
           T 
           P 
           =T 
           PRE-PROCESSING TIME 
         
       
     
     
       
         =max{ T   SYSTEM ROUND-TRIP DELAY   +T   DECOMPOSE   +T   ROUTING-CALCULATION } 
       
     
     wherein T SYSTEM ROUND-TRIP DELAY  is the time required by the management system (NMS or EMS, as appropriate) to send a configuration command and receive an acknowledgment from the successfully-configured element. This factor is typically on the order of several seconds. T DECOMPOSE  is the time required to actually break a complex SAR down into the actual configuration commands required to provision all constituent sub-requests. This factor is typically on the order of milliseconds. T ROUTING-CALCULATION  is the time needed to calculate the end-to-end route requested in the SAR and determine specific addresses and other parameters necessary to complete the link. This factor is typically on the order of nano- or microseconds. The above factors are set to a pre-defined default value at system initialization and are user adjustable. T SYSTEM ROUND-TRIP DELAY  is measured and updated throughout the process of some embodiments of the present invention, as will be further discussed below with reference to FIG.  2 . 
     Thus, as part of maturity test  120 , process  100  identifies the estimated pre-processing time T P  (i.e., the time required to decompose the SAR into its constituent sub-requests) associated with SAR  105 . This identification is accomplished, in one embodiment of the present invention, using initialization database  122 . Database  122  contains a list of all possible SAR types for the target network (or network element) and the current estimated time required to decompose (T DECOMPOSE ) each typical SAR into its constituent sub-requests. Initial values of T ROUTING-CALCULATION  and T SYSTEM ROUND-TRIP DELAY  are also stored in initialization database  122 . 
     If SAR  105  is not mature, it is placed in storage  125  and is continuously monitored by aggressive/passive checker  110 . 
     Step  130  determines the resource required to provision each sub-request, which is by definition limited to a single resource per sub-request. This determination is accomplished in one embodiment of the present invention by comparing the contents of SAR  105  against a database of network resources (not shown). 
     Process  100  next determines an initial bucket value (IBV) for each sub-request in step  135 . The IBV is also referred to as the initial ranking index. This determining consists, in one embodiment of the present invention, of a simple lookup in initialization database  122  of a default value for each resource set by the operator. 
     The SAR is assigned a virtual bucket value (VBV) in step  140 . The virtual bucket value is determined for the SAR as a whole and is also a ranking index. The virtual bucket value is determined by a simple minimum function of all sub-request bucket values, i.e.: 
     
       
         Virtual Bucket Value=min( BV   SR1   , BV   SR2   , . . . BV   SRn ) 
       
     
     where BV SR1  denotes the bucket value of the first sub-request and BV SRn  denotes the BV of the last sub-request invoked by SAR  105 . Note that for the very first sub-request processed, its BV is set to the BV determined in step  135  by the database lookup. On subsequent invocations of the same sub-request (i.e., when later received SARs request the same resource), step  135  supplies the adaptively-updated bucket value computed by monitoring process  200 , described below with reference to FIG.  2 . 
     If the virtual bucket value is greater than zero in test  150 , SAR  105  is processed  160 . In particular, process  100  calculates  162  the best route across several networks and determines  164  the precise NMS/EMS commands necessary to configure all network elements in the best route as required by each sub-request. Calculation  162  and determination  164  are accomplished by means well-known in the routing arts. The route is automatically provisioned  166  using the detailed commands determined in step  164  by means well-known in the art thus fulfilling the sub-requests of SAR  105 . Any provisioning errors are handled and reported by means well-known in the art as well. 
     If, on the other hand, the VBV is less than or equal to zero, denoting a resource shortfall or other inability to process, then SAR  105  is passed to storage  125  for monitoring by aggressive/passive checker  110  as described above. The system will continue to attempt to provision SAR  105 , waiting for resources to become available. In some embodiments of the present invention, this loop will continue indefinitely. In other embodiments, however, a monitoring process, part of aggressive/passive checker  110 , senses the lack of resources (i.e., VBV≦0) removes SAR  105  from the queue, and alerts the appropriate management system of its inability to fulfill the SAR. 
     FIG. 2 shows the process of determining and updating the sub-request BVs. Monitoring process  200  operates continuously and in parallel with SAR decomposition process  100  (FIG.  1 ). Monitoring process  200  begins by calculating the accumulated delay  205  for each requested resource according to the function: 
     
       
         Accumulated Delay=Σ( T   SYSTEM ROUND TRIP DELAY −delay Threshold) i   
       
     
     Wherein delay Threshold is a pre-determined time threshold used to set the sensitivity of process  200  to variations in T SYSTEM ROUND-TRIP DELAY . The summation is carried out for the i previous configuration commands sent to the resource of interest in step  166  of FIG. 1, where i is a fixed number set by the operator, typically on the order of 5 to 10. 
     Note that while the actual T P  includes T DECOMPOSE  and T ROUTING  calculation, the latter two factors are many orders of magnitude less than T SYSTEM ROUND-TRIP DELAY  and can thus be safely ignored. 
     If the accumulated delay is greater than zero for a resource, the actual delay is tested  215  against a size decrease trigger. The size decrease trigger is a pre-determined value above which the resource&#39;s BV must be decreased to reflect a high accumulated delay. If test  215  is negative, the process returns to monitoring and calculating the accumulated delay for the next resource, step  205 . If test  215  is positive, process  200  checks to see if the BV was recently (i.e., within a small, pre-determined number of monitoring cycles) decreased. If so, then it is possible that that resource has become unavailable or is not operating at full capacity. To ascertain the resource&#39;s true condition, the time interval since the last decrease is tested  224  against a pre-determined timeout parameter. 
     If the interval since the last size adjustment is less than the timeout value, a fast BV decrease  226  will occur. In one embodiment of the present invention, the BV fast decrease is accomplished according to the formula. 
     
       
           BV=BV  (1−fastDecreaseFactor) 
       
     
     where fastDecreaseFactor is a percentage value preset by the operator. This fastDecreaseFactor drives the BV toward zero, thus signifying the impossibility of provisioning the resource to the SAR. 
     On the other hand, if the outcome of test  224  is negative (signifying a decrease interval greater than the size adjust timeout value), the decrease counter is cleared and the process returns to test  220 . Now, because the counter is cleared, test  220  fails and the BV is decreased by a normal decrease amount. In one embodiment, the normal size decrease is performed according to the following formula: 
       BV=BV  (1−sizeDecreaseFactor) 
     where, as above, sizeDecreaseFactor is a percentage value preset by the operator. The sizeDecreaseFactor is, of course, less than fastDecreaseFactor. 
     In either the normal or the fast BV decrease case, process  200  returns to calculating the accumulated delay for the next requested resource at step  205 . 
     If the outcome of test  210  is negative, i.e., the accumulated delay is less than or equal to zero, the negative of the accumulated delay value (e.g., its absolute value) is compared to a size increase trigger. If the accumulated delay has fallen enough to enable an increase in the BV, steps  240 ,  242 ,  244 ,  246 , and  248  accomplish either a regular or a fast BV increase. As can be seen from FIG. 2, these latter steps operate analogously to the BV decrease logic discussed above. Similarly, in some embodiments steps  242  and  246  use similar equation as steps  222  and  226 , respectively, except that the increase logic uses factors sizeIncreaseFactor and fastIncreaseFactor instead of sizeDecreaseFactor and fastDecreaseFactor. 
     The following table shows representative values of the system threshold, trigger, and other parameters used in one embodiment of the present invention. 
     
       
         
               
               
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 delayThreshold 
                 3000 ms 
                   
               
               
                   
                 sizeIncreaseTrigger 
                 8000 ms 
               
               
                   
                 sizeDecreaseTrigger 
                 8000 ms 
               
               
                   
                 sizeAdjustTimeout 
                 30,000 ms 
               
               
                   
                 fastDecreaseFactor 
                 40% 
               
               
                   
                 sizeDecreaseFactor 
                 20% 
               
               
                   
                 fastIncreaseFactor 
                 30% 
               
               
                   
                 sizeIncreaseFactor 
                 15% 
               
               
                   
                   
               
             
          
         
       
     
     The order in which the steps of FIGS. 1 and 2 are performed is purely illustrative in nature. In fact, the steps can be performed in any order or in parallel, unless otherwise indicated by the present disclosure. 
     The method of the present invention may be performed in either hardware, software, or any combination thereof, as those terms are currently known in the art. In particular, the present method may be carried out by software, firmware, or microcode operating on a computer or computers of any type. Additionally, software embodying the present invention may be in the form of computer instructions in any form (e.g., source code, object code, interpreted code, etc.) stored in any computer-readable medium (e.g., ROM, RAM, magnetic media, punched tape or card, compact disc (CD) in any form, DVD, etc.). Furthermore, such software may also be in the form of a computer data signal embodied in a carrier wave, such as that found within the well-known Web pages transferred among computers connected to the Internet. Accordingly, the present invention is not limited to any particular platform, unless specifically stated otherwise in the present disclosure. 
     While particular embodiments of the present invention have been shown and described it will be apparent to those skilled in the art that changes and modifications may be made without departing from this invention in its broader aspect and, therefore, the appended claims are to encompass within their scope all such changes and modification as fall within the true spirit of this invention.