Wavelength switching delay and distribution in optical fiber networks

Published Online September 2019 in MECS DOI: 10.5815/ijcnis.2019.09.03

Due to unprecedented growth rates of using geographically distributed resources, such as storage nodes, super computers, and scientific equipment, next generation networks will necessitate fast, reliable, and efficient transfer of large datasets approaching the scale of petabytes and Exabyte’s. High-speed optical core networks have become the expected standard for supporting such emerging transfer scale. Wavelength Division Multiplexed (WDM) networks are the most deeply investigated technological solutions which have demonstrated their merit and facilitated the growth of optical communications for both modern and future wide-area backbone networks, as well as scientific grid and cloud infrastructures [1].

The fundamental problem of establishing light paths to support optical transfers through assigning both a physical route and wavelength carrier channel to a request is knows as Routing and Wavelength Assignment (RWA) [2]. Arriving requests which cannot secure light path resources are blocked, lowering the efficacy of any given all-optical RWA solution. Improving RWA solutions has been extensively investigated. In [3] a light path migration algorithm is proposed by which light paths may be altered just prior to connection. The authors of [4] re-provision scheduled light paths to re-optimize and improve network performance. Scheduling optimization through request ordering has also been investigated in [5]. The authors of [6] define and analyze the RWA problem by applying a virtual topology for the optical network. The work in [7] introduces an integer linear program formulation for RWA in survivable WDM networks which support wavelength conversion capability. The authors have investigated the benefits of wavelength conversion on the solution space.

This paper considers Advance Reservation (AR) traffic wherein transmission is scheduled to begin well after request arrival, following some predetermined book-ahead time delay. AR differs from the more traditional and less flexible Immediate Reservation (IR) demands, in that IR traffic expects service immediately upon arrival into the network. Networks employing AR services enjoy the efficiency offered through predictable scheduling and resource allocation among a set of competing or temporally conflicting light path demands [8]. AR is often a suit- able scheduling approach for highly predictable transmissions

• [9]    And repeatable background transfer tasks [10]. In this work, we assume that start- and end-times of dynamically arriving AR demands are given, and therefore understood by a centralized resource scheduler. We refer the reader to [11] for a com- apprehensive survey of AR work in optical networks, including supplementary coverage of AR classifications and constraints.

Our previous work in [12] proposes the novel concept of Delayed Allocation (DA) for WDM-enabled networks. In the prior work, we propose the decomposition of light path resource establishment into two distinct phases: the Resource Provisioning Phase (RPP) and the Resource Allocation Phase (RAP). Upon arrival, the scheduler applies RPP to incoming demands which are either blocked outright, or tentatively scheduled. The exact suite of network resources allocated to any given light path is determined only after a delay during which time competing demands from later traffic arrivals may be factored into an intelligently constructed light path schedule. The RAP therefore establishes the light path immediately prior to the scheduled start time for all requests which are successfully promised resources during the RPP. Previous investigation has demonstrated enormous potential for improving overall light- path establishment success rates and spectral utilization [13]. We have also previously developed a novel technique for enhancing resource allocation flexibility for AR traffic called Light path Switching (LPS). After extensive investigation, we have concluded definitively that allowing the set of resources incorporated into a single light path solution to be non-uniformly selected throughout the request schedule offers significant opportunity for efficiency improvement [14]. Specifically, we have determined that support for Wavelength Switching (λ-switching), or the ability for a light path to traverse different wavelength resources on its path at various points during light path establishment, is very effective at improving resource consumption efficiency [15]. λ-switching supports flexibility performance beyond that which is capable using traditional RWA solution mechanics. Furthermore, all burden for support- ing LPS is placed upon the scheduler with advanced knowledge of resource switches, and therefore requires no additional infrastructure enhancement to the underlying network.

In this work, we propose the novel integration of both the DA and λ -switching techniques in order to investigate the impact of supporting both enhancements in tandem. We develop a three- phase resource provisioning and allocation algorithm called Delayed Allocation with Wavelength Switching (DA-λS) , and evaluates it both qualitatively and quantitatively against baseline solutions supporting only DA. We first discuss our problem and network assumptions, and also present details on both DA and λ -switching enhancement opportunities in Section II. The novel approach of combining these enhancements is explored and presented as the DA- λ S algorithm in Section III. We then evaluate the DA- λ S approach against baselines under dynamic AR traffic scenarios in terms of blocking probability and LPS overhead Section IV. Section V concludes the paper, offers discussion of impact and previews potential areas of future extension.

• II.    Problem Description and Resource Assumptions

In this section we describe resource assumptions considered in evaluating the efficacy of combining DA and λ -switching. We also present expanded coverage of both of these techniques and prior conducted works which have investigated them separately.

• A.    Network Resource Assumptions

We consider a network topology as a connected graph t = ( V ,E , W ,T ), where V represents the set of core vertex nodes, and E is the set of fiber-link edges between nodes in V .

W is the set of available wavelengths on each edge. We assume a set of AR light Path request R, such that each r € R to determine as r= (S, d, t, a, w). S € V is the source node d € V – {S} is the destination node, t is the request arrival time A ≥ t is the transfer start time before which a light path must be scheduled, and w (≥ a) is the completion of time or satisfied reservation. The reservation is holding time may be trivially calculated in constant time as the duration from αr to ωr. Suitable RWA solutions carry a few stipulations. No two light paths may share the same wavelength on the same network link at any time in order to avoid interference. The wavelength continuity constraint enforces the use of the same wavelength between the source and destination nodes along each link the signal traverses. While intra-route wavelength conversion is possible, the technology necessary to support it is prohibitively expensive and often not incorporated into long-haul backbone net- works. Lastly, the time continuity constraint requires that every light path be established using the same wavelength throughout The set of network-wide resources may therefore be described as a matrix of binary availability values, [A]T ×W ×E.

• B.    Delayed Allocation in WDM Networks

Figure 1 offers an illustrative example of DA. Four requests arrive to the network in-order ( R 1 , R 2 , R 3 , R 4 ) and all require transmission between the same sourcedestination pair. We simplify each request to the generalized form R_r = ( α_r, ω_r ) to define each in terms of start- and end-time. Using a traditional IR policy, the resources are reserved upon arrival of a request. Figure 1(a) depicts how R 1 , R 2 , and R 3 are therefore assigned wavelengths in order of arrival, using a first-fit assignment scheme. Thus, when attempting to satisfy R ₄ , no remaining continuous wavelength resources are available, and the request is consequently blocked from receiving service. Figure 1(b) offers an alternative DA solution. Each demand is only promised resources at the time of arrival to the network scheduler during the RPP, and specific resources are allocated only immediately prior to the start-time during the RAP. For example, even though R 4 is last to arrive, it starts first, and is therefore the first reservation to be allocated a wavelength, beginning at time t ₁ . R ₂ is satisfied next, followed by R ₃ and R ₁ . Delaying allocation until each request’s α_r , eliminates blocking and lowers the spectral fragmentation for this sample demand set.

We have previously investigated multiple variants of DA in WDM, most notably All Slots Advance Reservation (ASAR) and Single Slot Advance Reservation (SSAR) [12]. The former approach attempts to schedule resources for a reservation’s entire duration in a single step. The result is complete scheduling of one light path reservation at a time. SSAR, by contrast, schedules resources one time-slot at a time, such that multiple competing demands are considered in parallel. Our work shows SSAR significantly outperforms ASAR blocking performance and also greatly reduces the complexity of the scheduling logic. Throughout our current work, we integrate λ -switching, which considers spectral availability at each time-slot irrespective of prior assignment. This approach is well suited to the SSAR scheduling heuristic.

ttt

Fig.1. Switching in WDN Network

In our previous work, we have proposed the novel approach of Delayed Spectrum Allocation (DSA) for light path establishment in Elastic Optical Networks. As elastic networks are generalized variants of WDM networks, so too is DSA a generalization of DA with additional complexity and flexibility as well as investigations consider time-slotted scheduling as opposed to continuous time management [16], [17]. Any unit of work that alters the state of the network is assumed to occur at the beginning of a time-slot and finish at the end of a possibility for scheduled demands and exhibits the tremendous potential to reduce blocking for scheduled light path demands [13].

• C.    λ-Switching in WDM Networks

We have extensively investigated LPS previously [14], [15]. By supporting the ability to consider wavelength resource assignment at per time-slot granularity irrespective of assignment at previous slots, LPS has been shown to reduce AR blocking through consumption of non-uniform resources over the course of a scheduled period. The result is an enhanced ability to flexibly reduce conflict overhead with competing traffic in heavily loaded networks. LPS requires no network equipment enhancements, but does necessitate a light path scheduling system with global knowledge about resource availability. Throughout this work, we investigate LPS in the context of λ -switching, which supports reassignment of the specific wavelength consumed throughout a portion of the light path’s lifetime. Note that λ -switching is not synonymous with intra-route wavelength conversion. The reader is reminded that wavelength continuity is enforced throughout all light path solutions for each specified time-slot, however the wavelength itself may be altered from one slot to the next. ³ An example light path which undergoes λ -switching three times along its fixed route is illustrated in Fig. 2. A vast set of novel RWA solutions incorporating degrees of λ - switching have been developed, with the problem domains them- selves proven to belong to the complexity class NP-Complete. All of these problems have been modeled and evaluated through the development of ILP formulations, performance bounds, and heuristic algorithms. Findings of thorough performance analysis indicate that λ -switching offers enormous potential for resource utilization efficiency. This conclusion is supported by quantitative observation using metrics which measure resource consumption efficiency improvement at various degrees of multi-dimensional resource granularity. Proposed λ -switching heuristics have been determined to offer efficiency beyond even the analytically derived best-performance bounds of traditional time-continuous RWA solutions.

Further study has compared λ-switching with another LPS variant called Path-switching (P -switching). P - switching supports alteration to the route along which a light path is established with time-slot fidelity. P -switching encompasses the simpler λ-switching approach as establishing new routes inherently requires freely selecting wavelength carriers as well. We have found that λ-switching significantly outperforms its more flexible counterpart by almost all measures. Furthermore, when λ-switching and P -switching are both supported in tandem, the performance gain is insignificant in comparison to solutions supporting λ-switching exclusively. This prior work establishes the well informed approach of incorporating λ-switching with DA, as discussed in the following section.

the packets generation rate(frame/ms)

Fig.2. Switching and Allocation

• III.    Delayed λ -S WITCHING and Allocation

In this s ection we address challenges posed by supporting DA and λ -switching in a combined RWA solution, and present a novel three-phase DA- λ S scheduling algorithm. Its merits are qualitatively discussed here and then quantitatively evaluated in subsequent sections.

DA leads to blocking in two ways. During the RPP, an insufficient quantity of resources will result in a request being unsatisfied. The second source of blocking, only able to be determined during the RAP, is a lack of resource continuity throughout a light path’s intended schedule. In our prior works, when the DA heuristic encounters the second form of blocking, the request is simply blocked outright. In this work however, we apply λ-switching as an additional scheduling phase such that the technique is applied only when a request cannot otherwise be satisfied during the RAP. This process is engineered to determine if through switching the wavelengths of some reservations (with time-slot granularity), all currently provisioned requests can be allocated resources while also enabling the current (otherwise blocked) request to be supported. Essentially, any request that successfully completes the RPP is granted a greater likelihood to also successfully complete the RAP if λ-switching is supported. In the following section, we investigate the degree to which the switching technique can reduce RAP blocking of incoming demands.

Figure 3 presents an illustrative comparison demonstrating how the proposed three-phase delayed λ -switching and allocation approach can decrease blocking probability over the less flexible two-phase DA-only heuristic. We assume the existence of a simple two link network with three wavelengths available on each, to which four demands ( R ₁ , R ₂ , R ₃ , R ₄ ) arrive and must be provisioned. For purposes of clarity, we restructure each request to the form R r = ( α r , ω r , L r ) to describe its start-time, end-time, and constituent link set of each reservation’s route solution. Requests arrive in order and are provisioned in first-come, first-serve manner using the SSAR assignment procedure. The scheduler tracks the wavelength availability on each link to determine if a particular demand must be blocked upon arrival (RPP blocking).

Algorithm 1: Delayed Allocation with λ -Switching (DA- λ S Input  : R _demand | R_i ∈ R _demand = ( s_i,d_i,t_i,α_i,ω_i )

Topology tt = ( V ,E,W ,T )

• 1    Rprovision → ∅

• 2    for each t ∈ T do

• 3    for each R i ∈ R demand do

• 4    Pi ← Dijkstra ( si,di )

• 5    gi ← λAvailable ( Pi,αi,ωi,W ) if gi <  1 then

• 7    BLOCK Ri

• 8    else

• 9            Rprovision.add ( Ri )

• 10   for each Rj ∈ Rprovision do

• 11    if αj == t then

• 12    gj ← λ Continuous ( Pi,αi,ωi,W )

• 13    if gj ≥ 1 then

• 14    Allocate ( Rj , W , T )

• 15    break

• 16    else

• 17 . Resource Switching Phase( Rj ,limit DD )

Algorithm 2: Resource Switching Phase (RSP)

Input : R j

Rprovisionli mD

• 1    f = False

• 2    while f do

• 3    R DD ^ Dependency ( R j , limitDD )

• 4    foreach R dd ∈ R DD do

• 5    R λ → ∅

• 6    if Movable ( R dd ) then

• 7    R _A .add ( R dd )

• 8    foreach R l ∈ R λ do

• 9    foreach R n E Dependency ( R l , 1 ) do

• 10    if Movable ( R n ) then

• 11    R x .add ( R n )

• 12    g j ^ ^ C ontinuous ( P i, a i,mi, W )

• 13    if g j 5 1 then

• 14    foreach R m ∈ R λ do

• 15    ALLOCATE( R m , W , T )

• 16    ALLOCATE( R j , W , T )

• 17    f=True

• 18    Break all

• 19    if f=False then

• 20    BLOCK R j

• 21    break

Figure 3(a) illustrates request allocation of requests at time t 2 . R 1 , R 2 , and R 4 all require scheduling during this time-slot. R 3 is not scheduled to begin until the following time-slot and is thus not yet allocated, despite its arrival to the network prior to R ₄ . Not that at t ₂ there is a single non continuous wavelength available on each link of R ₃ ’s path. R ₃ has therefore successfully proceeded through the RPP without blocking. Figure 3(b) shows the resource assignment at t 3 . Without λ -switching, R 3 would be blocked by the RAP due to insufficient continuity throughout the light path route. However, R 3 is now able to receive a continuous resource set on λ ₁ by λ -switching the already inprogress R ₁ . All requests are thus allocated resources during t ₃ as the direct result of supporting λ -switching. Note that in this example, only a single λ -switch operation is required, however multiple switches may be necessary at scale. The ability for each of these reservations to be moved to a different wavelength at the current time-slot is then inspected (Line 5), and those which can be moved are added to the set of LPS candidates (Line 7). Each candidate is then evaluated in terms of the ripple effect required to support the potential λ -switch operation. The reservation leading to the smallest ripple overhead invokes the LPS procedure, thereby re-allocating resources to that reservation and all affected reservations for the current time-slot only. If this procedure yields a successful solution, the incoming RAP-blocked demand will then be allocated (Lines 8-18). If no λ -switching solution leads to a state of complete satisfaction for all entries baseline two-phase DA heuristic with no LPS capability.

We have explored two categories of algorithmic variants. In the first category, the λ-switching DD is fixed to a value of 1. As such, the DA-λS heuristic is simplified such that only reservations with direct dependency to the RAP-blocked request will invoke λ-switching operations. This restriction eliminates any ripple effect. Despite this simplified variant, situations may arise when more than one conflicting reservation may need to undergo LPS to facilitate the incoming light path’s establishment on each link along its route. As such, in this category, we impose an additional limit on the quantity of reservations which may be switched to prevent RAP-blocking. Figure 5(a) illustrates blocking probability of this scenario for various limit thresholds. This figure shows that blocking probability of DA without λ-switching is much higher than with λ-switching. The improvement is up to 35%, however the relative performance improvement of supporting a higher LPS limit is negligible. Note that the RSP is applied only for RAP-blocked requests, and therefore we find that a simple limitation of just one permitted λ-switch cost is equivalent to a more costly permission on overall blocking. This indicates that the majority of RWA blocking occurs during the RPP due to lack of resource availability. Figure 5(b) shows the performance increase of λ-switching on DA exclusively for RAP-blocked demands. Increasing the λ-switching limit can decrease blocking that is due to fragmentation dramatically. We find however, that the performance improvement from increasing the LPS limitation beyond a value of 2 is not significant.

Speed Performance

-40 ----------------------- с-----------------------[-----------------------с-----------------------1-----------------------[-----------------------

О          5          10          15         20         25         30

Time (sec)

Fig.4. Comparision between RWA and RAP

(a) RWA Blocking: DD=1.      (b) RAP Blocking: DD=1

Fig.5. Display blocking performance

The second category explored does not restrict DD to a limit of 1. Rather, the ripple effect is permitted, and no limit is placed upon the number of requests which must be re-allocated to prevent RSP blocking. The LPS over head from this category is expected to be significantly higher than the first. Figure 5(c) shows once again that DA-λS exhibits lower blocking than the baseline DA approach. No significant performance improvement is observed for values of DD ≥ 1.

Figure 5(d) displays the blocking performance imposed by the continuity constraint during the RAP. LPS impact is dramatic. and leads to an order of magnitude performance improvement. Furthermore, increasing the value of DD to 2 offers blocking reduction beyond what was observed in the limited switching scenario with DD restricted to 1. These results showcase the benefit of supporting LPS ripple. Note however, that the improvement is not visible for values of DD ≥, because resource fragmentation is exceedingly low in those scenarios.

The tradeoff in terms of LPS overhead is shown in Fig. 6. The figure illustrates the average number of requests that need to perform λ-switching in order to support successful completion of the RSP. The data shown is normalized against the quantity of successful light path establishments. Comparing Figure 6(a) and Figure 6(b) shows that first approach (DD = 1, limited LPS) has a lower number of λ-switching operations. This is unsurprising, given the nature of the limited approach. Supporting higher DD limits increases the cost substantially, indicating a higher RAP-RSP complexity, and potentially scheduling delay. These results support the notion that  λ-switching   is an effective supplementary enhancement to DA, but that low DD limits should be imposed to lower the costs of implementation.

• IV. Conclusion

In this work we have investigated the problem of wavelength allocation using the proposed combined approach employing both DA and λ-switching. Various approaches for reducing call blocking and mitigating associated overhead cost and complexity are presented and evaluated. Three-phase   DA-λS   blocking improvement depends on the number of LPS operations permitted, and holds potential for dramatically minimizing RAP blocking over baseline two-phase DA. In the context of overall blocking, the impact is less significant, but still sizeable. Future works include modeling flows for optimization under DA with and without λ-switching. The impact of spectral LPS on elastic optical networks is also worth investigation.