Dynamic burstification based on fully/partially shared multicast entities

[0002] 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.

[0003] 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.

[0004] 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.

[0005] 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.

[0006] 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.

[0007] 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.

[0008] 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.

[0009] 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.

[0010] 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.

[0011] 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.

[0012] 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.

[0013] 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.

[0014] 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).

[0015] 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:

[0016] FIG. 1 shows one example of an optical burst-switched (OBS) network;

[0017] FIG. 2 shows one example of an equi-tree in an optical burst switched network (ETON) according to the present invention;

[0018] FIG. 3 shows one example of equi-coverage in an optical burst-switched network (ECON) according to the present invention;

[0019] FIG. 4 shows one example of super-coverage in an optical burst-switched network (SCON) according to the present invention;

[0020] FIG. 5 shows another example of super-coverage in an optical burst-switched network according to the present invention;

[0021] FIG. 6 shows one example of overlapping-coverage in an optical burst-switched network (OCON) according to the present invention;

[0022] FIG. 7 depicts a method for searching for multicast burstification classes in terms of a set of electronic egress edge routers;

[0023] FIG. 8 is a diagram showing two trees that are to be merged using the Breadth-First-Merge algorithm;

[0024] FIG. 9 is a diagram showing the result after the Breadth-First-Merge algorithm was run to merge the two trees in FIG. 8;

[0025] FIG. 10 shows a data structure for an ETON implementation;

[0026] FIG. 11 shows a data structure for ECON, SCON, and OCON implementations;

[0027] FIG. 12 shows a data structure of a multicast burstification class for ETON, ECON, SCON, and OCON; and

[0028] FIG. 13 shows a data structure for a multicast tree for ETON, ECON, SCON, and OCON.

[0029] 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.

[0030] 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.

[0031] 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.

[0032] 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.

[0033] 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₁and T₂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.

[0034] 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^thmulticast burstification class has R_jmulticast trees then:

[0035] MBC_j=(T_j1, T_j2, . . . , T_jRJ), where j=1,2, . . . , N

[0036] and

[0037] T_jk=(C_jk, E_jk, L_jk), where k=1,2, . . . , R_j.

[0038] 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₁205 and a second multicast tree T₂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.

[0039] In one embodiment of ETON, all of the multicast data packets associated with the first multicast tree T₁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₄and E₈115. Similarly, all of the multicast data packets associated with the second multicast tree T₂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₄and E₈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.

[0040] 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.

[0041] 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₁205 and the second multicast tree T₂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₁205 and T₂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₁205 or the second multicast tree T₂210. The single multicast burst can then be disassembled back into the multicast data packets at the electronic egress edge routers E₄and E₈115 and transmitted to the output subnets 130.

[0042] 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₂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_jRJin the ECON case.

[0043] In one embodiment of ECON, all of the multicast data packets associated with the first multicast tree T₁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₄and E₈115. Similarly, all of the multicast data packets associated with the second multicast tree T₂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₄and E₈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.

[0044] 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.

[0045] 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₁305 and the second multicast tree T₂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₁305 and T₂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₁305 or the second multicast tree T₂310. The single multicast burst can then be disassembled back into the multicast data packets at the electronic egress edge routers E₄and E₈115 and transmitted to the output subnets 130.

[0046] 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₁305 and T₂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.

[0047] 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₁405, and a second multicast tree T₂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.

[0048] In one embodiment of SCON, all of the multicast data packets associated with the first multicast tree T₁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₄and E₈115. Similarly, all of the multicast data packets associated with the second multicast tree T₂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₃, E₄, and E₈115. Finally the multicast bursts switched on the multicast tree T₁405 would be disassembled at the electronic egress edge routers E₄and E₈115 and transmitted to their respective subnets 130. Similarly, the multicast bursts switched on the multicast tree T₂410 would be disassembled at the electronic egress edge routers E₃, E₄and E₈115 and transmitted to their respective destination subnets 130.

[0049] 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.

[0050] In FIG. 4, note that the first multicast tree T₁405 and the second multicast tree T₂410 do not share the same electronic egress edge routers 115. However, multicast tree T₂410 covers all the electronic egress edge routers 115 covered by the first and second multicast trees combined (T₁405 and T₂410) thus creating a super-coverage multicast tree. Therefore, all of the multicast data packets associated with the first and second multicast trees (T₁405 and T₂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₂410. The multicast burst can then be disassembled back into multicast data packets at the electronic egress edge routers E₃, E₄and E₈115 and transmitted to the respective output subnets 130. Note also that the multicast data packets associated with multicast tree T₁405 are discarded at electronic egress edge router E₃115.

[0051] 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: $\begin{array}{cc}{E}_{\mathrm{jk}}\subseteq E_j^s\mathrm{for}\mathrm{all}k=1,2,\dots ,R_j& \\ \left|E_j^s-\stackrel{R_j}{\bigcap _i}{E}_{\mathrm{ji}}\right|\le h^E& \left(1\right)\\ \left|C_j^s-\stackrel{R_j}{\bigcup _i}{C}_{\mathrm{ji}}\right|+\left|\stackrel{R_j}{\bigcup _i}{C}_{\mathrm{ji}}-C_j^s\right|\le h^C,& \left(2\right)\\ \left|L_j^s-\stackrel{R_j}{\bigcup _i}{L}_{\mathrm{ji}}\right|+\left|\stackrel{R_j}{\bigcup _i}{L}_{\mathrm{ji}}-L_j^s\right|\le h^L.& \left(3\right)\end{array}$

[0052] Where h^C, h^Eand h^Lare 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.

[0053] 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.

[0054] 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^thmulticast burstification class, MBC_j, has R_jmulticast trees. The multicast traffic volume of the k^thmulticast group in the same MBC_jis D_jk, where k=1,2, . . . , R_j, and the cost of delivering a unit traffic volume on tree T_jkis S_jk. Further, the cost of delivering a unit traffic volume on super tree T_j^Sis S_j^S. The following inequality can be used to establish SCON class MBC_jfor an electronic ingress edge router. $\begin{array}{cc}{\mathrm{CER}}_j=\frac{\sum _{k=1}^{R_j}{D}_{\mathrm{jk}}{S}_{\mathrm{jk}}}{S_j^s\sum _{k=1}^{R_j}{D}_{\mathrm{jk}}}\ge h^R& \left(4\right)\end{array}$

[0055] The h^R(≧1) is a predefined value. For inequality (4), in one embodiment, S_jkthe sum of DWDM links in tree T_jk, and S_j^Sis the sum of DWDM links in the super tree. In another embodiment, S_jkand S_j^Sare the weighted sum of DWDM links in tree T_jkand 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₂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.

[0056] 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.

[0057] In one embodiment of OCON 600, all of the multicast data packets associated with the first multicast tree T₁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₄, E₈and E₉. Similarly, all of the multicast data packets associated with the second multicast tree T₂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₃, E₄and E₈. Finally the multicast bursts switched on the multicast tree T₁605 would then be disassembled at the electronic egress edge routers E₄, E₈and E₉and transmitted to their respective subnets 130. Similarly, the multicast bursts switched on the multicast tree T₂610 would be disassembled at the electronic egress edge routers E₃, E₄and E₈and transmitted to their respective destination subnets 130.

[0058] 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.

[0059] In FIG. 6 note that the first multicast tree T₁605 and the second multicast tree T₂610 do not share the same electronic egress edge routers 115, however, the combination of multicast trees T₁605 and T₂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₃, E₄and E₈, and E₉115 and transmitted to the respective output subnets 130. The trade off with OCON in FIG. 6 is that the electronic egress edge routers E3 and E9115 will need to discard some of the multicast data packets they receive.

[0060] 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.

[0061] 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.

[0062] 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.

[0063] 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.

[0064] 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*.

[0065] 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.

[0066] 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.

[0067] Insert and Add1 subprocedures are given below. The Insert subprocedure inserts a multicast tree into a Multicast Burstification Class.

[0068] The Add1 subprocedure adds the MBC into the lists according to the representative tree's edge router and link counts.

[0069] 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'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's MBC list. The procedure ETON_deletion is listed below.

[0070] 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.

[0071] Therefore, the addition procedure needs to be changed in the case of a non-injection function as follows:

[0072] 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.

[0073] For the non-injection function case, the ECON_addition2 procedure replaces the ECON_addition.

[0074] Deletion for ECON is exactly the same as the one for ETON case.

[0075] For the SCON case, the addition procedure searches for a MBC within the previously mentioned threshold values. Note that while h^Eis the threshold for the optical edge routers, h^Eis 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^Ein 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.

[0076] The Remove procedure removes the MBC from its corresponding list.

[0077] 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'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's MBC list. If the MBC includes any MT, these are re-accommodated in the system by being modified individually.

[0078] 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.

[0079] The procedure Breadth-First-Merge assumes that both trees' adjacency lists are available. The procedure takes MT1 as the primary tree and adds the edge routers, core routers, and links of the secondary tree MT2 which are different than MT1's.

[0080] FIG. 12 shows an example 1200 of the Breadth-first-merge procedure. There are two trees, primary tree MT1 and the secondary tree MT2, in FIG. 12. Starting from the secondary tree's root E₁, 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.

[0081] The step by step status of the queue is given below:

[0082] 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.

[0083] 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.

[0084] 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\left(A\right)=\sum _{i=1}^{\left|A\right|}{p}_i·a\left[i\right],$

[0085] where p_iis a prime number and p_i+1−p_i>N, for i=1, 2, . . . , |A|.

[0086] Any linear or nonlinear function can be used as non-injection function. For example: $f\left(A\right)=\sum _{i=1}^{\left|A\right|}{g}_i\left(a\left[i\right]\right),$

[0087] where g_i(a[i]) is a function of a[i] (e.g., g_i(a[i]) a[i]²).

[0088] 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.