# Availability-Aware Dynamic RSA with Protection using Consecutive Sub-
Channels

Varsha Lohani  Anjali Sharma  Yatindra Nath Singh

###### Abstract

Flexible grid Optical Networks provide efficient spectrum utilization by
employing the mechanisms to provide flexibility in the optical channel
(spectrum slot) sizes. One of the research problems in Flexible grid Optical
Networks is its survivability against failure. On the other hand, p-Cycles
have not found practical use due to significant compute time required for
finding optimal configuration for the size of networks seen in real-life.
Therefore, for real-time scenarios, we can write heuristics which can assign
protection to the new working paths without disturbing the existing traffic on
all the other routes in flexible grid networks. The provisioning of protection
to each link or path of the lightpath requests can be done using Dynamic
Cycles (D-Cycles) or Dynamic Shared Backup Resource Protection (D-SBRP).
However, protecting each link or path can lead to the wastage of the resources
in the network.

##  I Introduction

p-Cycles offer ring-like switching speed and mesh-like spare capacity
efficiency for providing protection against link failures. They can also
protect all the links in a network against simultaneous failures of multiple
links [1]. But it has been mostly studied for single link failure scenarios in
the networks with the objective to minimize spare capacity under the condition
of $100\%$ protection for any single link failure scenario.

p-Cycles have not found practical use, only due to significant compute time
required for finding optimal configurations for the size of networks seen in
real-life. Therefore, [2] investigated the sub-graphing method to reduce the
compute time for finding the p-cycles. Partitioning of network was used for
finding the real-time protection provisioning. It was shown that protection
can be achieved much more quickly as a consequence of the sub-graphing.

Another alternative approach to achieve real-time protection is to make local
information-based decisions using heuristics at all the nodes. The algorithm
from [2] can be compared with such actual real-time scenarios where the
protection is computed heuristically on need basis. In dynamically maintained
protection, when a p-cycle is not protecting any working path, it can be
dismantle to release the capacity. The existing p-cycles should be used
whenever possible with suitable modifications. In the considered scenario, it
is possible that we can set up a working path but cannot provide protection to
all of its constituent links. This constraint exists because of limited spare
capacity in practical networks, though the p-cycles in the network can be
merged or expanded to minimize the required protection capacity.

We expect that the proposed scheme may not always work with optimum capacity
but can be pushed towards optimality as the network operates. While by
partitioning, we can only periodically compute the optimal configuration and
reconfigure the operating p-cycles to achieve optimality. The dynamic
creation, dismantling, merger, and expansion of p-cycles are not done while
using partitioning method, thus achieving a sub-optimal performance most of
the time except at the instants just after the periodic re-configurations.
Also, the ILP for a partition should consider the total fixed capacity in all
the links for both working and protection capacities. The objective of ILP
will change to provide maximum protection within the available resources, but
sometimes the optimal solution may not provide $100\%$ single fault tolerance.
This is the problem one will face while using ILP based solution in real-time
network operation.

Alternatively, for real-time scenarios, we can write heuristics where we can
assign protection to the new working paths without disturbing the existing
paths and the traffic carried by them. The provisioning of protection to each
of the links or the whole path assigned to a lightpath requests can be done
using Dynamic Cycles (D-Cycles) or Dynamic Shared Backup Resource Protection
(D-SBRP). However, protecting each link or path can lead to the wastage of the
resources in the network.

An alternative approach for a real-time situation is to provide protection
based on the Availability of the link or path. Availability is the probability
that the Path or links are working at any random time t. Availability decides
the resilience of the networks. In other words, if the Availability of a link
or path is higher than some threshold value, then there is no need for
protection. However, if the Availability is lower than the threshold, then
protecting some of the links can improve the overall Availability of the path.
This approach provides protection, while requiring lesser spare capacity111it
means less contribution from the total capacity to the spare capacity..
However, there is no guarantee of $100\%$ restorability.

##  II Problem Statement

Protection means apriori assignment of spare capacity, to be used in case of
link or node failure in the middle of a call. Backup paths setup using spare
capacity provide protection to restore the communication in the event of
failure. p-Cycles have been considered for protection against link failure in
quite a good amount of literature. They are one of the best methods to provide
most efficient protection and achieve much faster restoration speeds in case
of failures. However, computing p-cycle apriori normally requires large
computation time. In addition, if sufficient resources are not there to setup
the p-cycles, the call cannot be protected, and there is wastage of time in
attempting to compute them. A similar problem occurs with Failure-Independent
Path Protecting (FIPP) p-cycles, which provision pre-computed and pre-
connected protection to the working paths [5]. Therefore, we propose a method
for protection in which cycles are provisioned on the fly dynamically in the
networks on need basis.

Another parameter of interest considered in this paper is the Availability of
optical links and hence the path formed with the links, before provisioning
for the protection. Chen et. al [6] proposed analysis for service availability
using p-cycles protection techniques. They proposed a theoretical model on the
service availability when using p-cycles, considering all the possible
scenarios. The algorithms were based on the already proposed ones, and were
compared with the existing algorithms for p-cycle design. Algorithms for
availability analysis using Dedicated Path Protection and Shared Backup Path
Protection [7] were also proposed. They analyzed the service availability of
various protection systems in EONs theoretically and then suggested an
algorithm that could adjust the path protection scheme to meet various service
availability needs. In [8], mathematical modeling of the Availability-aware
FIPP p-cycles in Flexi- grid optical networks was given and cyclic
partitioning was proposed for protection provisioning.

Some of the research works [9] have used availability analysis for validation
of their work related to protection provisioning. In most of the works,
protection arrangements (and hence capacity) are computed even before a
lightpath request arrives. The protection paths are mostly computed
considering distance or hops as a parameter for computation.

##  III Proposed Solution

In this paper, we consider consecutive spectrum slots (used for RSA in [10])
for backup path computation. For networks with dynamically arriving and
departing traffic, we propose a method for link protection that is a modified
form of p-Cycles and we call it Dynamic Cycles (D-cycles) as they are formed
and dismantled dynamically on need basis. Similarly, for path protection, we
are using Dynamic Shared Backup Path Protection with Spectrum Slots Sharing.
However, provisioning protection to each link or path of the lightpath
requests leads to wastage of spare capacity. Also, it increases blocking of
the requests as load increases. Instead we have considered availability as a
parameter for best-path selection and provisioning of protection.

In this paper, first, we will discuss protection techniques used. Reliability
and Availability of a link and path will be discussed in the subsequent
section. The Availability of paths in various scenarios is explained with the
help of examples. Finally, we will present the proposed algorithms and
evaluate its effectiveness.

##  IV Protection Techniques

Optical networks need to carry a large volume of data traffic while
maintaining service continuity even in the presence of faults. If not
automatically protected and restored within a short time after failure, even a
single link failure will result in loss of significant amount of data.
Therefore, survivability against link or path failures is a necessary design
requirement for high-speed optical networks.

This paper first explores path protection for real-time scenarios, i.e.,
Dynamic Shared Backup Path and Spectrum Slots (DSBPSS) [11]. Total traffic
from all the primary paths passing through a failed link is switched to backup
protection paths whenever restoration is done.

Another technique for protection, proposed by us is Dynamic Cycles (D-cycles)
for link protection. In link protection, the traffic through the faulty link
is restored via another path joining the two endpoints of the link. The
switching speed of link protection is faster than the path protection. Also,
fault detection is localized in link protection. Further all paths passing
through the failed links are restored as single event, unlike path protection.
However, each protection switch over will require spectrum converters.

###  IV-A Dynamic Shared Backup Path and Spectrum Slots

In Dynamic Shared Backup Path and Spectrum Slots (DSBPSS), a single backup
path protects a number of disjoint primary working paths with an extra feature
of sharing the spectrum slots. When a failure occurs in any one of the primary
paths, then the failed path’s traffic is switched to the backup path. The
primary paths must be link-disjoint with the backup path as well as among
themselves. After the setup lightpath are released, the backup paths are also
dismantled.

Figure 1: DSBPSS for three working paths.

Figure 1 shows an example of DSBPSS. There are three working lightpath
requests A-B-C-D, B-E and A-F. For lightpath requests A-B-C-D with three
slots, backup path A-F-E-D with three slots is provisioned. Whereas for
lightpath request B-E with two slots, backup path B-F-E with two slots is
provisioned, and for lightpath request A-F with a single slot, backup path
A-B-F with one slot is provisioned. The link F-E is common for protection of
two working paths such that the protection slots are shared by both the
working paths. The links of the working paths are disjoint.

Consequently, the failure of one of the working paths cannot affect the other.
We consider the probability of the simultaneous failure of the two paths to be
very low. Here, WP represents working path and BP is for Backup Path. Each of
the paths is provisioned with the spectrum slots on disjoint backup paths. If
the spectrum slots are not available on the backup path, another backup path
is checked. If available, then it will be provisioned. Else the path remains
unprotected.

  * Pros
  * •

Backup Path can protect against the failure of both the intermediate nodes as
well as the constituent link failures. The switchover happens at the source
and destination nodes.

  * •

There is no need for spectrum converters for switching from Working Path to
Backup Path.

  * Cons
  * •

The switching speed of the path protection scheme is slower than the link
protection schemes.

  * •

If there is a single link failure, the spectrum slots used on other links of
the working paths are no more in use after the restoration. In other words,
useful slots get wasted during restored operation. Though these slots are now
available for other request setups.

  * •

When a link fails, all the paths passing through it are to be restored using
backup paths. This creates a kind of sudden burst of multiple path
configurations all across the network.

####  IV-A1 Conditions for Backup Slots Assignment

For backup slots assignment for protection while using RSA using DSBPSS,
various conditions are required to be followed.

(a)

(b)

(c)

(d)

Figure 2: Backup Slot Assignment.

#### Condition I: Working paths have non-disjoint links.

Active working and Current working path requests share links and thus allotted
different slots for working capacity, and their corresponding backup paths are
link-disjoint among themselves as well as with working paths, thus the
allocated backup slots are independent being on different backup paths as
shown in figure 2(a).

Let us consider active lightpath request, B-C with three slots requirement,
and its corresponding backup path B-E-C is used for protection as shown in
figure 2(a). Whereas current lightpath request B-C-D with two slots
requirement, its corresponding backup path B-F-E-D can be used for protection.
The link B-C of active and current lightpath request are shared. Therefore,
the allocated backup links and slots must be disjoint otherwise only one of
path or link is protected in the event of failure on link B-C. Here, WP
represents working path and BP is for Backup Path.

#### Condition II: Working paths and Backup Paths are link-disjoint

Active working and Current working path requests are link-disjoint and their
corresponding backup paths are also link-disjoint, then allocated backup slots
are always disjoint being on different links.

Let us consider active lightpath request, B-C with three slots requirement,
and its corresponding backup path B-E-C is used for protection as shown in
figure 2(b). Whereas current lightpath request A-B with two slots requirement,
its corresponding backup path A-F-B is used for protection. Since WPs and BPs
are link disjoint therefore the allocated backup slots are also link-disjoint.

#### Condition III: Working paths are link-disjoint and Backup paths links are
non-disjoint

Active working and Current working path requests are link-disjoint and their
corresponding backup paths share links, then allocated backup slots can be
shared on the shared links.

Let us consider an active lightpath request, A-B-C-D with three slots
requirement, and its corresponding backup path A-F-E-D is used for protection
as shown in figure 2(c). Whereas current lightpath request B-E is with two
slots requirement, its corresponding backup path for protection is B-F-E.
Since the WPs are link-disjoint, therefore, their BPs can share links as well
as slots.

#### Condition IV: Working paths and Backup paths links are non-disjoint

Active working and Current working path requests share some links and assigned
different slots on shared links. Their corresponding backup paths also share
links, then slot shareability is not feasible on backup paths and disjoint
slots should be considered for backup provisioning.

Let us consider active lightpath request, A-B-C-D with three slot requirement,
and its corresponding backup path A-F-E-D is used for protection as shown in
figure 2(d). Whereas current lightpath request A-B-F is with one slots
requirement; its corresponding backup path A-F is used for protection. Since
the WPs and BPs are not link-disjoint. Therefore, the slots assigned for
protection should be disjoint.

###  IV-B Dynamic Cycles (D-Cycles)

In [10], we considered contiguous and continuous spectrum slots for Routing
and Spectrum Assignment. A similar algorithm is also used in this paper for
finding backup paths. Since we are using parameters that change with the
network conditions, instead of pre-configured-Cycles, Dynamic cycles are used.

The D-cycles technique is a backup path-finding technique to protect the links
against failures. Whenever a lightpath request arrives, there should be a
backup to each link in the lightpath requests to protect the traversing
demand. If there is a requirement of the backup path for some link, a cycle is
formed around it, and assignment of slots is made, to be used when protection
is activated. Considering that no two links fail simultaneously, if different
links on the cycle require backup, then the slots can be shared. After the
requests are released on completion of connection duration, the cycles if no
more needed, are also dismantled. Since there is no pre-configuration of the
cycles, i.e., cycles are formed on the fly, these cycles are called Dynamic
Cycles (D-cycles).

(a)

(b)

(c)

Figure 3: Dynamic Cycles for three working paths.

Figure 3 shows an example of Dynamic Cycles. There are three working lightpath
requests A-B-C, F-E-D, and F-B-E.

In figure 3(a), Working Path WP1 (A-B-C) with two slots requirement is setup.
Considering at max a single fault, a d-cycle A-B-C-E-F-A is created to protect
Working Path, WP1.

Another Working Path, WP2 (F-E-D) with two slots requirement is the next one
created, as shown in figure 3(b). Considering single fault, same d-cycle A-B-
C-E-F-A can be used to protect link F-E of WP2. For link E-D either we can
create second d-cycle or as we have done in the figure here, extend the
existing d-cycle to A-B-C-D-E-F-A. Since, only single link needs protection in
case of failure, backup slots used can be shared.

Working Path, WP3 (F-B-E) with two slots requirement, is the next one to be
setup as shown in figure 3(c). Same d-cycle A-B-C-E-F-A can be used to protect
WP3. Here, link F-B and B-E are straddling links. Since, only single link
needs protection in case of a failure, shared backup slots used on A-B-C-E-F-A
can be used for protection of WP3 links. Here, two slots D-Cycle can be used
to protect four slot working paths on the straddling links.

Here, each of the links in the requests is provisioned with a d-cycle. The
spectrum slots are shared for different lightpath requests. Also, working
links should be disjoint. As sharing of slots cannot be done if the working
links are not disjoint. If the sharing of slots does not follow this
constraint and a link fails, only one path can be protected; the other paths
simply breaks.

  * Pros
  * •

Incorporates the advantages of efficiency of mesh and protection speed of ring
networks.

  * •

The switching speed of link protection ($<50milliseconds$) is much faster than
the path protection due to the faster fault localization.

  * •

Only the affected link on a path is provisioned with backup. All other links
on the path remain intact.

  * •

As only one link is protected, there is no storm all across the network for
setting up protection paths for all the paths passing through the failed link.

  * Cons
  * •

Costly spectrum converters (waveband shifters) are needed at the end nodes of
the failed link, for restoring the paths.

The provisioning of a backup path for every link or path increases redundancy.
In this thesis, we are using the Availability of an optical link and path to
decide on if the costly protection should be provisioned or not, for a link.
We discuss Reliability and Availability in the next section.

##  V Reliability of an Optical Path

The reliability of an optical path is the probability that all of its links
are working without failure for an expected duration [12]. The availability of
each link is needed for the reliability analysis of a path. An optical path is
a sequence of series-connected optical links and it will work if and only if
all of its links are working.

Consider a path p consisting of l links and suppose that each one of them is
in either working or failed state. To indicate whether each link is working or
not, we use a binary indicator variable $x_{i}^{p}$ as represented by equation
1;

$x_{i}^{p}=\begin{cases}1,&\text{if $i^{th}$ link of path {p} is working,}\\\
0,&\text{otherwise.}\end{cases}$ (1)

The state vector ${x^{p}}=(x_{1}^{p},x_{2}^{p},......,x_{l}^{p})$ indicates
the state of the constituent links of the path p i.e., either they are working
or failed [13]. For lightpaths, whether or not the whole path is working or
not is determined by the structure function $\pi_{p}(x^{p})$ of the path and
indicated by equation 2;

$\pi_{p}(x^{p})=\begin{cases}1,&\text{if the path {p} is working when}\\\
&\text{the state vector is x,}\\\ 0,&\text{otherwise.}\end{cases}$ (2)

As we know the lightpath consists of series of independent links. Therefore,
the structure function of series system is given by equation 3;

$\pi_{p}(x^{p})=\prod_{i=1}^{l}x_{i}^{p}.$ (3)

Let us explain this with the help of an example. Consider a four-nodes and
three-links lightpath as shown in figure 4. $\pi_{p}(x)$ for the lightpath is
given in table I using the above equations [13].

Figure 4: A four-nodes and three-links lightpath request where $x_{1}$, $x_{2}$, and $x_{3}$ are the binary variables representing whether corresponding links are working or not. $x_{1}$ | $x_{2}$ | $x_{3}$ | $\pi(x)$
---|---|---|---
0 | 0 | 0 | 0
0 | 0 | 1 | 0
0 | 1 | 0 | 0
0 | 1 | 1 | 0
1 | 0 | 0 | 0
1 | 0 | 1 | 0
1 | 1 | 0 | 0
1 | 1 | 1 | 1
TABLE I: Different states of the links of an optical path with four-nodes and
three-links, where 1 represents that the link is working and 0 represents that
the link is in the failed state.

Let us suppose $X_{i}$ be a random variable that represents the state of the
$i^{th}$ link.

$P\\{X_{i}=1\\}=p_{i}=1-P\\{X_{i}=0\\}.$ (4)

$p_{i}$ in equation 4 is the probability that the $i^{th}$ link is working,
and is defined as the Reliability of the $i^{th}$ link. Therefore, reliability
function r(p) of an optical path p with series of connected independent links
is given by

$r(p)=P\\{\pi_{p}(x^{p})=1\\}.$ (5)

Reliability of an optical fiber link can be modeled with the help of Bathtub
curve as shown in figure 5. It maybe noted that the reliability is computed
for non-repairable systems.

Figure 5: Bathtub curve [14] representing the failure rate in an optical fiber
link with time.

The optical fiber links are repairable components. Therefore, in this thesis,
we consider Availability of an optical fiber instead of reliability, which
takes into account both failures and repairs.

##  VI Availability Analysis of an Optical Path

Consider a path with l links having reliability $r(p)$. Let us suppose, all
the links are working initially.

$A(t)=P\\{path\ is\ working\ at\ time\ t\\}$ (6)

A(t) is the availability of an optical path at time t, and $A_{e}(t)$ is the
availability of $e^{th}$ link at time t [13]. Since we are considering
repairable link, so a link can be in two states i.e., under repair after
failure and normally operating.

Availability of an optical path can be represented as

$A_{p}(t)=\prod_{e\in P}A_{e}(t),$ (7)

where p is the lightpath request and e is the link belonging to path P.

Figure 6: Availability analysis of a link.

In figure 6, MTTF is the Mean Time To Failure, MTTR is the Mean Time To Repair
and MTBF is the Mean Time Between Failures. $E_{1}$ is the event when first
failure occurs. After a certain repair time, event of link getting repaired
$E_{2}$ happens and next failure happens as event $E_{3}$ and so on.

Suppose that the link works for an exponentially distributed time with rate
$\lambda^{\prime}=\dfrac{1}{MTTF}=\dfrac{1}{MTBF}$ and then fails. Once
failed, it takes an exponentially distributed time with rate
$\mu^{\prime}=\dfrac{1}{MTTR}$ to be repaired. Therefore, Availability of an
optical link $e$ is

$A_{e}(t)=\dfrac{\ MTTF}{\ MTTF+\ MTTR},\text{ or}$ (8)

$A_{e}(t)=\dfrac{\ MTBF}{\ MTBF+\ MTTR}.$ (9)

MTTF (MTBF) is the average time of link operations since start (last repair)
to next failure. MTTR is the average time needed to repair the link.

###  VI-A Availability of Different Systems

In this section we will show how to compute the Availability of different
systems [13], assuming each link to be independent.

####  VI-A1 Series System

An optical lightpath is series-connected optical links or edges, where a link
$e\in E$; E is the set of edges in the optical network.

Figure 7: Series-connected optical path.

.

Figure 7 shows series-connected links forming an optical lightpath. A five
nodes four links lightpath has Availability of each link as
$A_{a-b},A_{b-c},A_{c-d},$ and $A_{d-e}$. The Availability of the series-
connected path is given by

$A_{series}=\prod_{e\in P}A_{e},$ (10)

where $A_{series}$ is the Availability of a series-connected path, and $A_{e}$
is the Availability of a link e belonging to path P. Thus, the Availability of
path in figure 7, is given by

$A_{series}=A_{a-b}A_{b-c}A_{c-d}A_{d-e}.$ (11)

The above is an example of series-connected system of working lightpath with
no backup.

####  VI-A2 Parallel System

In parallel system, redundant paths are found between source-destination
pairs. In other words, the connection of multiple series paths for a single
source-destination pair forms a parallel system (figure 8).

Figure 8: Parallel connected optical paths from a to e.

$A_{parallel}=1-(1-\prod_{e\in P_{l}}A_{e})^{l},$ (12)

where $A_{parallel}$ is the Availability of a path between source and
destination through parallel connected provisioned capacity, $A_{e}$ is the
Availability of a $e^{th}$ link belonging to path $P_{l}$ where l is the
number of redundant paths.

$A_{p^{\prime}}=A_{a-b}A_{b-c}A_{c-d}A_{d-e}$ (13)

$A_{p^{\prime\prime}}=A_{a-f}A_{f-g}A_{g-h}A_{h-i}A_{i-e}$ (14)

$A_{p^{\prime\prime\prime}}=A_{a-j}A_{j-k}A_{k-l}A_{l-m}A_{e-m}$ (15)

Here, $A_{p^{\prime}}$, $A_{p^{\prime\prime}}$, and
$A_{p^{\prime\prime\prime}}$ are the Availability of a three parallel
connected paths. Availability of a parallel system as shown in figure 8 is
given by

$A_{parallel}=1-((1-A_{p^{\prime}})(1-A_{p^{\prime\prime}})(1-A_{p^{\prime\prime\prime}}))$
(16)

An example of a parallel connected system is Shared Backup Path Protection,
where for a working path, multiple backup paths can be provisioned depending
upon the number of simultaneous failures expected. In the example of figure 8,
double faults can be tolerated, i.e., one fault on the working path and
another one on the backup path. Third path can be used as a backup for the
working path in case of two faults. Due to redundancy,
$A_{parallel}>A_{series}$.

####  VI-A3 Series-Parallel System

In series-parallel system, the backup paths for series connected links are
computed only for the affected (failed) links. In other words, a series system
is converted into series-parallel when there are faulty links. Additional
resources needed in such systems are less as compared to parallel systems.

Figure 9: Series-connected optical path with Parallel-connected backup path
for an optical edge $c-d$.

$A_{series-parallel}=\prod_{e\in
k}[1-((1-A_{e})(1-A^{\prime}_{e}))]\prod_{e\in L-k}A_{e},$ (17)

where k is the set of links which can go faulty. L is the set of links in the
working path, $A_{e}$ is the Availability of link e, and $A^{\prime}_{e}$ is
the Availability of protection path for link e.

$A_{series-parallel}=A_{a-b}A_{b-c}(1-(1-A_{c-d})(1-(A_{c-f}\\\
A_{f-g}A_{g-h}A_{h-d})))A_{d-e}.$ (18)

Equation 18 is the Availability of series-parallel system for figure 9. In
this example, out of four links, one link with low availability is provided
with backup path.

Examples of series-parallel systems are working paths with p-cycles or
d-cycles protecting the fault prone links.

##  VII Proposed Algorithms

In this paper, we propose two algorithms based on the availability of the
links and paths. For Routing and Spectrum Assignment of a Working path, we use
the algorithm from [10], i.e., Type II: Routing and Spectrum Assignment based
on Consecutive Spectrum Slots. For a Backup path, static parameters such as
hops or distance can increase the time complexity within the network. For
example, if we find the alternate backup path using the shortest path
algorithm, sometimes the required resources may not be available. Finding the
required resources becomes more challenging as the number of incoming requests
per unit time (or load in the network) increases. Instead of the shortest path
algorithm for the backup path, we use the Type II Algorithm for the backup
path also.

###  VII-A Notations Used in the Algorithms

  * •

$G(V,E,\\{\Delta_{e}\\})$: represents an optical network as a graph.
Here,

    * $V$ is the set of nodes represented as vertices of the graph, indexed by v,

    * $E$ is the set of optical fiber link represented as edges of the graph, indexed by e, and

    * $\Delta_{e}$ is the sequence of 1s and 0s to model the availability status of the spectrum slots on the edge $e\in E$.

  * •

$LR(s,d,\\{\Delta^{r}\\},k)$ is a Lightpath Request where

    * $s$ is the source node, $s\in V$,

    * $d$ is the destination node, $d\in V$ ,

    * $\Delta^{r}$ is the bitmap of required contiguous and continuous spectrum slots from $s$ to $d$, and

    * $k$ is a positive integer. It is the maximum number of paths to be computed by RSA.

  * •

$\Delta_{p}$ is the bitmap of available spectrum slots in path $p$ from $s$ to
$d$.

  * •

$(u,v)$ is the edge joining the pair of vertices (u and v), where $u$ is the
starting (head) node and $v$ is the ending (tail) node.

  * •

$A_{p}^{max}$ is the Maximum Availability of the working path selected from
the set of candidate working paths.

  * •

$A_{pp}^{max}$ is the Maximum Availability of the working path that needs
protection.

  * •

$A_{bp}^{max}$ is the Maximum Availability of the backup path selected from
the set of candidate backup paths.

  * •

$A_{th}$ is the Threshold Availability.

Algorithm 1 is the Routing and Spectrum Assignment with Consecutive Slots
(RSACS) algorithm used for finding both working paths as well as backup paths.
In this algorithm, CandidatePaths() function (Algorithm 2) is used to find set
of candidate working paths from source node to the destination node. It also
returns the value of the Availability $A_{p}$ of each candidate path $p$. The
function of CandidatePaths() has already been explained in paper (DRSA).

In the algorithm RSACS with Protection provisioning based on the Availability
of the path, we select the path with maximum availability $A_{p}^{max}$. The
backup path provisioning is done based on the Availability of the path
$A_{p}$. The decision of whether to consider a path with protection
provisioning depends on the value of the Availability Threshold, $A_{th}$. The
protection is provisioned for the paths whose Availability $A_{p}^{max}$ value
is less than the threshold value. Then the notation of $A_{p}^{max}$ changes
to $A_{pp}^{max}$, i.e., the Maximum Availability of the working path that
needs protection. Depending on the protection type, the backup paths are
provided to the less available working paths or links.

We consider two types of protection. First is Dynamic Shared Backup Path and
Spectrum Slots (DSBPSS) are used for path protection with slot sharing.
Another one is Dynamic Cycles (modified p-Cycles), used for link protection
with slot sharing.

Algorithm 1 RSACS with Protection provisioning based on Availability of the
path

1:Input: $G(V,E,\\{\Delta_{e}\\},A_{e})$,
$LR(s,d,|\Delta^{r}|,k),A_{th},BackupPaths,DCycles$

2:$AllPath\leftarrow$ A set of candidate paths from $s$ to $d$ using
CandidatePaths($G(V,E,\\{\Delta_{e}\\},A_{e})$, $LR(s,d,|\Delta^{r}|,k)$) and
the Availability $A_{p}$ of the candidate paths p $\triangleright$ Algorithm 2

3:if $AllPath$ is not empty then

4: Select the path with highest Availability $A_{p}^{max}$ from all then paths
listed in AllPath and store in BestPath

5: if $A_{p}^{max}<A_{th}$ then

6: $A_{pp}^{max}=A_{p}^{max}$

7: if Protection type is DSBPSS then

8: $BackupPath$ =
DSBPSS($G(V,E,\\{\Delta_{e}\\},A_{e}),LR(s,d,|\Delta^{r}|,k),BestPath,$
$BackupPath,A_{pp}^{max},A_{th}$) $\triangleright$ DSBPSS function is used for
path protection

9: if $BackupPath$ is not empty then

10: $BackupPaths=BackupPaths+BackupPath$

11: Return $BestPath$, $BackupPaths$

12: else

13: Return $BestPath$

14: end if

15: else

16: $Cycles$ = Dcyc($G(V,E,\\{\Delta_{e}\\},A_{e}),LR(s,d,|\Delta^{r}|,k),$
$BestPath,A_{pp}^{max},A_{th},Cycles$) $\triangleright$ Dcyc function is used
for link protection. Here, list of links which are protected and updated
cycles (each cycle is list of links) should be returned, such that
$A_{pp}^{max}\geq A_{th}$

17: if $Cycles$ is not empty then

18: $DCycles=DCycles+Cycles$

19: Return $BestPath$, $DCycles$

20: else

21: Return $BestPath$

22: end if

23: end if

24: else

25: Return $BestPath$

26: end if

27:else

28: Block the request

29:end if

Algorithm 2 CandidatePaths() $\rightarrow$ Path with contiguous slots $\geq$
$\Delta^{r}$

1:function CandidatePaths($G(V,E,\\{\Delta_{e}\\},A_{e})$,
$LR(s,d,|\Delta^{r}|)$, $k$)

2: $AllPath$ = [ ] $\triangleright$ $AllPath$ contain paths and their
availability.

3: $Path=[s,1]$ $\triangleright$ Element of Path and its availability.

4: while $Path$ is not empty do

5: $tmp$ = [ ]

6: for all paths in Path indexed by $i$ do

7: $u=Path(i).end$

8: $\\{v\\}=\textsc{Adj}(u))\backslash Path(i)$ $\triangleright$ All
neighbours of u which are already not there on the Path(i).

9: if $\\{v\\}\neq$ [ ] then

10: for all nodes in $\\{v\\}$ indexed by $j$ do

11: $\Delta_{i}\leftarrow\Delta_{i}\cap\Delta_{(u,v(j))}$

12: if IsFeasible($(\Delta_{i},|\Delta^{r}|$) $==\textsc{True}$ then

13: if $v(j)==d$ then

14: $A_{p}=A_{p}\times A_{(u,v(j))}$

15: $AllPath=AllPath+[(Path(i),v(j));A_{p}]$

16: if $size(AllPath)==k$ then

17: Return: $AllPath$

18: end if

19: else

20: $A_{p}=A_{p}\times A_{(u,v(j))}$

21: $tmp=tmp+[(Path(i),v(j));A_{p}]$

22: end if

23: end if

24: end for

25: end if

26: end for

27: $Path=tmp$

28: end while

29: Return: $AllPath$

30:end function

Algorithm 3 IsFeasible()

1:function IsFeasible($(\Delta_{a},|\Delta_{b}|)$) $\triangleright$ IsFeasible
function checks the $|\Delta_{b}|$ number of contiguous slots are available in
the bitmap $\Delta_{a}$

2: if $|\Delta_{b}|$ can be accommodated in $\Delta_{a}$ then

3: Return: True

4: else

5: Return: False

6: end if

7:end function

###  VII-B RSACS with DSBPSS

Algorithm 4 DSBPSS()

1:function
DSBPSS($G(V,E,\\{\Delta_{e}\\},A_{e}),LR(s,d,|\Delta^{r}|,k),BestPath,BackupPathList,$
$A_{pp}^{max},A_{th}$)

2: $BackupPath$ = [ ] $\triangleright$ $BackupPath$ stores the backup path
values

3:
$G(V^{\prime},E^{\prime},\\{\Delta^{\prime}_{e}\\},A^{\prime}_{e})=\textsc{RemoveLinks}(G(V,E,\\{\Delta_{e}\\},A_{e}),BestPath)$
$\triangleright$ RemoveLinks function remove links of BestPath from
$G(V,E,\\{\Delta_{e}\\},A_{e})$. This is done for finding working links
disjoint backup paths

4:
$G(V^{\prime},E^{\prime},\\{\Delta^{\prime}_{e}\\},A^{\prime}_{e})=\textsc{FBS}(G(V^{\prime},E^{\prime},\\{\Delta^{\prime}_{e}\\},A^{\prime}_{e}),BackupPathList)$
$\triangleright$ FBS function find all locally free slots for backup path.
These slots may have been already allocated to other backup paths in
BackupPaths in
$G(V^{\prime},E^{\prime},\\{\Delta^{\prime}_{e}\\},A^{\prime}_{e})$. This is
done for slots sharing between backup links.

5: $BackupPaths\leftarrow$ A set of candidate paths from $s$ to $d$ using
CandidatePaths($G(V^{\prime},E^{\prime},\\{\Delta^{\prime}_{e}\\},A_{e})$,
$LR(s,d,|\Delta^{r}|,k)$) and their corresponding Availability $A_{bp}$
$\triangleright$ Algorithm 2

6: while $A_{pp}^{max}<A_{th}$ do $\triangleright$ Here $A_{pp}^{max}$ is the
availability of the protected path.

7: if $BackupPaths$ is not empty then

8: Remove the path with highest Availability from all paths listed in
BackupPaths and store in BackupPath with its corresponding $A_{bp}^{max}$
$\triangleright$ $A_{bp}^{max}$ is the availability of the backup path

9: else

10: Return: BackupPath = [ ]

11: end if

12: $A_{pp}^{max}=\textsc{AvaDSBPSS}(A_{pp}^{max},A_{bp}^{max})$

13: end while

14: Return: BackupPath

15:end function

In Algorithm 1 line number 8, if the protection type is DSBPSS, the function
in Algorithm 4 is used for finding path protection. The remaining candidate
paths in AllPath (Algorithm 1) cannot be used for backup path, since slots
sharing is not feasible as we want to find slots disjoint candidate paths in
$AllPath$ (Algorithm 1).

In DSBPSS() function, first RemoveLinks function is used to remove the links
from the graph. For finding link disjoint backup path, we first exclude the
current working path’s links from the graph locally. Now, for corresponding
backup path all locally free slots which may also have been allocated to all
the other backup paths are found using Free Backup Slots (FBS) function. It
allows already allocated backup slots also to be shared. Next, for finding
backup paths and their corresponding Availability, CandidatePaths() function
is used. The backup path with higher $A_{bp}^{max}$ is selected for the backup
path.

The backup paths availability is updated with the help of function as in
Algorithm 5. After updating the $A_{pp}^{max}$ value again, it is verified to
be greater than $A_{th}$ or not. If not, then from the list of backup paths
(excluding already selected backup paths), we select another path with maximum
Availability. Therefore, the working path is provisioned with redundant backup
paths until the $A_{pp}^{max}\geq A_{th}$.

Algorithm 5 AvaDSBPSS()

1:function AvaDSBPSS($A_{pp}^{max},A_{bp}^{max}$)

2: $A_{pp}^{max}=1-((1-A_{pp}^{max})\times(1-A_{bp}^{max}))$ $\triangleright$
$A_{pp}^{max}$ is updated after backup path provisioning.

3:end function

###  VII-C RSACS with D-cycles

In Algorithm 1 line number 8, if the protection type is Dcyc, the function as
in Algorithm 6 is used for link protection. A set of working links
$(l_{1},l_{2},l_{3},...)$ forms a working path (p).

Algorithm 6 Dcyc()

1:function
Dcyc($G(V,E,\\{\Delta_{e}\\},A_{e}),LR(s,d,|\Delta^{r}|,k),BestPath,A_{pp}^{max},A_{th},Cycles$)

2: Store in $A$ the value of Availability of the links $A_{e}$ used
$\triangleright$ $A$ store the values of the Availability of the links that
form the working path.

3: $BackupLinks$ = [ ]

4: while $A_{pp}^{max}<A_{th}$ do

5: Find $A_{l}$ = $Min_{l}$(A) $\triangleright$ $A_{l}$ is the Availability of
the minimum available link l.

6: if CheckCycles($Cycles,LR(s,d,|\Delta^{r}|,l)$) == True then
$\triangleright$ CheckCycles checks an existing cycle in Cycles can be used
for protection of link l.

7: $[Cycles,A^{max}_{bp}]$ = UpdateCycles($Cycles,|\Delta^{r}|,l$)

8: else if path $p^{\prime}_{1}$ alternate to l can be found then
$\triangleright$ Algorithm 2.

9: if check $p^{\prime}_{1}$ can be used to extend existing cycles then

10: $[Cycles,A^{max}_{bp}]$ =
UpdateCycles($Cycles,|\Delta^{r}|,l,p^{\prime}_{1}$)

11: else if path $p^{\prime}_{2}$ can be found as alternative to l, while
being node and link disjoint to $p^{\prime}_{1}$ except to the end nodes of l
then $\triangleright$ Algorithm 2.

12: Use $p^{\prime}_{1}$ and $p^{\prime}_{2}$ to form new cycles
$\triangleright$ $p^{\prime}_{1}$ and $p^{\prime}_{2}$ must be link disjoint.

13: $[Cycles,A^{max}_{bp}]$ =
UpdateCycles($Cycles,|\Delta^{r}|,l,p^{\prime}_{1},p^{\prime}_{2}$)

14: else if extra slots are there on link l, to form a cycle with l as oncycle
then

15: $[Cycles,A^{max}_{bp}]$ =
UpdateCycles($Cycles,|\Delta^{r}|,l,p^{\prime}_{1}$)

16: else

17: Return: No cycles found

18: end if

19: else

20: Return: No cycles found

21: end if

22: $A^{max}_{pp},A_{pl}=\textsc{AvaDcyc}(A^{max}_{pp},A_{l},A^{max}_{bp})$
$\triangleright$ $A_{pl}$ is the Availability of the protected link.
Availability of the least available link which is modified by provisioning of
the backup path to it.

23: $A=(A-A_{l})+A_{pl}$

24: end while

25: Return: Cycles

26:end function

In this method, the working link with minimum Availability (say $i^{th}$ link,
$l_{i}\in p$) is selected from the set of working links for protection
provisioning. For protection, cycles are formed using available capacity in
the network. We used CheckCycles() function to check whether protection is
feasible or not using existing cycles in Cycles. If no backup cycles found in
Cycles, then new cycles is formed for protection and stored in Cycles along
with their assigned slots.

New cycles can provide either on-cycle or straddling protection. For on-cycles
protection, set of backup paths are found using CandidatePaths() function for
least available link, $l$. It also returns the Availability of the backup path
$A_{bp}$. The path $p^{\prime}_{1}$ with higher $A_{bp}$ is selected for the
backup path. Out of three conditions, one should be satisfied as mentioned
below.

  * •

Check if $p^{\prime}_{1}$ can be used to extend existing cycles from Cycles,
then update Cycles and assign it for protection.

  * •

Find another path $p^{\prime}_{2}$ path as an alternative to link $l$, and it
should be node and link disjoint to $p^{\prime}_{1}$ except the end nodes of
$l$, such that it forms a straddling cycle with link $l$. Update Cycles and
assign it for protection.

  * •

If any of the above two conditions are not satisfied, then check if extra
slots are there on link $l$, to form a cycle with $l$ for on-cycle protection,
then update Cycles and assign it for protection.

Algorithm 7 AvaDcyc()

1:function AvaDcyc($A^{max}_{pp},A_{l},A^{max}_{bp}$)

2: $A_{pl}=1-((1-A_{l})\times(1-A^{max}_{bp}))$

3: $A^{max}_{pp}=\dfrac{A^{max}_{pp}\times A_{pl}}{A_{l}}$

4: Return: $A^{max}_{pp},A_{pl}$

5:end function

The backup paths availability is updated with the help of function in
Algorithm 7. After updating the $A_{pp}^{max}$ value again, check either it is
greater than $A_{th}$ or not. If not, then repeat the same procedure till the
working path is provisioned with sufficient redundant backup paths to achieve
$A_{pp}^{max}\geq A_{th}$.

If none of the conditions are satisfied to form a backup cycle, then the
working path is not protected.

##  VIII Numerical Results

In paper [DRSA], the algorithm that outperforms every other is Type II:
Routing and Spectrum Assignment based on Consecutive Slots. Therefore, we
proposed algorithms in which the working paths and backup paths are found on
the basis of contiguous and continuous spectrum available. The protection is
provisioned to only those paths or links which have lower availability than
the threshold values.

###  VIII-A Performance Metrics

The performance of the proposed algorithms is evaluated on the basis of
blocking of the incoming requests, blocking of the incoming required slots,
the spectrum utilization, Capacity Used for Protection and Restorability Ratio
with the gradual increments of demand rate (in Gbps):

  * •

Blocking Probability: It is defined as the ratio of total number of blocked
connections to the total number of arrived connections.

  * •

Bandwidth Blocking Probability: It is defined as the ratio of the total amount
of incoming bandwidth or slots blocked to the total amount of bandwidth or
slots required for all the connections.

  * •

Spectrum Utilization: The ratio of total bandwidth or slots used to the total
bandwidth or slots in the spectrum.

  * •

Capacity Used for Protection: It is the total amount of usable bandwidth used
for protection222only for the paths whose Availability of the link or path is
less than the Threshold Availability. .

  * •

Restorability Ratio: It is the ratio of total number of protected paths to the
total number paths requiring protection (sum of protected path and unprotected
paths). This ratio is only for the paths whose Availability is less than the
Threshold Availability333only for the paths whose Availability of the link or
path is less than the Threshold Availability. .

Figure 10: 14 nodes, 22 links NSFNET, with distance in km marked on the each
edge.

###  VIII-B Network Settings

To evaluate the efficacy of our proposed algorithms, we operated a set of
simulations experiments using MATLAB R2019b. The simulations are done for
1,00,000 requests with multiple iterations. The performance of proposed
algorithms - RSACS with Dynamic Shared Backup Path Protection and Dynamic
Cycles in Flexigrid Optical Networks, are evaluated on the 14-nodes 22-links
NSFNET having an average degree of all the vertices444a.k.a. nodal degree,
$n_{d}=\dfrac{2E}{V}$ is 3.0 as shown in figure 10. We assume the fiber
bandwidth to be 4 THz on each link of the network. Using O-OFDM technology,
the whole bandwidth is divided into 12.5 GHz parallel channels. Therefore,
there are 320 spectrum slots on each link of the network. The traffic demands
for all the lightpath requests on each node pair are uniformly distributed.
The bandwidth required for each lightpath is chosen randomly in range from 1
to B Gbps, where different ‘B’ values are used as parameter in simulations. In
this thesis, the value of B is 100 Gbps5558 spectrum slots, if the grid size
is 12.5 GHz. For spectrum allocation, we also considered an additional guard
band (GB). The size of GB is considered to be 10 GHz.

The use of static traffic for simulation does not show the effectiveness of
the proposed algorithms. Hence, lightpath requests were generated dynamically,
i.e., we considered dynamic traffic scenario. The incoming lightpaths can be
set up and released upon request. These are equivalent to setting up and
releasing circuits in circuit-switched networks. The incoming lightpath
requests arrive with an exponentially distributed inter-arrival time with the
average of $\dfrac{1}{\lambda}$ seconds. Each connection is maintained for
exponentially distributed holding time with average of $\dfrac{1}{\mu}$
seconds before being released. The offered load ($\rho$) in Erlang (E) is
given by

$\rho=\dfrac{\dfrac{1}{\mu}}{\dfrac{1}{\lambda}}=\dfrac{\lambda}{\mu}.$ (19)

The performance parameters are estimated based on the observations made during
the steady-state condition (which is observed to happen after approximately
three times the average holding time, i.e., $3\times\dfrac{1}{\mu}$).

In this, we have used average values of failure rate ($\lambda^{\prime}$) and
repair rate ($\mu^{\prime}$), such that availability values on all links are
uniformly distributed. We are keeping fix the value of failure rate and
changing the values of repair rate. The link’s availability and threshold
availability ranges from 0.9 (one nine) to 0.999999 (six nines) as shown in
Table II.

Availability Values
---
one nine | 0.9
two nines | 0.99
three nines | 0.999
four nines | 0.9999
five nines | 0.99999
six nines | 0.999999
TABLE II: Different Availability values.

###  VIII-C Simulation Results

The Type-II algorithm is used for finding the working paths. When the path’s
availability is lower than the threshold availability, then for backup paths,
DSBPSS and D-cycles based on the Type-II algorithm are used.

####  VIII-C1 DSBPSS

(a)

(b)

(c)

Figure 11: Blocking Probability against various average link availabilities
and offered load per node for Type II-DSBPSS method.

Figure 11 plots the blocking probability for DSBPPS for different average
network links availability and load values. As seen in the figures 11(a),
11(b), and 11(c), the blocking probability is due to the blocking of the
working lightpath requests when the Average Network Links Availability
$>A_{th}$. Whereas, as the Average Network Links Availability $\leq A_{th}$,
the impact of the backup path on blocking probability is also observed in the
figures, i.e., the increase in the blocking probability is due to the incoming
working path and in ability to setup backup path. Based on the observations,
we can infer that when the Average Network Links Availability $\leq A_{th}$,
the backup path occupies the available spectrum slots at that instant such
that it becomes unavailable for new lightpath requests.

As the difference between Average Network Links Availability and $A_{th}$
increases, the blocking of the connection requests also increases. After a
certain $A_{th}$, the blocking probability reaches a steady-state condition.
There is a minor difference between blocking probabilities.

A similar pattern can be observed for figures 11(b), and 11(c), as the offered
load per node changes. The contrast is as the load increases, the blocking
probability also increases for various values of Average Network Links
Availability and $A_{th}$. We can also observe, after a certain threshold
value for offered load per node of 20 Erlang blocking starts decreasing. Most
likely, it is happening because backup paths could not be setup, leaving free
spaces for more connections. At $A_{th}$ = 0.999, more backup path could be
setup. This phenomena will be indent at higher load.

(a)

(b)

(c)

Figure 12: Bandwidth Blocking Probability against various average link
availabilities and offered load per node for Type II-DSBPSS method.

(a)

(b)

(c)

Figure 13: Spectrum Utilization against various average link availabilities
and offered load per node for Type II-DSBPSS method.

(a)

(b)

(c)

Figure 14: Capacity Used for Protection against various average link
availabilities and offered load per node for Type II-DSBPSS method.

(a)

(b)

(c)

Figure 15: Restorability against various average link availabilities and
offered load per node for Type II-DSBPSS method.

Figure 12 is the bandwidth blocking probability for DSBPPS for different
average network links availability and load values. The conclusions are the
same for blocking probability, except the bandwidth blocking probability is
slightly higher for all the slot sizes. It happens because instead of counting
the number of blocked connections, we consider each lightpath request’s
bandwidth.

Figure 13 is the spectrum utilization for DSBPPS for different average network
links availability and load values. As the Average Network Links Availability
$\leq Ath$, the impact of the backup paths on the spectrum utilization is
observed in the figures 13. The difference between Average Network Links
Availability and $A_{th}$ progresses, the utilization of the spectrum
increases due to backup path and working path. After a certain $A_{th}$, the
spectrum utilization reaches a steady-state condition.

The plots in Figure 14 are for capacity used for protection by backup path for
DSBPPS against different average network links availability and load values.
When the Average Network Links Availability $>Ath$, zero capacity is required
for protection. Now, as the Average Network Links Availability $\leq Ath$,
backup paths are required, which increases capacity used for protection by the
backup paths. The redundant paths are provisioned to the working path till the
$A_{pp}^{max}\geq A_{th}$. As the difference between Average Network Links
Availability and $A_{th}$ progresses, the capacity required for protection
starts decreasing due to the unavailability of the spectrum slots. After a
certain $A_{th}$, it reaches a steady-state condition. As the load values
increases, the steady-state condition is maintained as achieved earlier.

The plots in Figure 15 are for restorability of lightpath requests whose
$A_{pp}^{max}<A_{th}$ using DSBPPS. These are plotted against different
average network links availability and load values. When the Average Network
Links Availability $>A_{th}$, no protection is required; therefore, from here,
we can interpret that there is no restorability ratio. Now, as the Average
Network Links Availability $\leq A_{th}$ backup paths are required, which
results in requirement of more protection paths. Since restorability is the
ratio of the total number of protected paths to the total number of paths
requiring protection (sum of the protected and unprotected paths), this ratio
is only for the paths whose Availability is less than the threshold
Availability. Now, as the requirement for protection increases, the number of
the protected paths also increases. Hence the restorability ratio also
increases. The redundant paths are provisioned to the working path till the
$A_{pp}^{max}\geq A_{th}$. As the difference between Average Network Links
Availability and $A_{th}$ progresses, the restorability ratio decreases due to
the unavailability of the spectrum slots. Therefore, the denominator term
(protected paths $+$ unprotected paths) starts dominating. This means there is
an increase in the number of unprotected paths. After a certain $A_{th}$, it
reaches a steady-state condition. As the load values increases further, the
steady-state condition is maintained as achieved earlier.

The increase in the protection of number of lightpath requests can be done by
increasing the capacity of each link in the network, multiple core-based
networks or multiple band optical transmission networks.

####  VIII-C2 D-Cycles

Figure 16 plots the blocking probability for D-cycles for different average
network links availability and load values. As seen in the figures 16(a),
16(b), and 16(c), the blocking probability is due to the blocking of the
working lightpath requests when the Average Network Links Availability
$>A_{th}$. Whereas, as the Average Network Links Availability $\leq A_{th}$,
the impact of the protection on blocking probability is also observed in the
figures, i.e., the increase in the blocking probability is due to the incoming
working path and backup D-cycles. Based on the observations, when the Average
Network Links Availability $\leq A_{th}$, the part of the D-cycles used for
protection occupies the available spectrum slots at that instant such that it
becomes unavailable for new lightpath requests.

As the difference between Average Network Links Availability and $A_{th}$
increases, the blocking of the connection requests also increases. After a
certain $A_{th}$, the blocking probability reaches a steady-state condition.
There are minor difference between blocking probabilities.

A similar pattern can be observed for figures 16(b), and 16(c), as the offered
load per node changes. The contrast is, as the load increases, the blocking
probability also increases for various values of Average Network Links
Availability and $A_{th}$.

(a)

(b)

(c)

Figure 16: Blocking Probability against various average link availabilities
and offered load per node for Type II-D-cycles method.

(a)

(b)

(c)

Figure 17: Bandwidth Blocking Probability against various average link
availabilities and offered load per node for Type II-D-cycles method.

(a)

(b)

(c)

Figure 18: Spectrum Utilization against various average link availabilities
and offered load per node for Type II-D-cycles method.

(a)

(b)

(c)

Figure 19: Capacity Used for Protection against various average link
availabilities and offered load per node for Type II-D-cycles method.

(a)

(b)

(c)

Figure 20: Restorability against various average link availabilities and
offered load per node for Type II-D-cycles method.

Figure 17 is the bandwidth blocking probability for D-cycles for different
average network links availability and load values. The conclusions are the
same for blocking probability, except the bandwidth blocking probability is
slightly higher for all the slot sizes. It happens because instead of counting
the number of blocked connections, we consider each lightpath request’s
bandwidth.

Figure 18 is the spectrum utilization for D-cycles for different average
network links availability and load values. As the Average Network Links
Availability $\leq Ath$, the impact of the D-cycles requirement on the
spectrum utilization is observed in the figures 13. The difference between
Average Network Links Availability and $A_{th}$ progresses, the utilization of
the spectrum due to D-cycles and working path increases. After a certain
$A_{th}$, the spectrum utilization reaches a steady-state condition.

The plots in Figure 19 are for capacity used for protection using D-cycles.
These are plotted against different average network links availability and
load values. When the Average Network Links Availability $>Ath$, zero capacity
is required for protection. Now, as the Average Network Links Availability
$\leq Ath$ backup D-cycles are required, which increases capacity used for
protection. The redundant paths are provisioned to the link (part of the
working path) with minimum Availability till the $A_{pp}^{max}\geq A_{th}$. As
the difference between Average Network Links Availability and $A_{th}$
progresses, the capacity required for protection starts decreasing due to the
unavailability of the spectrum slots. After a certain $A_{th}$, it reaches a
steady-state condition. As the load values increases, the steady-state
condition is achieved earlier.

The plots in Figure 20 are for restorability of lightpath requests whose
$A_{pp}^{max}<A_{th}$ using D-cycles. These are plotted against different
average network links availability and load values. When the Average Network
Links Availability $>A_{th}$, no protection is required; therefore, from here,
we can interpret that there is no restorability ratio. Now, as the Average
Network Links Availability $\leq A_{th}$ backup D-cycles are required,
requiring a higher number of protection paths. Since restorability is the
ratio of the total number of protected paths to the total number of paths
requiring protection (sum of the protected and unprotected paths), this ratio
is only for the paths whose Availability is less than the threshold
Availability. Now, as the requirement for protection increases, the number of
the protected paths also increases. Hence, the restorability ratio also
increases. The redundant paths are provisioned to the working path till the
$A_{pp}^{max}\geq A_{th}$. As the difference between Average Network Links
Availability and $A_{th}$ progresses, the restorability ratio decreases due to
the unavailability of the spectrum slots. Therefore, the denominator term
(protected paths $+$ unprotected paths) starts dominating. This means there is
an increase in the number of unprotected paths. After a certain $A_{th}$, it
reaches a steady-state condition. As the load values increases, the steady-
state condition is achieved earlier.

The increase in the protection of number of lightpath requests can be done by
increasing the capacity of each link in the network, multiple core-based
networks or multiple band optical transmission networks.

##  IX Conclusion

The protection of an optical network is a crucial aspect for RSA of lightpath
requests. In this paper, we formulate heuristics to assign protection to the
new working path without disturbing existing traffic on all other routes.
However, assigning protection to all the requests is impossible. Therefore, we
use the Availability of the link and path as a parameter for protection. This
paper uses two protection techniques, Dynamic Shared Backup Path and Spectrum
Slots (DSBPSS), for the path protection and design Dynamic Cycles (D-cycles)
for the link protection. Both the protection techniques use adaptive
parameters, i.e., consecutive spectrum slots. The consecutive spectrum slots
(i.e., Type-II algorithm) keep changing with the network conditions. We
performed a detailed analysis of the proposed algorithms for NSFNET network
topology. Based on the observation from the plots, the performance of DSBPSS
and D-cycles are comparable. However, the switching speed of D-cycles is
better than DSBPSS. Therefore, D-cycles can be considered for protection
provisioning considering spectrum slots converter at the backup nodes.
Whereas, if the network is not equipped with spectrum converters, then DSBPSS
is an alternative solution for Routing, Spectrum Assignment and Protection
Provisioning.

## References

  * [1] P. Athe, and Y. N. Singh. “Improved double cycle and link pair methods for two-link failure protection.” Telecommunication Systems 74.1, pp. 83-93, 2020.
  * [2] V. Lohani, A. Sharma, and Y. N. Singh. “Sub-Graph p-cycle formation for span failures in all-Optical Networks,” arXiv preprint arXiv:2102.07361 (2021).
  * [3] ITU-T G.694.1, ”spectrum grids for WDM applications: DWDM frequency grid”, 2012.
  * [4] O. Gerstel, M. Jinno, A. Lord, and S. J. B. Yoo, “Elastic optical networking: A new dawn for the optical layer?,” IEEE Commun. Mag., vol. 50, no. 2, pp. 12-20, Feb. 2012.
  * [5] H. M. N. S. Oliveira, and N. L. S. Fonseca, “Protection in elastic optical networks using Failure-Independent Path Protecting p-cycles”, Optical Switching and Networking, vol. 35, pp. 1-10, 2020.
  * [6] X. Chen, F. Ji, and Z. Zhu, “Service availability oriented p-cycle protection design in elastic optical networks,” in IEEE/OSA Journal of Optical Communications and Networking, vol. 6, no. 10, pp. 901-910, Oct. 2014.
  * [7] X. Chen, M. Tornatore, S. Zhu, F. Ji, W. Zhou, C. Chen, D. Hu, L. Jiang, and Z. Zhu, “Flexible Availability-Aware Differentiated Protection in Software-Defined Elastic Optical Networks,” in Journal of Lightwave Technology, vol. 33, no. 18, pp. 3872-3882, Sept. 2015.
  * [8] X. Chen, M. Zhou, S. Zhu, S. Kang, L. Sun, and Z. Zhu, “Optimizing FIPP- ${p}$ -Cycle Protection Design to Realize Availability-Aware Elastic Optical Networks,” in IEEE Communications Letters, vol. 22, no. 1, pp. 65-68, Jan. 2018.
  * [9] R. Gour, G. Ishigaki, J. Kong, and J. P. Jue, “Availability-guaranteed slice composition for service function chains in 5G transport networks,” in IEEE/OSA Journal of Optical Communications and Networking, vol. 13, no. 3, pp. 14-24, March 2021.
  * [10] V. Lohani, A. Sharma, and Y. N. Singh. “Dynamic Routing and Spectrum Assignment based on the Availability of Consecutive Sub-channels in Flexi-grid Optical Networks,” arXiv preprint arXiv:2105.07560 (2021).
  * [11] C. Wang, G. Shen, and S. K. Bose, “Distance Adaptive Dynamic Routing and Spectrum Allocation in Elastic Optical Networks With Shared Backup Path Protection,” in Journal of Lightwave Technology, vol. 33, no. 14, pp. 2955-2964, July, 2015.
  * [12] W.Ahmad, O. Hasan, U. Pervez, and J. Qadir, “Reliability modeling and analysis of communication networks,” Journal of Network and Computer Applications, vol. 78, pp. 191-215, 2017.
  * [13] S. Ross, Introduction to Probability Models, Los Angeles, CA, United States of America, Academic Press, 2019.
  * [14] G. A. Klutke, P. C. Kiessler, and M. A. Wortman, “A critical look at the bathtub curve,” in IEEE Transactions on Reliability, vol. 52, no. 1, pp. 125-129, March 2003.


# Two-dimensional Weyl sums failing square-root cancellation along lines

Julia Brandes and Igor E. Shparlinski  JB: Mathematical Sciences, University
of Gothenburg and Chalmers Institute of Technology, 412 96 Göteborg, Sweden
<EMAIL_ADDRESS>IES: Department of Pure Mathematics, University of New
South Wales, Sydney NSW 2052, Australia<EMAIL_ADDRESS>
###### Abstract.

We show that a certain two-dimensional family of Weyl sums of length $P$ takes
values as large as $P^{3/4+o(1)}$ on almost all linear slices of the unit
torus, contradicting a widely held expectation that Weyl sums should exhibit
square-root cancellation on generic subvarieties of the unit torus. This is an
extension of a result of J. Brandes, S. T. Parsell, C. Poulias, G. Shakan and
R. C. Vaughan (2020) from quadratic and cubic monomials to general polynomials
of arbitrary degree. The new ingredients of our approach are the classical
results of E. Bombieri (1966) on exponential sums along a curve and R. J.
Duffin and A. C. Schaeffer (1941) on Diophantine approximations by rational
numbers with prime denominators.

###### Key words and phrases:

Exponential sums

###### 2010 Mathematics Subject Classification:

Primary 11L15; Secondary 11J83, 11T23

##  1\. Introduction

Given their central role in many number theoretic applications, it is no
surprise that Weyl sums and their properties have been subject to thorough
investigation over the years. For a collection ${\bm{\varphi}}$ of linearly
independent polynomials ${\varphi}_{1},\ldots,{\varphi}_{r}\in\mathbb{Z}[X]$
with respective degrees $k_{1},\ldots,k_{r}$ we consider the Weyl sums

$f_{{\bm{\varphi}}}({\bm{\alpha}})=\sum_{1\leqslant x\leqslant
P}{\mathbf{\,e}}({\alpha}_{1}{\varphi}_{1}(x)+\ldots+{\alpha}_{r}{\varphi}_{r}(x)),$

where ${\mathbf{\,e}}(z)=\exp\left(2\pi iz\right)$ and
${\bm{\alpha}}=({\alpha}_{1},\ldots,{\alpha}_{r})$. We also write
$\mathbb{T}=\mathbb{R}/\mathbb{Z}$ for the unit torus, and refer to the end of
this section for other notational conventions we use.

Whilst it is well known that $f_{{\bm{\varphi}}}({\bm{\alpha}})$ can be of
order $P$ when the entries of ${\bm{\alpha}}$ lie in the neighbourhood of
fractions with a small denominator, the general expectation has always been
that for a “typical” ${\bm{\alpha}}$ one should have the upper and lower
bounds

$P^{1/2}\ll f_{{\bm{\varphi}}}({\bm{\alpha}})\ll P^{1/2+o(1)}.$ (1.1)

This question has recently been investigated in work by Chen and Shparlinski
[7], which in particular implies that the bounds (1.1) hold for a subset of
${\bm{\alpha}}\in\mathbb{T}^{r}$ of full Lebesgue measure whenever the
polynomials ${\bm{\varphi}}$ have a non-vanishing Wronskian [7, Corollary
2.2]. A particularly strong version of this result, applicable to the
situation when ${\varphi}_{j}(X)=X^{j}$ for $1\leqslant j\leqslant r$, is
available in subsequent work [6], where the interested reader will also find a
more comprehensive bibliography on the subject.

In practical applications it is often necessary to control the size of
$f_{{\bm{\varphi}}}({\bm{\alpha}})$ on linear slices of $\mathbb{T}^{r}$,
where some of the ${\alpha}_{i}$ are fixed to lie in some set of full measure,
whereas the remaining ones range over the entire unit interval. Such
situations typically arise in “minor arcs” situations where some, but not all,
entries of ${\bm{\alpha}}$ may have a good rational approximation and thus lie
in an anticipated exceptional set. This problem has recently been studied in a
very general setup by Chen and Shparlinski [7] (see also [9]), refining an
approach developed by Wooley [15]. Their main result [7, Theorem 2.1] asserts
that whenever the polynomials ${\bm{\varphi}}$ have a non-vanishing Wronskian,
then for almost all $({\alpha}_{1},\ldots,{\alpha}_{d})\in\mathbb{T}^{d}$ one
has bounds of the shape

$\sup_{{\alpha}_{d+1},\ldots,{\alpha}_{r}\in\mathbb{T}}|f_{{\bm{\varphi}}}({\alpha}_{1},\ldots,{\alpha}_{r})|\ll
P^{1/2+\Gamma(d,{\bm{\varphi}})+o(1)},$

where $\Gamma(d,{\bm{\varphi}})$ is a non-negative function depending on the
degrees of the polynomials ${\bm{\varphi}}$, for the precise definition of
which we refer to [7]. Unfortunately, even though the bound of [7, Theorem
2.1] gives strong results in a number of configurations and notably implies
that one can take ${\Gamma}(d,{\bm{\varphi}})=0$ for all admissible $r$-tuples
of polynomials when $d=r$, in many other cases the bounds it furnishes do not
beat even the trivial bound. In such situations, one has to resort to the more
classical methods employing bounds of Weyl or Hua type and their subsequent
generalisations (see [14, Lemma 2.4 and Theorem 5.2] for the former, and [14,
Lemma 2.5] as well as the results of [16, Section 14] for the latter). Bounds
of this nature provide also the crucial input in the work by Erdoğan and
Shakan [11], as well as in recent work by Chen and Shparlinski [8] in which,
motivated by some links to certain questions on classical partial differential
equations, they establish upper bounds along linear slices of the exponential
sum associated with pairs of polynomials ${\varphi}_{1},{\varphi}_{2}$
differing by a linear term. Several related results have recently been
obtained by Barron [1]. However, as these bounds use Vinogradov’s mean value
theorem (see [3, Theorem 1.1] or [16, Theorem 1.1]) as their main input, which
is inefficient for Weyl sums whose degree exceeds their dimension, they are
inherently unable to provide bounds stronger than $O(P^{1-c_{k}})$ for some
positive parameter $c_{k}$ of size $c_{k}\asymp k^{-2}$.

Whilst exponents of this magnitude are not believed to be sharp in general,
Brandes et al. [4] have recently shown that one cannot hope to have
${\Gamma}(d,{\bm{\varphi}})=0$ for all choices of polynomials with non-
vanishing Wronskian when $d<r$. In particular, for the choice
${\varphi}_{1}(x)=X^{k}+X$ and ${\varphi}_{2}(X)=X^{k}$ with $k=2$ or $k=3$,
they show in [4, Theorem 1.3] that for all
${\alpha}_{2}\in\mathbb{R}\setminus\mathbb{Q}$ and any $\tau>0$ there exist
arbitrarily large values of $P$ for which we have the lower bound

$\sup_{{\alpha}\in\mathbb{T}}|f_{{\bm{\varphi}}}({\alpha}_{1},{\alpha}_{2})|\gg
P^{3/4-\tau},$ (1.2)

and that for almost all ${\alpha}_{2}\in\mathbb{T}$ this bound can be matched
by a corresponding upper bound

$\sup_{{\alpha}\in\mathbb{T}}|f_{{\bm{\varphi}}}({\alpha}_{1},{\alpha}_{2})|\ll
P^{3/4+o(1)}.$

To our knowledge, this is the first indication in the literature that the
expectation that (1.1) should hold for all ${\bm{\alpha}}$ on a linear slice
of $\mathbb{T}^{r}$ may be too naive. In [4] the authors speculate that the
same behaviour as in (1.2) might continue to hold for polynomials
${\varphi}_{1}(X)=X^{k}+X$ and ${\varphi}_{2}(X)=X^{k}$ with $k\geqslant 4$.

The goal of this paper is therefore to extend the bound in (1.2) to more
general polynomials, allowing also for higher degrees.

######  Theorem 1.

Let ${\varphi}\in\mathbb{Z}[X]$ be a polynomial of degree $k\geqslant 2$, and
set

$f({\alpha}_{1},{\alpha}_{2})=\sum_{1\leqslant x\leqslant
P}{\mathbf{\,e}}({\alpha}_{1}({\varphi}(x)+x)+{\alpha}_{2}{\varphi}(x)).$
(1.3)

There exists a set ${\mathscr{C}}\subseteq\mathbb{T}$ of full Lebesgue measure
such that for any $\tau>0$ and all ${\alpha}_{2}\in{\mathscr{C}}$ there exist
arbitrarily large values of $P$ for which one has the bound

$\sup_{{\alpha}_{1}\in\mathbb{T}}|f({\alpha}_{1},{\alpha}_{2})|\gg
P^{3/4-\tau}.$

Thus, whenever ${\bm{\varphi}}=({\varphi}_{1},{\varphi}_{2})$ is a pair of
polynomials differing only by a linear term, the associated exponential sum is
are substantially larger than originally anticipated on almost all linear
slices of $\mathbb{T}$. The fact that in our result the polynomials under
consideration differ only by a linear term seems to play a role, since linear
exponential sums do not exhibit square root cancellation in the same manner as
their cousins of higher degree do. It is therefore an interesting question to
investigate whether the behaviour observed in Theorem 1 persists, perhaps in a
weaker form, even when the polynomials occurring in the exponential sum differ
by more than a linear term.

Unlike in [4], our result in Theorem 1 is not complemented by a corresponding
upper bound. The methods presented in [4] could conceivably be adapted to
provide such upper bounds even in the more general case considered in the
manuscript at hand for all ${\alpha}_{2}$ lying in a subset of full measure of
a suitably defined set of “major arcs”. This would be sufficient when
$k\leqslant 3$, as then the entire unit interval $\mathbb{T}$ can be covered
by such major arcs. For higher degrees, these methods fail and we have no
improvements over the existing results of [8]. Nonetheless, we believe that
these difficulties are of a technical rather than fundamental nature, and
consequently it seems likely that the exponent $3/4$ should be sharp in those
cases also.

Our argument is a streamlined version of that presented in [4, Section 8],
which deals with the case of ${\varphi}(X)=X^{k}$ for $k=2,3$. However, we
augment this approach by two classical results. Firstly, we appeal to a bound
of Bombieri [2, Theorem 6] on exponential sums along a curve over a finite
field, and secondly we make use of a result of Duffin and Schaeffer [10,
Theorem I] which allows us to restrict to the case where the diophantine
approximations we consider have a prime denominator.

Notation. Throughout the paper, we make use of the following conventions. When
$x\in\mathbb{R}$ we denote by $\|x\|$ the distance from $x$ to the nearest
integer. Moreover, $P$ always denotes a large positive number, and the letter
$p$ is reserved for primes. We use the Vinogradov ‘$\ll$’, ‘$\gg$’ and
equivalent Bachmann–Landau notations ‘$O(\cdot)$’ liberally, and here the
implied constants are allowed to depend on ${\bm{\varphi}}$ and $\tau$, but
never on $P$ or ${\bm{\alpha}}$.

##  2\. Assembling the toolbox

###  2.1. Approximations by rational exponential sums

In our examination of the exponential sum (1.3) we rely heavily on our
understanding of the closely related sum

$g({\alpha},{\gamma})=\sum_{1\leqslant x\leqslant
P}{\mathbf{\,e}}({\alpha}x+{\gamma}{\varphi}(x))$

and its associated approximations. Indeed, it is apparent from the respective
definitions of these exponential sums that

$f({\alpha}_{1},{\alpha}_{2})=g({\alpha}_{1},{\alpha}_{1}+{\alpha}_{2}).$
(2.1)

When ${\varphi}(X)=X^{k}$, the latter one of these has been studied in [5] and
[4], but it turns out that in the situation we are mainly interested in the
pure power may be replaced by a more general polynomial. For $q\in\mathbb{N}$,
$a,c\in\mathbb{Z}$ and ${\beta}\in\mathbb{R}$ set

$S(q;a,c)=\sum_{x=1}^{q}{\mathbf{\,e}}\left(\frac{ax+c{\varphi}(x)}{q}\right)\qquad\text{
and }\qquad I({\beta})=\int_{0}^{P}{\mathbf{\,e}}({\beta}x){\,{\rm d}}x,$

and recall that for non-vanishing ${\beta}$ we can compute

$|I({\beta})|=P\left|\frac{\sin(\pi\beta P)}{\pi\beta
P}\right|\ll\min\\{P,\|{\beta}\|^{-1}\\},$ (2.2)

while a classical Weil bound (see, for example, [13, Corollary II.2F]) shows
that when $p$ is prime and $c\nmid p$ one has

$S(p;a,c)\leqslant(k-1)p^{1/2}.$ (2.3)

We then have the following straightforward modification of [5, Theorem 3] or
[14, Theorem 4.1].

######  Lemma 1.

Let ${\varphi}\in\mathbb{Z}[X]$ be a polynomial of degree $k\geqslant 2$.
Suppose that ${\gamma}\in\mathbb{Q}$ with ${\gamma}=c/p$ in lowest terms,
where $p$ is a prime number, and fix $a\in\mathbb{Z}$ such that
$|{\alpha}-a/p|\leqslant(2p)^{-1}$. Set then ${\beta}={\alpha}-a/p$. In this
notation we have

$g({\alpha},{\gamma})=p^{-1}S(p;a,c)I({\beta})+O(p^{1/2}\log p).$

###### Proof.

Just like in the proof of [14, Theorem 4.1], we sort the variables into
residue classes, which we then encode in terms of exponential sums. Thus

$g({\alpha},{\gamma})=\frac{1}{p}\sum_{b=1}^{p}S(p;a+b,c)f({\beta}-b/p,0).$

By [14, Lemma 4.2] we have $f({\beta}-b/p,0)=I({\beta}-b/p)+O(1)$, so that
together with [4, Lemma 2.2] we find that

$g({\alpha},{\gamma})=\frac{1}{p}\sum_{b=1}^{p}S(p;a+b,c)I({\beta}-b/p)+O(p^{1/2}).$

Since $c\nmid p$, it follows upon deploying (2.2) and (2.3) that

$g({\alpha},{\gamma})-p^{-1}S(p;a,c)I({\beta})\ll
p^{-1/2}\sum_{b=1}^{p-1}\|{\beta}-b/p\|^{-1}\ll p^{1/2}\log p,$

where in the last step we use that

$\|{\beta}-b/p\|\geqslant(2p)^{-1}$

for all $b\not\equiv 0\;(\mathrm{mod}\;{p})$. This completes the proof. ∎

###  2.2. A lower bound on rational exponential sums

Our second main tool shows that the complete exponential sum $S(p;a,c)$ cannot
be smaller than $p^{1/2}$ too often. It is useful to denote the leading
coefficient of ${\varphi}$ by $\operatorname{lc}({\varphi})$.

######  Lemma 2.

Let $p$ be a prime satisfying $p>(2k)^{4}$ with
$p\nmid\operatorname{lc}({\varphi})$, and let $c\in\mathbb{Z}$ with $p\nmid
c$. Then there exists $a\in\mathbb{Z}$ with $p\nmid(a+c)$ such that

$S(p;a,a+c)\geqslant\tfrac{1}{3}p^{1/2}.$

###### Proof.

When $k=2$, the desired result follows from classical bounds on Gauss sums, so
it is sufficient to consider the case when $k\geqslant 3$. By averaging and
shifting the variable of summation, the result follows if we can show that

$\sum_{a=1}^{p-1}|S(p;a-c,a)|^{2}\geqslant\tfrac{1}{3}p^{2}$ (2.4)

for all primes $p>(2k)^{4}$ not dividing $\operatorname{lc}({\varphi})$.

We begin by noting that

$\displaystyle\sum_{a=1}^{p-1}|S(p;a-c,a)|^{2}$
$\displaystyle=p\sum_{\begin{subarray}{c}m,n=1\\\
{\varphi}(m)+m\equiv{\varphi}(n)+n\;(\mathrm{mod}\;{p})\end{subarray}}^{p}{\mathbf{\,e}}\left(\frac{c(m-n)}{p}\right)-\left|\sum_{m=1}^{p}{\mathbf{\,e}}\left(\frac{cm}{p}\right)\right|^{2}.$

The second sum vanishes, and in the first one we make the change of variables
$n=m-h$ and isolate the term corresponding to $h=0$. Hence

$\sum_{a=1}^{p-1}|S(p;a-c,a)|^{2}=p^{2}+p\sum_{m=1}^{p}\sum_{\begin{subarray}{c}h=1\\\
{\Delta}(m,h)\equiv
0\;(\mathrm{mod}\;{p})\end{subarray}}^{p-1}{\mathbf{\,e}}(ch),$ (2.5)

where we put

${\Delta}(m,h)=({\varphi}(m+h)-{\varphi}(m)+h)/h.$

Upon re-inserting in the term corresponding to $h=0$ and noting that all
exponential sums in question take real values we discern that

$\displaystyle\sum_{m=1}^{p}\sum_{\begin{subarray}{c}h=1\\\
{\Delta}(m,h)\equiv
0\;(\mathrm{mod}\;{p})\end{subarray}}^{p-1}{\mathbf{\,e}}(ch)$
$\displaystyle=\sum_{\begin{subarray}{c}m,h=1\\\ {\Delta}(m,h)\equiv
0\;(\mathrm{mod}\;{p})\end{subarray}}^{p}{\mathbf{\,e}}(ch)-\sum_{\begin{subarray}{c}m=1\\\
{\Delta}(m,0)\equiv 0\;(\mathrm{mod}\;{p})\end{subarray}}^{p}1$
$\displaystyle\leqslant\sum_{\begin{subarray}{c}m,h=1\\\ {\Delta}(m,h)\equiv
0\;(\mathrm{mod}\;{p})\end{subarray}}^{p}{\mathbf{\,e}}(ch).$

If $k\geqslant 2$, then ${\Delta}(X,Y)$ is a nontrivial polynomial in two
variables of degree exactly $k-1$, so the congruence

${\Delta}(m,h)\equiv 0\;(\mathrm{mod}\;{p})$

defines a curve over the finite field $\mathbb{F}_{p}$. Furthermore, if $k>1$,
then ${\Delta}(X,Y)$ is a nontrivial polynomial of degree exactly $k-1$ with
respect to $X$ with the leading monomial
$k\operatorname{lc}({\varphi})X^{k-1}$. Thus for $p>k$ and
$p\nmid\operatorname{lc}({\varphi})$ the variable $h$ is not constant along
this curve. We may therefore apply [2, Theorem 6] and find that

$\sum_{\begin{subarray}{c}m,h=1\\\ {\Delta}(m,h)\equiv
0\;(\mathrm{mod}\;{p})\end{subarray}}^{p}{\mathbf{\,e}}(ch)\leqslant\left((k-1)^{2}+2(k-1)-3\right)\sqrt{p}+(k-1)^{2}.$
(2.6)

Under our assumption $p>(2k)^{4}$, for the right hand side in (2.6) we have

$\left((k-1)^{2}+2(k-1)-3\right)\sqrt{p}+(k-1)^{2}<\tfrac{2}{3}p.$

In view of (2.5), we derive (2.4), which is sufficient to establish the
result. ∎

##  3\. Proof of the main result

The following result, going back to Duffin and Schaeffer [10], is a key
ingredient in our arguments as it allows us to focus on those
${\alpha}\in\mathbb{T}$ whose rational approximations have prime denominators.

######  Lemma 3.

There is a set ${\mathscr{C}}\subseteq\mathbb{T}$ of full Lebesgue measure
such that for any $\alpha\in{\mathscr{C}}$ there are infinitely many
approximations

$\left|\alpha-\frac{a}{p}\right|<\frac{1}{p^{2}}$

with $a\in\mathbb{Z}$ and $p$ being a prime number.

###### Proof.

This is a direct application of [10, Theorem I], see also the remark on top of
p. 245 of that paper. ∎

We also remark that Lemma 3 is a special case of the Duffin-Schaeffer
conjecture, recently established as a theorem by Koukoulopoulos and Maynard
[12].

We now have the wherewithal to embark on the proof of Theorem 1. Fix $\tau>0$,
and let ${\alpha}_{2}\in{\mathscr{C}}$, where ${\mathscr{C}}$ is as in Lemma
3. Then we can find an arbitrarily large prime number $p$, and
$a_{2}\in\mathbb{Z}$ not divisible by $p$, that satisfy
$|{\alpha}_{2}-a_{2}/p|\leqslant p^{-2}$. For any fixed such $p$ satisfying
$p>(2k)^{4}$ and not dividing $\operatorname{lc}({\varphi})$, define $P$ via
the relation

$P^{1+\tau}=p^{2}.$ (3.1)

Lemma 2 now guarantees the existence of an integer $a_{1}$ with
$a_{1}+a_{2}\not\equiv 0\;(\mathrm{mod}\;{p})$ and having the property that

$S(p;a_{1},a_{1}+a_{2})\gg p^{1/2}.$ (3.2)

Take now ${\beta}_{2}={\alpha}_{2}-a_{2}/p$ and ${\beta}_{1}=-{\beta}_{2}$,
and put ${\alpha}_{1}=a_{1}/p+{\beta}_{1}$. Then upon recalling that
${\gamma}={\alpha}_{1}+{\alpha}_{2}$ in (2.1), we see that ${\gamma}=c/p$ with
$c=a_{1}+a_{2}\not\equiv 0\;(\mathrm{mod}\;{p})$, whereupon Lemma 1 yields the
relation

$g({\alpha}_{1},{\gamma})=p^{-1}S(p;a_{1},a_{1}+a_{2})I({\beta}_{1})+O(p^{1/2}\log
p).$

Recall now our definition of $P$ from (3.1). Since
$|{\beta}_{1}|=|{\beta}_{2}|\leqslant p^{-2}=P^{-1-\tau}$, it follows further
from (2.2) that $|I({\beta}_{1})|=P\,(1+O(P^{-2\tau}))$, so upon inserting
(3.2) we discern that

$g({\alpha}_{1},{\gamma})\gg Pp^{-1/2}\gg P^{3/4-\tau}.$

In the light of (2.1) and Lemma 3, this establishes the desired result.

## Acknowledgements

The authors would like to thank James Maynard for drawing our attention to a
result of Duffin and Schaeffer [10, Theorem I] on Diophantine approximations
with prime denominators.

During the preparation of this manuscript, JB was supported by Starting Grant
no. 2017-05110 of the Swedish Science Foundation (Vetenskapsrådet) and IS was
supported by the Australian Research Council Grant DP170100786.

## References

  * [1] A. Barron, _An $L^{4}$ maximal estimate for quadratic Weyl sums_, Preprint, 2020, available at https://arxiv.org/abs/2011.09885.
  * [2] E. Bombieri, _On exponential sums in finite fields_ , Am. J. Math. 88, No. 1 (1966) 71–105.
  * [3] J. Bourgain, C. Demeter and L. Guth, _Proof of the main conjecture in Vinogradov’s mean value theorem for degrees higher than three_ , Ann. of Math. (2) 184 (2016) 633–682.
  * [4] J. Brandes, S. T. Parsell, C. Poulias, G. Shakan and R. C. Vaughan, _On generating functions in additive number theory, II: lower order terms and applications to PDEs_ , Math. Ann., to appear.
  * [5] J. Brüdern and O. Robert, _Rational points on linear slices of diagonal hypersurfaces_ , Nagoya Math. J. 218 (2015), 51–100.
  * [6] C. Chen, B. Kerr, J. Maynard and I. E. Shparlinski, _Metric theory of Weyl sums_ , Preprint, 2020, available at https://arxiv.org/abs/2011.09306.
  * [7] C. Chen and I. E. Shparlinski, _New bounds of Weyl sums_ , Int. Math. Res. Not. (IMRN), to appear.
  * [8] C. Chen and I. E. Shparlinski, _Hybrid bounds on two-parametric families of Weyl sums along smooth curves_ , Michigan Math. J., to appear.
  * [9] C. Chen and I. E. Shparlinski, _On a hybrid version of the Vinogradov mean value theorem_ , Acta Math. Hung., to appear.
  * [10] R. J. Duffin and A. C. Schaeffer, _Khintchine’s problem in metric Diophantine approximation_ , Duke Math. J., 8 (1941), 243–255.
  * [11] M. B. Erdoğan and G. Shakan, _Fractal solutions of dispersive partial differential equations on the torus_ , Selecta Math. (N.S.) 25 (2019), Art. 11, 1–26.
  * [12] D. Koukoulopoulos and J. Maynard, _On the Duffin-Schaeffer conjecture_ , Ann. of Math. 192 (2020), 251–307.
  * [13] W. M. Schmidt, Equations over finite fields – An elementary approach. Lecture Notes in Mathematics 536, Springer, Berlin, 1976.
  * [14] R. C. Vaughan, The Hardy–Littlewood method. Cambridge Tracts in Mathematics 125, Cambridge University Press, 1997.
  * [15] T. D. Wooley, _Perturbations of Weyl sums_ , Int. Math. Res. Not. (IMRN) 2016 (2016), No. 9, 2632–2646.
  * [16] T. D. Wooley, _Nested efficient congruencing and relatives of Vinogradov’s mean value theorem_ , Proc. London Math. Soc. 118 (2019), 942–1016.