Patent Publication Number: US-6661789-B1

Title: Dynamic burstification based on fully/partially shared multicast entities

Description:
TECHNICAL FIELD OF THE INVENTION 
     The present invention relates generally to optical network systems, and more particularly, a system and method for providing dynamic burstification of multicast traffic based on fully/partially shared multicast entities. 
     BACKGROUND OF THE INVENTION 
     Data traffic over networks, particularly the internet, has increased dramatically over the past several years, and this trend will continue with increasing number of users and the introduction of new services which require more bandwidth. The enlarged volume of internet traffic requires a network with high capacity routers capable of routing unicast and multicast data packets with variable lengths. A unicast data packet is a data packet generated from an application requiring point-to-point communication. The unicast data packet is switched through a series of electronic packet switching systems to its destination. A multicast data packet is a data packet generated from an application requiring point-to-multipoint or multipoint-to-multipoint communications. The multicast data packet is switched through a tree of electronic packet switching systems to multiple destinations. 
     Different approaches advocating the use of optical technology in place of electronics in switching systems have been proposed, however current optical networks use only a small fraction of the bandwidth available on a single optical fiber. The emergence of dense-wavelength division multiplexing (DWDM) technology has helped to overcome the bandwidth problems encountered by current optical networks. A single DWDM optical fiber now has the capability of carrying as much as ten (10) terabits of data per second. However, this creates a serious mismatch with current switching technologies which are capable of switching data at rates of only up to a few hundreds gigabits per second. 
     While emerging ATM switches and IP routers can be used to switch data using the individual channels within a DWDM fiber, typically at 2.4 gigabits per second or 10 gigabits per second, this approach implies that tens or hundreds of switch interfaces must be used to terminate a single link with a large number of channels. 
     One approach, called optical burst-switched networking, attempts to achieve the best combination of optical and electronic switching technologies. To circumvent potential bottlenecks in electronic processing, the data unit to be transferred in the optical burst-switched network is a data burst. A data burst, or simply a burst, is a collection of one or more data packets which have a set of common attributes. An obvious example would be a common egress point in an optical burst-switched network. The electronics provide dynamic control of system resources by assigning individual user data bursts to channels on a DWDM fiber. Optical technology is used to switch the user data bursts entirely within an optical domain. Optical burst switched networks are able to switch both unicast and multicast data bursts. However, limitations of optical component technology has largely limited optical switching to facility management applications. 
     Previously developed optical burst-switched networking systems have performed poorly and generally tend to demonstrate the inefficiency of current optical components. For example, one prior art optical burst-switched network utilized ATM switches in the control network which made the design of the control network much more complicated and suboptimal. Other prior art optical burst-switched networks used electronic buffers in the optical routers, thus the optical burst-switched network was not purely optical. The electronic buffers did not provide end-to-end transparent optical paths for data bursts. Thus, little has been done to stimulate any serious move toward optical burst-switching. 
     SUMMARY OF THE INVENTION 
     The present invention provides a dynamic burstification system and method based on fully/partially shared multicast trees that substantially eliminates or reduces disadvantages and problems associated with previously developed systems and methods used for switching multicast data packets. 
     More specifically, the present invention provides a system and method for collecting multiple multicast data packets into a multicast burst according to some multicast burstification classification criteria, then switching the multicast burst through an optical burst switched network. To switch multicast data packets through an optical burst switched network according to the present invention, multicast data packets are first assembled into a multicast burst at an electronic ingress edge router according to a plurality of multicast burstification criteria (classes). The multicast burst is then switched through the optical burst-switched network to the destined electronic egress edge routers where the burst is disassembled back into multicast data packets and transmitted to its final (multiple) destinations. 
     The present invention provides a technical advantage by providing an optimized way to assemble multiple multicast data packets into a single multicast burst according to multiple multicast burstification classes and transmitting the multicast burst through an optical burst switched network. 
     The present invention provides a technical advantage by increasing the burst length of multicast traffic, thus providing increased efficiency in the transfer of multicast traffic in optical burst-switched networks. 
     The present invention provides another technical advantage by reducing the burst assembly time interval resulting in reduced multicast data packet latency at an electronic ingress edge router. 
     The present invention provides another technical advantage by reducing the amount of control traffic and control operations necessary to forward/route multicast bursts to their destinations. 
     The present invention provides another technical advantage since it is largely independent of the specifics of the control units of underlying optical burst-switches (e.g. ATM based) or the specifics of the optical switch matrix (e.g. may use electronic or optical buffers). 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     For a more complete understanding of the present invention and the advantages thereof, reference is now made to the following description taken in conjunction with the accompanying drawings in which like reference numerals indicate like features and wherein: 
     FIG. 1 shows one example of an optical burst-switched (OBS) network; 
     FIG. 2 shows one example of an equi-tree in an optical burst switched network (ETON) according to the present invention; 
     FIG. 3 shows one example of equi-coverage in an optical burst-switched network (ECON) according to the present invention; 
     FIG. 4 shows one example of super-coverage in an optical burst-switched network (SCON) according to the present invention; 
     FIG. 5 shows another example of super-coverage in an optical burst-switched network according to the present invention; 
     FIG. 6 shows one example of overlapping-coverage in an optical burst-switched network (OCON) according to the present invention; 
     FIG. 7 depicts a method for searching for multicast burstification classes in terms of a set of electronic egress edge routers; 
     FIG. 8 is a diagram showing two trees that are to be merged using the Breadth-First-Merge algorithm; 
     FIG. 9 is a diagram showing the result after the Breadth-First-Merge algorithm was run to merge the two trees in FIG. 8; 
     FIG. 10 shows a data structure for an ETON implementation; 
     FIG. 11 shows a data structure for ECON, SCON, and OCON implementations; 
     FIG. 12 shows a data structure of a multicast burstification class for ETON, ECON, SCON, and OCON; and 
     FIG. 13 shows a data structure for a multicast tree for ETON, ECON, SCON, and OCON. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Preferred embodiments of the present invention are illustrated in the FIGUREs, like numerals being used to refer to like and corresponding parts of the various drawings. 
     FIG. 1 shows one example of an optical burst-switched (OBS) network  100  according to the present invention. The optical burst-switched network  100  includes a plurality of electronic ingress edge routers  105 , a plurality of optical core routers  110 , a plurality of electronic egress edge routers  115 , and a plurality of DWDM links  120 . A plurality of input subnets  125  and destination subnets  130  shown in FIG. 1 are located outside the optical burst-switched network  100 . The optical burst-switched network  100  is able to switch unicast, multicast and broadcast databursts. 
     Note that, although electronic ingress edge router and electronic egress edge router are logically distinguished in FIG. 1, both functions are often physically combined in one single physical edge router device. Unicast data packets are assembled into bursts according to their destination electronic egress edge router address  115 . Multicast data packets are assembled into multicast bursts according to their source address and multicast group address (S, G), or simply by their multicast group address (*, G), depending on the multicast routing protocol used. Broadcast data packets are a special case of multicast data packets where the data packets are broadcast to every address in the optical burst-switched network  100 . 
     Apart from the source address and the multicast group address, multicast bursts are assembled based on two parameters, burst assembly time interval and maximum burst length. Because multicast data packets are usually assembled into multicast bursts within given time intervals (that are constrained by end-to-end delay among others), the average burst length of single group multicast traffic is much smaller than that of unicast traffic, as fewer packets fit the criteria to be assembled together in one burst. For a given multicast burst overhead, this results in very inefficient transfer of multicast traffic in the optical burst-switched network  100 . For example, if the multicast burst overhead is 10 Kbits in a 10 Gbps channel, an average multicast burst length of 200 Kbits is required to achieve 95% channel utilization. 
     In one embodiment of the present invention, increasing the average burst length for multicast traffic is accomplished by increasing the multicast burst assembly time interval. In another embodiment of the present invention, multicast data packets are assembled into bursts, not corresponding to merely one multicast group, but sets of multicast groups. A multicast group is a set of senders and receivers. From the optical burst-switched network  100  point of view, a multicast group consists of an electronic ingress edge router and a set of electronic egress edge routers. A multicast burstification class can be defined according to one of four scenarios. For the sake of simplicity, only two multicast groups in a multicast burstification class are shown to be associated with multicast trees T 1  and T 2  in describing each of the four scenarios. However, multiple groups within a multicast burstification class could be associated with multiple multicast trees. Although other criteria (e.g. quality of service or security requirements) may determine the burstification classes, these are not taken into account in this description. 
     In each of the four scenarios, T=(C, E, L) where T represents a multicast tree of a multicast group in the optical burst-switched network  100 , C is the set of optical core routers  110 , E is the set of member electronic ingress and egress edge routers,  105  and  115  respectively, and L is the set of DWDM links  120  that are occupied by a given multicast tree to deliver the multicast bursts. Furthermore, if there are N multicast burstification classes (MBC) at an electronic ingress edge router and the j th  multicast burstification class has R j  multicast trees then: 
     
       
           MBC   j =( T   j1   , T   j2   , . . . , T   jRJ ), where j=1,2, . . . , N 
       
     
     
       
         and 
       
     
     
       
           T   jk =( C   jk   , E   jk   , L   jk ), where k=1,2, . . . ,  R   j . 
       
     
     FIG. 2 shows one example of the first multicast burstification class called an “equi-tree in an optical burst-switched network” (ETON)  200 . The equi-tree in an optical burst-switched network or ETON includes one electronic ingress edge router  105 , a plurality of optical core routers  110 , a plurality of electronic egress edge routers  115 , a plurality of DWDM links  120 , a first multicast tree T 1    205  and a second multicast tree T 2    210 . In this first scenario, multicast trees associated with a multicast burstification class share the same links  120 , core routers  110 , electronic ingress edge router  105 , and electronic egress edge routers  115 . Specifically, for MBC j , T j1 =T j2 = . . . =T jRJ . 
     In one embodiment of ETON, all of the multicast data packets associated with the first multicast tree T 1    205  would be assembled in a multicast burst at the electronic ingress edge router  105  and switched through the optical burst-switched network  100  to the electronic egress edge routers E 4  and E 8    115 . Similarly, all of the multicast data packets associated with the second multicast tree T 2    210  would be assembled in a multicast burst at the electronic ingress edge router  105  and switched through the optical burst-switched network  100  to the electronic egress edge routers E 4  and E 8    115 . Once the two multicast bursts reach their respective electronic egress edge routers they would be disassembled and transmitted to their respective destination subnets  130 . 
     The problem with assembling the multicast data packets into two separate bursts at the same electronic ingress edge router  105  and transmitting the two multicast bursts to the same electronic egress edge routers  115  is that the same overhead is used for each multicast burst. In addition, since each multicast burst must be assembled in a given time interval and the volume of the multicast traffic is not very big, it is unlikely that enough multicast data packets will be assembled in a short interval. 
     In another embodiment of ETON, if a set of multicast data packets associated with different multicast trees which share the same electronic ingress edge router  105 , DWDM links  120 , optical core routers  110 , and electronic egress edge routers  115 , packets can be assembled together into a single multicast burst with one set of overhead. Hence, it is more likely that more multicast data packets can be assembled in the same time interval, thus making multicast data packet switching more efficient. In FIG. 2 note that the first multicast tree T 1    205  and the second multicast tree T 2    210  both share the same DWDM links  120 , optical core routers  110 , electronic ingress edge router  105 , and electronic egress edge routers  115  thus creating an equi-tree. Therefore, all of the multicast data packets associated with the first and second multicast trees, T 1    205  and T 2    210 , can be grouped in a multicast burstification class. The multicast packets can then be assembled into a single multicast burst with one set of overhead at the electronic ingress edge router  105  and switched through the optical burst-switched network  100  on either the first multicast tree T 1    205  or the second multicast tree T 2    210 . The single multicast burst can then be disassembled back into the multicast data packets at the electronic egress edge routers E 4  and E 8    115  and transmitted to the output subnets  130 . 
     FIG. 3 shows one example of the second multicast burstification class called equi-coverage in an optical burst-switched network (ECON)  300 . The ECON includes one electronic ingress edge router  105 , a plurality of optical core routers  110 , a plurality of electronic egress edge routers  115 , a plurality of DWDM links  120 , a first multicast tree T,  305 , and a second multicast tree T 2    310 . In this second scenario, the multicast trees associated with a multicast burstification classes share the same electronic ingress edge routers  105  and electronic egress edge routers  115 , but do not necessarily share the same DWDM links  120 , or optical core routers  110 . Specifically, MBC j , E j1 =E j2 = . . . =E jRJ  in the ECON case. 
     In one embodiment of ECON, all of the multicast data packets associated with the first multicast tree T 1    305  would be assembled in a multicast burst at the electronic ingress edge router  105  and switched through the optical burst switched network  100  to the electronic egress edge routers E 4  and E 8    115 . Similarly, all of the multicast data packets associated with the second multicast tree T 2    310  would be assembled in a multicast burst at the electronic ingress edge router  105  and switched through the optical burst-switched network to the electronic egress edge routers E 4  and E 8    115 . Once the two multicast bursts reached their respective electronic egress edge routers  115  they would be disassembled and transmitted to their respective destination subnets  130 . 
     Again, the problem with assembling the multicast data packets into two separate bursts at the same electronic ingress edge router  105  and transmitting the two multicast bursts to the same electronic egress edge routers  115  is that the same overhead is used for each multicast burst. Since each multicast burst must be assembled in a given time interval and the volume of the multicast traffic can be relatively light so that relatively few multicast data packets will be assembled during short time intervals. 
     In another embodiment of ECON, if a set of multicast data packets that are associated with different multicast trees and share the same electronic ingress edge router  105  and electronic egress edge routers  115  can be assembled together into a single multicast burst with one set of overhead, it is more likely that more multicast data packets can be assembled in the same time interval, thus making multicast data packet switching more efficient. In FIG. 3 note that the first multicast tree T 1    305  and the second multicast tree T 2    310  both share the same electronic ingress edge router  105  and electronic egress edge routers  115 , thus creating an equi-coverage multicast tree. Therefore, all of the multicast data packets associated with the first and second multicast trees, T 1    305  and T 2    310 , can be grouped in a multicast burstification class. The multicast data packets can then be assembled into a single multicast burst with one set of overhead at the electronic ingress edge router  105  and switched through the optical burst-switched network  100  on either the first multicast tree T 1    305  or the second multicast tree T 2    310 . The single multicast burst can then be disassembled back into the multicast data packets at the electronic egress edge routers E 4  and E 8    115  and transmitted to the output subnets  130 . 
     In ECON, load balancing can be used to determine which multicast tree to send the single multicast burst on. For example, one load balancing technique may be to alternate the multicast trees T 1    305  and T 2    310  evenly for sending multicast bursts. In another example, the total multicast traffic may be unevenly distributed in an alternating nature among multicast trees. Other load balancing techniques known to those skilled in the art may also be used. The load balancing decisions occur in the electronic ingress edge router  105 . 
     FIG. 4 shows an example of the third multicast burstification class called super-coverage in an optical burst-switched network (SCON)  400 . The SCON  400  or FIG. 4 includes one electronic ingress edge router  105 , a plurality of optical core routers  110 , a plurality of electronic egress edge routers  115 , a plurality of DWDM links  120 , a first multicast tree T 1    405 , and a second multicast tree T 2    410 . In this scenario, the multicast trees associated with a multicast burstification class may not share the same electronic egress edge routers  115 , DWDM links  120 , or optical core routers  110 , however, at least one of the multicast trees (called a super tree) covers the ingress edge router  105  and all the electronic egress edge routers  115  shared by all the multicast trees combined. The difference in the number of electronic egress edge routers  115 , DWDM links  120 , or optical core routers  110  between the super tree and each multicast trees should not be larger than some predetermined threshold value. 
     In one embodiment of SCON, all of the multicast data packets associated with the first multicast tree T 1    405  would be assembled in a multicast burst at the electronic ingress edge router  105  and switched through the optical burst switched network  100  to the electronic egress edge routers E 4  and E 8    115 . Similarly, all of the multicast data packets associated with the second multicast tree T 2    410  would be assembled in a multicast burst at the electronic ingress edge router  105  and switched through the optical burst-switched network  100  to the electronic egress edge routers E 3 , E 4 , and E 8    115 . Finally the multicast bursts switched on the multicast tree T 1    405  would be disassembled at the electronic egress edge routers E 4  and E 8    115  and transmitted to their respective subnets  130 . Similarly, the multicast bursts switched on the multicast tree T 2    410  would be disassembled at the electronic egress edge routers E 3 , E 4  and E 8    115  and transmitted to their respective destination subnets  130 . 
     Again, the problem with assembling the multicast data packets into two separate bursts at the same electronic ingress edge router  105  and transmitting the two multicast bursts to at least some of the same electronic egress edge routers  115  is that the same overhead is used for some of the multicast bursts. Since each multicast burst must be assembled in a given time interval and the volume of the multicast traffic is relatively small, it is unlikely that enough multicast data packets will be assembled in short time intervals. In another embodiment of SCON, where there is at least one multicast tree (called a super tree) which covers the electronic ingress edge router  105  and all the electronic egress edge routers  115  covered by all of the multicast trees combined, the multicast packets can be assembled into a single multicast burst with one set of overhead and transmitted on the super tree to all of the electronic egress edge routers  115 . Therefore, it is more likely that more multicast data packets can be assembled in the same time interval, thus making multicast data packet switching more efficient. 
     In FIG. 4, note that the first multicast tree T 1    405  and the second multicast tree T 2    410  do not share the same electronic egress edge routers  115 . However, multicast tree T 2    410  covers all the electronic egress edge routers  115  covered by the first and second multicast trees combined (T 1    405  and T 2    410 ) thus creating a super-coverage multicast tree. Therefore, all of the multicast data packets associated with the first and second multicast trees (T 1    405  and T 2    410 ) can be assembled into a single multicast burst with one set of overhead at the electronic ingress edge router  105  and switched through the optical burst-switched network  100  on the super tree. In FIG. 4, the super tree is the second multicast tree T 2    410 . The multicast burst can then be disassembled back into multicast data packets at the electronic egress edge routers E 3 , E 4  and E 8    115  and transmitted to the respective output subnets  130 . Note also that the multicast data packets associated with multicast tree T 1    405  are discarded at electronic egress edge router E 3    115 . 
     In SCON scenario, some criteria are required in constructing a SCON multicast burstification class. These criteria expect to ensure the overall delivery efficiency of multicast data packets in the optical burst switched network when using shared multicast entities concept. In one embodiment, a maximum threshold limit can be set on the difference in the number of DWDM links  120 , optical core routers  110 , and the electronic egress edge routers  115  that are allowed between the super tree and the other multicast trees in the MBC. A network administrator can set these maximum threshold limits. The electronic ingress edge router  105  compares the super tree to each individual multicast tree to make sure these maximum threshold limits are not violated. The following three inequalities can be used to establish a multicast burstification class with various threshold values for the DWDM links  120 , the optical core routers  110 , and the ingress and egress edge routers  105  and  115 :                    E   jk     ⊆       E   j   s                   for                 all                 k       =   1     ,   2   ,   …              ,     R   j                                      E   j   s     -         ⋂   i       R   j            E   ji              ≤     h   E             (   1   )                            C   j   s     -         ⋃   i       R   j            C   ji              +                ⋃   i       R   j            C   ji       -     C   j   s              ≤     h   C       ,           (   2   )                          L   j   s     -         ⋃   i       R   j            L   ji              +                ⋃   i       R   j            L   ji       -     L   j   s              ≤       h   L     .             (   3   )                         
     Where h C , h E  and h L  are the thresholds for the optical core routers C, electronic ingress and egress edge routers E and DWDM links L, respectively. Note that |Y| is the cardinality of set Y. 
     Equation one (1) defines the SCON classification and controls the trade-off between burstification efficiency and processing overhead on some edge routers. Equations two (2) and three (3) are related to the average performance of multicast burst delivery. Equations two (2) and three (3) control the tradeoff between system level burstification and overall multicast traffic efficiency. 
     In another embodiment, the Classification Efficiency Ratio, denoted by CER, is used, which gives the ratio of the accumulated cost of delivering multicast traffic of the individual multicast sessions via their multicast trees to the total cost of delivering multicast traffic of the MBC via the super tree. Again, let us assume there are N multicast burstification classes (MBC) at an electronic ingress edge router and the j th  multicast burstification class, MBC j , has R j  multicast trees. The multicast traffic volume of the k th  multicast group in the same MBC j  is D jk , where k=1,2, . . . , R j , and the cost of delivering a unit traffic volume on tree T jk  is S jk . Further, the cost of delivering a unit traffic volume on super tree T j   S  is S j   S . The following inequality can be used to establish SCON class MBC j  for an electronic ingress edge router.                CER   j     =           ∑     k   =   1       R   j                         D   jk          S   jk             S   j   s            ∑     k   =   1       R   j                       D   jk           ≥     h   R               (   4   )                         
     The h R (≧1) is a predefined value. For inequality (4), in one embodiment, S jk  the sum of DWDM links in tree T jk , and S j   S  is the sum of DWDM links in the super tree. In another embodiment, S jk  and S j   S  are the weighted sum of DWDM links in tree T jk  and the super tree T j   S , respectively. DWDM link length can for example be used as the weight in calculating the cost. FIG. 5 shows another example of super-coverage in an optical burst-switched network (SCON)  500  according to the present invention. In FIG. 5, the multicast tree T 2    510  is the super tree since it shares the same electronic ingress and egress edge routers as all of the multicast trees combined. Note that the example in FIG. 5 has more overhead than the example shown in FIG.  4 . Also note that for ETON, h C =h E =h L =0 and for ECON, h E =0. 
     FIG. 6 shows one example of overlapping-coverage in an optical burst-switched network (OCON)  600  according to the present invention. The OCON  600  is an extension of SCON  500 . In OCON  600 , the multicast trees of a multicast burstification class may not share all the egress edge routers  115 , however, a union tree which covers all of the egress edge routers  115  can be created to deliver the assembled multicast burst. As with SCON  500 , the difference between the union tree and multicast trees in terms of the numbers of egress edge routers  115 , DWDM links  120 , and optical core routers  110  should not be larger than some predetermined threshold value. Equations (1), (2), (3), and (4) used under SCON  500  hold for OCON  600 , as well. 
     In one embodiment of OCON  600 , all of the multicast data packets associated with the first multicast tree T 1    605  could be assembled in a multicast burst at the electronic ingress edge router  105  and switched through the optical burst switched network  100  to the electronic egress edge routers E 4 , E 8  and E 9 . Similarly, all of the multicast data packets associated with the second multicast tree T 2    610  could be assembled in a multicast burst at the electronic ingress edge router  105  and switched through the optical burst switched network to the electronic egress edge routers E 3 , E 4  and E 8 . Finally the multicast bursts switched on the multicast tree T 1    605  would then be disassembled at the electronic egress edge routers E 4 , E 8  and E 9  and transmitted to their respective subnets  130 . Similarly, the multicast bursts switched on the multicast tree T 2    610  would be disassembled at the electronic egress edge routers E 3 , E 4  and E 8  and transmitted to their respective destination subnets  130 . 
     Again, the problem with assembling the multicast data packets into two separate bursts at the same electronic ingress edge router  105  and transmitting the two multicast bursts to some of the same electronic egress edge routers  115  is that the same overhead is used for some of the multicast bursts. Since each multicast burst must be assembled in a given time interval and the traffic volume of a single multicast group is not very big, it is unlikely that enough multicast data packets can be assembled in a short interval. In another embodiment of OCON  600 , where none of the multicast trees of a multicast burstification class cover all the ingress and egress edge routers,  105  and  115  respectively, a union tree which covers all of the ingress and egress edge routers,  105  and  115  respectively, can be created to deliver multicast bursts to all of the egress edge routers  105  and  115 . Therefore, a single multicast burst with one set of overhead can be assembled and transmitted on the union tree. Thus, it is more likely that more multicast data packets can be assembled in the same time interval, thus making multicast data packet switching more efficient. 
     In FIG. 6 note that the first multicast tree T 1    605  and the second multicast tree T 2    610  do not share the same electronic egress edge routers  115 , however, the combination of multicast trees T 1    605  and T 2    610  covers all the electronic egress edge routers  115 , thus creating an overlapping-coverage multicast tree. Therefore, all of the multicast data packets from the first and second multicast tree can be assembled into a single multicast burst with one set of overhead at the electronic ingress edge router  105  and switched through the optical burst-switched network  100  on the newly formed overlapping-coverage multicast tree. The multicast burst can then be disassembled back into the multicast data packets at the electronic egress edge routers E 3 , E 4  and E 8 , and E 9    115  and transmitted to the respective output subnets  130 . The trade off with OCON in FIG. 6 is that the electronic egress edge routers E 3  and E 9   115  will need to discard some of the multicast data packets they receive. 
     For an efficient implementation of multicast burstification class (MBC) search, we propose data structures for ETON, ECON, SCON, and OCON cases. FIG. 7 depicts the data structure  700  for the ETON case where the LinkArray is an array of pointers to the corresponding EdgeArray for the MBCs having the same number of links in their trees. This number is represented by the index of the array. For example, LinkArray[i] contains a pointer relating all the MBCs having i number of links in their trees. This pointer points to another array of pointers which point to actual MBCs having the same number of edge routers in their trees. For example, EdgeArray i [j], likewise, points to a linked list of MBCs which have i number of links and j number of edge routers in their trees. Each MBC has a list of multicast trees (MTs) that belong to the MBC. The data structure  800  for the ECON, SCON, and OCON cases, given in FIG. 8, contains only one EdgeArray pointing to the lists of MBCs having the same number of edge routers in their representative trees regardless of the set of links. 
     FIG. 9 depicts the data structure  900  of the MBC for all cases. The structure has a pointer to a linked list of all the MTs (“pointer to MTs” in FIG. 9) that belong to this MBC. It maintains an information for the representative tree (“Representative MT” in FIG. 9) of the MBC by a pointer to a MT. It also maintains current difference (“CurrentE” in FIG. 9) between the representative tree and the smallest tree in edge, link, and core counts, respectively. It has pointers to shared edge routers (“EdgeRouter Set” in FIG.  9 ), links (“Link Set” in FIG.  9 ), and core routers (“CoreRouter Set” in FIG.  9 ), respectively. Furthermore, it has two pointers, “prev” and “next” in FIG. 9, to link the structure to a doubly linked list. 
     FIG. 10, shows the data structure  1000  of the MT for all cases. The data structure  1000  has pointers to lists of edge routers, core routers, and links that it utilizes. These lists are in order (e.g. ascending order of IDs). The structure keeps track of the numbers of edge routers, core routers and links. This information is used for direct access in the search process for addition and deletion of a MT. Every MT has LinkSet, EdgeSet, and CoreSet values. The purpose of using LinkSet, EdgeSet and CoreSet values is to further narrow down the search for a MT. Note that some of the content in in the generic data structure for any MT could be empty. 
     The purpose of using LinkSet, EdgeSet and CoreSet values are to further narrow down the search for a MT. Following are two implementations: (1) all the functions are injection where if a≠b implies f(a)≠f(b) and (2) at least one is non-injection. Using injection functions can greatly simplify the MT search as it provides a unique relationship between a set and its set value. Obtaining an injection function constitutes another problem. Note that some of the content in in the generic data structure for any MT could be empty if the related information is not available in some scenarios. 
     Management of the four burstification classes is another task. Management of the four burstification classes includes two basic operations: addition and deletion of a multicast group to and from a multicast burstification class. The electronic ingress edge routers  105  run a separate algorithm for the addition and deletion of multicast groups to and from a multicast burstification class. A high level generic description for the two algorithms are shown below. In each of the two high level generic algorithms, X=ETON, ECON, SCON, or OCON. The multicast tree subject to each of the algorithms is T*. 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 1. Addition: 
               
               
                   
                  algorithm X_addition(T*) 
               
               
                   
                   Search for the X MBC; 
               
               
                   
                   if there exists MBC j  which satisfies the X definition; 
               
               
                   
                    MBC j  ← MBC j  U T*; 
               
               
                   
                   else 
               
               
                   
                    MBC k  ← create a new MBC; 
               
               
                   
                   MBC k  ← T*; 
               
               
                   
                  end_algorithm 
               
               
                   
                 2. Deletion: 
               
               
                   
                  algorithm X_deletion(T*) 
               
               
                   
                   find MBC j  which contains T*; 
               
               
                   
                    MBC j  ← MBC j  − T*; 
               
               
                   
                    if MBC j  = Ø then terminate MBC j;   
               
               
                   
                  end_algorithm 
               
               
                   
                   
               
            
           
         
       
     
     A more detailed description of particular embodiments of the algorithms for the addition of a multicast tree into a multicast burstification class and the deletion of a multicast tree from a multicast burstification class are shown below. For a changed multicast group which no longer satisfies the definition of the multicast burstification class it belongs to, both deletion and addition operations are required which delete the multicast group from the current multicast burstification class and add it to a new multicast burstification class. 
     ETON Procedures 
     For the addition, the procedure ETON_addition, given below, is invoked. The procedure directly accesses the list of multicast burstification classes (MBCs) that have the same number of links and edge routers in their representative multicast trees (MTs) and finds the MBC whose representative MT shares exactly the same multicast tree. If the functions are injection functions then the sequential search is done by only comparing the set values. When the correct MBC is located, the MT is added to it, otherwise, anew MBC is created and initialized with the MT. The procedure ETON_addition is listed below. 
     
       
         
           
               
             
               
                   
               
             
            
               
                 procedure ETON_addition(MT i ) 
               
               
                 EdgeArray ← LinkArray[MT i .Num_of_Links] ; 
               
               
                 MBC_ptr ← EdgeArray[MT i .Num_of_Edges] ; 
               
               
                 if (MBC_ptr≠Null) /*there exists at least one MBC in 
               
               
                 the system */ 
               
               
                 while(MBC_ptr≠ Null and 
               
               
                 MBC_ptr.Representative_MT.LinkSet_value←MT i .LinkSet_value 
               
               
                 or 
               
               
                   MBC_ptr.Representative_MT.Edgeset_value ≠ MT i. EdgeSet_value 
               
               
                  or 
               
               
                   MBC_ptr.Representative_MT.CoreSet_value ≠ MT i .Core- 
               
               
                   Set_value) 
               
               
                    oldMBC_ptr ← MBC_ptr ; 
               
               
                    MBC_ptr ← MBC_ptr.next ; 
               
               
                  end_while 
               
               
                  if (MBC_ptr ≠ Null) 
               
               
                   Insert(MBC_ptr,MT i ) ; 
               
               
                   Return ; 
               
               
                  end_if 
               
               
                 end_if 
               
               
                 MBC_ptr ← create(MBC) ; 
               
               
                 MBC_ptr. Representative_MT ← MT i  ; 
               
               
                 Add1(MBC_ptr) ; 
               
               
                 Return; 
               
               
                 end_procedure 
               
               
                   
               
            
           
         
       
     
     Insert and Add1 subprocedures are given below. The Insert subprocedure inserts a multicast tree into a Multicast Burstification Class. 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 procedure Insert (MBCptr,MT) 
               
            
           
           
               
               
            
               
                   
                 MT.next ← MBC_ptr.ptr_to_MT; 
               
               
                   
                 MT.prev ← Null; 
               
               
                   
                 if (MBC_ptr.ptr_to_MT ≠ Null) MBC_ptr. 
               
               
                   
                 ptr_to_MT.prev ← MT; 
               
               
                   
                 MBC_ptr.ptr_to_MT← MT i  ; 
               
               
                   
                 MT i .MBC ← MBC_ptr ; 
               
            
           
           
               
            
               
                 end_procedure 
               
               
                   
               
            
           
         
       
     
     The Add1 subprocedure adds the MBC into the lists according to the representative tree&#39;s edge router and link counts. 
     
       
         
           
               
             
               
                   
               
             
            
               
                 procedure Add1 (MBC_ptr) 
               
               
                 MBC_ptr.next←Null ; 
               
               
                 EdgeArray ← LinkArray[MBC_ptr.Representative_MT.Num_of —   
               
               
                 Links] ; 
               
               
                 MBC_ptr.next ← 
               
               
                  EdgeArray [MBC_ptr.Representative_MT.Num_of_Edges]; 
               
               
                 if (EdgeArray[MBC_ptr.Representative_MT.Num_of_Edges] ≠ Null) 
               
               
                  EdgeArray[MBC_ptr.Representative_MT.Num_of_Edges] .prev ← 
               
               
                  MBC_ptr ; 
               
               
                 EdgeArray[MBC_ptr.Representative_MT.Num_of_Edges] ← 
               
               
                  MBC_ptr; 
               
               
                 end_procedure 
               
               
                   
               
            
           
         
       
     
     For the deletion of a MT from its MBC, the procedure ETON deletion, given below, is invoked. The procedure directly accesses the MT in the corresponding MBC&#39;s MT list and deletes the MT from the list if the MT is not the representative tree of the MBC. If the MT is the representative tree and there are some other member trees in the MBC then another member tree substitutes the representative tree due to the equivalence of the member trees and the representative tree. If there are no other member trees in the MBC, then the MBC is terminated from the system&#39;s MBC list. The procedure ETON_deletion is listed below. 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 procedure ETON_deletion(MT i ) 
               
               
                   
                 if (MT.MBC.Representative_MT = MT i ) 
               
               
                   
                  if (MT.MBC.ptr_to_MT = Null) 
               
               
                   
                   if (MT i .MBC.prev = Null) 
               
               
                   
                    if (MT i .MBC.next = Null) 
               
               
                   
                     EdgeArray[MT i .Num_of_Edges] ← Null ; 
               
               
                   
                    else 
               
               
                   
                     EdgeArray[MT i .Num_of_Edges]← MT i .MBC.next ; 
               
               
                   
                     MT i .MBC.next.prev ← Null ; 
               
               
                   
                    end_if 
               
               
                   
                   else 
               
               
                   
                    if (MT i .MBC.next = Null) 
               
               
                   
                     MT i .MBC.prev.next ← Null ; 
               
               
                   
                    else 
               
               
                   
                     MT i .MBC.prev.next ← MT i .MBC.next ; 
               
               
                   
                     MT i .MBC.next.prev ← MT i .MBC.prev ; 
               
               
                   
                    end_if 
               
               
                   
                   end_if 
               
               
                   
                  else 
               
               
                   
                   MT2 ← MT.MBC.ptr_to_MT ; 
               
               
                   
                   MT.MBC.Representative_MT ← MT2 ; 
               
               
                   
                   MT2.next.prev ← Null ; 
               
               
                   
                   MT.MBC.ptr_to_MT ← MT2.next ; 
               
               
                   
                  end_if 
               
               
                   
                 else 
               
               
                   
                  if (MT i .prev = Null) 
               
               
                   
                   if (MT i .next = Null) 
               
               
                   
                    MT i .MBC.ptr_to_MT ← Null) 
               
               
                   
                   else 
               
               
                   
                    MT i .MBC.MT ← MT i .next ; 
               
               
                   
                    MT i .next.prev ← Null ; 
               
               
                   
                   end_if 
               
               
                   
                  else 
               
               
                   
                   if (MT i .next = Null) 
               
               
                   
                    MT i .prev.next ← Null ; 
               
               
                   
                   else 
               
               
                   
                    MT i .prev.next ← MT i .next ; 
               
               
                   
                    MT i .next.prev ← MT i .prev ; 
               
               
                   
                   end_if 
               
               
                   
                  end_if 
               
               
                   
                 end_if 
               
               
                   
                 end_procedure 
               
               
                   
                   
               
            
           
         
       
     
     If the functions are not injections then we introduce a function, called Equi-set, in order to check the equivalence of two links and/or edge sets since the function value does not uniquely specify a link and/or edge set. The function equi_set is shown below. 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 function Equi_set(A,B,n) 
               
               
                   
                  for i← 1 to n 
               
               
                   
                   if A.ID ≠ B.ID return(FALSE) ; 
               
               
                   
                   A ← A.next ; 
               
               
                   
                   B ← B.next ; 
               
               
                   
                  end_for 
               
               
                   
                  return (TRUE); 
               
               
                   
                 end_function 
               
               
                   
                   
               
            
           
         
       
     
     Therefore, the addition procedure needs to be changed in the case of a non-injection function as follows: 
     
       
         
           
               
             
               
                   
               
             
            
               
                 procedure ETON_addition2(MT i ) 
               
               
                 EdgeArray ← LinkArray[MT i .Num_of_Links]; 
               
               
                 MBC_ptr ← EdgeArray[MT i .Num_of_Edges]; 
               
               
                 if (MBC_ptr≠Null) /*there exists at least a MBC in the system */ 
               
               
                  while( MBC_ptr≠ Null and 
               
               
                   MBC_ptr.Representative_MT.LinkSet_value ≠ 
               
               
                 MT i .LinkSet_value or 
               
               
                   MBC_ptr.Representative_MT EdgeSet_value ≠ MT i   
               
               
                 EdgeSet_value or 
               
               
                   MBC_ptr.Representative_MT CoreSet_value ≠ MT i   
               
               
                 CoreSet_value or 
               
               
                   Equi_set(MBC_ptr.Representative_MT.ptr_to_Links, 
               
               
                    MT i .ptr_to_Links,MT i .num_of_Links) or 
               
               
                   Equi_set(MBC_ptr.Representative_MT.ptr_to_EdgeRouter, 
               
               
                    MT i .ptr_to_EdgeRouter,num_of_Edge_R)) 
               
               
                   oldMBC_ptr ← MBC_ptr; 
               
               
                   MBC_ptr. ← MBC_ptr.next; 
               
               
                  end_while 
               
               
                  if (MBC_ptr ≠ Null) 
               
               
                   Insert(MBC_ptr,MT i ) ; 
               
               
                   return; 
               
               
                  end_if 
               
               
                 end_if 
               
               
                 MBC_ptr ← create(MBC); 
               
               
                 MBC_ptr. Representative_MT ← MT i  ; 
               
               
                 Add1(MBC_ptr) ; 
               
               
                 return; 
               
               
                 end_procedure 
               
               
                   
               
            
           
         
       
     
     ECON Procedures 
     For the addition of a MT, the procedure ECON_addition, given below, is invoked. The procedure directly accesses the list of MBCs that have the same number of edge routers in their MTs and sequentially searches for the MBC whose MTs have exactly the same edge router coverage. If the functions are injection functions then the sequential search is done by only comparing the set values. When the correct MBC is located, the MT is added to it, otherwise, a new MBC is created and initialized with the MT. The deletion procedure is the same as ETON case. 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 procedure ECON_addition(MT i ) 
               
               
                   
                 MBC_ptr ← EdgeArray[MT i .Num_of_Edges]; 
               
               
                   
                 if (MBC_ptr≠Null) /*there exists at least a MBC in the 
               
               
                   
                 system */ 
               
               
                   
                  while(MBC_ptr≠ Null and 
               
               
                   
                   MBC_ptr.Representative_MT.Edgeset_value≠MT i   
               
               
                   
                   EdgeSet_value ) 
               
               
                   
                   oldMBC_ptr ← MBC_ptr; 
               
               
                   
                   MBC_ptr. ← MBC_ptr.next; 
               
               
                   
                  end_while 
               
               
                   
                  if (MBC_ptr ≠ Null) 
               
               
                   
                   Insert(MBC_ptr,MT i ) ; 
               
               
                   
                   return ; 
               
               
                   
                  end_if 
               
               
                   
                 end_if 
               
               
                   
                 MBC_ptr ← create(MBC) ; 
               
               
                   
                 MBC_ptr. Representative_MT ← MT i  ; 
               
               
                   
                 Add1(MBC_ptr) ; 
               
               
                   
                 return; 
               
               
                   
                 end_procedure 
               
               
                   
                   
               
            
           
         
       
     
     For the non-injection function case, the ECON_addition2 procedure replaces the ECON_addition. 
     
       
         
           
               
             
               
                   
               
             
            
               
                 procedure ECON_addition2 (MT i ) 
               
               
                 MBC_ptr ← EdgeArray[MT i .Num_of_Edges] 
               
               
                 if (MBC_ptr≠Null) /*there exists at least a MBC in the system */ 
               
               
                  while( MBC_ptr≠ Null and 
               
               
                   MBC_ptr.Representative_MT EdgeSet_value ≠ 
               
               
                 MT i .EdgeSet_value or 
               
               
                   Equi_set(MBC_ptr. Representative_MT.ptr_to_EdgeRouter, 
               
               
                   MT i .ptr_to_EdgeRouter,num_of_Edge_R)) 
               
               
                    oldMBC_ptr ← MBC_ptr; 
               
               
                    MBC_ptr. ← MBC_ptr.next; 
               
               
                  end_while 
               
               
                  if (MBC_ptr ≠ Null) 
               
               
                   Insert(MBC_ptr,MT i ) ; 
               
               
                   return; 
               
               
                  end_if 
               
               
                 end_if 
               
               
                 MBC_ptr ← create(MBC); 
               
               
                 MBC_ptr. Representative_MT ← MT i  ; 
               
               
                 Add1(MBC_ptr) ; 
               
               
                 return; 
               
               
                 end_procedure 
               
               
                   
               
            
           
         
       
     
     Deletion for ECON is exactly the same as the one for ETON case. 
     SCON Procedures 
     For the SCON case, the addition procedure searches for a MBC within the previously mentioned threshold values. Note that while h E  is the threshold for the optical edge routers, h E  is discussed in terms of “distance” with respect to FIG. 11 to visualize better the concepts related to the number of optical edge routers for the SCON case. It starts the search with the MBC which has the same number of edge routers. It then continues searching in both directions alternatively for distance h E  in an incremental manner as shown in FIG.  11 . Therefore, it maintains shared edge routers and all links and core routers. It also keeps track of the current distance from the super tree in terms of edge router count. 
     
       
         
           
               
             
               
                   
               
             
            
               
                 p← 1 ; 
               
               
                 for i← 0 to h E   
               
               
                  j← 1 ; 
               
               
                  MBC_ptr ← EdgeArray[MT i .Num_of_Edges+p*i] ; 
               
               
                  while ( j=1 or (j=2 and i &lt; h E −MBC_ptr.CurrentE)) 
               
               
                   while ( MBC_ptr≠ Null and 
               
               
                   { p≠1 or 
               
               
                   !Subset (MBC_ptr.Representative_MT.ptr_to_EdgeRouters, 
               
               
                 MT i .ptr_to_EdgeRouters) or 
               
               
                   E ← (MBC_ptr. Representative_MT. Num_of_Edges − 
               
               
                    Cardinality(Intersectset(MBC_ptr.EdgeRouterSet, 
               
               
                 MT i .ptr_to_EdgeRouters)) &gt; h E  or 
               
               
                   [Cardinality(Diffset(MBC_ptr.Representative_MT.ptr_to_Links, 
               
               
                    Unionset(MBC_ptr.LinkSet, MT i .ptr_to_Links))) + 
               
               
                   Cardinality(Diffset (Unionset(MBC_ptr.LinkSet, 
               
               
                 MT i .ptr_to_Links), 
               
               
                    MBC_ptr. Representative_MT.ptr_to_Links ))] &gt; h L  or 
               
               
                  [Cardinality(Diffset(MBC_ptr. 
               
               
                 Representative_MT i .ptr_to_CoreRouters, 
               
               
                    Unionset(MBC_ptr.AllCoreRouters, 
               
               
                 MT i .ptr_to_CoreRouters))) + 
               
               
                  Cardinality(Diffset(Unionset(MBC_ptr.AllCoreRouters, 
               
               
                 MT i .ptr_to_CoreRouters), 
               
               
                    MBC_ptr. Representative_MT.ptr_to_CoreRouters ))] &gt; 
               
               
                 h C } 
               
               
                 and 
               
               
                 { p≠−1 or 
               
               
                  !Subset(MT i .ptr_to_EdgeRouters ,MBC_ptr. 
               
               
                 Representative_MT.ptr_to_EdgeRouters) or 
               
               
                  E ← (MT i . Num_of_Edges − Cardinality(MBC_ptr.EdgeRouterSet) &gt; 
               
               
                 h E  or 
               
               
                  [Cardinality(Diffset(MT i . ptr_to_Links, 
               
               
                    Unionset(MBC_ptr.Linkset, 
               
               
                 MBC_ptr.Representative_MT.ptr_to_Links))) + 
               
               
                  Cardinality(Diffset(Unionset(MBC_ptr.LinkSet, 
               
               
                 MBC_ptr.Representative_MT.ptr_to_Links), 
               
               
                    MT i .ptr_to_Links ))] &gt; h L  or 
               
               
                  (Cardinality(Diffset(MT i .ptr_to_CoreRouters, 
               
               
                 Unionset(MBC_ptr.CoreRouterSet,MBC_ptr.Representative —   
               
               
                 MT.ptr_to_CoreRouters))) + 
               
               
                  Cardinalty(Diffset(Unionset(MBC_ptr.CoreRouterSet, 
               
               
                    MBC_ptr.Representative_MT.ptr_to_CoreRouters), 
               
               
                 MT i .ptr_to_CoreRouters ))] &gt; h C   
               
               
                   } 
               
               
                 oldMBC_ptr ← MBC_ptr ; 
               
               
                     MBC_ptr. ← MBC_ptr.next ; 
               
               
                 end_while 
               
               
                 if (MBC_ptr ≠ Null) 
               
               
                 if (p=−1) 
               
               
                      Insert(MBC_ptr, MBC_ptr. Representative_MT) ; 
               
               
                    MBC_ptr. Representative_MT ← MT i ; 
               
               
                    MBC_ptr.LinkSet←Unionset(MBC_ptr.LinkSet, 
               
               
                 MBC_ptr.Representative_MT i .ptr_to_Links) ; 
               
               
                    MBC_ptr.CoreRouterSet←Unionset(MBC_ptr.CoreRouterSet, 
               
               
                 MBC_ptr.Representative_MT.ptr_to_CoreRouters) ; 
               
               
                      Remove(MBC_ptr) ; 
               
               
                      Add1(MBC_ptr) ; 
               
               
                   else /* p =1 */ 
               
               
                    MBC_ptr.LinkSet←Unionset(MBC_ptr.LinksSet, 
               
               
                 MT i .ptr_to_Links) ; 
               
               
                    MBC_ptr.CoreRouterSet←Unionset(MBC_ptr.CoreRouterSet, 
               
               
                 MT i .ptr_to_CoreRouters) ; 
               
               
                      Insert(MBC_ptr, MT i ) ; 
               
               
                     MBC_ptr.EdgeRouterSet ← 
               
               
                 Intersectset(MBC_ptr.EdgeRouterSet,MT i .ptr_to_EdgeRouters ; 
               
               
                 end_if /* if p=1) */ 
               
               
                 if (E &gt; MBC_ptr.CurrentE ) MBC_ptr.CurrentE ← E ; 
               
               
                 return; 
               
               
                 end_if 
               
               
                 p=p* (−1) ; 
               
               
                 j←j+1; 
               
               
                 end_while 
               
               
                 end_for 
               
               
                 MBC_ptr ← Create(MBC) ; 
               
               
                 MBC_ptr.Representative_MT ← MT i   
               
               
                 MBC_ptr.CurrentE ← 0 ; 
               
               
                 MBC_ptr.EdgeRouterSet ← MT i .ptr_to_EdgeRouters ; 
               
               
                 MBC_ptr.LinkSet ← Ø ; 
               
               
                 MBC_ptr. CoreRouterSet ← Ø ; 
               
               
                 Add1(MBC_ptr) ; 
               
               
                 return; 
               
               
                 end_procedure 
               
               
                   
               
            
           
         
       
     
     The Remove procedure removes the MBC from its corresponding list. 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 procedure Remove(MBC_ptr) 
               
               
                   
                 if (MT i .MBC.prev = Null) 
               
               
                   
                  if (MT i .MBC.next = Null) 
               
               
                   
                   EdgeArray[MT i .Num_of_Edges] ← Null ; 
               
               
                   
                  else 
               
               
                   
                   EdgeArray[MT i .Num_of_Edges] ← MT i .MBC.next ; 
               
               
                   
                   MT i .MBC.next.prev ← Null ; 
               
               
                   
                  end_if 
               
               
                   
                 else 
               
               
                   
                  if (MT i .MBC.next = Null) 
               
               
                   
                   MT i .MBC.prev.next ← Null ; 
               
               
                   
                  else 
               
               
                   
                   MT i .MBC.prev.next ← MT i .MBC.next ; 
               
               
                   
                   MT i .MBC.next.prev ← MT i .MBC.prev ; 
               
               
                   
                  end_if 
               
               
                   
                 end_if 
               
               
                   
                 end_procedure 
               
               
                   
                   
               
            
           
         
       
     
     For the deletion of a MT from its MBC, the procedure SCON_deletion, given below, is invoked. The procedure directly accesses to the MT in the corresponding MBC&#39;s MT list and deletes the MT from the list if the MT is not the representative tree of the MBC. If the MT is the representative tree then the MBC is terminated from the system&#39;s MBC list. If the MBC includes any MT, these are re-accommodated in the system by being modified individually. 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 procedure SCON_deletion(MT i ) 
               
               
                   
                 if (MT i .MBC.Representative_MT = MT i ) 
               
               
                   
                  if (MT i .MBC.ptr_to_MT ≠ Null) 
               
               
                   
                   while(MT_ptr ≠ Null) 
               
               
                   
                    Modify(MT_ptr) ; 
               
               
                   
                    MT_ptr ← MT_ptr.next ; 
               
               
                   
                   end_while 
               
               
                   
                  end_if 
               
               
                   
                  if (MT i .MBC.prev = Null) 
               
               
                   
                   if (MT i .MBC.next = Null) 
               
               
                   
                   EdgeArray[MT i .Num_of_Edges] ← Null ; 
               
               
                   
                   else 
               
               
                   
                    EdgeArray[MT i .Num_of_Edges] ← MT i .MBC.next ; 
               
               
                   
                    MT i .MBC.next.prev ← Null ; 
               
               
                   
                   end_if 
               
               
                   
                  else 
               
               
                   
                   if (MT i .MBC.next = Null) 
               
               
                   
                    MT i .MBC.prev.next ← Null ; 
               
               
                   
                   else 
               
               
                   
                    MT i .MBC.prev.next ← MT i .MBC.next ; 
               
               
                   
                    MT i .MBC.next.prev ← MT i .MBC.prev ; 
               
               
                   
                   end_if 
               
               
                   
                  end_if 
               
               
                   
                 else 
               
               
                   
                  if (MT i .prev = Null) 
               
               
                   
                   if (MT i .next = Null) 
               
               
                   
                    MT i .MBC.ptr_to_MT ← Null) 
               
               
                   
                   else 
               
               
                   
                    MT i .MBC.MT ← MT i .next ; 
               
               
                   
                    MT i .next.prev ← Null ; 
               
               
                   
                   end_if 
               
               
                   
                  else 
               
               
                   
                   if (MT i .next = Null) 
               
               
                   
                    MT i .prev.next ← Null ; 
               
               
                   
                   else 
               
               
                   
                    MT i .prev.next ← MT i .next ; 
               
               
                   
                    MT i .next.prev ← MT i .prev ; 
               
               
                   
                   end_if 
               
               
                   
                  end_if 
               
               
                   
                 end_if 
               
               
                   
                 end_procedure 
               
               
                   
                   
               
            
           
         
       
     
     OCON Procedures 
     For OCON case, a union tree is formed by observing the threshold values. Edge array for direct access is maintained according to the size of the edge router count of the representative tree. All the processes are similar to the SCON case, however, a new representative tree called union tree needs to be formed by merging the MT into the previous representative tree. This merging is done by two approaches. These are Breadth-First-Merge and Incremental-Merge. 
     
       
         
           
               
             
               
                   
               
             
            
               
                 procedure OCON_addition(MT i ) 
               
               
                 p← 1 ; 
               
               
                 for i← 0 to h E   
               
               
                  j← 1 ; 
               
               
                 while ( j=1 or (j=2 and i &lt; h E -MBC_ptr.CurrentE)) 
               
               
                  MBC_ptr ← EdgeArray[MT i .Num_of_Edges+p*i] ; 
               
               
                  MT2 ← Breadth-First_Merge(MBC_ptr. Representative_MT, MT i ); 
               
               
                  while ( MBC_ptr≠ Null and 
               
               
                   E ← (MT2 . Num_of_Edges - 
               
               
                    Cardinality (Intersectset (MBC_ptr.EdgeRouterSet, 
               
               
                   MT i .ptr_to_EdgeRouters)) &gt; h E  or 
               
               
                    [Cardinality(Diffset(MT2.ptr_to_Links, 
               
               
                     Unionset (MBC_ptr. LinkSet, 
               
               
                    MT i .ptr_to_Links))) + 
               
               
                   Cardinality(Diffset(Unionset(MBC_ptr.LinkSet, 
               
               
                 MT i .ptr_to_Links), 
               
               
                     MT2.ptr_to_Links ))] &gt; h L  or 
               
               
                   [Cardinality(Diffset(MT2.ptr_to_CoreRouters, 
               
               
                     Unionset(MBC_ptr.CoreRouterSet, 
               
               
                    MT i .ptr_to_CoreRouters))) + 
               
               
                   Cardinality(Diffset(Unionset(MBC_ptr.CoreRouterSet, 
               
               
                 MT i .ptr_to_CoreRouters), 
               
               
                     MT2.ptr_to_CoreRouters ))] &gt; h C ) 
               
               
                    oldMBC_ptr ← MBC_ptr ; 
               
               
                    MBC_ptr. ← MBC_ptr.next ; 
               
               
                   end_while 
               
               
                  if (MBC_ptr ≠ Null) 
               
               
                   Insert(MBC_ptr, MT i ) ; 
               
               
                   MBC_ptr. Representative_MT ← MT2 ; 
               
               
                   MBC_ptr.LinkSet←Unionset(MBC_ptr.LinksSet, 
               
               
                 MT i .ptr_to_Links) ; 
               
               
                   MBC_ptr.CoreRouterSet←Unionset(MBC_ptr.CoreRouterSet, 
               
               
                     MT i .ptr_to_CoreRouters) ; 
               
               
                   Remove(MBC_ptr) ; 
               
               
                   Add1(MBC_ptr) ; 
               
               
                   MBC_ptr.EdgeRouterSet ← 
               
               
                  Intersectset(MBC_ptr.EdgeRouterSet,MT i .ptr_to_EdgeRouters ; 
               
               
                 if (E &gt; MBC_ptr.CurrentE )  MBC_ptr.CurrentE ← 
               
               
                 E ; 
               
               
                 return ; 
               
               
                  end_if 
               
               
                  p=p* (−1) ; 
               
               
                  j←j+1; 
               
               
                 end_while 
               
               
                 end_for 
               
               
                 MBC_ptr ← Create(MBC) ; 
               
               
                 MBC_ptr.Representative_MT ← MT i   
               
               
                 MBC_ptr.CurrentE ← 0 ; 
               
               
                 MBC_ptr.EdgeRouterSet ← MT i .ptr_to_EdgeRouters ; 
               
               
                 MBC_ptr.LinkSet ← Ø ; 
               
               
                 MBC_ptr.CoreRouterSet ← Ø ; 
               
               
                 Add1(MBC_ptr) ; 
               
               
                 return; 
               
               
                 end_procedure 
               
               
                   
               
            
           
         
       
     
     The procedure Breadth-First-Merge assumes that both trees&#39; adjacency lists are available. The procedure takes MT 1  as the primary tree and adds the edge routers, core routers, and links of the secondary tree MT 2  which are different than MT 1 &#39;s. 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 procedure Breadth-First-Merge (MT1,MT2) 
               
               
                   
                 for each v which is edge or core router adjacent to MT2 
               
               
                   
                 destination (root) edge router through link 1 
               
               
                   
                  enqueue(Q,{v,1}) ; 
               
               
                   
                 while (Q≠Null) 
               
               
                   
                  {v,1} dequeue(Q) ; 
               
               
                   
                  if v ∉ edge or core router of MT1 
               
               
                   
                   include {v,1} to MT1 ; 
               
               
                   
                  for each y which is edge or core router adjacent to v 
               
               
                   
                 through link k 
               
               
                   
                   enqueue(Q,{y,k}) ; 
               
               
                   
                 end_while 
               
               
                   
                 end_procedure 
               
               
                   
                   
               
            
           
         
       
     
     FIG. 12 shows an example  1200  of the Breadth-first-merge procedure. There are two trees, primary tree MT 1  and the secondary tree MT 2 , in FIG.  12 . Starting from the secondary tree&#39;s root E 1 , the procedure maintains a queue, denoted by Q, of pairs each of which has an edge/core router and the corresponding link. The procedure dequeues an item (v,l) from Q and checks if v is included in the primary tree. If it is not included then it is connected to the primary tree with the link. The adjacent edge/core routers of v are enqueued in the Q. 
     The step by step status of the queue is given below: 
     
       
         
           
               
               
               
             
               
                   
                   
               
             
            
               
                   
                 Q(v,1)  C 6 ,L 1   
                 do not include C 6 ,L 1   
               
               
                   
                 Q(v,1)  C 2 ,L 2  ; C 5 ,L 3  ; E 8 ,L 4   
                 do not include C 2 ,L 2   
               
               
                   
                 Q(v,1)  C 5 ,L 3  ; E 8 ,L 4  ; E 2 ,L 5   
                 do not include C 5 ,L 3   
               
               
                   
                 Q(v,1)  E 8 ,L 4  ; E 2 ,L 5  ; C 4 ,L 6  ; E 6 ,L 7   
                 include E 8 ,L 4   
               
               
                   
                 Q(v,1)  E 2 ,L 5  ; C 4 ,L 6  ; E 6 ,L 7   
                 include E 2 ,L 5   
               
               
                   
                 Q(v,1)  C 4 ,L 6  ; E 6 ,L 7   
                 include C 4 ,L 6   
               
               
                   
                 Q(v,1)  E 6 ,L 7  ; E 5 ,L 8   
                 include E 6 ,L 7   
               
               
                   
                 Q(v,1)  E 5 ,L 8   
                 include E 5 ,L 8   
               
               
                   
                 Q(v,1)  Ø 
               
               
                   
                   
               
            
           
         
       
     
     The Incremental merge takes the largest multicast tree in terms of number of members as the master tree and adds the members of the other trees to the master in an incremental manner. The upstream link of an edge or core router means the link that goes up to the root of the multicast tree from the mentioned edge or core router. 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 Procedure Incremental-Merge (MT1,MT2) 
               
               
                   
                 T max ←Max(MT1,MT2); 
               
               
                   
                 T min ←Min(MT1,MT2); 
               
               
                   
                 for each v which is a member edge router of T min  and not contained 
               
               
                   
                 by the edge routers of T max   
               
               
                   
                  1←upsteam link of v in the tree T min ; 
               
               
                   
                  include(v,1) to T max ; 
               
               
                   
                  v←upsteam edge or core router in the tree T min ; 
               
               
                   
                  while(v ∉ edge or core router of MT1) 
               
               
                   
                   1←upsteam link of v in the tree T min ; 
               
               
                   
                   include(v,1) to T max ; 
               
               
                   
                   v←upsteam edge or core router in the tree T min ; 
               
               
                   
                  end-while 
               
               
                   
                 end-for 
               
               
                   
                 end-procedure 
               
               
                   
                   
               
            
           
         
       
     
     The deletion algorithm works similarly to the SCON case. The removal of the representative tree results in the re-organization of all the member trees that the MBC may have. FIG. 13 shows the result  1300  of the merger of the two trees in FIG. 12 after the Breadth-First-Merge procedure has been applied to it. 
     An injection function can be used to determine which multicast burstification class a new multicast tree should be added to, subtracted from, or modified. Therefore, instead of having to literally compare the multicast trees, the injection function value for each multicast tree can be compared to determine whether the multicast trees are the same or not. For the injection function, f(A) where A is an ordered set and kept in an array (e.g. a[i] accommodates the ith element in the ordered set). The maximum difference between the two elements of the set in value is N. The injection function is defined as follows:            f        (   A   )       =       ∑     i   =   1          A                            p   i     ·     a        [   i   ]             ,                   
     where p i  is a prime number and p i+1 −p i &gt;N, for i=1, 2, . . . , |A|. 
     Any linear or nonlinear function can be used as non-injection function. For example:            f        (   A   )       =       ∑     i   =   1          A                            g   i          (     a        [   i   ]       )           ,                   
     where g i (a[i]) is a function of a[i] (e.g., g i (a[i]) a[i] 2 ). 
     Although the present invention has been described in detail, it should be understood that various changes, substitutions and alterations can be made hereto without departing from the spirit and scope of the invention as described by the appended claims.