% THIS temple bare_jrnl_for_IJET.tex is is based on
%% bare_jrnl.tex
%% V1.3
%% 2007/01/11
%% by Michael Shell
%% see http://www.michaelshell.org/
%% for current contact information.
%%
%% This is a skeleton file demonstrating the use of IEEEtran.cls
%% (requires IEEEtran.cls version 1.7 or later) with an IEEE journal paper.
%%
%% Support sites:
%% http://www.michaelshell.org/tex/ieeetran/
%% http://www.ctan.org/tex-archive/macros/latex/contrib/IEEEtran/
%% and
%% http://www.ieee.org/

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\documentclass[journal,a4paper,twoside]{IEEEtran}

\def\IEEEkeywordsname{Keywords}


\usepackage{cite}
\usepackage{url}

\usepackage{graphicx}
\usepackage{epstopdf}
\usepackage{psfrag}

\hyphenation{op-tical net-works semi-conduc-tor}
\usepackage{balance}

\widowpenalty=300000
\clubpenalty=300000

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% EDITOR SECTION (Do not change)

%IJET firt page header 
\newcommand{\YEAR}{2016}
\newcommand{\VOLUME}{62}
\newcommand{\NUMBER}{1}
\newcommand{\PAGES}{1--6}
\newcommand{\RECEIVEDATE}{December 10, 2015}
\newcommand{\REVISIONDATE}{March, 2016}
\newcommand{\DOI}{DOI: 10.1515/eletel-2016-000x}  

\usepackage{fancyhdr}
\lhead
{
	\begin{picture}(0,0)
	\put(0,-15){\includegraphics{logo_first_page}}  
	\put(30,-2){\scriptsize\MakeUppercase{INTL Journal of Electronics and Telecommunications, \YEAR, Vol. \VOLUME, no. \NUMBER, pp. \PAGES}}
	\put(30,-10){\scriptsize{Manuscript received \RECEIVEDATE; revised \REVISIONDATE.$\qquad\,\quad\qquad$\DOI}}
	\end{picture}
}
\chead{}
\rhead{}
\lfoot{}
\cfoot{}
\rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}

\setcounter{page}{1}

\begin{document}

\title{Investigation of dynamic routing and spectrum allocation methods in elastic optical networks}

%\author{Author 1, Author 2, Author 3\\
%
	%\thanks{This work was supported by the grant No. xxxxxx ”The research of new instruments in LaTeX” financed from internal science fund of University of Technology.}% stops a space
	%\thanks{This work was supported by the grant No. xxxxxx ”The research of new instruments in LaTeX” financed from internal science fund of University of Technology.}% stops a space
%		%\thanks{This work was supported by the grant No. xxxxxx ”The research of new instruments in LaTeX” financed from internal science fund of University of Technology.}% stops a space
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\author{Edyta Biernacka, Jerzy Dom\.za\l{}$^1$, Robert W\'ojcik$^1$\\
$^1$\IEEEmembership{Member, IEEE} \\% <-this % stops a space
\thanks{E.~Biernacka, J. Dom\.za\l{} and R. W\'ojcik are with the Department of Telecommunications, AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Krak\'ow, Poland.} %(e-mail: {ebiernac@agh.edu.pl, jdomzal@kt.agh.edu.pl, robert.wojcik}@kt.agh.edu.pl).}% <
\thanks{Correspondence to E.~Biernacka, e-mail: ebiernac@agh.edu.pl.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
}



\markboth{}{}



\maketitle
\thispagestyle{fancy}%

%\markboth{Author 1, Author 2, Author 3}{Example of Article for International Journals of Electronics and Telecommunications}
\markboth{E.~Biernacka, J.~Dom\.za\l, R.~W\'ojcik}{Investigation of dynamic routing and spectrum allocation methods in elastic optical networks}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
The introduction of flexible frequency grids and advanced modulation techniques to optical transmission, namely an elastic optical network, requires new routing and spectrum allocation techniques. In this paper, we investigate dynamic two-step routing and spectrum allocation (RSA) methods for elastic optical networks. K-shortest path-based methods as well as spectrum allocation methods are analysed and discussed. Experimental verified of the investigated techniques is provided using simulation software. Based on the obtained experimental results, it can be seen that effectiveness of routing and spectrum allocation methods depend on network topologies. Moreover, performance of shortest path first methods improves considerably when a number of candidate paths increases in a topology with high nodal degree.
\end{abstract}

\begin{IEEEkeywords}
elastic optical network, routing and spectrum allocation, dynamic two-step RSA method 
\end{IEEEkeywords}


\IEEEpeerreviewmaketitle



\section{Introduction}
\IEEEPARstart{E}{lastic} optical networks (EONs) have been introduced as flexible and heterogeneous networks to replace Wavelength Division Multiplexing (WDM) networks \cite{Gerstel2012}. Since then, they are widely investigated and developed \cite{Gerstel2012,Christodoulopoulos2011,Jinno2009,Talebi2014,Zhang2012a}. EONs also referred to as SLICEs (Spectrum-Sliced Elastic Optical Path Networks \cite{Jinno2009}) have been proposed to meet requirements of Future Internet such as elastic access to spectral resources and elastic spectrum allocation. 

\begin{figure}[h]
	\begin{center}
		\includegraphics[width=0.9\linewidth]{Figures/eonSpectrum}
		 \end{center}
				\caption{An example of EON optical spectrum.}\label{fig:eon}
					\end{figure}
				
In order to achieve such elastic access, a frequency slot (FS) is introduced as the unit dividing optical spectrum resources. The ITU-T standardization \cite{Itu-T2012} defines a slot granularity of 6.25~GHz, 12.5~GHz, 25~GHz. The width of this FS corresponds to the bandwidth of an orthogonal frequency-division multiplexing (OFDM) subcarrier. In optical OFDM techniques, multiple parallel subcarriers serve high-speed data transmission \cite{Djordjevic2006}. As a result, optical connections employ different modulation formats and occupy such amount of frequency slots as need. Figure~\ref{fig:eon} shows elastic optical spectrum with different-sized connections \cite{Gerstel2012}. 
			
In EON, to set up an optical connection between pair nodes, a routing and spectrum allocation (RSA) problem needs to be solved. Such a solution known as routing and spectrum allocation method must satisfy the following constraints\cite{Christodoulopoulos2011,Velasco2012}: \emph{Spectrum continuity constraint}: the connection must allocate the same set of FSs along links of an end-to-end path; \emph{Spectrum contiguousness constraint}: all slots assigned to a connection should be adjacent; \emph{Non-overlapping spectrum constraint}: at the same time, at most one connection occupies spectrum of links; \emph{Transmission distance constraint}: the length of an end-to-end path, that uses a modulation format, cannot be longer than the maximum transmission distance of this modulation format; \emph{Guard band constraint}: two neighbour connections must be separated by guard band.

To satisfy all constraints, RSA methods have been proposed for both static \cite{Christodoulopoulos2011,Wang2011,Velasco2012} and dynamic scenarios \cite{Zhang2012a,Zhu2013,Olszewski} Considering dynamic nature of Internet traffic, dynamic RSA methods are of greater importance than static ones. In EON, dynamic different-sized allocation and de-allocation of resources generate unusable gaps between occupied FSs. In the worst case non-contiguous and partitioned spectral resources lead to blocking of connection requests and even though the resources exist, the network cannot handle further requests. Therefore, it is important that dynamic RSA methods minimize bandwidth blocking probability. In this work, we focus on dynamic RSA methods applied in EONs.

One type of such dynamic solutions are two-step RSA methods widely discussed in the literature. In such approach, the first step is to search and select a feasible path for a connection request. Then, in the second step optical resources are allocated along this path. The classification of RSA methods with theoretical description including two-step approach can be found in \cite{Zhang2012a,Talebi2014,Chatterjee2015a}, whereas numerical results in \cite{Sone2011,Takagi2010,Zhu2013,Zhang2013,Rosa2012}.

In this paper we present investigation of dynamic two-step RSA methods in elastic optical networks. According to dynamic two-step RSA methods,  improperly selected routing methods as well as spectrum allocation methods can increase bandwidth blocking probability. Usually, first numerical results only for routing strategies have been presented and then they are analysed in spectrum allocation policies. For example, in \cite{Zhang2013} the authors have proposed a routing method selecting a path with the lowest link utilization, while in \cite{Chatterjee2015} the authors have summarized and compared four spectrum allocation strategies including first-fit, exact-fit etc. 

The objective of this paper is to provide the numerical results for both steps. We extend the simulation experiments described in \cite{Zhu2013,Zhang2013} to show spectrum efficiency of routing methods. The computational complexity of the investigated methods was not taken into consideration. Therefore, a number of candidate paths for shortest path first methods was greater in respect to other methods. Finally, the results obtained from simulation of two different topologies show that  performance of spectrum allocation policies depends on network topologies.

The paper is organized as follows: in section \ref{sec:rsa} selected implementation methods are presented; in section \ref{sec:Exper} simulation setup is described; in section \ref{sec:Results} the numerical results are shown and discussed while section \ref{sec:Conclusion} concludes and summarises the paper.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\section{Two-step RSA }\label{sec:rsa}
In this section, we describe two-step RSA strategies selected for investigation. We take into consideration the most common k-shortest path-based methods for a routing step. The advantage of such methods is  low computation complexity. 

In the routing step, when a new connection request ${BW_{req}}$ arrives, candidate paths are sorted and organized based on a path selection policy. Then starting from the top of ordered paths, each one is being analysed. To serve a connection along a path, a number \emph{N} of FSs is required according to ${BW_{req}}$ and applied modulation format. Thus analysis of path covers calculation and search for available set of \emph{N} FSs. If available path is found for allocation, the routing step is stopped and a spectrum allocation step is triggered for this path.

Finally, a spectrum allocation policy selects an available set of \emph{N} FSs as well as assigns the request along the path. If the routing step does not find resources for a given request, this request is blocked. Since a particular k-shortest path-based method is defined by a specific path selection policy, we focus on investigating path selection policies. Next sections present strategies selected for the routing step and for the spectrum allocation step respectively.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Routing}	
In this paragraph, a brief description of path selection policies is provided. First, methods proposed in the literature are presented. Secondly, a strategy with path re-ordering is introduced. We investigate following methods:

Shortest Path First (SPF) method \cite{Zhang2013,Zhu2013} sorts paths in an ascending order based on physical length. Next, paths are checked one by one.

Most Slots First (MSF) method \cite{Zhang2013,Zhu2013} introduces a metric \emph{metric\_MSF} defined as the sum of free FSs along path links. For each path, \emph{metric\_MSF} is calculated and then paths are sorted in the descending order based on \emph{metric\_MSF}. As can be seen, this method considers the link utilization. As a result, the network load is distributed in a load-balanced way. However, the allocation along selected path can consume more resources than other candidate paths. 

Largest Slots-over-Hops First (LSoHF) method \cite{Zhang2013,Zhu2013} calculates a metric \emph{metric\_LSoHF} defined as the ratio of free resources along a path to a number of included links \emph{hops}. After calculating \emph{metric\_LSoHF} for each path, all candidates are sorted in a decreasing value of \emph{metric\_LSoHF}. Note that, ${metric\_LSoHF=metric\_MSF/hops}$. Therefore, selected path has lower number of hops than MSF and LSoHF consumes less resources.

In the MSF with path re-ordering (reMSF) method, a new metric \emph{metric\_reMSF} is introduced for change path orders. This metric considers the ratio of \emph{metric\_MSF} divided by the highest modulation format in terms of bit per symbol \emph{M}, supported by path. Thus for each path $metric\_reMSF=metric\_reMSF/M$ is calculated. Next, paths are sorted in increasing order based on \emph{metric\_reMSF}. The major goal of the reMSF method is to guarantee lower spectrum utilization than the MSF method. This can be achieved by allocating less congested path than SPF and allocating shorter path than MSF.

For better understanding of the difference between MSF and reMSF methods, let assume five candidate routing paths: \emph{p1, p2, p3, p4, p5} with the following parameters for request. Path lengths are: $l1<l2<l3<l4<l5$ and the modulation format using by \emph{p1, p2, p3} is the same and higher than by \emph{p5, p4}. Paths: \emph{p4, p5} adopt the same modulation format. Calculated metrics \emph{metric\_MSF} are: $\emph{metric\_MSF5}>\emph{metric\_MSF4}>\emph{metric\_MSF3}>\emph{metric\_MSF2}>\emph{metric\_MSF1}$. The SPF method checks candidate paths in the following order: \emph{p1 p2 p3 p4 p5}, the MSF method: \emph{p5 p4 p3 p2 p1} and the reMSF method: \emph{p3 p2 p1 p5 p4}. 

Note that methods such as MSF, LSoHF, reMSF consider metrics calculated on-line and varied during network operating. For instance, link utilization is varied during simulation. The MSF and LSoHF methods have been proposed to spread traffic over a network.
%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Spectrum Allocation}	
As a second step, spectrum allocation (SA) method selects a set of \emph{N} contiguous FSs along determined path \emph{p} since more than one such set can exist. Thus the spectrum allocation policy answers the question of how to choose the set of FSs across specific links. Here, we investigate first-fit, exact-fit and best-fit SA policies. Beforehand term spectral void need to be explained. The void is a free range of spectrum between existing optical connections. The size of such void in terms of number of FSs is especially considered by exact-fit and best-fit policies.

The simplest and often implemented spectrum allocation policy is a first-fit (FF) policy \cite{Zhu2013,Zhang2013,Rosa2012,Chatterjee2015}. This policy allocates a request in the first found available set of \emph{N} FSs along a path. 

Exact-fit (EF) policy searches \emph{N}-sized voids between existing connections firstly \cite{Rosa2012,Chatterjee2015}. If \emph{N}-sized void is found, the EF policy allocates the first free \emph{N}-sized void, otherwise the first-fit policy is used. 

Best-fit (BF) policy \cite{Zhang2013} considers voids with size equal or bigger than required \emph{N}. The first smallest one is allocated. In this way, bigger voids are left for future requests. In \cite{Rosa2012} the BF policy has been proposed as a smallest-fit policy. 

The above presented two-step RSA methods are investigated in terms of performance -- first performance of routing strategies, and then performance of spectrum allocation policies.
 \begin{figure*}[t] %\centering \footnotesize
	\begin{center}
	\includegraphics[width=0.6\linewidth]{Figures/NSF15net}
	\end{center}
	\caption {NSF15 topology used  for simulations with marked the link distances in kilometres.}
	 \label{fig:nsfNet}
	\end{figure*}
				\begin{figure*}[t] %\centering \footnotesize
\begin{center}
  \includegraphics[width=0.7\linewidth]{Figures/UBN24net}
	\end{center}
	\caption{ UBN24 topology (link distances in km).}
			 \label{fig:ubnNet}
\end{figure*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

\section{Simulation setup}\label{sec:Exper}
In this section, considered metrics are explained, next simulation model is introduced and necessary assumptions for the experiment are described.  

In order to investigate both routing and spectrum allocation we considered a bandwidth blocking probability (BBP) as a measure of performance. The metric BBP is a ratio of bandwidth of rejected requests to the total requested bandwidth. Additionally, we reported spectrum utilization ratio (SUR) for routing strategies. SUR defines the average number of occupied FSs to all network resources.

In order to provide elastic transmission in EON in terms of access to spectral resources and bandwidth allocation parameters such as frequency grid and slot capacity are of importance. In experiments, we used two reference network topologies: NSF15 with 15 nodes and 46 directed links, UBN24 with 24 nodes and 86 directed links. Note that, in NSF15 the average nodal degree is equal 3.0, whereas in UBN24 is 3.5. NSF15 topology used for simulation is presented in Fig.~\ref{fig:nsfNet} while UBN24 topology in Fig.~\ref{fig:ubnNet}. Spectrum of each link was divided into 300 frequency slots, each having width of 12.5~GHz \cite{Itu-T2012}. To separate neighbour connections, one FS was used as guard band (GB).

To achieve elastic spectrum allocation, we considered four modulation formats: BPSK (binary phase-shift keying), QPSK (quadrature phase-shift keying), 8QAM (8-quadrature amplitude modulation), 16QAM (16-quadrature amplitude modulation) as in \cite{Zhu2013,Zhang2013}. Each modulation format can be characterized by \emph{M} bits per symbol and the maximum supported transmission distance. Similarly as in \cite{Bocoi2009}, we assumed transmission distances of 9600~km for BPSK $(M=1)$, 4800~km for QPSK $(M=2)$, 2400~km for 8QAM $(M=3)$ and 1200~km for 16QAM $(M=4)$. For a given path length, the highest usable modulation format was chosen.

Connection requests were uniformly distributed among all nodes. Requested bandwidth $BW_{req}$ was randomly selected between 10~Gb/s and 200~Gb/s with uniform distribution. The number \emph{N} of FSs required for $BW_{req}$ along the routing path \emph{p} was calculated according to equation (\ref{eq:1}):
 
  \begin{equation} \label{eq:1}
	N=\lceil\frac{{BW_{req}}}{M_{p}*C_{FS}}\rceil+{GB}
\end{equation}

where: $BW_{req}$ is the requested bandwidth of connection in Gb/s; $M_{p}$ denotes modulation format in terms of bit per symbol adapted by path; $C_{FS}$ is the capacity of FS employing BPSK, equal to 12.5~Gb/s; ${GB}$ is the number of FSs for guard band. All parameters used in simulation are summarized in Table \ref{table_param}. 

\begin{table}[h]
\renewcommand{\arraystretch}{1.3}
\caption{Network parameters selected for simulations.}
\label{table_param}
\centering
\begin{tabular}{l|c}
\hline
Parameter & Value\\
\hline \hline
NSF15 & 15 nodes and 46 links\\
UBN24 & 24 nodes and 86 links\\ 
Number of FSs per link & 300\\
Width of FS & 12.5~GHz\\
Guard band & 1\\
$C_{FS}$ & 12.5~Gb/s\\
$BW_{req}$ & 10-200~Gb/s\\
\hline
Trans. distance of BPSK (M=1)& 9600~km\\
Trans. distance of QPSK (M=2)& 4800~km\\
Trans. distance of 8QAM (M=3)& 2400~km\\
Trans. distance of 16QAM (M=4)& 1200~km\\
\hline
\end{tabular}
\end{table}
 
Requests arrive one by one in the Poisson process with arrival rate $\lambda$ and a negative exponential distributed holding time with $1/\mu$. Therefore, traffic load could be defined as $\lambda/\mu$~Erlangs. For each value of traffic load, first 5000 requests were not considered, due to the network not being in steady-state.  After that, next $10^6$~requests were evaluated. For each point, simulation was repeated 30~times. 95\% confidence intervals were calculated using normal distribution and appropriately marked in all figures. Simulation experiments were carried using a discrete event simulator OMNeT++ \cite{omnet}. 

To simplify calculations, we assumed pre-computed k-shortest paths in the initialization phase. In routing investigation, we used set of candidate paths with k=5 for methods: MSF, LSoHF, reMSF as in \cite{Zhu2013,Zhang2013}. Additionally, we used k=10 and k=15 candidate paths for SPF methods. Whichever routing method is used, first fit policy allocates optical resources. In spectrum allocation investigation shortest path first method with k=3 and k=5 candidate paths realises the routing step.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\section{Simulation results} \label{sec:Results}
Two network topologies were investigated, i.e. NSF15 and UBN24 and for each of them we present simulation results of different routing methods. The obtained results are then compared to provide insight and evaluate performance of SA policies.

\subsection{Routing step}
\begin{figure}[h]
	\begin{center}
		\includegraphics[width=0.9\linewidth]{Plots/bbpNSF}
		 \end{center}
				\caption{Bandwidth blocking probability vs. traffic load for routing strategies using first-fit in NSF15.}
				\label{fig:bbpNSF10}
	\end{figure}
	
\begin{figure}
	\begin{center}
		\includegraphics[width=0.9\linewidth]{Plots/utilNSF}
		 \end{center}
		 		\caption{Spectrum utilization ratio vs. traffic load for routing strategies using first-fit in NSF15.}
				\label{fig:utilNSF10}
	\end{figure}	
	
\begin{figure}[h]
	\begin{center}
		\includegraphics[width=0.9\linewidth]{Plots/bbpUBN}
		 \end{center}
				\caption{Bandwidth blocking probability vs. traffic load for routing strategies using first-fit in UBN24.}
				\label{fig:bbpUBN10}
	\end{figure} 
		
 \begin{figure}[h]
	\begin{center}
		\includegraphics[width=0.9\linewidth]{Plots/utilUBN}
		 \end{center}
				\caption{Spectrum utilization ratio vs. traffic load for routing strategies using first-fit in UBN24.}
				\label{fig:utilUBN10}
	\end{figure}
	
Simulation results of BPP vs. traffic load and SUR vs. traffic load for NSF15 topology are given in Fig.~\ref{fig:bbpNSF10} and Fig.~\ref{fig:utilNSF10}, respectively while for UBN24 topology in Fig.~\ref{fig:bbpUBN10} and Fig.~\ref{fig:utilUBN10}.

Analysing results for the NSF15 topology,  it can be seen, that the  LSoHF method achieves  the lowest bandwidth blocking probability (see Fig.~\ref{fig:bbpNSF10}) compared to all other routing strategies. The BBP for reMSF is four times higher than MSF.  However, for traffic load above 2.3~Erlangs, the BBP for MSF and reMSF becomes similar.  Also, we can observe that the increasing number of candidate paths does not improve performance of the SPF method, even if k=15 candidate paths are used.

Observing results for spectrum utilisation ratio (see Fig. \ref{fig:utilNSF10}), it can be seen that for all studies the MSF method has the highest value among all routing methods. The lowest SUR for the LSoH method only confirms the results provided by \cite{Zhu2013,Zhang2013}. For SPF methods, we can also observe that when the traffic load is light, SUR of each method is very similar. However, for traffic load greater than approx. 1.8~Erlangs, the observed SUR of SPF(5) is lower than SPF(10) and SPF(15) and have gentler slope. Such property for SPF(5) is related to higher BBP (see Fig.~\ref{fig:bbpNSF10}).

Analysis of the obtained results for the UBN24 topology shows that for the reMSF method bandwidth blocking probability (see Fig.~\ref{fig:bbpUBN10}) provides the lowest BBP compared to another methods. For the reMSF method, the highest reduction of BBP is the most noticeable between 0.4 and 0.5~Erlangs.  Also, for this traffic gap BBP is very similar for SPF(15) and MSF methods.  Moreover, for traffic load greater than 0.5 Erlangs, values of BBP for methods: SPF(15), reMSF and LSoHF becomes very similar. Compared with MSF, reMSF reduces BBP by 16\%. Compared with the MSF method, SPF(15) reduces BBP by 11\%.

It can be seen based on Fig.~\ref{fig:utilUBN10} that MSF method has the highest spectrum utilization ratio, despite the fact that BBP of MSF is higher than for reMSF, SPF(15) and LSoHF. Compared with MSF, the reMSF method reduces SUR by 6\%. Detailed analysis of values of SUR for the SPF methods follow the similar trend of results as in NSF15. 

Summarizing the above presented studies, the SPF(5) method presents the worst performance for all studies of both topologies. For more detail,  please refer to \cite{Zhu2013,Zhang2013}. The obtained results show that LSoHF method might be the best choice for transmission in the NSF15 topology, whereas the reMSF method in UBN24. Since more paths are considered in the UBN24 topology, better performance can be obtained by the SPF strategy. In this case, i.e. greater number of paths, the computational complexity of methods is not considered.

Based on the obtained results for this part of the experiment, it is seen that the reMSF method achieves better spectral efficiency in the UBN24 topology than NSF15. The explanation for such phenomena can be that the UBN24 topology is relatively better balanced in terms of the node connectivity.  In such topology, the reMSF method can select a path, that is less congested than a path selected by SPF. On the other hand, the path selected by the reMSF method is shorter than the MSF method. As a result,  reMSF spreads traffic over a network.
 
\subsection{Results: Spectrum Allocation}
As second part of the experiment, we compare the performance of different spectrum allocation methods such as: first-fit, exact-fit, best-fit. To determine routing path, we use SPF methods with k=3 and k=5 candidate paths. 

Bandwidth blocking probability vs. traffic load was investigated and results for different SA methods in the NSF15 topology are shown in Fig.~\ref{fig:bbp2NSF10} while in UBN24 in Fig.~\ref{fig:bbp2UBN10}. The mean values of BBP for spectrum allocation policies are summarized in Table~\ref{sa_result}.
 
\begin{figure}[h]
	\begin{center}
		\includegraphics[width=0.9\linewidth]{Plots/bbp2NSF}
		 \end{center}
				\caption{Bandwidth blocking probability vs. traffic load for spectrum allocation methods in NSF15.}
				\label{fig:bbp2NSF10}
	\end{figure}
	
		\begin{figure}[h]
	\begin{center}
		\includegraphics[width=0.9\linewidth]{Plots/bbp2UBN}
		 \end{center}
	\caption{Bandwidth blocking probability vs. traffic load for spectrum allocation methods in UBN24.}
				\label{fig:bbp2UBN10}
	\end{figure}
	
	\begin{table}[t]
	\renewcommand{\arraystretch}{1.3}
	\caption{Mean value of BBP for slot allocation methods.}
	\label{sa_result}
	\centering
	\begin{tabular}{|c|c|c|c|}
		\hline
		Method& NSF15 & UBN24\\
		\hline
		SPF(3)FF & 0.0195 $\pm$ 0.0005 & 0.0434 $\pm$ 0.0006\\
		\hline
		SPF(3)EF & 0.0175 $\pm$ 0.0004 & 0.0435 $\pm$ 0.0005\\
		\hline
		SPF(3)BF & 0.0174 $\pm$ 0.0002 & 0.0454 $\pm$ 0.0006\\
		\hline
		SPF(5)FF & 0.0105 $\pm$ 0.0004 & 0.0322 $\pm$ 0.0005\\
		\hline
		SPF(5)EF & 0.0091 $\pm$ 0.0002 & 0.0328 $\pm$ 0.0006\\
		\hline
		SPF(5)BF & 0.0090 $\pm$ 0.0001 & 0.0343 $\pm$ 0.0009\\
		\hline
			\end{tabular}
\end{table}
		
As seen from Fig.~\ref{fig:bbp2NSF10}, the first-fit policy provides the worst performance compared to another SA policies in NSF15.  The best-fit policy achieves the best performance in terms of  reduction BBP compared with exact-fit and first-fit. The observed values of BBP (see Table~\ref{sa_result}) are similar for BF and EF. This means that, the best-fit and exact-fit policies select the same voids for allocation. This can be explained that, voids being equal to requested number of FSs exist along routing paths.

Next, we can observe that, the number of candidate paths does not change the ranking best to worst performance order between different SA methods, e.g. for k=3 candidates the lowest BBP achieves the best-fit policy, next exact-fit, the highest BBP -- first-fit.

In contrary to NSF15, the results for UBN24 results revealed that the best performance is obtained for the first-fit policy (see Fig.~\ref{fig:bbp2UBN10}). This can be attributed to the fact that the UBN24 topology has higher average nodal degree than NSF15. A larger number of different link paths increase the opportunity for finding allocation with starting index of FS close to earlier allocation.  

As seen from Table \ref{sa_result}, the values of BBP for the EF policy are very similar to ones for the FF policy for the UBN24 topology. Such phenomena can be explained that, lack of voids with size equal to required number of FSs leads the exact-fit policy to allocate resources according to a first-fit manner. Similarly as in case of the NSF15 topology, in UBN24 the available number of candidate paths does not influence the order of methods in terms of performance.

Moreover, the obtained results showed that, the best performance of the first fit policy in one network topology does not guarantee the same results in terms of reduction BBP in another topology.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\section{Conclusion}\label{sec:Conclusion}
This paper have investigated the performance of two-step dynamic routing strategies and spectrum allocation policies in elastic optical networks. Accordingly, in the first step the k-shortest path-based strategies have been implemented, whereas three slot allocation policies have been applied for the second step. Presented methods have been evaluated by means of numerical simulations using the Poisson traffic model and two different network topologies.

The obtained simulation results have separately verified the performance of routing and spectrum allocation methods in terms of effective reduction of bandwidth blocking probability. Neglecting computation complexity, it has been found that the growing number of candidate paths can improve performance of shortest path method in topology with higher nodal degree. In network with high nodal degree, the change of ordering paths for MSF also has improved the performance. Finally, the obtained experimental results have shown that the performance of SA policy depends on network topology. This observation may stimulate further research to consider scenarios with different network topologies.  In future, we investigate performance of methods using anycast transmission.



% use section* for acknowledgement

%\section*{Acknowledgment}

%The authors would like to thank...
\section*{Acknowledgment}
This research was carried out with the support of the project "High quality, reliable transmission in multilayer optical networks based on the Flow-Aware Networking concept" founded by the Polish National Science Centre under the project no. DEC-2011/01/D/ST7/03131.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\bibliography{Bibliography/bibliography}

\bibliographystyle{IEEE_class/IEEEtran}

%\begin{thebibliography}{99}

\balance
%REFERENCES

%\end{thebibliography}


\end{document}
