Abstract:
In an IPTV network, cache memory assigned to each DSLAM, Central Office (CO) or Intermediate Office (IO) can be determined by defining a network cost function having cache memory per DSLAM, cache memory per CO and cache memory per IO as decision variables. The network cost function can be minimized to determine the optimal cache memory size for the network. The network cost function can be subject to boundary constraints that the cache memory is between zero and a maximum cache memory size for each network node type, allowing the network cost function to be solved as a 3-ary tree.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims priority to U.S. provisional patent application Ser. No. 61/137,717, filed Aug. 1, 2008, the entire contents of which are herein incorporated by reference. 
     
    
     FIELD OF THE INVENTION 
       [0002]    This invention relates to Internet Protocol Television (IPTV) networks and in particular to caching of video content within the network. 
       BACKGROUND OF THE INVENTION 
       [0003]    IPTV networks in metro areas have a hierarchical structure. At the top of this hierarchy, shown in  FIG. 1 , is a Video Hub office (VHO)  19  where all video contents are stored in video servers. The VHO  19  is connected to several Intermediate Offices (IO)  18 , every IO  18  is connected to several Central Offices (CO)  16 , every CO  16  is connected to several Digital Subscriber Line Access Multiplexers (DSLAMs)  14 , and every DSLAM  14  is connected to a certain number of subscribers  12 . 
         [0004]    In an IPTV network, Video on Demand and other video services generate large amounts of unicast traffic from VHO  19  to subscribers  12  and, therefore, require additional bandwidth and equipment resources in the network. To reduce this traffic (and overall network cost), part of video content (e.g. most popular titles) may be stored in caches  15  closer to subscribers, e.g., in DSLAM  14 , in service switches at COs  16 , or in service routers at IO  18 . 
         [0005]    On one hand, cache memory has a cost, but on another hand, caching of video content allows decreasing amount of traffic from upstream levels of this hierarchy and, therefore decreasing of network cost. Cache effectiveness is defined as the hit rate, i.e. the ratio of traffic that is served from the cache to the total amount of requested traffic. Hit rate depends on size and throughput of the cache, statistical characteristics of the traffic (e.g., popularity distribution of different titles, their bit rate, size in memory) and on a caching algorithm. For an ideal caching algorithm, the cache size and statistical characteristics of the traffic define hit rate. 
         [0006]    Another important factor is granularity of network elements. In case of cache that means that cache is allocated in units whose size does not exceed some limit; cost of cache includes cache unit cost and cost per unit of memory. In case of equipment (switches, routers), cost includes unit cost, I/O module (IOM) cost, Model Driven Architecture (MDA) cost and port cost. The number of ports, MDA, IOMs and equipment units are defined by traffic as a part of the dimensioning process. There is a limited number of IOMs per equipment, and these resources should be shared by the MDAs and cache units. 
         [0007]    Overall, to find an optimal (in terms of network cost) location and amount of cache memory is a complex optimization problem. 
         [0008]    What is required is a system and method for optimizing a cache arrangement in an IPTV network. 
       SUMMARY OF THE INVENTION 
       [0009]    In one aspect of the disclosure there is provided a method for determining cache memories of one or more network nodes of an Internet Protocol Television (IPTV) network. A network cost function is defined comprising a plurality of cache memory decision variables that represent a cache memory size at one of the one or more network nodes and at least one cache hit rate function dependent on at least one of the cache memory decision variables. The network cost function is optimized to determine the plurality of cache memory decision variables. 
         [0010]    In one aspect of the disclosure, there is provided an Internet Protocol Television network comprising a plurality of network nodes, a plurality of the network nodes comprising a cache, wherein a size of the memory of the cache is in accordance with a minimum solution of a network cost function for the network. 
         [0011]    In one aspect of the disclosure, there is provided a computer-readable medium comprising computer-executable instructions for execution by a processor that, when executed cause the processor to receive a plurality of input parameters and calculate a cache memory size for a plurality of network nodes of an Internet Protocol TeleVision network that minimizes a network cost of the Internet Protocol TeleVision network. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0012]    Reference will now be made to specific embodiments, presented by way of example only, and to the accompanying drawings in which: 
           [0013]      FIG. 1  illustrates an architecture of an IPTV network; 
           [0014]      FIG. 2  illustrates a method for determining cache memory size; 
           [0015]      FIG. 3  illustrates a hit rate function and its derivative; 
           [0016]      FIG. 4  illustrates a minimum of a convex function on a segment; 
           [0017]      FIG. 5  illustrates a logical 3-ary tree; 
           [0018]      FIG. 6  illustrates an optimal cache configuration as a function of ZM power and traffic; 
           [0019]      FIG. 7  illustrates an optimal cache configuration as a function of traffic; 
           [0020]      FIG. 8  illustrates an equipment cost structure and its impact on cache memory; 
           [0021]      FIG. 9  illustrates an optimal cache configuration as a function of equipment cost; 
           [0022]      FIG. 10  illustrates an optimal cache configuration as a function of memory cost; 
           [0023]      FIG. 11  illustrates a system processor and associated memory; 
           [0024]      FIG. 12  illustrates an instruction set that may be executed on the processor of  FIG. 11 ; and 
           [0025]      FIG. 13  illustrates a user processor and memory in association with the system processor of  FIG. 11 . 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0026]    In  FIG. 2 , there is shown a method  100  for determining cache memories of one or more nodes of the IPTV network. At step  101 , a network cost function is defined that includes a plurality of cache memory decision variables that represent a cache memory size the network nodes and at least one cache hit rate function dependent on the cache memory decision variables. The network cost function is optimized at step  102  to determine the plurality of cache memory decision variables. 
         [0027]    The present disclosure thus describes an analytical model of hierarchical cache optimization. This model depends on basic parameters such as traffic, topology, and cost parameters. More simple cost structure and some reasonable assumptions allow an analytically optimal solution of the problem and an analysis of the factors that impact the solution. The optimal cache architecture may use caching at any combination of network hierarchy—DSLAM, CO and IO—depending on traffic, topology, and cost parameters, and thus hierarchical caching may be an important option for cost saving. 
         [0028]    Content caching is one of the most effective solutions to improve performance and cost effectiveness of multimedia services. In the present Applicant&#39;s copending patent application Attorney Docket No. 802883, U.S. patent application Ser. No. 12/284,079, the entire contents of which are incorporated herein by reference, a simplified analytical model for cache optimization was presented. The total network cost in this model was the sum of transport cost and memory cost, where the transport cost was proportional to the traffic amount that traverses the equipment, and memory cost was proportional to the memory size. In the Applicant&#39;s earlier patent application, unlike the present disclosure, no boundary cases (i.e., case without cache or with maximum cache size) were considered and network cost minimum assumed to be at a stable point (i.e., where derivative of network cost by appropriate parameters is equal to zero). The present disclosure demonstrates that boundary cases can be important for understanding why in some cases optimal solution does not require caching at some levels, or requires using maximum allowed cache size on another levels. However, boundary cases introduce significant complexity to the problem because they generate a large number of cases to be considered. 
         [0029]    The Applicant&#39;s copending patent application Attorney Docket No. 801935, PCT application Number PCT/U.S. Ser. No. 08/10269, filed on Aug. 29, 2008 which is based on and claims priority from U.S. Provisional Patent Application No. 60/969,162 filed 30 Aug. 2007, the entire contents of which are herein incorporated by reference, describes the concept of content cacheability and a fast algorithm that uses cacheability to optimally partition a cache between several video services with different traffic characteristics and content sizes. The goal of the optimization was to serve maximum (in terms of bandwidth) amount of subscribers&#39; requests subject to constraints on cache memory and throughput. 
         [0030]    In order to solve a cache optimization problem analytically in accordance with the present disclosure, some simplifying assumptions are made. 
         [0031]    First, granularity factors mentioned above are ignored. In particular, it is assumed that cost of cache is proportional to cache size and equipment cost is proportional to amount of traffic that traverse the equipment. More specifically, the equipment cost is estimated based on amount of traffic received by this equipment from upstream levels of network hierarchy (upstream traffic) and on amount of traffic send by this equipment downstream (downstream traffic). In order to calculate a total network cost, a unit cost of cache memory is defined for each level of network hierarchy (DSLAM, CO, IO). A unit cost of upstream and downstream traffic is also defined, as will be described in greater detail below. 
         [0032]    The next assumption regards hit rate, H(m), as a function of cache memory m. Hit rate, H(m)  31 , increases with memory m  32  as shown in  FIG. 3 . In addition to that, it is assumed that function H(m) has a continuous derivative H′ (m)  33  and this derivative decreases (effect of diminishing return for hit rate). This condition means that function H(m) is strictly concave. To justify this assumption it is noted that function H′ (m) in some ideal cases (when caching algorithm has complete information about statistical characteristics of the traffic) is equivalent to a popularity curve, which, indeed, decreases as a function of a title&#39;s rank. In case of multiple services, hit rate depends on popularity distribution and other characteristics of individual services, as described in the Applicant&#39;s copending patent application Attorney Docket No. 801935, PCT application Number PCT/U.S. Ser. No. 08/10269, referenced above. 
         [0033]    Because an IPTV network has a hierarchical (tree) structure and traffic is downstream-oriented, a concept of a “virtual” cache can be used. The “virtual” cache in any node of the tree is the actual cache at the node augmented by the cache sizes in a node deeper (towards the leafs) in the tree. A video content residing in the “virtual” cache of the node (i.e., in the node itself or in a node further down the tree) reduces the unicast traffic on the feeder link towards that node (and on all links towards the root of the tree). In the following, it is assumed that out of two cache resources—cache size and cache throughput—cache size is a limiting factor and the only resource to be considered. This assumption can be justified for a cache in DSLAM by setting a maximum cache size that guarantees that traffic from the cache does not exceed cache throughput. In this case, for a given traffic pattern of IPTV subscribers, if cache size per DSLAM is m 1 , cache size per service switch at CO is m 2 , and cache size per service router at IO is m 3 , then caching related traffic reduction (hit rate) at CO level is H(m 1 +m 2 ), and traffic reduction at IO level is H(m 1 +m 2 +m 3 ). 
         [0034]    This model considers unicast traffic only. Multicast traffic is a relatively small portion of total traffic on CO and IO levels and, therefore, does not make a big impact on equipment cost on those levels. Multicast traffic is a significant part of the total traffic on DSLAM level. However, there is almost no dependency of DSLAM cost on amount of traffic that traverses DSLAMs. 
       NOTATION AND MATHEMATICAL FORMULATION 
     Notations 
       [0035]    Decision Variables: 
         [0000]    m 1 —cache memory size per DSLAM (GB);
 
m 2 —cache memory size per service switch at CO (GB);
 
m 3 —cache memory size per service router at IO (GB).
 
         [0036]    Traffic and Topology Parameters: 
         [0000]    T—total amount of traffic requested by subscribers (Mbs);
 
H(m)—hit rate function;
 
N 1 —total number of DSLAMs in the network;
 
N 2 —total number of service switches in all COs in the network (it may be several service switches per CO);
 
         [0037]    N 3 —total number of service routers in all IOs in the network (it may be several service routers per IO); 
         [0000]    M 1 —maximum cache size per DSLAM (GB);
 
M 2 —maximum cache size per service switch at CO (GB);
 
M 3 —maximum cache size per service router at IO (GB).
 
         [0038]    Cost Parameters: 
         [0000]    c 1   m —unit cost of cache memory in DSLAM ($/GB);
 
c 1   m —unit cost of cache memory in CO ($/GB);
 
c 3   m —unit cost of cache memory in CO ($/GB);
 
c 11   t  and c 12   t —unit cost of downstream and upstream traffic for DSLAM ($/Mbs);
 
c 21   t  and c 22   t —unit cost of downstream and upstream traffic for CO ($/Mbs);
 
c 31   t  and c 32   t —unit cost of downstream and upstream traffic for IO ($/Mbs);
 
c 41   t  and c 42   t —unit cost of downstream and upstream traffic for VHO ($/Mbs);
 
         [0039]    Mathematical Formulation 
         [0040]    Total network cost, NtwkCost, may be calculated as: 
         [0000]    
       
         
           
             
               
                 
                   NtwkCost 
                   = 
                   
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         3 
                       
                        
                       
                         
                           N 
                           i 
                         
                          
                         
                           c 
                           i 
                           m 
                         
                          
                         
                           m 
                           i 
                         
                       
                     
                     + 
                     
                       Tc 
                       11 
                       t 
                     
                     + 
                     
                       
                         T 
                          
                         
                           ( 
                           
                             
                               c 
                               12 
                               t 
                             
                             + 
                             
                               c 
                               21 
                               t 
                             
                           
                           ) 
                         
                       
                        
                       
                         ( 
                         
                           1 
                           - 
                           
                             H 
                              
                             
                               ( 
                               
                                 m 
                                 1 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                     + 
                     
                       
                         T 
                          
                         
                           ( 
                           
                             
                               c 
                               22 
                               t 
                             
                             + 
                             
                               c 
                               31 
                               t 
                             
                           
                           ) 
                         
                       
                        
                       
                         ( 
                         
                           1 
                           - 
                           
                             H 
                              
                             
                               ( 
                               
                                 
                                   m 
                                   1 
                                 
                                 + 
                                 
                                   m 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                     + 
                     
                       
                         T 
                          
                         
                           ( 
                           
                             
                               c 
                               32 
                               t 
                             
                             + 
                             
                               c 
                               41 
                               t 
                             
                             + 
                             
                               c 
                               42 
                               t 
                             
                           
                           ) 
                         
                       
                        
                       
                         ( 
                         
                           1 
                           - 
                           
                             H 
                              
                             
                               ( 
                               
                                 
                                   m 
                                   1 
                                 
                                 + 
                                 
                                   m 
                                   2 
                                 
                                 + 
                                 
                                   m 
                                   3 
                                 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0041]    The goal is to minimize network cost subject to constraints on cache memory size: 
         [0000]        Ntwk Cost( m   1   ,m   2   ,m   3 )→min  (2) 
         [0000]      Subject to 0≦m i ≦M i , i=1, 2, 3  (3) 
         [0042]    Analytical Solution—Methodology 
         [0043]    Network cost (1) is a function of three variables {right arrow over (m)}=(m 1 , m 2 ,m 3 ) defined on polyhedral (3). Note, that this function is strictly convex (because hit rate function H is strictly concave according to the assumptions). The solution, uses the following result from calculus about minimum of a convex function: 
         [0044]    Theorem 
         [0045]    Let function f(x) be defined on an interval [a,b], convex, and has derivative f″(x). Then one of the following should take place ( FIG. 4 ):
       (a) f(x) attains its minimum 41 at x=a, i.e. f″(a)≧0;   (b) f(x) attains its minimum 42 at x=x min , a&lt;x min &lt;b, i.e. f″(x min )=0;   (c) f(x) attains its minimum 43 at x=b, i.e. f″(b)≦0.       
 
         [0049]    Consider partial derivatives of the network cost function (1): 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       ∂ 
                       
                         ( 
                         NtwkCost 
                         ) 
                       
                     
                     
                       ∂ 
                       
                         m 
                         1 
                       
                     
                   
                   = 
                   
                     
                       
                         N 
                         1 
                       
                        
                       
                         c 
                         1 
                         m 
                       
                     
                     - 
                     
                       
                         Ts 
                         1 
                       
                        
                       
                         
                           H 
                           ′ 
                         
                          
                         
                           ( 
                           
                             m 
                             1 
                           
                           ) 
                         
                       
                     
                     - 
                     
                       
                         Ts 
                         2 
                       
                        
                       
                         
                           H 
                           ′ 
                         
                          
                         
                           ( 
                           
                             
                               m 
                               1 
                             
                             + 
                             
                               m 
                               2 
                             
                           
                           ) 
                         
                       
                     
                     - 
                     
                       
                         Ts 
                         3 
                       
                        
                       
                         
                           H 
                           ′ 
                         
                          
                         
                           ( 
                           
                             
                               m 
                               1 
                             
                             + 
                             
                               m 
                               2 
                             
                             + 
                             
                               m 
                               3 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       ∂ 
                       
                         ( 
                         NtwkCost 
                         ) 
                       
                     
                     
                       ∂ 
                       
                         m 
                         2 
                       
                     
                   
                   = 
                   
                     
                       
                         N 
                         2 
                       
                        
                       
                         c 
                         2 
                         m 
                       
                     
                     - 
                     
                       
                         Ts 
                         2 
                       
                        
                       
                         
                           H 
                           ′ 
                         
                          
                         
                           ( 
                           
                             
                               m 
                               1 
                             
                             + 
                             
                               m 
                               2 
                             
                           
                           ) 
                         
                       
                     
                     - 
                     
                       
                         Ts 
                         3 
                       
                        
                       
                         
                           H 
                           ′ 
                         
                          
                         
                           ( 
                           
                             
                               m 
                               1 
                             
                             + 
                             
                               m 
                               2 
                             
                             + 
                             
                               m 
                               3 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         ∂ 
                         
                           ( 
                           NtwkCost 
                           ) 
                         
                       
                       
                         ∂ 
                         
                           m 
                           3 
                         
                       
                     
                     = 
                     
                       
                         
                           N 
                           3 
                         
                          
                         
                           c 
                           3 
                           m 
                         
                       
                       - 
                       
                         
                           Ts 
                           3 
                         
                          
                         
                           
                             H 
                             ′ 
                           
                            
                           
                             ( 
                             
                               
                                 m 
                                 1 
                               
                               + 
                               
                                 m 
                                 2 
                               
                               + 
                               
                                 m 
                                 3 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0050]    Where: 
         [0000]    
       
      
       s 
       1 
       =c 
       12 
       t 
       +c 
       21 
       t  
      
     
         [0000]    
       
      
       s 
       2 
       =c 
       22 
       t 
       +c 
       31 
       t  
      
     
         [0000]        s   3   =c   32   t   +c   41   t   +c   42   t   (7) 
         [0051]    Let {right arrow over (m)} o =(m 1   o , m 2   o , m 3   o ) denote an optimal solution of the problem. The process of network cost minimization for this problem has two phases—forward and backward, and each phase includes three steps. On each step, partial derivatives of network cost (1) are considered at {right arrow over (m)} o  by one variable and fixing two other variables. 
         [0052]    Forward phase includes the following three steps: 
         [0053]    1 st  step: minimize network cost (1) by m 3  for m 1 =m 1   o , m 2 =m 2   o  using (6). 
         [0054]    2 nd  step: minimize network cost (1) by m 2  for m 1 =m 1   o , m 3 =m 3   o  using (5) and results of optimization on the previous step. 
         [0055]    3 rd  step: minimize network cost (1) by m 1  for m 2 =m 2   o , m 3 =m 3   o  using (4) and results of optimization on the previous step. 
         [0056]    There are three alternatives to be considered on every step of the optimization process: zero cache size (no caching), some optimal non-zero cache size (moderate caching), or maximum cache size (maximum caching). 
         [0057]    Overall, the optimization process may be presented as a movement along the logical 3-ary tree  50  with 3 3 =27 leaves, as shown in  FIG. 5 . The forward phase moves down to the leaves of the tree. The backward phase moves up from the leaves of the tree. 
         [0058]    Description of Analytical Solution 
         [0059]    Forward Phase 
         [0060]    On the 1 st  step, network cost (1) is minimized by m 3  for m 1 =m 1   o , m 2 =m 2   o  using (6). Applying the theorem described above, there are the following three alternatives: 
         [0000]    
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 1 
                  
                 
                   : 
                 
                  
                 
                     
                 
                  
                 
                   m 
                   3 
                   o 
                 
               
               = 
               0 
             
             , 
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       3 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≥ 
               0 
             
             , 
             
               
 
             
              
             
               
                 
                   or 
                    
                   
                       
                   
                    
                   
                     Ts 
                     3 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         
                           m 
                           1 
                           o 
                         
                         + 
                         
                           m 
                           2 
                           o 
                         
                       
                       ) 
                     
                   
                 
                 ≤ 
                 
                   
                     N 
                     3 
                   
                    
                   
                     c 
                     3 
                     m 
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 2 
                  
                 
                   : 
                 
                  
                 
                     
                 
                  
                 0 
               
               &lt; 
               
                 m 
                 3 
                 o 
               
               &lt; 
               
                 M 
                 3 
               
             
             , 
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       3 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               = 
               0 
             
             , 
             
               
 
             
              
             
               
                 
                   or 
                    
                   
                       
                   
                    
                   
                     Ts 
                     3 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         
                           m 
                           1 
                           o 
                         
                         + 
                         
                           m 
                           2 
                           o 
                         
                         + 
                         
                           m 
                           3 
                           o 
                         
                       
                       ) 
                     
                   
                 
                 = 
                 
                   
                     N 
                     3 
                   
                    
                   
                     c 
                     3 
                     m 
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 3 
                  
                 
                   : 
                 
                  
                 
                     
                 
                  
                 
                   m 
                   3 
                   o 
                 
               
               = 
               
                 M 
                 3 
               
             
             , 
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       3 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≤ 
               0 
             
             , 
             
               
 
             
              
             
               
                 or 
                  
                 
                     
                 
                  
                 
                   Ts 
                   3 
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       
                         m 
                         1 
                         o 
                       
                       + 
                       
                         m 
                         2 
                         o 
                       
                       + 
                       
                         M 
                         3 
                       
                     
                     ) 
                   
                 
               
               ≥ 
               
                 
                   N 
                   3 
                 
                  
                 
                   c 
                   . 
                 
               
             
           
         
       
     
         [0061]    On the 2 nd  step, for every case of the 1 st  step, three alternatives, m 2   o =0, 0&lt;m 2   o &lt;M 2 , and m 2   o =M 2  are considered, so there are a total of 9 cases on this step: 1.1, 1.2, 1.3, 2.1, 2.2, 2.3, 3.1, 3.2, and 3.3. 
         [0062]    Finally, on the 3 rd  step, for every of the 9 cases of the 2 nd  step, three alternatives, m 1   o =0, 0&lt;m 1   0 &lt;M 1 , and m 1   o =M 1 , are considered, so there are a total of 27 cases on this step. By the end of this step, 9 values for m 1   o , an optimal value for m 1 , can be identified by analyzing 9 sets of cases: 1.1.x, 1.2.x, 1.3.x, 2.1.x, 2.2.x, 2.3.x, 3.1.x, 3.2.x and 3.3.x, where x=1, 2 and 3. For every of those alternative cases, m 1   o =0, if H′( 0 )≦P, m 1   o  is a solution of equation H′(m 1   o )=P, or m 1   o =M 1 , if H′(M 1 )≧P, where P depends on input parameters. These solutions will be termed “seeds” herein. 
         [0063]    Here a detailed description of the 2 nd  and 3 rd  steps of the forward phase is provided. 
         [0064]    On the 2 nd  step, the network cost (1) is minimized by m 2  for m 1 =m 1   o , m 3 =m 3   o  using (5). 
         [0065]    For the Case 1, (5) becomes: 
         [0000]    
       
         
           
             
               
                 
                   ∂ 
                   
                     ( 
                     NtwkCost 
                     ) 
                   
                 
                 
                   ∂ 
                   
                     m 
                     2 
                   
                 
               
                
               
                 ( 
                 
                   
                     m 
                     → 
                   
                   o 
                 
                 ) 
               
             
             = 
             
               
                 
                   N 
                   2 
                 
                  
                 
                   c 
                   2 
                   m 
                 
               
               - 
               
                 
                   Ts 
                   2 
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       
                         m 
                         1 
                         o 
                       
                       + 
                       
                         m 
                         2 
                         o 
                       
                     
                     ) 
                   
                 
               
               - 
               
                 
                   Ts 
                   3 
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       
                         m 
                         1 
                         o 
                       
                       + 
                       
                         m 
                         2 
                         o 
                       
                     
                     ) 
                   
                 
               
             
           
         
       
     
         [0066]    Applying the theorem, there are the following three alternatives: 
         [0000]    
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 1.1 
                  
                 
                   : 
                 
                  
                 
                     
                 
                  
                 
                   m 
                   2 
                   o 
                 
               
               = 
               0 
             
             , 
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       2 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≥ 
               0 
             
             , 
             
               
 
             
              
             
               
                 
                   or 
                    
                   
                       
                   
                    
                   
                     T 
                      
                     
                       ( 
                       
                         
                           s 
                           2 
                         
                         + 
                         
                           s 
                           3 
                         
                       
                       ) 
                     
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         m 
                         1 
                         o 
                       
                       ) 
                     
                   
                 
                 ≤ 
                 
                   
                     N 
                     2 
                   
                    
                   
                     c 
                     2 
                     m 
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 1.2 
                  
                 
                   : 
                 
                  
                 
                     
                 
                  
                 0 
               
               &lt; 
               
                 m 
                 2 
                 o 
               
               &lt; 
               
                 M 
                 2 
               
             
             , 
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       2 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               = 
               0 
             
             , 
             
               
 
             
              
             
               
                 
                   or 
                    
                   
                       
                   
                    
                   
                     T 
                      
                     
                       ( 
                       
                         
                           s 
                           2 
                         
                         + 
                         
                           s 
                           3 
                         
                       
                       ) 
                     
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         
                           m 
                           1 
                           o 
                         
                         + 
                         
                           m 
                           2 
                           o 
                         
                       
                       ) 
                     
                   
                 
                 = 
                 
                   
                     N 
                     2 
                   
                    
                   
                     c 
                     2 
                     m 
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 1.3 
                  
                 
                   : 
                 
                  
                 
                     
                 
                  
                 
                   m 
                   2 
                   o 
                 
               
               = 
               
                 M 
                 2 
               
             
             , 
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       2 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≤ 
               0 
             
             , 
             
               
 
             
              
             
               
                 or 
                  
                 
                     
                 
                  
                 
                   T 
                    
                   
                     ( 
                     
                       
                         s 
                         2 
                       
                       + 
                       
                         s 
                         3 
                       
                     
                     ) 
                   
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       
                         m 
                         1 
                         o 
                       
                       + 
                       
                         M 
                         2 
                       
                     
                     ) 
                   
                 
               
               ≥ 
               
                 
                   N 
                   2 
                 
                  
                 
                   
                     c 
                     2 
                     m 
                   
                   . 
                 
               
             
           
         
       
     
         [0067]    For the Case 2, (5) becomes: 
         [0000]    
       
         
           
             
               
                 
                   ∂ 
                   
                     ( 
                     NtwkCost 
                     ) 
                   
                 
                 
                   ∂ 
                   
                     m 
                     2 
                   
                 
               
                
               
                 ( 
                 
                   
                     m 
                     → 
                   
                   o 
                 
                 ) 
               
             
             = 
             
               
                 ( 
                 
                   
                     
                       N 
                       2 
                     
                      
                     
                       c 
                       2 
                       m 
                     
                   
                   - 
                   
                     
                       N 
                       3 
                     
                      
                     
                       c 
                       3 
                       m 
                     
                   
                 
                 ) 
               
               - 
               
                 
                   Ts 
                   2 
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       
                         m 
                         1 
                         o 
                       
                       + 
                       
                         m 
                         2 
                         o 
                       
                     
                     ) 
                   
                 
               
             
           
         
       
     
         [0068]    Applying the theorem, there are the following three alternatives: 
         [0000]    
       
         
           
             
               
                 
                   Case 
                    
                   
                       
                   
                    
                   2.1 
                    
                   
                     : 
                   
                    
                   
                       
                   
                    
                   
                     m 
                     2 
                     o 
                   
                 
                 = 
                 0 
               
               , 
               
                   
               
                
               
                 
                   and 
                    
                   
                       
                   
                    
                   
                     
                       ∂ 
                       
                         ( 
                         NtwkCost 
                         ) 
                       
                     
                     
                       ∂ 
                       
                         m 
                         2 
                       
                     
                   
                    
                   
                     ( 
                     
                       
                         m 
                         → 
                       
                       o 
                     
                     ) 
                   
                 
                 ≥ 
                 0 
               
               , 
               
                   
               
                
               
                 
 
               
                
               
                 
                   
                     or 
                      
                     
                         
                     
                      
                     
                       Ts 
                       2 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           m 
                           1 
                           o 
                         
                         ) 
                       
                     
                   
                   ≤ 
                   
                     
                       
                         N 
                         2 
                       
                        
                       
                         c 
                         2 
                         m 
                       
                     
                     - 
                     
                       
                         N 
                         3 
                       
                        
                       
                         c 
                         3 
                         m 
                       
                     
                   
                 
                 ; 
               
             
              
             
               
 
             
              
             
               
                 
                   Case 
                    
                   
                       
                   
                    
                   2.2 
                    
                   
                       
                   
                    
                   
                     : 
                   
                    
                   
                       
                   
                    
                   0 
                 
                 &lt; 
                 
                   m 
                   2 
                   o 
                 
                 &lt; 
                 
                   M 
                   2 
                 
               
               , 
               
                   
               
                
               
                 
                   and 
                    
                   
                       
                   
                    
                   
                     
                       ∂ 
                       
                         ( 
                         NtwkCost 
                         ) 
                       
                     
                     
                       ∂ 
                       
                         m 
                         2 
                       
                     
                   
                    
                   
                     ( 
                     
                       
                         m 
                         → 
                       
                       o 
                     
                     ) 
                   
                 
                 ≥ 
                 0 
               
               , 
               
                 
 
               
                
               
                 
                   
                     or 
                      
                     
                         
                     
                      
                     
                       Ts 
                       2 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           
                             m 
                             1 
                             o 
                           
                           + 
                           
                             m 
                             2 
                             o 
                           
                         
                         ) 
                       
                     
                   
                   = 
                   
                     
                       
                         N 
                         2 
                       
                        
                       
                         c 
                         2 
                         m 
                       
                     
                     - 
                     
                       
                         N 
                         3 
                       
                        
                       
                         c 
                         3 
                         m 
                       
                     
                   
                 
                 ; 
               
             
              
             
               
 
             
              
             
               
                 
                   Case 
                    
                   
                       
                   
                    
                   2.3 
                    
                   
                     : 
                   
                    
                   
                       
                   
                    
                   
                     m 
                     2 
                     o 
                   
                 
                 = 
                 
                   M 
                   2 
                 
               
               , 
               
                   
               
                
               
                 
                   and 
                    
                   
                       
                   
                    
                   
                     
                       ∂ 
                       
                         ( 
                         NtwkCost 
                         ) 
                       
                     
                     
                       ∂ 
                       
                         m 
                         2 
                       
                     
                   
                    
                   
                     ( 
                     
                       
                         m 
                         → 
                       
                       o 
                     
                     ) 
                   
                 
                 ≤ 
                 0 
               
               , 
               
                   
               
                
               
                 
 
               
                
               
                 
                   or 
                    
                   
                       
                   
                    
                   
                     Ts 
                     2 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         
                           m 
                           1 
                           o 
                         
                         + 
                         
                           M 
                           2 
                         
                       
                       ) 
                     
                   
                 
                 ≥ 
                 
                   
                     
                       N 
                       2 
                     
                      
                     
                       c 
                       2 
                       m 
                     
                   
                   - 
                   
                     
                       N 
                       3 
                     
                      
                     
                       
                         c 
                         3 
                         m 
                       
                       . 
                     
                   
                 
               
             
           
         
       
     
         [0069]    For the Case 3, (5) becomes: 
         [0000]    
       
         
           
             
               
                 
                   ∂ 
                   
                     ( 
                     NtwkCost 
                     ) 
                   
                 
                 
                   ∂ 
                   
                     m 
                     2 
                   
                 
               
                
               
                 ( 
                 
                   
                     m 
                     → 
                   
                   o 
                 
                 ) 
               
             
             = 
             
               
                 
                   N 
                   2 
                 
                  
                 
                   c 
                   2 
                   m 
                 
               
               - 
               
                 
                   Ts 
                   2 
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       
                         m 
                         1 
                         o 
                       
                       + 
                       
                         m 
                         2 
                         o 
                       
                     
                     ) 
                   
                 
               
               - 
               
                 
                   Ts 
                   3 
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       
                         m 
                         1 
                         o 
                       
                       + 
                       
                         m 
                         2 
                         o 
                       
                       + 
                       
                         M 
                         3 
                       
                     
                     ) 
                   
                 
               
             
           
         
       
     
         [0070]    Applying the theorem, there are the following three alternatives: 
         [0000]    
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 3.1 
                  
                 
                   : 
                 
                  
                 
                     
                 
                  
                 
                   m 
                   2 
                   o 
                 
               
               = 
               0 
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       2 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≥ 
               0 
             
             , 
             
               
 
             
              
             
               
                 
                   
                     or 
                      
                     
                         
                     
                      
                     
                       Ts 
                       2 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           m 
                           1 
                           o 
                         
                         ) 
                       
                     
                   
                   + 
                   
                     
                       Ts 
                       3 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           
                             m 
                             1 
                             o 
                           
                           + 
                           
                             M 
                             3 
                           
                         
                         ) 
                       
                     
                   
                 
                 ≤ 
                 
                   
                     N 
                     2 
                   
                    
                   
                     c 
                     2 
                     m 
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 3.2 
                  
                 
                     
                 
                  
                 
                   : 
                 
                  
                 
                     
                 
                  
                 0 
               
               &lt; 
               
                 m 
                 2 
                 o 
               
               &lt; 
               
                 M 
                 2 
               
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       2 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               = 
               0 
             
             , 
             
               
 
             
              
             
               
                 
                   
                     or 
                      
                     
                         
                     
                      
                     
                       Ts 
                       2 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           
                             m 
                             1 
                             o 
                           
                           + 
                           
                             m 
                             2 
                             o 
                           
                         
                         ) 
                       
                     
                   
                   + 
                   
                     
                       Ts 
                       3 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           
                             m 
                             1 
                             o 
                           
                           + 
                           
                             m 
                             2 
                             o 
                           
                           + 
                           
                             M 
                             3 
                           
                         
                         ) 
                       
                     
                   
                 
                 = 
                 
                   
                     N 
                     2 
                   
                    
                   
                     c 
                     2 
                     m 
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 3.3 
                  
                 
                     
                 
                  
                 
                   : 
                 
                  
                 
                     
                 
                  
                 
                   m 
                   2 
                   o 
                 
               
               = 
               
                 M 
                 2 
               
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       2 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≤ 
               0 
             
             , 
             
               
 
             
              
             
               
                 
                   or 
                    
                   
                       
                   
                    
                   
                     Ts 
                     2 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         
                           m 
                           1 
                           o 
                         
                         + 
                         
                           M 
                           2 
                         
                       
                       ) 
                     
                   
                 
                 + 
                 
                   
                     Ts 
                     3 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         
                           m 
                           1 
                           o 
                         
                         + 
                         
                           M 
                           2 
                         
                         + 
                         
                           M 
                           3 
                         
                       
                       ) 
                     
                   
                 
               
               ≥ 
               
                 
                   N 
                   2 
                 
                  
                 
                   
                     c 
                     2 
                     m 
                   
                   . 
                 
               
             
           
         
       
     
         [0071]    Finally, network cost (1) is minimized by m 1  for m 2 =m 2   o , m 3 =m 3   o  using eq. 4. Here the following 9 cases from the 2 nd  level of logical tree ( FIG. 5 ) are considered. 
         [0072]    For the Case 1.1, eq. 4 becomes: 
         [0000]    
       
         
           
             
               
                 
                   ∂ 
                   
                     ( 
                     NtwkCost 
                     ) 
                   
                 
                 
                   ∂ 
                   
                     m 
                     1 
                   
                 
               
                
               
                 ( 
                 
                   
                     m 
                     → 
                   
                   o 
                 
                 ) 
               
             
             = 
             
               
                 
                   N 
                   1 
                 
                  
                 
                   c 
                   1 
                   m 
                 
               
               - 
               
                 
                   T 
                    
                   
                     ( 
                     
                       
                         s 
                         1 
                       
                       + 
                       
                         s 
                         2 
                       
                       + 
                       
                         s 
                         3 
                       
                     
                     ) 
                   
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       m 
                       1 
                       o 
                     
                     ) 
                   
                 
               
             
           
         
       
       
         
           
             
               
                 
                   Case 
                    
                   
                       
                   
                    
                   1.1 
                    
                   
                     .1 
                     . 
                   
                 
                  
                 
                     
                 
                  
                 
                   m 
                   1 
                   o 
                 
               
               = 
               0 
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                     
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≥ 
               0 
             
             , 
             
                 
             
              
             
                
             
              
             
               
                 
                   or 
                    
                   
                       
                   
                    
                   
                     T 
                      
                     
                       ( 
                       
                         
                           s 
                           1 
                         
                         + 
                         
                           s 
                           2 
                         
                         + 
                         
                           s 
                           3 
                         
                       
                       ) 
                     
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       0 
                       ) 
                     
                   
                 
                 ≤ 
                 
                   
                     N 
                     1 
                   
                    
                   
                     c 
                     1 
                     m 
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 1.1 
                  
                 
                   .2 
                   . 
                   
                       
                   
                    
                   0 
                 
               
               &lt; 
               
                 m 
                 1 
                 o 
               
               &lt; 
               
                 M 
                 1 
               
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               = 
               0 
             
             , 
             
                 
             
              
             
                
             
              
             
               
                 
                   or 
                    
                   
                       
                   
                    
                   
                     T 
                      
                     
                       ( 
                       
                         
                           s 
                           1 
                         
                         + 
                         
                           s 
                           2 
                         
                         + 
                         
                           s 
                           3 
                         
                       
                       ) 
                     
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         m 
                         1 
                         o 
                       
                       ) 
                     
                   
                 
                 = 
                 
                   
                     N 
                     1 
                   
                    
                   
                     c 
                     1 
                     m 
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 1.1 
                  
                 .3 
                  
                 
                     
                 
                  
                 
                   m 
                   1 
                   o 
                 
               
               = 
               
                 M 
                 1 
               
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≤ 
               0 
             
             , 
             
                 
             
              
             
                
             
              
             
               
                 or 
                  
                 
                     
                 
                  
                 
                   T 
                    
                   
                     ( 
                     
                       
                         s 
                         1 
                       
                       + 
                       
                         s 
                         2 
                       
                       + 
                       
                         s 
                         3 
                       
                     
                     ) 
                   
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       M 
                       1 
                     
                     ) 
                   
                 
               
               ≥ 
               
                 
                   N 
                   1 
                 
                  
                 
                   c 
                   1 
                   m 
                 
               
             
           
         
       
     
         [0073]    For the Case 1.2, eq. 4 becomes: 
         [0000]    
       
         
           
             
               
                 
                   ∂ 
                   
                     ( 
                     NtwkCost 
                     ) 
                   
                 
                 
                   ∂ 
                   
                     m 
                     1 
                   
                 
               
                
               
                 ( 
                 
                   
                     m 
                     → 
                   
                   o 
                 
                 ) 
               
             
             = 
             
               
                 ( 
                 
                   
                     
                       N 
                       1 
                     
                      
                     
                       c 
                       1 
                       m 
                     
                   
                   - 
                   
                     
                       N 
                       2 
                     
                      
                     
                       c 
                       2 
                       m 
                     
                   
                 
                 ) 
               
               - 
               
                 
                   Ts 
                   1 
                 
                  
                 
                   H 
                   ′ 
                 
                  
                 
                   ( 
                   
                     m 
                     1 
                     o 
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 1.2 
                  
                 
                   .1 
                   . 
                   
                       
                   
                    
                   
                     m 
                     1 
                     o 
                   
                 
               
               = 
               0 
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≥ 
               0 
             
             , 
             
                 
             
              
             
                
             
              
             
               
                 
                   or 
                    
                   
                       
                   
                    
                   
                     Ts 
                     1 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       0 
                       ) 
                     
                   
                 
                 ≤ 
                 
                   
                     
                       N 
                       1 
                     
                      
                     
                       c 
                       1 
                       m 
                     
                   
                   - 
                   
                     
                       N 
                       2 
                     
                      
                     
                       c 
                       2 
                       m 
                     
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 
                   Case 
                    
                   
                       
                   
                    
                   1.2 
                    
                   
                     .2 
                     . 
                     
                         
                     
                      
                     0 
                   
                 
                 &lt; 
                 
                   m 
                   1 
                   o 
                 
                 &lt; 
                 
                   M 
                   1 
                 
               
               , 
               
                   
               
                
               
                 
                   and 
                    
                   
                       
                   
                    
                   
                     
                       ∂ 
                       
                         ( 
                         NtwkCost 
                         ) 
                       
                     
                     
                       ∂ 
                       
                         m 
                         1 
                       
                     
                   
                    
                   
                     ( 
                     
                       
                         m 
                         → 
                       
                       o 
                     
                     ) 
                   
                 
                 = 
               
               , 
               0 
             
              
             
                 
             
           
         
       
       
         
           
             
               
                 or 
                  
                 
                     
                 
                  
                 
                   Ts 
                   1 
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       m 
                       1 
                       o 
                     
                     ) 
                   
                 
               
               = 
               
                 
                   
                     N 
                     1 
                   
                    
                   
                     c 
                     1 
                     m 
                   
                 
                 - 
                 
                   
                     N 
                     2 
                   
                    
                   
                     c 
                     2 
                     m 
                   
                 
               
             
             ; 
           
         
       
       
         
           
             
               
                 
                   
                     Case 
                      
                     
                         
                     
                      
                     1.2 
                      
                     
                       .3 
                       . 
                     
                   
                    
                   
                       
                   
                    
                   
                     m 
                     1 
                     o 
                   
                 
                 = 
                 
                   M 
                   1 
                 
               
               , 
               
                   
               
                
               
                 
                   and 
                    
                   
                       
                   
                    
                   
                     
                       ∂ 
                       
                         ( 
                         NtwkCost 
                         ) 
                       
                     
                     
                       ∂ 
                       
                         m 
                         1 
                       
                     
                   
                    
                   
                     ( 
                     
                       
                         m 
                         → 
                       
                       o 
                     
                     ) 
                   
                 
                 ≤ 
                 0 
               
               , 
               
                   
               
                
               
                 
 
               
                
               
                 
                   or 
                    
                   
                       
                   
                    
                   
                     Ts 
                     1 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         M 
                         1 
                       
                       ) 
                     
                   
                 
                 ≥ 
                 
                   
                     
                       N 
                       1 
                     
                      
                     
                       c 
                       1 
                       m 
                     
                   
                   - 
                   
                     
                       N 
                       2 
                     
                      
                     
                       
                         c 
                         2 
                         m 
                       
                       . 
                     
                   
                 
               
             
              
             
                 
             
           
         
       
     
         [0074]    For the Case 1.3, eq. 4 becomes: 
         [0000]    
       
         
           
             
               
                 
                   ∂ 
                   
                     ( 
                     NtwkCost 
                     ) 
                   
                 
                 
                   ∂ 
                   
                     m 
                     1 
                   
                 
               
                
               
                 ( 
                 
                   
                     m 
                     → 
                   
                   o 
                 
                 ) 
               
             
             = 
             
               
                 
                   N 
                   1 
                 
                  
                 
                   c 
                   1 
                   m 
                 
               
               - 
               
                 
                   Ts 
                   1 
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       m 
                       1 
                       o 
                     
                     ) 
                   
                 
               
               - 
               
                 
                   Ts 
                   2 
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       
                         m 
                         1 
                         o 
                       
                       + 
                       
                         M 
                         2 
                       
                     
                     ) 
                   
                 
               
               - 
               
                 
                   Ts 
                   3 
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       
                         m 
                         1 
                         o 
                       
                       + 
                       
                         M 
                         2 
                       
                     
                     ) 
                   
                 
               
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 1.3 
                  
                 
                   .1 
                   . 
                   
                       
                   
                    
                   
                     m 
                     1 
                     o 
                   
                 
               
               = 
               0 
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≥ 
               0 
             
             , 
             
                 
             
              
             
                
             
              
             
               
                 
                   
                     or 
                      
                     
                         
                     
                      
                     
                       Ts 
                       1 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         0 
                         ) 
                       
                     
                   
                   + 
                   
                     
                       Ts 
                       2 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           M 
                           2 
                         
                         ) 
                       
                     
                   
                   + 
                   
                     
                       Ts 
                       3 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           M 
                           2 
                         
                         ) 
                       
                     
                   
                 
                 ≤ 
                 
                   
                     N 
                     1 
                   
                    
                   
                     c 
                     1 
                     m 
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 1.3 
                  
                 
                   .2 
                   . 
                   
                       
                   
                    
                   0 
                 
               
               &lt; 
               
                 m 
                 1 
                 o 
               
               &lt; 
               
                 M 
                 1 
               
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               = 
               0 
             
             , 
             
                 
             
              
             
                
             
              
             
               
                 
                   or 
                    
                   
                       
                   
                    
                   
                     Ts 
                     1 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         m 
                         1 
                         o 
                       
                       ) 
                     
                   
                 
                 + 
                 
                   
                     Ts 
                     2 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         
                           m 
                           1 
                           o 
                         
                         + 
                         
                           M 
                           2 
                         
                       
                       ) 
                     
                   
                 
                 + 
                 
                   
                     Ts 
                     3 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         
                           m 
                           1 
                           o 
                         
                         + 
                         
                           M 
                           2 
                         
                       
                       ) 
                     
                   
                 
               
               = 
               
                 
                   N 
                   1 
                 
                  
                 
                   c 
                   1 
                   m 
                 
               
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 1.3 
                  
                 
                   .3 
                   . 
                   
                       
                   
                    
                   
                     m 
                     1 
                     o 
                   
                 
               
               = 
               
                 M 
                 1 
               
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≤ 
               0 
             
             , 
             
                 
             
              
             
                
             
              
             
               
                 
                   or 
                    
                   
                       
                   
                    
                   
                     Ts 
                     1 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         M 
                         1 
                       
                       ) 
                     
                   
                 
                 + 
                 
                   
                     Ts 
                     2 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         
                           M 
                           1 
                         
                         + 
                         
                           M 
                           2 
                         
                       
                       ) 
                     
                   
                 
                 + 
                 
                   
                     Ts 
                     3 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         
                           M 
                           1 
                         
                         + 
                         
                           M 
                           2 
                         
                       
                       ) 
                     
                   
                 
               
               ≥ 
               
                 
                   N 
                   1 
                 
                  
                 
                   c 
                   1 
                   m 
                 
               
             
           
         
       
     
         [0075]    For the Case 2.1, eq. 4 becomes: 
         [0000]    
       
         
           
             
               
                 
                   ∂ 
                   
                     ( 
                     NtwkCost 
                     ) 
                   
                 
                 
                   ∂ 
                   
                     m 
                     1 
                   
                 
               
                
               
                 ( 
                 
                   
                     m 
                     → 
                   
                   o 
                 
                 ) 
               
             
             = 
             
               
                 ( 
                 
                   
                     
                       N 
                       1 
                     
                      
                     
                       c 
                       1 
                       m 
                     
                   
                   - 
                   
                     
                       N 
                       3 
                     
                      
                     
                       c 
                       3 
                       m 
                     
                   
                 
                 ) 
               
               - 
               
                 
                   T 
                    
                   
                     ( 
                     
                       
                         s 
                         1 
                       
                       + 
                       
                         s 
                         2 
                       
                     
                     ) 
                   
                 
                  
                 
                   H 
                   ′ 
                 
                  
                 
                   ( 
                   
                     m 
                     1 
                     o 
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 2.1 
                  
                 
                   .1 
                   . 
                   
                       
                   
                    
                   
                     m 
                     1 
                     o 
                   
                 
               
               = 
               0 
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≥ 
               0 
             
             , 
             
                 
             
              
             
                
             
              
             
               
                 
                   or 
                    
                   
                       
                   
                    
                   
                     T 
                      
                     
                       ( 
                       
                         
                           s 
                           1 
                         
                         + 
                         
                           s 
                           2 
                         
                       
                       ) 
                     
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       0 
                       ) 
                     
                   
                 
                 ≤ 
                 
                   
                     
                       N 
                       1 
                     
                      
                     
                       c 
                       1 
                       m 
                     
                   
                   - 
                   
                     
                       N 
                       3 
                     
                      
                     
                       c 
                       3 
                       m 
                     
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 
                   Case 
                    
                   
                       
                   
                    
                   2.1 
                    
                   
                     .2 
                     . 
                     
                         
                     
                      
                     0 
                   
                 
                 &lt; 
                 
                   m 
                   1 
                   o 
                 
                 &lt; 
                 
                   M 
                   1 
                 
               
               , 
               
                   
               
                
               
                 
                   and 
                    
                   
                       
                   
                    
                   
                     
                       ∂ 
                       
                         ( 
                         NtwkCost 
                         ) 
                       
                     
                     
                       ∂ 
                       
                         m 
                         1 
                       
                     
                   
                    
                   
                     ( 
                     
                       
                         m 
                         → 
                       
                       o 
                     
                     ) 
                   
                 
                 = 
                 0 
               
             
              
             
                 
             
           
         
       
       
         
           
             
               
                 or 
                  
                 
                     
                 
                  
                 
                   T 
                    
                   
                     ( 
                     
                       
                         s 
                         1 
                       
                       + 
                       
                         s 
                         2 
                       
                     
                     ) 
                   
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       m 
                       1 
                       o 
                     
                     ) 
                   
                 
               
               = 
               
                 
                   
                     N 
                     1 
                   
                    
                   
                     c 
                     1 
                     m 
                   
                 
                 - 
                 
                   
                     N 
                     3 
                   
                    
                   
                     c 
                     3 
                     m 
                   
                 
               
             
             ; 
           
         
       
       
         
           
             
               
                 
                   Case 
                    
                   
                       
                   
                    
                   2.1 
                    
                   
                     .3 
                     . 
                     
                         
                     
                      
                     
                       m 
                       1 
                       o 
                     
                   
                 
                 = 
                 
                   M 
                   1 
                 
               
               , 
               
                   
               
                
               
                 
                   and 
                    
                   
                       
                   
                    
                   
                     
                       ∂ 
                       
                         ( 
                         NtwkCost 
                         ) 
                       
                     
                     
                       ∂ 
                       
                         m 
                         1 
                       
                     
                   
                    
                   
                     ( 
                     
                       
                         m 
                         → 
                       
                       o 
                     
                     ) 
                   
                 
                 ≤ 
                 0 
               
               , 
               
                   
               
                
               
                  
               
                
               
                 
                   or 
                    
                   
                       
                   
                    
                   
                     T 
                      
                     
                       ( 
                       
                         
                           s 
                           1 
                         
                         + 
                         
                           s 
                           2 
                         
                       
                       ) 
                     
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         M 
                         1 
                       
                       ) 
                     
                   
                 
                 ≥ 
                 
                   
                     
                       N 
                       1 
                     
                      
                     
                       c 
                       1 
                       m 
                     
                   
                   - 
                   
                     
                       N 
                       3 
                     
                      
                     
                       
                         c 
                         3 
                         m 
                       
                       . 
                     
                   
                 
               
             
              
             
                 
             
           
         
       
     
         [0076]    For the Case 2.2, eq. 4 becomes: 
         [0000]    
       
         
           
             
               
                 
                   ∂ 
                   
                     ( 
                     NtwkCost 
                     ) 
                   
                 
                 
                   ∂ 
                   
                     m 
                     1 
                   
                 
               
                
               
                 ( 
                 
                   
                     m 
                     → 
                   
                   o 
                 
                 ) 
               
             
             = 
             
               
                 ( 
                 
                   
                     
                       N 
                       1 
                     
                      
                     
                       c 
                       1 
                       m 
                     
                   
                   - 
                   
                     
                       N 
                       2 
                     
                      
                     
                       c 
                       2 
                       m 
                     
                   
                 
                 ) 
               
               - 
               
                 
                   Ts 
                   1 
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       m 
                       1 
                       o 
                     
                     ) 
                   
                 
               
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 2.2 
                  
                 
                   .1 
                   . 
                   
                       
                   
                    
                   
                     m 
                     1 
                     o 
                   
                 
               
               = 
               0 
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≥ 
               0 
             
             , 
             
                 
             
              
             
                
             
              
             
               
                 
                   or 
                    
                   
                       
                   
                    
                   
                     Ts 
                     1 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       0 
                       ) 
                     
                   
                 
                 ≤ 
                 
                   
                     
                       N 
                       1 
                     
                      
                     
                       c 
                       1 
                       m 
                     
                   
                   - 
                   
                     
                       N 
                       2 
                     
                      
                     
                       c 
                       2 
                       m 
                     
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 2.2 
                  
                 
                   .2 
                   . 
                   
                       
                   
                    
                   0 
                 
               
               &lt; 
               
                 m 
                 1 
                 o 
               
               &lt; 
               
                 M 
                 1 
               
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               = 
               0 
             
              
             
                 
             
             , 
             
                 
             
              
             
                
             
              
             
               
                 
                   or 
                    
                   
                       
                   
                    
                   
                     Ts 
                     1 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         m 
                         1 
                         o 
                       
                       ) 
                     
                   
                 
                 = 
                 
                   
                     
                       N 
                       1 
                     
                      
                     
                       c 
                       1 
                       m 
                     
                   
                   - 
                   
                     
                       N 
                       2 
                     
                      
                     
                       c 
                       2 
                       m 
                     
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 2.2 
                  
                 
                   .3 
                   . 
                   
                       
                   
                    
                   
                     m 
                     1 
                     o 
                   
                 
               
               = 
               
                 M 
                 1 
               
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≤ 
               0 
             
             , 
             
                 
             
              
             
                
             
              
             
               
                 or 
                  
                 
                     
                 
                  
                 
                   Ts 
                   1 
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       M 
                       1 
                     
                     ) 
                   
                 
               
               ≥ 
               
                 
                   
                     N 
                     1 
                   
                    
                   
                     c 
                     1 
                     m 
                   
                 
                 - 
                 
                   
                     N 
                     2 
                   
                    
                   
                     
                       c 
                       2 
                       m 
                     
                     . 
                   
                 
               
             
           
         
       
     
         [0077]    For the Case 2.3, eq. 4 becomes: 
         [0000]    
       
         
           
             
               
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                     
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               = 
               
                   
               
                
               
                 
                   ( 
                   
                     
                       
                         N 
                         1 
                       
                        
                       
                           
                       
                        
                       
                         c 
                         1 
                         m 
                       
                     
                     - 
                     
                         
                     
                      
                     
                       
                         N 
                         3 
                       
                        
                       
                           
                       
                        
                       
                         c 
                         3 
                         m 
                       
                     
                   
                   ) 
                 
                 - 
                 
                     
                 
                  
                 
                   
                     Ts 
                     1 
                   
                    
                   
                       
                   
                    
                   
                     
                       H 
                       ′ 
                     
                     ( 
                     
                         
                     
                      
                     
                       m 
                       1 
                       o 
                     
                      
                     
                         
                     
                     ) 
                   
                 
                  
                 
                     
                 
                 - 
                 
                     
                 
                  
                 
                   
                     Ts 
                     2 
                   
                    
                   
                       
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                         
                     
                     ( 
                     
                         
                     
                      
                     
                       
                         m 
                         1 
                         o 
                       
                        
                       
                           
                       
                       + 
                       
                           
                       
                        
                       
                         M 
                         2 
                       
                     
                      
                     
                         
                     
                     ) 
                   
                 
               
             
              
             
                 
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 2.3 
                  
                 
                   .1 
                   . 
                   
                       
                   
                    
                   
                     m 
                     1 
                     o 
                   
                 
               
               = 
               0 
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≥ 
               0 
             
             , 
             
                 
             
              
             
               
 
             
              
             
               
                 
                   
                     or 
                      
                     
                         
                     
                      
                     
                       Ts 
                       1 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         0 
                         ) 
                       
                     
                   
                   + 
                   
                     
                       Ts 
                       2 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           M 
                           2 
                         
                         ) 
                       
                     
                   
                 
                 ≤ 
                 
                   
                     
                       N 
                       1 
                     
                      
                     
                       c 
                       1 
                       m 
                     
                   
                   - 
                   
                     
                       N 
                       3 
                     
                      
                     
                       c 
                       3 
                       m 
                     
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 2.3 
                  
                 
                   .2 
                   . 
                   
                       
                   
                    
                   0 
                 
               
               &lt; 
               
                 m 
                 1 
                 o 
               
               &lt; 
               
                 M 
                 1 
               
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               = 
               0 
             
              
             
                 
             
             , 
             
                 
             
              
             
               
 
             
              
             
               
                 
                   
                     or 
                      
                     
                         
                     
                      
                     
                       Ts 
                       1 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           m 
                           1 
                           o 
                         
                         ) 
                       
                     
                   
                   + 
                   
                     
                       Ts 
                       2 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           
                             m 
                             1 
                             o 
                           
                           + 
                           
                             M 
                             2 
                           
                         
                         ) 
                       
                     
                   
                 
                 = 
                 
                   
                     
                       N 
                       1 
                     
                      
                     
                       c 
                       1 
                       m 
                     
                   
                   - 
                   
                     
                       N 
                       3 
                     
                      
                     
                       c 
                       3 
                       m 
                     
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 2.3 
                  
                 
                   .3 
                   . 
                   
                       
                   
                    
                   
                     m 
                     1 
                     o 
                   
                 
               
               = 
               
                 M 
                 1 
               
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≤ 
               0 
             
             , 
             
                 
             
              
             
               
 
             
              
             
               
                 
                   or 
                    
                   
                       
                   
                    
                   
                     Ts 
                     1 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         M 
                         1 
                       
                       ) 
                     
                   
                 
                 + 
                 
                   
                     Ts 
                     2 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         
                           M 
                           1 
                         
                         + 
                         
                           M 
                           2 
                         
                       
                       ) 
                     
                   
                 
               
               ≥ 
               
                 
                   
                     N 
                     1 
                   
                    
                   
                     c 
                     1 
                     m 
                   
                 
                 - 
                 
                   
                     N 
                     3 
                   
                    
                   
                     
                       c 
                       3 
                       m 
                     
                     . 
                   
                 
               
             
           
         
       
     
         [0078]    For the Case 3.1, eq. 4 becomes: 
         [0000]    
       
         
           
             
               
                 
                   ∂ 
                   
                     ( 
                     NtwkCost 
                     ) 
                   
                 
                 
                   ∂ 
                   
                     m 
                     1 
                   
                 
               
                
               
                 ( 
                 
                   m 
                   
                     → 
                     o 
                   
                 
                 ) 
               
             
             = 
             
               
                 
                   N 
                   1 
                 
                  
                 
                   c 
                   1 
                   m 
                 
               
               - 
               
                 
                   Ts 
                   1 
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       m 
                       1 
                       o 
                     
                     ) 
                   
                 
               
               - 
               
                 
                   Ts 
                   3 
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       
                         m 
                         1 
                         o 
                       
                       + 
                       
                         M 
                         3 
                       
                     
                     ) 
                   
                 
               
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 3.1 
                  
                 
                   .1 
                   . 
                   
                     
 
                   
                    
                   
                     m 
                     1 
                     o 
                   
                 
               
               = 
               0 
             
             , 
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     m 
                     
                       → 
                       o 
                     
                   
                   ) 
                 
               
               ≥ 
               0 
             
             , 
             or 
           
         
       
       
         
           
             
               
                 
                   
                     T 
                      
                     
                       ( 
                       
                         
                           s 
                           1 
                         
                         + 
                         
                           s 
                           2 
                         
                       
                       ) 
                     
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       0 
                       ) 
                     
                   
                 
                 + 
                 
                   
                     Ts 
                     3 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         M 
                         3 
                       
                       ) 
                     
                   
                 
               
               ≤ 
               
                 
                   N 
                   1 
                 
                  
                 
                   c 
                   1 
                   m 
                 
               
             
             ; 
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 3.1 
                  
                 
                   .2 
                   . 
                   
                     
 
                   
                    
                   0 
                 
               
               &lt; 
               
                 m 
                 1 
                 o 
               
               &lt; 
               
                 M 
                 1 
               
             
             , 
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     m 
                     
                       → 
                       o 
                     
                   
                   ) 
                 
               
               = 
               0 
             
             , 
             or 
           
         
       
       
         
           
             
               
                 
                   
                     T 
                      
                     
                       ( 
                       
                         
                           s 
                           1 
                         
                         + 
                         
                           s 
                           2 
                         
                       
                       ) 
                     
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         m 
                         1 
                         o 
                       
                       ) 
                     
                   
                 
                 + 
                 
                   
                     Ts 
                     3 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         
                           m 
                           1 
                           o 
                         
                         + 
                         
                           M 
                           3 
                         
                       
                       ) 
                     
                   
                 
               
               = 
               
                 
                   N 
                   1 
                 
                  
                 
                   c 
                   1 
                   m 
                 
               
             
             ; 
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 3.1 
                  
                 
                   .3 
                   . 
                   
                     
 
                   
                    
                   
                     m 
                     1 
                     o 
                   
                 
               
               = 
               
                 M 
                 1 
               
             
             , 
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     m 
                     
                       → 
                       o 
                     
                   
                   ) 
                 
               
               ≤ 
               0 
             
             , 
             or 
           
         
       
       
         
           
             
               
                 
                   T 
                    
                   
                     ( 
                     
                       
                         s 
                         1 
                       
                       + 
                       
                         s 
                         2 
                       
                     
                     ) 
                   
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       M 
                       1 
                     
                     ) 
                   
                 
               
               + 
               
                 
                   Ts 
                   3 
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       
                         M 
                         1 
                       
                       + 
                       
                         M 
                         3 
                       
                     
                     ) 
                   
                 
               
             
             ≥ 
             
               
                 N 
                 1 
               
                
               
                 
                   c 
                   1 
                   m 
                 
                 . 
               
             
           
         
       
     
         [0079]    For the Case 3.2, eq. 4 becomes: 
         [0000]    
       
         
           
             
               
                 
                   ∂ 
                   
                     ( 
                     NtwkCost 
                     ) 
                   
                 
                 
                   ∂ 
                   
                     m 
                     1 
                   
                 
               
                
               
                 ( 
                 
                   
                     m 
                     → 
                   
                   o 
                 
                 ) 
               
             
             = 
             
               
                 ( 
                 
                   
                     
                       N 
                       1 
                     
                      
                     
                       c 
                       1 
                       m 
                     
                   
                   - 
                   
                     
                       N 
                       2 
                     
                      
                     
                       c 
                       2 
                       m 
                     
                   
                 
                 ) 
               
               - 
               
                 
                   Ts 
                   1 
                 
                  
                 
                     
                 
                  
                 
                   
                     H 
                     ′ 
                   
                   ( 
                   
                       
                   
                    
                   
                     m 
                     1 
                     o 
                   
                    
                   
                       
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 3.2 
                  
                 
                   .1 
                   . 
                   
                       
                   
                    
                   
                     m 
                     1 
                     o 
                   
                 
               
               = 
               0 
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≥ 
               0 
             
             , 
             
                 
             
              
             
                
             
              
             
               
                 
                   or 
                    
                   
                       
                   
                    
                   
                     Ts 
                     1 
                   
                    
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       0 
                       ) 
                     
                   
                 
                 ≤ 
                 
                   
                     
                       N 
                       1 
                     
                      
                     
                       c 
                       1 
                       m 
                     
                   
                   - 
                   
                     
                       N 
                       2 
                     
                      
                     
                       c 
                       2 
                       m 
                     
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 3.2 
                  
                 
                   .2 
                   . 
                   
                       
                   
                    
                   0 
                 
               
               &lt; 
               
                 m 
                 1 
                 o 
               
               &lt; 
               
                 M 
                 1 
               
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               = 
               0 
             
              
             
                 
             
             , 
             
                 
             
              
             
               
 
             
              
             
               
                 
                   or 
                    
                   
                       
                   
                    
                   
                     Ts 
                     1 
                   
                    
                   
                       
                   
                    
                   
                     
                       H 
                       ′ 
                     
                     ( 
                     
                         
                     
                      
                     
                       m 
                       1 
                       o 
                     
                      
                     
                         
                     
                     ) 
                   
                 
                  
                 
                     
                 
                 = 
                 
                   
                     
                       N 
                       1 
                     
                      
                     
                       c 
                       1 
                       m 
                     
                   
                   - 
                   
                     
                       N 
                       2 
                     
                      
                     
                       c 
                       2 
                       m 
                     
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 3.2 
                  
                 
                   .3 
                   . 
                   
                       
                   
                    
                   
                     m 
                     1 
                     o 
                   
                 
               
               = 
               
                 M 
                 1 
               
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≤ 
               0 
             
             , 
             
                 
             
              
             
               
 
             
              
             
               
                 or 
                  
                 
                     
                 
                  
                 
                   Ts 
                   1 
                 
                  
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     
                       M 
                       1 
                     
                     ) 
                   
                 
               
               ≥ 
               
                 
                   
                     N 
                     1 
                   
                    
                   
                     c 
                     1 
                     m 
                   
                 
                 - 
                 
                   
                     N 
                     2 
                   
                    
                   
                     
                       c 
                       2 
                       m 
                     
                     . 
                   
                 
               
             
           
         
       
     
         [0080]    For the Case 3.3, eq. 4 becomes as: 
         [0000]    
       
         
           
             
               
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                     
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               = 
               
                 
                   
                     N 
                     1 
                   
                    
                   
                     c 
                     1 
                     m 
                   
                 
                 - 
                 
                   
                     Ts 
                     1 
                   
                    
                   
                       
                   
                    
                   
                     
                       H 
                       ′ 
                     
                     ( 
                     
                         
                     
                      
                     
                       m 
                       1 
                       o 
                     
                      
                     
                         
                     
                     ) 
                   
                 
                  
                 
                     
                 
                 - 
                 
                   
                     Ts 
                     2 
                   
                    
                   
                       
                   
                    
                   
                     
                       H 
                       ′ 
                     
                     ( 
                     
                         
                     
                      
                     
                       
                         m 
                         1 
                         o 
                       
                        
                       
                           
                       
                       + 
                       
                         M 
                         2 
                       
                     
                     ) 
                   
                 
                 - 
                 
                   
                     Ts 
                     3 
                   
                    
                   
                       
                   
                    
                   
                     
                       H 
                       ′ 
                     
                     ( 
                     
                         
                     
                      
                     
                       
                         m 
                         1 
                         o 
                       
                        
                       
                           
                       
                       + 
                       
                         M 
                         2 
                       
                       + 
                       
                         M 
                         3 
                       
                     
                     ) 
                   
                 
               
             
              
             
                 
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 3.3 
                  
                 
                   .1 
                   . 
                   
                       
                   
                    
                   
                     m 
                     1 
                     o 
                   
                 
               
               = 
               0 
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≥ 
               0 
             
             , 
             
                 
             
              
             
               
 
             
              
             
               
                 
                   
                     or 
                      
                     
                         
                     
                      
                     
                       Ts 
                       1 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         0 
                         ) 
                       
                     
                   
                   + 
                   
                     
                       Ts 
                       2 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           M 
                           2 
                         
                         ) 
                       
                     
                   
                   + 
                   
                     
                       Ts 
                       3 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           
                             M 
                             2 
                           
                           + 
                           
                             M 
                             3 
                           
                         
                         ) 
                       
                     
                   
                 
                 ≤ 
                 
                   
                     N 
                     1 
                   
                    
                   
                     c 
                     1 
                     m 
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 3.3 
                  
                 
                   .2 
                   . 
                   
                       
                   
                    
                   0 
                 
               
               &lt; 
               
                 m 
                 1 
                 o 
               
               &lt; 
               
                 M 
                 1 
               
             
             , 
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               = 
               0 
             
              
             
                 
             
             , 
             
                 
             
              
             
                
             
              
             
               
                 
                   
                     or 
                      
                     
                         
                     
                      
                     
                       Ts 
                       1 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           m 
                           1 
                           o 
                         
                         ) 
                       
                     
                   
                   + 
                   
                     
                       Ts 
                       2 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           
                             m 
                             1 
                             o 
                           
                           + 
                           
                             M 
                             2 
                           
                         
                         ) 
                       
                     
                   
                   + 
                   
                     
                       Ts 
                       3 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           
                             m 
                             1 
                             o 
                           
                           + 
                           
                             M 
                             2 
                           
                           + 
                           
                             M 
                             3 
                           
                         
                         ) 
                       
                     
                   
                 
                 = 
                 
                   
                     N 
                     1 
                   
                    
                   
                     c 
                     1 
                     m 
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
               
                 Case 
                  
                 
                     
                 
                  
                 3.3 
                  
                 
                   .3 
                   . 
                   
                       
                   
                    
                   
                     m 
                     1 
                     o 
                   
                 
               
               = 
               
                 M 
                 1 
               
             
             , 
             
                 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∂ 
                     
                       ( 
                       NtwkCost 
                       ) 
                     
                   
                   
                     ∂ 
                     
                       m 
                       1 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       m 
                       → 
                     
                     o 
                   
                   ) 
                 
               
               ≤ 
               0 
             
             , 
             
                 
             
              
             
               
 
             
              
             
               
                 
                   
                     or 
                      
                     
                         
                     
                      
                     
                       Ts 
                       1 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           M 
                           1 
                         
                         ) 
                       
                     
                   
                   + 
                   
                     
                       Ts 
                       2 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           
                             M 
                             1 
                           
                           + 
                           
                             M 
                             2 
                           
                         
                         ) 
                       
                     
                   
                   + 
                   
                     
                       Ts 
                       3 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           
                             M 
                             1 
                           
                           + 
                           
                             M 
                             2 
                           
                           + 
                           
                             M 
                             3 
                           
                         
                         ) 
                       
                     
                   
                 
                 ≥ 
                 
                   
                     N 
                     1 
                   
                    
                   
                     c 
                     1 
                     m 
                   
                 
               
               ; 
             
           
         
       
     
         [0081]    At this point, up to 9 candidates for the optimal solution can be identified though the actual number of candidates for the optimal solution may be less than 9, because of possible infeasibility. In order to select the most optimal solution, a “backward” process can be used in the tree hierarchy. 
         [0082]    Backward Phase 
         [0083]    Every “seed” m 1   o  found on the 3 rd  step of the forward phase, can be checked to see if a feasible solution m 2   o  exists for a “parent” case. For example, if “seed” m 1   o  was found as a solution of case 2.3.x of the 3 rd  step of forwarding phase, then a check is made of the inequality in case 2.3: Ts 2 H′(m 1   o +M 2 )≧N 2 c 2   m −N 3 c 3   m . If this inequality is true, then corresponding value for m 2   o  is M 2 , which may be defined as a “seed pair” (m 1   o ,m 2   o ). Otherwise, there is no feasible solution for this “seed”. 
         [0084]    For every “seed pair” (m 1   0 ,m 2   0 ) found on the previous step, a check can be made to see if a feasible solution m 3   o  exists for a “parent” case. For example, if “seed pair” (m 1   0 ,m 2   0 ) was found as a solution of case 2.3 on the previous step, then a check may be made of case 2. If equation Ts 3 H′(m 3   o +m 2   o +m 3   o )=N 3 c 3   m  from case 2 has a feasible solution m 3   o , 0&lt;m 3   o &lt;M 3 , then a “seed triple” (m 1   0 ,m 2   0 ,m 3   0 ) may be defined. Otherwise, there is no feasible solution for this “seed pair”. 
         [0085]    Finally, the optimal solution can be selected out of the “seed triples” found above. 
         [0086]    Analysis and Observations 
         [0087]    The analytical solution presented above allows identifying conditions when the optimal solution requires moderate, maximum caching or does not require caching on different levels (DSLAM, CO, IO). Consider several examples. 
       Example 1 
       [0088]    Optimal solution that does not require caching at all corresponds to the case 1.1.1 (and “parent” cases 1.1 and 1 in logical hierarchy). The corresponding equations are: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         0 
                         ) 
                       
                     
                     ≤ 
                     
                       
                         
                           
                             N 
                             1 
                           
                            
                           
                             c 
                             1 
                             m 
                           
                         
                         
                           T 
                            
                           
                             ( 
                             
                               
                                 s 
                                 1 
                               
                               + 
                               
                                 s 
                                 2 
                               
                               + 
                               
                                 s 
                                 3 
                               
                             
                             ) 
                           
                         
                       
                        
                       
                           
                       
                        
                       and 
                        
                       
                           
                       
                        
                       
                         m 
                         1 
                         o 
                       
                     
                   
                   = 
                   0 
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           m 
                           1 
                           o 
                         
                         ) 
                       
                     
                     ≤ 
                     
                       
                         
                           
                             N 
                             2 
                           
                            
                           
                             c 
                             2 
                             m 
                           
                         
                         
                           T 
                            
                           
                             ( 
                             
                               
                                 s 
                                 2 
                               
                               + 
                               
                                 s 
                                 3 
                               
                             
                             ) 
                           
                         
                       
                        
                       
                           
                       
                        
                       and 
                        
                       
                           
                       
                        
                       
                         m 
                         2 
                         o 
                       
                     
                   
                   = 
                   0 
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           
                             m 
                             1 
                             o 
                           
                           + 
                           
                             m 
                             2 
                             o 
                           
                         
                         ) 
                       
                     
                     ≤ 
                     
                       
                         
                           
                             N 
                             3 
                           
                            
                           
                             c 
                             3 
                             m 
                           
                         
                         
                           Ts 
                           3 
                         
                       
                        
                       
                           
                       
                        
                       and 
                        
                       
                           
                       
                        
                       
                         m 
                         3 
                         o 
                       
                     
                   
                   = 
                   0 
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
         [0089]    In order that equations (8)-(10) have a solution, the following inequality should take place: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       0 
                       ) 
                     
                   
                   ≤ 
                   
                     min 
                      
                     
                       ( 
                       
                         
                           
                             
                               N 
                               1 
                             
                              
                             
                               c 
                               1 
                               m 
                             
                           
                           
                             T 
                              
                             
                               ( 
                               
                                 
                                   s 
                                   1 
                                 
                                 + 
                                 
                                   s 
                                   2 
                                 
                                 + 
                                 
                                   s 
                                   3 
                                 
                               
                               ) 
                             
                           
                         
                         , 
                         
                           
                             
                               N 
                               2 
                             
                              
                             
                               c 
                               2 
                               m 
                             
                           
                           
                             T 
                              
                             
                               ( 
                               
                                 
                                   s 
                                   2 
                                 
                                 + 
                                 
                                   s 
                                   3 
                                 
                               
                               ) 
                             
                           
                         
                         , 
                         
                           
                             
                               N 
                               3 
                             
                              
                             
                               c 
                               3 
                               m 
                             
                           
                           
                             Ts 
                             3 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
         [0090]    Equation (11) indicates that if hit rate growth at 0 is below some threshold (this threshold depends on topology, traffic and cost parameters), no caching is required for the optimal solution. 
       Example 2 
       [0091]    Optimal solution that requires moderate (i.e., below maximum cache size) caching on all three levels corresponds to the case 2.2.2 (and “parent” cases 2.2 and 2 in logical hierarchy). The corresponding equations are: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         m 
                         1 
                         o 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         
                           
                             
                               N 
                               1 
                             
                              
                             
                               c 
                               1 
                               m 
                             
                           
                           - 
                           
                             
                               N 
                               2 
                             
                              
                             
                               c 
                               2 
                               m 
                             
                           
                         
                         
                           Ts 
                           1 
                         
                       
                        
                       
                           
                       
                        
                       and 
                        
                       
                           
                       
                        
                       0 
                     
                     &lt; 
                     
                       m 
                       1 
                       o 
                     
                     &lt; 
                     
                       M 
                       1 
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         
                           m 
                           1 
                           o 
                         
                         + 
                         
                           m 
                           2 
                           o 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         
                           
                             
                               N 
                               2 
                             
                              
                             
                               c 
                               2 
                               m 
                             
                           
                           - 
                           
                             
                               N 
                               3 
                             
                              
                             
                               c 
                               3 
                               m 
                             
                           
                         
                         
                           Ts 
                           2 
                         
                       
                        
                       
                           
                       
                        
                       and 
                        
                       
                           
                       
                        
                       0 
                     
                     &lt; 
                     
                       m 
                       2 
                       o 
                     
                     &lt; 
                     
                       M 
                       2 
                     
                   
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         
                           m 
                           1 
                           o 
                         
                         + 
                         
                           m 
                           2 
                           o 
                         
                         + 
                         
                           m 
                           3 
                           o 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         
                           
                             N 
                             3 
                           
                            
                           
                             c 
                             3 
                             m 
                           
                         
                         
                           Ts 
                           3 
                         
                       
                        
                       
                           
                       
                        
                       and 
                        
                       
                           
                       
                        
                       0 
                     
                     &lt; 
                     
                       m 
                       3 
                       o 
                     
                     &lt; 
                     
                       M 
                       3 
                     
                   
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
         [0092]    If (12) has a solution m 1   o , its value may be substituted in (13). If (13) has a solution m 2   o , its value may be substituted in (14). If (14) has a solution m 3   o , that gives an optimal solution (m 1   o , m 2   o , m 3   o ) that uses caching in DSLAM, CO and IO levels. 
       Example 3 
       [0093]    Optimal solution that requires maximum caching (i.e., m i   o =M i , i=1, 2, 3) on all three levels corresponds to the case 3.3.3 (and “parent” cases 3.3 and 3 in logical hierarchy). The corresponding equations are: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         s 
                         1 
                       
                        
                       
                         
                           H 
                           ′ 
                         
                          
                         
                           ( 
                           
                             M 
                             1 
                           
                           ) 
                         
                       
                     
                     + 
                     
                       
                         s 
                         1 
                       
                        
                       
                         
                           H 
                           ′ 
                         
                          
                         
                           ( 
                           
                             
                               M 
                               1 
                             
                             + 
                             
                               M 
                               2 
                             
                           
                           ) 
                         
                       
                     
                     + 
                     
                       
                         s 
                         3 
                       
                        
                       
                         
                           H 
                           ′ 
                         
                          
                         
                           ( 
                           
                             
                               M 
                               1 
                             
                             + 
                             
                               M 
                               2 
                             
                             + 
                             
                               M 
                               3 
                             
                           
                           ) 
                         
                       
                     
                   
                   ≥ 
                   
                     
                       
                         N 
                         1 
                       
                        
                       
                         c 
                         1 
                         m 
                       
                     
                     T 
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         s 
                         2 
                       
                        
                       
                         
                           H 
                           ′ 
                         
                          
                         
                           ( 
                           
                             
                               M 
                               1 
                             
                             + 
                             
                               M 
                               2 
                             
                           
                           ) 
                         
                       
                     
                     + 
                     
                       
                         s 
                         3 
                       
                        
                       
                         
                           H 
                           ′ 
                         
                          
                         
                           ( 
                           
                             
                               M 
                               1 
                             
                             + 
                             
                               M 
                               2 
                             
                             + 
                             
                               M 
                               3 
                             
                           
                           ) 
                         
                       
                     
                   
                   ≥ 
                   
                     
                       
                         N 
                         2 
                       
                        
                       
                         c 
                         2 
                         m 
                       
                     
                     T 
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       s 
                       3 
                     
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           
                             M 
                             1 
                           
                           + 
                           
                             M 
                             2 
                           
                           + 
                           
                             M 
                             3 
                           
                         
                         ) 
                       
                     
                   
                   ≥ 
                   
                     
                       
                         N 
                         3 
                       
                        
                       
                         c 
                         3 
                         m 
                       
                     
                     T 
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
         [0094]    Consider now the case when cache memory cost and equipment cost (in terms of cost per unit of traffic) does not depend on level of hierarchy (homogeneous cost): 
         [0000]      c 1   m =c 2   m =c 3   m =c m   (18) 
         [0000]      c 11   t =c 12   t =c 21   t =c 22   t =c 31   t =c 32   t =c 41   t =c 42   t =c t   (19) 
         [0095]    Therefore, from eq. 7: 
         [0000]      s 1 =s 2 =2c t   (20) 
         [0000]      s 3 =3c t   (21) 
         [0096]    Note, that if cost is homogeneous, optimal cache configuration for a given topology (N 1 , N 2 , N 3 ), hit rate function H and maximum cache sizes (M 1 , M 2 , M 3 ) depends on the ratio 
         [0000]    
       
         
           
             
               
                 c 
                 m 
               
               
                 Tc 
                 t 
               
             
             . 
           
         
       
     
         [0097]    Substituting (18)-(21) into (11), gives rise to the following condition of optimal solution without cache: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       0 
                       ) 
                     
                   
                   ≤ 
                   
                     
                       
                         c 
                         m 
                       
                       
                         Tc 
                         t 
                       
                     
                      
                     
                       min 
                        
                       
                         ( 
                         
                           
                             
                               N 
                               1 
                             
                             7 
                           
                           , 
                           
                             
                               N 
                               2 
                             
                             5 
                           
                           , 
                           
                             
                               N 
                               3 
                             
                             3 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     11 
                      
                     a 
                   
                   ) 
                 
               
             
           
         
       
     
         [0098]    Equation (11a) demonstrates an impact of hit rate, cost, traffic and topology parameters on optimal cache architecture. For example, the chances that the optimal solution does not require caching increases when:
       Ratio       
 
         [0000]    
       
         
           
             
               c 
               m 
             
             
               Tc 
               t 
             
           
         
       
     
         [0000]    of memory cost c m  over equipment cost c t  and traffic T is high;
       Numbers of DSLAMs (N 1 ), COs (N 2 ) and IOs (N 3 ), but especially DSLAMs are large;   Hit rate function H has a small level of growth at 0.       
 
         [0102]    Substituting (18)-(21) into (12)-(14), the following equations define a condition of optimal solution with moderate caching on all levels: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         m 
                         1 
                         o 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         
                           
                             ( 
                             
                               
                                 N 
                                 1 
                               
                               - 
                               
                                 N 
                                 2 
                               
                             
                             ) 
                           
                            
                           
                             c 
                             m 
                           
                         
                         
                           2 
                            
                           
                               
                           
                            
                           
                             Tc 
                             1 
                             t 
                           
                         
                       
                        
                       
                           
                       
                        
                       and 
                        
                       
                           
                       
                        
                       0 
                     
                     &lt; 
                     
                       m 
                       1 
                       o 
                     
                     &lt; 
                     
                       M 
                       1 
                     
                   
                 
               
               
                 
                   ( 
                   
                     12 
                      
                     a 
                   
                   ) 
                 
               
             
             
               
                 
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         
                           m 
                           1 
                           o 
                         
                         + 
                         
                           m 
                           2 
                           o 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         
                           
                             ( 
                             
                               
                                 N 
                                 2 
                               
                               - 
                               
                                 N 
                                 3 
                               
                             
                             ) 
                           
                            
                           
                             c 
                             m 
                           
                         
                         
                           2 
                            
                           
                               
                           
                            
                           
                             Tc 
                             t 
                           
                         
                       
                        
                       
                           
                       
                        
                       and 
                        
                       
                           
                       
                        
                       0 
                     
                     &lt; 
                     
                       m 
                       2 
                       o 
                     
                     &lt; 
                     
                       M 
                       2 
                     
                   
                 
               
               
                 
                   ( 
                   
                     13 
                      
                     a 
                   
                   ) 
                 
               
             
             
               
                 
                   
                     
                       H 
                       ′ 
                     
                      
                     
                       ( 
                       
                         
                           m 
                           1 
                           o 
                         
                         + 
                         
                           m 
                           2 
                           o 
                         
                         + 
                         
                           m 
                           3 
                           o 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         
                           
                             N 
                             3 
                           
                            
                           
                             c 
                             m 
                           
                         
                         
                           3 
                            
                           
                               
                           
                            
                           
                             Tc 
                             t 
                           
                         
                       
                        
                       
                           
                       
                        
                       and 
                        
                       
                           
                       
                        
                       0 
                     
                     &lt; 
                     
                       m 
                       3 
                       o 
                     
                     &lt; 
                     
                       M 
                       3 
                     
                   
                 
               
               
                 
                   ( 
                   
                     14 
                      
                     a 
                   
                   ) 
                 
               
             
           
         
       
     
         [0103]    Substituting (18)-(21) into (15)-(17), the following equations define a condition of optimal solution with maximum caching on all levels: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       2 
                        
                       
                         
                           H 
                           ′ 
                         
                          
                         
                           ( 
                           
                             M 
                             1 
                           
                           ) 
                         
                       
                     
                     + 
                     
                       2 
                        
                       
                           
                       
                        
                       
                         
                           H 
                           ′ 
                         
                          
                         
                           ( 
                           
                             
                               M 
                               1 
                             
                             + 
                             
                               M 
                               2 
                             
                           
                           ) 
                         
                       
                     
                     + 
                     
                       3 
                        
                       
                         
                           H 
                           ′ 
                         
                          
                         
                           ( 
                           
                             
                               M 
                               1 
                             
                             + 
                             
                               M 
                               2 
                             
                             + 
                             
                               M 
                               3 
                             
                           
                           ) 
                         
                       
                     
                   
                   ≥ 
                   
                     
                       
                         N 
                         1 
                       
                        
                       
                         c 
                         m 
                       
                     
                     
                       Tc 
                       t 
                     
                   
                 
               
               
                 
                   ( 
                   
                     15 
                      
                     a 
                   
                   ) 
                 
               
             
             
               
                 
                   
                     
                       2 
                        
                       
                         
                           H 
                           ′ 
                         
                          
                         
                           ( 
                           
                             
                               M 
                               1 
                             
                             + 
                             
                               M 
                               2 
                             
                           
                           ) 
                         
                       
                     
                     + 
                     
                       3 
                        
                       
                           
                       
                        
                       
                         
                           H 
                           ′ 
                         
                          
                         
                           ( 
                           
                             
                               M 
                               1 
                             
                             + 
                             
                               M 
                               2 
                             
                             + 
                             
                               M 
                               3 
                             
                           
                           ) 
                         
                       
                     
                   
                   ≥ 
                   
                     
                       
                         N 
                         2 
                       
                        
                       
                         c 
                         m 
                       
                     
                     
                       Tc 
                       t 
                     
                   
                 
               
               
                 
                   ( 
                   
                     16 
                      
                     a 
                   
                   ) 
                 
               
             
             
               
                 
                   
                     3 
                      
                     
                       
                         H 
                         ′ 
                       
                        
                       
                         ( 
                         
                           
                             M 
                             1 
                           
                           + 
                           
                             M 
                             2 
                           
                           + 
                           
                             M 
                             3 
                           
                         
                         ) 
                       
                     
                   
                   ≥ 
                   
                     
                       
                         N 
                         3 
                       
                        
                       
                         c 
                         m 
                       
                     
                     
                       Tc 
                       t 
                     
                   
                 
               
               
                 
                   ( 
                   
                     17 
                      
                     a 
                   
                   ) 
                 
               
             
           
         
       
     
         [0104]    Equations (15a)-(17a) demonstrate that the chances that the optimal solution requires maximum caching on all levels increases when:
       Ratio       
 
         [0000]    
       
         
           
             
               c 
               m 
             
             
               Tc 
               t 
             
           
         
       
     
         [0000]    of memory cost c m  over equipment cost c t  and traffic T is low;
       Numbers of DSLAMs (N 1 ), COs (N 2 ) and IOs (N 3 ) are small;   Hit rate function H has a high level of growth at points M 1 , M 1 +M 2  and M 1 +M 2 +M 3 .       
 
         [0108]    Sensitivity Study 
         [0109]    Objective 
         [0110]    The impact of various parameters on optimal cache configuration will now be described using the following two metrics of optimal cache configuration:
       Size of cache memory in DSLAM, CO and IO nodes, that is {right arrow over (m)} o =(m 1   o ,m 2   o ,m 3   o );   Cost gain characterizes a potential cost savings from caching and defined as 1−NtwkCost opt /NtwkCoSt NoCache , where NtwkCost opt  is a cost (1) of network with optimal cache configuration, and NtwkCost NoCache  is a cost (1) of network without cache.       
 
         [0113]    Reference Scenario 
         [0114]    As a reference scenario, there is considered a network defined by the following parameters:
       N 1 , a total number of DSLAMs in the network, is 9,600;   N 2 , a total number of service switches in all COs, is 100;   N 3 , a total number of service routers in all IOs, is 16;   Total amount of traffic, T, in reference network is 9,600,000 Mbs (i.e., 1 Gbs per DSLAM);   M 1 , a maximum cache size per DSLAM, is 100 GB;   M 2 , a maximum cache size per service switch at CO, is 12,000 GB;   M 3 , a maximum cache size per service router at IO, is 24,000 GB.       
 
         [0122]    It is assumed that the unit cost of cache memory in DSLAM, CO and IO is $22/GB. As for equipment cost (i.e., cost per unit of traffic), it is assumed that the unit cost of upstream DSLAM traffic is $1.5/Mbs, unit cost of upstream and downstream CO traffic is $2.5/Mbs, and unit cost of upstream and downstream IO and VHO traffic is $4/Mbs. That corresponds to S 1 =$4/Mbs, S 2 =$6.5/Mbs, and S 3 =$12/Mbs. 
         [0123]    Hit rate function H(m) may be modeled in such a way that its derivative, H′(m), represents continuous version of Zipf-Mandelbrot distribution: 
         [0000]    
       
         
           
             
               
                 
                   H 
                   ′ 
                 
                  
                 
                   ( 
                   m 
                   ) 
                 
               
               = 
               
                 K 
                 
                   
                     ( 
                     
                       m 
                       + 
                       q 
                     
                     ) 
                   
                   α 
                 
               
             
             , 
           
         
       
     
         [0000]    truncated on interval [ 0 ,M], where 0&lt;M≦∞. Here, ZM power parameter α≧0 characterizes hit rate steepness at 0, shift parameter q&gt;0, and K is normalization coefficient: 
         [0000]    
       
         
           
             
               
                 ∫ 
                 0 
                 M 
               
                
               
                 
                   
                     H 
                     ′ 
                   
                    
                   
                     ( 
                     m 
                     ) 
                   
                 
                  
                 
                     
                 
                  
                 
                    
                   m 
                 
               
             
             = 
             1 
           
         
       
     
         [0124]    For the reference case, chosen parameters may be a α=1, q=1, and M=100,000. 
         [0125]    In the following, there is shown the sensitivity of optimal cache sizes to various parameters. 
         [0126]    Sensitivity to Power Parameter of ZM Distribution 
         [0127]    Sensitivity to power parameter of ZM distribution is shown for several levels of traffic per DSLAM: 0.1 Gbs, 0.5 Gbs, 1 Gbs and 10 Gbs (see  FIG. 6 ). 
         [0128]    Note, that for a small amount of traffic (e.g., 0.1 Gbs per DSLAM), the optimal amount of cache per node increases with ZM-power parameter up to some point, and then starts to decrease. When ZM-power parameter is small (i.e., hit rate is relatively flat) cache effectiveness is also small, so the optimal cache configuration uses a small amount of cache or no cache at all. With an increase of the ZM-power parameter, the cache effectiveness as well as cache size in the optimal configuration increases. After some point, further increases of ZM-power parameter has an inverse effect: i.e. the hit rate becomes so steep and cache effectiveness so high that the optimal result can be achieved with smaller and smaller amounts of cache size per node. Therefore, optimal cache size as a function of ZM-power parameter obtains its maximum at some point and declines after that. The maximum point of optimal cache size depends on total amount of traffic T and increases with increase of traffic. For a larger amount of traffic, when optimal cache size attains its limit, some boundary effect starts to play its role at first for cache at IO level, and then for cache at all three levels (IO, CO and DSLAM). In all considered scenarios, cost gain increases with power parameter. 
         [0129]    Sensitivity to Traffic 
         [0130]    The optimal amount of cache per DSLAM, CO and IO nodes, as well as cost gain, increases with traffic (see  FIG. 7 ). To justify cache at DSLAM, traffic should exceed some threshold. This threshold decreases with increase of ZM-power parameter as we demonstrated earlier. 
         [0131]    Sensitivity to Equipment Cost 
         [0132]    The optimal cache configuration depends on cost parameters S 1 , S 2 , and S 3 , defined by (7). There is a strong impact of value S 1  on size of DSLAM cache, value of S 2  on size of CO cache and value S 3  on size of IO cache (see  FIG. 8 ). 
         [0133]    In the same time, there may be an “isolation effect”: i.e. there is a relatively small impact of S 1  on size of CO and IO cache, S 2  on size of DSLAM and IO cache and S 3  on size of DSLAM and CO cache (see  FIG. 9 ). 
         [0134]    For example, when S 1  tends to 0, DSLAM cache size also tends to 0 (similar effect for S 2  and S 3 ). Caching in DSLAM impacts all network cost elements upstream from DSLAM by reducing traffic (a) from CO to DSLAM, (b) from IO to CO and (c) from VHO to IO. However, while (a) may be reduced by DSLAM caching (but not by CO and IO caching), for reduction of (b) caching at DSLAM and/or at CO can be used, and for reduction of (c) caching at DSLAM, at CO, and/or at IO can be used. Now, assume that S 1 =0 (or very small). In this case, caching at DSLAM makes no or small difference on network cost related to S 1 , because for upstream network cost (related to S 2  and S 3  elements), it is preferred to use the same amount X GB of cache memory at CO than at DSLAM to achieve the same network cost reduction effect, but with smaller cost there is X GB of cache memory at each CO instead of X GB of memory at each DSLAM. Cost gain decreases with increase of equipment cost. 
         [0135]    Sensitivity to Memory Cost 
         [0136]    When memory cost drops, more cache is used in an optimal configuration ( FIG. 10 ). The DSLAM cache as a part of optimal hierarchical configuration is used when cache cost is below some threshold. 
         [0137]    As described herein, the analytical model allows a calculation of optimal cache configuration and to investigate how sensitive the solution is to various parameters of the system (traffic, topology, cost parameters). 
         [0138]    Once an optimal solution of the network cost function has been determined and optimal values for the cache memory sizes m 1 , m 2 , and m 3  have been selected, the nodes of the network, i.e. the IOs  18 , COs  16  and DSLAMs  14  can be provided with cache memory in accordance with the optimized solution. 
         [0139]    In one embodiment, the analytical model of the network cost function may embodied in a computer system including one or more processors  1101  as shown in  FIG. 11 . The processor  1101  may be a system processor operatively associated with a system memory  1102  that stores an instruction set such as software for calculating a network cost function. The process may cause a user interface (not shown) to display user prompts that allow a user to provide input parameters such as the traffic, topology and costing parameters as described above. An example instruction set is shown in the flowchart  200  of  FIG. 12 . At step  201 , the processor receives the input parameters, e.g. through the user interface, and then at step  202 , the processor calculates a cache memory size for a plurality of network nodes of an Internet Protocol TeleVision network that minimizes a network cost of the Internet Protocol TeleVision network. 
         [0140]    The user interface may be displayed on a separate computer terminal such that the system processor  1101  may receive parameter information from a second processor  1107 , such as a user processor which is also operatively associated with a memory  1108 . The communication between the processors  1101 ,  1107  may be provided by a suitable communications link  1105  which may be hard wired, wireless, internet or FTP based, or any other suitable communications link. 
         [0141]    Although embodiments of the present invention have been illustrated in the accompanied drawings and described in the foregoing description, it will be understood that the invention is not limited to the embodiments disclosed, but is capable of numerous rearrangements, modifications, and substitutions without departing from the spirit of the invention as set forth and defined by the following claims. For example, the capabilities of the invention can be performed fully and/or partially by one or more of the blocks, modules, processors or memories. Also, these capabilities may be performed in the current manner or in a distributed manner and on, or via, any device able to provide and/or receive information. Further, although depicted in a particular manner, various modules or blocks may be repositioned without departing from the scope of the current invention. Still further, although depicted in a particular manner, a greater or lesser number of modules and connections can be utilized with the present invention in order to accomplish the present invention, to provide additional known features to the present invention, and/or to make the present invention more efficient. Also, the information sent between various modules can be sent between the modules via at least one of a data network, the Internet, an Internet Protocol network, a wireless source, and a wired source and via plurality of protocols.