Optical data transmission

Abstract

A routing and wavelength assignment method for use in an optical fiber system, comprising: (i) identifying a plurality of paths between a source node and a destination node, (ii) selecting one of the plurality of identified paths, (iii) defining within the spectrum band of the selected path one or more blocks of spectral resource, in which each block comprises either: one or more unused wavelength channels, or one or more wavelength channels having the same spectral width, (iv) obtaining an entropy value of the selected path defining the spectrum fragmentation across its spectrum band, based on a logarithm of the ratio of the number of wavelength channels in each of the one or more blocks, to the total number of wavelength channels across the spectrum band, (v) iterating (ii) to (v) until the entropy value of each of the plurality of identified paths has been determined, and (vi) choosing from the plurality of identified paths a path having the lowest entropy value.

Claims

1. A routing and wavelength assignment method for use in an optical system, comprising: (i) in an optical path between a source node and a destination node, selecting a block of spectrum resource comprising one or more adjacent wavelength channels, the block being of a width sufficient to accommodate a demand having a spectral width occupying one or more adjacent wavelength channels, and the optical path comprising a plurality of optical links between the source node and the destination node; (ii) calculating an entropy change value (Hfrag) that would result from introducing the demand into the block in each link of the optical path; (iii) summing, over the plurality of optical links, a total entropy change value for the block; (iv) iterating (i), (ii) and (iii) for at least one further block of spectrum resource in the optical path; and (v) selecting a block that results in a lowest summed entropy change value.

2. A method according to claim 1, wherein (ii) comprises determining the entropy change value (Hfrag) by using a formula: $-\underset{i=1}{\overset{N}{.Math.}}\frac{D_i}{D}\ln \frac{D_i}{D}$ where N is a number of blocks in a spectrum band of the optical path, D is a total number of wavelength channels, ln is the natural logarithm, and D.sub.i is a number of wavelength channels in the i.sup.th block.

3. A method according to claim 1, further comprising identifying the optical path through the plurality of optical links.

4. A method according to claim 1, wherein (i) comprises selecting a shortest optical path first.

5. A method according to claim 1, wherein the calculating is further based on information about network states and transceiver profiles.

6. A method according to claim 1, wherein the wavelength channels have arbitrary spectral widths.

7. A network management system enabling routing and wavelength assignment decisions, the system configured to: (i) in an optical path between a source node and a destination node, select a block of spectrum resource comprising one or more adjacent wavelength channels, the block being of a width sufficient to accommodate a demand having a spectral width occupying one or more adjacent wavelength channels, and the optical path comprising a plurality of optical links between the source node and the destination node; (ii) calculate an entropy change value (Hfrag) that would result from introducing the demand into the block in each link of the optical path; (iii) sum, over the plurality of optical links, a total entropy change value for the block; (iv) iterate (i), (ii) and (iii) for at least one further block of spectrum resource in the optical path; and (v) select a block that results in a lowest summed entropy change value.

8. A system according to claim 7, further comprising a transceiver.

9. A non-transitory computer-readable storage medium comprising computer executable code which, when executed on a computer, causes the computer to perform the method of claim 1.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Systems, methods and apparatus of embodiments will now be described by way of example only, with reference to the following drawings, wherein:

(2) FIG. 1 illustrates spectrum assignment in fixed grid and flexgrid scenarios.

(3) FIG. 2 depicts spectra of different entropy fragmentation levels.

(4) FIG. 3 depicts the optical frequency space of a fragmented optical spectrum.

(5) FIG. 4 depicts the results of the transformation of the optical frequency space shown in FIG. 3 into a state distribution space.

(6) FIGS. 5(a) and 5(b) respectively represent an unfragmented and ordered optical spectrum, and the associated transformed state space.

(7) FIG. 6 depicts the process flow for calculating a fragmentation entropy measure.

(8) FIGS. 7(a) and 7(b) together depict the process flow in a routing and spectrum assignment process of an embodiment.

(9) FIGS. 8(a) and 8(b) respectively depict the link-based and path-based entropy assessment approaches.

(10) FIG. 9 is a graph depicting the evolution of a network in spectrum entropic terms.

(11) FIG. 10 is a graph depicting the evolution of a network in terms of utilization.

(12) FIG. 11 is a block diagram of network components involved in the routing and spectrum assignment process of the prior art.

(13) FIG. 12 is a block diagram of network components involved in the routing and spectrum assignment process of an embodiment.

DETAILED DESCRIPTION

(14) As discussed above, FIG. 1 illustrates the differences in the fixed grid and flexgrid paradigms, and a comparison of graphs (d) (depicting fixed grid spectrum use) and graph (e) (flexgrid) highlights the spectrum savings that can be achieved using flexgrid.

(15) The techniques and apparatus described herein are largely directed to use of the invention in flexgrid networks given the inherent likelihood of fragmentation when slots are vacated in the manner described above. As will, however, be explained below, it is also possible to use them to advantage in fixed grid scenarios.

(16) Fragmentation Entropy Metric

(17) The following describes how a usable entropy metric can be calculated for any system with suitable characteristics. A worked example is also discussed in connection with FIGS. 3 to 5, to demonstrate an application of an entropy metric in the specific context of fragmentable optical spectrum resources. The fragmentation entropy metric or measure obtained using the method described herein, takes into account distinguishable minimum-entropy states and degrees of freedom in multi-granular/wavelength link traffic demands. The method takes from the Shannon theory of information, and is based on the Boltzmann approach of countable and distinguishable states. The result is monotonic and scale-less, and discriminates varying spectrum topological complexity for efficient resource management.

(18) Generally speaking, a system can exist in N different states (as will be described in more detail below), wherein the probability of existing in the i.sup.th state is p.sub.i. As known from Shannon information theory, the entropy H of the system is generally given by H=.sub.i=1.sup.Np.sub.i ln p.sub.i, where .sub.i=1p.sub.i=1.

(19) In measuring the fragmentation of a system's resource, two points of interest are: (i) whether a particular resource of the system is being used; and (ii) the relative location of that resource, in particular whether neighboring resources to it are being used.

(20) Referring to FIG. 2, the first (top-most) and last (bottom-most) spectra depict respectively the least and the most fragmented versions of the resource (in which empty boxes depict unfilled slots and black boxes depicted filled slots). From a practical point of view, when a section of resource is being used contiguously (i.e. no gaps in between), how the different contiguous chunks of resource are arranged within the overall section of contiguous space is not relevant. The first-order requirement is that the resource be as unfragmented as possible. As may be expected, management of a complex topology comprising a puzzle of interstitially-inserted resources (such as the last-depicted spectrum in FIG. 2) is more problematic than in a less fragmented system. As noted above in the case of an optical network, resource fragmentation is created when, e.g., a demand or requirement previously in use is removed from the system, which is likely to worsen over time if left unchecked, particular in flexgrid implementations. An appropriate tool will be required to assess the relative topological complexity and/or fragmentation of the resource utilization from time to time or on an ongoing basis. Maintenance in the form of, e.g., spectrum re-ordering and re-allocation (akin to a defragmentation of a computer hard disk) will have to be carried out to ensure efficient use of the available spectrum resource. This is potentially costly and disruptive as operations have to be temporarily halted while the spectrum defragmentation takes place. Having an entropic measure or metric will allow the network owner or operator to take informed decisions about when and how to undergo such maintenance, or test and diagnosis.

(21) In calculating such a metric, a start point is the fill-factor f, which has a value lying between 0 and 1. The fill-factor f indicates the fraction of the optical spectrum being consumed by the total number of data channels present. For a fully unfragmented spectrum, where the different permutations/combinations of the occupied spectrum are essentially indistinguishable from each other, the entropy of the system is given by:
H.sub.min(f)=f ln f(1f)ln(1f)(1)

(22) By definition, an unfragmented system comprises two sections, one of which is completely occupied and the other is completely unoccupied, so that a portion of optical spectrum exists in only N=2 different states. The probability that any resource quantum of the optical spectrum exists in the completely occupied or filled state is p.sub.1=f, and the probability of existing in the completely unoccupied or unfilled state is p.sub.2=1f. The fragmentation entropy of this unfragmented spectral case is referred to as H.sub.min, since it represents the lower bound of the system fragmentation entropy for any given fill-factor f. The shape of H.sub.min as a function off is the well-known symmetrical curve (even about f=0.5 where it reaches its maximum of 0.693) which is zero at f=0 and f=1.

(23) A fragmented spectrum, on the other hand, comprises separated chunks of used or unused optical resource each of which represents different states or blocks of the system.

(24) The states or blocks of the system are defined by considering the optical spectrum to be represented by a set of N different number of blocks of spectral resource. Each state or block consists of either a single wavelength or data channel, or a contiguous set of multiple data channels but each of the same kind and spectral width, e.g. all 10G, 40G, or 100G, etc. Referring briefly to the example shown in FIG. 3, there are a total of N=11 states or blocks, in which state 1 comprises one 10G channel, while state 5 comprises two 40G channels. The spectral width of the i.sup.th block is given by C.sub.i, assumed to be an integer multiple of a minimum spectral resource quantum q, e.g. q=6.25 GHz. A block of resource can therefore also represent either a single or a contiguous set of unused optical spectrum quanta (see states 2 and 4 respectively, in FIG. 3); in which case the single (or repeated) channel is of unit spectral width q.

(25) Because a block comprises either one single channel, or contiguous identical data channels, each block represents a maximally unfragmented (minimum entropy, MinEnt, or minimum topological complexity) sub-domain of the overall optical spectrum. This is because the position occupied by any one of the channels within a particular block is irrelevant to the entropy measure of the block, so that the entropy of the block itself can be thought of as a constant. Accordingly, swapping or shuffling channels within a block offers no advantage or difference in terms of optimal exploitation of the overall spectral resource.

(26) The total (i.e. filled+unfilled) spectrum resource within an optical fiber is assumed to be Pq, i.e. there are a total of P spectral quanta of total resource.

(27) In calculating the entropy measure, the next important abstraction is to consider each individual data channel (10G, 40G, 100G, etc.) as well as each unfilled quantum q, to represent a single degree of freedom (DoF) of the system, which is independent of the actual spectral width that each DoF represents. A DoF can be of varying spectral width, in the same way as a block or state. As noted above, a state or block can comprise more than one channel or unused section(s) of spectrum, so referring again to FIG. 3, there are 2 DoFs in each of e.g., states 4 and 5. Characterizing the data channels in DoF terms allows for appropriate account to be taken of the differing spectral widths of channels (and unused or free spectrum) especially in a flexgrid implementation. As would be expected, each DoF of the optical spectrum affects the overall entropy behavior of the optical spectrum.

(28) Each block contains D.sub.i DoFs, where D.sub.i=C.sub.i/Q.sub.i, and Q.sub.i represents the spectral width of the particular modulation format Q={q, 10G, 40G, 100G, etc.} present in that particular block. The total number of DoFs in the system is D, where D=.sub.i=1.sup.ND.sub.i. The probability of a quantum of optical spectrum being in the i.sup.th data block is p.sub.i=C.sub.i/P. However, rather than using this probability quantity which essentially depends only on P (i.e. the total number of resource requirement quanta q in the optical spectrum), the fragmentation of the orderings of the D DoFs of the system holds greater interest, where in general DP (equality is only achieved for a completely unused optical spectrum). The probability that any DoF lies within the i.sup.th block is p.sub.i=D.sub.i/D.

(29) The overall fragmentation entropy of the optical link is therefore given by:

(30) $\begin{array}{cc}{H}_{\mathrm{frag}}=-\underset{i=1}{\overset{N}{.Math.}}\frac{D_i}{D}\ln \frac{D_i}{D}& \left(2\right)\end{array}$
where D is the total number of DoFs present at that time across the spectrum band and D.sub.i is the number of DoFs in the i.sup.th block of used or unused spectrum. This formula provides a highly versatile and usable measure of resource fragmentation entropy and topological complexity, which gives system or network owners or operators information allowing for e.g. defragmentation or other maintenance activity to be carried out on the system. In particular, the metric can be used to make routing and wavelength assignment decisions, as will be discussed below. The metric can be obtained on the unused section of the spectrum, the used section, or both.

(31) As previously observed, the spectrum of an optical fiber is deemed to be completely unfragmented (i.e. with minimum topological complexity) where the spectrum is completely unfilled, or else completely filled to capacity with exactly the same sized channels (e.g. all 10G signals). When the optical frequency space of such an unfragmented spectrum is transformed into and viewed as a state distribution: in the first, completely unfilled, case there is just one state (i.e. unfilled) available with an associated probability p.sub.1=1, such that the fragmentation entropy is H.sub.frag=0. Likewise, where the spectrum is completely full (e.g. with only 10G channels), after transforming into the state distribution we yield a single state (i.e. 10G in this case) again with a probability p.sub.1=1, and associated fragmentation entropy of H.sub.frag=0. Hence, the entropy-based fragmentation entropy metric can have an absolute minimum value of zero. A relative fragmentation entropy measure h.sub.frag can also be defined, relative to the minimum possible entropy H.sub.min for a given fill-factor f. This is given by:

(32) $\begin{array}{cc}{h}_{\mathrm{frag}}=\frac{H_{\mathrm{frag}}}{H_{\min }}-1& \left(3\right)\end{array}$
and is zero for the maximally unfragmented case and with minimum topological complexity.

(33) In summary, an entropy metric can be calculated by considering the optical spectrum in terms of a number of slots representing the individual flexgrid quanta. These can then be grouped into N contiguous blocks consisting of either used (coming from any number of individual signals) or unused spectrum. The Shannon entropy metric H.sub.Frag of a spectrum can then be calculated using the formula (2) noted above. Large values of H.sub.Frag indicate higher levels of fragmentation.

(34) The entropy levels of the spectrum resources shown in FIG. 2 have been calculated using this approach. The first (top-most) example shows a completely unused spectrum which has a H.sub.Frag value of zero; as expected, a completely filled spectrum would also have a fragmentation metric of zero. The remaining examples show that for the same amount of free spectrum (represented by an equal number of filled and unfilled slots), the value of H.sub.Frag varies (and increases monotonically) depending on the amount of fragmentation, which reaches a maximum in the last example comprising alternating filled and unfilled slots. One advantage of this approach is that longer contiguous blocks of used or unused spectrum, which are more useful for accommodating future demands, tend to result in lower overall fragmentation entropy levels,

(35) An example to demonstrate and discuss how the entropy levels are calculated will now be discussed in connection with FIGS. 3 to 5 to illustrate the application of the above general principles.

(36) FIG. 3 depicts an example of an optical spectrum partly filled with data channels of differing bandwidths. The y-axis depicts channel power, while the x-axis is a representation of the spectrum resource. In this illustration, there are N=11 available blocks (i.e. representing 11 states) for this particular spectrum configuration. Here, block or state 1 comprises a 10G data channel, block 2 is unused (U) spectrum, block 3 comprises a 100G data channel, block 4 comprises 2 unused quanta of spectrum, and so on. The resource is fragmented in that it comprises used sections as well as unfilled sections. Each channel (U (or q), 10G, 40G or 100G, etc.) is considered to be a single DoF and can be a state in itself (e.g. blocks 1, 2, 3, 6, 7, 9, 10, 11). In FIG. 3, each DoF is depicted along the linear x-axis, so 2 instances of repeating or adjoining 10G channels can be seen in state 8, for example. Multiple consecutive (contiguous) channels can collectively constitute a single state if they are of the same kind or bandwidth (blocks 4, 5, 8). In the example of FIG. 3 therefore, there are a total of D=14 separate channels/quanta or DoFs.

(37) FIG. 4 depicts the optical frequency spectral distribution of the example shown in FIG. 3 in terms of its state-space distribution. As previously noted, the number of states is N=11 and the number of DoFs is D=14. Each state 1 to 11 is again depicted along the x-axis. In contrast with FIG. 3 however, the channels within the states are represented in terms of its DoFs, so for example there is in state 2, 1 DoF (out of a total of 14 DoFs), while in state 4 there are 2 DoFs (out of a total of 14 DoFs). The height of each bar in each state graphically represents the number of DoFs in each state (so the bar in state 4 is twice the height of that in state 2), which is numerically confirmed by the figures appearing above each bar ( 1/14 and 2/14 respectively in states 2 and 4). In transforming the view of the spectrum resource from the optical frequency view of FIG. 3 to the state-space view in FIG. 4, it is irrelevant whether the channels are arranged from left to right, or vice-versa.

(38) By applying the above-mentioned Shannon formula H=.sub.i=1.sup.Np.sub.i ln p.sub.i, it can be calculated that the fragmentation metric of the spectrum shown in FIG. 3 is H.sub.frag=2.342.

(39) It may be expected that an unfragmented resource would yield a lower entropy value. This can be demonstrated by reference to the example shown in FIGS. 5(a) and (b), in which FIG. 5(a) depicts the optical frequency of a set of data channels identical to those shown in FIG. 3, which are arranged, however, so that the DoFs (which in total remains unchanged at D=14) are clustered together in a maximally unfragmented state. Referring to the 10G channels for example, while they previously occupied states 1, 6, 8 and 11 (in FIG. 3), they now are arranged contiguously to form a single block in state 2. The other channels are similarly treated, so that the 14 DoFs are now distributed across the N=4 states (i.e. Unfilled in state 1, 10G in state 2, 40G in state 3, and 100G in state 4), which may be compared with the D=14 states in FIG. 3. As a result, there are only N=4 states in FIG. 5(a).

(40) FIG. 5(b) depicts the state-space distribution of that shown in FIG. 5(a) with associated probability amplitudes, and the overall fragmentation entropy can be calculated to give an entropy value of H.sub.frag=1.291. The entropy-based fragmentation metric thus offers an objective means to ascertain the degree of fragmentation present in an optical link, and as the metric is monotonic, the higher H.sub.frag=2.342 entropy value from the example shown in FIG. 3 clearly demonstrates that resource to be more fragmented than the more ordered configuration of FIG. 5(a) which has a lower entropy measure H.sub.frag=1.291.

(41) The fact that the fragmentation metric is monotonic makes it useful when considering the relative topological complexity of a fragmented spectrum. A monotonic metric offers a measure of the degree of fragmentation and topological complexity of a particular spectrum configuration. So for example, even for the case of FIG. 3 and FIG. 5(a) where the fill-factor (i.e. spectrum capacity utilization) is the same for both cases, the lower fragmentation metric for FIG. 5(a) confirms what we can visually ascertain as its lower fragmentation, and its relatively more simple topological-complexity. Although not shown as a figure, if the used spectrum channels of FIG. 5(a) were actually all identical, e.g. only 10G channels, (i.e. still the same fill-factor as for FIG. 3 and FIG. 5(a)) then the associated fragmentation entropy can be calculated using H.sub.min, and found to be H.sub.frag=0.389. This is again much lower than the fragmentation entropy of FIG. 5(a) and confirms that it is essentially less fragmented than FIG. 5(a), due to its lower topological complexity.

(42) This finding is confirmed when viewing the spectrum resource entropy in terms of its fill-factor. Referring back to the example in FIG. 5(a) and assuming for simplicity, quantum q=10 GHz so that the channel bandwidths are given by 10Gq, 40G4q, 100G10q, the total available spectrum is P=38q, following from the existence of 38 spectral resource quanta (5unfilled+510G+240G+2100G). With 5 unfilled slots, the fill-factor in this case is f=33/38=86.8%. The minimum fragmentation entropy for such a fill-factor is H.sub.min=0.389, but it can be noted that the total number of DoFs is now D=38. Likewise, for the case with the same fill-factor f=86.8% as is the case for the previous examples, but for an even more ordered, minimally low topological complexity situation of only one type of modulation format (e.g. 10G, so that there are 3310G essentially indistinguishable contiguous channels), then the fragmentation entropy reduces further to H.sub.frag=0.389, equal to H.sub.min.

(43) The above approach to derive the entropy metric is essentially scale-less (due to its logarithmic nature) and therefore can be applied in sub-networks, national, and pan-national networks in a naturally additive fashion. Usefully, additionally because of its monotonic behavior, it enables measurements of the fine differences between the performances of different defragmentation and RSA algorithms, and achieve optimum network resource exploitation. Furthermore, a link RSA having both local and global properties (e.g. modifying the spectral allocations of a local link will have global implications across the network), the entropic approach to measuring the state of disorder of links in a photonic network is analogous to measuring the entropy of a gas of particles, where each particle exhibits both local and global properties (i.e. a particle has a statistical distribution of short-range to long-range interactions/collisions with the other particles in the gas.) Hence, use of a local link fragmentation entropy also offers insights into a means to optimize the overall dynamic equilibrium performance of a photonic network.

(44) Entropy-Based Optical Routing

(45) Apparatus and methods based on use of an entropy metric which may be obtained in the manner described above, will now be discussed in relation to making routing decisions within an optical network, as an example of how such metrics may be used. Making routing decisions based on, at least in part, spectrum entropy levels especially in flexgrid-based systems, will help address issues which will arise as traffic levels increase, and could help maintain or even reduce spectrum fragmentation over time. This could reduce the need for network operators to carry out spectrum defragmentation activities which would cause delay and disruption to traffic flows.

(46) In particular, the entropy metrics derived from the Shannon-based approach described in the previous section can be applied to routing issues in at least two ways. The first method is based on a link-based minimized entropy measure (MinEnt) where the spectrum of each link along a particular path is considered in isolation. The second way it can be applied is a path-based MinEnt where the spectrum profiles along all the links in the path are combined together to form a single end-to-end profile. These two applications will be discussed in greater detail below.

(47) Generally, optical system owners or operators currently use network Routing and Wavelength Assignment (RWA) and/or Routing and Spectrum Assignment (RSA) algorithms in their network management systems (NMS) to find pathways through an optical network. In the classical RSA approach, the process comprises two separate steps: first, a route across the network is chosen following a shortest distance or minimum hops algorithm; and then a first fit algorithm is used to select the first free end-to-end wavelength block that can be found. The following pseudo code illustrates the approach:

(48) TABLE-US-00001 ClassicalRouteAndAssignDemand(Network, Source, Dest, Width) PathCandidates = MultiShortestPaths (Network, Source, Dest) if no PathCandidates found then return and block Demand for each Path in PathCandidates in ascending order Spectrum = GetPathSpectrum(Network, Path) for each Slot in Spectrum TxProfile = GetTxSpectrum(Slot, Width) if SpectrumFree(Spectrum, TxProfile) then return and allocate Demand <Path, Slot> end if next Slot next Path return and block Demand

(49) Embodiments and implementations discussed herein seek to include entropy measures into routing and spectrum assignment decisions to find a routing and spectrum assignment that minimizes entropy. This is achieved by use of an algorithm which assigns routes and spectrum by allotting the smallest slot which can accommodate the particular demand, in order to keep larger (contiguous) blocks of spectrum free, and/or for larger demands that need it. In this way, demands of narrower spectral width are not assigned to a large slot where a narrower but suitable slot is available, thus reducing the creation of unused sections next to the newly-occupied slot and allowing for a higher number of demands of various sizes to be supported by making better use of the spectrum.

(50) The entropy measure routine could be based on the approach described above using a version of e.g. formula (2) described above to obtain the H.sub.Frag value. In this approach, the entropy value is calculated only for the unused spectral components of a given optical spectrum by finding each block of unused spectrum and calculating the following:
(number_of_unused_slots/total_slots_across_spectrum)*LN(number_of_unused_slots/total_slots_across_spectrum)
where LN is the natural logarithm, and the total_slots is equal to the total number of spectrum slots (unused and used) across the whole spectrum band. This calculation is repeated for each block of unused spectrum and added together to get an overall calculation of the fragmentation entropy. It should be noted that a slot is deemed to be equivalent to a quantum q of spectrum, so that total slots across the spectrum is P as previously defined, and the number of unused slots is U where the total unused spectrum is therefore Uq. This can provide a usefully-quick (i.e. a less algorithmically complex) approximation to the fragmentation entropy of equation (2).

(51) The flow chart of FIG. 6 depicts the tasks involved in calculating the entropy measure of a given spectrum resource, in which the process begins by setting the entropy value (frag_entropy) to zero (S2). A block of unused spectrum is found (S4) and the number of unused slots (unused_slots) discovered up to that point is recorded (S6). The fragmentation entropy level for the unused spectrum block under consideration is calculated using the above formula (S8). If there are still unused blocks to be processed (S10), the tasks are iterated until all the blocks in the spectrum have been processed, at which point the entropy metric is obtained (S12) by adding together all the entropy level values of each unused spectrum block to get an overall calculation of the unused-spectrum fragmentation entropy.

(52) In pseudo code terms, the approach can be expressed thus:

(53) TABLE-US-00002 CalcFragEntropy(Spectrum) TotalSlots = count of number of slots in Spectrum Entropy = 0 for each UnusedBlock in Spectrum UnusedSlots = count of number of slots in UnusedBlock Entropy = Entropy + UnusedSlots / TotalSlots * ln(UnusedSlots/ TotalSlots) next block return -Entropy

(54) The obtained entropy measure sits at the heart of the routing process described in the flow chart set out in FIGS. 7(a) and 7(b). In brief, the approach involves the finding of a route though the optical network which has the lowest unused-spectrum fragmentation entropy, which is achieved by replacing the conventional lowest-cost path algorithm with a fragmentation entropy metric obtained by the exemplary method shown in FIG. 6. This requires the used spectrum state of each branch of the network to be stored and the spectrum of each additional hop under consideration needs to be added to these states. The fragmentation entropy of the spectrum is calculated using the formula given above. Generally speaking, discovery of the path with the lowest unused-spectrum fragmentation entropy path allows the network owner or operator to select a spectrum allocation which reduces the level of end-to-end fragmentation entropy along the chosen path, or else causes the fragmentation entropy to increase by the smallest amount. To accomplish this, the spectrum required for the transceiver is placed in every position along the entire spectrum. If for a given position the spectrum is currently unused, then the fragmentation entropy is calculated as set out in the flow chart of FIG. 6. The lowest unused-spectrum fragmentation entropy state is stored. Once identified, the routing and spectrum assignment is output to the NMS to be configured on the network nodes. As the skilled person would appreciate, a number of variations can be made to the implementations discussed here: for example, the two steps (of identifying and applying the entropy metric) can be more tightly coupled to form a single step, which might require additional computational time and resources. In any event, it can be expected that routing traffic in this manner would realize a network having an overall lower entropy measure, which will allow for bigger sections to remain available allowing for accommodation of future demands.

(55) Turning now to the exemplary process shown in the flow chart of FIG. 6: at the start of the process, information about the topology and state of the network is used to find a number n of paths between source A and destination B (S22) using conventional methods, e.g., based on Dijkstra's algorithm. Where no path is found (S24) (e.g. there is no discoverable path to the destination node B), the process is blocked (S26) and terminates. If a path is available, the shortest path is selected and the used spectrum profile of that path determined (S28). At this point, the profile of the transceiver device (which is carrying the traffic between source and destination) is applied to the path spectrum profile (S30) at a first location along the spectrum profile. If a section of free spectrum is found (S32, which includes the routine set out in FIG. 6), the fragmentation entropy of the newly-identified path is calculated (S34). A comparison is then made of the entropy levels of the latest-discovered path with any previously-discovered paths based on the spectrum configuration that would result from using the latest-discovered path (S36), and the spectrum allocation in question is stored (S38). The transceiver profile is now along by one slot to allow further placements along the spectrum to be checked (S41). When the spectrum has been fully searched (S40) and the lowest entropy allocation for this spectrum has been found for this new demand along the current considered path (S42), a comparison with previously-discovered paths is made to determine if the latest-discovered path has the lowest entropy rating (S44). If it does, the path and spectrum allocation is stored (S46). The tasks to find the path with the lowest entropy value are iterated until all n paths initially identified at S22 have been checked (S48 and S49). If no spectrum and path combination to the destination node B has been identified, the process is blocked (S52) and terminates. Otherwise, the path and spectrum allocation generating the least entropy in the spectrum resource is selected (S50 and S54), which seeks to guard against waste of the spectrum, e.g., avoid placing new demands within a large unused slot when narrower but suitable slots are also available.

(56) As noted above, the obtained entropy metric can be applied to RWAs and RSAs in at least two ways. The flow charts of FIGS. 6 and 7 allude to these methods, which will now be described in detail.

(57) Entropy-Based Optical Routing: (i) Link-Based Measure

(58) In the link-based approach based on minimized entropy level, the spectrum of each link or hop (i.e. between nodes) along a particular path is considered separately from each of the spectrums of the other links along the path. Specifically, the spectrum profile of each link is searched to find starting locations with enough free spectrum slots to support the transceiver's spectral width. For each available position, the change in the entropy levels of a spectrum in which the new signal is placed, is calculated. All other slots or positions which have insufficient spectral capacity, are ascribed an infinite delta (or change in entropy). This is repeated for the remaining links in the path and the sum of entropy deltas taken. The frequency slot with the lowest sum of entropy deltas is then selected.

(59) The concept can be illustrated in pseudo code as follows:

(60) TABLE-US-00003 MinEntLinkRouteAndAssignDemand(Network, Source, Dest, Width) PathCandidates = MultiShortestPaths(Network, Source, Dest) if no PathCandidates found then return and block Demand LowestEntropyDelta = infinity BestPath = null BestSlot = null for each Path in PathCandidates in ascending order EntropyDeltas[ ] = infinity for each Link in Path Spectrum = GetSpectrum(Network, Link) OrginalEntropy = CalcFragEntropy(Spectrum) for each Slot in Spectrum TxProfile = GetTxSpectrum(Slot, Width) if SpectrumFree(Spectrum, TxProfile) then TempSpectrum = Combine(Spectrum, TxProfile) NewEntropy = CalcFragEntropy(TempSpectrum) EntropyDelta = NewEntropy OriginalEntropy EntropyDeltas[Slot] = EntropyDeltas[Slot] + EntropyDelta else EntropyDeltas[Slot] = infinity end if next Slot end if for each Slot in EntropyDeltas if EntropyDeltas[Slot] < LowestEntropyDelta then LowestEntropyDelta = EntropyDeltas[Slot] BestPath = Path BestSlot = Slot end if next Slot next Path if LowestEntropyDelta = infinity then return and block Demand else return and allocate Demand <BestPath, BestSlot> end if

(61) In a worked example illustrating the above, FIG. 8(a) depicts a path comprising 4 links (S1 to S4) with 16 frequency slots (f1 to f16) along the spectra of each link. Again, the empty boxes depict unfilled slots and black boxes depicted filled slots, so it can be seen that all the spectra are fragmented to varying degrees. End-to-end paths for single-slot demands are available through all 4 links in slots f5, f6, f8, f9, f11, f12 and f13. In this example however, a new demand requiring 2 slots needs to be placed on the path, for which there is end-to-end path availability in slots f5, f8, f11 and f12. The values in the boxes show the entropy change or delta (Hfrag) if the new demand is placed starting at that location. These are obtained using the entropy calculation method described above for each link. Referring to link S1 as an example, slot f4 has an available slot next to it (slot f5) and so can accommodate a 2-slot demand. If it takes on the demand, the entropy delta value is 0.141. Slot f5 has identical characteristics, and so will also have an entropy delta value of 0.141 if it takes on the demand. Slot f7 is occupied, and so slot f6 has no capacity to take on a 2-slot demand, and so its change value is infinity. The values in the line Sum(Hfrag) shows the overall delta values for the end-to-end path in each available slot across all 4 links. Slot f8 yields the lowest overall (summed) MinEnt value of 0.742, and so according to exemplary implementation of the invention, the best choice would be to place the new signal in slot f8.

(62) In brief, the method can be summed up in the following tasks: (i) identifying a plurality of paths between a source node and a destination node, (ii) selecting one of the plurality of identified paths, (iii) defining a new demand as occupying one or more adjacent wavelength channels, (iv) selecting one of the plurality of possible new demand placements from the free spectrum available in the spectrum band on the selected path between the source node and the destination node, temporarily allocating it within the spectrum band, (v) defining within the spectrum band of the selected path one or more blocks of spectral resource, in which each block comprises of one or more adjacent used or unused wavelength channels, (vi) obtaining an entropy value of the selected path defining the spectrum fragmentation across its spectrum band, based on a logarithm of the ratio of the number of wavelength channels in each of the one or more blocks, to the total number of wavelength channels across the spectrum band, (vii) iterating (iv) to (vii) until the entropy value of each of the available demand placements has been determined, (viii) iterating (ii) to (viii) until the entropy value of each of the plurality of identified paths has been determined, and (ix) choosing from the plurality of identified paths and demand placements a path and wavelength assignment having the lowest entropy.
Entropy-Based Optical Routing: (ii) Path-Based Measure

(63) The second way entropy measures can be applied in routing decisions is based on a path-based MinEnt value, where the spectrum profiles along all the links in the path are combined together to form a single end-to-end profile which is then searched to find the spectrum allocation that produces the smallest entropy delta.

(64) The following pseudo code describes the idea behind the path-based approach:

(65) TABLE-US-00004 MinEntPathRouteAndAssignDemand(Network, Source, Dest, Width) PathCandidates = MultiShortestPaths(Network, Source, Dest) if no PathCandidates found then return and block Demand LowestEntropyDelta = infinity BestPath = null BestSlot = null for each Path in PathCandidates in ascending order Spectrum = GetPathSpectrum(Network, Path) OrginalEntropy = CalcFragEntropy(Spectrum) for each Slot in Spectrum TxProfile = GetTxSpectrum(Slot, Width) if SpectrumFree(Spectrum, TxProfile) then TempSpectrum = Combine(Spectrum, TxProfile) NewEntropy = CalcFragEntropy(TempSpectrum) EntropyDelta = NewEntropy OriginalEntropy if EntropyDelta < LowestEntropyDelta then LowestEntropyDelta = EntropyDelta BestPath = Path BestSlot = Slot end if end if next Slot next Path if LowestEntropyDelta = infinity then return and block Demand else return and allocate Demand <BestPath, BestSlot> end if

(66) Referring to FIG. 8(b), which is based on the 4-link 16-frequency slot example initially discussed in connection with FIG. 8(a), the approach in which the availability of an end-to-end path through all the links as a preliminary requirement is graphically depicted. Here, the two best slot choices are f5 and f8, both yielding the lowest MinEnt value of 0.311.

(67) This accords with the result of the link-based approach, with the added refinement to the result that of the two preferred slots, placement of the new signal into slot f8 would add less fragmentation to the system. Both schemes can be applied over a number of potential paths between the source and destination node to search for lower entropy routings and wavelength assignments.

(68) Network Evolution Projections

(69) The applicants have performed simulations on a specific network configuration comprising source and destination nodes, to test the usefuless of the two entropy-based routing approaches described above. FIGS. 9 and 10 provide a view of network performance against increasing demand levels over time, and illustrate the different results using the three RSA schemes. The curves shown in FIG. 9 show how the overall unused-spectrum network fragmentation entropy (the sum of the unused-spectrum fragmentation entropies across all network links) evolves as demands are added, in which the average network entropy on the y-axis is plotted against the level of demand on the x-axis. FIG. 10 shows how the overall network utilization (the amount of used spectrum across all links) evolves, and plots the average network fill factor (i.e capacity used, on the y-axis) against demand (on the x-axis). In both graphs, the projections based on the three RSA scheme are depicted for comparative purposes: the link-based MinEnt data is depicted by line (a), the path-based MinEnt data by line (b), and the classical shortest-path routing with first-fit spectrum assignment is indicated by line (c).

(70) Referring now to FIG. 9, which depicts a static based traffic generation simulation wherein traffic is only added and never changed or removed, it can be seen that using the link-based MinEnt scheme (line (a)) can yield a significant improvement in the capacity to absorb increased traffic increase levels, when compared to the classical approach (line (c)). Lower levels of entropy are maintained across the whole network indicating that fragmentation is being minimized. This is to be expected given the algorithm is attempting to obtain the lowest entropy delta across the links. As indicated by curve (b), use of the path-based MinEnt approach generated more entropy than the classical approach, yielding only a limited improvement over the conventional approach only at a high level of demand.

(71) FIG. 10 shows that network utilization of link-based MinEnt schemes initially follows the classical result closely, indicating that similar length routes are being selected by both schemes. At higher levels of demand and traffic levels however, line (a) of the link-based MinEnt spectrum allocation approach gradually diverges from the result of the classical approach, indicating that demands can be allocated even as the classical routing and allocation approach starts to slow down on that front. In the case of the path-based MinEnt scheme, curve (b) shows that its use results in greater overall levels of entropy, but of greater critical importance, results in faster consumption of overall network resource.

(72) Referring back to the worked example shown in FIGS. 8(a) and (b) provides an insight into the poor performance of the path-based MinEnt scheme. The path-based approach combining the spectrum profiles over the four links has hidden the complexity of the underlying spectrums and results in placements at f5 and f8 sharing the same lowest entropy delta. If f5 was selected, it reduces the potential to make use of the larger gaps present on links S1 to S3 in other paths, whereas placement at f8 results in filling in a common spectrum gap and reducing overall fragmentation. Longer paths are also likely to be selected as the number of links in the path is hidden by the spectrum profile combination resulting in higher levels of network utilization. By making use of all the information available, the link-based MinEnt scheme correctly identifies f8 to be the optimum choice.

(73) Finally, FIG. 11 is a schematic view of the process flows between the network components used in routing and allocation management in a conventional set up. The main functional block is the NMS (100) which sends and receives instructions. The process typically commences with a request for a connection to be made between source node A and destination node B. This request is sent to the NMS (S61), which seeks and obtains data about the network state (S62 and S63). This information is then used to discover a suitable path based on the network state (S64), which according to standard RSA methods (86) would include shortest-path calculations. The identified path is then returned (S65) to the NMS. The WDM transceivers (102) are then configured (S66 and S67) to place the signal along the path identified for that purpose.

(74) FIG. 12 illustrates the relative ease with which an entropy-based metric can be deployed within the routing system by replacement of the conventional RSA method with a process or routine for calculating the entropy metric of the path or the link as the case may be. The skilled person would appreciate that as an alternative to replacement, the system may include entropy calculations in addition to standard routing decisions, and that both the link- and path-based methods could in suitable cases allow for deeper analyses of the network and identified routes to be carried out before a decision is taken.

(75) The apparatus, methods and configurations described above and in the drawings are for ease of description only and not meant to restrict the scope of the invention to any particular embodiment. For example, it will be apparent to the skilled person that steps can be added or omitted from the methods and processes described herein. While the examples illustrating application of the invention are made in respect of an optical network and in particular in connection with flexgrid-based systems, it would be appreciated that other telecommunications systems as well as non-telecommunications systems can suffer from resource fragmentation as well during use, which could benefit from an analysis of entropy levels. In particular, entropy based fragmentation RSA techniques can also be applied in fixed grid scenarios to select a path and wavelength channel which reuses released channels in the network more optimally than starting to make use of a new wavelength that is currently unused in the network. It would also be appreciated that such entropy measures can be advantageously applied in a variety of situations, not being restricted to use only in respect of identifying network routes.